A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks

Introduction

Deep learning builds upon the mysterious ability of gradient-based optimization methods to solve related non-convex problems. Immense efforts are underway to mathematically analyze this phenomenon. The prominent landscape approach focuses on special properties of critical points (i.e. points where the gradient of the objective function vanishes) that will imply convergence to global optimum. Several papers (e.g. Ge et al. (2015); Lee et al. (2016)) have shown that (given certain smoothness properties) it suffices for critical points to meet the following two conditions: (i) no poor local minima — every local minimum is close in its objective value to a global minimum; and (ii) strict saddle property — every critical point that is not a local minimum has at least one negative eigenvalue to its Hessian. While condition (i) does not always hold (cf. Safran and Shamir (2018)), it has been established for various simple settings (e.g. Soudry and Carmon (2016); Kawaguchi (2016)). Condition (ii) on the other hand seems less plausible, and is in fact provably false for models with three or more layers (cf. Kawaguchi (2016)), i.e. for deep networks. It has only been established for problems involving shallow (two layer) models, e.g. matrix factorization (Ge et al. (2016); Du et al. (2018a)). The landscape approach as currently construed thus suffers from inherent limitations in proving convergence to global minimum for deep networks.

A potential path to circumvent this obstacle lies in realizing that landscape properties matter only in the vicinity of trajectories that can be taken by the optimizer, which may be a negligible portion of the overall parameter space. Several papers (e.g. Saxe et al. (2014); Arora et al. (2018)) have taken this trajectory-based approach, primarily in the context of linear neural networks — fully-connected neural networks with linear activation. Linear networks are trivial from a representational perspective, but not so in terms of optimization — they lead to non-convex training problems with multiple minima and saddle points. Through a mix of theory and experiments, Arora et al. (2018) argued that such non-convexities may in fact be beneficial for gradient descent, in the sense that sometimes, adding (redundant) linear layers to a classic linear prediction model can accelerate the optimization. This phenomenon challenges the holistic landscape view, by which convex problems are always preferable to non-convex ones.

Gradient Descent for Deep Linear Neural Networks

We denote by $\left\|{\mathbf{v}}\right\|$ the Euclidean norm of a vector ${\mathbf{v}}$, and by $\left\|A\right\|_{F}$ the Frobenius norm of a matrix $A$.

Note that the notation $L^{N}(\cdot)$ is consistent with that of Equation (2), as a network with depth $N=1$ precisely reduces to a (directly parameterized) linear model.

We focus on studying the process of training a deep linear neural network by gradient descent, i.e. of tackling the optimization problem in Equation (3) by iteratively applying the following updates:

where $\eta>0$ is a configurable learning rate. In the case of depth $N=1$, the training problem in Equation (3) is smooth and strongly convex, thus it is known (cf. Boyd and Vandenberghe (2004)) that with proper choice of $\eta$, gradient descent converges to global minimum at a linear rate. In contrast, for any depth greater than $1$, Equation (3) comprises a fundamentally non-convex program, and the convergence properties of gradient descent are highly non-trivial. Apart from the case $N=2$ (shallow network), one cannot hope to prove convergence via landscape arguments, as the strict saddle property is provably violated (see Section 1). We will see in Section 3 that a direct analysis of the trajectories taken by gradient descent can succeed in this arena, providing a guarantee for linear rate convergence to global minimum.

Convergence Analysis

In this section we establish convergence of gradient descent for deep linear neural networks (Equations (4) and (3)) by directly analyzing the trajectories taken by the algorithm. We begin in Subsection 3.1 with a presentation of two concepts central to our analysis: approximate balancedness and deficiency margin. These facilitate our main convergence theorem, delivered in Subsection 3.2. We conclude in Subsection 3.3 by deriving a convergence guarantee that holds with constant probability over a random initialization.

In our context, the notion of approximate balancedness is formally defined as follows:

Note that in the case of -balancedness, i.e. $W_{j+1}^{\top}W_{j+1}=W_{j}W_{j}^{\top}$, $\forall{j}\in\{1,\ldots,N-1\}$, all matrices $W_{j}$ share the same set of non-zero singular values. Moreover, as shown in the proof of Theorem 1 in Arora et al. (2018), this set is obtained by taking the $N$-th root of each non-zero singular value in the end-to-end matrix $W_{1:N}$. We will establish approximate versions of these facts for $\delta$-balancedness with $\delta>0$, and admit their usage by showing that if the weights of a linear neural network are initialized to be approximately balanced, they will remain that way throughout the iterations of gradient descent. The condition of approximate balancedness at initialization is trivially met in the special case of linear residual networks ($d_{0}=\cdots=d_{N}=d$ and $W_{1}(0)=\cdots=W_{N}(0)=I_{d}$). Moreover, as Claim 2 in Appendix B shows, for a given $\delta>0$, the customary initialization via random Gaussian distribution with mean zero leads to approximate balancedness with high probability if the standard deviation is sufficiently small.

The second concept we introduce — deficiency margin — refers to how far a ball around the target is from containing rank-deficient (i.e. low rank) matrices.

The term “deficiency margin” alludes to the fact that if Equation (6) holds, every matrix $W^{\prime}$ whose distance from $\Phi$ is no greater than that of $W$, has singular values $c$-bounded away from zero:

Suppose $W$ has deficiency margin $c$ with respect to $\Phi$. Then, any matrix $W^{\prime}$ (of same size as $\Phi$ and $W$) for which $\left\|W^{\prime}-\Phi\right\|_{F}\leq\left\|W-\Phi\right\|_{F}$ satisfies $\sigma_{min}(W^{\prime})\geq{c}$.

Our proof relies on the inequality $\sigma_{min}(A+B)\geq\sigma_{min}(A)-\sigma_{max}(B)$ — see Appendix D.1. ∎

We will show that if the weights $W_{1},\ldots,W_{N}$ are initialized such that (they are approximately balanced and) the end-to-end matrix $W_{1:N}$ has deficiency margin $c>0$ with respect to the target $\Phi$, convergence of gradient descent to global minimum is guaranteed. In fact, a deficiency margin implies that all critical points in the respective sublevel set (set of points with smaller loss value) are global minima. This however is far from sufficient for proving convergence, as sublevel sets are unbounded, and the loss landscape over them is non-convex and non-smooth. Indeed, we show in Appendix C that deficiency margin alone is not enough to ensure convergence — without approximate balancedness, the lack of smoothness can cause divergence. Moreover, the convergence will outpace a particular rate that gets faster when $c$ grows larger. This suggests that from a theoretical perspective, it is advantageous to initialize a linear neural network such that the end-to-end matrix has a large deficiency margin with respect to the target. Claim 3 in Appendix B provides information on how likely deficiency margins are in the case of a single output model (scalar regression) subject to customary zero-centered Gaussian initialization. It shows in particular that if the standard deviation of the initialization is sufficiently small, the probability of a deficiency margin being met is close to $0.5$; on the other hand, for this deficiency margin to have considerable magnitude, a non-negligible standard deviation is required.

