Provable Burer-Monteiro factorization for a class of norm-constrained matrix problems
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 low-rankness; such factorization introduces non-convexity in the objective. We focus on constraint sets that include both positive semi-definite (PSD) constraints and specific matrix norm-constraints. Such criteria appear in quantum state tomography and phase retrieval applications. We show that non-convex projected gradient descent favors local linear convergence in the factored space. We build our theory on a novel descent lemma, that non-trivially extends recent results on the unconstrained problem. The resulting algorithm is Projected Factored Gradient Descent, abbreviated as ProjFGD, and shows superior performance compared to state of the art on quantum state tomography and sparse phase retrieval applications.
Code (0)
등록된 구현이 없습니다.
Tasks
LEMMAQuantum State TomographyRetrievalSimilar Papers 제목 키워드 기반
Benign landscape for Burer-Monteiro factorizations of MaxCut-type semidefinite programs
We consider MaxCut-type semidefinite programs (SDP) which admit a low rank solution. To numerically leverage the low rank hypothesis, a standard algorithmic approach is the Burer-Monteiro factorization, which allows to s…
Convergence Rate of Block-Coordinate Maximization Burer-Monteiro Method for Solving Large SDPs
Semidefinite programming (SDP) with diagonal constraints arise in many optimization problems, such as Max-Cut, community detection and group synchronization. Although SDPs can be solved to arbitrary precision in polynomi…
Community DetectionA biconvex optimization for solving semidefinite programs via bilinear factorization
Many problems in machine learning can be reduced to learning a low-rank positive semidefinite matrix (denoted as $Z$), which encounters semidefinite program (SDP). Existing SDP solvers by classical convex optimization ar…
Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization
We consider minimizing a twice-differentiable, $L$-smooth, and $\mu$-strongly convex objective $\phi$ over an $n\times n$ positive semidefinite matrix $M\succeq0$, under the assumption that the minimizer $M^{\star}$ has …
Practical Large-Scale Optimization for Max-norm Regularization
The max-norm was proposed as a convex matrix regularizer by Srebro et al (2004) and was shown to be empirically superior to the trace-norm for collaborative filtering problems. Although the max-norm can be computed in po…
ClusteringCollaborative Filtering