Efficient Dictionary Learning with Gradient Descent

Understand

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.