Taking into account the need for both approximate balancedness and deficiency margin at initialization, we observe a delicate trade-off under the common setting of Gaussian perturbations around zero: if the standard deviation is small, it is likely that weights be highly balanced and a deficiency margin be met; however overly small standard deviation will render high magnitude for the deficiency margin improbable, and therefore fast convergence is less likely to happen; on the opposite end, large standard deviation jeopardizes both balancedness and deficiency margin, putting the entire convergence at risk. This trade-off is reminiscent of empirical phenomena in deep learning, by which small initialization can bring forth efficient convergence, while if exceedingly small, rate of convergence may plummet (“vanishing gradient problem”), and if made large, divergence becomes inevitable (“exploding gradient problem”). The common resolution of residual connections (He et al., 2016) is analogous in our context to linear residual networks, which ensure perfect balancedness, and allow large deficiency margin if the target is not too far from identity.

2 Main Theorem

Using approximate balancedness (Definition 1) and deficiency margin (Definition 2), we present our main theorem — a guarantee for linear convergence to global minimum:

Assume that gradient descent is initialized such that the end-to-end matrix $W_{1:N}(0)$ has deficiency margin $c>0$ with respect to the target $\Phi$, and the weights $W_{1}(0),\ldots,W_{N}(0)$ are $\delta$-balanced with \delta=c^{2}\big{/}\big{(}256\cdot{N}^{3}\cdot\left\|\Phi\right\|_{F}^{2(N-1)/N}\big{)}. Suppose also that the learning rate $\eta$ meets:

The assumptions made in Theorem 1 — approximate balancedness and deficiency margin at initialization — are both necessary, in the sense that violating any one of them may lead to convergence failure. We demonstrate this in Appendix C. In the special case of linear residual networks (uniform dimensions and identity initialization), a sufficient condition for the assumptions to be met is that the target matrix have (Frobenius) distance less than $0.5$ from identity. This strengthens one of the central results in Bartlett et al. (2018) (see Section 5). For a setting of random near-zero initialization, we present in Subsection 3.3 a scheme that, when the output dimension is $1$ (scalar regression), ensures assumptions are satisfied (and therefore gradient descent efficiently converges to global minimum) with constant probability. It is an open problem to fully analyze gradient descent under the common initialization scheme of zero-centered Gaussian perturbations applied to each layer independently. We treat this scenario in Appendix B, providing quantitative results concerning the likelihood of each assumption (approximate balancedness or deficiency margin) being met individually. However the question of how likely it is that both assumptions be met simultaneously, and how that depends on the standard deviation of the Gaussian, is left for future work.

An additional point to make is that Theorem 1 poses a structural limitation on the linear neural network. Namely, it requires the dimension of each hidden layer ($d_{i},~{}i=1,\ldots,N-1$) to be greater than or equal to the minimum between those of the input ($d_{0}$) and output ($d_{N}$). Indeed, in order for the initial end-to-end matrix $W_{1:N}(0)$ to have deficiency margin $c>0$, it must (by Claim 1) have full rank, and this is only possible if there is no intermediate dimension $d_{i}$ smaller than $\min\{d_{0},d_{N}\}$. We make no other assumptions on network architecture (depth, input/output/hidden dimensions).

2.2 Proof

The cornerstone upon which Theorem 1 rests is the following lemma, showing non-trivial descent whenever $\sigma_{min}(W_{1:N})$ is bounded away from zero:

Under the conditions of Theorem 1, we have that for every $t=0,1,2,\ldots$ : Note that the term $\frac{dL^{1}}{dW}(W_{1:N}(t))$ below stands for the gradient of $L^{1}(\cdot)$ — a convex loss over (directly parameterized) linear models (Equation (2)) — at the point $W_{1:N}(t)$ — the end-to-end matrix of the network at iteration $t$. It is therefore (see Equation (5)) non-zero anywhere but at a global minimum.

We prove the lemma here for the idealized setting of perfect initial balancedness ($\delta=0$):

and infinitesimally small learning rate ($\eta\to 0^{+}$) — gradient flow:

where $\tau$ is a continuous time index, and dot symbol (in $\dot{W}_{j}(\tau)$) signifies derivative with respect to time. The complete proof, for the realistic case of approximate balancedness and discrete updates ($\delta,\eta>0$), is similar but much more involved, and appears in Appendix D.2.

We will see that a stronger version of Equation (10) holds, namely, one without the $1/2$ factor (which only appears due to discretization).

By (Theorem $1$ and Claim $1$ in) Arora et al. (2018), the weights $W_{1}(\tau),\ldots,W_{N}(\tau)$ remain balanced throughout the entire optimization, and that implies the end-to-end matrix $W_{1:N}(\tau)$ moves according to the following differential equation:

where $vec(A)$, for an arbitrary matrix $A$, stands for vectorization in column-first order, and $P_{W_{1:N}(\tau)}$ is a positive semidefinite matrix whose eigenvalues are all greater than or equal to $\sigma_{min}(W_{1:N}(\tau))^{2(N-1)/N}$. Taking the derivative of $L^{1}(W_{1:N}(\tau))$ with respect to time, we obtain the sought-after Equation (10) (with no $1/2$ factor):

The first transition here (equality) is an application of the chain rule; the second (equality) plugs in Equation (11); the third (inequality) results from the fact that the eigenvalues of the symmetric matrix $P_{W_{1:N}(\tau)}$ are no smaller than $\sigma_{min}(W_{1:N}(\tau))^{2(N-1)/N}$ (recall that $\left\|\cdot\right\|$ stands for Euclidean norm); and the last (equality) is trivial — $\left\|A\right\|_{F}=\left\|vec(A)\right\|$ for any matrix $A$. ∎

With Lemma 1 established, the proof of Theorem 1 readily follows:

Since the coefficients $1-\eta\cdot\sigma_{min}(W_{1:N}(t))^{\frac{2(N-1)}{N}}$ are necessarily non-negative (otherwise would contradict non-negativity of $L^{1}(\cdot)$), we may unroll the inequalities, obtaining:

Now, this in particular means that for every $t^{\prime}=0,1,2,\ldots$ :

Deficiency margin $c$ of $W_{1:N}(0)$ along with Claim 1 thus imply \sigma_{min}\big{(}W_{1:N}(t^{\prime})\big{)}\geq{c}, which when inserted back into Equation (12) yields, for every $t=1,2,3,\ldots$ :

$\eta\cdot{c}^{\frac{2(N-1)}{N}}$ is obviously non-negative, and it is also no greater than $1$ (otherwise would contradict non-negativity of $L^{1}(\cdot)$). We may therefore incorporate the inequality 1-\eta\cdot{c}^{2(N-1)/N}\leq\exp\big{(}-\eta\cdot{c}^{2(N-1)/N}\big{)} into Equation (13):

from which it follows that $L^{1}(W_{1:N}(t))\leq\epsilon$ if:

3 Balanced Initialization

We define the following procedure, balanced initialization, which assigns weights randomly while ensuring perfect balancedness:

