# Dropping Convexity for Faster Semi-definite Optimization

arXiv: https://arxiv.org/abs/1509.03917 · HTML: https://mlsanity.com/paper/1509.03917/

## Key facts

- Cited by 40 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Sep 2015.

## Built on by (most cited first, 30 of 40)

- [MARINA: Faster Non-Convex Distributed Learning with Compression](https://mlsanity.com/paper/2102.07845/) (2021)
- [Large Learning Rate Tames Homogeneity: Convergence and Balancing Effect](https://mlsanity.com/paper/2110.03677/) (2021)
- [Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization](https://mlsanity.com/paper/2106.14289/) (2021)
- [On the computational and statistical complexity of over-parameterized matrix sensing](https://mlsanity.com/paper/2102.02756/) (2021)
- [Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certification](https://mlsanity.com/paper/2206.03345/) (2022)
- [How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initialization](https://mlsanity.com/paper/2310.01769/) (2023)
- [Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorization](https://mlsanity.com/paper/2102.12430/) (2021)
- [Convergence of Alternating Gradient Descent for Matrix Factorization](https://mlsanity.com/paper/2305.06927/) (2023)
- [Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorization](https://mlsanity.com/paper/2504.09708/) (2025)
- [Noisy Low-rank Matrix Optimization: Geometry of Local Minima and Convergence Rate](https://mlsanity.com/paper/2203.03899/) (2022)
- [Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descent](https://mlsanity.com/paper/2401.11940/) (2024)
- [Factorization Approach for Low-complexity Matrix Completion Problems: Exponential Number of Spurious Solutions and Failure of Gradient Methods](https://mlsanity.com/paper/2110.10279/) (2021)
- [Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completion](https://mlsanity.com/paper/2208.11246/) (2022)
- [Fast quantum state reconstruction via accelerated non-convex programming](https://mlsanity.com/paper/2104.07006/) (2021)
- [Sharp Global Guarantees for Nonconvex Low-rank Recovery in the Noisy Overparameterized Regime](https://mlsanity.com/paper/2104.10790/) (2021)
- [Probe-Free Low-Rank Activation Intervention](https://mlsanity.com/paper/2502.04043/) (2025)
- [Tensor Train Quantum State Tomography using Compressed Sensing](https://mlsanity.com/paper/2506.23560/) (2025)
- [Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization](https://mlsanity.com/paper/2108.01772/) (2021)
- [Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspective](https://mlsanity.com/paper/2209.15130/) (2022)
- [On Geometric Connections of Embedded and Quotient Geometries in Riemannian Fixed-rank Matrix Optimization](https://mlsanity.com/paper/2110.12121/) (2021)
- [Low-Rank Extragradient Method for Nonsmooth and Low-Rank Matrix Optimization Problems](https://mlsanity.com/paper/2202.04026/) (2022)
- [Gradient-Based Spectral Embeddings of Random Dot Product Graphs](https://mlsanity.com/paper/2307.13818/) (2023)
- [Provable Acceleration of Nesterov's Accelerated Gradient for Rectangular Matrix Factorization and Linear Neural Networks](https://mlsanity.com/paper/2410.09640/) (2024)
- [When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?](https://mlsanity.com/paper/2502.16912/) (2025)
- [One Rank at a Time: Cascading Error Dynamics in Sequential Learning](https://mlsanity.com/paper/2505.22602/) (2025)
- [Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing](https://mlsanity.com/paper/2101.05113/) (2021)
- [On Stochastic Variance Reduced Gradient Method for Semidefinite Optimization](https://mlsanity.com/paper/2101.00236/) (2021)
- [Local Stochastic Factored Gradient Descent for Distributed Quantum State Tomography](https://mlsanity.com/paper/2203.11579/) (2022)
- [Symphony in the Latent Space: Provably Integrating High-dimensional Techniques with Non-linear Machine Learning Models](https://mlsanity.com/paper/2212.00852/) (2022)
- [Implicit Bias in Matrix Factorization and its Explicit Realization in a New Architecture](https://mlsanity.com/paper/2501.16322/) (2025)

## Abstract (arXiv)

We study the minimization of a convex function f(X) over the set of n× n positive semi-definite matrices, but when the problem is recast as minU g(U) := f(UU^top), with U ∈ ℝn × r and r ≤ 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.