# Efficient Dictionary Learning with Gradient Descent

arXiv: https://arxiv.org/abs/1809.10313 · HTML: https://mlsanity.com/paper/1809.10313/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Sep 2018.

## Built on by (most cited first, 10 of 10)

- [The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensing](https://mlsanity.com/paper/2302.01186/) (2023)
- [AbsTopK: Rethinking Sparse Autoencoders For Bidirectional Features](https://mlsanity.com/paper/2510.00404/) (2025)
- [Simple Alternating Minimization Provably Solves Complete Dictionary Learning](https://mlsanity.com/paper/2210.12816/) (2022)
- [Closed-Loop Transcription via Convolutional Sparse Coding](https://mlsanity.com/paper/2302.09347/) (2023)
- [SPEAR++: Scaling Gradient Inversion via Sparsely-Used Dictionary Learning](https://mlsanity.com/paper/2510.24200/) (2025)
- [Efficient Sparse Coding using Hierarchical Riemannian Pursuit](https://mlsanity.com/paper/2104.10314/) (2021)
- [Resource-Efficient Invariant Networks: Exponential Gains by Unrolled Optimization](https://mlsanity.com/paper/2203.05006/) (2022)
- [Exact Sparse Orthogonal Dictionary Learning](https://mlsanity.com/paper/2103.09085/) (2021)
- [LASERS: LAtent Space Encoding for Representations with Sparsity for Generative Modeling](https://mlsanity.com/paper/2409.11184/) (2024)
- [Sharper Convergence Rates for Nonconvex Optimisation via Reduction Mappings](https://mlsanity.com/paper/2506.08428/) (2025)

## Abstract (arXiv)

Randomly initialized first-order optimization algorithms are the method of choice for solving many high-dimensional nonconvex problems in machine learning, yet general theoretical guarantees cannot rule out convergence to critical points of poor objective value. For some highly structured nonconvex problems however, the success of gradient descent can be understood by studying the geometry of the objective. We study one such problem -- complete orthogonal dictionary learning, and provide converge guarantees for randomly initialized gradient descent to the neighborhood of a global optimum. The resulting rates scale as low order polynomials in the dimension even though the objective possesses an exponential number of saddle points. This efficient convergence can be viewed as a consequence of negative curvature normal to the stable manifolds associated with saddle points, and we provide evidence that this feature is shared by other nonconvex problems of importance as well.