Global Convergence and Geometric Characterization of Slow to Fast Weight Evolution in Neural Network Training for Classifying Linearly Non-Separable Data

Ziang Long, Penghang Yin, Jack XinarXiv 2020 · arXiv

Abstract

This paper investigates the mathematical foundations of the "slow-to-fast" transition frequently observed during the training of deep neural networks. By analyzing one-hidden-layer ReLU networks trained on linearly non-separable data, the authors identify a critical "Geometric Condition" (GC) that governs training dynamics. They demonstrate that training consists of two distinct phases: a slow "weight-spreading" phase where neurons search for an optimal configuration, and a fast convergence phase triggered once the convex hull of the weights surrounds the origin in a projected space. This framework provides a global convergence guarantee and offers a theoretical explanation for why over-parameterization accelerates the training process.

Introduction

In the practice of deep learning, researchers often observe a distinct "plateau" effect: the training loss remains stagnant for many iterations before suddenly plunging toward zero. While this phenomenon is ubiquitous, providing a rigorous mathematical explanation for this "click" has remained a challenge. Most existing convergence theories rely on the "over-parameterized" regime—often characterized by the Neural Tangent Kernel (NTK)—where weights stay very close to their random initialization. However, in practical settings, weights often evolve significantly from their starting points.

Published in AIMS' Journals (and appearing on arXiv in late 2020), authors Ziang Long, Penghang Yin, and Jack Xin provide a theoretical explanation for this transition by analyzing the geometry of weight evolution. They move beyond the simplified case of linearly separable data to address more realistic, linearly non-separable data structures.

Problem Statement: Landscape and Dynamics

The authors tackle two primary challenges in neural network theory:

  1. The Landscape Problem: In a non-convex and non-smooth optimization space, why does gradient descent consistently avoid bad local minima to find global solutions?
  2. The Dynamics Problem: What governs the transition between the slow initial progress and the subsequent rapid convergence?

To address these, the study focuses on data where different classes lie in orthogonal subspaces. This structure serves as a high-dimensional approximation of real-world data, such as image sets, where features for different categories (e.g., "cats" vs. "cars") occupy distinct regions of the feature space.

Methodology

The researchers analyzed a one-hidden-layer ReLU network trained using Gradient Descent (GD) on a hinge loss function. Their methodology involved several key components:

  • Subspace Decomposition: By assuming data classes are orthogonal, the authors proved that the evolution of weights associated with each class can be analyzed independently, simplifying the complex high-dimensional dynamics.
  • Landscape Analysis: They established that under a "non-degenerate data condition," every critical point of the population loss is a global minimum, effectively explaining why the optimizer does not get trapped.
  • Geometric Condition (GC): The central contribution of the paper is the definition of the GC. The transition to fast convergence occurs when the convex hull of the weight vectors (projected onto a unit sphere) contains the origin.

The Two-Phase Training Evolution

The paper characterizes training as a "two-phase dance":

Phase 1: The Slow Weight-Spreading Phase

During the initial stage of training, the weights are "searching" the space. If the initial weights are clustered in a narrow direction (a "half-space"), they cannot effectively represent the complexity of the non-separable data. In this phase, the gradient is relatively uninformative, leading to the observed plateau. The weights must "spread out" over the unit sphere to satisfy the Geometric Condition.

Phase 2: The Fast Convergence Phase

Once the weights sufficiently "bracket" or surround the origin, the Geometric Condition is met. At this point, the gradient becomes highly informative, and the network enters a phase of rapid convergence toward the global minimum, resulting in zero classification error.

Key Insights and Results

Global Convergence Guarantees

The authors provide a rigorous proof that gradient descent will converge to a global minimum with zero classification error, provided the weights stay bounded—a condition consistently observed in their numerical simulations.

The Role of Over-parameterization

The theory offers a fresh perspective on why larger models train faster. The authors prove that as the number of neurons ($k$) increases, the probability that a random initialization already satisfies the Geometric Condition approaches 1. Consequently, massive models often skip the slow phase entirely, beginning their training in the fast convergence regime.

Empirical Validation

The researchers validated their theoretical findings using both synthetic and real-world data:

  • Synthetic Data: By using linearly independent subspaces in $\mathbb{R}^4$, they controlled the angles between classes to test the limits of the orthogonality assumption.
  • MNIST: Using a simplified LeNet-5 architecture, they demonstrated that real-world features cluster into subspace structures. Visualizations of the training process showed the predicted "click" occurring around iteration 400, marking the transition from the slow to the fast phase.

Conclusion and Future Directions

This research provides a significant step toward understanding the non-linear dynamics of neural network training. By identifying the Geometric Condition, the authors bridge the gap between abstract optimization theory and the practical observations of deep learning practitioners.

While the current proof relies on the assumption of orthogonal subspaces and shallow architectures, it sets the stage for future work. The authors suggest that developing methods to monitor the GC in real-time could lead to new diagnostic tools for identifying and fixing "stuck" models in more complex, multi-layer architectures.

Summary updated

Abstract

In this paper, we study the dynamics of gradient descent in learning neural networks for classification problems. Unlike in existing works, we consider the linearly non-separable case where the training data of different classes lie in orthogonal subspaces. We show that when the network has sufficient (but not exceedingly large) number of neurons, (1) the corresponding minimization problem has a desirable landscape where all critical points are global minima with perfect classification; (2) gradient descent is guaranteed to converge to the global minima. Moreover, we discovered a geometric condition on the network weights so that when it is satisfied, the weight evolution transitions from a slow phase of weight direction spreading to a fast phase of weight convergence. The geometric condition says that the convex hull of the weights projected on the unit sphere contains the origin.
BibTeX
@misc{long2020global,
  author = {Ziang Long and Penghang Yin and Jack Xin},
  title = {{Global Convergence and Geometric Characterization of Slow to Fast Weight Evolution in Neural Network Training for Classifying Linearly Non-Separable Data}},
  year = {2020},
  eprint = {2002.12563},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2002.12563},
}
Figure