An Inexact Augmented Lagrangian Algorithm for Training Leaky ReLU Neural Network with Group Sparsity

Wei Liu, Xin Liu, Xiaojun Chen

TL;DR

Researchers have developed a new optimization framework called IALAM (Inexact Augmented Lagrangian Algorithm with Alternating Minimization) to train Leaky ReLU neural networks with group sparsity. Unlike standard gradient descent methods that "brute force" their way through non-differentiable points, IALAM uses auxiliary variables and a rigorous penalty-based approach to guarantee convergence to stable mathematical points (KKT points), resulting in sparser models and lower error rates.

What Problem Does This Paper Address?

Training deep neural networks is essentially a massive optimization puzzle. When we add Leaky ReLU activation functions and group sparsity (using the $l_{2,1}$ regularizer to prune entire neurons), the puzzle becomes "nonsmooth" and "nonconvex."

The industry standard, Stochastic Gradient Descent (SGD) and its cousins (like Adam), handles this by applying the "chain rule" even at points where the function isn't technically differentiable. While this works surprisingly well in practice, it lacks mathematical rigor; these methods can't deterministically guarantee they've found a truly stationary point and can stumble in extreme numerical cases. The authors aim to bridge this gap by creating a deterministic algorithm that handles the multi-layer, nonsmooth structure of these networks with theoretical guarantees.

Methods

The authors introduce a framework called IALAM. The approach involves several clever steps:

  1. Variable Splitting: To "peel the complicated composite objective like a bamboo shoot," the authors introduce auxiliary variables ($u$ and $v$) for each layer. This transforms a deep, nested function into a set of simpler constraints.
  2. The Penalty Model (PP): They convert the hard constraints of the network into a partial $l_1$ penalty model. This makes the problem more tractable while maintaining a clear relationship to the original objective.
  3. Two-Level Iteration:
    • Outer Loop (Augmented Lagrangian): Manages the Lagrangian multipliers and penalty parameters to ensure the constraints are eventually satisfied.
  4. Inner Loop (Alternating Minimization): This is the "engine." It swaps between updating the weights/biases ($w, b$) and the auxiliary variables ($u, v$).
  5. Mathematical Rigor: Crucially, the authors prove that their model satisfies the Mangasarian-Fromovitz constraint qualification (MFCQ), a technical condition that ensures the optimization landscape is well-behaved enough to guarantee convergence to a Karush-Kuhn-Tucker (KKT) point.

Datasets

The algorithm was evaluated on two main types of data:

  • Synthetic Datasets: Randomly generated data designed to test the algorithm's ability to recover specific parameters in a controlled environment.
  • MNIST: The classic benchmark of 60,000 handwritten digits. This was used to test the algorithm on a real-world classification task across various network depths (up to four hidden layers).

Key Insights and Ideas

  • The "Chain Rule" Hack: The paper highlights that standard deep learning libraries often calculate "gradients" at non-differentiable points by simply ignoring the math. IALAM provides a mathematically sound alternative that doesn't rely on this "brute force" approach.
  • Leaky ReLU vs. ReLU: The authors provide a theoretical justification for why Leaky ReLU is often better than standard ReLU. They show that the Leaky ReLU network with regularization has a nonempty and bounded solution set, whereas standard ReLU networks might not, potentially leading to instability during training.
  • Closed-Form Efficiency: One of the "aha" moments in the paper is showing that the subproblem for the auxiliary variables ($u, v$) has a unique, closed-form solution. This means the most complex part of the splitting can be solved instantly and exactly, making the alternating minimization highly efficient.

Key Results

  • Superior Sparsity: IALAM consistently found sparser solutions (higher "Column Sparsity Ratio") than SGD, Adam, or ProxSGD. This is vital for model compression and deploying networks on edge devices.
  • Lower Error: On the MNIST dataset, IALAM achieved lower training and test errors compared to popular SGD-based methods. For example, in several tests, IALAM reached higher accuracy levels faster than vanilla SGD or Adadelta.
  • Stability: The feasibility violations (how much the auxiliary variables deviate from the actual network logic) and KKT violations were shown to drop to near zero, confirming the algorithm's theoretical convergence in practice.

Limitations and Future Work

  • Computational Overhead: While IALAM is efficient in terms of iterations, each iteration involves solving subproblems that are more complex than a single backpropagation step in SGD. The authors note it is "more efficient," but the per-iteration wall-clock time on massive-scale models remains a point for further investigation.
  • Scaling to "Big" AI: The experiments focused on relatively small architectures (up to 4 layers, MNIST-scale). Testing IALAM on modern architectures like Transformers or very deep ResNets is a natural next step.
  • ReLU Extension: While the paper focuses on Leaky ReLU, the authors mention the framework can be extended to standard ReLU ($\alpha=0$), though it requires additional constraints to keep the solution set bounded.

Reference: Liu, W., Liu, X., & Chen, X. (2022). An Inexact Augmented Lagrangian Algorithm for Training Leaky ReLU Neural Network with Group Sparsity. arXiv:2205.05428v1.

Summary updated

Abstract

The leaky ReLU network with a group sparse regularization term has been widely used in the recent years. However, training such a network yields a nonsmooth nonconvex optimization problem and there exists a lack of approaches to compute a stationary point deterministically. In this paper, we first resolve the multi-layer composite term in the original optimization problem by introducing auxiliary variables and additional constraints. We show the new model has a nonempty and bounded solution set and its feasible set satisfies the Mangasarian-Fromovitz constraint qualification. Moreover, we show the relationship between the new model and the original problem. Remarkably, we propose an inexact augmented Lagrangian algorithm for solving the new model and show the convergence of the algorithm to a KKT point. Numerical experiments demonstrate that our algorithm is more efficient for training sparse leaky ReLU neural networks than some well-known algorithms.
BibTeX
@misc{liu2022inexact,
  author = {Wei Liu and Xin Liu and Xiaojun Chen},
  title = {{An Inexact Augmented Lagrangian Algorithm for Training Leaky ReLU Neural Network with Group Sparsity}},
  year = {2022},
  eprint = {2205.05428},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2205.05428},
}
Figure