Source-linked AI summary
Provable Benefit of Orthogonal Initialization in Optimizing Deep Linear Networks
Wei Hu, Lechao Xiao, Jeffrey Pennington
TL;DR
The paper addresses the limited proof about how initialization affects gradient-descent convergence. It analyzes deep linear networks and rigorously compares orthogonal with iid Gaussian initialization. Orthogonal initialization permits efficient convergence with width independent of depth, while Gaussian initialization requires width scaling with depth.
Problem
Although initialization is an impactful choice, relatively little has been proved about its effect on gradient-descent convergence rates.
Source: §1 · p. 1Method
The paper analyzes gradient-descent convergence in deep linear networks under orthogonal and iid Gaussian weight initializations.
Source: §1 · p. 1Results
Orthogonal initialization permits efficient convergence with width independent of depth, whereas Gaussian initialization requires width that scales linearly with depth.
Source: §1 · p. 1, §7 · p. 10Takeaways & Limitations
The analysis establishes a provable orthogonal-initialization benefit during training, beyond properties measured only at initialization.
Source: §1 · p. 2
Abstract
from arXiv · showhide
The selection of initial parameter values for gradient-based optimization of deep neural networks is one of the most impactful hyperparameter choices in deep learning systems, affecting both convergence times and model performance. Yet despite significant empirical and theoretical analysis, relatively little has been proved about the concrete effects of different initialization schemes. In this work, we analyze the effect of initialization in deep linear networks, and provide for the first time a rigorous proof that drawing the initial weights from the orthogonal group speeds up convergence relative to the standard Gaussian initialization with iid weights. We show that for deep networks, the width needed for efficient convergence to a global minimum with orthogonal initializations is independent of the depth, whereas the width needed for efficient convergence with Gaussian initializations scales linearly in the depth. Our results demonstrate how the benefits of a good initialization can persist throughout learning, suggesting an explanation for the recent empirical successes found by initializing very deep non-linear networks according to the principle of dynamical isometry.
1 INTRODUCTION
The introduction frames initialization as an impactful but poorly understood choice for gradient-descent convergence. It presents a rigorous comparison in deep linear networks: orthogonal initialization needs width independent of depth for efficient convergence, unlike Gaussian initialization.
1 INTRODUCTION
- Initialization is an impactful hyperparameter, but relatively little has been proved about how it affects gradient-descent convergence rates.The introduction situates this gap amid the engineering effort and many hyperparameters involved in designing high-performing models.Source: §1 · p. 1
- Orthogonal initialization speeds convergence relative to iid Gaussian initialization; its efficient-convergence width is independent of depth, while Gaussian width scales linearly with depth.The paper presents this as the first rigorous proof of the comparison.Source: §1 · p. 1
- The paper studies initialization effects on gradient-descent convergence in deep linear networks.It previews a positive orthogonal-initialization result, a Gaussian slow-convergence result when width is too small relative to depth, and supporting experiments.Source: §1 · pp. 1–2
- Prior work found orthogonal weights can speed convergence in linear-regime networks, while this analysis studies their benefit throughout training rather than only at initialization.The cited prior work includes deep linear and non-linear networks (Saxe et al., 2014; Advani & Saxe, 2017; Pennington et al., 2018; Xiao et al., 2018; Gilboa et al., 2019; Chen et al., 2018; Pennington et al., 2017; Tarnowski et al., 2019; Ling & Qiu, 2019).Source: §1 · pp. 1–2
2 RELATED WORK
Related work studies deep linear optimization landscapes, gradient-descent trajectories, orthogonal initialization, and dynamical isometry. The paper positions its contribution as establishing convergence benefits during training and contrasting orthogonal and Gaussian initializations.
2 RELATED WORK
- Deep linear networks have non-convex landscapes; even when all local minima are global under assumptions, that fact alone does not guarantee global convergence or a concrete rate.Landscape work includes Kawaguchi (2016), Hardt & Ma (2016), Lu & Kawaguchi (2017), Yun et al. (2017), Zhou & Liang (2018), and Laurent & von Brecht (2018).Source: §2 · p. 2
- For Gaussian initialization, the paper says width–depth dependence is necessary for efficient convergence, whereas orthogonal initialization permits width independent of depth.Du & Hu (2019) showed efficient convergence for Gaussian initialization when width exceeds depth; the paper also says its Gaussian negative result generalizes Shamir (2018).Source: §2 · p. 2
- Prior work links dynamical isometry—an input-output Jacobian spectrum concentrated around 1 at initialization—to improved convergence times in non-linear networks.The paper says conditions for dynamical isometry in the infinite-width limit basically require an approximately linear input-output map and orthogonal weight matrices (Pennington et al., 2017; 2018).Source: §2 · p. 2
- In recurrent networks, orthogonality can improve conditioning and support learning over long horizons, but this paper does not study that setting.The authors suggest an extension of their analysis might help determine when orthogonality is beneficial for recurrent networks.Source: §2 · p. 2
3 PRELIMINARIES
The preliminaries set notation and define the deep linear-network training problem. They specify the data, layered linear map, squared-loss objective, and randomly initialized gradient descent.
3.1 NOTATION
- Notation defines [n], identity matrices, Gaussian and chi-squared distributions, matrix and vector norms, eigenvalues, singular values, and column-first vectorization.It also defines the Kronecker product as a block matrix whose blocks are entries of the first matrix multiplied by the second matrix.Source: §3.1 · p. 3
- The text uses O(·), Ω(·), and Θ(·) to hide universal constant factors, and C for a sufficiently large universal constant that may vary..Source: §3.1 · p. 3
3.2 PROBLEM SETUP
- The setup uses n training examples and an L-layer linear network with weights W1 through WL, mapping x to αWLWL−1···W1x.Layer dimensions satisfy d0 = dx and dL = dy; α is a normalization constant specified according to initialization scheme.Source: §3.2 · p. 3
- Training minimizes the ℓ2 loss over the data using gradient descent from randomly sampled initial weight matrices.The update uses learning rate η; Wj:i denotes the product WjWj−1···Wi, with Wi−1:i equal to the identity.Source: §3.2 · p. 3
4 EFFICIENT CONVERGENCE USING ORTHOGONAL INITIALIZATION
Orthogonal initialization enables efficient convergence to a global minimum without requiring width to grow with depth. The proof relates this guarantee to maintaining near-isometry during training and controlling a time-varying matrix.
4 EFFICIENT CONVERGENCE USING ORTHOGONAL INITIALIZATION
- Orthogonal initialization enables efficient convergence to a global minimum with width independent of depth, while Gaussian initialization requires width scaling nearly linearly with depth [Du & Hu (2019)].The linear dependence on depth is necessary for efficient convergence with Gaussian initialization, making the earlier sufficient-width condition nearly tight.Source: §4 · pp. 3–4
- With the learning rate set optimally, the objective decreases by a ratio of 1 − Θ(κ^-1) per iteration, matching the convergence rate for one-layer linear regression.The stated learning rate is η = Θ( dy L∥X∥2 ).Source: §4 · p. 4
4.1 PROOF OF THEOREM 4.1
- The proof controls a time-varying positive semidefinite matrix’s eigenvalues and keeps relevant weight products close to isometry during training.It also requires the higher-order term in the output evolution to remain small.Source: §4.1 · pp. 4–5
5 EXPONENTIAL CURSE OF GAUSSIAN INITIALIZATION
For Gaussian initialization, efficient convergence in deep networks requires width nearly linear in depth; below that scale, gradient descent can take exponentially long. The proof connects this slowdown to small initial layer-product norms and the time needed to leave a neighborhood of initialization.
5 EXPONENTIAL CURSE OF GAUSSIAN INITIALIZATION
- Gaussian initialization requires width nearly linear in depth for efficient convergence; otherwise gradient descent can take exponentially long.The section’s theorem assumes sufficiently large depth and bounds layer widths by O(L^(1−γ)); the result holds with probability at least 0.9 under its stated learning-rate condition.Source: §5 · p. 6
- The nearly linear width requirement is necessary for Gaussian initialization, complementing Du & Hu (2019), who proved efficient convergence when width exceeds linear in depth.The section also states that its theorem generalizes Shamir (2018), which treated the special case d0 = · · · = dL = 1.Source: §5 · p. 6
5.1 PROOF OF THEOREM 5.1
- With high probability, sufficiently long products of scaled Gaussian weight matrices have exponentially small norm, supplying the key initialization property behind the lower bound.The proof establishes this for layer intervals of length at least L/10, then uses an epsilon-net argument to bound the operator norm.Source: §5.1 · p. 7
- Small perturbations preserve the small-product property, keeping the objective within a bounded interval near initialization.The proof uses this neighborhood control to argue that optimization must leave the initial neighborhood before the objective can decrease substantially.Source: §5.1 · p. 8
- Escaping that neighborhood takes many gradient steps because each layer’s movement per step is bounded while the required displacement is larger.The proof compares the per-iteration movement bound with the distance needed for some weight matrix to leave the neighborhood.Source: §5.1 · p. 8
6 EXPERIMENTS
Experiments on synthetic data vary network width and depth to compare Gaussian and orthogonal initialization. The results show distinct width thresholds for trainability and faster training with orthogonal initialization at small widths.
6 EXPERIMENTS
- Gaussian initialization’s trainability transition follows a contour with a linear relation between width and depth, while orthogonal initialization’s threshold is approximately depth-independent.The experiments train networks with widths from 10 to 1000 and depths from 1 to 700; Figure 1 displays relative loss at two training steps.Source: §6 · p. 9
- The observed transitions are reported to verify the theory developed in Sections 4 and 5.The experiments use a fixed synthetic dataset, with target labels formed from a linear map applied to the inputs.Source: §6 · p. 9
- Orthogonal initialization enables fast training at small width independent of depth, whereas Gaussian initialization’s required width depends on depth.Figure 2 compares relative loss over training time across depth-width configurations and initialization schemes.Source: §6 · p. 9, Figure 2 · p. 10
7 CONCLUSION
The conclusion contrasts Gaussian and orthogonal initialization for gradient descent in deep linear networks. Gaussian convergence time grows exponentially with depth unless width is at least as large as depth, while orthogonal initialization needs width independent of depth for efficient convergence.
7 CONCLUSION
- For deep linear networks, Gaussian initialization has exponentially growing convergence time unless width is at least as large as depth.The conclusion frames this as a result about gradient-descent convergence time.Source: §7 · p. 10
- With orthogonal initialization, the width needed to guarantee efficient convergence is independent of depth.Source: §7 · p. 10
- The paper presents these findings as the first concrete proof that orthogonal initialization is superior to Gaussian initialization in convergence time.Source: §7 · p. 10
A.1 PROOF OF LEMMA 4.2
The proof bounds the network’s initial output by relating it to a random-subspace projection. Concentration bounds and a union bound extend the result across the finite input set.
A.1 PROOF OF LEMMA 4.2
- The proof reduces bounding the initial network output to bounding a vector’s projection onto a random low-dimensional subspace.The text identifies the projection as signed and the subspace dimension as dy.Source: §A.1 · p. 13
- Standard chi-squared tail bounds are used to control the random quantities involved in the projection argument.Source: §A.1 · p. 13
- A union bound gives probability at least 1 − δ that the inequality holds for every input in the finite set.The passage specifies the set as {x1, . . . , xr}.Source: §A.1 · p. 13
A.2 PROOF OF CLAIM 4.3
The proof bounds the objective and its gradient along the trajectory, then establishes C(t + 1).
A.2 PROOF OF CLAIM 4.3
- The argument bounds the gradient norm for every layer throughout 0 ≤ s ≤ t.It uses the objective bound ℓ(s) ≤ (1−ηγ)^sB.Source: §A.2 · p. 13
- These bounds establish C(t + 1).Source: §A.2 · p. 14
A.3 PROOF OF CLAIM 4.4
The proofs establish B(t) by bounding the change in layer products, then use B(t) to bound the dynamics and establish A(t + 1).
A.3 PROOF OF CLAIM 4.4
- Expanding the layer-product difference into terms involving layer changes establishes B(t) under the stated width condition.The expansion uses the bound on each layer change and m > C(LR)^2.Source: §A.3 · p. 14
A.4 PROOF OF CLAIM 4.5
- The lower-bound argument uses the dimension relation m ≥ d_x ≥ r.Source: §A.4 · p. 14
- The proof establishes A(t + 1) after bounding the dynamics using B(t).The argument targets upper and lower eigenvalue bounds for P(t) and a small high-order term E(t).Source: §A.4 · pp. 14–15
B.1 PROOF OF LEMMA 5.2
The appendix gives probability and product bounds used to analyze deep-network behavior, including an exponentially small initial output bound.
B.1 PROOF OF LEMMA 5.2
- With probability at least 1 − δ, all initial layer subproducts simultaneously satisfy the stated norm bound.Source: §B.1 · p. 16
B.2 PROOF OF LEMMA 5.4
- For sufficiently separated layers, the product involving a layer change is bounded by e^-1.6c1L^γ · O(L^3).The proof uses exponential spectral-norm decay on one of the two surrounding subproducts.Source: §B.2 · p. 16
B.3 PROOF OF LEMMA 5.5
- The initial network output has Frobenius norm at most e^-Ω(L^γ), leaving the objective close to 1/2 ∥Y∥²_F for large L.Source: §B.3 · p. 16