# Second Order Path Variationals in Non-Stationary Online Learning

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 53 references that are in the map.
- First posted on arXiv 4 May 2022.

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

- [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)
- [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)
- [Adaptive piecewise polynomial estimation via trend filtering](https://mlsanity.com/paper/1304.2986/) (2013)
- [Trend Filtering on Graphs](https://mlsanity.com/paper/1410.7690/) (2014)
- [Parameter-free Mirror Descent](https://mlsanity.com/paper/2203.00444/) (2022)
- [Optimal Dynamic Regret in Exp-Concave Online Learning](https://mlsanity.com/paper/2104.11824/) (2021)
- [Efficient Second Order Online Learning by Sketching](https://mlsanity.com/paper/1602.02202/) (2016)
- [Improved Analysis for Dynamic Regret of Strongly Convex and Smooth Functions](https://mlsanity.com/paper/2006.05876/) (2020)
- [Non-stationary Online Learning with Memory and Non-stochastic Control](https://mlsanity.com/paper/2102.03758/) (2021)
- [Online Forecasting of Total-Variation-bounded Sequences](https://mlsanity.com/paper/1906.03364/) (2019)
- [Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond](https://mlsanity.com/paper/2201.08905/) (2022)
- [Smoothed Online Optimization for Regression and Control](https://mlsanity.com/paper/1810.10132/) (2018)
- [A Chaining Algorithm for Online Nonparametric Regression](https://mlsanity.com/paper/1502.07697/) (2015)
- [Efficient improper learning for online logistic regression](https://mlsanity.com/paper/2003.08109/) (2020)
- [Dual Adaptivity: A Universal Algorithm for Minimizing the Adaptive Regret of Convex Functions](https://mlsanity.com/paper/1906.10851/) (2019)
- [Online Nonparametric Regression with General Loss Functions](https://mlsanity.com/paper/1501.06598/) (2015)
- [Trading-Off Static and Dynamic Regret in Online Least-Squares and Beyond](https://mlsanity.com/paper/1909.03118/) (2019)
- [Adaptive Online Estimation of Piecewise Polynomial Trends](https://mlsanity.com/paper/2010.00073/) (2020)
- [Online Isotonic Regression](https://mlsanity.com/paper/1603.04190/) (2016)
- [An Optimal Reduction of TV-Denoising to Adaptive Online Learning](https://mlsanity.com/paper/2101.09438/) (2021)
- [Non-stationary Stochastic Optimization under Lp,q-Variation Measures](https://mlsanity.com/paper/1708.03020/) (2017)

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

- [Online Label Shift: Optimal Dynamic Regret meets Practical Algorithms](https://mlsanity.com/paper/2305.19570/) (2023)
- [Dynamic Regret Reduces to Kernelized Static Regret](https://mlsanity.com/paper/2507.05478/) (2025)
- [Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting](https://mlsanity.com/paper/2305.12131/) (2023)
- [Adapting to Online Distribution Shifts in Deep Learning: A Black-Box Approach](https://mlsanity.com/paper/2504.07261/) (2025)
- [Adaptive Estimation and Learning under Temporal Distribution Shift](https://mlsanity.com/paper/2505.15803/) (2025)
- [On the Relation Between Interval Regret and Dynamic Regret](https://mlsanity.com/paper/2609.34423/) (2026)
- [Agile Online Model Selection: Resolving Adaptation Lag via Safeguarded Large Learning Rates](https://mlsanity.com/paper/2605.26919/) (2026)

## Abstract (arXiv)

We consider the problem of universal dynamic regret minimization under exp-concave and smooth losses. We show that appropriately designed Strongly Adaptive algorithms achieve a dynamic regret of tilde O(d2 n1/5 Cn2/5 vee d2), where n is the time horizon and Cn a path variational based on second order differences of the comparator sequence. Such a path variational naturally encodes comparator sequences that are piecewise linear -- a powerful family that tracks a variety of non-stationarity patterns in practice (Kim et al, 2009). The aforementioned dynamic regret rate is shown to be optimal modulo dimension dependencies and poly-logarithmic factors of n. Our proof techniques rely on analysing the KKT conditions of the offline oracle and requires several non-trivial generalizations of the ideas in Baby and Wang, 2021, where the latter work only leads to a slower dynamic regret rate of tilde O(d2.5n1/3Cn2/3 vee d2.5) for the current problem.