# Efficient Methods for Non-stationary Online Learning

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 68 references that are in the map.
- First posted on arXiv 16 Sep 2023.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018)
- [Black-Box Reductions for Parameter-free Online Learning in Banach Spaces](https://mlsanity.com/paper/1802.06293/) (2018)
- [Strongly Adaptive Online Learning](https://mlsanity.com/paper/1502.07073/) (2015)
- [A Second-order Bound with Excess Losses](https://mlsanity.com/paper/1402.2044/) (2014)
- [Online Control with Adversarial Disturbances](https://mlsanity.com/paper/1902.08721/) (2019)
- [Dynamic Regret of Convex and Smooth Functions](https://mlsanity.com/paper/2007.03479/) (2020)
- [Scale-Free Online Learning](https://mlsanity.com/paper/1601.01974/) (2016)
- [Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization](https://mlsanity.com/paper/2112.14368/) (2021)
- [The Nonstochastic Control Problem](https://mlsanity.com/paper/1911.12178/) (2019)
- [Improved Strongly Adaptive Online Learning using Coin Betting](https://mlsanity.com/paper/1610.04578/) (2016)
- [Open-environment Machine Learning](https://mlsanity.com/paper/2206.00423/) (2022)
- [MetaGrad: Multiple Learning Rates in Online Learning](https://mlsanity.com/paper/1604.08740/) (2016)
- [Parameter-free Mirror Descent](https://mlsanity.com/paper/2203.00444/) (2022)
- [Dynamical Models and Tracking Regret in Online Convex Programming](https://mlsanity.com/paper/1301.1254/) (2013)
- [Bandit Convex Optimization in Non-stationary Environments](https://mlsanity.com/paper/1907.12340/) (2019)
- [Logarithmic Regret for Adversarial Online Control](https://mlsanity.com/paper/2003.00189/) (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)
- [No-Regret Learning in Time-Varying Zero-Sum Games](https://mlsanity.com/paper/2201.12736/) (2022)
- [Non-stationary Online Learning with Memory and Non-stochastic Control](https://mlsanity.com/paper/2102.03758/) (2021)
- [Minimizing Dynamic Regret and Adaptive Regret Simultaneously](https://mlsanity.com/paper/2002.02085/) (2020)
- [Revisiting Smoothed Online Learning](https://mlsanity.com/paper/2102.06933/) (2021)
- [Adaptive Regret of Convex and Smooth Functions](https://mlsanity.com/paper/1904.11681/) (2019)
- [Dynamic Regret of Online Markov Decision Processes](https://mlsanity.com/paper/2208.12483/) (2022)
- [Online Adaptive Principal Component Analysis and Its extensions](https://mlsanity.com/paper/1901.07687/) (2019)

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

- [An Equivalence Between Static and Dynamic Regret Minimization](https://mlsanity.com/paper/2406.01577/) (2024)
- [Non-stationary Online Learning for Curved Losses: Improved Dynamic Regret via Mixability](https://mlsanity.com/paper/2506.10616/) (2025)
- [Universal Online Convex Optimization with 1 Projection per Round](https://mlsanity.com/paper/2405.19705/) (2024)
- [Exploring the Noise Robustness of Online Conformal Prediction](https://mlsanity.com/paper/2501.18363/) (2025)
- [Dynamic Regret Reduces to Kernelized Static Regret](https://mlsanity.com/paper/2507.05478/) (2025)
- [Dynamic Regret via Discounted-to-Dynamic Reduction with Applications to Curved Losses and Adam Optimizer](https://mlsanity.com/paper/2602.08372/) (2026)
- [A Simple, Optimal and Efficient Algorithm for Online Exp-Concave Optimization](https://mlsanity.com/paper/2512.23190/) (2025)
- [Adapting to Online Distribution Shifts in Deep Learning: A Black-Box Approach](https://mlsanity.com/paper/2504.07261/) (2025)
- [Online Learning with Gradient-Variation Interval Regret](https://mlsanity.com/paper/2606.03831/) (2026)
- [Non-stationary Bandit Convex Optimization: A Comprehensive Study](https://mlsanity.com/paper/2506.02980/) (2025)
- [Online Conformal Model Selection for Nonstationary Time Series](https://mlsanity.com/paper/2506.05544/) (2025)
- [A Modular Algorithm for Non-Stationary Online Convex-Concave Optimization](https://mlsanity.com/paper/2509.07901/) (2025)
- [Gradient-Variation Regret Bounds for Unconstrained Online Learning](https://mlsanity.com/paper/2604.11151/) (2026)
- [On the Relation Between Interval Regret and Dynamic Regret](https://mlsanity.com/paper/2609.34423/) (2026)
- [Policy-Controlled Generalized Share: A General Framework with a Transformer Instantiation for Strictly Online Switching-Oracle Tracking](https://mlsanity.com/paper/2603.28198/) (2026)

## Abstract (arXiv)

Non-stationary online learning has drawn much attention in recent years. In particular, dynamic regret and adaptive regret are proposed as two principled performance measures for online convex optimization in non-stationary environments. To optimize them, a two-layer online ensemble is usually deployed due to the inherent uncertainty of non-stationarity, in which multiple base-learners are maintained and a meta-algorithm is employed to track the best one on the fly. However, the two-layer structure raises concerns about computational complexity -- such methods typically maintain O(log T) base-learners simultaneously for a T-round online game and thus perform multiple projections onto the feasible domain per round, which becomes the computational bottleneck when the domain is complicated. In this paper, we present efficient methods for optimizing dynamic regret and adaptive regret that reduce the number of projections per round from O(log T) to 1. The proposed algorithms require only one gradient query and one function evaluation at each round. Our technique hinges on the reduction mechanism developed in parameter-free online learning and requires non-trivial modifications for non-stationary online methods. Furthermore, we study an even stronger measure, namely "interval dynamic regret", and reduce the number of projections per round from O(log2 T) to 1 for minimizing it. Our reduction demonstrates broad generality and applies to two important applications: online stochastic control and online principal component analysis, resulting in methods that are both efficient and optimal. Finally, empirical studies verify our theoretical findings.