Research map / Learning theory and algorithms / Prediction and decision losses
Optimal and Approximate Adaptive Stochastic Quantization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Presents QUIVER and accelerated/approximate variants that solve adaptive stochastic quantization optimally with O(s·d) time and space, plus a fast discretized approximation (Apx. QUIVER) for on-the-fly quantization.
Problem
Adaptive stochastic quantization (ASQ) selects quantization values per input to minimize MSE, but known optimal methods (ZipML dynamic program, O(s·d^2) time and O(d^2) space) are considered too slow and memory-heavy for large ML vectors.
Approach
Reduces the ASQ dynamic program to row-minima of a totally monotone matrix (via the quadrangle inequality) solved with SMAWK, using O(1) prefix-sum preprocessing for interval variance; adds a closed-form s=3 step to pair quantization values, and a discretized-grid approximation with a provable additive error bound.
Key results
- Accelerated QUIVER computes optimal 4-bit (s=16) quantization for a d=1M vector in under one second on a commodity PC, versus ZipML which cannot run for d>=2^17 due to memory.
- Apx. QUIVER computes near-optimal 4-bit quantization values for d=2^20 in about six milliseconds and about 70 ms for d=2^24.
- Exact algorithms are up to four orders of magnitude faster than ZipML; Accelerated QUIVER is up to 5.4x faster than QUIVER.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Accelerated QUIVER instead of ZipML for exact adaptive quantization | Exact ASQ · LogNormal(0, 1) input vectors | runtime: up to four orders of magnitude | Helped |
| use Apx. QUIVER rather than the exact solutions as vector dimension increases | Adaptive quantization · LogNormal(0, 1) input vectors | runtime: six milliseconds for d = 220; about 70ms for d = 224 | Helped |
| replace QUIVER with Accelerated QUIVER, placing two quantization values per dynamic-program step (ablation) | QUIVER · Normal and LogNormal input vectors | runtime: up to 5.4× | Helped |
| increase the discretization grid size m (ablation) | Apx. QUIVER · LogNormal(0, 1) input vectors | vNMSE | Helped |
| increase the number of quantization values s (ablation) | Accelerated QUIVER · LogNormal(0, 1), d = 212 and d = 216 | vNMSE | Helped |
| use Apx. QUIVER rather than ZipML approximation variants | Approximate ASQ · LogNormal(0, 1) input vectors | vNMSE | Helped |
| use biased adaptive quantization rather than unbiased adaptive quantization | Adaptive quantization · Single-vector estimation, LogNormal(0, σ²) | MSE | Helped |
| use unbiased adaptive quantization rather than biased adaptive quantization | Adaptive quantization · Distributed mean estimation with many identical vectors | MSE | Helped |
| use adaptive rather than non-adaptive quantization | Stochastic quantization · Single-vector estimation, LogNormal(0, σ²) | MSE | Helped |
Surprising findings
- Optimal biased adaptive quantization gives lower error than optimal unbiased quantization for a single vector, but unbiasedness becomes critical for distributed mean estimation with many senders.
Limitations
- QUIVER is not GPU friendly; exact solutions assume a sorted input (adds O(d log d) otherwise).
- Approximation error bound is loose relative to the norm-based term; guarantee depends on grid size m.
- The s>3 closed form does not extend, so acceleration is limited to pairing values via SMAWK.
Experimental setup
Datasets: synthetic i.i.d. LogNormal, Normal, Exponential, TruncNorm, and Weibull vectors
Benchmarks: synthetic vector quantization (vNMSE and runtime) distributed mean estimation MSE
Metrics: vNMSE runtime (ms) speedup
Baselines: ZipML ALQ ZipML-CP Uniform ZipML-CP Quantiles ZipML 2-Approximation QSGD NUQSGD RTN
Builds on: ZipML SMAWK ALQ NUQSGD
Closest papers by meaning
- Adaptive Gradient Quantization for Data-Parallel SGD (NeurIPS 2020 · similarity 0.88)
- Learning under Quantization for High-Dimensional Linear Regression (ICLR 2026 · similarity 0.88)
- Quant Experts: Token-aware Adaptive Error Reconstruction with Mixture of Experts for Large Vision-Language Models Quantization (CVPR 2026 · similarity 0.86)
- GSQ: Highly-Accurate Low-Precision Scalar Quantization for LLMs via Gumbel-Softmax Sampling (NeurIPS 2026 · similarity 0.86)
- PARQ: Piecewise-Affine Regularized Quantization (ICML 2025 · similarity 0.86)
- MagR: Weight Magnitude Reduction for Enhancing Post-Training Quantization (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.