Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 8: Accept
review_content: The authors consider two problems: Overcomplete dictionary learning (ODL)
and convolution dictionary learning (CDL).
Dictionary learning learns a matrix factorization of the data
Y = A X
where A is the dictionary and X is the (known to be sparse) code.
Y consists of n rows (sample size) and p columns (dimension).
In the overcomplete version A is n x m where m > n, i.e. the number of learned
features is larger than the sample size.
The CDL problem is a special case of the ODL problem where the dictionary
matrix is known to consist of convolution filters instead of being unstructured.

The authors show that under a given set of assumptions local nonconvex
optimization can be used to find globally relevant solutions.
The basic assumptions are:
(i) unit norm tight frame
(ii) mu-incoherence
	(relates the angles of the columns of a, e.g.\ if columns are orthogonal,
	they are incoherent / have small mu)
(ii) stochastic model of the code X that says entries are Gaussian and sparse
	according to a Bernoulli random variable
The authors present the idea of maximizing the l^4 norm of A^T q in order to
find q as rows of A.
Apparently l^4 norm maximization leads to "spikiness" which is exactly
desirable under mu-incoherence.

The authors show (assuming p \to \infty) that the optimization nonconvex
landscape (constrained to the sphere) does not contain any stationary points
without negative curvature.
A saddle avoiding optimizer therefore converges to local minimizers from
random initialization.

The authors also show that the analysis extends to CDL via a preconditioned
initializer.
Finally, they go on to briefly show some experiments that further validate
the theory presented in the paper.

Overall, the authors present a rigorous technical analysis using powerful
mathematical tools for nonconvex optimization (which is relevant to many
machine learning problems).

I am recommending to accept based on the high quality of the work.
But I am not confident as to the accessibility of the paper to the wide
audience of ICLR as it is rather technical.
Perhaps, the complete contribution would be better suited as a journal article.

Notes:
It would have been useful to give some more intuition about what "spikiness"
of A^T q is, why spikiness exists under mu-incoherence and why l^4 norm
maximization improves spikiness.

I am not sure that the inclusion of the CDL problem is beneficial for a
converence paper and would rather have more space allocated to the intuition on
why the method works for ODL.

review_title: Official Blind Review #3

final_score: rating: 8: Accept
review_content: This paper studies the dictionary learning problem for two popular settings involving sparsely used over-complete dictionaries and convolutional dictionaries.

For 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$. 

For 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. 

The 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.

Minor comments:

1. In page 2, "....can be simply summarized by the following slogan." ---> "....can be simply summarized by the following statement."?

2.  In page 7, replace "cook up" with "propose"?

------------------------------
After rebuttal

Thank you for the response. Releasing the code for reproducibility purposes is certainly a great idea.
review_title: Official Blind Review #1

final_score: rating: 8: Accept
review_content: [Summary]
This 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.

[Pros]
The 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. 

Specifically, 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.

The 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.)

[Cons]
It 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? 

review_title: Official Blind Review #2

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)