Quantization is a fundamental optimization for many machine-learning use
cases, including compressing gradients, model weights and activations, and
datasets. The most accurate form of quantization is \emph{adaptive}, where the
error is minimized with respect to a given input, rather than optimizing for
the worst case. However, optimal adaptive quantization methods are considered
infeasible in terms of both their runtime and memory requirements.
We revisit the Adaptive Vector Quantization (AVQ) problem and present
algorithms that find optimal solutions with asymptotically improved time and
space complexity. We also present an even faster near-optimal algorithm for
large inputs. Our experiments show our algorithms may open the door to using
AVQ more extensively in a variety of machine learning applications.

量化是许多机器学习应用中的基础优化之一，该研究论文重新审视自适应矢量量化问题，并提出了改进的时间和空间复杂度的最优解算法，以及适用于大型输入的更快的近似最优算法。实验结果表明这些算法可能在各种机器学习应用中更广泛地应用于自适应矢量量化。