SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant

Source: arXiv:2608.05127 · Published 2026-08-05 · By Adel Javanmard, David P. Woodruff, Vahab Mirrokni

TL;DR

This paper addresses the challenge of achieving local differential privacy (LDP) in distributed optimization and federated learning while maintaining low communication cost and minimal utility loss. Existing vector quantization methods either suffer from dimension-dependent variance scaling or impose high communication overheads. To overcome these limitations, the authors propose Subsampled Stochastic TurboQuant (SSTQ), a novel vector quantization framework that combines overcomplete equal-norm tight frames (ENTFs), coordinate subsampling, and privacy-aware one-dimensional scalar quantization. SSTQ transmits only logarithmic bits in the ambient dimension plus a small codebook bit-width, significantly reducing communication while achieving near-optimal LDP variance scaling.

The core innovation lies in the use of Kashin representations with oblivious coordinate subsampling, enabling a 1-sparse quantization and private transmission of a single coordinate per client. Two variants are developed: a Flat Randomized Response (Flat-RR) providing unbiased decoding and a Metric-Aware Laplace mechanism optimized for higher bit-widths and denser codebooks. The authors rigorously derive privacy proofs, mean squared error (MSE) bounds, and a convex surrogate loss to optimize the quantization codebooks under privacy constraints. Empirically, SSTQ consistently outperforms prior state-of-the-art private vector quantization methods such as vqSGD and SQKR on CIFAR-10 and Fashion-MNIST federated learning tasks, achieving lower error at substantially reduced communication rates.

Key findings

• SSTQ achieves optimal MSE scaling of O(d / min(ε, ε²)) for ε = O(1) regime with communication cost ⌈log₂ N⌉ + b bits per client, where N = Θ(d) is the frame size.
• The privacy-aware codebook optimization reduces codebook-dependent MSE scaling from O(4^b) to O(2^b), exponentially improving with codebook bit-width b (Theorem 4.3).
• Metric-Aware Laplace mechanism variant further reduces variance growth at higher bit-widths, achieving MSE bounded by terms independent of codebook size M=2^b and adding a small dimension-free bias bounded by O(1/ε²) (Theorem 5.2).
• SSTQ removes the shared randomness assumption required by prior works like SQKR, transmitting a fixed cost of ⌈log₂ N⌉ + b bits per client without public-coin protocols.
• Empirically, SSTQ(Flat-RR) and SSTQ(Metric-Aware) outperform vqSGD, SQKR, and PrivUnit baselines in federated learning accuracy, convergence speed, and communication efficiency on CIFAR-10 and Fashion-MNIST (Figures 3, 4).
• Flat Randomized Response variant suffers from variance explosion at larger bit-widths, but this is stabilized by the Metric-Aware Laplace variant (Figure 5).
• SSTQ's codebook optimization using a surrogate uniform distribution yields convex objectives with unique minimizers facilitating practical implementations.
• The theoretical communication cost scales logarithmically with dimension, contrasting cubic or linear dependencies seen in other LDP vector quantizers.

Threat model

The adversary is a central server or aggregator that receives privatized client vectors and attempts to infer individual client data. The adversary has no access to shared randomness or direct client data and is restricted to post-processing privatized messages. The protocol guarantees strict pure ε-local differential privacy, providing plausible deniability for any client input. The adversary cannot break this privacy even with auxiliary side information or auxiliary data.

Methodology — deep read

1. Threat Model & Assumptions: The adversary is an untrusted aggregator receiving privatized client vectors. The protocol ensures strict pure ε-LDP, guaranteeing that the output distributions for any two client inputs are within e^ε multiplicative factors for all measurable events. No assumptions are made on the adversary’s side information, and no trusted parties or shared randomness are required.

2. Data & Preprocessing: The method is agnostic to data distribution, focusing on vectors normalized to the unit sphere Sd-1 in d dimensions. For experiments, federated learning benchmarks CIFAR-10 and Fashion-MNIST are used with standard train/test splits. Vectors represent gradients or model updates.

