This paper concerns dictionary learning, i.e., sparse coding, a fundamental representation learning problem. We show that a subgradient descent algorithm, with random initialization, can recover orthogonal dictionaries on a natural nonsmooth, nonconvex L1 minimization formulation of the problem, under mild statistical assumption on the data. This is in contrast to previous provable methods that require either expensive computation or delicate initialization schemes. Our analysis develops several tools for characterizing landscapes of nonsmooth functions, which might be of independent interest for provable training of deep networks with nonsmooth activations (e.g., ReLU), among other applications. Preliminary synthetic and real experiments corroborate our analysis and show that our algorithm works well empirically in recovering orthogonal dictionaries. Dictionary learning (DL), i.e. , sparse coding, concerns the problem of learning compact representations, i.e., given data Y , one tries to find a representation basis A and coefficients X, so that Y ≈ AX where X is most sparse. DL has numerous applications especially in image processing and computer vision (Mairal et al., 2014) . When posed in analytical form, DL seeks a transformation Q such that QY is sparse; in this sense DL can be considered as an (extremely!) primitive "deep" network (Ravishankar & Bresler, 2013) .Many heuristic algorithms have been proposed to solve DL since the seminal work of Olshausen & Field (1996) , most of them surprisingly effective in practice (Mairal et al., 2014; Sun et al., 2015) . However , understandings on when and how DL is solvable have only recently started to emerge. Under appropriate generating models on A and X, Spielman et al. (2012) showed that complete (i.e., square, invertible) A can be recovered from Y , provided that X is ultra-sparse. Subsequent works BID0 BID1 Chatterji & Bartlett, 2017; BID4 provided similar guarantees for overcomplete (i.e. fat) A, again in the ultra-sparse regime. The latter methods are invariably based on nonconvex optimization with model-dependent initialization, rendering their practicality on real data questionable.The ensuing developments have focused on breaking the sparsity barrier and addressing the practicality issue. Convex relaxations based on the sum-of-squares (SOS) SDP hierarchy can recover overcomplete A when X has linear sparsity BID6 Ma et al., 2016; Schramm & Steurer, 2017) , while incurring expensive computation (solving large-scale SDP's or large-scale tensor decomposition). By contrast, Sun et al. (2015) showed that complete A can be recovered in the linear sparsity regime by solving a certain nonconvex problem with arbitrary initialization. However, the second-order optimization method proposed there is still expensive. This problem is partially addressed by (Gilboa et al., 2018) which proved that the first-order gradient descent with random initialization enjoys a similar performance guarantee.A standing barrier toward practicality is dealing with nonsmooth functions. To promote sparsity in the coefficients, the 1 norm is the function of choice in practical DL, as is common in modern signal processing and machine learning BID10 : despite its nonsmoothness, this choice often admits highly scalable numerical methods, such as proximal gradient method and alternating directionThe reader is welcome to refer to our arXiv version for future updates.method (Mairal et al., 2014) . The analyses in Sun et al. (2015) ; Gilboa et al. (2018) , however, focused on characterizing the algorithm-independent function landscape of a certain nonconvex formulation of DL, which takes a smooth surrogate to 1 to get around the nonsmoothness. The tactic smoothing there introduced substantial analysis difficulty, and broke the practical advantage of computing with the simple 1 function.In this paper, we show that working directly with a natural 1 norm formulation results in neat analysis and a practical algorithm. We focus on the problem of learning orthogonal dictionaries: given data {y i } i∈ [m] generated as y i = Ax i , where A ∈ R n×n is a fixed unknown orthogonal matrix and each x i ∈ R n is an iid Bernoulli-Gaussian random vector with parameter θ ∈ (0, 1), recover A. This statistical model is the same as in previous works (Spielman et al., 2012; Sun et al., 2015) .Write Y . = [y 1 , . . . , y m ] and similarly X . = [x 1 , . . . , x m ]. We propose to recover A by solving the following nonconvex (due to the constraint), nonsmooth (due to the objective) optimization problem: DISPLAYFORM0 |q y i | subject to q 2 = 1.(1.1)Based on the statistical model, q Y = q AX has the highest sparsity when q is a column of A (up to sign) so that q A is 1-sparse. Spielman et al. (2012) formalized this intuition and optimized the same objective as Eq. (1.1) with a q ∞ = 1 constraint, which only works when θ ∼ O(1/ √ n). Sun et al. (2015) worked with the sphere constraint but replaced the 1 objective with a smooth surrogate, introducing substantial analytical and computational deficiencies as alluded above.In constrast, we show that with sufficiently many samples, the optimization landscape of formulation (1.1) is benign with high probability (over the randomness of X), and a simple Riemannian subgradient descent algorithm can provably recover A in polynomial time. Theorem 1.1 (Main result, informal version of Theorem 3.1). Assume θ ∈ [1/n, 1/2]. For m ≥ Ω(θ −2 n 4 log 4 n), the following holds with high probability: there exists a poly(m, −1 )-time algorithm, which runs Riemannian subgradient descent on formulation (1.1) from at most O(n log n) independent, uniformly random initial points, and outputs a set of vectors { a 1 , . . . , a n } such that up to permutation and sign change, a i − a i 2 ≤ for all i ∈ [n].In words, our algorithm works also in the linear sparsity regime, the same as established in Sun et al. (2015) ; Gilboa et al. (2018) , at a lower sample complexity O(n 4 ) in contrast to the existing O(n 5.5 ) in Sun et al. (2015) . 1 As for the landscape, we show that (Theorems 3.4 and 3.6) each of the desired solutions {±a i } i∈ [n] is a local minimizer of formulation (1.1) with a sufficiently large basin of attraction so that a random initialization will land into one of the basins with at least constant probability. To obtain the result, we integrate and develop elements from nonsmooth analysis (on Riemannian manifolds), set-valued analysis, and random set theory, which might be valuable to studying other nonconvex, nonsmooth optimization problems. This paper presents the first theoretical guarantee for orthogonal dictionary learning using subgradient descent on a natural 1 minimization formulation. Along the way, we develop tools for analyzing the optimization landscape of nonconvex nonsmooth functions, which could be of broader interest.For futute work, there is an O(n 2 ) sample complexity gap between what we established in Theorem 3.1, and what we observed in the simulations alongside previous results based on the SOS method BID6 Ma et al., 2016; Schramm & Steurer, 2017) . As our main geometric result Theorem 3.6 already achieved tight bounds on the directional derivatives, further sample complexity improvement could potentially come out of utilizing second-order information such as the strong negative curvature (Lemma B.2), or careful algorithm-dependent analysis.While our result applies only to (complete) orthogonal dictionaries, a natural question is whether we can generalize to overcomplete dictionaries. To date the only known provable algorithms for learning overcomplete dictionaries in the linear sparsity regime are based on the SOS method BID6 Ma et al., 2016; Schramm & Steurer, 2017) . We believe that our nonsmooth analysis has the potential of handling over-complete dictionaries, as for reasonably well-conditioned overcomplete dictionaries A, each a i (columns of A) makes a A approximately 1-sparse and so a i AX gives noisy estimate of a certain row of X. So the same formulation as Eq. (1.1) intuitively still works. We would like to leave that to future work.Nonsmooth phase retrieval and deep networks with ReLU mentioned in Section 1.1 are examples of many nonsmooth, nonconvex problems encountered in practice. Most existing theoretical results on these problems tend to be technically vague about handling the nonsmooth points: they either prescribe a rule for choosing a subgradient element, which effectively disconnects theory and practice because numerical testing of nonsmooth points is often not reliable, or ignore the nonsmooth points altogether, assuming that practically numerical methods would never touch these points-this sounds intuitive but no formalism on this appears in the relevant literature yet. Besides our work, (Laurent & von Brecht, 2017; Kakade & Lee, 2018 ) also warns about potential problems of ignoring nonsmooth points when studying optimization of nonsmooth functions in machine learning. We need the Hausdorff metric to measure differences between nonempty sets. For any set X and a point p in R n , the point-to-set distance is defined as DISPLAYFORM0 For any two sets X 1 , X 2 ∈ R n , the Hausdorff distance is defined as DISPLAYFORM1 Moreover, for any sets DISPLAYFORM2 (A.4) On the sets of nonempty, compact subsets of R n , the Hausdorff metric is a valid metric; particularly, it obeys the triangular inequality: for nonempty, compact subsets X, Y, Z ⊂ R n , DISPLAYFORM3 (A.5) See, e.g., Sec. 7.1 of Sternberg (2013) for a proof. Lemma A.1 (Restatement of Lemma A.1). For convex compact sets X, Y ⊂ R n , we have DISPLAYFORM4 where h S (u) . = sup x∈S x, u is the support function associated with the set S.
Efficient dictionary learning by L1 minimization via a novel analysis of the non-convex non-smooth geometry.
{"src": "scitldr-AIC_train", "paper_id": "HklSf3CqKm"}