Asymptotics of Gradient-based Neural Network Training Algorithms

Sayandev Mukherjee, Terrence FineNeurIPS 1994

Introduction

When training neural networks using online gradient descent—updating weights after every single example rather than in batches—the weights do not simply settle on a single optimal point. Instead, the constant stream of noisy data causes them to "jitter" or fluctuate around an optimal value.

In the early 1990s, most researchers relied on classical stochastic approximation to understand this behavior. This theory assumes that the learning rate ($\mu$) eventually shrinks to zero, leading to a predictable Gaussian (normal) distribution for the weights. However, in practical engineering applications, it is common to use a fixed, non-zero learning rate. This paper investigates a fundamental question: When a neural network is trained indefinitely with a fixed learning rate, does a stable distribution of weights even exist? And if it does, is it truly Gaussian?

The authors prove that for any fixed, non-zero learning rate, the true limiting distribution is actually non-Gaussian, though it converges toward a Gaussian distribution as the learning rate approaches zero.

Methodology

To rigorously analyze weight dynamics, the authors treat the sequence of weight updates as a discrete-time continuous state-space Markov process. Their methodology is divided into two primary approaches:

  • Exact Analysis (1D Case): For a simple one-dimensional scenario involving a single sigmoidal node, the authors apply Foster’s criteria to prove that the weight iterates are "positive-recurrent." This guarantees that the weights will eventually settle into a stable, unique limiting distribution.
  • Linearization (General Case): Because the exact mathematics become intractable for complex, multi-dimensional networks, the authors apply a Taylor series expansion to linearize the update equation around the optimal weight ($w^0$). This transforms the neural network problem into one of "random affine transformations." By leveraging the theory of random matrices—specifically Berger’s Lemma—they prove the existence of a unique stationary distribution for small, fixed learning rates.
  • Moment Analysis: To test for "Gaussian-ness," the authors calculate the first four moments of this distribution: mean, variance, skewness, and kurtosis.

The paper relies heavily on theoretical proofs, supported by controlled simulations rather than large-scale empirical benchmarks. The synthetic 1D simulations tested a single sigmoidal node ($1 / [1 + e^{-wX}]$) trained on standard normal inputs with Gaussian noise. The experiments evaluated eight specific configurations, varying the learning rate ($\mu \in \{0.1, 0.2, 0.3, 0.5\}$) and noise variance ($\sigma^2 \in \{0.1, 0.5\}$).

Key Findings

The paper successfully bridges the gap between fixed-learning-rate realities and classical stochastic approximation, yielding several critical insights:

  • The Non-Gaussian Reality: The most significant theoretical breakthrough is the proof that the limiting distribution is generally not Gaussian. For a fixed learning rate, the "jitter" takes on a specific shape dictated by the network's architecture and the underlying data distribution. Statistical testing using skewness and kurtosis confirmed significant normality violations for certain parameter pairs (e.g., $\mu=0.1, \sigma=0.1$).
  • Reconciling Theories: While the distribution is non-Gaussian for any $\mu > 0$, the authors demonstrate that the normalized weight error does indeed become Gaussian as $\mu$ vanishes.
  • Existence of a Limit: The paper rigorously establishes that for a wide class of feedforward networks, a unique limiting distribution of weights exists provided the learning rate is sufficiently small. Kolmogorov-Smirnov tests in simulations confirmed that the weight sequences reach this stable distribution.
  • Practical Implications: Despite the theoretical proof of non-Gaussianity, the results indicate that for very small learning rates, the deviation from a Gaussian distribution is minimal. For most practical engineering purposes, the Gaussian model remains a "good enough" approximation.

Limitations

While foundational, the study acknowledges several limitations:

  • The Linearization Crutch: The proof for the general multi-dimensional case relies on a linearization approximation. This holds true only when the weights are already "close" to the optimum and fails to describe the distribution during the early, chaotic phases of training.
  • Intractability of Multiple Parameters: The exact, non-linearized method successfully used for the 1D case remains mathematically intractable for networks with many parameters.
  • Assumption of I.I.D. Data: The analysis assumes that the training data is independent and identically distributed (i.i.d.). In real-world online learning scenarios, such as reinforcement learning, this assumption is frequently violated.

Summary updated

BibTeX
@inproceedings{mukherjee1994asymptotics,
  author = {Sayandev Mukherjee and Terrence Fine},
  title = {{Asymptotics of Gradient-based Neural Network Training Algorithms}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1994},
}
Figure