Abstract
In this paper, the online variants of the classical Frank-Wolfe algorithm are considered. We consider minimizing the regret with a stochastic cost. The online algorithms only require simple iterative updates and a non-adaptive step size rule, in contrast to the hybrid schemes commonly considered in the literature. Several new results are derived for convex and non-convex losses. With a strongly convex stochastic cost and when the optimal solution lies in the interior of the constraint set or the constraint set is a polytope, the regret bound and anytime optimality are shown to be ${\cal O}( \log^3 T / T )$ and ${\cal O}( \log^2 T / T)$, respectively, where $T$ is the number of rounds played. These results are based on an improved analysis on the stochastic Frank-Wolfe algorithms. Moreover, the online algorithms are shown to converge even when the loss is non-convex, i.e., the algorithms find a stationary point to the time-varying/stochastic loss at a rate of ${\cal O}(\sqrt{1/T})$. Numerical experiments on realistic data sets are presented to support our theoretical claims.
Introduction
High-dimensional constrained optimization is a cornerstone of modern machine learning, with the Projected Gradient (PG) method often serving as the standard approach. However, PG's reliance on a projection step onto constraint sets—such as nuclear norm balls or polytopes—can be computationally prohibitive in applications like matrix completion or sparse recovery.
The Frank-Wolfe (FW) algorithm, or conditional gradient method, provides a "projection-free" alternative by substituting the costly projection with a simpler linear optimization step. While online variants of FW have been proposed, they frequently suffer from slow convergence or necessitate complex "hybrid" modifications to remain competitive. This work bridges this gap by introducing a simple, iterative online FW framework applicable to both convex and non-convex losses.
Algorithmic Framework
We analyze two primary algorithms:
- Online Frank-Wolfe (O-FW): A direct online generalization of the classical FW algorithm. It utilizes an aggregated gradient (the average of all observed gradients) to determine the update direction, effectively smoothing noise in stochastic settings.
- Online Away-step Frank-Wolfe (O-AW): Designed to mitigate the "zig-zagging" behavior of iterates near polytope boundaries. By allowing moves away from previously active atoms, O-AW significantly accelerates convergence on polytope constraints.
Both algorithms employ a simple, non-adaptive step size rule ($\gamma_t \approx 1/t$), facilitating straightforward implementation compared to adaptive or hybrid schemes.
Theoretical Contributions
A major milestone of this research is the extension of projection-free methods to non-convex online optimization. We prove that O-FW and O-AW can identify stationary points at a rate of $O(1/\sqrt{T})$, even for non-convex losses like the sigmoid loss used in robust classification.
Furthermore, for strongly convex costs, we improve the regret bound to $O(\log^3 T/T)$ and anytime optimality to $O(\log^2 T/T)$. The analysis also highlights the role of constraint geometry: while O-FW excels when the optimal solution is in the interior, O-AW is essential for maintaining performance when the solution lies on the boundary of a polytope.
Experimental Evaluation
The theoretical claims were validated across diverse benchmarks, including synthetic data for Matrix Completion and LASSO, real-world collaborative filtering (MovieLens 100k/20m), large-scale text classification (rcv1.binary), and single-pixel imaging (R64.mat).
In Matrix Completion tasks on the MovieLens 20m dataset, O-FW demonstrated significant time efficiency. As shown in Figure 1, O-FW converges much faster in terms of wall-clock time compared to the Online Projected Gradient (O-PG) method, as its linear optimization step (SVD-based) is significantly cheaper than a full projection.
Figure 3 illustrates the convergence in terms of iteration count. While O-FW and O-PG may show comparable iteration-wise progress, the computational savings per iteration make O-FW the superior choice for high-dimensional problems. Additionally, in classification tasks with 25% label noise, the non-convex sigmoid loss optimized via O-FW outperformed the standard convex logistic loss, showcasing the practical value of the non-convex analysis.
Discussion and Future Work
While O-AW is highly effective for polytopes, its memory overhead grows with the number of active atoms, presenting a challenge for non-atomic constraint sets. The fast $O(1/t)$ rate for O-FW currently relies on the assumption that the optimal point lies in the interior of the constraint set. Future research will investigate if this assumption can be relaxed, as empirical results suggest robust performance even when it is violated.
Summary updated