296 citations · 1.7k across the 43 of their papers we have counts for
9 papers · 1 filter
Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form
Srinadh Bhojanapalli, Nicolas Boumal, Prateek Jain +1
Semidefinite programs (SDP) are important in learning and combinatorial optimization with numerous applications. In pursuit of low-rank solutions and low complexity algorithms, we…
Implicit Regularization in Matrix Factorization
Suriya Gunasekar, Blake Woodworth, Srinadh Bhojanapalli +2
We study implicit regularization when optimizing an underdetermined quadratic objective over a matrix with gradient descent on a factorization of . We conjecture and provide…
Single Pass PCA of Matrix Products
Shanshan Wu, Srinadh Bhojanapalli, Sujay Sanghavi +1
In this paper we present a new algorithm for computing a low rank approximation of the product by taking only a single pass of the two matrices and . The straightforw…
Provable Burer-Monteiro factorization for a class of norm-constrained matrix problems
Dohyung Park, Anastasios Kyrillidis, Srinadh Bhojanapalli +2
We study the projected gradient descent method on low-rank matrix problems with a strongly convex objective. We use the Burer-Monteiro factorization approach to implicitly enforce…
Global Optimality of Local Search for Low Rank Matrix Recovery
Srinadh Bhojanapalli, Behnam Neyshabur, Nathan Srebro
We show that there are no spurious local minima in the non-convex factorized parametrization of low-rank matrix recovery from incoherent linear measurements. With noisy measurement…
Dropping Convexity for Faster Semi-definite Optimization
Srinadh Bhojanapalli, Anastasios Kyrillidis, Sujay Sanghavi
We study the minimization of a convex function over the set of positive semi-definite matrices, but when the problem is recast as , wi…
A New Sampling Technique for Tensors
Srinadh Bhojanapalli, Sujay Sanghavi
In this paper we propose new techniques to sample arbitrary third-order tensors, with an objective of speeding up tensor algorithms that have recently gained popularity in machine…
Universal Matrix Completion
Srinadh Bhojanapalli, Prateek Jain
The problem of low-rank matrix completion has recently generated a lot of interest leading to several results that offer exact solutions to the problem. However, in order to do so,…
Completing Any Low-rank Matrix, Provably
Yudong Chen, Srinadh Bhojanapalli, Sujay Sanghavi +1
Matrix completion, i.e., the exact and provable recovery of a low-rank matrix from a small subset of its elements, is currently only known to be possible if the matrix satisfies a…