SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant

The paper addresses the fundamental tension between two objectives in federated learning: communication efficiency and strong privacy guarantees. As the authors state: "The communication bottleneck in federated learning (FL) and large-scale distributed optimization has led to significant interest in gradient compression techniques. At the same time, protecting sensitive client data against adversarial or untrusted aggregators necessitates the use of Local Differential Privacy (LDP). These two objectives—communication efficiency and strong privacy guarantees—are inherently at odds. Compression reduces high-dimensional continuous signals to compact discrete representations, while LDP requires adding noise and maintaining sufficient support over the same space to ensure plausible deniability."

The authors identify three existing paradigms with distinct limitations: (1) geometric quantization methods such as vqSGD, which encode vectors using structured high-dimensional polytopes and apply randomized response over the resulting discrete set but suffer from unfavorable variance scaling, which can grow cubically with the dimension; (2) methods achieving optimal variance scaling under LDP such as SQKR and PrivUnit, which attain the information-theoretic limit of O(d/ϵ2) but either impose restrictive communication constraints—such as 1-bit quantization and shared randomness in SQKR—or require transmitting dense, uncompressed vectors, as in PrivUnit; and (3) data-oblivious quantization methods like TurboQuant, which are highly effective for compression but do not provide privacy guarantees and can suffer from directional bias when combined with naive privatization schemes.

The authors propose Subsampled Stochastic TurboQuant (SSTQ), a framework that combines overcomplete equal-norm tight frames, coordinate subsampling, and privacy-aware one-dimensional quantization. The framework decouples the codebook size M from the ambient dimension d by combining overcomplete tight frames, data-oblivious coordinate subsampling, and one-dimensional stochastic quantization.

The algorithmic pipeline works as follows: the client first performs Redundant Kashin Bounding by executing Lyubarskii's algorithm to find a coefficient vector y with bounded infinity norm (∥y∥∞ ≤ B = K/√N). Then Oblivious Subsampling uniformly samples an index j independent of the data and extracts the scalar coordinate yⱼ. Next, Strict Stochastic Interpolation stochastically rounds yⱼ to a discrete token v via exact linear interpolation between adjacent codebook bounds. Finally, either Flat Randomized Response (applying pure ϵ-LDP over the M elements of the codebook) or a Metric-Aware Laplace mechanism introduces privacy noise. The client transmits the tuple (j, index of z) at a cost of ⌈log2N⌉ + b bits.

Optimal MSE scaling with logarithmic communication. The authors prove that SSTQ achieves the O(d/(1 ∧ ϵ ∧ ϵ2)) variance scaling, which is the optimal rate for the ϵ = O(1) regime, while requiring only ⌈log2N⌉ + b bits per client in a private-coin setting, where N = Θ(d) is the frame size. Theorem 3.1 establishes that The SSTQ with flat randomized response... satisfies pure ϵ-Local Differential Privacy. Furthermore, the decoding algorithm... returns an unbiased estimator, E[x̂] = x. Theorem 3.2 bounds the MSE as MSESSTQ < d2K2/(N(p-q)2) = O(d(1 + 4b/(ϵ ∧ ϵ2))).

Privacy-aware codebook optimization. The authors derive a surrogate privacy-aware stochastic quantization loss L SSTQ, yielding a convex formulation for codebook design. The surrogate objective is defined as L SSTQ(Γ) = Σ (ck+1 − ck)3/(12B) + (1/(e ϵ − 1)) Σ ci2, subject to anchored Kashin boundaries, ordering constraints, and a zero-sum condition. Theorem 4.2 proves The objective function L SSTQ(Γ) is strictly globally convex and has a unique global minimizer Γ*. Crucially, this optimized codebook reduces the codebook-dependent MSE scaling from O(4b) (worst-case, Theorem 3.2) to O(2b) (Theorem 4.3), an exponential improvement in the base that grows with the codebook bit-width b.

Metric-aware Laplace mechanism. To address the exponential variance growth of Flat Randomized Response at higher bit-widths, the authors propose a mechanism that draws a continuous sample T from a truncated Laplace distribution on [−B, B] centered at ck with density f Tv=ck(t) = (1/Zk)exp(−ϵt−ck/(2∆)), followed by Nearest-codeword quantization setting z = argmin ci∈ΓT − ci. Theorem 5.1 proves this satisfies pure ϵ-LDP via the post-processing theorem. Theorem 5.2 bounds the MSE as MSEMA ≤ (dK2/ρ)(1 + 2C2/(2b−1)2 + 16/ϵ + 256/ϵ2) with bias ζ2 ≤ 64K2/(ρϵ2), where ρ = N/d > 1 is the frame redundancy ratio. The authors note the bias of the estimator is bounded independently of the ambient dimension d and this bound is independent of the discretization bit-width b.

