Entropy-Constrained Adaptive Stochastic Quantization

• URL: http://arxiv.org/abs/2608.18147v1
• Date: Mon, 10 Aug 2026 17:32:40 GMT
• Title: Entropy-Constrained Adaptive Stochastic Quantization
• Abstract summary: Adaptive quantization (ASQ) is a recently introduced quantization approach that optimize the Mean Squared Error (MSE) for a given input while preserving unbiasedness.<n>We formulate the Entropy Constrained Adaptive Quantization (ECASQ) problem, which jointly selects adaptive quantization values to minimize MSE under an entropy budget.<n>We give an optimal dynamic program with $O(sd2)$ time and $O(d2)$ space for a length-d vector and at most s quantization values, and a GPU-friendly approximate program with $O(sd
• Score: 18.204242530505308
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Adaptive stochastic quantization (ASQ) is a recently introduced quantization approach that optimizes the Mean Squared Error (MSE) for a given input while preserving unbiasedness. It is designed to alleviate the communication and memory bottlenecks of modern data and machine learning workloads, including model, gradient, and KV-cache compression and nearest-neighbor search. Further, practical systems can then compress quantized data with a lossless entropy encoder. However, existing unbiased methods, including ASQ, choose their quantization values without considering this later encoding stage, leaving accuracy on the table. We formulate the Entropy Constrained Adaptive Stochastic Quantization (ECASQ) problem, which jointly selects adaptive quantization values to minimize MSE under an entropy budget and an unbiasedness constraint. We give an optimal dynamic program with $O(sd^2)$ time and $O(d^2)$ space for a length-d vector and at most s quantization values, and a GPU-friendly approximate dynamic program with $O(sd^2)$ time and $O(d)$ space. The approximation guarantees that the solution has an MSE no larger than the optimal solution that uses one fewer bit of entropy per entry. We also provide an iterative refinement procedure for the approximation solution that, in our experiments, yields near-optimal results while retaining a substantial speed advantage over our solver for the optimal solution.

Related papers

• Scalable Lindblad Noise Learning via Stochastic Tensor-Network Simulation [48.887627688666974]
  Learning dissipation rates in large-scale open quantum systems is a major obstacle for near-term quantum technologies.<n>Here, we propose a scalable noise-learning framework for Lindblad dissipation rates that combines a simulation method, the Jump Method (TJM)<n>We demonstrate the approach on two noise models in the Ising model, in which independent dissipation rates are learned for each site up to $N_mathrmsite=16$.<n>This combination of scalable numerics and rigorous theoretical guarantees positions TJM-based noise learning as a practical foundation for characterizing dissipation in large quantum devices.
  arXiv  Detail & Related papers  (2026-08-25T15:07:11Z)
• Wall-Clock Complexity for Zeroth-Order Optimization with Tunable Oracle Fidelity [68.54852541944625]
  Black-box optimization is applied when gradients are unavailable and objective evaluations rely on expensive simulations.<n>We show how the choice of oracle type, noise model, and optimization scheme induces explicit wall-clock-optimal choices for the algorithmic parameters.
  arXiv  Detail & Related papers  (2026-05-29T14:24:54Z)
• EQE-QAOA: An Equivalence-Preserving Qubit Efficient Framework for Combinatorial Optimization [54.05451096499336]
  Existing techniques rely on qubit reduction at the cost of information loss, leading to degraded computational performance.<n>We propose the Equivalence-preserving Qubit Efficient QAOA, which significantly reduces the required number of qubits without degrading performance.<n>We show that it is broadly applicable to large-scale optimization problems, excluding only unconstrained problems with completely independent variables.
  arXiv  Detail & Related papers  (2026-04-20T13:57:49Z)
• Adaptive Probability Flow Residual Minimization for High-Dimensional Fokker-Planck Equations [14.22534820071447]
  Solving high-dimensional Fokker-Planck equations is a challenge in computational physics and dynamics.<n>Existing deep learning approaches, such as Physics-Informed Neural Networks, face computational challenges as dimensionality increases.<n>We propose the Adaptive Probability Flow Residual Minimization (A-PFRM) method.
  arXiv  Detail & Related papers  (2025-12-22T09:31:31Z)
• MPQ-DMv2: Flexible Residual Mixed Precision Quantization for Low-Bit Diffusion Models with Temporal Distillation [74.34220141721231]
  We present MPQ-DMv2, an improved textbfMixed textbfPrecision textbfQuantization framework for extremely low-bit textbfDiffusion textbfModels.
  arXiv  Detail & Related papers  (2025-07-06T08:16:50Z)
• An Adaptive Weighted QITE-VQE Algorithm for Combinatorial Optimization Problems [0.0]
  We propose an Adaptive Weighted QITE-VQE (AWQV) algorithm that integrates the VQE gradients with the cQITE updates through an adaptive weighting scheme during optimization.<n>AWQV achieves near-optimal approximation ratios, while for weighted ErdHos-R'enyi instances, it outperforms the classical Goemans-Williamson algorithm.
  arXiv  Detail & Related papers  (2025-04-14T19:05:16Z)
• Near-Optimal Parameter Tuning of Level-1 QAOA for Ising Models [3.390330377512402]
  We show how to reduce the two-dimensional $(gamma, beta)$ search to a one-dimensional search over $gamma$, with $beta*$ computed analytically.<n>This approach is validated using Recursive QAOA (RQAOA), where it consistently outperforms both coarsely optimised RQAOA and semidefinite programs.
  arXiv  Detail & Related papers  (2025-01-27T19:00:00Z)
• Optimal and Near-Optimal Adaptive Vector Quantization [15.221460131211684]
  Quantization is a fundamental optimization for many machine-learning use cases, including compressing, model weights and activations, and datasets.<n>We revisit the Adaptive Vector Quantization (AVQ) problem and present algorithms that find optimal solutions with improved time and space complexity.<n>Our experiments show our algorithms may open the door to using AVQ more extensively in a variety of machine learning applications.
  arXiv  Detail & Related papers  (2024-02-05T16:27:59Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  Many real-world problems have complicated non functional constraints and use a large number of data points. Our proposed method outperforms an existing method with the previously best-known result.
  arXiv  Detail & Related papers  (2022-12-19T14:48:54Z)
• Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimator [75.05106948314956]
  We show that an increasing large momentum parameter for the first-order moment is sufficient for adaptive scaling.<n>We also give insights for increasing the momentum in a stagewise manner in accordance with stagewise decreasing step size.
  arXiv  Detail & Related papers  (2021-04-30T08:50:24Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  In this work, we seek to balance the fact that attenuating step-size is required for exact convergence with the fact that constant step-size learns faster in time up to an error. Rather than fixing the minibatch the step-size at the outset, we propose to allow parameters to evolve adaptively.
  arXiv  Detail & Related papers  (2020-07-02T16:02:02Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)

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.