mlsanityData to 14 Oct 2026

Dropping Convexity for Faster Semi-definite Optimization

arXiv 1509.03917 ↗First posted 14 Sep 2015stat.ML cs.DS cs.ITcited by 40

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 13; 2022: 9; 2023: 4; 2024: 3; 2025: 7; 2026: 4.

40 papers.

Sort:

  1. 2021MARINA: Faster Non-Convex Distributed Learning with Compressioncited by 78
  2. 2021Large Learning Rate Tames Homogeneity: Convergence and Balancing Effectcited by 50
  3. 2021Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorizationcited by 45
  4. 2021On the computational and statistical complexity of over-parameterized matrix sensingcited by 31
  5. 2022Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certificationcited by 21
  6. 2023How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initializationcited by 18
  7. 2021Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorizationcited by 15
  8. 2023Convergence of Alternating Gradient Descent for Matrix Factorizationcited by 12
  9. 2025Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorizationcited by 12
  10. 2022Noisy Low-rank Matrix Optimization: Geometry of Local Minima and Convergence Ratecited by 8
  11. 2024Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descentcited by 7
  12. 2021Factorization Approach for Low-complexity Matrix Completion Problems: Exponential Number of Spurious Solutions and Failure of Gradient Methodscited by 6
28 more
  1. 2022Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completioncited by 6
  2. 2021Fast quantum state reconstruction via accelerated non-convex programmingcited by 5
  3. 2021Sharp Global Guarantees for Nonconvex Low-rank Recovery in the Noisy Overparameterized Regimecited by 5
  4. 2025Probe-Free Low-Rank Activation Interventioncited by 5
  5. 2025Tensor Train Quantum State Tomography using Compressed Sensingcited by 5
  6. 2021Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimizationcited by 4
  7. 2022Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspectivecited by 4
  8. 2021On Geometric Connections of Embedded and Quotient Geometries in Riemannian Fixed-rank Matrix Optimizationcited by 3
  9. 2022Low-Rank Extragradient Method for Nonsmooth and Low-Rank Matrix Optimization Problemscited by 3
  10. 2023Gradient-Based Spectral Embeddings of Random Dot Product Graphscited by 3
  11. 2024Provable Acceleration of Nesterov's Accelerated Gradient for Rectangular Matrix Factorization and Linear Neural Networkscited by 3
  12. 2025When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?cited by 3
  13. 2025One Rank at a Time: Cascading Error Dynamics in Sequential Learningcited by 3
  14. 2021Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensingcited by 2
  15. 2021On Stochastic Variance Reduced Gradient Method for Semidefinite Optimizationcited by 1
  16. 2022Local Stochastic Factored Gradient Descent for Distributed Quantum State Tomographycited by 1
  17. 2022Symphony in the Latent Space: Provably Integrating High-dimensional Techniques with Non-linear Machine Learning Modelscited by 1
  18. 2025Implicit Bias in Matrix Factorization and its Explicit Realization in a New Architecturecited by 1
  19. 2026Tomography by Design: An Algebraic Approach to Low-Rank Quantum Statescited by 1
  20. 2021Momentum-inspired Low-Rank Coordinate Descent for Diagonally Constrained SDPscited by 0
  21. 2022Local Linear Convergence of Gradient Methods for Subspace Optimization via Strict Complementaritycited by 0
  22. 2022Low-Rank Mirror-Prox for Nonsmooth and Low-Rank Matrix Optimization Problemscited by 0
  23. 2023Conic Descent Redux for Memory-Efficient Optimizationcited by 0
  24. 2024LASE: Learned Adjacency Spectral Embeddingscited by 0
  25. 2025Linear Discriminant Analysis with Gradient Optimizationcited by 0
  26. 2026AdaPaD: Adaptive Parallel Deflation for PEFT with Self-Correcting Rank Discoverycited by 0
  27. 2026A Block Tensor Train Burer-Monteiro Framework for Low-Rank Quantum State Tomographycited by 0
  28. 2026On the Regularization Landscape for the Linear Recommendation Modelscited by 0