SSTQ: Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant

The paper introduces Subsampled Stochastic TurboQuant (SSTQ), a privacy-preserving vector quantization framework for distributed optimization. It combines overcomplete equal-norm tight frames, coordinate subsampling, and privacy-aware one-dimensional quantization. SSTQ provides a Flat Randomized Response variant and a Metric-Aware Laplace variant, with the latter targeting higher codebook bit widths. The authors derive optimal mean-squared-error scaling with ceil(log2 N)+b bits per client, where N=Theta(d), and propose a surrogate codebook objective that reduces codebook-dependent MSE scaling from O(4^b) to O(2^b). Experiments on federated CIFAR-10 and Fashion-MNIST report favorable utility and communication efficiency against established baselines.