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 converges to a global minimum for almost all initializations in deep linear networks. It needs neither the deficiency-margin condition nor the a priori boundedness that earlier results assumed.
- The theoretical key is a norm-based bound on the GD iterates that controls exploding gradients and opens the door to a discrete Lojasiewicz inequality. The maximum permissible learning rate that falls out of it stops decreasing exponentially with depth, which is what separates this result from what came before. Experiments then show the same convergence behavior on nonlinear 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 theoretical work on this problem either analyzed gradient flow (the continuous-time limit of GD, which ignores discretization effects) or imposed restrictive assumptions such as deficiency-margin conditions and a priori boundedness of iterates. These assumptions rarely hold in practice and limit the applicability of the resulting convergence theorems to real training scenarios.
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; empirical validation on nonlinear networks. 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 to a global minimum for almost all initializations under an explicit step-size bound that does not degrade exponentially with network depth, then check the theory empirically on standard nonlinear architectures.
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 develops a norm-based bound: working from the algebraic structure of the gradient in deep matrix factorizations, it shows the product of weight matrix norms never increases along the GD trajectory under the prescribed step-size condition. 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. The structure of the loss makes every critical point with a certain rank property a global minimum. Put that together with the Lojasiewicz result and GD converges to a global minimum for almost all initializations.
- Three or more layers. The result is convergence to a global minimum on the manifold of matrices of a fixed rank. The initialization fixes that rank, and it stays invariant along the GD trajectory, a property carried over from the continuous gradient flow analysis and confirmed to survive discretization.
Step-size conditions
The step-size bound is what makes this work usable. In earlier discrete-time analyses, the maximum permissible step size decreases exponentially with depth L. The conditions here depend polynomially on the problem parameters instead, so the theory 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 |
Empirical validation on nonlinear networks
The framework is built for linear networks, and the practical consequences reach further. Experiments on networks with tanh activations show the derived learning rate bounds and the convergence behavior carrying over to nonlinear architectures. Push past the prescribed step-size bound and training diverges, which is the check that the theoretical condition is tight rather than conservative.
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.