Set $W_{N}\simeq{U}\Sigma^{1/N},W_{N-1}\simeq\Sigma^{1/N},\ldots,W_{2}\simeq\Sigma^{1/N},W_{1}\simeq\Sigma^{1/N}V^{\top}$, where the symbol “$\simeq$” stands for equality up to zero-valued padding. These assignments can be accomplished since $\min\{d_{1},\ldots,d_{N-1}\}\geq\min\{d_{0},d_{N}\}$. By design $W_{1:N}=A$ and $W_{j+1}^{\top}W_{j+1}=W_{j}W_{j}^{\top}$, $\forall{j}\in\{1,\ldots,N{-}1\}$ — these properties are actually all we need in Theorem 2, and step (iii) in Procedure 1 can be replaced by any assignment that meets them.

The concept of balanced initialization, together with Theorem 1, leads to a guarantee for linear convergence (applicable to output dimension $1$ — scalar regression) that holds with constant probability over the randomness in initialization:

For any constant $0<p<1/2$, there are constants $d_{0}^{\prime},a>0$ As shown in the proof of the theorem (Appendix D.3), $d_{0}^{\prime},a>0$ can take on any pair of values for which: (i) $d_{0}^{\prime}\geq 20$; and (ii) \big{(}1-2\exp(-d_{0}^{\prime}/16)\big{)}\big{(}3-4F(2/\sqrt{a/2})\big{)}\geq 2p, where $F(\cdot)$ stands for the cumulative distribution function of the standard normal distribution. For example, if $p=0.25$, it suffices to take any $d_{0}^{\prime}\geq 100,a\geq 100$. We note that condition (i) here ($d_{0}^{\prime}\geq 20$) serves solely for simplification of expressions in the theorem. such that the following holds. Assume $d_{N}=1,d_{0}\geq d_{0}^{\prime}$, and that the weights $W_{1}(0),\ldots,W_{N}(0)$ are subject to balanced initialization (Procedure 1) such that the entries in $W_{1:N}(0)$ are independent zero-centered Gaussian perturbations with standard deviation $s\leq\|\Phi\|_{2}/\sqrt{ad_{0}^{2}}$. Suppose also that we run gradient descent with learning rate \eta\leq(s^{2}d_{0})^{4-2/N}\big{/}\big{(}10^{5}N^{3}\|\Phi\|_{2}^{10-6/N}\big{)}. Then, with probability at least $p$ over the random initialization, we have that for every $\epsilon>0$ and:

Experiments

Balanced initialization (Procedure 1) possesses theoretical advantages compared with the customary layer-wise independent scheme — it allowed us to derive a convergence guarantee that holds with constant probability over the randomness of initialization (Theorem 2). In this section we present empirical evidence suggesting that initializing with balancedness may be beneficial in practice as well. For conciseness, some of the details behind our implementation are deferred to Appendix E.

In addition to a three layer network, we also evaluated a deeper, eight layer model (with hidden widths identical to the former — $N=8$, $d_{1}=\cdots=d_{7}=32$). In particular, using the same experimental protocol as above, we measured convergence time under different choices of standard deviation for the initialization. Figure 1(a) displays the result of this test alongside that of the three layer model. As the figure shows, transitioning from three layers to eight aggravated the instability with respect to initialization — there is now a narrow band of standard deviations that lead to convergence in reasonable time, and outside of this band convergence is extremely slow, to the point where it does not take place within the duration we allowed ($10^{6}$ iterations). From the perspective of our analysis, a possible explanation for the aggravation is as follows: under layer-wise independent initialization, the magnitude of the end-to-end matrix $W_{1:N}$ depends on the standard deviation in a manner that is exponential in depth, thus for large depths the range of standard deviations that lead to moderately sized $W_{1:N}$ (as required for a deficiency margin) is limited, and within this range, there may not be many standard deviations small enough to ensure approximate balancedness. The procedure of balanced initialization (Procedure 1) circumvents these difficulties — it assigns $W_{1:N}$ directly (no exponential dependence on depth), and distributes its content between the individual weights $W_{1},\ldots,W_{N}$ in a perfectly balanced fashion. Rerunning the experiment of Figure 1(a) with this initialization replacing the customary layer-wise scheme (using same experimental protocol), we obtained the results shown in Figure 1(b) — both the original three layer network, and the deeper eight layer model, converged quickly under virtually all standard deviations tried.

As a final experiment, we evaluated the effect of balanced initialization in a setting that involves non-linear activation, softmax-cross-entropy loss and stochastic optimization (factors not accounted for by our analysis). For this purpose, we turned to the MNIST tutorial built into TensorFlow (Abadi et al., 2016), https://github.com/tensorflow/tensorflow/tree/master/tensorflow/examples/tutorials/mnist which comprises a fully-connected neural network with two hidden layers (width $128$ followed by $32$) and ReLU activation (Nair and Hinton, 2010), trained through stochastic gradient descent (over softmax-cross-entropy loss) with batch size $100$, initialized via customary layer-wise independent Gaussian perturbations centered at zero. While keeping the learning rate at its default value $0.01$, we varied the standard deviation of initialization, and for each value measured the training loss after $10$ epochs. As opposed to the dataset used in our experiments with linear networks, measuring the training loss with MNIST is non-trivial computationally (involves passing through $60K$ examples). Therefore, rather than continuously polling training loss until it reaches a certain threshold, in this experiment we chose to evaluate speed of convergence by measuring the training loss once after a predetermined number of iterations. We then replaced the original (layer-wise independent) initialization with a balanced initialization based on Gaussian perturbations centered at zero (latter was implemented per Procedure 1, disregarding non-linear activation), and repeated the process. The results of this experiment are shown in Figure 1(d). Although our theoretical analysis does not cover non-linear activation, softmax-cross-entropy loss or stochasticity in optimization, its conclusion of balanced initialization leading to improved (faster and more stable) convergence carried over to such setting.

Related Work

Theoretical study of gradient-based optimization in deep learning is a highly active area of research. As discussed in Section 1, a popular approach is to show that the objective landscape admits the properties of no poor local minima and strict saddle, which, by Ge et al. (2015); Lee et al. (2016); Panageas and Piliouras (2017), ensure convergence to global minimum. Many works, both classic (e.g. Baldi and Hornik (1989)) and recent (e.g. Choromanska et al. (2015); Kawaguchi (2016); Hardt and Ma (2016); Soudry and Carmon (2016); Haeffele and Vidal (2017); Nguyen and Hein (2017); Safran and Shamir (2018); Nguyen and Hein (2018); Laurent and Brecht (2018)), have focused on the validity of these properties in different deep learning settings. Nonetheless, to our knowledge, the success of landscape-driven analyses in formally proving convergence to global minimum for a gradient-based algorithm, has thus far been limited to shallow (two layer) models only (e.g. Ge et al. (2016); Du and Lee (2018); Du et al. (2018a)).

