A Stability Principle for Learning Under Nonstationarity

Chengpiao Huang, Kaizheng WangOperations Research 2025 · OpenReview

TL;DR

This paper introduces a novel "stability principle" for online learning in non-stationary environments, where the underlying data distribution changes over time. Their method adaptively selects the most relevant historical data by balancing bias and variance, achieving near-optimal performance without prior knowledge of the non-stationarity. This is achieved through a new function similarity measure and a segmentation technique, demonstrated on real-world electricity demand and hospital staffing data.

What Problem Does This Paper Address?

Many real-world systems, from financial markets to healthcare, exhibit non-stationarity – their underlying dynamics change over time. This poses a significant challenge for traditional machine learning algorithms, which often assume stationary data. When the environment shifts, past data can become irrelevant or even misleading, leading to poor decision-making. The core problem is how to effectively learn and adapt in such dynamic settings, specifically by intelligently choosing which historical data to rely on when making current predictions or decisions. The paper addresses the challenge of selecting an optimal "look-back window" of historical data in an online learning setting, where decisions must be made sequentially without knowing future data or the exact nature of the non-stationarity.

Methods

The paper's core contribution is a stability principle for adaptively selecting a look-back window. At each time step, the algorithm aims to find the largest window of historical data where the cumulative bias introduced by non-stationarity is controlled relative to the stochastic error. This is achieved through a series of pairwise comparisons of candidate windows, where a window is deemed "admissible" if it doesn't perform significantly worse than smaller windows. The largest admissible window is then chosen.

Key novelties include:

  • Function Similarity Measure: A new definition of "closeness" between functions that quantifies how well their sub-optimality gaps relate, providing a robust way to compare function behaviors.
  • Segmentation Technique: A method to partition the non-stationary data sequence into "quasi-stationary" segments, allowing for more refined analysis and tighter regret bounds.
  • Stability-based Adaptive Window Selection (SAWS): The overarching algorithm that leverages the stability principle to dynamically adjust the look-back window.

The theoretical analysis provides regret bounds for both strongly convex and Lipschitz loss functions, showing that SAWS achieves minimax optimal rates up to logarithmic factors.

Datasets

The paper evaluates its approach on two real-world datasets:

  • Electricity Demand Data: Daily electricity demand in Victoria, Australia, from January 1st, 2016, to October 6th, 2020. This data is used for predicting daily electricity demand.
  • Hospital Nurse Staffing Data: Weekly ED visit counts for vomiting in NYC from January 7th, 2019, to December 31st, 2023. This data is used to model nurse staffing decisions.

The paper also uses synthetic data generated from linear regression and stochastic linear optimization problems to test the algorithm under controlled non-stationary conditions.

Key Insights and Ideas

  • "Expansion until proven guilty" for window selection: The core idea of SAWS is to expand the look-back window as much as possible while ensuring that the historical data remains relevant. If the window becomes "guilty" (i.e., performance degrades significantly due to non-stationarity), it's shrunk. This is a principled way to balance data utilization with adaptation.
  • Non-stationarity as segmentation: Instead of relying on global measures of non-stationarity like path variation, the paper proposes segmenting the data into quasi-stationary pieces. This allows for a more nuanced understanding of how the environment changes and leads to tighter theoretical guarantees.
  • Adaptivity without prior knowledge: A major strength of SAWS is its ability to adapt to unknown non-stationarity. It doesn't require any prior information about the rate or pattern of environmental changes, making it broadly applicable.
  • Bridging theory and practice: The paper not only provides strong theoretical guarantees but also demonstrates the practical effectiveness of SAWS on real-world datasets, showing it can outperform fixed-window methods.

Key Results

  • Theoretical Guarantees: SAWS achieves minimax optimal dynamic regret bounds (up to logarithmic factors) for both strongly convex and Lipschitz loss functions. These bounds are shown to be adaptive to the degree of non-stationarity, measured by the number of quasi-stationary segments.
  • Practical Performance: On electricity demand prediction and hospital nurse staffing tasks, SAWS consistently outperformed fixed-window benchmarks. For instance, in the nurse staffing experiment, SAWS achieved a lower loss than all fixed-window benchmarks considered.
  • Improved Efficiency: The paper introduces more efficient versions of the algorithm (Algorithms 3 and 4) that reduce the computational complexity by using a geometric sequence of candidate windows and a caching mechanism.

Limitations and Future Work

  • Threshold Selection: The paper notes that the threshold sequence in the algorithm relies on knowledge of the function class, smoothness parameters, and noise levels. Future work could explore adaptive thresholds to handle these parameters more flexibly.
  • Prior Knowledge Integration: The current approach assumes no prior knowledge of non-stationarity. Incorporating available forecasts or structural information about the underlying dynamics could further boost performance.
  • Other Performance Measures: Investigating whether the approach enjoys good theoretical guarantees with respect to other performance measures, such as strongly adaptive regret, is a promising direction.
  • Extension to Sequential Decision-Making: A significant future direction is to extend the framework to sequential decision-making problems with partial feedback, such as bandit problems and reinforcement learning, where exploration-exploitation trade-offs become crucial in non-stationary environments.

Summary updated

Abstract

We develop a versatile framework for statistical learning in nonstationary 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 nonstationarity. 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 nonstationary data sequence into quasistationary pieces. We evaluate the practical performance of our approach through real-data experiments on electricity demand prediction and hospital nurse staffing. Funding: This work was supported by the Data Science Institute, Columbia University [Seed Grant SF-181], the National Science Foundation [Grant DMS-2210907], and Fu Foundation School of Engineering and Applied Science (startup grant). Supplemental Material: All supplemental materials, including the code, data, and files required to reproduce the results are available at https://doi.org/10.1287/opre.2024.0766.
BibTeX
@inproceedings{huang2025stability,
  author = {Chengpiao Huang and Kaizheng Wang},
  title = {{A Stability Principle for Learning Under Nonstationarity}},
  booktitle = {Operations Research},
  year = {2025},
  url = {https://openreview.net/forum?id=qUibOuHNu9},
}
Figure