An Augmented Lagrangian Method for Training Recurrent Neural Networks

Yue Wang, Chao Zhang, Xiaojun ChenarXiv 2024 · DOI · arXiv

Recurrent Neural Networks (RNNs) are the workhorses of sequential data, but training them is notoriously difficult. Traditional methods like Backpropagation Through Time (BPTT) often run into the "vanishing or exploding gradient" problem, and the non-smooth nature of popular activation functions like ReLU adds another layer of complexity.

In this paper, researchers Yue Wang, Chao Zhang, and Xiaojun Chen propose a fresh perspective: stop treating RNN training as a simple unconstrained minimization and start treating it as a constrained optimization problem. By using an Augmented Lagrangian Method (ALM), they bypass many of the traditional pitfalls of gradient-based training.

TL;DR

The authors reformulate RNN training into a constrained optimization problem using auxiliary variables, effectively "breaking" the complex nested structure of the network. They solve this using a novel Augmented Lagrangian Method (ALM) where the subproblems have efficient, closed-form solutions, leading to better convergence and higher accuracy than standard Adam or SGD.

What Problem Does This Paper Address?

Training an RNN involves minimizing a loss function that is a "composition of compositions." Because the same weights are used at every time step, the gradient calculation involves a long chain of multiplications. If those weights are even slightly larger or smaller than one, the gradients can explode to infinity or vanish to zero over long sequences ($T$).

Furthermore, modern networks use ReLU (Rectified Linear Unit), which is non-smooth at zero. Standard gradient descent assumes smoothness, and while it works in practice, it lacks rigorous convergence guarantees in these non-smooth, non-convex settings. The authors aim to provide a method that is both theoretically sound and numerically superior to standard gradient descent variants.

Methods

The core innovation is a reformulation of the training objective. Instead of a single, deeply nested function, they introduce auxiliary variables for the hidden states ($h_t$) and pre-activation values ($u_t$). This turns the training into a problem with a simple objective function subject to a series of constraints:

  1. $u_t = Wh_{t-1} + Vx_t + b$ (Linear dynamics)
  2. $h_t = \sigma(u_t)$ (Activation function)

To solve this, they employ an Augmented Lagrangian Method (ALM). The ALM handles constraints by adding them to the objective function along with penalty terms and "Lagrange multipliers."

To solve the resulting subproblems, they design a Block Coordinate Descent (BCD) algorithm. The magic here is that the updates for each block—the weights ($W, V, A, b, c$), the hidden states ($h$), and the pre-activations ($u$)—all have closed-form solutions. This means you don't need to perform an internal gradient descent loop with its own learning rate tuning; you just calculate the optimal update directly.

Datasets

The authors evaluated their method on both synthetic and real-world data:

  • Synthetic Datasets: Two sets with sequence lengths $T=10$ and $T=500$. These were generated using known weight matrices with added noise to test the algorithm's ability to recover underlying patterns.
  • Volatility of S&P Index: A real-world dataset consisting of monthly realized volatility of the S&P 500 index and 11 exogenous variables from 1973 to 2009 ($T=437$).

Key Insights and Ideas

  • Breaking the Chain: By introducing auxiliary variables, the "chain" of the chain rule is broken. The gradients no longer need to be propagated through time in the traditional sense, which mitigates the vanishing/exploding gradient problem.
  • Theoretical Rigor: The authors prove that their reformulated problem satisfies a technical condition called NNAMCQ (No Nonzero Abnormal Multiplier Constraint Qualification). This is a big deal because it guarantees that any local minimizer of their problem is a KKT point—essentially a point that satisfies the first-order optimality conditions.
  • Global Convergence: They establish that the ALM sequence globally converges to a KKT point, providing a level of mathematical certainty that standard SGD lacks.
  • Handling Non-smoothness: The BCD approach handles the non-smoothness of ReLU (and Leaky ReLU/ELU) elegantly through the closed-form updates for the $u$ and $h$ blocks, rather than relying on sub-gradients.

Key Results

The ALM was compared against several state-of-the-art optimizers: Gradient Descent (GD), GD with Clipping (GDC), Nesterov Momentum (GDNM), SGD, and Adam.

  • Superior Accuracy: In almost every test case (across different initialization strategies like He, Glorot, and Xavier), the ALM achieved lower training and test errors (TrainErr and TestErr). For example, on the $T=500$ synthetic task, ALM's training error was orders of magnitude lower than Adam's.
  • Robustness to Initialization: While standard GD and Adam are highly sensitive to how you initialize weights, the ALM showed remarkably consistent performance regardless of the starting point.
  • Efficiency: Despite the overhead of managing auxiliary variables, the closed-form BCD updates allow the ALM to reach high-quality solutions quickly in terms of CPU time.

Limitations and Future Work

  • Architecture Scope: This paper focuses on the Elman RNN, the simplest recurrent architecture. While the authors suggest the method can be generalized, it hasn't yet been tested on more complex units like LSTMs or GRUs, which have more intricate gating mechanisms.
  • Scalability: The current approach requires storing auxiliary variables for every time step, which could become memory-intensive for extremely long sequences or massive datasets.
  • Stochastic Extension: The current ALM is deterministic. Developing a stochastic version of this ALM would be necessary to scale the method to the "Big Data" regimes where deep learning typically thrives.

Summary updated

Abstract

Recurrent Neural Networks (RNNs) are widely used to model sequential data in a wide range of areas, such as natural language processing, speech recognition, machine translation, and time series analysis. In this paper, we model the training process of RNNs with the ReLU activation function as a constrained optimization problem with a smooth nonconvex objective function and piecewise smooth nonconvex constraints. We prove that any feasible point of the optimization problem satisfies the no nonzero abnormal multiplier constraint qualification (NNAMCQ), and any local minimizer is a Karush-Kuhn-Tucker (KKT) point of the problem. Moreover, we propose an augmented Lagrangian method (ALM) and design an efficient block coordinate descent (BCD) method to solve the subproblems of the ALM. The update of each block of the BCD method has a closed-form solution. The stop criterion for the inner loop is easy to check and can be stopped in finite steps. Moreover, we show that the BCD method can generate a directional stationary point of the subproblem. Furthermore, we establish the global convergence of the ALM to a KKT point of the constrained optimization problem. Compared with the state-of-the-art algorithms, numerical results demonstrate the efficiency and effectiveness of the ALM for training RNNs.
BibTeX
@misc{wang2024augmented,
  author = {Yue Wang and Chao Zhang and Xiaojun Chen},
  title = {{An Augmented Lagrangian Method for Training Recurrent Neural Networks}},
  year = {2024},
  eprint = {2402.13687},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2402.13687},
}
Figure