Low-Rank Extragradient Method for Nonsmooth and Low-Rank Matrix Optimization Problems

Atara Kaplan, Dan Garber

Matrix optimization problems—such as Robust PCA, sparse PCA, and matrix completion—are fundamental to machine learning and statistics. Often, these tasks require finding a low-rank matrix that satisfies specific constraints, typically formulated as convex optimization problems over the spectrahedron (the set of positive semi-definite matrices with unit trace).

However, these problems present a dual challenge:

  1. Nonsmoothness: Many of these objectives are nonsmooth (e.g., involving $L_1$ norms), which traditionally forces the use of subgradient methods that suffer from a slow $O(1/\sqrt{t})$ convergence rate.
  2. Computational Cost: Standard projection methods require a full Singular Value Decomposition (SVD) at every step. For an $n \times n$ matrix, this incurs a prohibitive $O(n^3)$ cost, making it unscalable for large datasets.

While previous research has successfully utilized low-rank SVDs for smooth problems, the nonsmooth case has remained a significant bottleneck. This paper bridges that gap by introducing a highly efficient approach that leverages saddle-point reformulations and the extragradient method.

The Proposed Solution: The Extragradient Method

The authors propose a three-step strategy to bypass the limitations of traditional subgradient methods:

  • Saddle-Point Reformulation: They transform the nonsmooth objective into a smooth convex-concave saddle-point (min-max) problem.
  • Extragradient Method: By moving to a saddle-point formulation, they can employ the extragradient algorithm. This method takes two steps per iteration (a "look-ahead" step and a final update) and achieves a superior $O(1/t)$ convergence rate.
  • Low-Rank Truncated Projections: The core theoretical contribution is proving that, under a "warm-start" initialization, the expensive full-rank SVDs required for projections can be entirely replaced by truncated rank-$r$ SVDs. This reduces the per-iteration cost from $O(n^3)$ to $O(rn^2)$, where $r$ is the rank of the target matrix.

Key Insights and Theoretical Guarantees

Several key insights underpin why this methodology succeeds where others fail:

  • The Failure of Subgradients: The authors demonstrate mathematically that standard projected subgradient methods can inadvertently increase the rank of matrix iterates, even when initialized very close to a low-rank optimal solution. This necessitates the saddle-point approach.
  • Generalized Strict Complementarity (GSC): If the optimal solution is low-rank and satisfies the GSC condition, there is effectively a "gap" in the spectrum of the gradient at the optimum. This gap acts as a stability buffer, preventing small perturbations from pushing the iterates into a high-rank space.
  • The Initialization Trade-off: The paper establishes a precise mathematical trade-off: increasing the rank of the SVD used in the algorithm (computing more singular vectors than strictly required by the ground truth) significantly expands the radius of the "warm-start" ball. In essence, slightly more computation per step makes the algorithm much less sensitive to its starting point.

Empirical Validation

The researchers evaluated their method on synthetic datasets designed to mimic common matrix recovery benchmarks, including Sparse PCA, Robust PCA, linearly-constrained low-rank estimation, and simultaneous low-rank/sparse matrix recovery.

Across varying dimensions ($n=100$ to $600$) and noise levels, the results were striking: the extragradient method using only rank-$r$ SVDs produced exactly the same iterates as the version using full-rank SVDs. Furthermore, despite the theoretical requirement for a "warm-start," simple initialization schemes—such as a single rank-one approximation of the data matrix—proved sufficient for the algorithm to converge correctly in practice.

Limitations and Future Directions

While highly effective, the approach has limitations. The proof for the correctness of the low-rank projection is local, meaning it guarantees success only if the algorithm starts within a certain distance of the optimum. A "global" guarantee for the low-rank version remains an open challenge.

Additionally, the required initialization radius depends on the "eigen-gap" ($\delta$), a parameter generally unknown in real-world applications. Future work may focus on adaptive methods to estimate the necessary rank dynamically during optimization.

Summary updated

Abstract

Low-rank and nonsmooth matrix optimization problems capture many fundamental tasks in statistics and machine learning. While significant progress has been made in recent years in developing efficient methods for \textit{smooth} low-rank optimization problems that avoid maintaining high-rank matrices and computing expensive high-rank SVDs, advances for nonsmooth problems have been slow paced. In this paper we consider standard convex relaxations for such problems. Mainly, we prove that under a natural \textit{generalized strict complementarity} condition and under the relatively mild assumption that the nonsmooth objective can be written as a maximum of smooth functions, the \textit{extragradient method}, when initialized with a "warm-start'' point, converges to an optimal solution with rate $O(1/t)$ while requiring only two \textit{low-rank} SVDs per iteration. We give a precise trade-off between the rank of the SVDs required and the radius of the ball in which we need to initialize the method. We support our theoretical results with empirical experiments on several nonsmooth low-rank matrix recovery tasks, demonstrating that using simple initializations, the extragradient method produces exactly the same iterates when full-rank SVDs are replaced with SVDs of rank that matches the rank of the (low-rank) ground-truth matrix to be recovered.
BibTeX
@inproceedings{kaplan2021low,
  author = {Atara Kaplan and Dan Garber},
  title = {{Low-Rank Extragradient Method for Nonsmooth and Low-Rank Matrix Optimization Problems}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=90c-FVYJ5rL},
}
Figure