A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks

Sanjeev Arora; Nadav Cohen; Noah Golowich; Wei Hu

Source-linked AI summary

A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks

Sanjeev Arora, Nadav Cohen, Noah Golowich, Wei Hu

arXiv:1810.02281v3Oct 4, 2018cs.LGcs.NEstat.ML

TL;DR

The paper asks when gradient descent efficiently reaches the global optimum in deep linear networks, where depth creates non-convex training problems. It analyzes discrete optimization trajectories on whitened-data ℓ2 loss and proves linear-rate convergence under width and initialization conditions, including constant-probability success for scalar regression.

Problem
The paper addresses the difficulty of rigorously proving efficient global convergence for gradient descent in deep linear networks.
Method
The paper uses a trajectory-based analysis of gradient descent on deep linear networks minimizing ℓ2 loss over whitened data.
Results
Linear-rate convergence to the global minimum holds when hidden widths support full rank and initialization is approximately balanced with positive deficiency margin.
Takeaways & Limitations
For scalar regression, balanced or standard random near-zero initialization meets the assumptions with constant probability, so global convergence follows with constant probability.
Takeaways & Limitations
For rank-deficient targets, the analysis requires aligned left and right null spaces at initialization; relaxing this requirement remains future work.

Abstract

from arXiv · show

We analyze speed of convergence to global optimum for gradient descent training a deep linear neural network (parameterized as $x \mapsto W_N W_{N-1} \cdots W_1 x$) by minimizing the $\ell_2$ loss over whitened data. Convergence at a linear rate is guaranteed when the following hold: (i) dimensions of hidden layers are at least the minimum of the input and output dimensions; (ii) weight matrices at initialization are approximately balanced; and (iii) the initial loss is smaller than the loss of any rank-deficient solution. The assumptions on initialization (conditions (ii) and (iii)) are necessary, in the sense that violating any one of them may lead to convergence failure. Moreover, in the important case of output dimension 1, i.e. scalar regression, they are met, and thus convergence to global optimum holds, with constant probability under a random initialization scheme. Our results significantly extend previous analyses, e.g., of deep linear residual networks (Bartlett et al., 2018).

1 INTRODUCTION

The paper studies gradient descent trajectories in general deep linear networks and proves linear-rate convergence under width and initialization conditions. It extends prior trajectory-based results beyond linear residual networks and identifies when scalar regression succeeds with constant probability.

The paper analyzes gradient descent for general deep linear neural networks, extending trajectory-based analysis beyond the residual setting.The analysis covers the residual setting of Bartlett et al. (2018) and additional configurations closer to practical deep learning.
Linear-rate convergence to the global minimum holds when hidden widths meet the input-output rank requirement and initialization is approximately balanced.The hidden dimensions must be at least the minimum of the input and output dimensions.
The initialization must also have initial loss below every rank-deficient solution’s loss.This condition is described as a deficiency-margin requirement around the target.
Both initialization assumptions are necessary because violating either may cause convergence failure.The paper demonstrates these failures explicitly.
For scalar regression, standard random near-zero initialization satisfies the assumptions with probability close to 0.5, yielding convergence to the global minimum.The conclusion also describes constant-probability success under balanced initialization.

2 GRADIENT DESCENT FOR DEEP LINEAR NEURAL NETWORKS

The paper formulates deep linear-network training as gradient descent on squared Frobenius loss over whitened data. Although depth greater than one makes the problem non-convex, direct trajectory analysis provides a route to linear-rate convergence.

A linear predictor trained on whitened data minimizes squared Frobenius distance to a target matrix Φ.The target is the empirical cross-covariance between labels and instances.
A depth-N network realizes the end-to-end map W1:N = W_N W_{N−1} ··· W_1, with loss equal to that of the corresponding end-to-end linear map.The network factors the target-matrix approximation through its layer matrices.
Gradient descent trains the layer matrices by iteratively applying updates with configurable learning rate η.The updates are indexed by layer j and iteration t.
For depth N = 1, the objective is smooth and strongly convex, whereas depth greater than 1 yields a fundamentally non-convex program.For deeper networks, strict-saddle landscape arguments do not generally suffice beyond the shallow case.
The analysis uses gradient-descent trajectories because landscape arguments cannot generally prove convergence for deep networks.The paper distinguishes this trajectory-based route from direct critical-point analysis.

