ProxSGD: Training Structured Neural Networks under Regularization and Constraints

Yang Yang, Yaxiong Yuan, Avraam Chatzimichailidis, Ruud J. G. van Sloun, Lei Lei, Symeon ChatzinotasICLR 2020 · OpenReview

Training modern neural networks is usually a balancing act. We want models that are accurate, but we also want them to be "structured"—perhaps sparse to save memory, or binarized to run on low-power edge devices. Achieving this structure typically involves adding nonsmooth regularizers (like the $L_1$ norm) or hard constraints.

While Stochastic Gradient Descent (SGD) is the workhorse of deep learning, it struggles with these non-differentiable or constrained components. In their paper, Yang et al. introduce ProxSGD, a theoretically grounded and practically efficient algorithm designed to handle these exact challenges.

The Challenge of Structured Neural Networks

In the quest for efficient AI, we often seek "Structured Neural Networks" (SNNs). Two common ways to enforce structure are:

  1. Regularization: Adding a penalty term like the $L_1$ norm to encourage weights to become exactly zero (sparsity).
  2. Constraints: Restricting weights to specific ranges (e.g., interval constraints) or forcing them toward specific values (e.g., binarization to -1 or +1).

Standard deep learning frameworks often handle nonsmooth terms like $|x|$ by simply setting the gradient to 0 at $x=0$. This "subgradient" approach is a heuristic that often leads to slow convergence and "lazy" sparsity, where weights are small but not exactly zero. Furthermore, when you have hard constraints, you must "project" weights back into the allowed set after every step. This projection is a non-linear operation that breaks the statistical properties (unbiasedness) that SGD relies on for convergence.

ProxSGD: A Proximal Approach with Momentum

The authors propose ProxSGD, which reformulates the training step. Instead of a simple gradient update, it solves a "proximal" subproblem at each iteration.

The Secret Sauce: Momentum

The most critical insight in ProxSGD is the role of momentum. In standard SGD, momentum is a trick to speed up training. In ProxSGD, momentum is mathematically essential. The algorithm maintains an aggregate gradient $v(t)$ that averages past stochastic gradients. The authors prove that this averaging allows $v(t)$ to converge to the true (but unknown) gradient of the loss function, which is the key to handling constraints and nonsmoothness rigorously.

The Update Rule

At each step $t$, ProxSGD solves an approximation subproblem:

$$\hat{x}(t) = \text{argmin}_{x \in \mathbb{X}} \left\{ (x - x(t))^T v(t) + \frac{1}{2} (x - x(t))^T \text{diag}(\tau(t)) (x - x(t)) + r(x) \right\}$$

Where:

  • $v(t)$ is the momentum-based gradient.
  • $\mathbb{X}$ is the constraint set.
  • $r(x)$ is the nonsmooth regularizer.
  • $\tau(t)$ is a quadratic gain (similar to the adaptive learning rates in ADAM).

For many common cases, like $L_1$ regularization or box constraints, this subproblem has a simple, closed-form solution (like the soft-thresholding operator), making it computationally efficient.

Key Insights and Ideas

  • True Sparsity vs. "Small" Weights: Standard optimizers like ADAM with $L_1$ penalties often produce weights that are very small (e.g., $10^{-6}$) but not zero. ProxSGD produces "hard" sparsity where weights are exactly zero, which is much more useful for model pruning and hardware acceleration.
CDF of Weights showing exact sparsity for ProxSGD
  • Theoretical Convergence: The paper provides a rigorous proof that, with probability 1, every limit point of the ProxSGD sequence is a stationary point of the nonconvex objective. This provides a level of mathematical reliability often missing from heuristic pruning methods.
  • Binarization via Relaxation: To train Binary Neural Networks, the authors use a clever trick: they augment the loss with a penalty that pushes weights toward -1 or 1 and use box constraints $[0, 1]$ on a "switch" variable. ProxSGD handles this complex setup much more effectively than previous specialized BNN algorithms.

Key Results

The authors evaluated ProxSGD across several standard benchmarks, including training a sparse 6-layer CNN on CIFAR-10, a sparse DenseNet-201 on CIFAR-100, and a Binary Neural Network on MNIST.

  • Superior Sparsity: On CIFAR-10, ProxSGD achieved over 90% exact sparsity (weights at zero) while maintaining or improving accuracy. In contrast, ADAM and AMSGrad only reached 40-50% sparsity under the same conditions.
  • DenseNet Performance: For the complex DenseNet-201 on CIFAR-100, ProxSGD reached 92-94% sparsity. It achieved lower training loss than SGD with momentum and ADAM, proving it scales to deep architectures.
Training Loss comparison showing ProxSGD's faster convergence
  • Binary Accuracy: In BNN training on MNIST, ProxSGD reached 95% test accuracy, significantly outperforming the 89% achieved by the baseline BinaryConnect algorithm, while converging faster.
  • Efficiency: While the proximal step adds a small amount of overhead, the training time per epoch remained comparable to ADAM (e.g., 16.04s for ProxSGD vs 17.24s for ADAM on a CNN).

Limitations and Future Work

  • Convergence Rate: While the paper proves the algorithm will converge, it does not derive the rate of convergence (how many steps it takes).
  • Assumptions vs. Reality: The proof assumes the loss function is smooth (Lipschitz continuous gradients). In practice, neural networks using ReLU activations or Batch Normalization technically violate this, though the algorithm still performs well empirically.
  • Hyperparameters: Like all momentum-based methods, ProxSGD requires tuning learning rates for both the weights and the momentum. The authors suggest a specific decay schedule, but finding the "perfect" settings for a new architecture may still require a grid search.

Summary updated

Abstract

In this paper, we consider the problem of training neural networks (NN). To promote a NN with specific structures, we explicitly take into consideration the nonsmooth regularization (such as L1-norm) and constraints (such as interval constraint). This is formulated as a constrained nonsmooth nonconvex optimization problem, and we propose a convergent proximal-type stochastic gradient descent (Prox-SGD) algorithm. We show that under properly selected learning rates, momentum eventually resembles the unknown real gradient and thus is crucial in analyzing the convergence. We establish that with probability 1, every limit point of the sequence generated by the proposed Prox-SGD is a stationary point. Then the Prox-SGD is tailored to train a sparse neural network and a binary neural network, and the theoretical analysis is also supported by extensive numerical tests.
BibTeX
@inproceedings{yang2020proxsgd,
  author = {Yang Yang and Yaxiong Yuan and Avraam Chatzimichailidis and Ruud J. G. van Sloun and Lei Lei and Symeon Chatzinotas},
  title = {{ProxSGD: Training Structured Neural Networks under Regularization and Constraints}},
  booktitle = {International Conference on Learning Representations},
  year = {2020},
  url = {https://openreview.net/forum?id=RhVtstTYVYt},
}
Figure