An alternative to the landscape approach is a direct analysis of the trajectories taken by the optimizer. Various papers (e.g. Brutzkus and Globerson (2017); Li and Yuan (2017); Zhong et al. (2017); Tian (2017); Brutzkus et al. (2018); Li et al. (2018); Du et al. (2018c; b); Liao et al. (2018)) have recently adopted this strategy, but their analyses only apply to shallow models. In the context of linear neural networks, deep (three or more layer) models have also been treated — cf. Saxe et al. (2014) and Arora et al. (2018), from which we draw certain technical ideas for proving Lemma 1. However these treatments all apply to gradient flow (gradient descent with infinitesimally small learning rate), and thus do not formally address the question of computational efficiency.

Conclusion

For deep linear neural networks, we have rigorously proven convergence of gradient descent to global minima, at a linear rate, provided that the initial weight matrices are approximately balanced and the initial end-to-end matrix has positive deficiency margin. The result applies to networks with arbitrary depth, and any configuration of input/output/hidden dimensions that supports full rank, i.e. in which no hidden layer has dimension smaller than both the input and output.

Our assumptions on initialization — approximate balancedness and deficiency margin — are both necessary, in the sense that violating any one of them may lead to convergence failure, as we demonstrated explicitly. Moreover, for networks with output dimension $1$ (scalar regression), we have shown that a balanced initialization, i.e. a random choice of the end-to-end matrix followed by a balanced partition across all layers, leads assumptions to be met, and thus convergence to take place, with constant probability. Rigorously proving efficient convergence with significant probability under customary layer-wise independent initialization remains an open problem. The recent work of Shamir (2018) suggests that this may not be possible, as at least in some settings, the number of iterations required for convergence is exponential in depth with overwhelming probability. This negative result, a theoretical manifestation of the “vanishing gradient problem”, is circumvented by balanced initialization. Through simple experiments we have shown that the latter can lead to favorable convergence in deep learning practice, as it does in theory. Further investigation of balanced initialization, including development of variants for convolutional layers, is regarded as a promising direction for future research.

The analysis in this paper uncovers special properties of the optimization landscape in the vicinity of gradient descent trajectories. We expect similar ideas to prove useful in further study of gradient descent on non-convex objectives, including training losses of deep non-linear neural networks.

This work is supported by NSF, ONR, Simons Foundation, Schmidt Foundation, Mozilla Research, Amazon Research, DARPA and SRC. Nadav Cohen is a member of the Zuckerman Israeli Postdoctoral Scholars Program, and supported by Schmidt Foundation.

References

References

Appendix

By definition, when data is whitened, $\Lambda_{xx}$ is equal to identity, yielding:

where $c:=-\tfrac{1}{2}\operatorname{Tr}(\Lambda_{yx}\Lambda_{yx}^{\top})+\tfrac{1}{2}\operatorname{Tr}(\Lambda_{yy})$ does not depend on $W$. Hence we arrive at Equation (1).

Appendix B Approximate Balancedness and Deficiency Margin Under Customary Initialization

Two assumptions concerning initialization facilitate our main convergence result (Theorem 1): (i) the initial weights $W_{1}(0),\ldots,W_{N}(0)$ are approximately balanced (see Definition 1); and (ii) the initial end-to-end matrix $W_{1:N}(0)$ has positive deficiency margin with respect to the target $\Phi$ (see Definition 2). The current appendix studies the likelihood of these assumptions being met under customary initialization of random (layer-wise independent) Gaussian perturbations centered at zero.

For approximate balancedness we have the following claim, which shows that it becomes more and more likely the smaller the standard deviation of initialization is:

In terms of deficiency margin, the claim below treats the case of a single output model (scalar regression), and shows that if the standard deviation of initialization is sufficiently small, with probability close to $0.5$, a deficiency margin will be met. However, for this deficiency margin to meet a chosen threshold $c$, the standard deviation need be sufficiently large.

Appendix C Convergence Failures

In this appendix we show that the assumptions on initialization facilitating our main convergence result (Theorem 1) — approximate balancedness and deficiency margin — are both necessary, by demonstrating cases where violating each of them leads to convergence failure. This accords with widely observed empirical phenomena, by which successful optimization in deep learning crucially depends on careful initialization (cf. Sutskever et al. (2013)).

Claim 4 below shows For simplicity of presentation, the claim treats the case of even depth and uniform dimension across all layers. It can easily be extended to account for arbitrary depth and input/output/hidden dimensions. that if one omits from Theorem 1 the assumption of approximate balancedness at initialization, no choice of learning rate can guarantee convergence:

In terms of deficiency margin, we provide (by adapting Theorem 4 in Bartlett et al. (2018)) a different, somewhat stronger result — there exist settings where initialization violates the assumption of deficiency margin, and despite being perfectly balanced, leads to convergence failure, for any choice of learning rate: This statement becomes trivial if one allows initialization at a suboptimal stationary point, e.g. $W_{j}(0)=0,~{}j=1,\ldots,N$. Claim 5 rules out such trivialities by considering only non-stationary initializations.

Appendix D Deferred Proofs

To simplify the presentation we will oftentimes use $W$ as an alternative (shortened) notation for $W_{1:N}$ — the end-to-end matrix of a linear neural network. We will also use $L(\cdot)$ as shorthand for $L^{1}(\cdot)$ — the loss associated with a (directly parameterized) linear model, i.e. $L(W):=\frac{1}{2}\left\|W-\Phi\right\|_{F}^{2}$. Therefore, in the context of gradient descent training a linear neural network, the following expressions all represent the loss at iteration $t$:

where we define $W_{1:0}(t):=I_{d_{0}}$ and $W_{N+1:N}(t):=I_{d_{N}}$ for completeness.

where $a_{i,j}$ is the element in the $i$-th row and $j$-th column of $A$.

Recall that for any matrices $A$ and $B$ of compatible sizes $\sigma_{min}(A+B)\geq\sigma_{min}(A)-\sigma_{max}(B)$, and that the Frobenius norm of a matrix is always lower bounded by its largest singular value (Horn and Johnson (1990)). Using these facts, we have:

D.2 Proof of Lemma 1

To prove Lemma 1, we will in fact prove a stronger result, Lemma 2 below, which states that for each iteration $t$, in addition to (9) being satisfied, certain other properties are also satisfied, namely: (i) the weight matrices $W_{1}(t),\ldots,W_{N}(t)$ are $2\delta$-balanced, and (ii) $W_{1}(t),\ldots,W_{N}(t)$ have bounded spectral norms.

For $1\leq j\leq N-1$, $\|W_{j+1}^{\top}(t)W_{j+1}(t)-W_{j}(t)W_{j}^{\top}(t)\|_{F}\leq 2\delta$.

If $t\geq 1$, then for $1\leq j\leq N-1$,

For $1\leq j\leq N$, $\|W_{j}(t)\|_{\sigma}\leq(4\|\Phi\|_{F})^{1/N}$.

First we observe that Lemma 1 is an immediate consequence of Lemma 2.

Notice that condition $\mathcal{B}(t)$ of Lemma 2 for each $t\geq 1$ immediately establishes the conclusion of Lemma 1 at time step $t-1$. ∎

