Dropping Convexity for Faster Semi-definite Optimization

By Srinadh Bhojanapalli, Anastasios Kyrillidis, Sujay Sanghavi. 2015

183 citations recorded by the source corpus.

We study the minimization of a convex function $f(X)$ over the set of $n\times n$ positive semi-definite matrices, but when the problem is recast as $\min_U g(U) := f(UU^\top)$, with $U \in \mathbb{R}^{n \times r}$ and $r \leq n$. We study the performance of gradient descent on $g$---which we refer to as Factored Gradient Descent (FGD)---under standard assumptions on the original function $f$. We provide a rule for selecting the step size and, with this choice, show that the local convergence rate of FGD mirrors that of standard gradient descent on the original $f$: i.e., after $k$ steps, the error is $O(1/k)$ for smooth $f$, and exponentially small in $k$ when $f$ is (restricted) strongly convex. In addition, we provide a procedure to initialize FGD for (restricted) strongly convex objectives and when one only has access to $f$ via a first-order oracle; for several problem instances, such proper initialization leads to global convergence guarantees. FGD and similar procedures are widely used in practice for problems that can be posed as matrix factorization. To the best of our knowledge, this is the first paper to provide precise convergence rate guarantees for general convex functions under standard convex assumptions.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

In Mathematical Optimization

Citations in the corpus

Recovery guarantee of weighted low-rank approximation via alternating minimization (2016, background): “Finally, two related works are [Bhojanapalli et al., 2015a,b].”
Global Optimality of Local Search for Low Rank Matrix Recovery (2016, unknown): “[2] considered gradient descent methods on the factor space and proved local convergence.”
An Overview of Low-Rank Matrix Recovery From Incomplete Observations (2016, unknown): “Convergence analysis for closely related local descent methods can be found in the recent works [13,134].”
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, methodology): “We have also left out several important nonconvex problems and methods in order to stay focused, including but not limited to (1) blind calibration and finding sparse vectors in a subspace [203]–[205]; (2) tensor completion, decomposition and mixture models [140], [206]–[209]; (3) parameter recovery”
No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis (2017, background): “Bhojanapalli et al. [2015] gave a framework for local analysis for these low rank problems.”
Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow (2016, methodology): “First, in parallel with spectral initialization methods, the proposed orthogonality-promoting initialization can be applied for semideﬁnite optimization [38], [62], matrix completion [63], [41], as well as blind deconvolution [39], [40].”
The non-convex geometry of low-rank matrix optimization (2016, background): “The past two years have seen renewed interest in the Burer-Monteiro factorization for solving low-rank matrix optimization problems [4, 24, 25, 36, 37, 53].”
Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization (2021, background): “…ﬁrst uses spectral initialization to ﬁnd a near-optimal solution, then starting from there, gradient descent converges to an optimum with a linear rate [Tu et al., 2016, Zheng and Lafferty, 2016, Zhao et al., 2015, Bhojanapalli et al., 2016], though in practice random initialization often sufﬁces.”