We analyze speed of convergence to global optimum for gradient descent training a deep linear neural network by minimizing the L2 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). 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 FORMULA1 ), 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) ; BID12 ). 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) ; BID1 ) 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, BID1 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.Even in the linear network setting, a rigorous proof of efficient convergence to global minimum has proved elusive. One recent progress is the analysis of BID3 for linear residual networks -a particular subclass of linear neural networks in which the input, output and all hidden dimensions are equal, and all layers are initialized to be the identity matrix (cf. Hardt and Ma (2016) ). Through a trajectory-based analysis of gradient descent minimizing 2 loss over a whitened dataset (see Section 2), BID3 show that convergence to global minimum at a linear rateloss is less than > 0 after O(log 1 ) iterations -takes place if one of the following holds: (i) the objective value at initialization is sufficiently close to a global minimum; or (ii) a global minimum is attained when the product of all layers is positive definite.The current paper carries out a trajectory-based analysis of gradient descent for general deep linear neural networks, covering the residual setting of BID3 , as well as many more settings that better match practical deep learning. Our analysis draws upon the trajectory characterization of BID1 for gradient flow (infinitesimally small learning rate), together with significant new ideas necessitated due to discrete updates. Ultimately, we show that when minimizing 2 loss of a deep linear network over a whitened dataset, gradient descent converges to the global minimum, at a linear rate, provided that the following conditions hold: (i) the dimensions of hidden layers are greater than or equal to the minimum between those of the input and output; (ii) layers are initialized to be approximately balanced (see Definition 1) -this is met under commonplace near-zero, as well as residual (identity) initializations; and (iii) the initial loss is smaller than any loss obtainable with rank deficiencies -this condition will hold with probability close to 0.5 if the output dimension is 1 (scalar regression) and standard (random) near-zero initialization is employed. Our result applies to networks with arbitrary depth and input/output dimensions, as well as any configuration of hidden layer widths that does not force rank deficiency (i.e. that meets condition (i)). 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 case of scalar regression, they are met with constant probability under a random initialization scheme. We are not aware of any similarly general analysis for efficient convergence of gradient descent to global minimum in deep learning.The remainder of the paper is organized as follows. In Section 2 we present the problem of gradient descent training a deep linear neural network by minimizing the 2 loss over a whitened dataset. Section 3 formally states our assumptions, and presents our convergence analysis. Key ideas brought forth by our analysis are demonstrated empirically in Section 4. Section 5 gives a review of relevant literature, including a detailed comparison of our results against those of BID3 . Finally, Section 6 concludes. 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.A 2 LOSS OVER WHITENED DATA Recall the 2 loss of a linear predictor W ∈ R dy×dx as defined in Section 2: DISPLAYFORM0 By definition, when data is whitened, Λ xx is equal to identity, yielding: 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: DISPLAYFORM1 Claim 2. Assume all entries in the matrices W j ∈ R dj ×dj−1 , j = 1, . . . , N , are drawn independently at random from a Gaussian distribution with mean zero and standard deviation s > 0. Then, for any δ > 0, the probability of W 1 , . . . , W N being δ-balanced is at least max{0, 1 − 10δ DISPLAYFORM2 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.Claim 3. There is a constant C 1 > 0 such that the following holds. Consider the case where DISPLAYFORM3 13 and suppose all entries in the matrices W j ∈ R dj ×dj−1 , j = 1, . . . , N , are drawn independently at random from a Gaussian distribution with mean zero, whose standard deviation s > 0 is small with respect to the target, i.e. DISPLAYFORM4 , the probability of the end-to-end matrix W 1:N having deficiency margin c with respect to Φ is at least 0.49 if: DISPLAYFORM5 Proof. See Appendix D.5. 13 The requirement d0 ≥ 20 is purely technical, designed to simplify expressions in the claim. 14 The probability 0.49 can be increased to any p < 1/2 by increasing the constant 10 5 in the upper bounds for s and c.15 It is not difficult to see that the latter threshold is never greater than the upper bound for s, thus sought-after standard deviations always exist.
We analyze gradient descent for deep linear neural networks, providing a guarantee of convergence to global optimum at a linear rate.
{"src": "scitldr-AIC_train", "paper_id": "SkMQg3C5K7"}