Quantization through Piecewise-Affine Regularization: Optimization and Statistical Guarantees
This work addresses the combinatorial difficulty of quantization in machine learning, offering a continuous optimization framework with theoretical backing, but it is incremental as it builds on existing regularization methods.
The paper tackles the challenge of optimizing discrete or quantized variables by using piecewise-affine regularization (PAR) in supervised learning, showing that critical points achieve high quantization in overparameterized regimes and deriving proximal methods with statistical guarantees for linear regression.
Optimization problems over discrete or quantized variables are very challenging in general due to the combinatorial nature of their search space. Piecewise-affine regularization (PAR) provides a flexible modeling and computational framework for quantization based on continuous optimization. In this work, we focus on the setting of supervised learning and investigate the theoretical foundations of PAR from optimization and statistical perspectives. First, we show that in the overparameterized regime, where the number of parameters exceeds the number of samples, every critical point of the PAR-regularized loss function exhibits a high degree of quantization. Second, we derive closed-form proximal mappings for various (convex, quasi-convex, and non-convex) PARs and show how to solve PAR-regularized problems using the proximal gradient method, its accelerated variant, and the Alternating Direction Method of Multipliers. Third, we study statistical guarantees of PAR-regularized linear regression problems; specifically, we can approximate classical formulations of $\ell_1$-, squared $\ell_2$-, and nonconvex regularizations using PAR and obtain similar statistical guarantees with quantized solutions.