Linear Convergence of Stochastic Frank Wolfe Variants

Donald Goldfarb, Garud Iyengar, Chaoxu Zhou

Abstract

In this paper, we show that the Away-step Stochastic Frank-Wolfe Algorithm (ASFW) and Pairwise Stochastic Frank-Wolfe algorithm (PSFW) 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. Such a technique has rarely been used 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.

Introduction

Optimization is the heartbeat of modern machine learning, but researchers often face a frustrating trade-off: choosing between algorithms that are computationally "cheap" per iteration (stochastic) or those that converge "fast" (linear convergence). The Frank-Wolfe (FW) algorithm is highly valued for its ability to handle complex constraints without expensive projection steps, yet it has traditionally struggled to provide both speed and low per-iteration cost.

This work bridges that gap by providing the first theoretical proof that two stochastic variants of Frank-Wolfe—Away-step Stochastic Frank-Wolfe (ASFW) and Pairwise Stochastic Frank-Wolfe (PSFW)—can achieve linear convergence. This means they close in on the optimal solution exponentially fast, even when utilizing noisy, stochastic gradients.

Problem Formulation

When training models on massive datasets (Empirical Risk Minimization), calculating the full gradient of the loss function is computationally prohibitive. While Stochastic Gradient Descent (SGD) addresses this by using gradient estimates from small data batches, constrained problems (e.g., parameters within a specific polytope) often require a "projection" step. In many high-dimensional settings, this projection can be as expensive as the gradient calculation itself.

Frank-Wolfe algorithms offer a solution by replacing projections with simple linear optimizations (LO). However, standard FW is sub-linear, converging at a rate of $O(1/k)$. While deterministic "Away-step" variants were known to converge linearly, their stochastic counterparts' performance under the noise of batch sampling remained theoretically unproven until now.

Methodology

Algorithm Variants

The authors focus on two primary variants designed to eliminate the "zig-zagging" behavior that slows down standard FW:

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

Theoretical Framework

Proving linear convergence for stochastic algorithms typically requires gradient noise to vanish. The authors employ a novel technique using empirical processes and concentration inequalities (specifically bracketing numbers and Hoeffding’s inequality) to bound stochastic gradient error. They demonstrate that with an adaptive batching schedule ($m^{(k)} \approx (1-\rho)^{-2k}$), the algorithms maintain a linear convergence path.

Theoretical and Empirical Results

The theoretical contribution is summarized in the comparison of convergence rates across different Frank-Wolfe and proximal variants. As shown in the table below, ASFW and PSFW achieve $O(\log 1/\epsilon)$ complexity for linear optimization (LO) calls, matching the efficiency of deterministic variants while operating in stochastic environments.

Table 1: Comparison of convergence rates for various Frank-Wolfe and proximal algorithms under different conditions.

Key Findings

  • Convergence Properties: The authors established a theoretical bridge showing that linear convergence in expectation implies linear convergence "almost surely" for these algorithms.
  • Empirical Performance: Testing on simulated shape-restricted regression and the Million Song Dataset (YearPredictionMSD) showed that ASFW and PSFW perform as well as or better than state-of-the-art methods like SVRF and Prox-SVRG in terms of actual CPU time.
  • Stability: Unlike variance-reduced methods (e.g., SVRF) which often exhibit large fluctuations at the start of new epochs, ASFW and PSFW demonstrate smoother and more stable descent trajectories.

Conclusion and Future Work

This research provides a rigorous foundation for using stochastic Frank-Wolfe variants in large-scale constrained optimization. While the current proofs assume a strongly convex objective, future research directions include extending these proofs to non-strongly convex functions, adapting the algorithms for block-coordinate structures, and further integrating variance reduction techniques to minimize stochastic gradient calls.

Summary updated

Abstract

In this paper, we show that the Away-step Stochastic Frank-Wolfe Algorithm (ASFW) and Pairwise Stochastic Frank-Wolfe algorithm (PSFW) 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. Such a technique has rarely been used 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