Understanding non-convex optimization for sparse coding
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.
- Series:
- Microsoft Research Talks
- Date:
- Speakers:
- Tengyu Ma
- Affiliation:
- Princeton University
-
-
Jeff Running
-
Series: Microsoft Research Talks
-
-
-
-
Galea: The Bridge Between Mixed Reality and Neurotechnology
Speakers:- Eva Esteban,
- Conor Russomanno
-
Current and Future Application of BCIs
Speakers:- Christoph Guger
-
Challenges in Evolving a Successful Database Product (SQL Server) to a Cloud Service (SQL Azure)
Speakers:- Hanuma Kodavalla,
- Phil Bernstein
-
Improving text prediction accuracy using neurophysiology
Speakers:- Sophia Mehdizadeh
-
-
DIABLo: a Deep Individual-Agnostic Binaural Localizer
Speakers:- Shoken Kaneko
-
-
Recent Efforts Towards Efficient And Scalable Neural Waveform Coding
Speakers:- Kai Zhen
-
-
Audio-based Toxic Language Detection
Speakers:- Midia Yousefi
-
-
From SqueezeNet to SqueezeBERT: Developing Efficient Deep Neural Networks
Speakers:- Sujeeth Bharadwaj
-
Hope Speech and Help Speech: Surfacing Positivity Amidst Hate
Speakers:- Monojit Choudhury
-
-
-
-
-
'F' to 'A' on the N.Y. Regents Science Exams: An Overview of the Aristo Project
Speakers:- Peter Clark
-
Checkpointing the Un-checkpointable: the Split-Process Approach for MPI and Formal Verification
Speakers:- Gene Cooperman
-
Learning Structured Models for Safe Robot Control
Speakers:- Ashish Kapoor
-
-