We next prove some preliminary lemmas which will aid us in the proof of Lemma 2. The first is a matrix inequality that follows from Lidskii’s theorem. For a matrix $A$, let $\operatorname*{Sing}(A)$ denote the rectangular diagonal matrix of the same size, whose diagonal elements are the singular values of $A$ arranged in non-increasing order (starting from the $(1,1)$ position).

For any two matrices $A,B$ of the same size, $\|\operatorname*{Sing}(A)-\operatorname*{Sing}(B)\|_{\sigma}\leq\|A-B\|_{\sigma}$ and $\|\operatorname*{Sing}(A)-\operatorname*{Sing}(B)\|_{F}\leq\|A-B\|_{F}$.

$\|D_{1}-OD_{1}O^{\top}\|_{F}\leq 2\epsilon$.

Since $D_{1}$ and $OD_{2}O^{T}$ are both symmetric positive semi-definite matrices, their singular values are equal to their eigenvalues. Moreover, the singular values of $D_{1}$ are simply its diagonal elements and the singular values of $OD_{2}O^{T}$ are simply the diagonal elements of $D_{2}$. Thus by Lemma 3 we get that $\|D_{1}-D_{2}\|_{F}\leq\|D_{1}-OD_{2}O^{T}\|_{F}\leq\epsilon$. Since the Frobenius norm is unitarily invariant, $\|D_{1}-D_{2}\|_{F}=\|OD_{1}O^{T}-OD_{2}O^{T}\|_{F}$, and by the triangle inequality it follows that

Lemma 5 below states that if $W_{1},\ldots,W_{N}$ are approximately balanced matrices, i.e. $W_{j+1}^{\top}W_{j+1}-W_{j}W_{j}^{\top}$ has small Frobenius norm for $1\leq j\leq N-1$, then we can bound the Frobenius distance between $W_{1:j}^{\top}W_{1:j}$ and $(W_{1}^{\top}W_{1})^{j}$ (as well as between $W_{j:N}W_{j:N}^{\top}$ and $(W_{N}W_{N}^{\top})^{N-j+1}$).

and for $1\leq j\leq N$, $\|W_{j}\|_{\sigma}\leq M$. Then, for $1\leq j\leq N$,

Moreover, if $\sigma_{min}$ denotes the minimum singular value of $W_{1:N}$, $\sigma_{1,min}$ denotes the minimum singular value of $W_{1}$ and $\sigma_{N,min}$ denotes the minimum singular value of $W_{N}$, then

Since the Frobenius norm is invariant to orthogonal transformations, we get that

By Lemma 4, we have that $\|\Sigma_{j+1}^{\top}\Sigma_{j+1}-\Sigma_{j}\Sigma_{j}^{\top}\|_{F}\leq\nu$ and $\|\Sigma_{j}\Sigma_{j}^{\top}-V_{j+1}^{\top}U_{j}\Sigma_{j}\Sigma_{j}^{\top}U_{j}^{\top}V_{j+1}\|_{F}\leq 2\nu$. We may rewrite the latter of these two inequalities as

For matrices $A,B$, we have that $\|AB\|_{F}\leq\|A\|_{\sigma}\cdot\|B\|_{F}$. Therefore, for $j+1\leq i\leq N$, we have that

We now argue that $\|(\Sigma_{i-1}\Sigma_{i-1}^{\top})^{k}-(\Sigma_{i}^{\top}\Sigma_{i})^{k}\|_{F}\leq\nu\cdot kM^{2(k-1)}$. Note that $\|\Sigma_{i-1}\Sigma_{i-1}^{\top}-\Sigma_{i}^{\top}\Sigma_{i}\|_{F}\leq\nu$, verifying the case $k=1$. To see the general case, since square diagonal matrices commute, we have that

By the triangle inequality, we then have that

By an identical argument (formally, by replacing $W_{j}$ with $W_{N-j+1}^{\top}$), we get that

(19) and (20) verify (17) and (16), respectively, so it only remains to verify (18).

Let us write the eigendecomposition of $W_{1:N}W_{1:N}^{\top}$ with an orthogonal eigenbasis as $W_{1:N}W_{1:N}^{\top}=U\Sigma U^{\top}$, where $\Sigma$ is diagonal with its (non-negative) elements arranged in non-increasing order and $U$ is orthogonal. We can write the left hand side of (21) as $\|U\Sigma U^{\top}-U_{N}(\Sigma_{N}\Sigma_{N}^{\top})^{N}U_{N}^{\top}\|_{F}=\|\Sigma-U^{\top}U_{N}(\Sigma_{N}\Sigma_{N}^{\top})^{N}U_{N}^{\top}U\|_{F}$.

By an identical argument using (20), we get that, in the case that $d_{0}\leq d_{N}$, if $\sigma_{1,min}$ denotes the minimum singular value of $\Sigma_{1}$, then

(Notice that we have used the fact that the nonzero eigenvalues of $W_{1:N}W_{1:N}^{\top}$ are the same as the nonzero eigenvalues of $W_{1:N}^{\top}W_{1:N}$.) This completes the proof of (18). ∎

Using Lemma 5, we next show in Lemma 6 that if $W_{1},\ldots,W_{N}$ are approximately balanced, then an upper bound on $\|W_{N}\cdots W_{1}\|_{\sigma}$ implies an upper bound on $\|W_{j}\|_{\sigma}$ for $1\leq j\leq N$.

Suppose $\nu,C$ are real numbers satisfying $C>0$ and $0<\nu\leq\frac{C^{2/N}}{30N^{2}}$. Moreover suppose that the matrices $W_{1},\ldots,W_{N}$ satisfy the following:

For $1\leq j\leq N-1$, $\|W_{j+1}^{\top}W_{j+1}-W_{j}W_{j}^{\top}\|_{F}\leq\nu$.

Then for $1\leq j\leq N$, $\|W_{j}\|_{\sigma}\leq C^{1/N}\cdot 2^{1/(2N)}$.

For $1\leq j\leq N$, let us write the singular value decomposition of $W_{j}$ as $W_{j}=U_{j}\Sigma_{j}V_{j}^{\top}$, where the singular values of $W_{j}$ are decreasing along the main diagonal of $\Sigma_{j}$. By Lemma 4, we have that for $1\leq j\leq N-1$, $\|\Sigma_{j+1}^{\top}\Sigma_{j+1}-\Sigma_{j}\Sigma_{j}^{\top}\|_{F}\leq\nu$, which implies that $\left|\|\Sigma_{j+1}^{\top}\Sigma_{j+1}\|_{\sigma}-\|\Sigma_{j}\Sigma_{j}^{\top}\|_{\sigma}\right|\leq\nu$.

Write $M=\max_{1\leq j\leq N}\|W_{j}\|_{\sigma}=\max_{1\leq j\leq N}\|\Sigma_{j}\|_{\sigma}$. By the above we have that $\|\Sigma_{j}\Sigma_{j}^{\top}\|_{\sigma}\geq M^{2}-N\nu$ for $1\leq j\leq N$.

