This paper, presented at NeurIPS 2021, introduces a robust framework for training "structured" neural networks—those designed to be sparse or quantized for efficiency. By merging the strengths of adaptive optimizers (like ADAM) with proximal gradient methods, the authors provide a more principled way to handle the non-smooth, non-convex regularizers common in modern deep learning.
TL;DR
The authors propose PROXGEN, a general framework for stochastic proximal gradient descent that incorporates arbitrary preconditioners and non-convex regularizers. It yields the first proximal version of the popular ADAM optimizer and a revised, more accurate version of PROXQUANT for network quantization, outperforming standard subgradient-based methods in both convergence speed and final model accuracy.
What Problem Does This Paper Address?
To make neural networks smaller and faster, researchers use "structured" training, which involves regularizers that encourage weights to be zero (sparsity) or discrete values (quantization). These regularizers (like the $L_1$ norm) are often non-smooth (they have "kinks") and sometimes non-convex.
Standard deep learning libraries typically handle these using subgradient methods. However, subgradient methods are notorious for oscillating near the optimum and failing to produce truly sparse solutions. Proximal Gradient Descent (PGD) is the mathematically "correct" way to handle such terms, but existing PGD variants often lack adaptivity—the ability to scale learning rates for different parameters based on their gradient history (a key feature of optimizers like ADAM).
As highlighted in the comparison above, prior algorithms force a compromise between handling non-convex regularizers, utilizing arbitrary preconditioners, incorporating momentum, or maintaining theoretical convergence guarantees. This paper bridges that gap by ticking all the boxes.
Methods
The authors introduce PROXGEN, a unified framework that performs a two-step update at each iteration:
- Gradient Step: Compute a stochastic gradient of the smooth loss function (the standard neural network error).
- Proximal Step: Solve a subproblem that balances staying close to the gradient update while minimizing the regularizer.
What’s New: * Integrated Preconditioning: Unlike previous attempts, PROXGEN incorporates the preconditioner (the matrix that scales learning rates in adaptive methods) directly into the proximal mapping. This ensures the geometry of the data is respected during the regularization step. * Proximal ADAM: They derive the first exact proximal version of ADAM. * Revised PROXQUANT: They improve upon the PROXQUANT algorithm by including the preconditioner in the quantization-specific proximal mapping, leading to better binary neural networks. * Theoretical Guarantees: They provide non-asymptotic convergence analysis for non-convex losses and non-convex regularizers, showing that adaptive methods can converge faster than vanilla SGD when dealing with sparse data.
Key Insights and Ideas
- Adaptivity + Proximal is Non-Trivial: You cannot simply apply a proximal operator after an ADAM update. To be mathematically sound and effective, the "distance" in the proximal subproblem must be measured using the same preconditioner used for the gradient update.
- Proximal > Subgradient for Non-Convexity: The benefits of proximal methods are even more pronounced when using non-convex regularizers (like $L_q$ norms where $q < 1$). Subgradients struggle significantly with the steep slopes of these functions, whereas proximal mappings handle them analytically.
- The "Exact Zero" Advantage: In sparsity tasks, PROXGEN can reach an exact zero value for a parameter in a single step, whereas subgradient methods or "two-stage" proximal methods (like Prox-SGD) often just get very close to zero or overestimate sparsity.
- Sparsity Speeds Up Convergence: The theory confirms that for sparse data, adaptive preconditioners reduce the "constant" in the convergence rate, explaining why PROXGEN feels faster in practice.
Key Results
The framework was evaluated on standard computer vision benchmarks (CIFAR-10, CIFAR-100, ImageNet) using architectures like ResNet and DenseNet.
- Sparsity: As seen in the charts above, on ResNet-34 (CIFAR-10), PROXGEN achieved higher test accuracy than subgradient-based ADAM across various pruning ratios and regularizers ($L_1, L_{2/3}, L_{1/2}, L_0$). With $L_0$ regularization, it significantly outperformed the "hard-concrete" baseline.
- Quantization: The Revised PROXQUANT achieved a Top-1 error of 34.85% on ImageNet with ResNet-18, beating the original PROXQUANT (36.24%) and other baselines like BinaryConnect.
- Convergence: In head-to-head tests, PROXGEN converged to a lower objective value faster than Prox-SGD, proving the importance of their exact subproblem formulation.
Limitations and Future Work
- Computational Overhead: While closed-form proximal mappings exist for many common regularizers, more complex "structured" regularizers (like group sparsity) might require iterative solvers for the proximal subproblem, which could slow down training.
- Diagonal Focus: Most of the practical implementations in the paper use diagonal preconditioners (like ADAM). Extending this efficiently to full-matrix or block-diagonal preconditioners (like KFAC) remains a challenge.
- Future Directions: The authors suggest developing more efficient procedures to compute proximal mappings for complex structured norms when used in conjunction with non-diagonal preconditioners.
Summary updated