Backpropagation Convergence via Deterministic Nonmonotone Perturbed Minimization

Olvi L. Mangasarian, Mikhail V. SolodovNeurIPS 1993

Introduction

In the early 1990s, backpropagation (BP) was already the workhorse of neural network training, but its theoretical foundations remained somewhat shaky. From an optimization perspective, "online" BP—updating weights after every single training example—is problematic because it is not a true descent method. While an update might decrease the error for one specific training example, it might simultaneously increase the total error across the entire dataset. This makes the error function "nonmonotone," causing the optimization path to zig-zag rather than move steadily toward a minimum.

At the time, existing convergence proofs were largely stochastic, relying on the assumption that training data is a random variable. This paper addresses that gap by providing a rigorous, purely deterministic proof for the convergence of the backpropagation algorithm. By treating BP as a "nonmonotone perturbed gradient method," the authors establish that the algorithm is guaranteed to reach a stationary point based on its own internal calculus, regardless of whether the data is random, even when incorporating momentum, weight decay, or parallel processing.

Methods & The Perturbation Framework

The core contribution of the paper is reframing BP as a Deterministic Nonmonotone Perturbed Gradient Method.

  1. Perturbation Framework: The authors treat the difference between a single-example gradient (used in online BP) and the true gradient of the entire dataset as a "perturbation" or error term.
  2. Serial BP with Momentum (Algorithm 2.1): They define a standard online BP update that explicitly includes a momentum term ($\alpha$) and a learning rate ($\eta$).
  3. Parallel BP (Algorithm 2.2): They introduce a parallel version where the dataset is partitioned across $k$ processors. Each processor runs serial BP on its subset, and their resulting weights are averaged (synchronized) at the end of each major iteration (epoch).
Schematic of the Parallel Backpropagation Algorithm showing data partitioning, local serial BP, and weight averaging.

To guarantee mathematical convergence, the authors prove that if the learning rates are chosen such that their sum diverges ($\sum \eta_i = \infty$) but the sum of their squares converges ($\sum \eta_i^2 < \infty$), the algorithm will eventually stabilize at a stationary point where the gradient is zero.

Key Insights

  • BP is not strictly "Gradient Descent": The authors point out that calling online BP "gradient descent" is technically incorrect in optimization terms because it doesn't guarantee a decrease in the objective function at every step. A more accurate label is a nonmonotone perturbed gradient algorithm.
  • The "Price" of Convergence: To guarantee convergence, the learning rate and momentum must asymptotically tend toward zero. While practitioners often use fixed learning rates for speed, this paper defines the specific decay schedule required for absolute mathematical certainty.
  • Robustness Justified: By viewing BP as a perturbed system, the paper provides a theoretical justification for why neural networks are robust to noise. If the network can recover from the "perturbations" inherent to online training, it can likely recover from other small numerical disturbances.
  • Parallelization via Averaging: The paper validates a simple parallelization strategy: split the data, train locally, and average the weights. They prove this approach shares the exact same convergence guarantees as the serial version.

Key Results

  • Theorem 2.1: As the main result of the paper, this theorem proves that for both serial and parallel BP, the sequence of error values will converge, and the gradient will vanish ($\nabla f(x) \to 0$).
  • Stationary Point Guarantee: Every accumulation point of the BP iterates is proven to be a stationary point of the error function.
  • Unified Theory: The proof is robust enough to simultaneously cover several popular variations of BP, including standard online BP, BP with a momentum term, BP with weight decay (regularization), and parallelized BP.

Limitations and Future Work

  • Local vs. Global Minima: Like most first-order optimization proofs, this paper only guarantees convergence to a stationary point. It cannot guarantee that the algorithm will find the global minimum; the network might still get stuck in a local minimum or a saddle point.
  • Learning Rate Practicality: The mathematical conditions for convergence require the learning rate to vanish over time. In practical applications, this can lead to impractically slow training in the later stages. The authors note that practitioners often use small, finite learning rates to obtain "approximate" solutions much faster.
  • Fixed Topology: The analysis assumes the network architecture (e.g., the number of hidden units and layers) is fixed. It does not address how dynamically changing the topology during training might affect these convergence guarantees.

Summary updated

BibTeX
@inproceedings{mangasarian1993backpropagation,
  author = {Olvi L. Mangasarian and Mikhail V. Solodov},
  title = {{Backpropagation Convergence via Deterministic Nonmonotone Perturbed Minimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1993},
}
Figure