Provable Nonconvex Methods/Algorithms

JUN 18TH, 2014

General nonconvex optimization is undoubtedly hard – in sharp contrast to convex optimization, of which there is good separation of problem structure, input data, and optimization algorithms. But many nonconvex problems of interest become amenable to simple and practical algorithms and rigorous analyses once the artificial separation is removed. This page collects recent research effort in this line. (Update: Oct 06 2015)

Problems with Hidden Convexity or Analytic Solutions

These slidessummarize lots of them.

Blind Deconvolution

Blind Deconvolution using Convex Programming(2012)

Separable Nonnegative Matrix Factorization (NMF)

Computing a Nonnegative Matrix Factorization – Provably(2011)

Problems with Provable Global Results

Matrix Completion/Sensing

(See alsolow-rank matrix/tensor recovery)

Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees(2015)

Low-rank Solutions of Linear Matrix Equations via Procrustes Flow(2015)

A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements(2015)

Guaranteed Matrix Completion via Non-convex Factorization(2014)

Fast Exact Matrix Completion with Finite Samples(2014)

Non-convex Robust PCA(2014)

Fast Matrix Completion without the Condition Number(2014)

Understanding Alternating Minimization for Matrix Completion(2013)

Low-rank Matrix Completion using Alternating Minimization(2012)

Matrix Completion from a Few Entries(2009)

Guaranteed Rank Minimization via Singular Value Projection(2009)

Tensor Recovery & Hidden Variable Models

Analyzing Tensor Power Method Dynamics: Applications to Learning Overcomplete Latent Variable Models(2014)

Tensor decompositions for learning latent variable models(2014)

Provable Learning of Overcomplete Latent Variable Models: Semi-supervised and Unsupervised Settings(2014)

Provable Tensor Factorization with Missing Data(2014)

Guaranteed Non-Orthogonal Tensor Decomposition via Alternating Rank-1 Updates(2014)

Phase Retrieval

The Local Convexity of Solving Quadratic Equations(2015)

Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems(2015)

Phase Retrieval via Wirtinger Flow: Theory and Algorithms(2014)

Phase Retrieval using Alternating Minimization(2013)

Dictionary Learning

Complete Dictionary Recovery over the Sphere(2015)

Simple, Efficient, and Neural Algorithms for Sparse Coding(2015)

More Algorithms for Provable Dictionary Learning(2014)

Exact Recovery of Sparsely Used Overcomplete Dictionaries(2013)

New Algorithms for Learning Incoherent and Overcomplete Dictionaries(2013)

Learning Sparsely Used Overcomplete Dictionaries via Alternating Minimization(2013)

Sparse Vectors in Linear Subspaces

(See alsoStructured Element Pursuit)

Nonnegative/Sparse Principal Component Analysis

Non-negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics(2014)

Mixed Linear Regression

Provable Tensor Methods for Learning Mixtures of Classifiers(2014)

Alternating Minimization for Mixed Linear Regression(2013)

Blind Deconvolution

Near Optimal Compressed Sensing of Sparse Rank-One Matrices via Sparse Power Factorization(2013)

Numerical Linear Algebra

Computing Matrix Squareroot via Non Convex Local Search(2015)

Bayesian Inference

On some provably correct cases of variational inference for topic models(2015)

Burer-Monteiro Style Decomposition Algorithms

Global Convergence of Stochastic Gradient Descent for Some Nonconvex Matrix Problems(2014)

Of Statistical Nature …

Provable Sparse Tensor Decomposition(2015)

Statistical consistency and asymptotic normality for high-dimensional robust M-estimators(2015)

Support recovery without incoherence: A case for nonconvex regularizations(2014)

High Dimensional Expectation-Maximization Algorithm: Statistical Optimization and Asymptotic Normality(2014)

Statistical guarantees for the EM algorithm: From population to sample-based analysis(2014)

Nonconvex Statistical Optimization: Minimax-Optimal Sparse PCA in Polynomial Time(2014)

Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima(2013)

High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity(2011)

Relevant Tools/Local Results

Escaping From Saddle Points — Online Stochastic Gradient for Tensor Decomposition(2015)

Proximal alternating linearized minimization for nonconvex and nonsmooth problems(2013)

Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods(2013)

Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka-Łojasiewicz inequality(2008)

Disclaimer- This page is meant to serve a hub for references on this problem, and does not represent in any way personal endorsement of papers listed here. So I do not hold any responsibility for quality and technical correctness of each paper listed here. The reader is advised to use this resource with discretion.

If you’d like your paper to be listed here- Just drop me a few lines via email (which can be found on “Welcome” page). If you don’t bother to spend a word, just deposit your paper on arXiv. I get email alert about new animals there every morning,  and will be happy to hunt one for this zoo if it seemsfit.

Jun 18th, 2014