3. Architecture/Algorithm: The core algorithm uses an overcomplete equal-norm tight frame (ENTF) U ∈ R^{N×d} with frame redundancy N > d, such as a randomized partial Hadamard transform, satisfying Kashin’s uncertainty principle to ensure bounded coefficients. A client vector x ∈ Sd-1 is transformed to Kashin coefficients y ∈ R^N by y = argmin with bounded ∞-norm. The encoding picks a coordinate index j uniformly at random (oblivious subsampling) and stochastically rounds y_j to one of two nearest codebook points in an ordered scalar codebook Γ of size M=2^b. Privacy noise is injected via either:

• Flat Randomized Response (Flat-RR): a discrete randomized response over codebook elements yielding unbiased estimators but variance growing with codebook size.
• Metric-Aware Laplace mechanism: draws noise from a truncated Laplace distribution centered on y_j followed by nearest codeword quantization, trading minimal bias for reduced variance better suited to higher bit-widths.

4. Training Regime: Since this is a vector quantization and privacy mechanism, "training" refers to codebook optimization. A surrogate privacy-aware convex loss LSSTQ is derived based on a uniform prior over codebook intervals; this convex optimization finds the unique global minimizer codebook to reduce the codebook-dependent noise variance in quantization plus privacy steps.

5. Evaluation Protocol: Theoretical bounds on MSE and privacy are derived rigorously, including worst-case and data-dependent scaling (Theorems 3.2, 4.3, 5.2, 5.3). Empirical evaluation involves federated learning training with SSTQ encoding for clients, comparing accuracy, communication cost, and MSE against baselines such as vqSGD, SQKR, PrivUnit. Metrics include test accuracy, training loss convergence, accuracy per communication bit, and coordinate MSE. Experiments vary dimension d ∈ {50, 100, 200}, privacy budget ε (e.g., ε=3), and codebook bit-width b (4 to 8). Statistical significance tests are not explicitly reported.

6. Reproducibility: Code is not publicly released at time of writing. The Kashin frame is implemented using randomized partial Hadamard transforms for efficiency. All algorithmic details, including parameter settings and theoretical proofs, are fully documented in appendices. Data sets (CIFAR-10, Fashion-MNIST) are standard and publicly available.

Example end-to-end: For a normalized client gradient x ∈ R^d, SSTQ computes its Kashin vector y ∈ R^N with ∥y∥_∞ ≤ B. It chooses an index j uniformly at random; then the scalar y_j is stochastically rounded between two nearest codebook points (c_k, c_{k+1}). Flat-RR or Metric-Aware mechanisms add LDP noise. The client transmits index j and quantized codeword z using ⌈log₂ N⌉ + b bits. The server debiases the noisy codeword, reconstructs a 1-sparse vector, and projects back using UT to obtain an unbiased or low-bias estimator of x with bounded MSE under ε-LDP.

Technical innovations

• Introduction of Subsampled Stochastic TurboQuant (SSTQ), combining overcomplete equal-norm tight frames, oblivious coordinate subsampling, and 1D scalar quantization for private vector compression with logarithmic communication costs.
• Development of a surrogate privacy-aware convex codebook optimization loss LSSTQ that reduces quantization error under randomized response from O(4^b) to O(2^b) scaling in codebook bit-width b.
• Design of a Metric-Aware Laplace mechanism noise injection that replaces uniform randomization with truncated Laplace noise followed by nearest-codeword quantization, drastically reducing variance explosions at high bit-widths.
• Removal of shared randomness assumptions seen in previous Kashin-based mechanisms (e.g., SQKR), enabling fixed communication cost protocols in pure ε-local differential privacy without public-coin protocols.

Datasets

• CIFAR-10 — ~60,000 images — publicly available
• Fashion-MNIST — 70,000 images — publicly available

Baselines vs proposed

