Optimal and Near-Optimal Adaptive Vector Quantization

2024/02/05 by Ben-Basat, Ran, Ben-Itzhak, Yaniv, Mitzenmacher, Michael +1 · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning (cs.LG) #Networking and Internet Architecture (cs.NI)

paper · doi:10.48550/arxiv.2402.03158

Abstract

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 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.

Cited by

• PacTrain: Pruning and Adaptive Sparse Gradient Compression for Efficient Collective Communication in Distributed Deep Learning

Related

• Rate-Adaptive Quantization: A Multi-Rate Codebook Adaptation for Vector Quantization-based Generative Models
• MQGrad: Reinforcement Learning of Gradient Quantization in Parameter Server
• Preventing Local Pitfalls in Vector Quantization via Optimal Transport
• GPTVQ: The Blessing of Dimensionality for LLM Quantization
• Accelerating Competitive Learning Graph Quantization