Analysis of training neural networks
How large a training step you can take before a model stops learning, worked out in advance instead of found by watching a run fail.
The short version
- Training a deep network means optimizing a nonconvex loss, and convergence guarantees for that are still an open problem.
- This work carries earlier gradient flow analyses into the discrete gradient descent setting and proves that, under explicit step-size conditions, GD on a deep linear network converges to a critical point of the square loss. For two layers it reaches a global minimum for almost all initializations, and for three or more a global minimum on a manifold of matrices of fixed rank. It needs no initialization close to a global minimum, and it proves the iterates stay bounded instead of assuming it.
- The theoretical key is a bound on the norms of the GD iterates, which keeps them bounded and lets the Lojasiewicz theorem apply. The maximum allowed step size does not decay exponentially with depth: it is of order L⁻³ for a network of depth L. Experiments in my PhD thesis show the loss decreasing in the same way on networks with tanh activations.
- What that buys you in practice: you can compute how large a training step to take before the run starts, at any depth, instead of finding the ceiling by watching a run diverge.
Problem statement and research objective
Context and significance
Modern deep learning relies almost entirely on gradient-based optimization to train neural networks. Despite remarkable empirical success, the theoretical understanding of why gradient descent finds good solutions in highly nonconvex loss landscapes remains incomplete. The objective function of even a simple fully connected network is riddled with saddle points and spurious local minima, yet practitioners observe that standard GD and SGD routinely converge to high-quality solutions. Closing the gap between this empirical observation and rigorous mathematical guarantees is a central question in optimization theory and deep learning.
Prior work on this problem either analyzed gradient flow (the continuous-time limit of GD, which ignores discretization effects) or proved results for GD under restrictive conditions: near-zero initialization on a scalar regression problem, bounded iterates assumed rather than proved, hidden layers wider than the input or the output, or an initialization close to a global minimum. Such conditions exclude models used in practice, such as autoencoders with narrow intermediate layers.
Mathematical formulation
The problem is framed as minimizing the square loss of a deep linear network, a product of weight matrices that parameterize a deep matrix factorization. Given training data, the network output is the composition of L weight matrices, and the loss measures the squared Frobenius-norm distance between the network output and a target matrix. Despite the linearity of the individual layers, the loss function is nonconvex in the factored parameters due to the multiplicative coupling between weight matrices. The analysis focuses on gradient descent with a fixed or slowly decaying learning rate applied directly to these factored parameters.
Scope
In scope: Convergence analysis of discrete GD for deep linear networks, including two-layer, three-layer, and general L-layer architectures; derivation of explicit step-size conditions; numerical experiments on linear networks, extended in the PhD thesis to networks with tanh activations. Out of scope: Stochastic gradient descent analysis (addressed in a companion SampTA 2023 paper), batch normalization effects, and convolutional architectures.
Success criteria
Establish that GD converges under an explicit step-size bound that does not decay exponentially with network depth, and to a global minimum for almost all initializations wherever the analysis reaches it. Then check the theory numerically on linear networks, and in the PhD thesis on networks with tanh activations.
Methodology and approach
Boundedness of the GD iterates
The analysis starts by proving the GD iterates stay bounded throughout training. Without that, gradient norms grow without control, which is the exploding gradient problem, and no convergence guarantee survives it. The proof works from the algebraic structure of the gradient in deep matrix factorizations. Under the step-size condition, it shows that the iterates keep a fixed balancedness constant (a measure of how far the layers drift from being balanced), that the loss never increases, and that every weight matrix stays bounded in norm. This holds without assuming the iterates stay inside a pre-specified compact set, which is where earlier analyses had to start.
Convergence through a discrete Lojasiewicz inequality
With boundedness in hand, the analysis connects the GD dynamics to the Lojasiewicz inequality, a tool from real algebraic geometry. The square loss of a linear network is a polynomial, so it is real-analytic and satisfies a Lojasiewicz gradient inequality near every critical point. Boundedness keeps the GD trajectory in the region where that inequality applies, and a discrete-time version of the Lojasiewicz convergence theorem then forces the iterates to converge to a single critical point of the loss.
From critical points to global minima
Reaching a critical point is not enough on its own, since that point could be a saddle or a local minimum. The analysis handles this depth by depth:
- Two-layer networks. Gradient descent avoids strict saddle points for almost all initializations. For two layers, the strict-saddle analysis of the loss then turns convergence to a critical point into convergence to a global minimum.
- Three or more layers. The result is convergence to a global minimum on the manifold of matrices of some fixed rank, a rank the analysis cannot determine in advance. The paper conjectures that the two-layer result extends to deeper networks, and notes that the current proof method cannot show it.
Step-size conditions
The step-size bound is what makes this work usable. It does not decay exponentially with depth: with the balancedness constant chosen of order L⁻², the step sizes need to be of order L⁻³. The theory therefore reaches deeper architectures without demanding learning rates too small to train with.
Results and impact
Key theoretical results
| Result | Network depth | Guarantee |
|---|---|---|
| Convergence to critical point | Any L | GD converges to a critical point of the square loss under the explicit step-size bound |
| Global convergence | L = 2 | GD converges to a global minimum for almost all initializations |
| Rank-manifold convergence | L ≥ 3 | GD converges to a global minimum on the manifold of fixed-rank matrices |
| Step-size scalability | Any L | Maximum step size does not decrease exponentially with depth |
Experiments: linear networks in the paper, tanh networks in the thesis
The paper trains linear networks of depth 2, 3, and 5 with the step size set at the bound, and the loss converges. A step size above the bound still converged in one experiment, which suggests the bound may not be entirely sharp. Raising it further leads to divergence, so some bound on the step size is necessary. My PhD thesis extends the experiments to networks with tanh activations on the last two layers, trained with the same step-size formula, where the loss decreases steadily (Figure 2, top). The theorems themselves cover linear networks only.
Limitations and what comes next
The analysis covers the square loss and fully connected architectures. Cross-entropy loss, convolutional layers, and residual connections are still open. The companion SGD work (SampTA 2023) starts on the stochastic side, using stochastic approximation and asymptotic pseudo-trajectory frameworks to establish convergence guarantees for SGD on linear neural networks under decreasing and adaptive learning rate schedules.