Abstract
In this paper, we investigate online variants of the classical Frank-Wolfe algorithm for minimizing regret with stochastic costs. Unlike existing hybrid schemes, our proposed online algorithms utilize simple iterative updates and a non-adaptive step size rule. We derive several new results for both convex and non-convex losses. For strongly convex stochastic costs, we establish a regret bound of ${\cal O}( \log^3 T / T )$ and anytime optimality of ${\cal O}( \log^2 T / T)$, provided the optimal solution is in the interior of the constraint set or the set is a polytope. Furthermore, we demonstrate that these algorithms converge to a stationary point for non-convex losses at a rate of ${\cal O}(\sqrt{1/T})$. Numerical experiments on realistic datasets, including MovieLens and MNIST, validate our theoretical findings.
Introduction
In high-dimensional constrained optimization, the Projected Gradient (PG) algorithm is often considered the standard approach. However, the projection step in PG can become a significant computational bottleneck when dealing with complex constraint sets, such as trace-norm balls or large polytopes.
The Frank-Wolfe (FW) algorithm, or conditional gradient method, offers a compelling alternative by replacing the expensive projection with a linear optimization step. While well-established in offline settings, online variants of FW—where cost functions are revealed stochastically over time—have previously relied on complex hybrid schemes. This work demonstrates that simple, projection-free online FW algorithms can achieve state-of-the-art convergence rates for both convex and non-convex stochastic optimization.
Methods: Online Frank-Wolfe Variants
We analyze two primary algorithmic variants:
- Online Frank-Wolfe (O-FW): A direct generalization of classical FW that uses an aggregated gradient (the average of all observed gradients) to solve a linear optimization subproblem at each round.
- Online Away-step Frank-Wolfe (O-AW): This variant incorporates an "away step" to mitigate the "zig-zagging" behavior common in standard FW when near the boundary of a polytope constraint set.
A key contribution of our approach is the use of a simple, non-adaptive step size rule (e.g., $\gamma_t = 2/(t+1)$). Our theoretical breakthrough stems from a refined analysis of how stochastic gradient estimation errors propagate, treating the aggregated gradient as an inexact version of the true expected gradient.
Empirical Performance and Wall-Clock Efficiency
The primary advantage of projection-free methods is their computational efficiency. In our experiments on matrix completion and robust classification, O-FW consistently outperformed both batch FW and Online Projected Gradient (O-PG) methods in terms of wall-clock time.
As shown in the primal optimality plots, O-FW reaches lower error levels orders of magnitude faster than O-PG. This is particularly evident in tasks like matrix completion using the MovieLens datasets, where the projection onto a trace-norm ball is computationally prohibitive.
Key Insights and Theoretical Results
- Convex Regret: For strongly convex costs, we improved the regret bound to $O(\log^3 T / T)$, matching or exceeding the performance of more complex hybrid algorithms.
- Non-Convex Convergence: We provide the first convergence rate guarantees for online projection-free optimization under non-convex losses (e.g., sigmoid loss), finding a stationary point at a rate of $O(1/\sqrt{T})$.
- Robustness: In classification tasks with 25% label noise, the non-convex sigmoid loss optimized via O-FW significantly outperformed standard convex logistic loss, highlighting the utility of our non-convex results.
Conclusion
This work establishes that simple online Frank-Wolfe algorithms are not only theoretically sound but also practically superior for high-dimensional constrained optimization. By eliminating the projection bottleneck and providing guarantees for non-convex objectives, these methods offer a robust framework for modern stochastic optimization challenges. Future work will explore extending these non-adaptive rules to fully adversarial settings and managing the active set size in O-AW for more complex constraints.
Summary updated