• vqSGD: MSE scales as O(d^3 / ε^2) vs SSTQ (Flat-RR): MSE scales as O(d (1 + 4b / ε))
• SQKR (Dense): requires O(d) bits vs SSTQ: requires ⌈log2 N⌉ + b bits (~logarithmic in dimension)
• PrivUnit: Θ(d) bits with O(d / ε^2) MSE vs SSTQ: O(d (1 + 2b / ε)) MSE with much lower bit cost
• Empirical FL accuracy: SSTQ outperforms SQKR, vqSGD across dimensions d and privacy ε=3 with b=8 bits (Fig 3,4).
• FL convergence: SSTQ Metric-Aware stable for b=8 while Flat-RR error explodes (Fig 5).

Figures from the paper

Figures are reproduced from the source paper for academic discussion. Original copyright: the paper authors. See arXiv:2608.05127.

Fig 1: presents the training loss, test accuracy, and accuracy-vs-communication-cost

Fig 2: MSE versus dimension for all methods (per-round ε = 3, b = 8, M = 256, C = 0.2). Flat-RR

Fig 3: Distributed SGD convergence under ε-LDP (ε = 3, b = 4). Comparison of the two variants of

Fig 4: Flat-RR explosion versus Metric-Aware stability at d = 200, ε = 3. Left: Low bit-width (b = 4,

Fig 5 (page 41).

Limitations

• SSTQ requires knowledge or estimation of the Kashin frame which can be computationally intensive or memory heavy for very large dimensions.
• Metric-Aware Laplace variant introduces a bias tradeoff; the impact of this bias on downstream model accuracy is not fully characterized.
• Codebook optimization relies on surrogate uniform distributions or requires oracle knowledge of the true Kashin coordinate distribution, limiting real-world adaptability.
• Public code release and reproducibility remain pending; practical integration details with real-world FL systems need further exploration.
• Experimental evaluation is limited to CIFAR-10 and Fashion-MNIST; results on more complex tasks or non-iid federated distributions are not provided.
• No explicit adversarial robustness or attack scenarios beyond standard ε-LDP analyzed; practical threats in federated settings may differ.

Open questions / follow-ons

• How to efficiently learn or adapt the quantization codebook online under privacy constraints without oracle knowledge of the true coordinate distribution?
• Can SSTQ be extended to heterogeneous clients with differing data distributions and dimensionalities in federated learning?
• What is the practical impact of the Metric-Aware Laplace mechanism’s bias on downstream machine learning tasks beyond MSE metrics?
• How does SSTQ perform under adversarial manipulations or poisoning attacks in federated learning beyond the privacy guarantees?

Why it matters for bot defense

For bot-defense or CAPTCHA practitioners focused on secure federated learning or private client embeddings, SSTQ offers a novel mechanism to compress high-dimensional client data into very low-bit representations while providing strong local differential privacy guarantees. This addresses key bottlenecks of communication efficiency and privacy in distributed optimization.

SSTQ’s use of overcomplete tight frames and oblivious coordinate subsampling can inspire design of private encoding schemes for client behavioral vectors or interaction features in CAPTCHA systems, balancing communication overhead versus attack surface. The metric-aware quantization technique also highlights the benefits of trading slight bias for variance reduction when operating at high precision under privacy constraints—an insight relevant for fine-grained feature encoding in adversarially aware systems.

However, practitioners should note SSTQ’s reliance on linear transformations and specialized codebook optimizations that may be computationally intensive and require further engineering for real-time CAPTCHA client workflows. Its strict ε-local differential privacy model offers strong privacy but assumes no adversarial side channels beyond model updates. Overall, SSTQ provides cutting-edge quantization and privacy theory relevant for privacy-preserving bot detection and client attestation pipelines, especially those integrating federated or distributed learning components.

Cite

@article{arxiv2608_05127,
  title={ SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant },
  author={ Adel Javanmard and David P. Woodruff and Vahab Mirrokni },
  journal={arXiv preprint arXiv:2608.05127},
  year={ 2026 },
  url={https://arxiv.org/abs/2608.05127}
}

Read the full paper

• arXiv:2608.05127 (abstract)
• arXiv:2608.05127 (PDF)