3 CONVERGENCE ANALYSIS

The analysis establishes linear convergence of gradient descent for deep linear networks under approximate balancedness and a positive deficiency margin at initialization. It also identifies initialization trade-offs, architectural requirements, and a constant-probability guarantee for scalar regression.

Core concepts: Approximate balancedness keeps layer singular values aligned, while deficiency margin keeps the end-to-end matrix away from rank deficiency.Balanced layers share corresponding non-zero singular values, and deficiency margin ensures nearby matrices retain singular values bounded below.
Main theorem: Gradient descent converges to the global minimum when initialization satisfies approximate balancedness and positive deficiency margin under a suitable learning rate.The theorem guarantees that the loss at iteration T is at most ϵ under its initialization and step-size conditions.
Initialization: Initialization involves a trade-off: very small variance weakens deficiency margin, whereas large variance jeopardizes both balancedness and deficiency margin.The paper relates these regimes to vanishing-gradient and exploding-gradient behavior, respectively.
Assumptions: Both initialization assumptions are necessary: violating either approximate balancedness or deficiency margin may cause convergence failure.Deficiency margin alone can still permit divergence because the deep-network loss is non-smooth without balancedness.
Architectural scope: The theorem requires every hidden dimension to be at least min{d0, dN}, because the initial end-to-end matrix must have full rank.No other assumptions on depth or input, output, and hidden dimensions are imposed.
Balanced initialization: For scalar regression, balanced initialization yields linear convergence with constant probability over the random initialization.The construction ensures perfect balancedness and supports the theorem's conditions with probability at least any fixed p satisfying 0 < p < 1/2.

4 EXPERIMENTS

Experiments compare customary and balanced initialization for deep linear networks, finding that balanced initialization broadens fast-convergence regimes and mitigates depth-related instability. An additional MNIST experiment tests whether this benefit extends beyond the analyzed linear setting.

Experimental setup: Balanced initialization theoretically offers convergence guarantees with constant probability over initialization randomness and is tested empirically for practical benefit.The experiments focus on linear networks trained by gradient descent with ℓ2 loss over whitened data, while a final experiment adds nonlinear and stochastic components.
Linear-network experiments: The UCI Ethanol experiment trains a three-layer network with hidden widths 32 and measures iterations to reach training loss within ϵ = 10^-5 of optimum.Learning rates are grid-searched independently for each initialization standard deviation.
Linear-network experiments: Increasing depth from three to eight layers aggravates initialization instability, leaving only a narrow standard-deviation band that yields convergence.Both models use hidden widths of 32 under the same experimental protocol.
Interpretation: Under layer-wise independent initialization, end-to-end weight magnitude varies exponentially with depth, restricting standard deviations that support a usable deficiency margin and approximate balancedness.Balanced initialization is designed to circumvent these depth-dependent difficulties.
Beyond the analyzed setting: A final experiment evaluates balanced and customary initialization in a fully connected ReLU MNIST network using softmax-cross-entropy loss and stochastic optimization.These factors are outside the paper’s theoretical analysis.

5 RELATED WORK

Related work includes landscape and trajectory-based analyses of neural-network optimization, with prior deep linear-network results largely addressing gradient flow rather than discrete gradient descent. Bartlett et al. provide a rigorous gradient-descent result for a restricted linear residual setting.

Landscape analyses: Landscape analyses seek no poor local minima and strict-saddle properties that imply convergence to a global minimum under suitable smoothness assumptions.This is one prominent approach to analyzing gradient-based optimization in deep learning.
Trajectory-based analyses: Trajectory-based analyses focus on the optimizer’s path, but many cited results apply only to shallow models.The approach is motivated by the possibility that only a small region near optimizer trajectories matters.
Deep linear networks: Prior deep linear-network treatments by Saxe et al. and Arora et al. analyze gradient flow, not computational efficiency for discrete gradient descent.The paper draws technical ideas from these analyses while addressing discrete updates.
Closest prior result: Bartlett et al. are identified as the only existing work known to rigorously prove global linear convergence for gradient descent training a deep model.Their setting also uses linear networks, ℓ2 loss, and whitened data.
Comparison: The present work broadens the dimensional and initialization settings beyond linear residual networks, allowing configurations without bottlenecks and approximate balancedness.The cited comparison contrasts uniform width and identity initialization with more general choices.

