A Geometric Approach of Gradient Descent Algorithms in Neural Networks

Yacine Chitour, Zhenyu Liao, Romain Couillet

Abstract

This paper provides a rigorous geometric proof that continuous-time gradient descent in linear neural networks (LNNs) almost always converges to a global minimum, effectively avoiding the "traps" of saddle points. By leveraging dynamical systems theory and discovering structural invariants within the network, the authors demonstrate that training trajectories never diverge to infinity and that the basins of attraction for saddle points have a mathematical volume of zero for single-hidden-layer networks.

Introduction

Training deep neural networks involves navigating highly non-convex loss landscapes. In general non-convex optimization, algorithms like Gradient Descent (GD) are prone to getting stuck in sub-optimal local minima or saddle points. Yet, in practice, deep learning models routinely converge to global minima. To understand this phenomenon, researchers often study linear neural networks (LNNs)—networks without non-linear activation functions.

While previous research established that LNNs have no "bad" local minima and that their saddle points have directions of escape, a significant gap remained: it was not proven that gradient descent trajectories actually avoid these saddle points from random initializations, nor was it proven that weights would remain bounded. The authors address this by formalizing the "overfitting conjecture" (OVF): the idea that for almost any random initialization, continuous-time gradient descent in an LNN will successfully navigate the landscape and converge to a global minimum.

Theoretical Framework

The authors approach the problem through the lens of differential geometry and dynamical systems. Instead of discrete steps, they model training as Continuous-Time Gradient Flow (Gradient Descent Dynamics, or GDD).

A key insight is the identification of Network Invariants. The cascading structure of neural networks creates hidden mathematical quantities—specifically, the difference between the squared weight matrices of adjacent layers—that remain constant throughout the training process. These invariants ensure that training is inherently bounded; because the magnitude differences are conserved, the weights cannot explode to infinity.

Architecture and dimensions of a linear neural network.

To analyze the convergence of these bounded trajectories, the authors employ Lojasiewicz’s Theorem from real algebraic geometry. This theorem guarantees that if a trajectory on a polynomial landscape is bounded, it must converge to a critical point, ruling out infinite oscillation. Furthermore, they use the concept of Normal Hyperbolicity to analyze the "stable manifolds" (basins of attraction) of saddle points, proving that the regions of initialization space that lead to saddle points are infinitely thin.

Key Results

The study yields several significant theoretical results:

  • Global Convergence for Arbitrary Depth: For linear networks of any depth, every gradient descent trajectory is bounded and will converge to a critical point.
  • Exponential Convergence Rates: Under specific "pyramidal" dimensional conditions (where each layer is smaller than the last), GD converges to the global minimum at an exponential rate.
  • Proof of the OVF Conjecture ($H=1$): For single-hidden-layer linear networks, the authors successfully proved the overfitting conjecture. For almost every initialization in the parameter space, the network will converge to a global minimum.

Discussion and Future Work

While the authors proved convergence to some critical point for any depth, the proof that GD almost always escapes saddles to find a global minimum is currently limited to single-hidden-layer networks ($H=1$). Deeper networks ($H \ge 2$) contain complex saddle points with non-negative Hessians, requiring more sophisticated global analysis.

Additionally, the analysis assumes continuous-time gradient flow. While a standard theoretical proxy, real-world training uses discrete step sizes which can introduce different dynamics. Future research directions include extending this geometric framework to non-linear networks (e.g., ReLU) and applying it to modern optimizers like SGD with Momentum or Adam. Proving trajectory boundedness in non-linear regimes remains a primary open challenge.

Summary updated

BibTeX
@inproceedings{chitour2022geometric,
  author = {Yacine Chitour and Zhenyu Liao and Romain Couillet},
  title = {{A Geometric Approach of Gradient Descent Algorithms in Neural Networks}},
  booktitle = {Mathematical},
  year = {2022},
  doi = {10.3934/mcrf.2022021},
}
Figure