SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant

• URL: http://arxiv.org/abs/2608.05127v2
• Date: Fri, 07 Aug 2026 01:49:17 GMT
• Title: SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant
• Abstract summary: Subsampled TurboQuant (SSTQ) is a framework that combines overcomplete equal-width tight frames, coordinate subsampling, and privacy-aware quantization.<n>SSTQ achieves mean squared error scaling while using only $lceil log N il + b$ bits per client, where $N = (d)$ is the frame size.<n>We also derive a surrogate privacy-aware codebook objective that reduces the codebook-dependent MSE scaling from $O(4b)$ to $O(2b)$.
• Score: 79.24089819400126
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 $\lceil \log_2 N \rceil + 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.

Related papers

• Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions [51.50375419691955]
  Distributionally robust Markov decision processes provide a principled framework for sequential decision making under model uncertainty.<n>We study how many samples are necessary and sufficient to learn an $varepsilon$-optimal robust policy under the average-reward criterion.
  arXiv  Detail & Related papers  (2026-08-06T19:49:48Z)
• Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes [32.65125292684608]
  We propose a novel adaptive mean estimator based solely on randomized threshold queries.<n>Our estimator's sample complexity has an extra multiplicative $O(log(/))$ penalty.<n>For both threshold queries and more general interval queries, the sample complexity of any non-adaptive estimator must scale linearly.
  arXiv  Detail & Related papers  (2026-04-09T04:49:21Z)
• Stochastic Dimension-Free Zeroth-Order Estimator for High-Dimensional and High-Order PINNs [5.601252185916962]
  We propose a unified framework that achieves dimension-independent complexity in both space and memory.<n>textbfSDZE enables the training of 10-million-dimensional PINNs on a single NVIDIA A100 GPU, delivering significant improvements in memory efficiency over state-of-the-art baselines.
  arXiv  Detail & Related papers  (2026-03-25T07:02:34Z)
• Adaptation to Intrinsic Dependence in Diffusion Language Models [5.185131234265025]
  Diffusion language models (DLMs) have emerged as a promising alternative to autoregressive (AR) approaches.<n>We introduce a distribution-agnostic unmasking schedule for DLMs that adapts to the (unknown) dependence structure of the target data distribution.<n>Our results significantly improve upon prior convergence theories and yield substantial sampling acceleration for low-complexity distributions.
  arXiv  Detail & Related papers  (2026-02-23T18:41:34Z)
• Tensor Network Generator-Enhanced Optimization for Traveling Salesman Problem [12.04919729571293]
  We present an application of the tensor network generator-enhanced optimization (TN-GEO) framework to the traveling salesman problem (TSP)<n>Our approach employs a tensor network Born machine based on automatically differentiable matrix product states (MPS) as the generative model.<n>$k$-site variants, which put more focus on local correlations, show better results compared to the full-MPS case.
  arXiv  Detail & Related papers  (2026-02-12T21:18:19Z)
• Multiple-play Stochastic Bandits with Prioritized Arm Capacity Sharing [52.124267908936396]
  The model is composed of $M$ arms and $K$ plays.<n>Each arm has a number of capacities, and each unit of capacity is associated with a reward function.<n>When multiple plays compete for the arm capacity, the arm capacity is allocated in a larger priority weight first manner.
  arXiv  Detail & Related papers  (2025-12-25T11:19:09Z)
• FedSVD: Adaptive Orthogonalization for Private Federated Learning with LoRA [68.44043212834204]
  Low-Rank Adaptation (LoRA) is widely used for efficient fine-tuning of language models in learning (FL)<n>Low-Rank Adaptation (LoRA) is widely used for efficient fine-tuning of language models in learning (FL)
  arXiv  Detail & Related papers  (2025-05-19T07:32:56Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  Single-Index Models are high-dimensional regression problems with planted structure. We show that computationally efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree Polynomial (LDP) framework, necessarily require $Omega(dkstar/2)$ samples.
  arXiv  Detail & Related papers  (2024-03-08T18:50:19Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  We study the Shortest Path (SSP) problem with a linear mixture transition kernel. An agent repeatedly interacts with a environment and seeks to reach certain goal state while minimizing the cumulative cost. Existing works often assume a strictly positive lower bound of the iteration cost function or an upper bound of the expected length for the optimal policy.
  arXiv  Detail & Related papers  (2024-02-14T07:52:00Z)
• Learning Low-Rank Representations for Model Compression [6.721845345130468]
  We propose a Low-Rank Representation Vector Quantization ($textLR2textVQ$) method that outperforms previous VQ algorithms in various tasks and architectures. In our method, the compression ratio could be directly controlled by $m$, and the final accuracy is solely determined by $tilded$. With a proper $tilded$, we evaluate $textLR2textVQ$ with ResNet-18/ResNet-50 on ImageNet classification datasets, achieving 2.8%/1.0% top
  arXiv  Detail & Related papers  (2022-11-21T12:15:28Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  We propose a novel method named Multi-block-probe Variance Reduced (MSVR) to alleviate the complexity of compositional problems. Our results improve upon prior ones in several aspects, including the order of sample complexities and dependence on strongity.
  arXiv  Detail & Related papers  (2022-07-18T12:03:26Z)
• Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models [45.14286976373306]
  We establish optimal Statistical Query (SQ) lower bounds for robustly learning certain families of discrete high-dimensional distributions. Our SQ lower bounds match the error guarantees of known algorithms for these problems, providing evidence that current upper bounds for these tasks are best possible.
  arXiv  Detail & Related papers  (2022-06-09T16:10:23Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  We consider online statistical inference of constrained nonlinear optimization problems.<n>We apply the Sequential Quadratic Programming (StoSQP) method to solve these problems.
  arXiv  Detail & Related papers  (2022-05-27T00:34:03Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  A novel model-free algorithm is proposed to minimize regret in episodic reinforcement learning. The proposed algorithm employs an em early-settled reference update rule, with the aid of two Q-learning sequences. The design principle of our early-settled variance reduction method might be of independent interest to other RL settings.
  arXiv  Detail & Related papers  (2021-10-09T21:13:48Z)
• Hashing embeddings of optimal dimension, with applications to linear least squares [1.2891210250935143]
  We present subspace embedding properties for $s$-hashing sketching matrices, with $sgeq 1$, that are optimal in the projection dimension $m$ of the sketch. We apply these results to the special case of Linear Least Squares (LLS), and develop Ski-LLS, a generic software package for these problems.
  arXiv  Detail & Related papers  (2021-05-25T10:35:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.