Let the singular value decomposition of $W_{1:N}$ be denoted by $W_{1:N}=U\Sigma V^{\top}$, so that $\|\Sigma\|_{\sigma}\leq C$. Then by (17) of Lemma 5 and Lemma 4 (see also (22), where the same argument was used), we have that

Now recall that $\nu$ is chosen so that $\nu\leq\frac{C^{2/N}}{30\cdot N^{2}}.$ Suppose for the purpose of contradiction that there is some $j$ such that $\|W_{j}W_{j}^{\top}\|_{\sigma}>2^{1/N}C^{2/N}$. Then it must be the case that

Next, using (25) and $(1+1/x)^{x}\leq e$ for all $x>0$,

Since $\|(\Sigma_{N}\Sigma_{N}^{\top})^{N}\|_{\sigma}=\|\Sigma_{N}\Sigma_{N}^{\top}\|_{\sigma}^{N}$, we get by combining (23) and (26) that

and since $1-e/20>1/(5/4)$, it follows that $\|\Sigma_{N}\Sigma_{N}^{\top}\|_{\sigma}<(5/4)^{1/N}C^{2/N}$, which contradicts (24). It follows that for all $1\leq j\leq N$, $\|W_{j}W_{j}^{\top}\|_{\sigma}\leq 2^{1/N}C^{2/N}$. The conclusion of the lemma then follows from the fact that $\|W_{j}W_{j}^{\top}\|_{\sigma}=\|W_{j}\|_{\sigma}^{2}$. ∎

D.2.2 Single-Step Descent

Lemma 7 below states that if certain conditions on $W_{1}(t),\ldots,W_{N}(t)$ are met, the sought-after descent — Equation (9) — will take place at iteration $t$. We will later show (by induction) that the required conditions indeed hold for every $t$, thus the descent persists throughout optimization. The proof of Lemma 7 is essentially a discrete, single-step analogue of the continuous proof for Lemma 1 (covering the case of gradient flow) given in Section 3.

Assume the conditions of Theorem 1. Moreover, suppose that for some $t$, the matrices $W_{1}(t),\ldots,W_{N}(t)$ and the end-to-end matrix $W(t):=W_{1:N}(t)$ satisfy the following properties:

$\|W_{j}(t)\|_{\sigma}\leq(4\|\Phi\|_{F})^{1/N}$ for $1\leq j\leq N$.

$\|W(t)-\Phi\|_{\sigma}\leq\|\Phi\|_{F}$.

$\|W_{j+1}^{\top}(t)W_{j+1}(t)-W_{j}(t)W_{j}^{\top}(t)\|_{F}\leq 2\delta$ for $1\leq j\leq N-1$.

${\sigma}_{min}:={\sigma}_{min}(W(t))\geq c$.

Then, after applying a gradient descent update (4) we have that

For simplicity write $M=(4\|\Phi\|_{F})^{1/N}$ and $B=\|\Phi\|_{F}$. We first claim that

Since $c\leq\sigma_{min}$, for (27) to hold it suffices to have

As the minimum singular value of $\Phi$ must be at least $c$, we must have $c\leq\|\Phi\|_{\sigma}$. Since then $\frac{c}{\|\Phi\|_{F}}\leq\frac{c}{\|\Phi\|_{\sigma}}\leq 1$, it holds that

The second inequality above is trivial, and for the first to hold, since $c\leq\|\Phi\|_{F}$, it suffices to take

which is guaranteed by the definition of $\delta$ in Theorem 1.

Next we continue with the rest of the proof. It follows from (14) thatHere, for matrices $A_{1},\ldots,A_{K}$ such that $A_{K}A_{K-1}\cdots A_{1}$ is defined, we write $\prod_{1}^{j=K}A_{j}:=A_{K}A_{K-1}\cdots A_{1}$.

where $(\star)$ denotes higher order terms in $\eta$. We now bound the Frobenius norm of $(\star)$. To do this, note that since $L(W)=\frac{1}{2}\|W-\Phi\|_{F}^{2}$, $\frac{dL}{dW}(W(t))=W(t)-\Phi$. Then

where the last inequality uses $\eta M^{N-2}BN\leq 1/2$, which is a consequence of (27). Next, by Lemma 5 with $\nu=2\delta$,

Next, by standard properties of tensor product, we have that

Let us write eigenvalue decompositions $W_{1}^{\top}W_{1}=UDU^{\top},W_{N}W_{N}^{\top}=VEV^{\top}$. Then

where the second inequality follows from (D.2.2). Hence the minimum diagonal element of $\Lambda$ is at least $(\sigma_{min}^{2}/(4/3))^{(N-1)/N}\geq\sigma_{min}^{2(N-1)/N}/(4/3)$.

It follows as a result of the above inequalities that if we write $E(t)=vec(W(t+1))-vec(W(t))+\eta(O\Lambda O^{\top})vec\left(\frac{dL}{dW}(W(t))\right)$, then

where the first inequality follows since $L(W)=\frac{1}{2}\|W-\Phi\|_{F}^{2}$ is $1$-smooth as a function of $W$. Next, by (29) and (30),

By (27, D.2.2), which bound $\eta,2\delta$, respectively, we have that

D.2.3 Proof of Lemma 2

We use induction on $t$, beginning with the base case $t=0$. Since the weights $W_{1}(0),\ldots,W_{N}(0)$ are $\delta$-balanced, we get that $\mathcal{A}(0)$ holds automatically. To establish $\mathcal{B}(0)$, note that since $W_{1:N}(0)$ has deficiency margin $c>0$ with respect to $\Phi$, we must have $\|W_{1:N}(0)-\Phi\|_{F}\leq\sigma_{min}(\Phi)\leq\|\Phi\|_{F}$, meaning that $L^{1}(W_{1:N}(0))\leq\frac{1}{2}\|\Phi\|_{F}^{2}$.

Finally, by $\mathcal{B}(0)$, which gives $\|W(0)-\Phi\|_{F}\leq\|\Phi\|_{F}$, we have that

To show that the above implies $\mathcal{C}(0)$, we use condition $\mathcal{A}(0)$ and Lemma 6 with $C=2\|\Phi\|_{F}$ and $\nu=2\delta$. By the definition of $\delta$ in Theorem 1 and since $c\leq\|\Phi\|_{F}$, we have that

as required by Lemma 6. As $\mathcal{A}(0)$ and (33) verify the preconditions 1. and 2., respectively, of Lemma 6, it follows that for $1\leq j\leq N$, $\|W_{j}(t)\|_{\sigma}\leq(2\|\Phi\|_{F})^{1/N}\cdot 2^{1/(2N)}<(4\|\Phi\|_{F})^{1/N}$, verifying $\mathcal{C}(0)$ and completing the proof of the base case.

The proof of Lemma 2 follows directly from the following inductive claims.