Structural distinction from SQKR. The paper highlights three key differences from prior Kashin-based LDP mechanisms: (1) SSTQ removes the effective bandwidth restriction present in SQKR by allocating the full b-bit budget to a single coordinate; (2) SSTQ replaces 1-bit quantization with a continuous surrogate optimization via stochastic quantization over a multi-bit codebook optimized for the privatized setting; and (3) SSTQ operates as a private-coin protocol with explicit communication cost—"SQKR relies on shared randomness to coordinate subsampling; without it, transmitting indices increases the communication cost... SSTQ directly transmits the sampled index along with the quantized value, resulting in a fixed cost of ⌈log2N⌉ + b bits, independent of shared randomness assumptions."

Optimal bit-width allocation. The paper derives the optimal required codebook dimension by equating the dominant scales: 1/(2b − 1)2 ≍ 1/(ϵ ∧ ϵ2), which yields b = O(⌈log2(ϵ)⌉). This confirms that relatively compressed codebooks are mathematically sufficient to achieve the fundamental operational bounds of the metric-aware mechanism.

Under assumptions of non-convex optimization, bounded statistical variance, bounded compression noise, and bounded bias, the authors prove a general DSGD convergence result (Theorem 6.2): min E[∥∇F(w t)∥2] ≤ 16L∆0/T + 8√(∆0LV)/√T + 2ζ2. For Flat-RR, since the estimator is strictly unbiased (ζ = 0) with variance multiplier ω = O(d·2b/(ϵ ∧ ϵ2)), the rate simplifies to O(1/T + √(d·2b·(ϵ ∧ ϵ2)−1G2 + σ2)/(nT)). For the Metric-Aware variant, with ω = O(d(1 + ϵ−1 + ϵ−2)) and ζ2 = O(G2ϵ−2), the rate includes a bias floor explicitly independent of the massive parameter scale d.

The authors evaluate SSTQ against PrivUnit, vqSGD, and SQKR, in federated learning tasks on CIFAR-10 and Fashion-MNIST using a fully connected neural network with a single hidden layer of 32 units and ReLU activations, operating under pure ε-LDP with per-round ε = 3 and bit budget b = 4 with W = 100 workers and T = 100 communication rounds.

Fashion-MNIST (d = 25,450): "Clean SGD reaches 65.4% and PrivUnit closely tracks at 63.3%. Among quantized methods, SQKR achieves 63.2% using 64 bits per client, while SSTQ (Flat-RR, optimized codebook) achieves 63.3% and SSTQ (Flat-RR, uniform codebook) reaches 62.4%—both using only 20 bits per client, a 3.2× reduction compared to SQKR. vqSGD fails to learn (7.2%, near random chance)."

CIFAR-10 (d = 98,666): "Clean SGD reaches 29.1% and PrivUnit 21.3%. Among quantized methods, SQKR achieves 21.0% (72 bits), followed by SSTQ (Flat-RR, uniform codebook) at 19.7%, SSTQ (Flat-RR, optimized codebook) at 19.1% (both using 22 bits), and SSTQ (Metric-Aware) at 17.7%. vqSGD reaches 10.3% (18 bits)."

Communication advantage: "SSTQ achieves accuracy comparable to SQKR while requiring substantially fewer bits per client. On Fashion-MNIST, SSTQ (Flat-RR, optimized codebook) achieves 63.3%—essentially matching SQKR's 63.2%—while using 3.2× fewer bits (20 vs. 64 bits). On CIFAR-10... a difference of only 2%, while using 3.3× fewer bits (22 vs. 72 bits). PrivUnit, while achieving the best accuracy, requires full-precision transmission (>800K bits), making it impractical for communication-constrained settings."

Variance scaling experiments: In the MSE-versus-dimension experiment (ε = 3, b = 8, M = 256), vqSGD exhibits devastating cubic O(d3/ε2) scaling, with MSE growing from ≈ 561 at d = 100 to ≈ 4.4 × 108 at d = 10,000. Among quantized methods, SSTQ (Metric-Aware) achieves the lowest MSE across all dimensions (≈ 2.0 at d = 100 and ≈ 171 at d = 10,000). The Flat-RR variants show the O(M2) variance inflation from the RR debiasing scalar at large M = 256, with optimized codebooks providing a 7–8× improvement over the uniform variant but still far above the Metric-Aware variant (by 27–30×).

