# Improved Dynamic Regret for Online Frank-Wolfe

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 38 references that are in the map.
- First posted on arXiv 11 Feb 2023.

## Builds on (most cited first, 23 of 23)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018)
- [Strongly Adaptive Online Learning](https://mlsanity.com/paper/1502.07073/) (2015)
- [Dynamic Regret of Convex and Smooth Functions](https://mlsanity.com/paper/2007.03479/) (2020)
- [Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient](https://mlsanity.com/paper/1605.04638/) (2016)
- [MetaGrad: Multiple Learning Rates in Online Learning](https://mlsanity.com/paper/1604.08740/) (2016)
- [Improved Dynamic Regret for Non-degenerate Functions](https://mlsanity.com/paper/1608.03933/) (2016)
- [Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets](https://mlsanity.com/paper/1406.1305/) (2014)
- [Faster Projection-free Online Learning](https://mlsanity.com/paper/2001.11568/) (2020)
- [Optimal Dynamic Regret in Exp-Concave Online Learning](https://mlsanity.com/paper/2104.11824/) (2021)
- [Improved Analysis for Dynamic Regret of Strongly Convex and Smooth Functions](https://mlsanity.com/paper/2006.05876/) (2020)
- [Online Forecasting of Total-Variation-bounded Sequences](https://mlsanity.com/paper/1906.03364/) (2019)
- [Efficient Projection-Free Online Convex Optimization with Membership Oracle](https://mlsanity.com/paper/2111.05818/) (2021)
- [New Projection-free Algorithms for Online Convex Optimization with Adaptive Regret Guarantees](https://mlsanity.com/paper/2202.04721/) (2022)
- [Revisiting Projection-free Online Learning: the Strongly Convex Case](https://mlsanity.com/paper/2010.07572/) (2020)
- [Projection-free Online Learning over Strongly Convex Sets](https://mlsanity.com/paper/2010.08177/) (2020)
- [A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimization](https://mlsanity.com/paper/1301.4666/) (2013)
- [Projection-free Distributed Online Learning with Sublinear Communication Complexity](https://mlsanity.com/paper/2103.11102/) (2021)
- [Projection-free Adaptive Regret with Membership Oracles](https://mlsanity.com/paper/2211.12638/) (2022)
- [Exploiting the Curvature of Feasible Sets for Faster Projection-Free Online Learning](https://mlsanity.com/paper/2205.11470/) (2022)
- [Efficient Online Learning with Memory via Frank-Wolfe Optimization: Algorithms with Bounded Dynamic Regret and Applications to Control](https://mlsanity.com/paper/2301.00497/) (2023)

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

- [Non-stationary Projection-free Online Learning with Dynamic and Adaptive Regret Guarantees](https://mlsanity.com/paper/2305.11726/) (2023)
- [Optimal and Efficient Algorithms for Decentralized Online Convex Optimization](https://mlsanity.com/paper/2402.09173/) (2024)
- [Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback](https://mlsanity.com/paper/2310.14085/) (2023)
- [Revisiting Projection-Free Online Learning with Time-Varying Constraints](https://mlsanity.com/paper/2501.16046/) (2025)
- [Dynamic Regret Analysis of Safe Distributed Online Optimization for Convex and Non-convex Problems](https://mlsanity.com/paper/2302.12320/) (2023)
- [Riemannian Projection-free Online Learning](https://mlsanity.com/paper/2305.19349/) (2023)
- [Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting](https://mlsanity.com/paper/2305.12131/) (2023)
- [From Switching to Dynamic Regret: A Simple Reduction via Unbiased Random Sequences](https://mlsanity.com/paper/2609.20968/) (2026)

## Abstract (arXiv)

To deal with non-stationary online problems with complex constraints, we investigate the dynamic regret of online Frank-Wolfe (OFW), which is an efficient projection-free algorithm for online convex optimization. It is well-known that in the setting of offline optimization, the smoothness of functions and the strong convexity of functions accompanying specific properties of constraint sets can be utilized to achieve fast convergence rates for the Frank-Wolfe (FW) algorithm. However, for OFW, previous studies only establish a dynamic regret bound of O(√T(VT+√DT+1)) by utilizing the convexity of problems, where T is the number of rounds, VT is the function variation, and DT is the gradient variation. In this paper, we derive improved dynamic regret bounds for OFW by extending the fast convergence rates of FW from offline optimization to online optimization. The key technique for this extension is to set the step size of OFW with a line search rule. In this way, we first show that the dynamic regret bound of OFW can be improved to O(√T(VT+1)) for smooth functions. Second, we achieve a better dynamic regret bound of O(T1/3(VT+1)2/3) when functions are smooth and strongly convex, and the constraint set is strongly convex. Finally, for smooth and strongly convex functions with minimizers in the interior of the constraint set, we demonstrate that the dynamic regret of OFW reduces to O(VT+1), and can be further strengthened to O(minPT^ast,ST^ast,VT+1) by performing a constant number of FW iterations per round, where PT^ast and ST^ast denote the path length and squared path length of minimizers, respectively.