$\mathcal{A}(t),\mathcal{B}(t),\mathcal{C}(t)\Rightarrow\mathcal{B}(t+1)$. To prove this, we use Lemma 7. We verify first that the preconditions hold. First, $\mathcal{C}(t)$ immediately gives condition 1. of Lemma 7. By $\mathcal{B}(t)$, we have that $\|W(t)-\Phi\|_{\sigma}\leq\|W(t)-\Phi\|_{F}\leq\|\Phi\|_{F}$, giving condition 2. of Lemma 7. $\mathcal{A}(t)$ immediately gives condition 3. of Lemma 7. Finally, by $\mathcal{B}(t)$, we have that $L^{N}(W_{1}(t),\ldots,W_{N}(t))\leq L^{N}(W_{1}(0),\ldots,W_{N}(0))$, so $\sigma_{min}(W_{1:N}(t))\geq c$ by Claim 1. This verifies condition 4. of Lemma 7. Then Lemma 7 gives that $L^{N}(W_{1}(t+1),\ldots,W_{N}(t+1))\leq L^{N}(W_{1}(t),\ldots,W_{N}(t))-\frac{1}{2}\sigma_{min}(W(t))^{2(N-1)/N}\eta\left\|\frac{dL}{dW}(W(t))\right\|_{F}^{2}$, establishing $\mathcal{B}(t+1)$.

$\mathcal{A}(0),\mathcal{A}^{\prime}(1),\ldots,\mathcal{A}^{\prime}(t),\mathcal{A}(t),\mathcal{B}(0),\ldots,\mathcal{B}(t),\mathcal{C}(t)\Rightarrow\mathcal{A}(t+1),\mathcal{A}^{\prime}(t+1)$. To prove this, note that for $1\leq j\leq N-1$,

By $\mathcal{B}(0),\ldots,\mathcal{B}(t)$, $\|W_{1:N}(t)-\Phi\|_{F}\leq\|\Phi\|_{F}$. By the triangle inequality it then follows that $\|W_{1:N}(t)\|_{\sigma}\leq 2\|\Phi\|_{F}$. Also $\mathcal{A}(t)$ gives that for $1\leq j\leq N-1$, $\|W_{j}(t)W_{j}^{\top}(t)-W_{j+1}^{\top}(t)W_{j+1}(t)\|_{F}\leq 2\delta$. By Lemma 6 with $C=2\|\Phi\|_{F},\nu=2\delta$ (so that (34) is satisfied),

In the first inequality above, we have also used the fact that for matrices $A,B$ such that $AB$ is defined, $\|AB\|_{F}\leq\|A\|_{\sigma}\|B\|_{F}$. (35) gives us $\mathcal{A}^{\prime}(t+1)$.

We next establish $\mathcal{A}(t+1)$. By $\mathcal{B}(i)$ for $0\leq i\leq t$, we have that $\left\|\frac{dL}{dW}(W(i))\right\|_{F}=\left\|W-\Phi\right\|_{F}\leq\|\Phi\|_{F}$. Using $\mathcal{A}^{\prime}(i)$ for $0\leq i\leq t$ and summing over $i$ gives

Next, by $\mathcal{B}(0),\ldots,\mathcal{B}(t)$, we have that $L(W(i))\leq L(W(0))$ for $i\leq t$. Since $W(0)$ has deficiency margin of $c$ and by Claim 1, it then follows that $\sigma_{min}(W(i))\geq c$ for all $i\leq t$. Therefore, by summing $\mathcal{B}(0),\ldots,\mathcal{B}(t)$,

where (2) follows from the definition of $\eta$ in (7), and the last equality follows from definition of $\delta$ in Theorem 1. By (36), it follows that

$\mathcal{A}(t),\mathcal{B}(t)\Rightarrow\mathcal{C}(t)$. We apply Lemma 6 with $\nu=2\delta$ and $C=2\|\Phi\|_{F}$. First, the triangle inequality and $\mathcal{B}(t)$ give

verifying precondition 2. of Lemma 6. $\mathcal{A}(t)$ verifies condition 1. of Lemma 6, so for $1\leq j\leq N$, $\|W_{j}(t)\|_{\sigma}\leq(4\|\Phi\|_{F})^{1/N}$, giving $\mathcal{C}(t)$.

The proof of Lemma 2 then follows by induction on $t$. ∎

D.3 Proof of Theorem 2

Theorem 2 is proven by combining Lemma 8 below, which implies that the balanced initialization is likely to lead to an end-to-end matrix $W_{1:N}(0)$ with sufficiently large deficiency margin, with Theorem 1, which establishes convergence.

Then, with probability at least $(1-\epsilon)\cdot\frac{3-4F(2/\sqrt{b_{1}})}{2}$, $V$ will have deficiency margin $\|\Phi\|_{2}/(b_{2}d)$ with respect to $\Phi$.

The proof of Lemma 8 is postponed to Appendix D.5, where Lemma 8 will be restated as Lemma 16.

By Lemma 9 with $k=d_{0}/16$, we have that

We next use Lemma 8, with $b_{1}=\|\Phi\|_{2}^{2}/(2s^{2}d_{0}^{2}),b_{2}=2\|\Phi\|_{2}^{2}/(s^{2}d_{0}^{2})$; note that since $a\geq 2$, $b_{1}\geq 1$, as required by the lemma. Lemma 8 then implies that with probability at least

$W_{1:N}(0)$ will have deficiency margin ${s^{2}d_{0}}/{2\|\Phi\|_{2}}$ with respect to $\Phi$. By the definition of balanced initialization (Procedure 1) $W_{1}(0),\ldots,W_{N}(0)$ are -balanced. Since $2^{4}\cdot 6144<10^{5}$, our assumption on $\eta$ gives

so that Equation (7) holds with $c=\frac{s^{2}d_{0}}{2\|\Phi\|_{2}}$. The conditions of Theorem 1 thus hold with probability at least that given in Equation (38). In such a constant probability event, by Theorem 1 (and the fact that a positive deficiency margin implies $L^{1}(W_{1:N}(0))\leq\frac{1}{2}\|\Phi\|_{2}^{2}$), if we choose

then $L^{1}(W_{1:N}(t_{0}))\leq\frac{1}{8}\|\Phi\|_{2}^{2}$, meaning that $\|W_{1:N}(t_{0})-\Phi\|_{2}\leq\frac{1}{2}\|\Phi\|_{2}=\|\Phi\|_{2}-\frac{1}{2}\sigma_{min}(\Phi)$. Moreover, by condition $\mathcal{A}(t_{0})$ of Lemma 2 and the definition of $\delta$ in Theorem 1, we have, for $1\leq j\leq N-1$,

We now apply Theorem 1 again, verifying its conditions again, this time with the initialization $(W_{1}(t_{0}),\ldots,W_{N}(t_{0}))$. First note that the end-to-end matrix $W_{1:N}(t_{0})$ has deficiency margin $c=\|\Phi\|_{2}/2$ as shown above. The learning rate $\eta$, by Equation (39), satisfies Equation (7) with $c=\|\Phi\|_{2}/2$. Finally, since

