SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant
2026-08-05 • Machine Learning
Machine LearningArtificial Intelligence
AI summaryⓘ
The authors address the problem of keeping data private when many users work together to optimize machine learning models, without using too much communication. They introduce a new method called Subsampled Stochastic TurboQuant (SSTQ), which cleverly combines mathematical frames, selecting parts of data, and privacy-aware quantization to reduce errors. SSTQ has two versions tailored for different communication settings and achieves better efficiency in terms of error and data size than previous methods. Their experiments on image classification tasks show that SSTQ works well compared to existing approaches.
local differential privacydistributed optimizationvector quantizationtight framescoordinate subsamplingrandomized responseLaplace mechanismmean squared errorfederated learningcommunication efficiency
Authors
Adel Javanmard, David P. Woodruff, Vahab Mirrokni
Abstract
Achieving local differential privacy in distributed optimization while maintaining low communication cost remains challenging. Existing vector quantization methods, such as vqSGD, use high-dimensional geometric constructions but incur unfavorable dimension-dependent variance. In this work, we propose Subsampled Stochastic TurboQuant (SSTQ), a framework that combines overcomplete equal-norm tight frames, coordinate subsampling, and privacy-aware one-dimensional quantization. SSTQ includes two variants: a Flat Randomized Response version and a Metric-Aware Laplace version, the latter being better suited to higher codebook bit-width regimes. We show that SSTQ achieves optimal mean squared error scaling while using only $\lceil \log_2 N \rceil + b$ bits per client, where $N = Θ(d)$ is the frame size. We also derive a surrogate privacy-aware codebook objective that reduces the codebook-dependent MSE scaling from $O(4^b)$ to $O(2^b)$. Finally, we empirically evaluate SSTQ against established baselines on federated learning tasks using CIFAR-10 and Fashion-MNIST, demonstrating favorable utility and communication efficiency.