7 papers
Scalable Second-order Riemannian Optimization for -means Clustering
Peng Xu, Chun-Ying Hou, Xiaohui Chen +1
Clustering is a hard discrete optimization problem. Nonconvex approaches such as low-rank semidefinite programming (SDP) have recently demonstrated promising statistical and local…
Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certification
Gavin Zhang, Salar Fattahi, Richard Y. Zhang
We consider using gradient descent to minimize the nonconvex function over an factor matrix , in which is an underlying smooth convex cost fun…
Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorization
Gavin Zhang, Salar Fattahi, Richard Y. Zhang
In practical instances of nonconvex matrix factorization, the rank of the true solution is often unknown, so the rank of the model can be overspecified as $r>r^{\st…
Simple Alternating Minimization Provably Solves Complete Dictionary Learning
Geyu Liang, Gavin Zhang, Salar Fattahi +1
This paper focuses on the noiseless complete dictionary learning problem, where the goal is to represent a set of given signals as linear combinations of a small number of atoms fr…
Complexity of Chordal Conversion for Sparse Semidefinite Programs with Small Treewidth
Richard Y. Zhang
If a sparse semidefinite program (SDP), specified over matrices and subject to linear constraints, has an aggregate sparsity graph with small treewidth, then ch…
Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization
Richard Y. Zhang
We consider minimizing a twice-differentiable, -smooth, and -strongly convex objective over an positive semidefinite matrix , under the assumptio…