Simple, Efficient, and Neural Algorithms for Sparse Coding

By Sanjeev Arora, Rong Ge, Tengyu Ma, Ankur Moitra. 2015

200 citations recorded by the source corpus.

Sparse coding is a basic task in many fields including signal processing, neuroscience and machine learning where the goal is to learn a basis that enables a sparse representation of a given set of data, if one exists. Its standard formulation is as a non-convex optimization problem which is solved in practice by heuristics based on alternating minimization. Re- cent work has resulted in several algorithms for sparse coding with provable guarantees, but somewhat surprisingly these are outperformed by the simple alternating minimization heuristics. Here we give a general framework for understanding alternating minimization which we leverage to analyze existing heuristics and to design new ones also with provable guarantees. Some of these algorithms seem implementable on simple neural architectures, which was the original motivation of Olshausen and Field (1997a) in introducing sparse coding. We also give the first efficient algorithm for sparse coding that works almost up to the information theoretic limit for sparse recovery on incoherent dictionaries. All previous algorithms that approached or surpassed this limit run in time exponential in some natural parameter. Finally, our algorithms improve upon the sample complexity of existing approaches. We believe that our analysis framework will have applications in other settings where simple iterative algorithms are used.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Representation & Self-Supervised Learning, Optimization & Training, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Representation & Self-Supervised Learning

In Optimization & Training

In Signal Processing

Citations in the corpus

Train faster, generalize better: Stability of stochastic gradient descent (2015, background): “(Arora et al., 2015) show that two-layer sparse coding dictionaries can be learned via stochastic gradient.”
On exponential convergence of SGD in non-convex over-parametrized learning (2018, background): “Some notable examples satisfying RSI include two-layer neural networks [7], matrix completion [13], dictionary learning [2], and phase retrieval [3].”
Why Do Similarity Matching Objectives Lead to Hebbian/Anti-Hebbian Networks? (2017, methodology): “(19), follow from alternating optimization (Olshausen et al., 1996; Olshausen and Field, 1997; Arora et al., 2015) of l PSP,t .”
Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions (2016, background): “dictionary learning [1], latent-variable models [28], matrix completion [9], and phase retrieval [2]).”
Complete dictionary recovery over the sphere (2015, methodology): “[9, 10] and [11, 12] have subsequently given efficient algorithms for the overcomplete setting (m ≥ n), based on a combination of {clustering or spectral initialization} and local refinement.”
Gradient Descent Only Converges to Minimizers (2016, background): “, phase retrieval (Candes et al., 2015; Cai et al., 2015), dictionary learning (Arora et al., 2015), and latent-variable models (Zhang et al., 2014; Belkin et al., 2014).”
Natasha 2: Faster Non-Convex Optimization Than SGD (2017, background): “However, one-point convexity is only known to apply to relatively simpler nonconvex tasks such as matrix completion [44], dictionary learning [11], phase transition [14] and a two-layer neural network [31], but not for complicated tasks such as training a deep neural network.”
Online Representation Learning with Multi-layer Hebbian Networks for Image Classification Tasks (2017, methodology): “Two important properties of brain-inspired models, namely competitive learning [3] and sparse coding [4, 5] can be performed using Hebbian and anti-Hebbian learning rules.”
Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems (2015, background): “(38) Here, one has (4− )‖h‖2 in (37) instead of 4‖h‖2 to account for the bias introduced by adaptive trimming, where is small as long as we only throw away a small fraction of data.”
Gradient Descent Converges to Minimizers (2016, background): “We remark that the strict saddle assumption is necessary in the worst case, due to hardness results regarding testing the local optimality of functions whose Hessians are highly degenerate at criticalpoints (e.g, quartic polynomials) [19].”
Provable Alternating Gradient Descent for Non-negative Matrix Factorization with Strong Correlations (2017, unknown): “Inverse decoding was also used in (Li et al., 2016; Arora et al., 2015; 2016).”