Geometric Analysis of Nonconvex Optimization Landscapes for Overcomplete Learning
Authors: Qing Qu
Yuexiang Zhai
Xiao Li
Yuqian Zhang
Zhihui Zhu
Venue:  (2020)
Keywords: dictionary learning
sparse representations
nonconvex optimization

Abstract: Learning overcomplete representations finds many applications in machine learning and data analytics. In the past decade, despite the empirical success of heuristic methods, theoretical understandings and explanations of these algorithms are still far from satisfactory. In this work, we provide new theoretical insights for several important representation learning problems: learning (i) sparsely used overcomplete dictionaries and (ii) convolutional dictionaries. We formulate these problems as $\ell^4$-norm optimization problems over the sphere and study the geometric properties of their nonconvex optimization landscapes. For both problems, we show the nonconvex objective has benign (global) geometric structures, which enable the development of efficient optimization methods finding the target solutions. Finally, our theoretical results are justified by numerical simulations.


Published as a conference paper at ICLR 2020
GEOMETRIC ANALYSIS OF NONCONVEX OPTIMIZA- TION LANDSCAPES FOR OVERCOMPLETE LEARNING
Qing Qu"
Yuexiang Zhai
Xiao Li
Center for Data Science
EECS
Elctronic Engineering CUHK
New York University
UC Berkeley
nq213@nyu.edu
ysz berkeley.edu
xli @li@ee..cme we.cuhk..duu edu.
Yuqian Zhang
Zhihui Zhu
Electrical & Computer Engineering
Electrical & Computer Engineering
Rutgers University
University of Denver
yqz.zhang @ rutgers.
zhihui zhu @ du.edu
ABSTRACT
Learning overcomplete representations finds many applications in machine learning and data analytics. In the past decade, despite the empirical success of heuristic methods, theoretical understandings and explanations of these algorithms are still far from satisfactory. In this work, we provide new theoretical insights for several important representation learning problems: learning (i) sparsely used overcom- plete dictionaries and (ii) convolutional dictionaries. We formulate these problems as ---norm optimization problems over the sphere, and study the geometric prop- erties of their nonconvex optimization landscapes. For both problems, we show the nonconvex objectives have benign (global) geometric structures, which enable development of efficient optimization methods finding the target solutions. Finally, our theoretical results are justified by numerical simulations.
INTRODUCTION
High dimensional data often has lov-complexity structures (e.g.. sparsity or low rankness). The performance of modern machine learning and data analytical methods heavily depends appropriate low-complexity data representations (or features) which capture hidden information underlying the data. While we used manually craft representations in the past, has been demonstrated that learned representations from the data show much superior performance (Elad, 2010). Therefore, (unsupervised) learning latent representations of high-dimensional data becomes fundamental problem in signal processing, machine learning, theoretical neuroscience and many other fields (Bengio al., 2013). Moreover, overcomplete representations for which the number of latent features exceeds the data dimensionality, have shown better representation of the data in various applications compared to complete representations (Lewicki & Sejnowski, 2000; Chen et al., 2001; Rubinstein al., 2010). In this paper, we study the following overcomplete representation learning problems.
Overcomplete dictionary learning (ODL). One of the most important unsupervised representa- tion learning problems is learning sparsely used dictionaries (Olshausen & Field, 1997), which finds many applications in image processing and computer vision (Wright et al., 2010; Mairal et al., 2014). The task is given data
(1.1)
dictionary
sparse
want to learn the compact representation (or dictionary) A Raxm along with the sparse code X e Rmxp, For better representation of the data, it is often more desired that the dictionary A is overcomplete m n, where it provides greater flexibility in matching structures in the data.
Convolutional dictionary learning (CDL). Inspired by deconvolutional networks (Zeiler et al., 2010), the convolutional form of sparse representations (Bristow et al., 2013; Farcia-Cardoma &
*hhe full version of this work be found https: https://arxiv.orgg//
02427.

---

Published as a conference paper at ICLR 2020
Wohlberg, 2018) replaces the unstructured dictionary A with set of convolution filters {aok k==1 Namely, the problem is that given multiple circulant convolutional measurements
yi
Gok
Jisk
i P.
(1.2)
filter
sparse code
one wants to Iearn the filters {cos)k-1 along with the sparse codes. The problem resembles a lot similarities to classical ODL. Indeed, one can show that Equation (1.2) reduces to Equation (1.1) in overcomplete settings by reformulation (Huang & Anandkumar, 2015). The interest of studying CDL was spurred by its better modeling ability of human visual and cognitive systems and the development of more efficient computational methods (Bristow et al., 2013), and has led to a number of applications in which the convolutional form provides state-of-art performance (Gu et al., 2015; Papyan et al., 7b; Lau et al., 2019). Recently, the connections between CDL and convolutional neural network have also been extensively studied (Papyan et al., 2017a; 2018).
In addition, variants of finding overcomplete representations appear in many other problems beyond the dictionary learning problems we introduced here, such as overcomplete tensor decomposition (Anandkumar et al., 2017; Ge & Ma, 2017), overcomplete ICA (Lewicki & Sejnowski, 1998; Le et al., 201 I), and thort-and-sparss blind deconvolution (Zhang et al., 2017; 2018; Kuo al., 2019).
Prior arts on dictionary learning (DL). In the past decades, numerous heuristic methods have been developed for solving DL (Lee et al., 2007; Aharon al., 2006; Mairal et al., 2010). Despite their empirical success (Wright et al., 2010; Mairal et al., 2014), theoretical understandings of when and why these methods work are still limited.
When the dictionary A is complete (Spielman et al., 2012) (i.e., square and invertible, m n), by the fact that the row space of Y equals to that of X (i.e., row(Y) = row(X)), Sun et al. (2016a) reduced the problem to finding the sparsest vector in subspace (Demanet & Hand, 2014; Qu et al., 2016). By considering a (smooth) variant of the following f e'-minimization problem over the sphere,
min
q Y 1
s.t.
g
(1.3)
Sun et al. (2016a) showed that the nonconvex problem has no spurious local minima when the sparsity level' e ((), and every local minimizer q. is global minimizer with q. Y corresponding to one row of X. The new discovery has led efficient, guaranteed optimization methods for complete DL from random initializations (Sun et al., 2016b; Bai et al., 2018 10 Gilboa et al., 2019).
However, all these methods critically rely on the fact that row row(Y) row( X) for complete A, there is no obvious way to generalize the approach to the overcomplete setting m. > n. On the other hand, for learning incoherent overcomplete dictionaries, with sparsity E ((1//R) and stringent assumptions on X, most of the current theoretical analysis results are local (Geng et al., 2011; Arora et al., 2015; Agarwal al., 2016; Chatterji Bartlett, 2017), in the sense that they require complicated initializations that could be difficult to implement in practice. Therefore, the legitimate question remains: why do heuristic methods solve ODL with simple initializations?
Contributions. In this work we study the geometry of nonconvex landscapes for overcom- plete/convolutionnal DL, where our result can be simply summarized by the following statement.
There exists nonconvex formulations for ODL/CDL with benign optimization landscapes, that descent methods can learn overcomplete/connoluiion dictionaries with simple" initializations.
Our approach follows the spirit of Sun et al. (2016a), while we overcome the aforementioned obstacles for overcomplete dictionaries by directly finding columns of A instead of recovering sparse rows of X. We achieve this by reducing the problem to maximizing the e norm'm of Y q over the sphere,
1 Herre the sparsity level 0 denotes the proportion of nonzero entries in X.
Here, for ODL simple means random initializations: for CDL, it means simple data-driven initializations.
'The use of gd - can also be justified from the perspective of sum of squares (SOS) (Barak et al., 2015; Ma et al.. 2016; Schramm & Steurer, 2017). One can utilize properties of higher order SOS polynomials (such as 4-th order polynomials) to correctly recover columns of A. But the complexity of these methods are polmoma,, and hence much more expensive than the direct optimization approach we consider here.
2

---

Published as a conference paper at ICLR 2020
which is known to promote the spikiness of the solution (Zhang al., 2018: Li & Bresler, 2018; Zhai et al., 2019). In particular, we show the following results for ODL and CDL, respectively.
For the ODL problem, when A unit norm tight frame and incoherent, our nonconvex objective is strict saddle (Ge et al., 2015; Sun et al., 2015b) in the sense that any saddle point can be escaped by negative curvature and all local minimizers are globally optimal. Furthermore, every local minimizer is close to a column of A.
2. For the CDL problem, when the filters are self and mutual incoherent, similar nonconvex objective is strict saddle over a sublevel set, within which every local minimizer is close to a target solution. Moreover, develop simple dataedriven initialization that falls into this sublevel set.
Our analysis on ODL provides the first global characterization for nonconvex optimization landscape in the overcomplete regime. On the other hand, result also gives the first provable guarantee for CDL. Indeed, under mild assumptions, our landscape analysis implies that with simple initializations, any descent method with the ability of escaping strict saddle points* provably finds global minimizers that are close to our target solutions for both problems. Moreover, our result opens up several interesting directions on nonconvex optimization that are worth of further investigations.
OVERCOMPLETE DICTIONARY LEARNING
In this section, we start stating our result with ODL. In Section 3, we will show how our geometric analysis here can be extended to CDL in a nontrivial way.
2.1 BASIC ASSUMPTIONS
We study the DL problem in Equation (1.1) under the following assumptions for A E Raxm and assumption for the dictionary A can be viewed generalization of orthogonality in the overcomplete setting (Mixon, 2016).
X Rmxp, In particular,
Assumption 2.1 (Tight frame and incoherent dictionary A) We assume that the dictionary A is unit norm tight frame (UNTF) (Mixon, 2016), in the sense that
- AA = I, a = 1 (1Et
n
(2.1)
m
and its columns satisfy the y-incoherence condition. condittio Namely, let A
[[]
a2
am.
m(A)
==
max LEffjEm
K
|ail
a;
aj [ayll
E (0, 1).
(2.2)
We assume the coherence of A is small, i.e., p(A) < 1. Assumption 2.2 (Random Bernoulli-Gausian X) We assume entries of X m.dd BG(O)², that
X BOG, Big ridd Ber(O),
Gij~i.h N(O,,), 1),
where the Bernoulli parameter 0 e (0,1) controls the sparsity level of X.
The coherence parameter μ plays an important role in shaping the optimization land- scape. A smaller coherence implies that the columns of A are less correlated, and hence easier for optimization. For matrices with & -onormallzedd columns, classical Welch bound (Welch, 1974;
Remark 1.
Foucart & Rauhut, 2013a) suggests that the coherence μ lower bounded by ((A)
(mm-1)m
which is achieved when A is equiangular tight frame (Sustik et al., 2007). For a generic random
matrix A, w.h.p. it is approximately UNTF, with coherence μ(A) ~ V log m roughly achieving
the order of Welch bound. For typical dictionary A under Assumption 2.1, this suggests that the coherence parameter ((A) often decreases w.r.t. the feature dimension n.
'Recent results show that methods such as trust-region (Absil ct al., 2007; Boumal et al., 2018), cubic- regularization (Nesterov & Polyak, 2006), curvilinear search (Goldfarb et al., 2017), and even gradient descent (Lee al., 2016) can provably escape strict saddle points.
'Here, we use (0) for abbreviation of Semoulli-Gausiinn distribution, with sparsity level 0 E (0, 1). 'For instance, when A random Gaussian matrix, with each entry ai L.d.d. N (0, 1/n).
3

---

Published as a conference paper at ICLR 2020
(a) (r()), n 3, m
(b) (T())))
03
spikiness
Figure 2: Spikiness e(C)
vs.
|< / ||ll We generate UNTF A. randomly draw many points
Figure Plots of landscapes (p((q) and (Q) over 3?.
Both function values normalized to [0, 1]. The overcomplete
q q sm-1, and compute |< and spikiness e(C) in (2.6) with S A q. On the plot, we mark each point q g"-1 by *+".
dictionary A is generated to be UNTF, with n = 3 and m 4.
The sparse coefficient X BG(() with
0.1 and p 2 x 10a. Black dots denote columns of A (target).
2.2 PROBLEM FORMULATION
We solve DL in the overcomplete regime by considering the following problem
min PDL(g) == CDL
1 = CDL 1 A s.t. |ql12 = 1,
(2.3)
where CDL O is a normalizing constant. At the first glance, our objective looks similar to Equation (1.3) in complete DL, but we tackle the problem from very different aspect we directly find columns of A instead of recovering sparse rows of X. Given UNTF A and random X ~ (g( our intuition of solving Equation (2.3) originates from the fact (Lemma D.1)
0
Ex [q)
(g
PT(g)
q
(2.4)
2(1 0)
n
4
where (Q)()) can be viewed as the objective for 4th order tensor decomposition Ge Ma (2017).
When is large, this tells us that optimizing Equation (2.3) is approximately maximizing no of Ç A over the sphere (see Figure 1). If q equals to one of the target solutions (e.g., a1),
((q) = A A = [
am
(2.5)
H <
then Ç is spiky when f is small (e.g., μr & 1). Here, we introduce a notion of spikiness g for a vector
m by e(C) / |(nD ((2) ... ((m))
(2.6)
where C(s) denotes the ith ordered entry of Ç. Figure 2 shows that larger e(C) leads to larger [ with (--ormm fixed. This implies that maximizing E4-norm over the sphere promotes the spikiness of (Zhang et al., 2018; Li & Bresler, 2018; Zhai et al., 2019). Thus, from Equation (2.5), we expect the global minimizer q. of Equation (2.3) is close to one column of A. Ge & Ma (2017) proved that for (p((g) there is no spurious local minimizer below a sublevel set whose measure over S geometrically shrinks w.r.t. the dimension n, and without providing valid initialization into the set. Therefore, the challenge still remains: can simple descent methods solve the nonconvex objective Equation (2.3) to global optimality? In this work, we show that the answer is affirmative. Under proper assumptions, show that objective actually has benign global geometric structure, explaining why descent methods with random initialization solve the problem to the target solutions.
2.3 GEOMETRIC ANALYSIS OF NONCONVEX OPTIMIZATION LANDSCAPE
To characterize the landscape of (pD over the sphere 5n-1, let us first introduce some basic tools from Riemannian optimization (Absil et al., 2009a). For any function f gn-1 - R. we have
grad g(g)
P v()))
Hess f(g) Pa 2 f(g) (g. v.(g)) Pa-
4

---

Published as a conference paper at ICLR 2020
to be the Riemannian gradient and Hessian' of fq)). In addition, we partition g" into two regions
RN = ( -" (p)(g) > -DDL 2/ |5(
(2.7)
Rc = - Sn-1 (p(()) < -DD ((()))
(2.8)
for some fixed numerical constant EDL > Unlike the approach in Sun et al. (2016a), our partition and landscape analysis based on function value (g(()) instead of target solutions. This is because in overcomplete case the optimization landscape is more irregular compared to that of the complete/orthogonal case, which introduces extra difficulties for explicit partition of the sphere. In particular, for each region we show the following results.
Theorem 2.3 (Global geometry of nonconvex landscape for ODL) Suppose we have
K m/n, 0 E (m-,,3-²), ŞDL 2
(0,40
(2.9)
and assume AX such that A and X satisfy Assumption 2.1 and Assumption 2.2, respectively. 1. (Negative curvature in Rx) W.h.p. over the randomness of X, whenever
p 3 COK* log(On/1 and K <<3. (1 (1+ + 6LDL, 2/5
any point E RN exhibits negative curvature in the sense that
3 e gn-1 s.t. v Hess (Q)( & -3 14l IICll
2. (No bad critical points in Re) W.h.p. over the randomness of X, whenever
> COKS max {ur Kn²) n² log(On/p) and < 2.2./.
every critical point qe of (p)((g) in Re is either strict saddle point that exhibits negative curvature for descent, or it is near one of the target solutions (e.g. a1) such that
ge) 2 1 1-5Ept.
Here C > O is universal constant.
Remark 2. A combination of our geometric analysis for both regions provides the first global geometric analysis for ODL with O(1), which implies that (QL((q) has no spurious local minimizers over S"-1; any critical point is either strict saddle point that can be efficiently escaped, or it near one of the target solutions. Moreover, recent results show that nonconvex problems with this type of optimization landscapes be solved to optimal solutions by using (noisy) gradient descent methods with random initializations (Lee et al., 2016; Jin et al., 2017; Lee et al.; Criscitiello & Boumal, 2019). In addition, we point several limitations of our result for future work.
As we have only characterized properties of critical points, our result does not directly lead to convergence rate for descent methods. To show polynomial-time convergence, as suggested by Sun et al. (2016a; 2018); Li & Bresler (2018); Kuo et al. (2019), we need finer partitions of the sphere and uniform controls of derivatives in each region". We leave this for future work.
Our analysis in RN says that when j is sufficiently small the maximum overcompleteness K allowed is roughly = 3, which is smaller than that of Re (which could be a large constant). We believe this is mainly due to loose bounds for controlling norms of A in Re. Moreover, our experiment result in Section 4 suggests that there is a substantial gap of K between our theory and practice: the phase transition in Figure 3a shows that gradient descent with random initialization works even in the regime m & n² We leave improvement of our result as an open question.
"The Riemannian derivatives are similar to ordinary derivatives in Euclidean space, but they are defined in the tangent space of the manifold M g--1, We refer readers to Absil et al. (2009a) for more details. *Our preliminary investigation indicates that our premature analysis not tight enough to achieve this. From Remark 1, for typical A, we expect e Ō(nK)) -1/2) be diminishing w.r.t. n.
5

---

Published as a conference paper at ICLR 2020
Brief sketch of analysis. From Equation (2.4), we know that (DD((q) reduces to (p)(q) in large sample limit as - :0. This suggests an expectation and concentration type of analysis: (i) we first characterize critical points and negative curvature for the deterministic function (Pr in Re and RN (see Appendix B); (íi) for any small & > O, we show the measure concentrates in the sense that
for finitely large > 12 (poly")))
sup llgrad ( - grad pr(4))l & 6,
sup Hess (DL(() Hess (pr < 6 988e-1
qe8
holds w.h.p. over the randomness of X. Thus we can turn our analysis of (T(()) to that of (DL(( by perturbation analysis (see Appendix C & D). Here, should be noticed that grad (or (g) and Hess PDL (g) are 4th-order polynomials of X, which are heavy-tailed empirical processes over q 8 To control suprema heavy-tailed processes. we developed a general truncation and concentration type of analysis similar to Zhang et al. (2018); Zhai et al. (2019), so that we can utilize classical bounds for sub-exponential random variables (Boucheron al., 2013) (see Appendix F).
CONVOLUTIONAL DICTIONARY LEARNING
3.1 PROBLEM FORMULATION
Recall from Section 1, the basic task of CDL is that given convolutional measurements in the form of Equation (1.2), ODL, we generalize our analysis from Section 2.3 to CDL with a few new ingredients.
recover kernels {aox ) --1 Here, by reformulating" CDL in the form of
K
Reduction from CDL to ODL. For any E R", let C2 _= be the circulant matrix generated from z. From Equation (1.2), the properties of circulant matrix imply that
Cyp
CSK 2km1
Caoi Czys
Ao
X;
leiEp.
R=1
with Ao =
[Cao Caoa Caox and X;
[
CT C I so that
Ao E RaxnK is overcomplete and structured. Thus, contencating all Cy., we have
C y
Cy
Cy.
Ao
X
X
Xp]
Y Ao. X.
YERuxuP
XepaXxap
This suggests that view the CDL problem ODL: if we recover column of the overcomplete dictionary Ag, we find one the filters auk (1 & & K) up to a circulant shift!!
Nonconvex problem formulation and preconditioning. To solve CDL, one may consider the same objective Equation (2.3) as ODL. However, for many applications our structured dictionary Ao could be badly conditioned and not tight frame, which results in bad optimization landscape and even spurious local minimizers. To deal with this issue, we whiten our data Y by preconditioning"
PY = PA,X, P = [(KK3pp) YY
1/2
(3.1)
For large p. we approximately have (K-1 Ag -1/2 A01 (see Appendix E.5), so that
A = (K- A04,) 1/2 Ao:
PY where A is automatically tight frame with K AAA I. This suggests to consider
Ao X A.X. X,
min (CDL(() := CCDL np
q [P
s.t.
|gl12
1,
(3.2)
Simimiarr formulation ideas also appeared in (Huang & Anandkumar, 2015) with no theoretical guarantces. 1Te CDL problem exhibits shift symmetry in the sense that aok @ a. = Se [aos] @s.2 [mu]. where se [-] a circulant operator by length This implies we can only hope to solve CDI up to shift ambiguity.
Again, the 0 here is only for normalization purpose, which does not affect optimization landscape. Similar
P is also considered in Sun (2016a); Zhang al. (2018); Qu al. (2019).

---

Published as a conference paper at ICLR 2020
Algorithm 1 Finding one filter with data-driven initialization
Input: data Y Ruxp
Output: an esimated filter a. preconditioning. Cook up the preconditioning matrix P in Equation (3.1).
2: initialization. Initialize Ginit Pgg- (Py:) with random sample ye, 1 & 8 &
3: optimization with escaping saddle points. Optimize Equation (3.2) to local minimizer q., by using descent method such as Goldfarb et al. (2017) that escapes strict saddle points.
4: return an estimated filter a, = Pg.-1 (P-tq.). q.).
for some normalizing constant CCDL > O, so that is close to optimizing
(g)
CCDL
1 AX
(PDL(())
ni
for tight frame dictionary A (we make this rigorous in Appendix E.4). To study the problem, we make assumptions on the sparse signals Fik s.id (G) similar Assumption 2.2. Furthermore, we assume Ao and A satisfy the following properties which serve counterparts to Assumption 2.1.
Assumption 3.1 (Properties of Ao and A) We assume the filter matrix Ao has minimun singular value O minn (Ao) > with bounded condition number ro, Ao)) = Fmax (Ao) J (Ao). (Ao)) addition,
we assume the columns of A are mutually incoherent: max44j
aa μ.
3.2 GEOMETRIC ANALYSIS AND NONCONVEX OPTIMIZATION
Optimization landscape for CDL. We characterize the geometric structure of (CDL( over
RCDL = {q g--1 (T(()) & -CCDL 122/3 (Ao) (5()))3
(3.3)
for some fixed numerical constant {CDL > 0, where ((g) = A q and (p(()) -4- -4- as introduced in Equation (2.4). We show (CDDL(q) satisfies the following properties.
Theorem 3.2 (Local geometry of nonconvex landscape for CDL) Let us denote m == Kn, and let C and 17 2-6 be some positive constants. Suppose we have
θ E (m (m-1,3')).
ÊCDL = Co 2/3
P E (0, 40.40% (),40"),
and assume that Assumption 3.1 and Iik wisdd. (G( hold. There exists some constant C > 0, w.h.p. over the randomness of wass whenever
KKO 1 o (Ao) n log (n/Hm) and K < Co.
p M COK2 69K2pp221 2 max
every critical point qe in REDL is either strict saddle point that exhibits negative curvature for descent, or it is near one of the target solutions (e.g. a1) such that (a1/ |ail qo) 1 5x 2n.
The analysis is similar to that of ODL in Re (see Appendix D). In contrast, our sample complexity and RCDL have extra dependence k( Ao) due to preconditioning in Equation (3.1). On the other hand, because our preconditioned dictionary is tight frame but not necessarily UNTF, in the worst case cannot exclude existence of spurious local minima in REDL n for CDL.
Remark 3.
From geometry to optimization. Nonetheless, Algorithm 1 we propose simple data-driven initialization qinit such that quiit RRDDL- Since REDI does not have bad local minimizers, by proving that all iterates stay within RODL. it suffices to show global convergence of Algorithm We initialize q by randomly picking preconditioned data sample Pye with E [p], and set
Ginit = P (Pyr), s.t. Sinit A Ginit VKP (A Awz)
(3.4)
For generic A, small p( () implies that A A close to diagonal matrix 13 that Çinit is spiky for sparse æe. Therefore, we expect large [Smit and qmit E RCDL by leveraging sparsity ay.
This because the off diagonal entries bounded roughly by VKps, which are tiny when is small.
7

---

Published as a conference paper at ICLR 2020
6.5
0.2
Utaio Altres
0.0
Ingal (w))
Filter
0.4
15
(og
21
2.7
600
1000
1000
2000
2000
3000
0.2
Youn MW
(a) Asymptotic ODL: Phase transition. (b) Asymptotic ODL: Recover full A.
-02
Beoner Fechabiigg
0.8
(b) Filter
0.2
04
0.2
0.2
0.
50
10
0.5
2.5
3.5
0.1
0.3
0.4
0.5
0.8
(c) Filter
(c) ODL: Recovery probability vs. p.
(d) ODL: Recovery probability vs.
Figure CDL Simulation.
Parameters: 64, 0 - 0.1,
Figure 3: Simulations for ODL. (a) 0.1; (b)
64: (c)
64,0
K = 3, = 10
0.1: (d) m 3n, p = x 10*.
Proposition 3.3 (Convergence of Algorithm 1 to target solutions) log m
With m Kn, suppose
14 2/3
1///3
Ky
min
(3.5)
m/33 log
(14/3'
m2 log m
W.h.p. over the randomness of DASS, whenever
p > COK2 max RK ( (Ao), n} log (m/H),
we have quiit E RCDL, and all future iterates of Algorithm I stay within REDI, and converge to an approximate solution (e.g., some circulant shift se [aoi] of aok with 1 & n) the sense that
P (P-'q.) st [aoi]]]
<
where is small numerical constant. Here, CI, C2, C> O are some numerical constants.
Remark 4. Our result (Equation (3.5)) suggests that there a tradeoff between μ and for optimization. For generic filters (e.g. drawn uniformly from the sphere), approximately have J ((m-1/2) and к O(1), that our theory suggests the maximum sparsity allowed is Õ(m 2/3). For other smoother filters which may have larger and K, the sparsity allowed tends to be smaller. Improving Equation (3.5) is the subject of future work. On the other hand, result guarantees convergence to an approximate solution of constant error. We left exact recovery for future work. Finally, although write CDL in the matrix- vector form, the optimization could be implemented very efficiently using fast Fourier transform (FFT) (see Appendix G).
4 EXPERIMENTS
In this section, we experimentally demonstrate our proposed formulation and approach for ODL and CDL. We solve our nonconvex problems in Equation (2.3) and Equation (3.2) using optimization 15 with random initializations introduced in Appendix G.
"See Figure of Zhang (2018) for an illustration of these estimations.
For simplicity, power method (see Algorithm 3) for optimizing without tuning step sizes. In practice, find both power method and Riemannian gradient descent have similar performance.
8

---

Published as a conference paper at ICLR 2020
Experiments ODL. We generate data Y AX, with dictionary A E Rax being UNTF's and sparse code X E Rmxp i.i.d. (0). To judge the success recovery of one column of A, let
min (1 - Kg., a:/ |a: I>) 1m
Pe
We have P. when q. Ppa- (a:), thus we assume a recovery successful if pe < 5 x 10-2 Overcompleteness. First, we fix 9 0.1. and test the limit of the overeompleteness K m/n we can achieve by plotting the phase transition on (m, n2) in log scale. To get rid of the influence of sample complexity p. we run our algorithm on 4PT (g) which the sample limit of (D). For each pair of (m, n),, we repeat the experiment for 12 times. As shown in Figure 3a, it suggests that the limit of overcompleteness roughly m & n², which is much larger than our theory predicts. Recovering full matrix A. Second, although our theory only guarantees recovery of one column of A, Figure 3b suggests that we can recover the full dictionary A by repetitive independent trials. As the result shows, O log m) independent runs suffice to recover the full A.
Recovery with varying & and p. Our simulation in Figure 3e implies that we need more samples when the overcompleteness K increases. Meanwhile, Figure 3d shows successful recovery even when sparsity 0 s 0.3. The maximum seems to remain as a constant when n increases.
Experiments CDL. Finally, for CDL,, generate measurement according Equation (1.2) with K 3, where the filters {aoz]a_1 are drawn uniformly from the sphere g--1, and Zi "... (G).). Figure 4 shows that our method can approximately recover all the filters by running a few number of repetitive independent trials.
CONCLUSION AND DISCUSSION
In this work, we showed that nonconvex landscapes of overcomplete representation learning also possess benign geometric structures. In particular, by reducing the problem to an E optimization problem over the sphere, critical point is either an approximate solution or a saddle point can be efficiently escaped. Moreover, showed that this type of analysis to the first provable method for solving CDL globally. Our results have opened several interesting questions that are worth of further investigations, that we discuss as follows.
proved that ODL has no spurious local minimizers globally: every
be carried over CDL with a few new ingredients, leading
Tighter bound on overcompleteness for ODL. As shown in Theorem 2.3, our bound on the overcompleteness K m/nn is absolute constant, which we believe is far from tight (see experiments in Figure 3a). In the high overcompleteness regime (e.g.. n < m & n²), one conjecture that spurious local minimizer does exist but descent methods with random initializations implicitly regularizes itself such that bad regions are automatically avoided Ma et al. (2017); another conjecture that there is actually no spurious local minimizers. We tend to believe the latter conjecture is true. Indeed, the looseness of our analysis appears in the region R (see Appendix B.2), for controlling the norms of A.
One idea might be to consider i.i.d. Gaussian dictionary instead of the deterministic incoherent dictionary A, and use probabilistic analysis instead of the worst-case deterministic analysis. However, our preliminary analysis suggests that elementary concentration tools for Gaussian empirical processes are not sufficient to achieve this goal. More advanced probabilistic tools might be needed here.
Another idea that might be promising is to leverage more advanced tools such as the sum of squares (SoS) techniques Lasserre (2001); Blekherman et al. (2012). Previous results Barak et al. (2015); Ma et al. (2016); Hopkins et al. (2015) used SoS while the computational complexity is often quasi-poly guasi-polynomial and hence cannot handle problems of large-scale. In contrast, our idea here is landscape instead of computation, to have a better uniform control of the negative curvature in Rx- If we succeeded, this might lead tighter bound on the overcompleteness. Moreover, analogous to building dual certificates for convex relaxations such as compressive sensing Candès & Wakin (2008); Candes & Plan (2011) and matrix completion Candès & Recht (2009); Candès al. (201 I), it could potentially lead to a more general approach for verifying benign geometry structures for nonconvex optimization.
computational tool for solving this type of problems,
SoS verify the geometric structure of the optimizing
16e UNTF dictionary is generated by Tropp et al. (2005): from A altemate between preconditioning the matrix and normalize the columns until convergence.
(i) generate standard Gaussian matrix Ag, (ii)

---

Published as a conference paper at ICLR 2020
Composition rules for nonconvex optimization? Another interesting phenomenon found through understanding ODL is that under certain scenarios the benign nonconvex geometry can be preserved under nonnegative addition. Indeed, if we separate our dictionary A into several AN]. then the asymptotic version of nonconvex objective for ODL (Equation (2.3)) can be rewritten
subdictionaries as A [A1
pr(() - 1T Σ (l(g)
( == - ( (5.1)
Presumably, every function (q) also possess benign geometry for each submatrix As. This discovery might suggest more general properties in nonconvex optimization - benign geometry structures be preserved under certain composition rules. Analogous the study of convex functions Boyd & Vandenberghe (2004), discovering composition rules can potentially lead to simpler analytical tools for studying nonconvex optimization problems and hence have broad impacts.
Finding all components over Stiefel or Oblique manifolds. The nonconvex formulations consid- ered in this work is only guaranteed to recover one column/filter at a time for ODL/CDL. Although our experimental results in Section 4 implies that the full dictionary or all the filters can be recovered by using repetitive independent trials, is more desirable to have formulation that can recover the whole dictionary/filters in one shot. This requires to consider optimization problems constraint over more complicated manifolds rather than the sphere, such as Stiefel and Oblique manifolds Absil et al. (2009a). Despite of recent empirical evidences Lau et al. (2019); Li et al. (2019) and study of local geometry Zhai et al. (2019); Zhu et al. (2019), more technical tools need to be developed towards better understandings for nonconvex problems constraint over these more complicated manifolds.
Miscellaneous. Finally, we summarize several small questions that might be also worth of pursuing.
Exact recovery. Our results only lead to approximate recovery of the target solutions. To obtain exact solutions, one might need to consider similar rounding steps introduced in Qu et al. (2016); Sun et al. (2016b); Qu et al. (2019).
Designing better loss functions. The Ed objective we considered here for ODL and CDL heavy-tailed for sub-Gaussian random variables, resulting in bad sample complexity and large approximation error. It would be nice to design better loss functions that also promotes spikiness of the solutions.
Non-asymptotic convergence for descent methods. Unlike the results in Sun et al. (2016a;0) Kuo et al. (2019), our geometric analysis here does not directly lead non-asymptotic convergence guarantees of any descent methods to global minimizers. This is because we only characterized the geometric properties of critical points on the function landscape. To show non-asymptotic con- vergence of methods introduced in Appendix G, we need to uniformly characterize the geometric properties over the sphere.
Finer models for CDL, Finally, for CDL, it is worth noting that in many cases the length of the filters {aut) ) is often much shorter than the observations {yr)²_ Zhang et al. (2017); Kuo et al. (2019); Zhang et al. 8); Lau et al. (2019), which has not been considered in this work. The extra structure leads the so-called short-and-sparse CDL Lau al. (2019), where the lower dimensional model can lead to fewer samples for recovery. Based on our results, we believe the short structure can be dealt with by developing finer analysis such that in Kuo et al. (2019).
ACKNOWLEDGEMENT
Part of this work was done when QQ and YXZ were at Columbia University. QQ thanks the generous support of the Microsoft graduate research fellowship and Moore-Sloan fellowship. XL would like to 142106177 from the Hong Kong Research Grants Council. YQZ is grateful to be supported by NSF award I 170822. ZZ was partly supported by NSF Grant 1704458. The authors would like to thank Joan Bruna (NYU Courant), Yuxin Chen (Princeton University). Lijun Ding (Cornell University), Han-wen Kuo (Columbia University), Shuyang Ling (NYU Shanghai). Yi Ma (UC Berkeley), Ju Sun (University of Minnesota, Twin Cities). René Vidal (Johns Hopkins University), and John Wright (Columbia University) for helpful discussions and inputs regarding this work.
acknowledge the support by Grant
10

---

Published as a conference paper at ICLR 2020
REFERENCES
P-A Absil, Robert Mahony, and Rodolphe Sepulchre. Optimization algorithums on matrix manifolds. Princeton University Press, 2009a.
Pierre-Antoine, Absil, Christopher G. Baker, and Kyle A. Gallivan. Trust-region methods on Riemannian manifolds. Foundations of Computational Mathematics, 7(3):033 -30, 2007.
Pierre-Antoima Absil, Robert Mahoney, and Rodolphe Sepulchre. Optimization Algorithms on Matrix Manifolds. Princeton University Press, 2009b.
Alekh Agarwal, Animashree Anandkumar, Prateck Jain, and Praneeth Netrapalli. Learning sparsely used overcomplete dictionaries via alternating minimization. SIAM Journal on Optinization, 26411)77777 2016.
Michal Aharon, Michael Elad, and Alfred Bruckstein. K-svd: An algorithm for designing overcomplete dictionaries for sparse representation. IEEE Transactions on signal processing. 54(1 1):431--22,, 2006.
Animashree Anandkumar, Rong Ge. and Majid Janzamin. Analyzing tensor power method dynamics in overcomplete regime. The Journal of Machine Learning Research, 18(1):752-79, 2017.
Sanjeev Arora, Rong Ge, Tengyu Ma, and Ankur Moitra. Simple, efficient, and neural algorithms for sparse coding. Journal of Machine Learning Research, 40(2015), 2015.
Yu Bai, Qijia Jiang, and Ju Sun. Subgradient descent Icarns orthogonal dictionarics. arXiv preprint arXiv: 17881011702,. 2018.
Boaz Barak, Jonathan Kelner, and David Steurer. Dictionary learning and tensor decomposition via oum-of-squaree method. In Proceedings of the sevtn-seventh annual ACM symposium on Theory of computing. pp. 143- 151. ACM, 2015.
Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE transactions on pattern analysis and machine intelligence, 35(8):1998-1826, 2013.
Grigoriy Blekherman, Pablo A Parrilo, and Rekha R Thomas. Semidefinite optimization and convex algebraic geometry. STAM, 2012.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymptotic theory of independence. Oxford university press, 2013.
Nicolas Boumal, Pierre-Antoine Absil, and Coralia Cartis. Global rates of convergence for nonconvex optimiza- tion manifolds. IMA Journal of Numerical Analysis, 39(1):1-33, 2018
Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Hilton Bristow, Anders Eriksson, and Simon Lucey. Fast convolutional sparse coding. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 391-398, 2013.
Emmanuel J Candes and Yaniv Plan. probabilistic and ripless theory of compressed sensing. IEEE transactions on information theory, 57(11):7235 7254, 2011.
Emmanuel Candès and Benjamin Recht. Exact matrix complction via convex optimization. Foundations of Computational mathematics, (6):717, 2009.
Emmanuel Candès and Michael Wakin. An introduction compressive sampling la sensing/sampling
paradigm that goes against the common knowledge data acquisition]. IEEE signal processing magazine, 25(2):21 30, 2008.
Emmanuel J Candès, Xiaodong Li, Yi Ma, and John Wright. Robust principal component analysis? Journal of the ACM (JACM). 58(3):1,, 2011.
Niladri Chatterji and Peter L Bartltt. Alternatigg minimization for dictionary learning with random initialization. In Advances in Neural Information Processing Systems, pp. 1997-2006, 2017.
Scott Shaobing Chen, David L Donoho, and Michael A Saunders. Atomic decomposition by basis pursuit. SIAM review, 43(1):129-159, 2001.
C. Criscitiello and N. Boumal. Ffficiently escaping saddle points manifolds. In To appear in the proceedings of NewrlPS, 2019.
11

---

Published as a conference paper at ICLR 2020
Laurent Demanet and Paul Hand. Scaling law for recovering the sparsest element in subspace. Information and Inference: Journal of the IMA, 3(4):295-308) 2014.
Michael Flad. Sparse and redundant representations: from theory to applications signal and image processing. Springer Science & Business Media, 2010.
Simon Foucart and Holger Rauhut. An invitation compressive sensing. A mathematical introduction to compressive sensing, pp. 1-39. Springer, 2013a.
Simon Foucart and Holger Rauhut. A Mathematical Introduction Compressive Sensing. Springer, 2013b.
Cristina Carcia-Cardona and Brendt Wohlberg. Convolutional dictionary learning: A comparative review and new algorithms. IEEE Transactions on Computational Imaging, 4(3):366-311, 2018.
Rong Ge and Tengyu Ma. On the optimization landscape of tensor decompositions. In Advances Neural Information Processing Systems, pp. 3653-3663, 2017.
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points online stochastic gradient for tensor decomposition. Proceedings of The 28th Conference on Learning Theory, pp. 797 797-842, 2015.
Quan Geng. Huan Wang, and John Wright. On local correctness of minimization for dictionary learning. 2011.
arXiv preprint
Dar Gilboa, Sam Buchanan, and John Wright. Efficient dictionary learning with dradient descent. International Conference on Machine Learning, pp. 2252-2259, 2019.
Donald Goldfarb, Cun Mu, John Wright, and Chaoxu Zhou, Using negative curvature solving nonlinear programs, Computational Optimization and Applications, 68(3):479-50) -004799-5-22220 2017.
Shuhang Gu, Wangmeng Zuo, Qi Xie, Deyu Meng, Xiangchu Feng, and Lei Zhang. Convolutional sparse coding for image super-resolution. In Proceedings of the IEEE International Conference on Computer Vision, pp. 2015.
Samuel B Hopkins, Jonathan Shi, and David Steurer. Tensor principal component analysis via sum-of-square proofs. In Conference on Learning Theory, pp. 956-1006, 2015.
Furong Huang and Animashree Anandkumar. Convolutional dictionary learning through tensor factorization. In Feature Extraction: Modern Questions and Challenges, pp. 116-129, 2015.
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. How escape saddle points efficiently. Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 1724-1732. JMLR. org, 2017.
Michel Journée, Yurii Nesterov, Peter Richtárik, and Rodolphe Sepulchre. Generalized power method for sparse principal component analysis. Journal of Machine Learning Research, 11(Feb):517-553, 2010.
Han-Wen Kuo, Yuqian Zhang, Yenson Lau, and John Wright. Geometry and symmetry in short-and-spare deconvolution. In International Conference on Machine Learning, pp. 3570-3580, 2019.
Jean B Lasserre. Global optimization with polynomials and the problem of moments. SIAM Journal on optimization, 11(3):796 817, 2001.
Yenson Lau, Qing Qu, Han-Wen Kuo, Pengcheng Zhou, Yuqian Zhang, and John Wright. Short-and-spare deconvolution-a geometric approach. arXiv preprint arXiv:1908. 1 10959, 2019.
Quac Le, Alexandre Karpenko, Jiquan Ngiam, and Andrew Ng. Ica with reconstruction cost for efficient overcomplete feature learning. In Advances in neural information processing systems, pp. 1017-1025, 2011. I.
Honglak Loc, Alexis Battle, Rajat Raina, and Andrew Y Ng. Efficient sparse coding algorithms. In Advances in
neural information processing systems, pp. 801-808, 2007.
Jason D Lee, loannis Panageas, Georgios Piliouras, Max Simchowitz. Michael I Jordan, and Benjamin Recht. First-order methods almost always avoid strict saddle points. Mathematical Programming, pp. 1-27.
Jason D Lee, Max Simchowitz. Michael Jordan, and Benjamin Recht. Gradient descent only converges to minimizers. In Conference on Learning Theory, pp. 1246-1257, 2016.
Michael S Lewicki and Terrence J Sejnowski. Learning nonlinear overcomplete representations for efficient.
coding. In Advances in neural information processing systems, pp. 556-562,, 1998.
12

---

Published as a conference paper at ICLR 2020
Michael Lewicki and Terrence J Sejnowski. Learning overcomplete representations. Neural computation, 12 (2):337-365, 2000.
Xiao Li, Shixiang Chen, Zengde Deng. Qing Qu, Zhihui Zhu, and Authony Man Cho So. Nonsmooth optimization over stiefel manifold: Riemannian subgradient methods. arXiv preprint 191 2019.
Yanjun Li and Yoram Bresler. Global geometry of multichannel sparse blind deconvolution on the sphere. In Advances in Neurul Information Processing Systems, pp. 1132-1143, 2018.
Cong Ma, Kaizheng Wang, Yuejie Chi, and Yuxin Chen. Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval, matrix completion and blind deconvolution. arXiv preprint ar100 2017.
Tengyu Ma, Jonathan Shi, and David Steurer. Polynomial-time tensor decompositions with 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 438 438-446. IEEE, 2016.
In
Julien Mairal, Francis Bach, Jean Ponce, and Guillermo Sapiro. Online learning for matrix factorization and sparse coding. Journal of Machine Learning Research, 1 1J(J))):19660 2010.
Julien Mairal, Francis Bach, Jcan Ponce, et al. Sparse modeling for image and vision processing. Foundations and Trends in Computer Graphics and Vision, 8(2-3):85-283, 2014.
Dustin G Mixon. Unit norm tight frames in finitediimensionll spaces. Finite Frame Theory: A Complete Introduction Overcompletenesx, 93:53, 2016.
Yurii Nesterov and Boris T. Polyak. Cubic regularization of newton method and its global performance. Mathematical Progrumming. 108(1):177-205, 2006.
Bruno Olshausen and David Field. Sparse coding with an overcomplete basis set: A strategy employed by v1? Vision research, 37(23):3311-333 13-3232,, 1997.
Vardan Papyan, Yaniv Romano, and Michael Elad, Convolutional neural networks analyzed via convolutional sparse coding. The Journal of Machine Learning Research, 18(1):2887-299 2017a.
Vardan Papyan, Yaniv Romano, Jeremias Sulam, and Michael Flad. Convolutional dictionary learning via local processing, In Proceedings of the IEEE International Conference on Computer Vision, pp. 5296-5304, 7h.
Vardan Papyan, Yaniv Romano, Jeremias Sulam, and Michael Elad. Theoretical foundations of deep learning via sparse representations: A multilayer sparse model and its connection convolutional neural networks. IEEE Signal Processing Magazine, 35(4):72-89, 2018
Qing Qu, Sun, and John Wright. Finding sparse vector a subspace: Linear sparsity using alternating directions. IEEE Transactions on Information Theory, (2(10):5855-588) 2016.
Qing Qu, Xiao Li, and Zhihui Zhu. A nonconvex approach for exact and efficient multichannel sparse blind deconvolution. arXiv preprint arXiv: 10776, 2019.
Ron Rubinstein, Alfred M Bruckstein, and Michael Flad. Dictionaries for sparse representation modeling. Proceedings of the IEFF, 1045-100) 2010.
Tselil Schramm and David Steurer. Fast and robust tensor decomposition with applications to dictionary lcarning. Proceedings of Machine Learning Research vol, 65:1-34, 2017.
Daniel A. Spielman, Huan Wang, and John Wright. Exact recovery of sparsely-used dictionaries. In Conference on Learning Theory. 2012.
Ju Sun, Qing Qu, and John Wright. Complete dictionary recovery over the sphere. arXiv preprint 10x1v:/504.06785, 2015a.
Ju Sun. Qing Qu, and John Wright, When are nonconvex problems not scary? arXiv preprint 111..05500 2015b.
Ju Sun, Qing Qu, and John Wright. Complete dictionary recovery over the sphere i: Overview and the geometric picture. IEEE Transactions Information Theory, 63(2):833-88) 884, 2016a.
Ju Sun, Qing Qu, and John Wright, Complete dictionary recovery over the sphere ii: Recovery by riemannian trust-region method. IEEE Transactions Information Theory, 63(2)888-914, 2016h.
13

---

Published as a conference paper at ICLR 2020
Ju Sun, Qing Qu, and John Wright. geometric analysis of phase retreival. arXiv preprint arXiv:1602.06664. 2016c.
Ju Sun, Qing Qu, and John Wright. A geometric analysis of phase retrieval. Foundations of Computational Mathematics, 185):1131-1198, 2018.
Mátyás Sustik, Joel A Tropp, Inderjit S Dhillon, and Robert W Heath Jr. On the existence of equiangular tight frames. Linear Algebra and its applications, (26(2-3):619 635, 2007.
Joel A Tropp. Inderjit S Dhillon, Robert W Heath, and Thomas Strohmer. Designing structured tight frames via an alternating projection method. IEEE Transactions on information theory, 51(1):188-200 2005.
Joel A Tropp al. An introduction to matrix concentration incqualities. Foundations and Trendy Machine Learning, 8(1-2)11-25) 2300, 2015.
Lloyd Welch. Lower bounds the maximum correlation of signals (conresp.). IEEE Transactions on Information theory, 20(3):977-39,, 1974.
John Wright, Yi Ma. Julien Mairal, Guillermo Sapiro, Thomas Huang. and Shuicheng Yan. Sparse representa- tion computer vision pattern recognition. Proceedings of the IEEE, 98(6):0031-1044, 2010.
Matthew D Zeiler, Dilip Krishman, Graham W Taylor, and Rob Fergus. Deconvolutional networks. In 2010 IEEE Computer Society Conference on computer vision and pattern recognition, pp. 2528-2535. IEEE, 2010.
Yuexiang Zhai, Zitong Yang, Zhenyu Liao, John Wright, and Yi Ma. Complete dictionary learning via no-morm maximization over the orthogonal group. arXiv preprint arXiv:1906.024: 2019.
Yuqian Zhang, Yenson Lau, Han-wen Kuo, Sky Cheung, Abhay Pasupathy, and John Wright. On the global geometry of sphere-constrained sparse blind deconvolution. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 4894 4902, 2017.
Yuqian Zhang, Han- Wen Kuo, and John Wright. Structured local optima in sparse blind deconvolution. arXiv preprint /806: 00338, 2018.
Zhihui Zhu, Tianyu Ding, Daniel Robinson, Manolis Tsakiris, and René Vidal. lincarly convergent method for non-smooth non-convex optimization on the grassmannian with applications to robust subspace and dictionary learning. In Advunces in Neural Information Processing Systems, pp. 9437-9447, 2019.
14

---

Published as a conference paper at ICLR 2020
APPENDIX
The Appendix is organized as follows. In Appendix A, we introduce the basic notations and technical tools for analysis. Appendix B provides determinsitic characterization of the optimization landscape in population. In Appendix C, we turn our analysis of Appendix into finite sample version. Appendix D and Appendix E provide the detailed proof for ODL and CDL, respectively. The detailed concentration bounds are postponed to Appendix F, Finally, Appendix G provides some ideas of optimization methods.
A NOTATIONS AND BASIC TOOLS
A.1 BASIC NOTATIONS
Throughout this paper, all vectors/matrices are written bold font A; indexed values are written a, Aij. We use S to denote n--dimensional unit sphere in the Euclidean space R", We let [m] = 21,2. .. m... We use + to denote Hadamard product between two vectors/matrices. For v e R", we use or to denote entry-wise power of order i.e., v = [....... . Let n DFT matrix, with [ = /n, and F, n F In
F, E C" denote a unnormalized many cases, we just use F to denote the DFT matrix.
Some basic operators. We use Pv and Pul to denote projections onto e and its orthogonal complement, respectively. We let Ps- to be the (P-normalization operator. To sum up, we have
ve
ve u1| u
P u
U, Pou
Pgn-1U
|
Circular convolution and circulant matrices. The convolution operator + is circular with modulo-m: (a @ x),
-i-0 m- ayTi-j- For v E R let se[u] denote the cyclic shift of with length E. Thus, can introduce the circulant matrix C. R=xx generated through v R=
U1
Um
U3
U2
1/
U1
mm
03
C
U2
V1
- [s [b]
S1 [v]
8m-1 [b]]
(A.1)
Um-1
Um
Um
Um-1
Now the circulant convolution can also be written in simpler matrix-vector product form. For instance, for any u Rmm and v E Rm
C. In addition, the correlation between and can be also written in similar form of convolution operator which reverses one vector before convolution.
Cn U C. uu
Cuga
Basics Riemannian derivatives. Here, we give a brief introduction to manifold optimization over the sphere, and the forms of Riemannian gradient and Hessian. We refer the readers to the book (Absil et al., 2009b) for more backgrounds. Given a point q E S the tangent space T,S" 7 defined as T, s=, {u x q = 0}. Therefore, we have the projection onto TT5"=1 equal Pat. For a function f(q) defined over -1, we use grad f and Hess f to denote the Riemannian gradient and the Hessian of then we have
grad f(g) = Pq- Vf(g),
Hess f(g) = Pgt (v2 - (q. ff(g)) 1) Pgt.
where vf(g) and (²ʃ(g) are the normal first and second derivatives in Euclidean space. For example, for the function (p((g) defined in Equation (2.4), direct calculations give that
(p(() -P A(A
O3 = -
ag q) ak
k-1
Hess (p((g) = -Pal [A ((A
02
A - A g1 Pa
15

---

Published as a conference paper at ICLR 2020
A.2 BASIC TOOLS
Lemma A.I (Norm Inequality) 1fp > r > O, then for x E IR", we have
|alp |,2|, $ 1/- 1///-1/p ||r||p-
Lemma A.2 Let 2, T We have
(1 + 2)r 1 (2" 1)2, V [0 E R((,,),
(1 + 2)" & 1 12,
2 E
[0,1].
where the second inequality reverse when r 10,
Lemma A.3 (Moments the Gaussian Random Variable) If ~ N (0, ox). then it holds for all integer that
E [[
& ox (m 1)!!, k |m/2].
Lemma A.4 (Noncentral moments of the Random Variable) If 7 x xm), then it holds for all integer p 2 that
E | = 20/2 I (p/2 m/2) r (m//2)
& p!! m/2
Lemma A.5 (Bernstein's Inequality for R.V.s (Foucart & Rauhut, 2013b)) Let X Xp be i.i.d. real-valued random variables. Suppose that there exist some positive numbers R and oxx such that
m! 2 Rm= 2 for all integers > 2.
E X
ox
2
Let EP_ Xs. then for all >>> 0, it holds that
pt
P PIS - E [S] t < 2exp
20 2Rt
Lemma A.6 (Bernstein's Inequality for Random Vectors (Sun et al., 2015a)) Let 21,...,, Rd be fi.dd random vectors. Suppose there exist some positive number R and o%x such that
& 2 o Rmm2 for all integers m > 2.
m!
8 = 1 Ek- Tke then for any > 0, holds that
pt²
P[ [ > 1 < 2(d+1)ex)
22x ( 2RI
Lemma A.7 (Bernstein's Inequality for Bounded R.M.s, Theorem 1.6.2 of Tropp et al. (2015))
Let X1,X2 X2, Xxp Rd xd2 be i.i.d. random matrices. Suppose have
| & R almost surely,
max [E E
}
<
2x lei<p
Let 1 E X,, then we have
pt²
P (IS E[S]
3 1) & (d1 + d2) exp
20 4 AR1/3
Lemma A.8 (Bernstein's Inequality for Bounded Random Vectors) Let 21, Ep Bd be i..dd. random vectors. Suppose we have
x < R almost surely,
E
[
< 2x. leiEp
Let $
1 INP Fy then we have
plz -20xx + 4Rt/33
PP P[[s - E [x]]]
2 t) & dexp
16

---

Published as a conference paper at ICLR 2020
Lemma A.9 (Lemma A.4 of (Zhang et al., 2018)) Let (er distribution, then
R with each entry following i.i.d.
3t
P (11lll 8d] t0d) & cxxp
2t + Ad
Lemma A.10 (Matrix Perturbation Bound, Lemma B.12 of (Qu et al., 2019)) Suppose B > positive definite matrix. For any symmetric perturbation matrix A with |
$ 7 (B),
holds that
A
B 1/2 -
oh B
4 A
(B + A) B
3/2
(
min
where (B) denotes the minimum singular value of B.
Lemma A.11 For any q, 91 Q2 E 5 we have
P = P.
P
< 2 92l
Proof
The first is obvious, and for the second inequality we have
a- Pat = 1q:q] u29.l < [qiq]]
9i9.l ll + |/
924d _
< 2 2|q- - qall
as desired.
Lemma A.12 For any nonzero vectors u and v, we have
2
au
|
[
Proof We have
u
||
m/l
[
[||
||al||
|ea||
2
||
ml|
+
|0|||
||
||0||]
22
|00||
2
as desired.
B ANALYSIS OF ASYMPTOTIC OPTIMIZATION LANDSCAPE
In this part of the appendix, we present the detailed analysis of the optimization landscape of the asymptotic objective
min pr(() q
1
AA s.t. q Sn-1
over the sphere. We denote the overcompleteness. of the dictionary A E paxm and the correlation of columns A with q by
K n
((g) A q
1s1
Gm]] G
Without loss of generality, for given q E gn-1 we assume that
16ml-
17

---

Published as a conference paper at ICLR 2020
Assumption.
We assume that the dictionary A is tight frame with e -orm bounded columns
AA
| <
M (1 ( m).
(B.1)
K
We also assume that the columns of satisfy the j-inccherennce condition. Namely, we have
H (A)
max 1ei+jsm
a
a,ll
(0,
(B.2)
such that is sufficiently small. Based on the function value of the objective (p((1), we partition the sphere into two regions
Rc(g:E) { { |
|C > En
|5133
(B.3)
(x( {gESS-L |<| En 1s113]
(B.4)
where ç some scalar. the following, for appropriate choices of K, 14, and &, we first show that Rg does not have any spurious local minimizers by characterizing all the critical points within the region. Second, under more stringent condition that A is Le column normalized, for the region Rx we show that there exhibits large negative curvature throughout the region, such that there is local/global minimizer within Rn.
B.1 GEOMETRIC ANALYSIS OF CRITICAL POINTS IN Rc
In this subsection, we show that all the critical points of (P(()) in Re are either ridable saddle points, or satisfy second-order optimality condition and are close to the target solutions.
Proposition B.1 Suppose we have
KM < -- M < 17 g3/2 5
(B.5)
20
for some constant 1) 2-6 Then any critical point q E Re. with grad (p(()))))))) = 0, either is ridable (strict) saddle point, satisfies second-order optimality condition and is near one of the components e.g., dn in the sense that
||a|||
9
1-
3
=1111
3/2
3 1- 1-57
First, in Appendix B.1.1 we characterize some basic properties of critical points of (p((g). Based on this, we prove Proposition B.1 Appendix B.1.2.
B.1.1 BASIC PROPERTIES OF CRITICAL POINTS
Lemma B.2 (Properties of critical points) For any point q Sh-1, ,, if is critical point of (p((g) over the sphere, then it satisfies
f(Gi) = - 8 = 0
(B.6)
for all i [m] with ((g) = A where
|CIl+
Eatr ag)
0;
B:
(B.7)
a,
|a=s|"
Proof For any point q E gn-1, g is critical point of (p(()) over the sphere, then its Riemannian gradient satisfies
grad (T()) = Pg AÇ O
oç 03 |cl 0.
Multiple a, (1 m) on both sides the equality, we obtain
|| c ICII ç: + Σ
(a,, a,) 23 0.
18

---

Published as a conference paper at ICLR 2020
V9
11
fLVO
/6 V/
va
20
Va
((#)
f(ya
41 vo
Figure 5: Illustration of f() in Equation (B.8) when > 0.
By replacing a, and 3, defined in Equation (B.7) into the equation above, we obtain the necessary condition in Equation (B.6) as desired.
Since the roots of (z) correspond to the critical points of (pr(g), we characterize the properties of the roots as follows.
Lemma B.3 Consider the following cubic polynomial
f12)
az +
(B.8)
with
1
0 18
3/2
0.
(B.9)
Then the roots of the function [(z is contained in one of the nonoverlapping intervals:
2 |3
2 2|
I
R
I
2 R
|a
Val
a
2
Ig
R
2
a
3/2 and a > in Equation (B.9), obvious that the intervals I1, Iz. and I3 nonoverlapping. Without loss of generality. let us assume that 3 is positive. We have
Proof By our construction |:3| < 3/2
f(va) f(-va) f(0) 3 0.
(B.10)
Thus, as illustrated in Figure 5, if we can show that
O, (-va (-va-2) 2,
0, ((va-
23 < 0,
(B.11)
then this together with Equation (B.10) suffices to show that there exists at least one root in each of the three intervals I,, I2, and Zz. Next, we show Equation (B.11) by direct calculations. First, notice that
f (225)
233 a
2,9
3
- B
3
(832 -02)
B (1
3
a²)
1
0,
α
a
a
2
2
Second, we have
f LL 2,9
28
3
28
Va
Va
+
a
a
83
123²
833
12,2
3/2
63
+ 3/2
33
38
23/2
a3/2
Similarly, we have
(vaa
28
833
12.22
8,2
128
833
33
3
+
3
0.
a
3
03/2
3
3/2
a
This proves Equation (B.11). Similar argument also holds for 3 < 0. Thus, obtain the desired results.
19

---

Published as a conference paper at ICLR 2020
B.1.2 GEOMETRIC CHARACTERIZATIONS OF CRITICAL POINTS Re
Based the results in Appendix B.1.1, we prove Proposition B.I, showing that there no spurious local minimizers in Rc-
Proof [Proof of Proposition B.1] First recall from Lemma B.2, defined
K a
Σjfr (ai, a₃) Cj
02
2
>
0,
B
|a,1
Then for any Rc, we have
18
Exji as aj)
azl
nMM |cl
M/5-3/2
(B.12)
3/2
|<l
15l1
where for the first inequality we used the fact that for any i [m], ||
< M and
Σ aa. J
(a.
Σ
aa
max 1s)5m
ayyl
&
pM
= μM² ||
aall
and the last inequality derives from the fact that q RRc- Thus, by Equation (B.5) and Equation (B.12), we obtain
1 4
3 3/2
M
This implies that the condition in Equation (B.9) holds, that can apply Lemma B.3 to char- acterize the critical points. Based on Lemma B.3, we classify critical points E 'Re into three categories
1. All [Gd
& m) smaller than 21d. ax
Only [G1] is larger than 21
At least [[1| and [22] are larger than 2|0.1 and respectively.
2|0a| 0n 0g
For Case 1, Lemma B.4 shows that this type of critical point does not exist under the assumption in Equation (B.5). For Case 2, under the same assumption, Lemma B.5 implies that such a critical point E Re satisfies the second-order optimality condition, and it is near one of the target solution with
01
1 1 55 11-55-8/2
3/2
> 1 1 1-5
|ail
for 1) 2 Finally, for Case 3. Lemma B.6 proves that this type of critical points & Re ridable saddle, for which the Riemannian Hessian exhibits negative eigenvalue. Therefore, the target solutions, that there is spurious critical points in Rg either ridable saddle local minimizer in Rc.
In the following, we provided more detailed analysis for each case.
CASE 1: NO CRITICAL POINTS WITH SMALL ENTRIES.
First, we show by contradiction that if q Re and is a critical points, then there is least one coordinate, e.g., |Ci| > 2|0a1 This implies that Case (i.e., all |cal (1 & i & m) are smaller than 2 is impossible to happen. In other words, this means that any critical point q Re should be close to superpositions of columns of A.
Lemma B.4 Suppose have
M 4/3 K1/3
-1/3g.
If E Re is a critical point, then there exists at least one i [m] such that the entry S. of ((
satisfies
2 2|3
Ical
>
20

---

Published as a conference paper at ICLR 2020
Proof Suppose there exists q Re such that all entries Se satisfying 1sal
2/8:1
Then we have
az
(a,,
as>
Sil
2M 2/12ll
max 1s
Icil
|cl
<
||</|
This implies that
4M* |s11
Icla
ICI2
|C|2
|K<l
4M²
|<|| < 4 1/3 M K1/3 1 ||||
where we used the fact that |c12 K according to Equation (B.1). Thus, by our assumption, we have
g//3/1/3 5/42/3
|Cll
1413 <
This contradicts with the fact that q e Rc.
CASE 2: CRITICAL POINTS NEAR GLOBAL MINIMIZERS
Second, consider the case that there exists only one big St, for which the critical point satisfies second-order optimality and near a true component.
Lemma B.5 Suppose & is sufficiently large such that
M
3322 KM < 4-1 .0/
(B.13)
for some constant 2-6, For any critical point q Re, if there is only one entry in Ç such that <1
2|0:1
a1 |ail|
M > 1- 5n. 55
9
Moreover, such critical point Rg satisfies the second-order optimality condition: for any gn-1 with 1. q
Hess (g)
20
Proof We first show that under assumptions the critical point q Re is target solution. Following this, we prove that also satisfies second-order optimality condition.
Closeness to target solutions. First, if q a critical point such that there is only one Ci > 2011 we show that such q is very close to a true component, By Lemma B.2 and Lemma B.3, we know that (1 needs to be upper bounded by
(vai= + 21311
|
2
2 m (ai, a&) Cil
G &
+
|a
a1
[Cl|
2p S1l la
maxi M [ay)
2
|a
?
KK
By using the fact that q Rc and ||ay||
< M (1 < j < m). we have
a 2
2p | || maxisjem
|| 57 1+
1C11 (1+25-3/2 1511 (B.14)
21

---

Published as a conference paper at ICLR 2020
On the other hand, by using the fact that [Sx|
2|0kl an
for all & > 2. we have
m
4
|32 az
|K| 1 4u² |15 KMr
ct
2 |c
4
|cll
K
IslI
|| (1 -1-45 K
(B.15)
Combining the lower and upper bounds in Equation (B.14) and Equation (B.15), we obtain
G
1-45-$KM
(1- (1-45-8KM²
a1
9
21+
1+ 6f 3
1 3 M3 (3E 22MM
2 1 - 8 3/2 M - 81),
where the second inequality follows by Lemma A.2, and the last inequality follows from Equa- tion (B.13). This further gives
a [a
q
3/2 8/-3/2
88
M
1 -32 M
1 4 33/2 = 1 55
55-3/2
3/2 > 57.. (B.16)
M/3 1/2
Second-order optimality condition. Second, check the second order optimality condition for the critical point. Let E gn-1 be any vector such that v 1. q. then
v Hess pp(4)v = -3v T diag 02
A T v + |c1
3 m
akk 8)² 22 + |sl
-3 2 322 A u|]" + +lS
= -3 0)² G 3K3 ||<|
(B.17)
Next, we control u) ot and K22 in terms of ||5 respectively. By Equation (B.14) and (q, v) 0,
2
(0,, 2). S
a1
(lai (1ai1?<?)
=
q. v
01
q
2
1
+ 25
3/2 3/2 2 1c1/
[1
||
2
a1
q )) (1 [+ 2$ 3/2 3/-33///// M2) 3/3))
1cl1
[ail
(1 2 3/2 MD) 2 1cl/ &
< 10g 3/2 M
4 |c
(B.18)
On the other hand, for q Re, using Equation (B.13) we have
KC K 2
4K n22 Icl
1
4KM*5
(B.19)
12
15
Thus, combining the results in Equation (B.17), Equation (B., and Equation (B.19), obtain
(1
1
Hess ( >
>
151
4
5
20
This completes our proof.
22

---

Published as a conference paper at ICLR 2020
CASE 3: CRITICAL POINTS ARE RIDABLE SADDLES.
Finally, we consider the critical points q e Re that at least two entries [Si| and [S2l larger than 2 and 2|0a| respectively. For this type of critical points Rc, we show that they are ridable saddle points: the Hessian is nondegenerate and exhibits negative eigenvalues.
Lemma B.6 Suppose we have
1
M 17 (3/2
11
(B.20)
20
for some constant
< 2-6 For any critical point q Ro. if there are at least two entries in ((q) such that [ca] 2|3:1 (i E [m]], then q is strict saddle point: there exists some S with
a;
1 q, such that
v Hess (q))) & - -151
Proof Without loss of generality, for any critical point q Re, we assume that Çi al q and
C a. q are the two largest entries in ((g). We pick vector span |ail [
such that
1 with v gm-1 Thus.
Hess pp(()) -3v' TTA A diag (5
T v +
Icl1
2
2
-3 |a1l 7
|a2l
a2
v
+
|ClI
a1
a2
Since 16 >=
2| and [C2] 2
2/ by Lemma B.2, Lemma B.3, and the fact that E Re, we have
2 2
2
1 2nM
|1 ||al||
|a G
|
Vai
|cll
a1
1<
1 - 25 3/2 2M)
|C
In the same vein, we can also show that
1 2 > (1 2 3/2 MM3
Therefore, combining the results above, we obtain
Hess (p(()) 1cl
1 3 (1-23 28 25-560 3/2 (1-25-3/211)) 2))
+
a
a2
As v E span
ai |a:]
a2 |aæ||
we can write
01
a2
02
a1
a22
for some coefficients C1, E R. u sn-1 we observe
||all2
of + oz
20
|ail"
|a2
o7 + 2
1
-
222eg022/ 2 1 - 4p,
where the last inequality follows from Lemma B.7. Thus, we observe
2
))
2
a
a2
a
a2
a
a2
C1 02
aa
[22l|
+
c2
+
|ail
a2
(cf + og) + (cf + +g))
a
a2
+
4c102
a |ai
a2
||
|
|g
P
4u - (1 4p) 11
4
1
4
10pz
23

---

Published as a conference paper at ICLR 2020
By the fact in Equation (B.20) and combining all the bounds above obtain
1 - 3 (1 (1-25 25 22-) 2 (1 10110000/0 1IS E -1 1511
1 Hess pr( &
This completes the proof.
Lemma B.7 Suppose
& with < 1/2. Let span
a [ai]
such that
|ai
|ail
|
|||| and c
a2 |aal'
then we have
1
c202
1 n
Proof By the fact that
(v,
Taal
a1
v
d2
$ 1, we have
Ma
+
a1
02
a1
02
C2
C2 + c1
1,
|q1
[2
[1
a2
which further implies that
2
c102 c + (G
a1
a2
C102
a1
22
1.
an
[a2]
a
a2
Since |o|| 1, we also have
+ = - 20
a1
a2
||a
a2
Combining the two (in)equalities above, we obtain
Q1
Q2
a1
22
1
>>
C1
+
C102
[ail
[2
[ai]
[2
> |ci02|
a
a2
2
-
a
a2
>
|c102|
(1 (1- -²)
a
a2
Thus, obtain the desired result.
B.2 NEGATIVE CURVATURE IN RN
Finally, make more stringent assumption on A that each column of is l normalized. i.c.,
|a
1, 1 < < m.
We show that the function (p)(g) exhibits negative curvature in the region Rx Namely, the Rieman- nian Hessian for any points q Ry has a negative eigenvalue, such that the Hessian is negative in certain direction.
Lemma B.8 Suppose each column of 2 normalized and
K & 3 For any point q E Ry, there exists some direction d S such that
[1 (1
6p + 6g (,23/5,,/8)) -1
d Hess (r -4 ||[]] 1s12
24

---

Published as a conference paper at ICLR 2020
Proof By definition, we have
a Hess p
3a - P. diag (5 A PA aq a1 KC1 P 1
3a A diag (5 A a1 + 61|51l 5" diag (5 A a1 - -311 |1cl |<ll (1a1l) - |1c11
I<l ||i1| + +6<4 |aill + |S| - I11 Icl IK]l
|<ll + 6 + 6 1[1] - 4 4 |<ll + +|<|
< ||<|| x (-3+ 61<4 -
I<1?))
||<| x
(33 6 6| + 6uK - 4 + K)
where for the second inequality used the fact that |Cll |5| Icl and for the last equality applicd that |||] q' AA q = K. Moreover, as E Rx. we have
| < ||<112 $
$2/2 p//3 |4l|a
1/3
Ik513 = |sal
<
1clb K1/3
Thus, obtain
15 & 52/2 1/3 |K 1/3 K1/3
1<l2 < 53/5 (HK))/1.
Hence, we have
a Hess (q)a)) & ||S1 (-3 3 + 653/5 (nK)215 + 6uK - 4 |15511 + K) & 11
whenever
K & 3 (1 6p 6 65 6,53//1115)
Thus, we obtain the desired result.
C OPTIMIZATION LANDSCAPE IN FINITE SAMPLE
In this section. will show that the finite sample objective functions in the overcomplete dictionary learning and convolutional dictionary learning have similar geometric properties as (q) = - & ||A al); analyzed in Appendix B. Specifically, we will analyze the geometric properties of objective function (lq)) (which could be (g) and (g))(g)) whose gradient and Hessian are close to (q)).. We denote by
(g) grad p(g) grad ypT (4), A # (q) := Hess ppq) - Hess upr(4),
(C.1)
both of which will be proved to be small for overcomplete dictionary learning and convolutional dictionary learning in Appendix F.
C.I GEOMETRIC ANALYSIS OF CRITICAL POINTS IN Re
Proposition C.1 Assume
[[8,(4)] & pM |cli and |Ax(g))
Also suppose we have
KM 8- 2322 M < 2n 8/22
(C.2)
20
25

---

Published as a conference paper at ICLR 2020
for some constant 7) < 2 Then any critical point q Rc, with g(q) O. either is ridable (strict) saddle point, or satisfies second-order optimality condition and is near one of the components e.g., ai in the sense that
01
1- 11-55--
55-3/2M²
> 1 - -57.
(C.3)
|a
Proof [Proof Proposition C.I] With the same argument in Lemma B.2, we have that any critical point q gm-1 satisfies
S(Gi) = C. - + 8 = 0,
for all ie [m] with Ç = Alg. where
K<|
B (6g(g), a.) + Ejti (ai, ag) (3
B,+ (og(g), a.)
a;
|aa 2'
|a,1
|a,1"
(C.4)
E, a
with 3.
which is defined equation B.7.
|a.1*
Recall that widely used upper bound for 3 in Appendix B.I is:
|8 شigee (a, (a.aa)) C)
n. |cll [a
|ail1
which together with [x)( μM ||<| gives
(g(()) a.)
uu Icl
8' B +
(C.5)
|ai||
To easily utilize the proofs in Appendix B.I, we define ç = 2 2-2/3g such that 3/2 2 3/2 Plugging the assumption 3 < into equation C.5, we have
|
H.M
KK 3 1 |a,1|
HMM Icl & 2M---33 3/2
2M &
3/2
K
1412
O2
This implies that the condition in equation B.9 holds, so that we can apply Lemma B.3 based on which we classify critical points E Re into three categories
All |S/| (1 & i & m) are smaller than 2/1
a,
Only |Ci| is larger than 2| a:
At least [Gi| and K2] are larger than 2/1 and
2/0
respectively.
For Case 1, using the same argument in Lemma B.4 can easily show that this type of critical point does not exist. For Case 2, with the same argument as in Lemma B.5, we obtain that such critical point is
of the target solution with
> 1 1- 55 > 1 - 51,,
and satisfies the second-order optimality condition, i.e., for any 5n with 1 q. have
Hess v(q)v > T Hess (q(()) (q)
|cl - A
20
Finally, for Case 3, with the same v constructed in Lemma B.6 and using the assumption || |r)l <
20 |[|l we have
v Hess < u Hess p (q)v + (g)
+ <0
indicating that this type of critical points g Re is ridable saddle, for which the Riemannian Hessian exhibits negative eigenvalue. Therefore, the critical points in Re are either ridable saddle or near target solutions, so that there is no spurious local minimizer in Re-
26

---

Published as a conference paper at ICLR 2020
C.2 NEGATIVE CURVATURE IN RN
By directly using Lemma B.8, we obtain the negative curvature of (p(g) in Rx.
Lemma C.2 Assume
Also suppose each column of A is l normalized and
K & 3 (1
6/ 653/ 11266
For any point E Rx, there exists some direction d E Sn-1, such that
d Hess p(q)d - II
Proof First, it follows Lemma B.8 that for any point q RN, there exists some direction d Sn-1, such that
d Hess (r(q)d < -41
which together with the assumption [Ax(g)) |Cl12 S1l and the fact d' Hess p(q)d
d Hess ( + d' Ax(g)d & d Hess (
(x()) completes the proof.
D OVERCOMPLETE DICTIONARY LEARNING
In this section, we consider the nonconvex problem of
min (q) 120(1 0)p 1
120(1 0)p T
AX 1
s.t. lql 1.
We characterize its expectation and optimization landscape as follows.
D.1 EXPECTATION CASE: OVERCOMPLETE TENSOR DECOMPOSITION
First, we show that (q) reduces to pp((g) in expectation w.r.t. X.
Lemma D.I When X is i..d. drawn from Bernoulli Gaussian distribution as Assumption 2.2, then we have
0
2
Ex [FDL(G)] = =pp((q) 2(1 - 0) m
Proof Let Ç = Al q E 1 with | m By using the fact that
X
x 32 xpl,
by C gk, by ~ Ber(f), 9k ~ NNO,
observe
Ex [pD
Ex xx/1
Exg ((Taz))
12(1 0)0p
12(1 - 0)0p
1
Eb.g
(s
12(1
0)0
F&
[|
4(1 0)0
Write I bli2
>m (Ixba)² 2, we obtain
27
Ex [p))(())
4(1 - 0)0 Ed
Σ
(zxbR)²
1
Σ 23
4(1 0)
2(1
0)
k-1
0
|211
2(1 0
0
pp(1)
2(1
0)
n
27

---

Published as a conference paper at ICLR 2020
desired.
D.2 MAIN GEOMETRIC RESULT
Combining Proposition C.I and Lemma C.2 together with the concentration results of the gradient and Hessian in Proposition F.3 and Proposition F.,, we obtain the following geometry results of overcomplete dictionary learning.
Theorem D.2 Suppose A satisfies Equation (2.2) and E IR follows BG(0) with 0 ( 2 Also suppose have
K < max ,
53/2, 5-12, (1+ 6fz (,555
< 2n. 63/2 1 < 20
for some constant 17 < 2-
If COK max 1og(0n Kn log(On?) then with probability at least 1 cp cp= any critical point Rc of (p)(4)) either is ridable (strict) saddle point, it satisfies second-order optimality condition and is near one of the components e.g., an in the sense that
> 1 1 55 53-3/2
- 5m7.
a1
(q) is a ridable (strict) saddle point. P C0K*n log(On'), then with probability at least 1 cp-2, any critical point q RN of
Here, C > 0 are some numerical constants.
Proof First note that for overcomplete dictionary in Equation (2.2), satisfies Equation (F.9) with M = 1. Now it follows from Proposition F.3 and Proposition F.6 that when
log(OKn/Hu I<I))) Kolog(O (((12
p 2 COK" max
(D.1)
122 |K
1
then with probability at least cp
grad (DL( - grad pp(g)) < μM |[1
sup 9
1 20
sup ge
Hess (q) - Hess pp(4))
< |
which together with Proposition C.1 implies that any critical point q E Re of (g) either is ridable (strict) saddle point, or it satisfies second-order optimality condition and is near one of the components e.g., di in the sense that
a
1 - 5n)-
We complete the proof for q E Re by plugging inequalities [Clla 2 m 1//6 [|l12 11 and |K|4 m 1/4 |cl,, K1/4 14--1/ 1/4 into Equation (D.1).
Similarly, by Proposition F.6, when
p CAK (0K CeRKnIIIS1d 1151
(D.2)
1c12 1112
then with probability at least 1 - -ppppp
sup gm
Hess (p)(()) Hess (g)
max ||113. 1414
which together with Lemma C.2 implies that any critical point g RN of (DL (g) either is a ridable
(strict) saddle point. The proof is completed by plugging |||| 2 n -1/22nnto Equation (D.2).
28

---

Published as a conference paper at ICLR 2020
E CONVOLUTIONAL DICTIONARY LEARNING
In this part of appendix, we provide the detailed analysis for CDL. Recall from Section 3, we denote
Y
Cy y
Cyz
Cy,l
Rexp.
Ao
[Ca,
Caz
Cag E R
Cmn1
422
Ca.
2;
X; =
E R
RRmx
X=
[
X2
Xpl E R
Caix
For simplicity we
A A)
-1/2 Ao:
m nK.
Recall from Section 3, for CDL we make the following assumptions Au. A and X.
Assumption E.1 (Properties of Ag and A) We assume the matrix An has full row rank with
> 0, condition number: m(Ao) Fmax (max)(o))
minimum singular value: a mii (Ag)
m (Ag)
In addition, we assume the columns of A are mutually incoherent in the sense that
aj p.
max
14J
a.
[ayy
Assumption E.2 (Bernoulli-Gaussian w.x) We assume entries of wa mi..dd BG(0) that
Lik = bik O gike
bik i.s.d. Ber(O), Iik Liidd NO, 1 p. & k
In comparison with Assumption 2.1, it should be noted that the preconditioning does necessarily result in e norrmallie columns of A. But their norms are still bounded in the sense that
| < | & K |ayll
|axxl & VK, 1 k & nK.
(E.1)
Because of the unbalanced columns of A, unlike the ODL problem, the CDL problem
min (q) 9E
1
PY ||
1
q PA,
120 0)np
120(1 0)p
does not have global geometric structures in the worst case. But still can show that the problem is following. Moreover, we also show that we can cook up data driven initialization which falls into the local region.
benign local regions
E.1 MAIN RESULT OF OPTIMIZATION LANDSCAPE
In this part, we show our main result for optimization landscape for CDL. Namely, consider the region introduced in Equation (3.3) as
REDL =- {q e S- (p((g) & -CCDL n x//3,,2 K5))
where ÉCDL > 0 is a fixed numerical constant. We show the following result.
Theorem E.3 (Local geometry of nonconvex landscape for CDL) Let Co 5 be some constant and r < 2 2-6, Suppose we have
n ÉCDL C. 2/33 P 1 K Co.
0=
and we assume Assumption E. and Assumption E.2 hold. There exists some constant C' > 0, with probability at least ei (n(K)- over the randomness of B&KS, whenever
KK5 (AA) 2 min (Ap)* "1 log (m/p),
p > p0 max
every critical point qe of (CDL(()) in REDL. either a strict saddle point that exhibits negative curvature for descent, or it is near one of the target solutions (e.g. a1) such that
(1)
qe
1 1-5K -5x-2
a1
29

---

Published as a conference paper at ICLR 2020
Proof Noting Equation (E.1), set M VK in Proposition C.I. It follows from Proposition E.11
that when
p 3 COK log" max x=*'(Ao) min (Ao) nj
Tog(OKn/uKK) 1/2 (((1))
log( Ogg(OKn/
(|5
max
/ ||<l|3
|c12 (E.2)
then with probability least 1 ci (mk))=.
grad PCDI(()) grad pp(()) & jv K |Cll
sup 9=3
sup Hoss PCDL (q) Hess (r(()) 9E3
|
20
Thus, by using Proposition C.I, we have that any critical point q. E REDI. of PCDL (q) either is ridable (strict) saddle point, or it satisfies second-order optimality condition and is of the components, e.g., d1 in the sense that
a1
E 1 1 -- 3/22 x- E 1- 5mp
9o
a
where we have plugged M = V and & ECDL,443 Equation (C.3). Finally, we complete the proof by using inequalities |[|| e m 1/6 ||1/ = K 1/33n= and ||]]| e m m-1/4 [Cl12 = 12 114 in Equation (E.2).
E.2 PROOF OF OPTIMIZATION
In the following, we show that with high probability Algorithm with initialization returns an approximate solution of one of the kernels up to shift.
Proposition E.4 (Global convergence of Algorithm 1) With m = nK, suppose
log
2/3
4//3
Kμ
min
(E.3)
m
4333m log m
(4433) m² log m
Whenever
(xo)
= COK2 max
n n log (m/M), 0 min (An)
our initialization in Algorithm I satisfies
Qinit REDL == {q pp((g) & -ECDL 1 2/3 4/3 K
=
REDL,
(E.4)
such that all future iterates of Algorithm I stays within REDL and converge to an approximate solution (e.g., circulant shift se [aai] of (01)) in the sense that
|Pa--1 (P (P-'q.) q.)
Se [ami]] $
where is a small numerical constant.
Proof Note that RCDL ReDL is due to the fact that
A
AA K.
We show that the iterates of Algorithm converge to one of the target solutions by the following.
Initialization falls into REDL- From Proposition E.5, taking & 4/D with 0 satisfies Equation (E.3), whenever
K² K 10/3 (Ao) log(m),
p D C
11:30 2 (Ao)
w.h.p. our initialization ginit satisfies spr (rnii))))
2ECDL /2/3///33 A/3K. K.
30

---

Published as a conference paper at ICLR 2020
Iterate stays within the region. Let ( be the sequence generated by Algorithm 1 with q())
qiit. From Proposition E.12, we know that whenever
OK²
R (Au)
p 2 C2 4 8/3
max
0 iiii (A))
n n² log (Onj 2/xxx 4/3)) (mg),
have
sup gE3
(CDL(9)
(pL(a))
0
x²)
< 2 fCDL / k/3
2(1 - 8)
which together with the fact that the sequence (g satisties (CDI(((h) & (CDI(a implies
pr(((()) x (CDL(q + 2(1 0)
K²
+ fCDL 1//3 //,K/KKK
1
2
0
(CDL(q + 2(1 - 0)
K²
fCDL μt /2/3//11 4/3 K
2
( ECDI. 11 k 1/3 K
& - _CDD,. م 4/3 K.
Closeness to the target solution. From Theorem E.3, we know that whenever
(K (Ao) oiin (Ao) n log (m/p),
p M COK2P-2n max
the function (CDL(q) has benign optimization landscape, that whenever our method can efficient escape strict saddle points, Algorithm 1 produces a solution q. that is close to one of the target solutions (e.g. a1, the first column of A) in the sense that
q-
1-
[ail"
with e = 2 In the following, we show that our final output a, Pg (P- should be correspondingly close to circulant shift of one of the kernels {aok k=1- Without loss of generality, suppose q. = a1, then the corresponding solution should be agz with zero shift (or in other words, the first column aoi of Aq). In the following, make this rigorous. Notice that
P q.) amil
P (P-1g.) - P
aoi [ai]]
< 2 [|ai]]
p-1g.
aoI
|
where for the last inequality we used Lemma A.12. Next, by triangle inequality, we have
PP
[ q.)
4o1
$ 22 <21
p-1
a1
a01
+ 2 |1|l
p-1 ( a1
9.
[ail
a1
a=
= = (p-1 (K-IAAAA -1/2
-1) aoi
+ 2 |all
p-1
a1
q+
[a]
2
(0mp
r
1
1/2
(Ao4b) -12
+ 2 a
P
a1
0mp
|ai]
Let 8 E (0, 1) be a small constant. From Lemma E.18 and Corollary E. we know that whenever
10 (AA)))
> C0-1K3
8 log(m),
0 (An)
we have
1/2 1 rrr) (AnAD)) 1/2
8mp
& 5,
p-1| & 2K 2K-1/2 1/2 |
Therefore, obtain
P (P- avzl
< 28 + 4v Aul Ve
28 + 4V2 max (An)x-1 & 28 4V2 &
when 1) is sufficiently small. Here, is small numerical constant.
31

---

Published as a conference paper at ICLR 2020
E.3 PROOF OF INITIALIZATION
In this subsection, we show that we can cook up good data-driven initialization. We initialize the problem by using random sample (1 < p)
Pinit
Ps- (Pyi), lElEp,
which roughly equals
Tiit
P (Axy),
A qmit & VKP (ATAn)) Axx)
For generic kernels, A T A is a close diagonal matrix, as the magnitudes of off-diagonal entries are bounded by column mutual incoherence. Hence, the sparse property of æ should be approximately preserved, so that A qait is spiky with large
| quiit ll We define
Sinit = A qmit.
Sinse VKPmm-1 Axt).
By leveraging the sparsity level 0, one can make sure that such an initialization qinit suffices.
Proposition E.S Let m = nK. Suppose the sparsity level 0 satisfies
log 0
Kμ Kp-2/3
&
1
C1
m
C2
Eml m
min
Ku4/3
m2 log m
Whenever
C K2
x (AA)
log(m))
1A13520 oiin (Ao)
for some & > 0 we have
|Siitll 3 2/3
holds with probability least 1 cm d, Here, C1, c22 c, d, C are some numerical constants.
By using the convexity of losss,, can show that the values of ||Sinilll and (iiit
Proof
close,
(iiit 1 > (Laste _ + 4 (S Sinit Sinie
(Siitt - Sinse
Sinit
4
iiit 3/3
4
Sinit
Simit
(E.5)
4
small
Thus, it is enough to lower bound [mii Let I supp(#e), and let Pr RR R that maps all off support entries to zero and all support entries to themselves. Thus, we have
Stnit
K² AA Aæz
|lAT Awx
R²
(|Pz (AT Aw:)) 11² + PPr (AT Aax)))))) [Pz (AT A
K²
|Pgn-1 (Pr (AT Amx))
(1 + p)²
Proo ( AT (ATAx)))
with p =
By Lemma E.7 and Lemma E.9, whenever
Pr(A Amzil
log
/
C1
&
C2
m
m log m
32

---

Published as a conference paper at ICLR 2020
have
& C1 Jumy 0 logm; m, PI: (AT AT)a)))l
|Pz (AT Awe)l
2
KvOm
v2
holding with probability at least - C3m 54, so that
Piz (AT AAAA)))) PP (A Ax;)l
2
C2p2m log m.
Thus, we have
((mit 1 >
P (PIAT Axx) 1 3
CyK²
PPgm- (PIA Axx) 11
ps p= log
By Lemma 10,0, we have
1
Pgm (PrA) Azx)
20m
with probability at least
C5m
co, Thus, with high probability, we have
CzK²
(tmit
2
22, 2/3
(E.6)
mmm2 log 20m
whenever
Ku-2. 2/3
0 < C4
Em
m²m² log" m
Finally, Lemma E.6 implies that for any 8 E (0,1), 1), whenever
p 2 C30-1k3 k (Ao)
8-2 log(m),
o (Ao)
it holds that
(imtt - Sinss < 8,
with probability at least - (m)) - Choose 8 such that
3/2 Ginit Smiss
3/2 EKp2/3 8 & 1/2 22/3
(E.7)
then by Equations (E.5) to (E.7) we have
Siii (mmit
\ - Gimit > 2K
4K3/2 Siii
Summarizing all the result above, we obtain the desired result.
Lemma E.6 Let 8 E (0, 1). Whenever
> C0-1K3 (An)) 8-2 -o0gmmm) on (An)
we have
Kinit Siait
with probability at least ci(Kn) -2, Here, Ci C22 C > O some numerical constants.
33

---

Published as a conference paper at ICLR 2020
Proof By definition, we observe
Sinit
Smit
A T Pg (Pyc) VVKP8- (AT Axxe)
=
( [Kmpp
-1/2
A P
Anaee
VVPS (A Aws))
-1/2
A
8mp
YYT
Aga
A Axt
( YYT)
-1/2
|Axz
0mp
||
YY
-1/2
ADoz - (AuAD) -1/2
Auxz
|Axy
0mp
< 2vK
xze|
Aoll
(
0mmp
r
-1/2
- (AcAd)
-1/2 -112
|Axr]
Omny
112
= 2 |
YY
- (AA44)) -1/2 1/2
Omp
where for the first inequality we invoked Lemma A.12, and the last equality follows the fact that minimum singular value of A is unity. Next, by Lemma 1.18, for some E (0, 1), whenever
p K²- n² (Ao)
log(m),
min (Ao)
we have
(Smit Sinit & 8vK K A
holding with probability least - c1 (m) Here, C1, C2; C > 0 are some numerical constants.
Replace 8vK ||Ao|| e, obtain the desired result.
Lemma E.7 Suppose the columns of A are ju-inchheent and satisfies Assumption 3.1, and suppose I, satisfies Assumption E.2. Let supp (xz). For any t > 0, we have
Ppz (A AT))))) & loffdiag (A A) æi| &
holds with probability at least 4m exp
(- (-min mini
e kmmmm0mm Kammm }).
Proof Since we have
Piz (AT A=;)) offddag (AT A) xg
(E.8)
we could bound
|Pz-AT Axe] via controlling offdiag (AT A) æz|| Let
m
M offdiag (ATA)
m1
mm] E m and 8 Mæs
Σ
myFe
Thus, we can apply vector version Bernstein inequality. By Lemma A.3 and the fact that ||TTaoll & K Kuym
& m! 2
E[s = 0, E [1' = # || E0-N
(KuVm)"
Therefore, by applying Lemma A.6, we obtain
P (loffdiag (A A) æ > t) P
Σ 8k E E[s]
12
2(m 1) exp
22 + 2K pm / mt
2Kum
Finally, Equation (E.8) gives the desired result.
34

---

Published as a conference paper at ICLR 2020
Lemma E.8 We have
diag (AT A) zell & K20m
(E.9)
with probability at least exp (-8 min +a Om
Proof First, let
d diag (ATA),
8 ||diag (ATA) xt Σ
where by Lemma A.4, we have
[| & OK2pP P!2
0 Oliciag ATA)IE < K20m.
2
Thus, by Bernstein inequality in Lemma A.5, we obtain
P (Idiag (A (ATA) A) x
K20m 3 1) <exp exp (-AK40m 4K2mmt
as desired.
Lemma E.9 Suppose satisfies Assumption E.2. Suppose æe satisfies Assumption E.2. Let I supp (ze). Whenever satisfies
log m
(E.10)
log
we have
PAT Ax:))]
3 K20m
(E.11)
with probability at least 1 - m. Here, c1 > 0 are some numerical constants.
Proof Notice that
PPz (AT Axx)))l
|diag (AT (A) at Px (offdiag (AT A) me)
||diag (ATA) A) x; + Pr (offdiag (AT A) x; a=))]² 2 (diag (AT A) æ,, Pr (offdiag (ATA) ai))
|diag (ATA) A) xı 2 2 |diag (A A) x; Pr (offdiag (A A) xæ)i|
By Lemma A.9, Lemma E.7, and Lemma E.8, we have
ddaag (A A) x; K20m C K2 0m log m
Pz (offdiag (A A) æz) C20
holds with probability at least m ", Thus, we obtain
P2 (AT Axx) Km0m (1-Ci) Ci
log m Om
Csp /m log m
Finally, by using Equation (F), we have
P2 (ATAZ)) Axt)]l
1 >
K² 2m
as desired.
35

---

Published as a conference paper at ICLR 2020
Lemma E.10 Suppose æe satisfies Assumption E.2. LetI = supp (xt).
Whenever E
log m
then have
Pgmm- (Pi (A Axxe) >
20m
with probability at least m
Proof By Lemma A.I, we know that for any 2,
|| > ||=||a" ||=||
and the fact that P3m-1 (Pz (A Axx)
1l0 1 = |azello- we have
Pam (Pz (A Axx))); > |xello
By Lemma A.9, we have
1
æzlo
20m
Pgm (PI(A Ax;))
20m
holds with probability at least -
E.4 CONCENTRATION AND PERTURBATION
We prove the following concentration results for Riemannian gradient and Hessian, and its function value.
Proposition E.11 For some small 8 E (0, 1), whenever the sample complexity satisfies
6 (Ao)
log (4/")
[0Kn
p * C8 CO-2 max 0 Ao)
logo (mK),
11
have
sup
grad (CDL(q))) - grad (p(()) < 8
ge5--1
sup q88--1
Hess (q) Hess (p(()) < 8
hold with probability least (mm)) Here, C1, C2 C > are some numerical constants.
Proof Let (g) be introduced as Equation (E.
@CDL (q)
AX 14
128(1 9)
so that we bound the Riemannian gradient and Hessian separately using triangle inequalities via (CDL
Riemannian gradient. Notice that
sup 9=8--1
Igrad (CDL(() (q) (g(())
sup g=
Igad PCDL grad (c)L(q))l + sup qes
||grad (CDL(9) grad (r
From Proposition E.13, we know that whenever
p > C10R110 n: (Ap) 2 (Ap) 8 1 Img),
we have
sup gea>
l|grad (Q) - grad (CDL &
36

---

Published as a conference paper at ICLR 2020
with probability at least (mK) ". On the other hand, Corollary F.9 implies that whenever
0Kn
p > C28-20K log
8
we have
8
sup ge8n-1
Igrad GCDL (q) grad pp(())
2
holds with probability at least 1 - camp 2, Combining the bounds above gives the desired result on the gradient.
Riemannian Hessian. Similarly, we have
sup
Hess (Css( Hess (g(())
ge8"
sup ge8nm1
Hess (PDDL Hess (cDL
+ sup 963--1
|Hess (CDL(C) Hess (pT(4)
From Proposition E.15, know that whenever
p > C30K10 R (Ao) min (Ao)
2n2 log" (mg',
we have
sup qe8a-1
Hess (CDL(q) Hess (CDL(4)) $
2
with probability at least
ca (m)) cs, On the other hand, Corollary F.10 implies that whenever p C,0K log (0Kn/8),
we have
sup |Hess pou Hess pp(())) < q03"-1
holds with probability least camp Combining the bounds above gives the desired result the Hessian.
Similar to Lemma D.1, for convolutional dictionary learning, asymptotically we have
0 K2
E (g)
Ex [g) (p((g) 2(1 0)
(p
1 A
Next, we turn this asymptotical results into finite sample for the function value via concentration and preconditioning.
Proposition E.12 For some small 8 (0, 1), whenever the sample complexity satisfies
& (Aa)
[KKn
p 2 C8 C8-2KK* max 2 (Ao)
n n log
log 3 (mK),
have
sup ge$a-1
(CDL(
(Pr(q)
k2)
2(1 0)
hold with probability at least 1 - (m(K)) Here, Cı, C O are some numerical constants.
Proof By triangle inequality, we have
(CDL(()) (T)((g) 2(1 K2)
sup n-
(PCDL( PCDL (g)l sup n
sup
|@CDL (q) Ex [PCDL(q))! (g)]l
gega-1
Ts Thus, by using Corollary E.14 we can control Ti. For Tz, we can control a similar way as Corollary F.9 or Corollary F.10. For simplicity, we omitted here.
37

---

Published as a conference paper at ICLR 2020
E.5 PRECONDITIONING
In this part of appendix, let us introduce
1
(CDL(C)= = 120 mnp q (PAo) (CDL(g) == 120 0)mp
q
AA
(E.12)
In the following, we show that the differences of function value, Riemannian gradient, and Hessian of those two functions are small by preconditioning analysis. For simplicity, let us also introduce
eo
X (PAo)' q.
v( A q.
(E.13)
E.5.1 CONCENTRATION AND PRECONDITIONING FOR RIEMANNIAN GRADIENT AND FUNCTION VALUE
First, the gradients of (CD and (CDL(C)) and their Riemannian variants can be written
VeCDL = 30(1 0)mp
PAp Xu Os
VGCDL( = 30 0)mp
1
AX AXo 08
grad PPDD (g) = P (g)Dn.(g))
grad (CDL( = Pq VGCDI(
where recall from Section that we introduced the following preconditioning matrix
(
-1/2
1/2
p
YYT
Ao
X,X7
Ag
(K
mp
In the following, we show that the difference between grad (CDL(()) and grad (CDL(C) is small. Proposition E.13 Suppose 0 E (1) For any ò E (0, 1). whenever
2)
p > 10K10 x (Ao) 8 2n log (mK),
- (Ao)
we have
sup ge3--1
||grad (CDL(c) grad (CDL(9))l <
sup geS
(VCDL(()) V(CDL(())] <
with probability at least 1 - (1(K)) - Here, Cı, C C> O some numerical constants.
Proof Notice that have
sup qE8n-1
IgDu grad (cDL(g))
sup qe8"
VPCDL(()) V&CDL(q))
sup q
PA 0o
o
30(1
0)up
sup
PA
03
08
sup gESn-1
(PA, A) Xx
30(1
0)mp
968a-1
Ti
Ta
Controlling Tı
For the first term, we observe
Ti
PApl
|X|
sup
00
30(1 - 0)mp
qs8n
38

---

Published as a conference paper at ICLR 2020
where for all Sn-1 we have
|
$ |20 02
||||| + 20- ---ol vollo
< VK (vK + |IPAol))
|PA0
All
max
[Xex]
|
Igkenp
2
+ |P A|| |PAol
|X
max LEkEnp
(VK+ (VK+IPAb))
|
max LEkEnp
Xex|
|PA Al
where for the last two inequalities we used Lemma E.16. Thus, we have
Ti & (VK+IPAO))
|| "
max leksnp
|xeel]
PPo - A
Controlling T2. For the second term, by Lemma E.16, we have
2
To & PA. Al
x | K3/2 |
max L
[xxll)
IPAo
Al.
Summary.
Putting all the bounds together, we have Iggadd (q) grad (q)
sup
968
1
(VK k |PAol) | K3/22
|X|2
max 1skenp
[Xeal)
PAo All
30(1 0ymp
By Lemma E. and Lemma E,20, we have
|X| < 2m/ppp
Xee < 4v0mloggH
max LEk-mpp
with probably at least 1 - 2p - On the other hand, by Lemma E.19, there exists some constant C > 0, for any E (0, whenever
p > C0-1K3 (Ao)
log(mK),
o (Ao)
we have
PPA All & c, c,
|PAol
2
hold with probability at least 1 - Ci (mK) for some numerical constants 0. These together give
T & CK (m))c.
Replacing 8 Cm log? (Km) c gives the desired result.
Here, the perturbation analysis for gradient also leads the following result
Corollary E.14 For some small E (0, 1), under the same setting of Proposition E.13, we have
sup q=8--1
((CDL(g) (CDLL & 5
hold with probability least
ai (mK) Here, Gr 02 are some numerical constants.
Proof Under the same setting Proposition E.13, we have
( (gD = sup --
sup
|
1
9E8 4
30( 0)mp
30(1
m)p
sup
(q, PA,
X
AX
gEa
30(1 0)mp
sup
ViPCDL(g) - (CDL(q))
<
4'
as desired,
39

---

Published as a conference paper at ICLR 2020
E.5.2 CONCENTRATION AND PRECONDITIONING FOR RIEMANNIAN HESSIAN
For simplicity, let vo and be as introduced in Equation (E.13), Similarly, the Riemannian Hessian of (CDDL()) and (CDL(g)) can be written
Hess (g)
30(1 0yp Pa
(P X diag (o
) (PAn) -1vol - Pat
Hess (CDL(q)
Pq
3AX diag (vo2) x A
|la Pa
30(1 0)p
respectively. In the following, we show that the difference between grad (CDr and grad (q) is small.
Proposition E.15 Suppose 0 ( 2)- For any (0, 1), whenever
p > COK10 KO (Au) 5 -n2 log (m)),
0 (Ao)
we have
sup qE8
Hess (CDL (q) Hess (CDL(g)) <
with probability at least (m(m)) a Here, C1, C2 C C> O are some numerical constants.
Proof Notice that
sup q
Hess (CDL(()) Hess (cDL(
(PAo A) X diag (2)²) x (PAn)
sup
0(1
Oymp ges
+
sup g-
AX diag 22 X (PAo - T
8(1 m)
AX diag (ug² - )02)x X (PA))
sup
0(1
np
qe
Ts
1
|0|
4
sup
38(1 m)p
np
qe8--1
Tx
By using Lemma E.16, we have
Ti <
PApl
X
PA
All
sup qESn-1
| a
&
PA
3
2
max l
Xex|
PPAo - Al.
2
T2 [ |
sup qEBn-1
1012 2
&
K
X|2
max Igkgnp
|Xeil]
|PAo Al.
Similarly, Lemma 1. implies that
Tg < PAol
|
X
sup
C2 100
02
q
2
KK
IIPA))
PAp
|X|2
max 1skknp
|Xeal]
PAA
Al,
40

---

Published as a conference paper at ICLR 2020
and
sup gea
||00|
|/0oll
2 sup qea
Kr- Bl, 400
sup ge8
|
Woll |0|6
2
3/2
XI|
max lgkenp
[Xex]
PAo - All
Thus, combining all the results above, we obtain
sup 9E8
|ess (GD
Hess (CDI(
PAull (VK+IIPAOl) (Pol)
K| + 4K |x|
max lEksnp
Xeal]
IIA All
8 -8mp
By Lemma E.17 and Lemma E.20, we have
X & 2 0mp,
Xex
4v 4v0m log Kp)
kgg
with probably at least 1 2p-2 ? On the other hand, by Lemma E.19, there exists some constant C' > 0, for any c e 1) whenever
> C0-1K3 (Ao)))
log(mK),
22 min (Ao)
we have
PP All <
|P & 2VK
hold with probability at least 1 e1 (m(K)) for numerical constants C1 02 0. These together gives
Hess (g) Hess (g) 6'K5/20mlog (Kp)
sup n-
Replacing å = CCKK3/20mlog' log (Kp) gives the desired result.
E.5.3 AUXILIARY RESULTS
Lemma E.16 Let vo and v be defined in Equation (E.13), with
vo(g) X X (PAo) q. v(g) A
For all q 8--1, we have
& v
max Isksnp
[eell
|ooloo &
max PAoll laksnp
Xeell
|
<
K
X
K 2
max Iskgap
|
0,
22
&
/ +
|P
PA
All
max Igkenp
|Xex||
vol
PA A X
Proof In the following, bound each term, respectively.
41

---

Published as a conference paper at ICLR 2020
Bounding norms of and vy- For the f--ormm notice that
|
|||
&
vKI
On the other hand, for the f norm, have
||
max skp
e
q
& V
max
[ee]
l
|
max Isksnp
e X
(PAo)
T
q
&
PAol
max Iskenp
Xee||
Thus, the results above give
l < |1l2
|0|
& K x|2
max Igkenp
Bounding the difference between and Un-
First, bound the difference in e-norm,
| woll = XT (PAo A) < |PA. - All ||
On the other hand, we have
1002 o 1o
10- volool
110 voloo & ([v) + -11ola)) 1/0 vol
where
-ovol
C x (PAo A) 9 & PAu All max lsksnp
[Xee
kgkenp
Thus, obtain
[xell] 2
02 D 021
& (VK+IPAN IPA A
max lgkgnp
desired.
Lemma E.17 Suppose X satisfies Assumption E.2, we have
[Xex| < 4v0m pp
max 1gk
with probability at least 1 p 20m
Proof Let us write
8- [+a]]
X;
32 Tin], with Dej
ieiEp, lEjEn,
Sj-1
[xix]
where sy [-] denotes circulant shift of length l. Given X
[X]
X Xpl. have
max 1k
|eell
max LeiEpIEEjE
max 1eisp,1ajEn
Σ 18y_ [+lI
K
max Ef
Next, we bound maxigisp. ||aze| By using Bernstein inequality in Lemma A.5, we obtain
12
TP
| 2 no
x t)
exxp
4nd
Thus, by using a union bound, we obtain
4v0nloge (Kp),
with probability at least 1- 1-p p-20mp2 20m Summarizing the bounds above, we obtain the desired result.
42

---

Published as a conference paper at ICLR 2020
E.6
INTERMEDIATE RESULTS FOR PRECONDITIONING
Lemma E.18 Suppose X satisfies Assumption E.2. For any E (0, 1), whenever
C0 K2 15 (Au) 8 log(m),
Mmin (Ao)
have
(Di YY LYYYT
-1/2
(AcAo)
E ó -1/2
0mp
((
1/2
(Omp
(AgAa)
112
-
< mmin - -
hold with probability at least - (mK))=a Here, C1s C2
C> > O are some numerical constants,
Proof Notice that
1
1 A AT AoA + Ao
1 -x -1 Ao
-YY
Omp
Omp
0mp
By Lemma E.20, for any E (0, 1/K,, whenever
p C0 2
have
1 xx 1 <
0mp
with probability at least
02 (mK)
-0,
Thus, by the first inequality in Lemma A.10 we observe
1 Omp
11/2
(ApAo) -1/2
(B+ B 1/2
B-1/2
40 -2
(B) |
min
4x² (Ao)
4x²( 02 min (Ao) c.
Xx
o (A))
Omp
On the other hand, by using the second inequality in Lemma A.10, we have
(1
1
1/2
(AnA,)) (A0A5)-1/22
= B A)
B 1/2 1|
0mm
& 40 min
B A
4x 2 Ao)
1
4x2 Omin (Ao) -E.
xX
1
Mmin AAn)
Omp
(An)
Choose
8, we obtain the desired results.
Omii (Aa)
Given the definition of preconditioning matrix P, the result above leads to the following corollary. Corollary E.19 Under the same settings of Lemma E. for any 8 e (0, 1), whenever
p 13 (Au)) log(mK),
σ2 min (An)
we have
PPA. A P-1 2K 1/2 |
PAool & |||| + & V +
hold with probability least cr (mK) -2, -ca, Here, Gi C22 C O are some numerical constants.
43

---

Published as a conference paper at ICLR 2020
Proof For the first inequality, we have
(11) 0mp
-1/2
(AnA)) -1/2
IPAo A & VK
YY
|Aull
Thus, for any & E (0, 1), Lemma E.18 implies that whenever
p * C0-2K3 (Ao) 8 log(mk),
min (Au)
we have
PAo- Al & 6, PPoll < |A||
|PA - -Al & VK + 8
with probability at least 01 (mK) -2 On the other hand, by Lemma E.18 we have
p-1 & p [K (K-1A0 Ao 1/21 + (K-1 AoAo) 1/1
(K- (K-AAAA)) Ao 1 (1 + p-1 AgAo) -1/2 -122 112-11) -T)
Aoll 1+ (mmp (1mppr))) 1/2
(AD4.) -1)
K-2 1/2
2K ||Aol
desired.
Lemma E.20 Suppose X satisfies Assumption E.2. For any 8 E (0, 1), we have
1
xx
<
6,
| < 00mp (1 + 8)
Omp
with probability at least numerical constants.
Ci mK exp
(-c2ppmin ( .44) Here, C₁, C2 > are some
Proof By using the fact that X
[X] X2
Xp). we observe
Casa
XXT
X
X
k=1
CHAK
21
For any 2 gn-1 write
:
We have
1
-1
XX
XXT -1 -1=
sup ze8t-1
0mp
Omp
1 T
X,X.
= 1|
sup
-1
0mp
''55
T
sup 268
Oz. 2x
> Can zx
-1x12
Omp
sup z6
T CT 2
Ca., 24 +
Σ
Co. #1
- |x
Omp
kitt
K sup 265
1
z
CT
Cas -1 2b
+
2
CT
min Cau
26
Omp
Omp
k+t
K
K
1
CT
Ca.
+ 2K
Σ
Σ
C Cau
Onp
Omp
1-1
R4F
i-1
44

---

Published as a conference paper at ICLR 2020
By Lemma E.21, we obtain
xx I & ti 2K12 < 8
0mp
with probability at least
- 2m exp 1-cppminn (69,5)) 2mK exp (-c20pmin (x-10) K x-16))
Finally, the second inequality directly follows from the fact that
xx
I E δ =
X & (0mp) (1 + 0),
0mp
as desired.
Lemma E.21 Suppose æij satisfies Assumption E.2. For any j [K], we have
CT Ca.,
I $ t
Omp
holding with probability at least 1 - 2m exp with k + E, we have
(-
0p min
of t1)
Moreover, for any k,l E [K]
1
Σ
cT
Ca..
< 12
Onp
Bin
holding with probability at least
2 2m exp (-
cp min (2)
2
Proof Notice that
C Cany
F8 diag (IF2.))
(2) (2))
F,
Cuu
F diag (Fax O Fa.:)) F. (B.14)
2i5
Bounding
D 2
Cans
I|.
From Equation (F.14), we have
Onp
1
p
Ca.y Cwi
Fa diag
2
Fxig
O2
F
@np
Onp
i=1
1
p
Faig
02
Bnp
Let f be row of F, by Lemma A.3 we have for any l 1,
2
[ x.g
26
<
2 Es, Ber(O) 1b fx
< 0 (
2
Thus, by Bernstein inequality in Lemma A.5, we have
p01f (-10If
ff xb
> t1
<
2exp
(8+
Onp
Thus, by using union bounds, we obtain
p
C Ø.
Ca.,
1
Σ
Fx
02
& ti
Onp
Onp
i=1
for all 1 < & K with probability at least
2nK exp
(-
Ap
min
122 11)
45

---

Published as a conference paper at ICLR 2020
Bounding
1 Omp
-
Czax ma
Caus|
On the other hand, by Equation (E.14), we know that
1
p
p
Crrie
<
Fau C Fax
Onp
2it
0mp
Let sid
mie
mie a.faffaa (1 & d & n), have its moments for
1
IE
E [1 x &
s!
B Ber(A)
|1ba O fall 2x
8!
On"
Thus, by Bernstein inequality Lemma A.5, we obtain
8pt2
t2
<
2exp
Onp
2 2t2
Thus, by applying union bounds, we have
C
Cas
$ 12
@mp
mik
for all 1 & k, & K and k + l with probability at least
2mK exp
(-
8p min {1z t2))
F MEASURE CONCENTRATION
In this part of the appendix, show measure concentration of Riemannian gradient and Hessian for both PDL (q) and PCDL (q) over the sphere. Before that, we first show the following preliminary results that are key for our proof. For simplicity, we also use K mm/ throughout the section.
F.1 PRELIMINARY RESULTS
Here, as the gradient and Hessian of *-loss is heavy-tailed, traditional concentration tools do not directly apply to our cases. Therefore, first develop some general tools for concentrations of superema of heavy-tailed empirical process over the sphere. In later part of this appendix, we will apply these results for concentration of Riemannian gradient and Hessian for both overcomplete dictionary learning and convolutional dictionary learning.
Theorem F.1 (Concentration of heavy-tailed random matrices over the sphere) Let Z1 Zz.... Zp Ra be i.i.d. centered subgaussian random matrices, with
Z, a Z (1 E Ei< p) and
[[ 0,
[[
1) & 2exp
2x
For a fixed q Sn-1, let us define function fq(:) R x - Rdd xd2, such that
[Z) is heavy tailed process of Z. in the sense IP (l)a(Z)] > t) < 2 exp (-CVI). The expectation E [Jq (Z) is bounded and Lipscciii i.e.
[TB (2)]] By, and [ (2)] - E. [Saz 2)]l & T.g |1 - 22l. V 41: l2 gn-1
(F.1)
Let Z be truncated random matrix of Z, such that
Zij
if Zigl B, otherwise.
2 = 2 Zij =
(F2)
0
with B ==2oyloy log (nin For the truncated matrix Z, further assume that
[sa(2)| & Ri(a), max
[[,( & Ra(a),
(F3)
1/ ( Sap [ T,(()) |q 92ll A n, Q2 5n-1
(F4)
46

---

Published as a conference paper at ICLR 2020
Then for any 8 (o, 6 ). whenever
min (d1, d2) By 5 R
6 [61
p 2 C' Cax
n nlog
+ log(d, + d2)
R1122d
we have
Σ (z.)) B[f( & 6,
sup qE5
P i-1
holding with probability at least (mi -2 - cooo (E. for some constant c, C 0.
Proof As aforementioned, traditional concentration tools does not directly apply due to the heavy- tailed behavior of fa(2). (Z). To circumvent the difficulties, we first truncate and introduce bounded random variable Z as in Equation (F.2), with truncation level B = 2a /log (nin2p). Thus, we have
P sup 9ES--1
(4(
(Z) fq (t)
3 1
p 1-1
1 P
P
sup
Σ
- E [la
P
Zilla
B
968
p
P1(1)
P2
As fg( ()) is also bounded, then we can apply classical concentration tools to Pi (t), and bound P2 by using subgaussian tails of Z. In the following, we make this argument rigorous with more technical details.
Tail bound for Pz. Since Zj centered subgaussian, by an union bound, we have
B²
P2 P
max 1stEp
B
< ninepl ([Zjal
> B)
exp
(-22
20"
log (mim2p)
Choose
2 log (11 (11p) we obtain
P2 = P
max lEiEp
Z
B
(1inop)
Tail Bound for
1 Σ [z,
E [
with a fixed E S"-1 First, we control the quan-
tity for given for q E gn-1
gn-1 Later, we will turn the tail bound result to a uniform bound over the sphere We first apply triangle inequality, where we have
1 2
(2) -(G(2))
1/
(((Z))
B[6(Z)]] -
p
1=1
such that
p
P
P Σ (z.) - [l)
=t)
P
fa(Z)) B[(((2)]
t- [-[E(((Z2) E B [[,(2)]]
Notice that [[,(()
[2)] & |E [2) 01 12 & [B[[ (2) | [
2 z+z 2
min (di, d2} B₁
Σ
p (Zi + Zig)
12
& min (di BB fn exp
20
47

---

Published as a conference paper at ICLR 2020
where for the second inequality used Cauchy-Schwarr Schwarz inequality, the third one follows from
and the last one follows from the fact in Z is subgaussian. With B = 2 Vloyoo (n122p), we obtain
min (d1, d2) Br
n1 R2
so that
( {1 (())))) -
> 21) & P (1L - B 2i]
By YI T22p
P
E[f
>
Next, we need to show concentration of - - [ to finish this part of proof. By our assumption in Equation (F.3), we apply bounded Bernstein's 's inequality in Lemma A.7, such that
[fg
P (()
t & (d1 + d2) exp (-
ptp
(z.)
2R2 + 2R
Choose p large enough such that
2 min (d1 d2) B
min {d1, d2) B
p
$ 2
n1n2
111 71
Thus, for fixed q E Sn-1 we have
P
21 P (1
P _ (z.).)
PP
Sa 2 [[]
la Zi)
-B[G((2]]
1/2
p
i=1
pt²
(d1 + d2) exp (-8Re + 8Rst/3
Bounding Pi(() (l) via covering over the sphere Sn-1 Finally, we finish by Let N(e) be an
epsilon net of the sphere, where we know that
V E s--1. 3 N(e), s.t. a q'l & c, and #N(c) & 3 R-1
Thus, we have
sup 9E8--1
fg (Z.) Blff
p Σ fa Zi) - E (e
sup q/E m
(zi - - P fg Zi)
sup (c)
fgr Zi) - E (fg
+
sup d'EN(e))le) te
p Σ fa
p==
sup c & [ [2)]
By our Lipschitz continuity assumption in Equation (F.1) and Equation (F.4), for any q E gn-1, we obtain
E [[q [2]] - E E [I)
< Ly [|ele
falte Z,)
Σ fg Zz)
< ( & [, lell
which implies that
P 1 Σ
1
(g(Z.) - E[a(Z
(z. + (L, Li)
sup 9es
sup g'NN(()
p
P
48

---

Published as a conference paper at ICLR 2020
Therefore, for any t >> O, choose
2(L, IT)
so that we obtain
P fq - -
P
sup
> =t)
0e3"
P 1-1
sup (e)N(()
(Z,) - BISG (2)
3 -- (L
P
1 (Z.) - ((6
P
sup (eN(()
> f/2
P -
P (Z,) - B[fG(2)]
#N((c)
P
> t/2
n-1
pt2
(d1 + d2) exp
32R₂ + 16R2t/3
pt²
3pl
6 (6 (6(,, [1)
exp
min
+ n nlo
log(d; + d2)
64Rg
32R1
Therefore, combining all the results above, for any d E (o. (0.6 R2
Summary of the results. whenever
min (d1, d2. Bj 8- --2 nlog
6 (6 I1) log(d1 + da)
p 3 max
n1n26
have
1 P > fg( [z.) [[] < 8,
sup ge
P i-1
holding with probability at least - (ninpp) 2 n -2 -L for some constant e, > 0.
Corollary F.2 (Concentration of heave- random vectors over the sphere) Let
æ1, R2, Ap E 1h be i.i.d. centered subgaussian random matrices, with 2, = (1 < <
and
E [2:] = 0, IP ((=)
t) E eexp 20
For a fixed q Sn-1, let us define function fa(-) RR Rd,, such that
1. fz(z) is heavy tailed process of 2, in the sense of P (1]f((z) > 1) < 2exp (-OVI).
2. The expectation E [x)] is bounded and L -ipsschht i.e.
[T [2)]] & Bj, and [E (z)] [[fgz Ly lq: -2ll, V 41, g2 Sn-1
(F.5)
3. Let z be a (runcated random matrix of 2, such that
2:
if 12 B, otherwise.
(F66
0
with B = 20 log (n1p). For the truncated matrix z, we further assume that
[1)( & Ri) E [[]{())]] & R2(g),
(F.7)
(z) - (x)) T.y(a) q21, V 4ı l2 gn-1
(F88
49

---

Published as a conference paper at ICLR 2020
Then for any E (o, 6 ). whenever
B₁
6 (((s++z)) [,)
+ log(di) }
p > C max
8~2 nlog
n1d²
we have
1 P fz.).) [[fg
sup
< 6,
qe8*
p
holding with probubility at least (m1p) - n colos (L, for some constant c, C >
Proof The proof analogous to that of Theorem F.1. The slight difference is that we need to apply vector version Bernstein's 's inequality in Lemma A.8 instead of matrix version in Lemma A.7, by utilizing our assumption Equation (F.7). We omit the detailed proof here.
F.2 CONCENTRATION FOR OVERCOMPLETE DICTIONARY LEARNING
In this part of appendix, assume that the dictionary A is tight frame with ---ormm bounded columns
1
AA I, |a, & M (I m).
(F.9)
K
for some M with 1s & M & K.
F.2.1 CONCENTRATION OF grad (-)
First, we show concentration of grad (DD (q) to its expectation E [grad (DL(()) grad (p(()),
P
grad (g) 38(1 B)p
P
Σ (q Arx) (Axx)
graddp(() PPp. (A
where 24 follows i.idd. BC(() distribution in Assumption 2.2. Concretely, we have the following result.
Proposition F.3 (Concentration of grad (PL(-)) Suppose satisfies Equation (F.9) and X (0, (0,ck²/(mm log" p plog" np)),, when-
Ipm follows (0) with E (th, 2). For any given ever
[KKn
p C5 20-20K log
we have
sup l|grad (p) - grad (p(()) ge8
holds with probability at least - cpp-2 Here, c,d.C C 0 are some numerical constants.
Proof Since have
grad (DL(() 30(1 0)p
P Σ (q Axx) (Axx),
we invoke Corollary F.2 to show this result by letting
1
fz(x)
(q Ax) Pa-Ax R",
(F.10)
30 0)
where x (B) and we need to check the conditions in Equation (F.5), Equation (F.7), and Equation (F.8).
50

---

Published as a conference paper at ICLR 2020
Calculating subgaussian parameter o² for and truncation. Since each entry of follows Dj wiid (G))), its tail behavior is very similar and can be upper bounded by the tail of Gaussian, ie.,
P (11y) > t) & exp (-t²/2).
so that we choose the truncation level B = /og (mp).
Calculating R1 and R2 in Equation (F.7). First, for each i (1 & p). we have
|Ar
|| + ||a,||*
K-2 x;
[x)() 38(1 0) (a" Au.) Pq Aæ;
38(1 8)
30(1 0)
30( 1 0)
By Lemma A.9 and union bound, we know that for any
i $ p,
| < 40m logp,
Telloo & 40m log
x 2
B
T llo
4B3 log
(F.11)
with probability at least - p 20m, Thus, by our truncation level, we have w.h.p.
60
lf (x;1)
K2 K2B log R1.
(1-
On the other hand, by Lemma F.5, for the second moment we have
E
[
< E
[1f < cfK
for some constant e 0. Thus, we obtain
60
R1
Bm log" p:
R₂ ckKmm.
(F.12)
Calculating L in Equation (F.8). by Lemma F.4 we have
Notice that for any q1 92 8n-1, let C:
A q: (i 1,2),
1f
T
fgz
T
(C] T
P o8
AT
(5. x)
At
30(1 8)
93
||||
(C (T)z)
Pat (5 Φ
Paj
30(1 0)
||||| [
[|cT oz)
Pgj Pat
+ (GT a²)
(55 =5Ix=)" "]
30(1 0)
||||| <c
[2 |A|
|
1/:1 d2l
+ 3 311 3 x |1 42l
30(1 0)
2 || 4
[ 4
|q
qell
0(1 0)
where for the last two inequalities we used Lemma A. 11 and
(c] Φ 3 - (c, x)
= (C: (2) क (c क) + (c, 3) (c] Φ) + x)
< A| |
91 qell
(cT + (<Ix) + +|< [<
< 3 A
T || 42l
Furthermore, by Equation (F.11) we obtain
2 A x
329
I1 (x) - (x))
11q1 42l
<
3² log pll - -921
0[1 0)
1-
This gives
320
L,
K² B² 1 m2 log² p.
(F.13)
51

---

Published as a conference paper at ICLR 2020
Calculating By and Ly in Equation (E.5). From Lemma F.4 we know that B[f{(z)] Pa Aços, so that
[E [f)())] 4 03
< p |||| | q/s
A A ql
< |||
K2
By.
(F.14)
where used Lemma A.1 for the second inequality. Moreover, we have
IE [qn (x) [l (x)]]
Pat A Por A
03
P A P A 03
All |5 003
P
Paz
| 0
A| ((: (2) 3 (5 + S1 3 S2 + (P2) | + 2 A| |1
91 -22
< ||| || - 42l 5K2 1 - 42l
b 91 8ell
(F.15)
where for the last inequality, we used the fact that
[[<1 (2) (CP 1 (P
[<1 C2 5/ O1 1
<
< A T (qi - 92)l (//99) + 14 o Cell + |(
< 3 A|A 3 |q| q2ll
Thus, from Equation (F.14) and Equation (F.15). we obtain
B, = K2
Lj = 5
(F.16)
Final calculation. Finally, we are now ready to put all the estimations in Equations (F.12), (F.13)
and (F.16) together and apply Corollary F.2 obtain result. For any 8 e (0,6 Rr
whenever
2 C5 C8-208-8 -0 n² log (0Kn/o),
we have
1 -
[z.z - [[G((}]]] < 6,
sup ge8n
P
holding with probability at least 1 - (np)) -2 n ca log(9Kn/66) - 20m for some constant C2 C' 0.
Lemma F.4 (Expectation of (pr. Vq Sn-1, the expectation of grad (.D(()) satisfies grad yDL (q) (p(() P
Proof Direct calculation.
Lemma F55 Suppose æ BG(() and let fx) be defined as Equation (F.10), then we have
E [1(((()))
COK4m (K m/nn.
Proof Since (G) write b + g with Ber(O) and (), Let I be the nonzero support of x with I = suppæ. x. And let Pz(.) be an operator that restricts a vector to the support I, so that write Pz(g). Notice that
m
E {f))))) = E
Σ
fou [x)]
max E 222 (x))
ke [m]
52

---

Published as a conference paper at ICLR 2020
Let W pa. A with we being the hhhh row of W. For vk [n].
902 0)2 E
(q Ax)
Wk
E (A q, x.) 10)
902 8)2
(0 0)2 (R (B (AT q) .9) 1))
$ ( (B(Pz (20x) (tx)) ,g)")
Notice that
(Pr qA - >>NN>>( (AT 9)13 and (wx( . ~ No0, IPz (wx))l
hence
v) 11)= = V11!! Ez Pz (A q) 11)2
E (P (AT q) .0)
Let A 6, then we have
Ez Pi (A q)
Σ
mi, Lii T Skg Iazzz LAMES RoEESt IKEEI (F.17)
ke....k.
for bounding equation F.17, we discuss the following cases:
When only one index among K1, k2...., kg is in I:
E2 Px (ATa) 4) 1
Σ & OK
When only indices among 1;,, lig ........ . Ki are in I:
E, Pz (A q)
12 8² Σ
(c 10
Sh Sky + Sky Sh2) < k
When only three indices among &1. .2...., hg are in I:
Ex Pz (A 4)
0
Σ (G C2 Sh + G Ch Ska C2, Sk2 (2) 30
When only four indices among ki, k2.....
K6 are in I:
Ex Pr A 9) = 0²
Σ
(C2 22 22 Sh + 22 22 (t, < 10
kaikka
When only five indices among k1, k2 .... . Ko are in I:
Ez Pr (A (AT
05
Σ
(Ch Skg Sky Ske
22
(1, < K
Rs do Ro Ks
When all six indices of k1, ..., Ki are in
Ez PP (A [T])
86
Σ
(C2 S2 Sha
Sog (2 < K*
kn kyy Ks.
Hence, we have
Eg P2 (A (ATq)) 0K* + 30" + 303 + K + K + K & C
for constant C1 11. Similarly, we have
E (E (wx). w 0)
-3 Ez Pi (2==)11)
53

---

Published as a conference paper at ICLR 2020
and
whisr LKLEZWR Jazez & C20 m²
Er Pl (wx)) ) = Σ
n22
R1 K1
for constant C2 2. Hence, we have
E Pz (A .)))).))) .) 10) (B (B(Prws,g))
Cge" m² ne
Cz
for constant C3 829. Hence, we know that bk [n],
C4 m
[B/"(())] (x)] < 0(1 0)2 n = COK
for constant C₁ > 93. Therefore
IE [fg((()) & &.O
for constant C'
93
8-71-077
F.2.2 CONCENTRATION Hess (-))
Proposition F.6 (Concentration of Hess (pD(()) Suppose A satisfies Equation (F99 and X Rmx follows BG(0) with 0 E ( 1). For any given E (0, </..k2//// /logg plog* np)), whenever
p 2 28-20K log (0Kn/5),
we have
sup gES
Hess (p) - Hess (p(()) <
holds with probability at least
dp- Here, d. C> > 0 are some numerical constants.
Proof Since have
Hess (g) 30(1 0)p
Pgt 3 Axx) Ava (Axx) Ta Axx) i Pgt,
we invoke Theorem F.1 to show our result by letting
fq(x) = 30(1 0) pgt 33 (q Ax)² Ax (Ax) (A I P. Raxn (F.18)
where BB)()) and we need to check the conditions in Equation (F.1), Equation (F.3), and Equation (F.4).
Calculating subgaussian parameter a² for æ and truncation. Since each entry of follows miid (G),), its tail behavior is very similar and can be upper bounded by the tail of Gaussian, ie.,
P ((1.1 > t) < exp (-t²/2),
so that we choose the truncation level B 2 log (ri)). By Lemma A.9 and union bound, we know that for any & i p.
| &
40m log
Tello & 40m logp
B
T ll
4B20m log
(F.19)
with probability at least -22m
54

---

Published as a conference paper at ICLR 2020
Calculating R1 and Rg in Equation (F.3).
For simplicity, let g = Az. First of all, we have
(T))
1
Pat
3 q
E)
EE
() I pat
30(1
0)
(q E)*
2
39E
(q {aT&)²
3)² r
38(1 8)
4
|||] < 30(1 0) ||||| [
4
<
64.*
OK3 log" p.
30(1
3(1 0)
On the other hand, by Lemma E.7, we have
E [ '1 = | [[((T] (4 [x]] < [B[G(() [[(( [()3)]] & c.OKmm
for some numerical constant C1 > 0. In summary, we obtain
R1 = 64
OK m2 log' p.
R₂ akt.m.
(F.20)
3(1 0)
Calculating Ly in Equation (F44. For any Qı, Q2 E gn-1, we have
lfq. (T)
fqz [T)
3 (11 E)
EC - -(qT 1 pot -aat
3 (3 E) EC
- E) r Pat
30(1 8)
Paj (ql E)
2 EC Pap Pat
(92E) 2 EE Pa:
+ 30(1 0)
(ql E) 4 q -
4 - E)
Pa
0(1 0)
where by Lemma A,1 we have
Ti
Pa
E)
E
P
P
(q) E)
EE
P 42
P qi
EqT=) EE P -Pat
(q E) EE Pa
41
E
P qi
Pa
+
Pot
(ql E) EE
P (q: E)
EE
+
Pat (qz E)
EE
P (q E) 2 EE
< E
P
Pat
+ [ (ql + [ (q [ - E)
< E
4 |19 - d2l
& 4 ||||| |a||
gell & 64K² B² m log 11q1 92l
and
To <
((TTE) Pot (q E) p
+ (9 E)
Put (q E) Paz
< (( 2 + (q {) (q) + 42)
EE
(q) 92) + 2 [
1 |1 92l
< 6|| |qq - dell < 6 ||A|
| ||
q2l
< 96K2 B 0² m² log p p|qi - q2ll
where for the last inequality we used Equation (F.19). Therefore, have
960
Il (z)
(+)
<
1-0
k² 3mm² m2 log² p pllq: - q2l
so that
969
Lf
1-0 K2 BAm² log² p.
(F21)
Calculating By and Ly in Equation (F.I). We have
[E [=)]]]]]]]
Pg 3A 3A diag (5 AT - -I151 1] Pg
3. diag (5 A |c|1 z|
< 3 ||/
||A
e 8 +
||A| 4 < K (3M² + K),
55

---

Published as a conference paper at ICLR 2020
where
|A] maxis |ax & M. On the other hand, for any q1. 92 E S"-1, we have
| [g (x)]
E g (z)]]
=l|Pat 3A diag (cP²) A -13 I Pot -
3A diag (c.
A -IKalll I Pas
Pat - Pat A diag (cx²) < Pat diag (c9²) A
A Pg
45
+
|s2 Paf - -12lll Paj
By direct calculation, we have
L1
< Pat A diag (cP2)
A
A Adig (2) A pa
95
42
< Pqt diag
(CP2)
A
Pgt
Paj )| + P पト diag (5P²) - p3j A diag (c A Pgp
|
2 1
P
p
+ |A||
P - Pat A diag
(5P²) )| + P A diag (5 (
& 2 ||
|/q: - Q2
+ ||| //1 !9- q2ll
+ ||A [1 + Colloo Is1 C2 00
< 6 |||
||A
e g 1q
2
-2ll
& 6KM2 1q1 921.
and
L2 < |G
Pot P
|cal -Ksell Pat
< 2 ||| + ||
92ll
|||1|| | ((1 (1 (1sil1 1K<2ll1)
< 2 | ||q1
q2ll
|[1 -22l (1aal + [l(al) (1sil1 +1</l??)
< 6 ||| ||q - q2ll
= 6K² | - 42l
These together give us
[L (a)] - E [3)
& 6K (K + M²) 1q: q2ll
Summarizing everything together, we have
B K (3M² + K).
L 6K (K + M²).
(F:22)
Final calculation.
Finally, we are now ready to put all the estimations in Equations (F.20) to (F.22) together and apply Theorem F.1 obtain our result. For any d (0, 6 R2 R4 whenever
p C8
C8-20K' n0 log (0Kn/ō),
we have
1 P
sup g=8n-1
- Σ
fz(z;) B[fa(}]]
< 6,
p i=1
holding with probability at least (npp -2 log(0Kn//))
20m for some constant C12 C >>> 0.
Lemma E7 Suppose 0 ( 1). Let (x) be defined as in Equation (F.18). We have [fg [[(x))))(({)]]] & CK*0m²
for some numerical constant > 0.
Proof Let x =b@g g with b Ber(O) and g N(O, First, let E Ax. we have
[E [ fx(x)]] E 9 (qT)) PA EE EE Pa- 6 E) P P.IEEPat
+ {E Pa-
9 E (q =) EA EE P +6 P E
(q E) EE
Pa
+ E
(q E)
To
Ta
Ts
56

---

Published as a conference paper at ICLR 2020
Bound
Ti B ((T
E) P. EE Pai EE P.
< B (q 8) EE Pa EET]|
B. [ 5) Pai 35
(a E) [(51")] & (R(q g)))))) [E|(S) $ 1/2
$ E
(P
1/2
(mm)
E
[( [<xTT)))]]]
1/2
where
E (PIA' q. ) I1 v7!! Bz PIAT 1)²²
C10 (m)
(F.23)
the proof of the last inequality is omitted, more details can be found in Lemma F.5, and
E x T Φ ]
E PPIx, Pra)
IE (P 92
c + 22 + cam2 + cam+ot.
(F:24)
combine, equation F.23 and equation F.24, yield
Ti x C1 m²
E (q E) 6 E5"
q E) 6 EE
(q E) G
< {E(q" (E(qTE) 1) (El1" 1/2
T2
Pat <
= E
(E<AA q, 2
12 1/2
TE
1/2 - (Pr A q). 9) )) |Ax||
12)
1/2
E(x T x:)
1/2
& C2 |PI(A 2)
1/2
m (m)
(3m0 + m(m 1)02)
1/2
C202m m
m
the proof of the first inequality in the last line is omitted, more details can be found in Lemma F.5.
Ts = E <P (A Hence, summarizing all the results above, we obtain
< CsEz || ()
< C301Al
C3f m
COm² 2 E [[([))][[x{)]]]]]
m
as desired.
Lemma E8 (Expectation of Hess (-)) Vg Sn-1, 1, the expectation of Hess (DL(.)
(-) satisfies
Hess (q) = Hess (p)(4) = P. 3A diag ((A) AT - Pg-
Proof Direct calculation.
F.3 CONCENTRATION FOR CONVOLUTIONAL DICTIONARY LEARNING
In this section, show concentration for the Riemannian gradient and Hessian of the following objective for convolutional dictionary learning,
1
1
@CDL(q)
4
TAXI
AX,
120 (1 0) np
120 (1 0) mp
with
C
X
X
X₂
X,h,
X;
(F:25)
C
57

---

Published as a conference paper at ICLR 2020
we introduced in Section 3, where Ziy follows i..d. BG( distribution as in Assumption E.2. Since Cæ., is a circulant matrix generated from Zty, it should be noted that each row and column of X is not statistically independent, that concentration result of dictionary learning in the previous subsection does not directly apply here. However, from Lemma D.I, asymptotically we still have
0
- 1 pr(g) = - [
K2 Ex (FCDL = (r(()) 2(1 0)
the following we prove finite sample concentration of (CDI.(q) to expectation (PT(4) by leveraging our previous results for overcomplete dictionary learning in Proposition F.3 and Proposition F.6.
F.3.1 CONCENTRATION FOR grad (CDL(-)
Corollary F9 (Concentration of grad (-DL()) Suppose A satisfies Equation (F.9) and X Rmxnp is generated as in Equation (F.25) with Zij iiid (G( (1 & & p. & & K)
and 0 E ( 1). For any given å E (0, ck / log" pog np)), whenever
10k
> C6 log
we have
sup ge83-1
Igrad (CDL - grad pp((g)] <
holds with probability at least 222 Here, c, C' are some numerical constants.
Remark. Note that our prove have not utilized the convolutional structure of the problem, so that our sample complexity could be loose of factor of order n.
Proof Let us write
- 1 [1
X;
322
3mn] with Tey
T & n,
S
[
(F:26)
where [-] denotes circulant shift of length e. Thus, the Riemannian gradient of PCDL (q) can be written as
P
1
grad (q) 30(1
P
A.t.s))
(A...)
m)
P
(q A (A
n
30 [1
0)P
:=1
grad, (enr.(g)
so that for each with j n,
grad, (q) 30(1 0)p Pat (q A (Awx))
a summation of independent random vectors across Hence, we have
" sup 9ES
ggadd, (CDL(g) grad (p((a)))
sup (CDL(q) grad))(g)) -=S
where for each we can apply concentration results in Proposition F.3 for controlling each individual quantity ||grad, PCDI grad upT(4)) Therefore, by using a union bound we can obtain the desired result.
58

---

Published as a conference paper at ICLR 2020
Table 1: Gradient for each different loss function
Problem
Overcomplete Tensor
ODL
CDL
Loss (pq)
-4 A q
1 Ap
Y gli
===1
y 9
Gradient Vg((g)
A [ q
Y (Y q)
03
y
y q
63
np
F.3.2 CONCENTRATION FOR Hess (-DL(-)
Corollary F.10 (Concentration of Hess (CDL(-)) Suppose A satisfies Equation (F.9) and X Rmxap is generated as Equation (F.25) with Zij wiid. (G (1 & & p. & & K) and
DE (L) m 2)
For any given 6 E (0, ck2 (/K22(n) 7/m log" p plog" np)). whenever
> 28 log (0Kn/o),
we have
sup Hess (q) - Hess pp(()) < ge3r
holds with probability at least cnp-2 Here, e, c, C' are some numerical constants.
Proof Similar to the proof of Corollary F.9, the Riemannian Hessian of (CDL(C) be written
Hess (c)
1
12
Pq- 3 3
Aaa))) Ax (Attg) (q Tg A I Pat
30(1
0)p
1 a
p
Pau
3 (q Aw.y)) Aa, (At..y) (q Aw:,) )01)))111 Pa
7
30(1
0)p
Hess, (CDL(O)
so that for each j with 1 < n,
Hessy (q)
1
3 3 A Ar (Ati.)) (q Aw:ss) I Pa
30(1 0)P
a summation of independent random vectors across Hence, we have
n sup 9E8
sup geg--1
|[Hess (g) Hess (p()))
Hessy (q) Hess spr (q)]
where for each we apply concentration results in Proposition F.6 for controlling each individual quantity [[Hessy @CDL Hess upr(q))) Therefore, by using a union bound we can obtain the desired result.
G OPTIMIZATION ALGORITHMS
G.1 OPTIMIZATION
In this part of the appendix, we introduce algorithmic details for optimizing the following problem min cp(g).
E gn-1
where the loss function spq) and its gradient Vg((g) for different problems are listed in Table 1.
59

---

Published as a conference paper at ICLR 2020
Algorithm 2 Projected Riemannian Gradient Descent Algorithm
Input: Data Y R
Output: the vector
Initialize the iterate q0)) randomly, and set stepsize -())
2: while not converged do
3: Compute Riemannian gradient grad ((g(A)) = P(aai) V)(((()).
4: Update the iterate by
q (++1) Pan-1 (q 7(k) grad ((q()))
5:
Choose new stepsize 7(k+1), and set k + 1.
6: end while
Algorithm 3 Power Method
Input: Data Y E R=x
Output: the vector q-
I: Randomly initialize the iterate (º)
2: while not converged do
3: Compute the gradient (k))
4: Update the iterate by
q (k+1) = Psn-1 (-vp(g(t)))
5: Set k: < + 1.
6: end while
Riemannian gradient descent. To optimize the problem, the most natural idea is starting from a random initialization, and taking projected Riemannian gradient descent steps
Pan-1 (q
grad (q)):
grad pp()) Pyt Vip(g).
(G.1)
where T is the stepsize that can be chosen via linesearch or set as small constant. We summarize this simple method in Algorithm 2.
Power method. In Algorithm 3 we also introduce a simple power method Journée et al. (2010) by noting that the loss function (p(q) is concave so that the problem is equivalent maximizing convex function. For each iteration, we simply update by
P (-V
which is parameter-free and enjoys much faster convergence speed. We summarized the method in Algorithm 3. Notice that the power iteration can be interpreted as the Riemannian gradient descent with varied step sizes in the sense that
Pgn-1 (q T grad p(q)) Pgn-1 (-VVp(() + (1-T T V+(()) g) Pgn-1 (- (-)))
=
by setting T = Volgg
G.2 FAST IMPLEMENTATION OF CDL VIA FFT
Given the problem setup of CDL in Section 3, in the following we describe more efficient implemen- tation of solving CDL using convolution and FFTs. Namely, we show how to rewrite the gradient of (CDIL(g) in the convolutional form. Notice that the preconditioning matrix can be rewrite
limilar approach also appears in (Zhai al., 2019).
60

---

Published as a conference paper at ICLR 2020
circulant matrix by
-1/2
-1/2
2 P = Onp
y. y
F diag (p) F = Cp:
F-1
01 O2
Onp
where Ds = Fy.. Thus, we have
PC
CyCu.
CpEv.
Cyf'
y p yi.
so that
min (PDD
Σ
c
pey. All
y 2
s.t. q qE gES-!
4mp
4mp
Thus, we have the gradient
V (g)
Σ up
y
y
1-1
where e denote a cyclic reversal of any v E R", i.e.,
[Vi, Unyy Un- 02
61


Reviews:
[{"review_id": "rJe375X3KB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "[Summary]\nThis paper studies the problem of non-convex optimization for Dictionary Learning (DL) in the situation when the underlying dictionary is over-complete (more basis vectors m than the dimension n). The paper proves that the L4 maximization formulation has a nice global landscape and can be efficiently minimized by (Riemannian) gradient descent, when the over-complete ratio m/n is less than an absolute constant. A similar result is proved for convolutional dictionary learning.\n\n[Pros]\nThe theoretical results in this paper provides a solid improvement over the prior understandings on overcomplete DL, a setting that is practically important yet theoretically more challenging than standard orthogonal/complete DL. \n\nSpecifically, the prior work of (Ge & Ma 2017) shows only a nice local optimization landscape when m > n^{1+\\eps} and hypothesizes that the global landscape is bad in the same setting (there exists bad local minima out of a certain sub-level set). In comparison, this work proves that at least for m/n <= 3 (roughly), the landscape is globally benign (has the strict saddle property), therefore providing a new understanding that the benign landscape is still preserved from “the other side” where m/n grows mildly above 1. The analysis contains novel technicalities and can be of general interest for understanding the landscape of non-convex problems.\n\nThe paper also provides experimental evidence that gradient descent converges globally up until m = O(n^2), a broader regime than suggested by the theory (m <= 3n). (Though when m >= n^{1+\\eps}, the reason of global convergence from random init may be far from the present theory, in that there can be potentially exponentially many bad local min yet gradient descent won’t get trapped.)\n\n[Cons]\nIt is still a bit disturbing to see that m/n needs to be bounded by a fixed absolute constant, rather than *any* constant, for the theory to work. From the proofs it seems like this constant (3) may have the potential to be improved, but it is not quite easy to completely get rid of it? \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "BygCupVAYH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the dictionary learning problem for two popular settings involving sparsely used over-complete dictionaries and convolutional dictionaries.\n\nFor the over-complete dictionary setting, given the measurements of the form $Y = A X$, where $A$ and $X$ denote the over-complete dictionary and the sparse coefficients, respectively, the paper explores an $\\ell^4$-norm maximization approach to recover the dictionary $A$. This corresponds to maximizing $\\|q^TY\\|^4_4$ over $q \\in \\mathbb{S}^{n-1}$. Interestingly, the paper shows that when $A$ is unit norm tight frame and incoherent the optimization landscape of the aforementioned non-convex objective has strict saddle points that can be escaped by along negative curvature. Furthermore, all local minimizers are globally optimal which are close to one of the columns of $A$. This shows that any descent method that can escape the saddle points will (approximately) recover one of the columns of $A$. \n\nFor convolution dictionaries, the paper shows that when the underlying filters are incoherent a suitably modified $\\ell^4$-norms based objective has only strict saddles over a sub-level set. Furthermore, all local optimizers within this sub-level set are close to one of the convolution filters. \n\nThe reviewer believes that this paper presents many interesting and novel results that extend our understanding of provable methods for dictionary learning. As claimed in the paper, this the first global characterization for the non-convex optimization landscape for over-complete dictionary learning. Besides, the paper provides the first provable guarantees for convolution dictionary learning. Overall, the paper is very well written and the key ideas used in the paper are nicely explained in the main body of the paper. The experimental results in the paper also corroborate the theoretical findings of the paper.\n\nMinor comments:\n\n1. In page 2, \"....can be simply summarized by the following slogan.\" ---> \"....can be simply summarized by the following statement.\"?\n\n2.  In page 7, replace \"cook up\" with \"propose\"?\n\n------------------------------\nAfter rebuttal\n\nThank you for the response. Releasing the code for reproducibility purposes is certainly a great idea.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "ByeYfqGlcH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors consider two problems: Overcomplete dictionary learning (ODL)\nand convolution dictionary learning (CDL).\nDictionary learning learns a matrix factorization of the data\nY = A X\nwhere A is the dictionary and X is the (known to be sparse) code.\nY consists of n rows (sample size) and p columns (dimension).\nIn the overcomplete version A is n x m where m > n, i.e. the number of learned\nfeatures is larger than the sample size.\nThe CDL problem is a special case of the ODL problem where the dictionary\nmatrix is known to consist of convolution filters instead of being unstructured.\n\nThe authors show that under a given set of assumptions local nonconvex\noptimization can be used to find globally relevant solutions.\nThe basic assumptions are:\n(i) unit norm tight frame\n(ii) mu-incoherence\n\t(relates the angles of the columns of a, e.g.\\ if columns are orthogonal,\n\tthey are incoherent / have small mu)\n(ii) stochastic model of the code X that says entries are Gaussian and sparse\n\taccording to a Bernoulli random variable\nThe authors present the idea of maximizing the l^4 norm of A^T q in order to\nfind q as rows of A.\nApparently l^4 norm maximization leads to \"spikiness\" which is exactly\ndesirable under mu-incoherence.\n\nThe authors show (assuming p \\to \\infty) that the optimization nonconvex\nlandscape (constrained to the sphere) does not contain any stationary points\nwithout negative curvature.\nA saddle avoiding optimizer therefore converges to local minimizers from\nrandom initialization.\n\nThe authors also show that the analysis extends to CDL via a preconditioned\ninitializer.\nFinally, they go on to briefly show some experiments that further validate\nthe theory presented in the paper.\n\nOverall, the authors present a rigorous technical analysis using powerful\nmathematical tools for nonconvex optimization (which is relevant to many\nmachine learning problems).\n\nI am recommending to accept based on the high quality of the work.\nBut I am not confident as to the accessibility of the paper to the wide\naudience of ICLR as it is rather technical.\nPerhaps, the complete contribution would be better suited as a journal article.\n\nNotes:\nIt would have been useful to give some more intuition about what \"spikiness\"\nof A^T q is, why spikiness exists under mu-incoherence and why l^4 norm\nmaximization improves spikiness.\n\nI am not sure that the inclusion of the CDL problem is beneficial for a\nconverence paper and would rather have more space allocated to the intuition on\nwhy the method works for ODL.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper investigates the use non-convex optimization for two dictionary learning problems, i.e., over-complete dictionary learning and convolutional dictionary learning. The paper provides theoretical results, associated with empirical experiments, about the fact that, that when formulating the problem as an l4 optimization, gives rise to a landscape with strict saddle points and as such, they can be escaped with negative curvature. As a result, descent methods can be used for learning with provable guarantees. All reviews found the work extremely interesting, highlighting the importance of the results that constitute "a solid improvement over the prior understandings on over-complete DL" and "extends our understanding of provable methods for dictionary learning". This is an interesting submission on non-convex optimization, and as such of interest to the ML community of ICLR . I'm recommending this work for acceptance.
Decision: Accept (Talk)