# SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant

arXiv: https://arxiv.org/abs/2608.05127 · HTML: https://mlsanity.com/paper/2608.05127/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 31 references that are in the map.
- First posted on arXiv 5 Aug 2026.

## Builds on (most cited first, 20 of 20)

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Federated Learning: Challenges, Methods, and Future Directions](https://mlsanity.com/paper/1908.07873/) (2019)
- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences](https://mlsanity.com/paper/1807.01647/) (2018)
- [Protection Against Reconstruction and Its Applications in Private Federated Learning](https://mlsanity.com/paper/1812.00984/) (2018)
- [TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate](https://mlsanity.com/paper/2504.19874/) (2025)
- [Breaking the Communication-Privacy-Accuracy Trilemma](https://mlsanity.com/paper/2007.11707/) (2020)
- [EDEN: Communication-Efficient and Robust Distributed Mean Estimation for Federated Learning](https://mlsanity.com/paper/2108.08842/) (2021)
- [DRIVE: One-bit Distributed Mean Estimation](https://mlsanity.com/paper/2105.08339/) (2021)
- [RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2405.12497/) (2024)
- [Optimal Algorithms for Mean Estimation under Local Differential Privacy](https://mlsanity.com/paper/2205.02466/) (2022)
- [Joint Privacy Enhancement and Quantization in Federated Learning](https://mlsanity.com/paper/2208.10888/) (2022)
- [SoteriaFL: A Unified Framework for Private Federated Learning with Communication Compression](https://mlsanity.com/paper/2206.09888/) (2022)
- [Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation](https://mlsanity.com/paper/2304.01541/) (2023)
- [Correlated quantization for distributed mean estimation and optimization](https://mlsanity.com/paper/2203.04925/) (2022)
- [Fast Optimal Locally Private Mean Estimation via Random Projections](https://mlsanity.com/paper/2306.04444/) (2023)
- [Breaking The Dimension Dependence in Sparse Distribution Estimation under Communication Constraints](https://mlsanity.com/paper/2106.08597/) (2021)
- [Improved Communication-Privacy Trade-offs in L2 Mean Estimation under Streaming Differential Privacy](https://mlsanity.com/paper/2405.02341/) (2024)
- [Correlation Aware Sparsified Mean Estimation Using Random Projection](https://mlsanity.com/paper/2310.18868/) (2023)
- [Collaborative Compressors in Distributed Mean Estimation with Limited Communication Budget](https://mlsanity.com/paper/2601.18950/) (2026)

## Abstract (arXiv)

Achieving local differential privacy in distributed optimization while maintaining low communication cost remains challenging. Existing vector quantization methods, such as vqSGD, rely on high-dimensional geometric constructions but incur unfavorable dimension-dependent variance. In this work, we propose Subsampled Stochastic TurboQuant (SSTQ), a framework that combines a bounded Kashin representation, data-independent coordinate subsampling, and privacy-aware one-dimensional quantization. SSTQ includes two variants: (1) a Flat Randomized Response variant that is unbiased and, for a fixed codebook bit-width, frame redundancy, and dimension-independent Kashin level, achieves reconstruction MSE that scales linearly with the ambient dimension d, while using only lceil log2 N rceil + b bits per message. Here, N = Theta(d) denotes the frame size in the Kashin transform and b is the codebook bit-width; and (2) a metric-aware truncated-Laplace variant that removes the exponential dependence on bit-width at the cost of a non-vanishing bias. We also derive a convex uniform-surrogate codebook objective whose worst-case codebook-dependent upper bound improves from O(4b) to O(2b). Experiments on synthetic regression, Fashion-MNIST, and CIFAR-10 compare the per-message privacy-utility and uplink-communication trade-offs of SSTQ with those of established baselines, demonstrating favorable utility and communication efficiency.