SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant
Abstract
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 ⌈ log2 N ⌉ + b bits per message. Here, N = Θ(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.
Related
- Toward Human-Perceptive 6G: Privacy-Preserving Network Intelligence from Human Dynamics
- Privacy Preserving Gossip Learning
- Privacy-Preserving Causal Meta-Mediation Analysis with Survival Outcomes
- Design of Privacy-Preserving Estimators Under Prior Information Exposure
- Privacy-Preserving Distributed Online Dispatch of Low-Carbon Microgrids with TCN–BiLSTM Probabilistic Photovoltaic Forecasts
BibTeX
@misc{javanmard2026sstqprivacypreserving,
title = {{SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant}},
author = {Adel Javanmard and David P. Woodruff and Vahab Mirrokni},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.05127},
eprint = {2608.05127},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.05127},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant
AU - Adel Javanmard
AU - David P. Woodruff
AU - Vahab Mirrokni
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2608.05127
UR - https://arxiv.org/abs/2608.05127
AB - 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 ⌈ log_2 N ⌉ + b bits per message. Here, N = Θ(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(4^b) to 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 with those of established baselines, demonstrating favorable utility and communication efficiency.
ER -