Codebook size ablation: Increasing codebook size from M = 16 to M = 256 at d = 200 causes a dramatic degradation in both Flat-RR variants—SSTQ (Flat-RR, uniform codebook) grows from ≈ 132.8 to ≈ 271.6 (2.0× increase), while SSTQ (Flat-RR, optimized codebook) grows from ≈ 140.5 to ≈ 226.7 (1.6× increase)—consistent with the predicted O(M2) scaling of the unbiasing factor. In contrast, SSTQ (Metric-Aware) remains essentially unchanged, with final error growing only marginally from ≈ 162.0 to ≈ 163.7, demonstrating the decisive advantage of the Metric-Aware Discrete Laplace mechanism in eliminating the exponential 2b dependence.

The authors note: "our approach assumes a predetermined communication budget and a known data range; future work should address practical extensions to highly non-stationary data streams and the design of robust, range-agnostic adaptive mechanisms to further improve real-world deployment flexibility."

Based on the SSTQ framework, here are concrete improvements to AI systems, particularly for federated learning and distributed optimization:

• Communication-efficient private federated learning: AI systems can now achieve strong local differential privacy (LDP) while transmitting only ⌈log2N⌉ + b bits per client update (e.g., 20–22 bits) instead of full-precision vectors (hundreds of thousands of bits) or less efficient compressed private methods. This enables training on bandwidth-constrained networks (e.g., mobile, IoT) with privacy guarantees.

• Optimal variance scaling under LDP: The improved system attains the information-theoretically optimal MSE scaling of O(d/(1 ∧ ϵ ∧ ϵ2)) with logarithmic communication, eliminating the cubic O(d3/ϵ2) variance explosion seen in prior geometric quantization methods like vqSGD. This allows scaling to high-dimensional models (d > 100k) without catastrophic estimation error.

• Unbiased low-variance gradient estimators: With flat randomized response and an optimized codebook, the system produces strictly unbiased estimates of client gradients (E[x̂] = x) with variance O(d·2b/(ϵ ∧ ϵ2)). This enables stable convergence in non-convex optimization, with the same convergence rate as unpricatized SGD up to a mild variance term.

• Exponentially improved codebook design: By solving a convex surrogate loss for codebook boundaries, the AI system reduces privacy-induced distortion from O(4b) to O(2b) in the bit-width b—a quadratic improvement in variance. This allows the same accuracy with smaller codebooks or lower privacy budgets.

• Metric-aware privacy mechanism for flexible bit-widths: The truncated Laplace + nearest-codeword mechanism removes the exponential 2b variance growth entirely, yielding MSE independent of bit-width (bounded by O(1 + 1/ϵ + 1/ϵ2)) with bias bounded independently of dimension. This lets the system scale to high-precision quantization (large b) without paying a privacy penalty—ideal for tasks needing fine-grained updates.

• Decoupling codebook size from dimension: The combination of overcomplete tight frames and coordinate subsampling means the codebook size M no longer depends on the ambient dimension d. AI systems can use the same codebook across a wide range of model sizes, simplifying deployment and hardware implementation.

• Private-coin protocol with fixed communication cost: Unlike SQKR, which relies on shared randomness, SSTQ works in a private-coin setting with explicit, fixed per-client communication. This avoids coordination overhead and makes the protocol easier to deploy in heterogeneous, asynchronous federated systems.

• Predictable convergence guarantees: The convergence analysis provides explicit rates for non-convex objectives: min E[∥∇F(w)∥2] ≤ O(1/T + 1/√T) for the unbiased Flat-RR variant, and a bias floor O(1/ϵ2) for the metric-aware variant. System designers can thus predict training performance given T, ε, and d, and automatically choose the minimal bit-width b = O(log2 ε) that still meets the optimal MSE bound.

• Practical accuracy at a fraction of the bit budget: Empirically, the improved system matches or closely approaches full-precision private baselines (e.g., 63.3% vs. 63.3% for PrivUnit on Fashion-MNIST) while using 3.2× fewer bits than prior state-of-the-art private compression (SQKR) and 40,000× fewer bits than uncompressed PrivUnit. This means real-world FL deployments can preserve accuracy and privacy while drastically reducing bandwidth and energy consumption.

• Robustness to codebook size selection: The metric-aware mechanism is insensitive to codebook redundancy (error changes <1% when M goes from 16 to 256), while flat-RR variants degrade. This allows system designers to choose larger codebooks for richer quantization without worrying about privacy-induced variance blow-up—enabling adaptive precision tuning at runtime.

In summary, the improved AI system can perform privacy-preserving federated learning with near-optimal statistical efficiency, exponentially reduced communication costs, predictable convergence, and robust performance across model dimensions and quantization settings—without requiring shared randomness or full-precision transfers.

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 2 N + 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. 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.