SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant

[Submitted on 5 Aug 2026 (v1), last revised 7 Aug 2026 (this version, v2)]

View PDF HTML (experimental)

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 = Theta(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.
Some of the analytical derivations were first obtained using a fully automated Gemini-based agentic system developed internally at Google. The authors have verified those derivations and edited them for clarity of presentation.

Submission history

From: Adel Javanmard [view email]
[v1] Wed, 5 Aug 2026 17:51:25 UTC (1,244 KB)
[v2] Fri, 7 Aug 2026 01:49:17 UTC (1,245 KB)