On the Online Frank-Wolfe Algorithms for Convex and Non-convex Optimizations

Jean Lafond, Hoi-To Wai, Éric Moulines

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:

  1. 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.
  2. 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.

Figure 2: Primal optimality vs. Time (s) comparing O-FW, O-PG, and Batch FW. O-FW demonstrates significantly faster convergence in real time due to the absence of expensive projection steps.

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.

Figure 3: MSE vs. Time (sec) for matrix completion. O-FW and Batch FW variants achieve low MSE much faster than the projection-based O-PG method.

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

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.
BibTeX
@misc{lafond2015online,
  author = {Jean Lafond and Hoi-To Wai and Éric Moulines},
  title = {{On the Online Frank-Wolfe Algorithms for Convex and Non-convex Optimizations}},
  year = {2015},
  eprint = {1510.01171},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1510.01171},
}
Figure