# A Stability Principle for Learning under Non-Stationarity

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 63 references that are in the map.
- First posted on arXiv 27 Oct 2023.

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

- [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)
- [Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach](https://mlsanity.com/paper/2102.05406/) (2021)
- [A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free](https://mlsanity.com/paper/1902.00980/) (2019)
- [Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient](https://mlsanity.com/paper/1605.04638/) (2016)
- [Efficient Contextual Bandits in Non-stationary Worlds](https://mlsanity.com/paper/1708.01799/) (2017)
- [Hedging the Drift: Learning to Optimize under Non-Stationarity](https://mlsanity.com/paper/1903.01461/) (2019)
- [Dynamical Models and Tracking Regret in Online Convex Programming](https://mlsanity.com/paper/1301.1254/) (2013)
- [Feature Robustness in Non-stationary Health Records: Caveats to Deployable Model Performance in Common Clinical Machine Learning Tasks](https://mlsanity.com/paper/1908.00690/) (2019)
- [Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond](https://mlsanity.com/paper/2201.08905/) (2022)
- [Tracking Most Significant Arm Switches in Bandits](https://mlsanity.com/paper/2112.13838/) (2021)
- [Adapting to Online Label Shift with Provable Guarantees](https://mlsanity.com/paper/2207.02121/) (2022)
- [Online Stochastic Optimization with Wasserstein Based Non-stationarity](https://mlsanity.com/paper/2012.06961/) (2020)
- [Non-Stationary Bandit Learning via Predictive Sampling](https://mlsanity.com/paper/2205.01970/) (2022)
- [An Adaptive Algorithm for Learning with Unknown Distribution Drift](https://mlsanity.com/paper/2305.02252/) (2023)
- [Stochastic Optimization under Distributional Drift](https://mlsanity.com/paper/2108.07356/) (2021)
- [Smooth Non-Stationary Bandits](https://mlsanity.com/paper/2301.12366/) (2023)
- [On Adaptivity in Non-stationary Stochastic Optimization With Bandit Feedback](https://mlsanity.com/paper/2210.05584/) (2022)
- [An Information-Theoretic Analysis of Nonstationary Bandit Learning](https://mlsanity.com/paper/2302.04452/) (2023)
- [Learning with a Drifting Target Concept](https://mlsanity.com/paper/1505.05215/) (2015)
- [Non-Stationary Bandits with Auto-Regressive Temporal Dependency](https://mlsanity.com/paper/2210.16386/) (2022)
- [Learning Rate Schedules in the Presence of Distribution Shift](https://mlsanity.com/paper/2303.15634/) (2023)
- [Learning and Optimization with Seasonal Patterns](https://mlsanity.com/paper/2005.08088/) (2020)
- [High-Dimensional Dynamic Pricing under Non-Stationarity: Learning and Earning with Change-Point Detection](https://mlsanity.com/paper/2303.07570/) (2023)
- [Time varying regression with hidden linear dynamics](https://mlsanity.com/paper/2112.14862/) (2021)
- [MNL-Bandit in non-stationary environments](https://mlsanity.com/paper/2303.02504/) (2023)

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

- [Model Assessment and Selection under Temporal Distribution Shift](https://mlsanity.com/paper/2402.08672/) (2024)
- [Learning to Bid in Non-Stationary Repeated First-Price Auctions](https://mlsanity.com/paper/2501.13358/) (2025)
- [Online Decision-Focused Learning](https://mlsanity.com/paper/2505.13564/) (2025)
- [Fast Rates for Nonstationary Weighted Risk Minimization](https://mlsanity.com/paper/2602.05742/) (2026)
- [Distribution-Free Predictive Inference under Unknown Temporal Drift](https://mlsanity.com/paper/2406.06516/) (2024)
- [Non-Stationary Online Structured Prediction with Surrogate Losses](https://mlsanity.com/paper/2510.07086/) (2025)
- [The Cost of Learning Under Multiple Change Points](https://mlsanity.com/paper/2602.11406/) (2026)
- [Adaptive Window Selection for Financial Risk Forecasting](https://mlsanity.com/paper/2603.01157/) (2026)
- [Signature Approach for Contextual Bandits with Nonlinear and Path-dependent Rewards](https://mlsanity.com/paper/2605.10313/) (2026)
- [Beyond Discrepancy: Oracle Drift in Nonstationary Weighted Risk Minimization](https://mlsanity.com/paper/2610.13598/) (2026)

## Abstract (arXiv)

We develop a versatile framework for statistical learning in non-stationary environments. In each time period, our approach applies a stability principle to select a look-back window that maximizes the utilization of historical data while keeping the cumulative bias within an acceptable range relative to the stochastic error. Our theory showcases the adaptivity of this approach to unknown non-stationarity. We prove regret bounds that are minimax optimal up to logarithmic factors when the population losses are strongly convex, or Lipschitz only. At the heart of our analysis lie two novel components: a measure of similarity between functions and a segmentation technique for dividing the non-stationary data sequence into quasi-stationary pieces. We evaluate the practical performance of our approach through real-data experiments on electricity demand prediction and hospital nurse staffing.