for $d_{0}\geq 2$, by Equation (41), the matrices $W_{1}(t_{0}),\ldots,W_{N}(t_{0})$ are $\delta$-balanced with $\delta=\frac{\|\Phi\|^{2/N}(1/2)^{2}}{256N^{3}}$. Iteration $t_{0}$ thus satisfies the conditions of Theorem 1 with deficiency margin $\|\Phi\|_{2}/2$, meaning that for

Recall that this entire analysis holds only with the probability given in Equation (38). As $\lim_{d\rightarrow\infty}(1-2\exp(-d/16))=1$ and $\lim_{a\rightarrow\infty}(3-4F(2\sqrt{2/a}))/2=1/2$, for any $0<p<1/2$, there exist $a,d_{0}^{\prime}>0$ such that for $d_{0}\geq d_{0}^{\prime}$, the probability given in Equation (38) is at least $p$. This completes the proof.

In the context of the above proof, we remark that the expressions $1-2\exp(-d_{0}/16)$ and $(3-4F(2\sqrt{2/a}))/2$ converge to their limits of $1$ and $1/2$, respectively, as $d_{0},a\rightarrow\infty$ quite quickly. For instance, to obtain a probability of greater than $0.25$ of the initialization conditions being met, we may take $d_{0}\geq 100,a\geq 100$.

D.4 Proof of Claim 2

We first consider the probability of $\delta$-balancedness holding between any two layers:

Note that for $1\leq i,j\leq d$, let $X_{ij}$ be the random variable $(A^{T}A-BB^{T})_{ij}$, so that

Then (43) follows from Markov’s inequality. ∎

Now the proof of Claim 2 follows from a simple union bound:

By (43) of Lemma 10, for each $1\leq j\leq N-1$, $k\geq 1$,

and the claim follows with $\delta=ks^{2}\sqrt{10d_{max}^{3}}$. ∎

D.5 Proof of Claim 3

To establish Claim 3, we will use the following low-degree anti-concentration result of Carbery and Wright (2001) (see also Lovett (2010); Meka et al. (2016)):

There is an absolute constant $C_{{0}}$ such that the following holds. Suppose that ${h}$ is a multilinear polynomial of $K$ variables $X_{1},\ldots,X_{K}$ and of degree $N$. Suppose that $X_{1},\ldots,X_{K}$ are i.i.d. Gaussian. Then, for any $\epsilon>0$:

The below lemma characterizes the norm of the end-to-end matrix $W_{1:N}$ following zero-centered Gaussian initialization:

Let $f(W_{1},\ldots,W_{N})=\|W_{1:N}\|_{2}^{2}$, so that $f$ is a polynomial of degree $2N$ in the entries of $W_{1},\ldots,W_{N}$. Notice that

Next, by Lemma 11, there is an absolute constant $C_{0}>0$ such that for any $\epsilon>0$, and any $1\leq i_{0}\leq d_{0}$,

Since $f^{2}\geq g_{i_{0}}^{2}$ for each $i_{0}$, it follows that

Next, given $0<C_{2}<1$, choose $\epsilon=(1-C_{2})/(2C_{0}N)$, and $B_{1}=2/(1-C_{2})$. Then by (44) and (45) and a union bound, we have that

The result of the lemma then follows by taking $C_{1}=\max\left\{\frac{2}{1-C_{2}},\frac{2C_{0}}{1-C_{2}}\right\}$. ∎

For $d\geq 20$, choose any $0\leq h\leq 1$. Then, the area of a $(d,1)$-hyperspherical cap of height $h$ is at least

In Chudnov (1986), it is shown that the area of a $(d,1)$-hyperspherical cap of height $h$ is given by $\frac{1-C_{d-2}(h)/C_{d-2}(0)}{2}$, where

Next, by the inequality $1-t^{2}\geq\exp(-2t^{2})$ for $0\leq t\leq 1/2$,

where the last inequality follows from the standard estimate $F(x)\geq 1-\exp(-x^{2}/2)$ for $x\geq 1$. Also, since $1-t^{2}\leq\exp(-t^{2})$ for all $t$,

Therefore, for $d\geq 20$, by (46) and (47),

where the second inequality has used $1/(1-y)\leq 1+2y$ for all $0<y<1/2$ (and where $y=2\exp((-(d-3)/4))<2\exp(-17/4)<1/2$), and the final inequality uses $1+4\exp(-(d-3)/4)\leq\sqrt{2}$ for $d\geq 20$. The above chain of inequalities gives us the desired result. ∎

By rescaling, we may assume without loss of generality that $\|\Phi\|_{2}=1$, so that $r=1/\sqrt{ad}$. Let $\mathcal{D}$ denote the intersection of $B^{d}(r)$ with the open $d$-ball of radius $1-1/(ad)$ centered at $\Phi$. Let $\mathcal{C}\subset B^{d}(r)$ denote the $(d,r)$-hyperspherical cap of height r\cdot\big{(}1-2/(\sqrt{ad})\big{)}=r-2/(ad) whose base is orthogonal to the line between $\mathbf{0}$ and $\Phi$ (see Figure 2). Note that ${\sigma}^{d,r}(\partial\mathcal{D}\cap S^{d}(r))$, the Haar measure of the portion of $\partial\mathcal{D}$ intersecting $S^{d}(r)$, gives the probability that $V$ belongs to the boundary of $\mathcal{D}$. By Lemma 14 above (along with rescaling arguments), since $d\geq 20$, $\sigma^{d,r}(\partial\mathcal{C}\cap S^{d}(r))\geq\frac{1}{2}\cdot(3-4F(2/\sqrt{a}))$, and therefore $V\in{\partial}\mathcal{C}$ with at least this probability.

The calculation of $\left\|P-Q\right\|_{2}$ is simply an application of the law of cosines: letting $\theta$ be the angle determining the intersection of $\partial B^{d}(r)$ and $\mathcal{T}$ (see Figure 2), note that

Using that $\mathcal{C}\subseteq\mathcal{D}$, we continue with the proof. Notice the fact that $\mathcal{C}\subseteq\mathcal{D}$ is equivalent to $\partial\mathcal{C}\cap S^{d}(r)\subseteq\partial\mathcal{D}\cap S^{d}(r)$, by the structure of $\mathcal{C}$ and $\mathcal{D}$. Since the probability that $V$ lands in $\partial\mathcal{C}$ is at least $\frac{3-4F(2/\sqrt{a})}{2}$, this lower bound applies to $V$ landing in $\partial\mathcal{D}$ as well. Since all $V\in\partial\mathcal{D}$ have distance at most $1-1/(ad)$ from $\Phi$, and since $\sigma_{min}(\Phi)=\|\Phi\|_{2}=1$, it follows that for any $V\in\partial\mathcal{D}$, $\|V-\Phi\|_{2}\leq\sigma_{min}(\Phi)-1/(ad)$. Therefore, with probability of at least $\frac{3-4F(2/\sqrt{a})}{2}$, $V$ has deficiency margin $\|\Phi\|_{2}/(ad)$ with respect to $\Phi$. ∎