Low Precision Representations for High Dimensional Models

The large memory footprint of high dimensional models require quantization to a lower precision for deployment on resource constrained edge devices. With this motivation, we consider the problems of learning a (i) linear regressor, and a (ii) linear classifier from a given training dataset, and quantizing the learned model parameters subject to a pre-specified bit-budget. The error metric is the prediction risk of the quantized model, and our proposed randomized embedding-based quantization methods attain near-optimal error while being computationally efficient. We provide fundamental bounds on the bit-budget constrained minimax risk that, together with our proposed algorithms, characterize the minimum threshold budget required to achieve a risk comparable to the unquantized setting. We also show the efficacy of our strategy by quantizing a two-layer ReLU neural network for non-linear regression. Numerical simulations show the improved performance of our proposed scheme as well as its closeness to the lower bound.