Optimal and Near-Optimal Adaptive Vector Quantization
Ran Ben-Basat Yaniv Ben-Itzhak Michael Mitzenmacher Shay Vargaftik
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.