Data Reuse in Non-Stationary Learning
Abstract
We consider online learning in non-stationary environments, where the goal is to track an unknown parameter that switches abruptly between a finite set of recurring values. Recurrence opens the possibility of judiciously reusing past observations to improve algorithm performance. However, the changing nature of the underlying signal and lack of information on these dynamics may limit the ability to "safely" reuse data. In this paper we quantify some of the fundamental tradeoffs in this class of problems, and show that they bear a certain resemblance to the classical bias-variance dilemma. Specifically, we propose a class of anytime algorithms, dubbed Exposure-Capped Reuse (ECR), that combine online change detection, compatibility testing, and "contamination" control. We characterize the regime in which ECR's regret scales with the number of distinct values rather than the number of changes, and derive a novel information-theoretic lower bound that establishes the near-minimax optimality of ECR. This provides rigorous quantification of the statistical "value" of data reuse.
Related
- Matching Complexity for Second-Order Stationary Point with Sample Reuse
- Energetic Variational Deep Learning for Solving High-Dimensional Stationary Fokker-Planck Equations
- Detection Augmented Learning In Non-Stationary Bandit Environments
- Resilience Beyond Stationary Client Unavailability: Unlocking Efficient and Unbiased Federated Learning
- Parametric Resonance in Primal-Dual Learning for Slowly Non-Stationary Constrained MDPs
BibTeX
@misc{gafni2026data,
title = {{Data Reuse in Non-Stationary Learning}},
author = {Tomer Gafni and Garud Iyengar and Assaf Zeevi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.10340},
eprint = {2610.10340},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.10340},
}
RIS
TY - UNPB
TI - Data Reuse in Non-Stationary Learning
AU - Tomer Gafni
AU - Garud Iyengar
AU - Assaf Zeevi
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.10340
UR - https://arxiv.org/abs/2610.10340
AB - We consider online learning in non-stationary environments, where the goal is to track an unknown parameter that switches abruptly between a finite set of recurring values. Recurrence opens the possibility of judiciously reusing past observations to improve algorithm performance. However, the changing nature of the underlying signal and lack of information on these dynamics may limit the ability to "safely" reuse data. In this paper we quantify some of the fundamental tradeoffs in this class of problems, and show that they bear a certain resemblance to the classical bias-variance dilemma. Specifically, we propose a class of anytime algorithms, dubbed Exposure-Capped Reuse (ECR), that combine online change detection, compatibility testing, and "contamination" control. We characterize the regime in which ECR's regret scales with the number of distinct values rather than the number of changes, and derive a novel information-theoretic lower bound that establishes the near-minimax optimality of ECR. This provides rigorous quantification of the statistical "value" of data reuse.
ER -