Adaptive Proximal Gradient Methods for Structured Neural Networks

Jihun Yun, Aurelie Lozano, Eunho YangNeurIPS 2021 · OpenReview

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).

Comparison of optimization algorithms and their supported features.

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:

  1. Gradient Step: Compute a stochastic gradient of the smooth loss function (the standard neural network error).
  2. 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.

Learning curves and test accuracy for ResNet-34 across different regularizers.
  • 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

Abstract

We consider the training of structured neural networks where the regularizer can be non-smooth and possibly non-convex. While popular machine learning libraries have resorted to stochastic (adaptive) subgradient approaches, the use of proximal gradient methods in the stochastic setting has been little explored and warrants further study, in particular regarding the incorporation of adaptivity. Towards this goal, we present a general framework of stochastic proximal gradient descent methods that allows for arbitrary positive preconditioners and lower semi-continuous regularizers. We derive two important instances of our framework: (i) the first proximal version of \textsc{Adam}, one of the most popular adaptive SGD algorithm, and (ii) a revised version of ProxQuant for quantization-specific regularizers, which improves upon the original approach by incorporating the effect of preconditioners in the proximal mapping computations. We provide convergence guarantees for our framework and show that adaptive gradient methods can have faster convergence in terms of constant than vanilla SGD for sparse data. Lastly, we demonstrate the superiority of stochastic proximal methods compared to subgradient-based approaches via extensive experiments. Interestingly, our results indicate that the benefit of proximal approaches over sub-gradient counterparts is more pronounced for non-convex regularizers than for convex ones.
BibTeX
@inproceedings{yun2021adaptive,
  author = {Jihun Yun and Aurelie Lozano and Eunho Yang},
  title = {{Adaptive Proximal Gradient Methods for Structured Neural Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=Qijzj3WqUl3},
}
Figure