SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant

Achieving local differential privacy (LDP) in distributed optimization at low communication cost remains challenging: existing vector quantization methods such as vqSGD rely on high-dimensional geometric constructions and incur unfavorable dimension-dependent variance. We propose Subsampled Stochastic TurboQuant (SSTQ), combining a bounded Kashin representation, data-independent coordinate subsampling, and privacy-aware one-dimensional quantization. SSTQ has two variants: (1) a Flat Randomized Response variant that is unbiased and, for fixed codebook bit-width $b$, frame redundancy, and dimension-independent Kashin level, achieves reconstruction MSE linear in the ambient dimension $d$ using only $\lceil {\log }_{2}N\rceil +b$ bits per message, where $N=\Theta (d)$ is the Kashin frame size; and (2) a metric-aware truncated-Laplace variant that removes the exponential bit-width dependence at the cost of a non-vanishing bias. We also derive a convex uniform-surrogate codebook objective whose worst-case codebook-dependent bound improves from $\mathcal{O}(4^b)$ to $\mathcal{O}(2^b)$. Experiments on synthetic regression, Fashion-MNIST, and CIFAR-10 compare the per-message privacy–utility and uplink-communication trade-offs of SSTQ against established baselines, demonstrating favorable utility and communication efficiency.