Randomly initialized first-order optimization algorithms are the method of choice for solving many high-dimensional nonconvex problems in machine learning, yet general theoretical guarantees cannot rule out convergence to critical points of poor objective value. For some highly structured nonconvex problems however, the success of gradient descent can be understood by studying the geometry of the objective. We study one such problem -- complete orthogonal dictionary learning, and provide converge guarantees for randomly initialized gradient descent to the neighborhood of a global optimum. The resulting rates scale as low order polynomials in the dimension even though the objective possesses an exponential number of saddle points. This efficient convergence can be viewed as a consequence of negative curvature normal to the stable manifolds associated with saddle points, and we provide evidence that this feature is shared by other nonconvex problems of importance as well. Many central problems in machine learning and signal processing are most naturally formulated as optimization problems. These problems are often both nonconvex and highdimensional. High dimensionality makes the evaluation of second-order information prohibitively expensive, and thus randomly initialized first-order methods are usually employed instead. This has prompted great interest in recent years in understanding the behavior of gradient descent on nonconvex objectives (18; 14; 17; 11) . General analysis of first-and second-order methods on such problems can provide guarantees for convergence to critical points but these may be highly suboptimal, since nonconvex optimization is in general an NP-hard probem BID3 . Outside of a convex setting (28) one must assume additional structure in order to make statements about convergence to optimal or high quality solutions. It is a curious fact that for certain classes of problems such as ones that involve sparsification (25; 6) or matrix/tensor recovery (21; 19; 1) first-order methods can be used effectively. Even for some highly nonconvex problems where there is no ground truth available such as the training of neural networks first-order methods converge to high-quality solutions (40).Dictionary learning is a problem of inferring a sparse representation of data that was originally developed in the neuroscience literature (30), and has since seen a number of important applications including image denoising, compressive signal acquisition and signal classification (13; 26) . In this work we study a formulation of the dictionary learning problem that can be solved efficiently using randomly initialized gradient descent despite possessing a number of saddle points exponential in the dimension. A feature that appears to enable efficient optimization is the existence of sufficient negative curvature in the directions normal to the stable manifolds of all critical points that are not global minima BID0 . This property ensures that the regions of the space that feed into small gradient regions under gradient flow do not dominate the parameter space. FIG0 illustrates the value of this property: negative curvature prevents measure from concentrating about the stable manifold. As a consequence randomly initialized gradient methods avoid the "slow region" of around the saddle point. Negative curvature helps gradient descent. Red: "slow region" of small gradient around a saddle point. Green: stable manifold associated with the saddle point. Black: points that flow to the slow region. Left: global negative curvature normal to the stable manifold. Right: positive curvature normal to the stable manifold -randomly initialized gradient descent is more likely to encounter the slow region.The main results of this work is a convergence rate for randomly initialized gradient descent for complete orthogonal dictionary learning to the neighborhood of a global minimum of the objective. Our results are probabilistic since they rely on initialization in certain regions of the parameter space, yet they allow one to flexibly trade off between the maximal number of iterations in the bound and the probability of the bound holding.While our focus is on dictionary learning, it has been recently shown that for other important nonconvex problems such as phase retrieval BID7 performance guarantees for randomly initialized gradient descent can be obtained as well. In fact, in Appendix C we show that negative curvature normal to the stable manifolds of saddle points (illustrated in FIG0 ) is also a feature of the population objective of generalized phase retrieval, and can be used to obtain an efficient convergence rate. The above analysis suggests that second-order properties -namely negative curvature normal to the stable manifolds of saddle points -play an important role in the success of randomly initialized gradient descent in the solution of complete orthogonal dictionary learning. This was done by furnishing a convergence rate guarantee that holds when the random initialization is not in regions that feed into small gradient regions around saddle points, and bounding the probability of such an initialization. In Appendix C we provide an additional example of a nonconvex problem that for which an efficient rate can be obtained based on an analysis that relies on negative curvature normal to stable manifolds of saddles -generalized phase retrieval. An interesting direction of further work is to more precisely characterize the class of functions that share this feature.The effect of curvature can be seen in the dependence of the maximal number of iterations T on the parameter ζ 0 . This parameter controlled the volume of regions where initialization would lead to slow progress and the failure probability of the bound 1 − P was linear in ζ 0 , while T depended logarithmically on ζ 0 . This logarithmic dependence is due to a geometric increase in the distance from the stable manifolds of the saddles during gradient descent, which is a consequence of negative curvature. Note that the choice of ζ 0 allows one to flexibly trade off between T and 1 − P. By decreasing ζ 0 , the bound holds with higher probability, at the price of an increase in T . This is because the volume of acceptable initializations now contains regions of smaller minimal gradient norm. In a sense, the result is an extrapolation of works such as (23) that analyze the ζ 0 = 0 case to finite ζ 0 .Our analysis uses precise knowledge of the location of the stable manifolds of saddle points.For less symmetric problems, including variants of sparse blind deconvolution (41) and overcomplete tensor decomposition, there is no closed form expression for the stable manifolds. However , it is still possible to coarsely localize them in regions containing negative curvature. Understanding the implications of this geometric structure for randomly initialized first-order methods is an important direction for future work.One may hope that studying simple model problems and identifying structures (here, negative curvature orthogonal to the stable manifold) that enable efficient optimization will inspire approaches to broader classes of problems. One problem of obvious interest is the training of deep neural networks for classification, which shares certain high-level features with the problems discussed in this paper. The objective is also highly nonconvex and is conjectured to contain a proliferation of saddle points BID10 , yet these appear to be avoided by first-order methods BID15 for reasons that are still quite poorly understood beyond the two-layer case (39).[19] Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi. Low-rank matrix completion using alternating minimization. DISPLAYFORM0 . Thus critical points are ones where either tanh( q µ ) = 0 (which cannot happen on S n−1 ) or tanh( q µ ) is in the nullspace of (I − qq * ), which implies tanh( q µ ) = cq for some constant b. The equation tanh( x µ ) = bx has either a single solution at the origin or 3 solutions at {0, ±r(b)} for some r(b). Since this equation must be solves simultaneously for every element of q, we obtain ∀i ∈ [n] : q i ∈ {0, ±r(b)}. To obtain solutions on the sphere, one then uses the freedom we have in choosing b (and thus r(b)) such that q = 1. The resulting set of critical points is thus DISPLAYFORM1 To prove the form of the stable manifolds, we first show that for q i such that |q i | = q ∞ and any q j such that |q j | + ∆ = |q i | and sufficiently small ∆ > 0, we have DISPLAYFORM2 For ease of notation we now assume q i , q j > 0 and hence ∆ = q i − q j , otherwise the argument can be repeated exactly with absolute values instead. The above inequality can then be written as DISPLAYFORM3 If we now define DISPLAYFORM4 where the O(∆ 2 ) term is bounded. Defining a vector r ∈ R n by DISPLAYFORM5 we have r 2 = 1. Since tanh(x) is concave for x > 0, and |r i | ≤ 1, we find DISPLAYFORM6 From DISPLAYFORM7 and thus q j ≥ 1 √ n − ∆. Using this inequality and properties of the hyperbolic secant we obtain DISPLAYFORM8 and plugging in µ = c √ n log n for some c < 1 DISPLAYFORM9 log n + log log n + log 4).We can bound this quantity by a constant, say h 2 ≤ 1 2 , by requiring DISPLAYFORM10 ) log n + log log n ≤ − log 8and for and c < 1, using − log n + log log n < 0 we have DISPLAYFORM11 Since ∆ can be taken arbitrarily small, it is clear that c can be chosen in an n-independent manner such that A ≤ − log 8. We then find DISPLAYFORM12 since this inequality is strict, ∆ can be chosen small enough such that O(∆ 2 ) < ∆(h 1 − h 2 ) and hence h > 0, proving 9.It follows that under negative gradient flow, a point with |q j | < ||q|| ∞ cannot flow to a point q such that |q j | = ||q || ∞ . From the form of the critical points, for every such j, q must thus flow to a point such that q j = 0 (the value of the j coordinate cannot pass through 0 to a point where |q j | = ||q || ∞ since from smoothness of the objective this would require passing some q with q j = 0, at which point grad [f Sep ] (q ) j = 0).As for the maximal magnitude coordinates , if there is more than one coordinate satisfying |q i1 | = |q i2 | = q ∞ , it is clear from symmetry that at any subsequent point q along the gradient flow line q i1 = q i2 . These coordinates cannot change sign since from the smoothness of the objective this would require that they pass through a point where they have magnitude smaller than 1/ √ n, at which point some other coordinate must have a larger magnitude (in order not to violate the spherical constraint), contradicting the above result for non-maximal elements. It follows that the sign pattern of these elements is preserved during the flow. Thus there is a single critical point to which any q can flow, and this is given by setting all the coordinates with |q j | < q ∞ to 0 and multiplying the remaining coordinates by a positive constant to ensure the resulting vector is on S n . Denoting this critical point by α, there is a vector b such that q = P S n−1 [a(α) + b] and supp(a(α)) ∩ supp(b) = ∅, b ∞ < 1 with the form of a(α) given by 5 . The collection of all such points defines the stable manifold of α.Proof of Lemma 2: (Separable objective gradient projection). i) We consider the sign(w i ) = 1 case; the sign(w i ) = −1 case follows directly.Recalling that DISPLAYFORM13 qn , we first prove DISPLAYFORM14 for some c > 0 whose form will be determined later. The inequality clearly holds for w i = q n .To DISPLAYFORM15 verify that it holds for smaller values of w i as well, we now show that ∂ ∂w i tanh w i µ − tanh q n µ w i q n − c(q n − w i ) < 0 which will ensure that it holds for all w i . We define s 2 = 1 − ||w|| 2 + w 2 i and denote q n = s 2 − w 2 i to extract the w i dependence, givingWhere in the last inequality we used properties of the sech function and q n ≥ w i . We thus want to show DISPLAYFORM16 and it follows that 10 holds. For µ < 1 BID15 we are guaranteed that c > 0.From examining the RHS of 10 (and plugging in q n = s 2 − w 2 i ) we see that any lower bound on the gradient of an element w j applies also to any element |w i | ≤ |w j |. Since for |w j | = ||w|| ∞ we have q n − w j = w j ζ, for every log( 1 µ )µ ≤ w i we obtain the bound DISPLAYFORM17 Proof of Theorem 1: (Gradient descent convergence rate for separable function).We obtain a convergence rate by first bounding the number of iterations of Riemannian gradient descent in C ζ0 \C 1 , and then considering DISPLAYFORM18 . Choosing c 2 so that µ < 1 2 , we can apply Lemma 2, and for u defined in 7, we thus have DISPLAYFORM19 Since from Lemma 7 the Riemannian gradient norm is bounded by √ n, we can choose c 1 , c 2 such that µ log( DISPLAYFORM20 . This choice of η then satisfies the conditions of Lemma 17 with r = µ log( DISPLAYFORM21 , M = √ n, which gives that after a gradient step DISPLAYFORM22 for some suitably chosenc > 0. If we now define by w (t) the t-th iterate of Riemannian gradient descent and DISPLAYFORM23 and the number of iterations required to exit C ζ0 \C 1 is DISPLAYFORM24 To bound the remaining iterations, we use Lemma 2 to obtain that for every w ∈ C ζ0 \B ∞ r , DISPLAYFORM25 where we have used ||u DISPLAYFORM26 We thus have DISPLAYFORM27 Choosing DISPLAYFORM28 where L is the gradient Lipschitz constant of f s , from Lemma 5 we obtain DISPLAYFORM29 According to Lemma B, L = 1/µ and thus the above holds if we demand η < µ 2 . Combining 12 and 13 gives DISPLAYFORM30 .To obtain the final rate, we use in g(w 0 ) − g * ≤ √ n andcη < 1 ⇒ 1 log(1+cη) <C cη for somẽ C > 0. Thus one can choose C > 0 such that DISPLAYFORM31 From Lemma 1 the ball B ∞ r contains a global minimizer of the objective, located at the origin.The probability of initializing in Ȃ C ζ0 is simply given from Lemma 3 and by summing over the 2n possible choices of C ζ0 , one for each global minimizer (corresponding to a single signed basis vector).
We provide an efficient convergence rate for gradient descent on the complete orthogonal dictionary learning objective based on a geometric analysis.
{"src": "scitldr-AIC_train", "paper_id": "HyxlHsActm"}