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

Ron Fisher, Dan Garber

The Subspace Optimization Dilemma

Subspace optimization is fundamental to data science, serving as the backbone for Principal Component Analysis (PCA) and its robust, sparse, and logistic variants. The goal is to find a $k$-dimensional subspace in $\mathbb{R}^n$ (where $k \ll n$) that minimizes a convex and smooth loss.

While standard PCA is easily solved via Singular Value Decomposition (SVD), modern variants designed to handle outliers or improve interpretability present a significant computational challenge. Researchers typically face a trade-off between two paths:

  • The Nonconvex Path: Computationally cheap per iteration, but mathematically "wild"—it is difficult to prove the algorithm won't get stuck in a local minimum.
  • The Convex Path: Relaxes the problem into a convex one by optimizing over a set called the "Fantope." This guarantees global convergence but is computationally expensive, often requiring full SVDs of large $n \times n$ matrices.

Bridging the Gap: Strict Complementarity

This paper bridges the gap between these two paradigms. The authors demonstrate that under a strict complementarity assumption, the unique optimal solution to the convex relaxation is identical to the optimal solution of the original nonconvex problem.

In optimization theory, strict complementarity implies a distinct "gap" between the $k$-th and $(k+1)$-th eigenvalues of the gradient at the optimal solution. When this gap exists, the nonconvex landscape behaves favorably near the optimum. This theoretical bridge justifies using highly efficient nonconvex methods to solve what is fundamentally a convex problem.

Gradient Orthogonal Iteration (GOI)

To capitalize on this bridge, the study focuses on a specific algorithm known as Gradient Orthogonal Iteration (GOI).

Unlike standard Projected Gradient Descent (PGD), which requires an expensive SVD at every step to project back onto the manifold of projection matrices, GOI is entirely SVD-free. It executes a simple gradient step followed by a QR factorization of an $n \times k$ matrix. Because $k \ll n$, this reduces the per-iteration computational complexity from $O(n^3)$ to $O(nk^2)$, offering massive speedups for high-dimensional data.

Experimental Validation and Key Results

The authors evaluated their approach using synthetic datasets, including a Spiked Covariance Model (where a low-rank signal is buried in noise) and a Sparsely Corrupted Entries Model (testing robustness via the Huber loss function). Experiments with $n=100$ dimensions, a $k=10$ dimensional subspace, and $m=500$ samples yielded several critical insights:

  • Theoretical Guarantee: The paper provides the first proof of local linear convergence for the SVD-free GOI algorithm under strict complementarity.
  • Computational Speedup: In numerical simulations, GOI achieved the exact same accuracy as PGD but in significantly less wall-clock time due to the avoidance of heavy SVD computations.
  • Robustness: By utilizing the Huber loss—a smooth, convex loss less sensitive to outliers than squared error—the proposed methods successfully handled noisy environments, vastly outperforming naive PCA.
  • The Importance of Warm Starts: The linear convergence guarantee is local. The authors show that initializing the algorithm with a single standard PCA step provides a "warm start" that immediately places the optimization process into the fast, exponentially decaying local linear convergence regime.

Limitations and Future Directions

While the theoretical and practical results are strong, the reliance on a warm start means that if the initial guess is too far from the truth, the convergence guarantees do not hold. Determining the exact "radius of attraction" for various loss functions remains an open question.

Additionally, the convergence rate is highly sensitive to the eigengap ($\delta$); a weak signal with a tiny gap will naturally slow down convergence. Finally, the current analysis is deterministic. Extending these proofs to stochastic gradient methods—where only a mini-batch of data points is processed at a time—would be a vital next step for scaling these robust PCA techniques to massive, real-world datasets.

Summary updated

Abstract

We consider optimization problems in which the goal is to find a $k$-dimensional subspace of $\mathbb{R}^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 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 \textit{SVD-free} and requires only a single QR-factorization of an $n\times 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.
BibTeX
@inproceedings{fisher2022local,
  author = {Ron Fisher and Dan Garber},
  title = {{Local Linear Convergence of Gradient Methods for Subspace Optimization via Strict Complementarity}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=4MT-e8mn3X},
}
Figure