Understanding non-convex optimization for sparse coding

  • Tengyu Ma | Princeton University

Sparse coding is a basic algorithmic primitive in many machine learning applications, such as image denoising, edge detection, compression and deep learning. Most of the existing algorithms for sparse coding minimize a non-convex function by heuristics like alternating minimization, gradient descent or their variants. Despite their success in practice, they are not mathematically rigorous because they could potentially converge to local minima. In this work we prove that, alternating minimization and some other variants indeed converge to global minima provably form a suitable starting point, under a generative model and incoherence assumptions on the ground truth codes. We also provide a new spectral-method based initialization procedure that returns such a good starting point. Our framework of analysis is potentially useful for analyzing other alternating minimization type algorithms for problems with hidden variables. No prior knowledge is assumed and this is the joint work with Sanjeev Arora, Rong Ge and Ankur Moitra.

Speaker Details

Tengyu Ma has a bachelor’s degree from Tsinghua University and is currently a second-year graduate student at Princeton University. Previously he won a silver medal at the International Mathematical Olympiad and was ranked 8th at MAA’s Putman Competition. He also received the Simons Award for Graduate Students in Theoretical Computer Science in 2014. Ma’s work seeks to develop efficient algorithms with provable guarantees for machine learning problems. One of his works gives polynomial time algorithms for a class of deep neural networks in the generative model and reveals interesting structures of neural networks with random weights. In another work, Ma and his co-authors showed that dictionary learning/sparse coding can be solved provably by minimizing a certain non-convex function using alternating minimization as well as simple neurally plausible algorithms.

    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks