Can I read Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms on EtoBox?

Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms by Saha, Rajarshi; Pilanci, Mert; Goldsmith, Andrea J. is a scholarly article available to read on EtoBox.

What is Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms about?

High-dimensional models often have a large memory footprint and must be quantized after training before being deployed on resource-constrained edge devices for inference tasks. In this work, we develop an information-theoretic framework for the problem of quantizing a linear regressor learned from training data $(\mathbf{X}, \mathbf{y})$, for some underlying statistical relationship $\mathbf{y} = \mathbf{X}\boldsymbol{\theta} + \mathbf{v}$. The learned model, which is an estimate of the latent parameter $\boldsymbol{\theta} \in \mathbb{R}^d$, is constrained to be representable using only $Bd$ bits, where $B \in (0, \infty)$ is a pre-specified budget and $d$ is the dimension. We derive an information-theoretic lower bound for the minimax risk under this setting and propose a matching upper bound using randomized embedding-based algorithms which is tight up to constant factors. The lower and upper bounds together characterize the minimum threshold bit-budget required to achieve a performance risk comparable to the unquantized setting. We also propose randomized Hadamard embeddings that are computationally efficient and are optimal up to a mild logarithmic factor of the lower bound. O

Author

Saha, Rajarshi; Pilanci, Mert; Goldsmith, Andrea J.

Published

2022

Language

EN