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:
- 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.
- 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.
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