6 CONCLUSION

The paper proves linear-rate convergence of gradient descent to global minima for broad deep linear networks under structural and initialization conditions. It also establishes the necessity of the initialization assumptions and identifies balanced initialization as a promising direction beyond the analyzed setting.

Conclusion: The theorem covers arbitrary depth and dimension configurations that support full rank, meaning no hidden layer is smaller than both input and output dimensions.The network must avoid hidden-layer bottlenecks.
Conclusion: Linear-rate convergence to global minima is proven when initial weights are approximately balanced and the end-to-end matrix has positive deficiency margin.These conditions accompany the full-rank dimensional requirement.
Conclusion: Violating either approximate balancedness or deficiency margin may lead to convergence failure, demonstrating that both initialization assumptions are necessary.The paper reports explicit demonstrations of these failures.
Conclusion: For scalar regression, balanced initialization satisfies the assumptions and yields convergence with constant probability under random initialization.The construction randomly chooses the end-to-end matrix and then partitions it in a balanced way across layers.
Open questions: The customary layer-wise independent initialization problem remains open, while balanced initialization is presented as a way to circumvent a depth-related negative result.The paper suggests studying balanced-initialization variants for convolutional layers as future work.
Future directions: The trajectory-based landscape properties identified here may support future analyses of gradient descent on non-convex objectives, including deep nonlinear-network training losses.This is stated as an expectation for further study, not as an established result.

A ℓ2 LOSS OVER WHITENED DATA

For a linear predictor, the training objective is expressed as squared Frobenius error between predictions and targets. Whitening the data simplifies the covariance term because the input covariance becomes the identity.

Loss expansion: The loss expansion contains prediction covariance, prediction-target correlation, and target covariance terms.The trace form makes these three components explicit.
Whitened data: Whitening sets Λxx equal to the identity matrix, simplifying the loss expression used for the analysis.The input covariance is the term affected by whitening.
Whitened data: The remaining target-covariance term, 1/2 Tr(Λyy), does not depend on W and therefore does not affect optimization over the predictor.This permits the paper to work with the resulting simplified objective.

B APPROXIMATE BALANCEDNESS AND DEFICIENCY MARGIN UNDER CUSTOMARY INITIALIZATION

Under customary Gaussian initialization, approximate balancedness becomes more likely at smaller variance, while scalar regression can satisfy a positive deficiency margin with probability near 0.5 under suitable variance conditions.

Initialization assumptions: The main convergence theorem relies on approximately balanced initial weights and a positive deficiency margin of the initial end-to-end matrix.These are the two initialization assumptions studied under independent Gaussian perturbations.
Approximate balancedness: Smaller initialization standard deviation makes approximate balancedness more likely.This qualitative conclusion accompanies the Gaussian probability bound.
Approximate balancedness: The probability of δ-balanced initialization is at least max{0, 1 − 10δ−2Ns4d3max}, where dmax := max{d0, . . . , dN}.The bound follows for independent zero-mean Gaussian entries with standard deviation s.
Deficiency margin: In scalar regression, sufficiently small initialization variance yields a deficiency margin with probability close to 0.5.Claim 3 considers dN = 1, d0 ≥ 20, and Gaussian layer-wise independent initialization.

C CONVERGENCE FAILURES

The paper shows that each initialization condition is necessary: violating approximate balancedness or deficiency margin can make gradient descent fail for every learning rate in specified network settings.

Necessity of initialization conditions: Violating either approximate balancedness or deficiency margin can lead to convergence failure.The appendix demonstrates separate failure cases for the two initialization assumptions supporting the main convergence theorem.
Failure without balancedness: Without approximate balancedness, some even-depth equal-width networks fail to converge for every learning rate despite having a positive deficiency margin.The objective remains above a positive constant.
Failure without deficiency margin: The failure result without deficiency margin is presented as somewhat stronger than the corresponding balancedness result and adapts Bartlett et al. (2018).The construction uses 0-balanced, non-stationary initializations.
Failure without deficiency margin: Without deficiency margin, some even-depth equal-width networks fail for every learning rate despite being non-stationary and perfectly balanced.Claim 5 rules out trivial zero stationary initializations, and the objective never drops below a positive constant.

D.3 PROOF OF THEOREM 2

