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

arXiv: https://arxiv.org/abs/1510.01171 · HTML: https://mlsanity.com/paper/1510.01171/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Oct 2015.

## Built on by (most cited first, 4 of 4)

- [Fast online ranking with fairness of exposure](https://mlsanity.com/paper/2209.13019/) (2022)
- [On Private Online Convex Optimization: Optimal Algorithms in ℓp-Geometry and High Dimensional Contextual Bandits](https://mlsanity.com/paper/2206.08111/) (2022)
- [Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Experts](https://mlsanity.com/paper/2606.14929/) (2026)
- [Always Valid Risk Monitoring for Online Matrix Completion](https://mlsanity.com/paper/2211.10363/) (2022)

## Abstract (arXiv)

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( log3 T / T ) and cal O( log2 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(√1/T). Numerical experiments on realistic data sets are presented to support our theoretical claims.