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:
- Zig-Zagging: Near the optimal solution, the algorithm oscillates between vertices, slowing convergence to $O(1/k)$.
- 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).
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.
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