The proof combines a probabilistic initialization argument with the convergence theorem, then reapplies that theorem after the end-to-end matrix develops a larger deficiency margin to capture faster later progress.

Proof strategy: Theorem 2 follows by combining a lemma showing likely sufficient deficiency margin at initialization with Theorem 1’s convergence guarantee.The proof targets a constant-probability convergence result under balanced initialization.
Rate improvement: The proof reapplies Theorem 1 after the deficiency margin grows from O(∥Φ∥2/d0) to a constant, improving the guaranteed convergence-rate bound.The later application captures acceleration as iterates escape the saddle near the all-zero initialization.
Probabilistic initialization: The initial end-to-end matrix is analyzed as a rotation-invariant Gaussian vector whose norm is controlled using a χ2 concentration bound.Lemma 8 supplies the deficiency-margin probability, while Lemma 9 controls norm spread.
Applying the convergence theorem: A positive deficiency margin at initialization implies a bounded initial loss, allowing Theorem 1 to establish convergence on the successful initialization event.The proof verifies the theorem’s conditions and then tracks the resulting iterate properties.
Probability guarantee: The probability of satisfying the initialization conditions approaches 1/2 in the relevant large-dimension and parameter limits.For example, probability greater than 0.25 is obtained with d0 ≥ 100 and a ≥ 100.

D.5 PROOF OF CLAIM 3

Claim 3 establishes a constant-probability deficiency-margin guarantee for the end-to-end matrix under independent Gaussian initialization, using rotation invariance, norm control, and hyperspherical-cap bounds.

Norm control: The end-to-end norm is bounded with high probability using polynomial variance estimates, Markov’s inequality, and a union bound.The resulting bounds control f(W1, . . . , WN) between dimension- and depth-dependent multiples of the initialization scale.
Rotation invariance: Gaussian weight initialization makes the end-to-end matrix distribution rotation-invariant.The proof first establishes invariance for the initial matrix and propagates it through the independent product structure.
Geometric probability: Hyperspherical-cap geometry converts rotation invariance into a deficiency-margin probability for vectors on a sphere.Lemma 15 supplies the key lower bound for a uniformly sampled vector, while Lemma 16 extends it to rotation-invariant distributions with densities.
Claim 3: With a≥10^5, the proof obtains at least 0.49 probability that the Gaussian end-to-end matrix has deficiency margin proportional to ∥Φ∥2/(ad^3).The bound combines the norm event with the geometric margin estimate and the chosen constants.

D.6 PROOF OF CLAIM 4

Claim 4 constructs initializations for which gradient descent fails to converge by forcing alternating-sign weights and exponentially growing loss, including scalar and equal-width matrix cases.

Scalar construction: A scalar construction initializes factors with product c<1 while preserving a large imbalance parameterized by A and η.The initialization is chosen so W1:N(0)=c, with different factor scales in the first and second halves of the network.
Trajectory dynamics: The induction maintains a common alternating sign across all layers and bounds every factor between B(t) and C(t).The recurrence sets B(t+1)=9C(t) and C(t+1)=ηC(t)^(2N−1), preserving the required separation condition.
Scalar construction: The scalar loss remains equal to 1 for every t≥1 under this construction.The stated loss behavior follows from the alternating-sign trajectory established by Lemma 17.
Matrix extension: The same divergence mechanism extends to equal-width matrix networks through diagonal initialization, leaving all but one diagonal coordinate constant.The active diagonal coordinate evolves exactly as in the scalar construction.
Consequence: The proof remarks that the loss grows at least exponentially in t, accompanied by exploding gradients and weights.This is presented as the practical failure mode when initialization is not chosen with care.

E IMPLEMENTATION DETAILS

The implementation details describe preprocessing and optimization calibration for the whitened numeric regression experiment conducted in PyTorch.

Experimental setup: The experiments use PyTorch and apply PCA whitening to the UCI numeric regression dataset.The preprocessing enforces zero mean and identity covariance.
Experimental setup: Labels are rescaled so the uncentered cross-covariance matrix has unit Frobenius norm.The rescaling calibrates the learning rate and initialization standard deviation without otherwise affecting optimization.
Optimization target: The experiment computes the global optimum c using the formula derived in Appendix A.The training objective is then evaluated using the calibrated, whitened data and labels.