# Local Linear Convergence of Gradient Methods for Subspace Optimization via Strict Complementarity

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 36 references that are in the map.
- First posted on arXiv 8 Feb 2022.

## Builds on (most cited first, 17 of 17)

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees](https://mlsanity.com/paper/1509.03025/) (2015)
- [Error bounds, quadratic growth, and linear convergence of proximal methods](https://mlsanity.com/paper/1602.06661/) (2016)
- [Dropping Convexity for Faster Semi-definite Optimization](https://mlsanity.com/paper/1509.03917/) (2015)
- [An Overview of Robust Subspace Recovery](https://mlsanity.com/paper/1803.01013/) (2018)
- [Finding Low-Rank Solutions via Non-Convex Matrix Factorization, Efficiently and Provably](https://mlsanity.com/paper/1606.03168/) (2016)
- [Fast, Robust and Non-convex Subspace Recovery](https://mlsanity.com/paper/1406.6145/) (2014)
- [A Well-Tempered Landscape for Non-convex Robust Subspace Recovery](https://mlsanity.com/paper/1706.03896/) (2017)
- [List Decodable Subspace Recovery](https://mlsanity.com/paper/2002.03004/) (2020)
- [Fast Stochastic Algorithms for SVD and PCA: Convergence Properties and Convexity](https://mlsanity.com/paper/1507.08788/) (2015)
- [On the Convergence of Projected-Gradient Methods with Low-Rank Projections for Smooth Convex Minimization over Trace-Norm Balls and Related Problems](https://mlsanity.com/paper/1902.01644/) (2019)
- [Spectral Frank-Wolfe Algorithm: Strict Complementarity and Linear Convergence](https://mlsanity.com/paper/2006.01719/) (2020)
- [Linear Convergence of Frank-Wolfe for Rank-One Matrix Recovery Without Strong Convexity](https://mlsanity.com/paper/1912.01467/) (2019)
- [Dimensionality Reduction for Binary Data through the Projection of Natural Parameters](https://mlsanity.com/paper/1510.06112/) (2015)
- [Global Convergence of a Grassmannian Gradient Descent Algorithm for Subspace Estimation](https://mlsanity.com/paper/1506.07405/) (2015)
- [Randomized Robust Subspace Recovery for High Dimensional Data Matrices](https://mlsanity.com/paper/1505.05901/) (2015)

## Abstract (arXiv)

We consider optimization problems in which the goal is find a k-dimensional subspace of ℝn, k<<n, which minimizes a convex and smooth loss. Such problems generalize the fundamental task of principal component analysis (PCA) to include robust and sparse counterparts, and logistic PCA for binary data, among others. This problem could be approached either via nonconvex gradient methods with highly-efficient iterations, but for which arguing about fast convergence to a global minimizer is difficult or, via a convex relaxation for which arguing about convergence to a global minimizer is straightforward, but the corresponding methods are often inefficient in high dimensions. In this work we bridge these two approaches under a strict complementarity assumption, which in particular implies that the optimal solution to the convex relaxation is unique and is also the optimal solution to the original nonconvex problem. Our main result is a proof that a natural nonconvex gradient method which is textitSVD-free and requires only a single QR-factorization of an n× k matrix per iteration, converges locally with a linear rate. We also establish linear convergence results for the nonconvex projected gradient method, and the Frank-Wolfe method when applied to the convex relaxation.