# Non-stationary Projection-free Online Learning with Dynamic and Adaptive Regret Guarantees

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 55 references that are in the map.
- First posted on arXiv 19 May 2023.

## Builds on (most cited first, 30 of 32)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [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)
- [Online Optimization : Competing with Dynamic Comparators](https://mlsanity.com/paper/1501.06225/) (2015)
- [Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient](https://mlsanity.com/paper/1605.04638/) (2016)
- [Improved Strongly Adaptive Online Learning using Coin Betting](https://mlsanity.com/paper/1610.04578/) (2016)
- [MetaGrad: Multiple Learning Rates in Online Learning](https://mlsanity.com/paper/1604.08740/) (2016)
- [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)
- [Lipschitz Adaptivity with Multiple Learning Rates in Online Learning](https://mlsanity.com/paper/1902.10797/) (2019)
- [Online Forecasting of Total-Variation-bounded Sequences](https://mlsanity.com/paper/1906.03364/) (2019)
- [Minimizing Dynamic Regret and Adaptive Regret Simultaneously](https://mlsanity.com/paper/2002.02085/) (2020)
- [Efficient Projection-Free Online Convex Optimization with Membership Oracle](https://mlsanity.com/paper/2111.05818/) (2021)
- [Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond](https://mlsanity.com/paper/2201.08905/) (2022)
- [MetaGrad: Adaptation using Multiple Learning Rates in Online Learning](https://mlsanity.com/paper/2102.06622/) (2021)
- [New Projection-free Algorithms for Online Convex Optimization with Adaptive Regret Guarantees](https://mlsanity.com/paper/2202.04721/) (2022)
- [Adaptive Regret of Convex and Smooth Functions](https://mlsanity.com/paper/1904.11681/) (2019)
- [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 Bandit Convex Optimization](https://mlsanity.com/paper/1805.07474/) (2018)
- [Improved Regret Bounds for Projection-free Bandit Convex Optimization](https://mlsanity.com/paper/1910.03374/) (2019)
- [Online Learning for Changing Environments using Coin Betting](https://mlsanity.com/paper/1711.02545/) (2017)
- [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)
- [Following the Leader and Fast Rates in Linear Prediction: Curved Constraint Sets and Other Regularities](https://mlsanity.com/paper/1702.03040/) (2017)
- [Projection-free Online Exp-concave Optimization](https://mlsanity.com/paper/2302.04859/) (2023)
- [Curvature of Feasible Sets in Offline and Online Optimization](https://mlsanity.com/paper/2002.03213/) (2020)
- [Improved Dynamic Regret for Online Frank-Wolfe](https://mlsanity.com/paper/2302.05620/) (2023)

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

- [From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization](https://mlsanity.com/paper/2405.00065/) (2024)
- [Triplets Better Than Pairs: Towards Stable and Effective Self-Play Fine-Tuning for LLMs](https://mlsanity.com/paper/2601.08198/) (2026)
- [Improved Regret for Bandit Convex Optimization with Delayed Feedback](https://mlsanity.com/paper/2402.09152/) (2024)
- [SPACE: Noise Contrastive Estimation Stabilizes Self-Play Fine-Tuning for Large Language Models](https://mlsanity.com/paper/2512.07175/) (2025)
- [Universal Online Convex Optimization with 1 Projection per Round](https://mlsanity.com/paper/2405.19705/) (2024)
- [Revisiting Projection-Free Online Learning with Time-Varying Constraints](https://mlsanity.com/paper/2501.16046/) (2025)
- [A Unified Framework for Analyzing Meta-algorithms in Online Convex Optimization](https://mlsanity.com/paper/2402.08621/) (2024)
- [Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting](https://mlsanity.com/paper/2305.12131/) (2023)
- [Projection-Free Variance Reduction Methods for Stochastic Constrained Multi-Level Compositional Optimization](https://mlsanity.com/paper/2406.03787/) (2024)
- [Online Conformal Model Selection for Nonstationary Time Series](https://mlsanity.com/paper/2506.05544/) (2025)
- [Online Nonsubmodular Optimization with Delayed Feedback in the Bandit Setting](https://mlsanity.com/paper/2508.00523/) (2025)
- [From Switching to Dynamic Regret: A Simple Reduction via Unbiased Random Sequences](https://mlsanity.com/paper/2609.20968/) (2026)
- [DT-GOL: Dual-Track Geometric Online Learning in Nonstationary Environment with Label Delay](https://mlsanity.com/paper/2606.22950/) (2026)

## Abstract (arXiv)

Projection-free online learning has drawn increasing interest due to its efficiency in solving high-dimensional problems with complicated constraints. However, most existing projection-free online methods focus on minimizing the static regret, which unfortunately fails to capture the challenge of changing environments. In this paper, we investigate non-stationary projection-free online learning, and choose dynamic regret and adaptive regret to measure the performance. Specifically, we first provide a novel dynamic regret analysis for an existing projection-free method named BOGDIP, and establish an O(T3/4(1+PT)) dynamic regret bound, where PT denotes the path-length of the comparator sequence. Then, we improve the upper bound to O(T3/4(1+PT)1/4) by running multiple BOGDIP algorithms with different step sizes in parallel, and tracking the best one on the fly. Our results are the first general-case dynamic regret bounds for projection-free online learning, and can recover the existing O(T3/4) static regret by setting PT = 0. Furthermore, we propose a projection-free method to attain an tildeO(τ3/4) adaptive regret bound for any interval with length τ, which nearly matches the static regret over that interval. The essential idea is to maintain a set of BOGDIP algorithms dynamically, and combine them by a meta algorithm. Moreover, we demonstrate that it is also equipped with an O(T3/4(1+PT)1/4) dynamic regret bound. Finally, empirical studies verify our theoretical findings.