Linear convergence of Frank-Wolfe for rank-one matrix recovery without strong convexity

Dan GarberMath. Program 2023 · DOI

TL;DR

This paper presents a novel Frank-Wolfe algorithm that achieves linear convergence for recovering rank-one matrices from convex relaxations, even when the objective function isn't strongly convex. This is a significant improvement over existing methods, offering faster convergence and avoiding computationally expensive SVDs, making it more practical for large-scale problems.

What Problem Does This Paper Address?

Many problems in machine learning and statistics, such as matrix completion and robust PCA, involve recovering a low-rank matrix. Often, these problems are NP-hard due to non-convexity. A common approach is to use convex relaxations, where the low-rank constraint is replaced by a trace-norm constraint. While these relaxations are popular, their scalability can be limited by the computational cost of standard optimization methods, which might require high-rank SVDs. This paper focuses on a specific scenario: recovering a rank-one matrix. The authors identify a crucial condition – a spectral gap in the gradient of the objective function at the optimal solution – that allows for significantly faster convergence of the Frank-Wolfe algorithm, even without strong convexity. This condition is key to ensuring that the convex relaxation yields a unique, rank-one solution.

Methods

The core of the paper revolves around the Frank-Wolfe algorithm, a conditional gradient method. The authors propose a standard Frank-Wolfe algorithm with line-search (Algorithm 1) and show that under a specific "spectral gap" condition (Assumption 1), it achieves a convergence rate of $O(\log 1/\epsilon)$ iterations, a substantial improvement over the typical $O(1/\epsilon)$ for non-strongly convex objectives. This algorithm only requires a single rank-one SVD computation per iteration.

They also introduce:

  • Variants of Frank-Wolfe: Two variants are presented with potentially improved complexities.
  • Extension to Robust PCA: An adaptation of the method is proposed for problems motivated by robust PCA, involving a structured objective function.
  • Nonsmooth Extension: The framework is extended to handle nonsmooth objective functions by using smooth approximations.
  • Bounded-Rank Algorithm: A modification (Algorithm 2) is introduced that guarantees the iterates remain bounded in rank, independent of the desired accuracy $\epsilon$.

The key to their theoretical results is Assumption 1, which states that the difference between the two largest eigenvalues of the gradient of the objective function at the optimal solution is strictly positive. This "spectral gap" is shown to imply a quadratic growth property, which is crucial for achieving linear convergence.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and proposes algorithms. Empirical validation is done through synthetic data generation in the "Numerical Experiments" section.

Key Insights and Ideas

  • Spectral Gap is Key: The presence of a spectral gap in the gradient of the objective function at the optimal solution is a surprisingly powerful condition. It not only guarantees a unique, rank-one optimal solution but also unlocks significantly faster convergence for Frank-Wolfe.
  • Frank-Wolfe's Efficiency: The paper highlights that Frank-Wolfe, with its low computational cost per iteration (rank-one SVD), is well-suited for rank-one recovery problems, especially when combined with line-search to avoid parameter tuning.
  • Beyond Strong Convexity: Achieving linear convergence without strong convexity is a significant theoretical advance, as many existing methods rely on this property.
  • Rank-One Specifics: The focus on rank-one recovery allows for specialized analysis and algorithms that are more efficient than general low-rank recovery methods.

Key Results

  • $O(\log 1/\epsilon)$ Convergence: The proposed Frank-Wolfe algorithm (Algorithm 1) achieves an $O(\log 1/\epsilon)$ iteration complexity to find an $\epsilon$-approximate solution, under Assumption 1 and for smooth objectives. This is a significant improvement over the $O(1/\epsilon)$ bound for general convex objectives.
  • Rank-One Solution Guarantee: Assumption 1 guarantees that the optimal solution is indeed rank-one.
  • Robustness to Noise: Lemma 3 shows that the spectral gap condition is robust to small perturbations in the objective function, which is important for real-world applications where data might be noisy.
  • Bounded Rank Iterates: Algorithm 2 ensures that the iterates of the algorithm maintain a bounded rank, which is beneficial for memory efficiency.
  • Empirical Validation: Numerical experiments on synthetic data for rank-one matrix recovery and robust PCA demonstrate that the proposed methods recover the ground truth with low error and that the spectral gap assumption is satisfied in practice.

Limitations and Future Work

  • Assumption 1 Dependency: The main theoretical results rely on Assumption 1 (the spectral gap). While the paper provides empirical evidence and a robustness result (Lemma 3), verifying this assumption in practice can still be challenging.
  • Computational Cost of SVD: While the algorithm requires only rank-one SVDs, these can still be computationally intensive for very large matrices.
  • "Burn-in" Phase: Some variants of the algorithm (Theorems 2 and 3) exhibit linear convergence only after an initial "burn-in" phase. Algorithm 3 (Regularized Frank-Wolfe) addresses this by removing the burn-in phase if the gap is known.
  • Future Work: The paper suggests exploring extensions to more general low-rank recovery problems and investigating the practical performance of the proposed algorithms on real-world datasets. The authors also mention that their results can be extended to complex matrices.

Summary updated

BibTeX
@article{garber2023linear,
  author = {Dan Garber},
  title = {{Linear convergence of Frank-Wolfe for rank-one matrix recovery without strong convexity}},
  journal = {Math. Program},
  year = {2023},
  doi = {10.1007/s10107-022-01821-8},
}
Figure