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 ℓ 4 -norm optimization problems over the sphere, and study the geometric properties 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.
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.