Optimal and Near-Optimal Adaptive Vector Quantization
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913967741337600 |
|---|---|
| author | Ben-Basat, Ran Ben-Itzhak, Yaniv Mitzenmacher, Michael Vargaftik, Shay |
| author_facet | Ben-Basat, Ran Ben-Itzhak, Yaniv Mitzenmacher, Michael Vargaftik, Shay |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_03158 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Optimal and Near-Optimal Adaptive Vector Quantization Ben-Basat, Ran Ben-Itzhak, Yaniv Mitzenmacher, Michael Vargaftik, Shay Machine Learning Data Structures and Algorithms Information Theory Networking and Internet Architecture 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. |
| title | Optimal and Near-Optimal Adaptive Vector Quantization |
| topic | Machine Learning Data Structures and Algorithms Information Theory Networking and Internet Architecture |
| url | https://arxiv.org/abs/2402.03158 |