Linear Convergence of Stochastic Frank Wolfe Variants

Donald Goldfarb, Garud Iyengar, Chaoxu Zhou

Introduction

Presented at AISTATS 2017, this research provides a significant theoretical advancement for stochastic optimization. The authors demonstrate that two stochastic variants of the Frank-Wolfe algorithm—Away-step (ASFW) and Pairwise (PSFW)—achieve linear convergence. This means they close the gap to the optimal solution at a consistent exponential rate, both in expectation and "almost surely."

The Challenge of Large-Scale Optimization

Empirical Risk Minimization (ERM) is central to machine learning. However, as datasets and model parameters scale, traditional methods like Proximal Gradient Descent encounter bottlenecks. These methods require a "projection" step—solving a mini-optimization problem every iteration to keep the model within constraints (such as a polytope).

The Frank-Wolfe (FW) algorithm offers a computationally "cheap" alternative by replacing projections with linear optimization steps. Despite its efficiency, standard FW suffers from two primary issues:

  1. Zig-Zagging: Near the optimal solution, the algorithm oscillates between vertices, slowing convergence to $O(1/k)$.
  2. Computational Cost: Calculating exact gradients for massive datasets is prohibitively slow.

While "Away-step" and "Pairwise" variants were developed to mitigate zig-zagging, and stochastic versions were created for large-scale data, proving that these combined approaches yield linear convergence ($O(e^{-k})$) remained an open challenge.

Stochastic Frank-Wolfe Variants

The authors analyze two specific algorithms:

  • Away-step Stochastic Frank-Wolfe (ASFW): This variant can either move toward a promising new vertex or move away from a suboptimal vertex in its active set.
  • Pairwise Stochastic Frank-Wolfe (PSFW): This variant shifts weight directly from a suboptimal vertex to a promising one in a single step.

The theoretical breakthrough lies in a novel proof technique. By utilizing Empirical Process Theory and Bracketing Numbers, the authors treat the difference between stochastic and true gradients as a stochastic process. This allows them to use concentration inequalities to bound errors across the entire feasible region, bridging the gap between combinatorial vertex tracking and stochastic gradient noise.

Empirical Performance

The algorithms were evaluated on synthetic shape-restricted regression problems and the Million Song Dataset (YearPredictionMSD).

Comparison of ASFW and PSFW against SVRF and SVRG on simulated data, showing loss versus CPU time.

In head-to-head tests against state-of-the-art competitors like Stochastic Variance-Reduced Frank-Wolfe (SVRF) and Prox-SVRG, ASFW and PSFW demonstrated superior or comparable performance in actual CPU time. As seen in Figure 1, the proposed stochastic variants exhibit smoother descent compared to the instability often seen in SVRF at the start of new epochs.

Logarithmic loss versus number of iterations on the Million Song Dataset across various regularization parameters.

On the Million Song Dataset, solving a least-squares problem with elastic-net regularization, ASFW and PSFW consistently reached lower loss values faster than variance-reduced alternatives across various settings (Figure 3).

Conclusion

By proving linear convergence for ASFW and PSFW, the authors provide a robust theoretical foundation for using these algorithms in large-scale machine learning. Their use of bracketing numbers offers a new template for analyzing other stochastic algorithms. While the current proof assumes strong convexity and polytope constraints, it sets the stage for future work in non-convex optimization and more general convex sets.

Summary updated

Abstract

In this paper, we show that the Away-step Stochastic Frank-Wolfe (ASFW) and Pairwise Stochastic Frank-Wolfe (PSFW) algorithms converge linearly in expectation. We also show that if an algorithm convergences linearly in expectation then it converges linearly almost surely. In order to prove these results, we develop a novel proof technique based on concepts of empirical processes and concentration inequalities. As far as we know, this technique has not been used previously to derive the convergence rates of stochastic optimization algorithms. In large- scale numerical experiments, ASFW and PSFW perform as well as or better than their stochastic competitors in actual CPU time.
BibTeX
@inproceedings{goldfarb2017linear,
  author = {Donald Goldfarb and Garud Iyengar and Chaoxu Zhou},
  title = {{Linear Convergence of Stochastic Frank Wolfe Variants}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2017},
  url = {https://openreview.net/forum?id=newT0DkFlU},
}
Figure