Improving online tracking by safely reusing data in changing environments
Data Reuse in Non-Stationary Learning
Machine Learning
Summary
This paper looks at how to keep learning and predicting when the thing being studied changes suddenly but repeats past patterns. The authors explore how to reuse old data safely without making mistakes because the situation changes. They created a method called Exposure-Capped Reuse that detects changes and decides when old data helps or hurts. This approach nearly matches the best possible performance and explains what makes reusing data beneficial in such tricky cases.
What this means in practice
- •For real-time analytics teams: Improve tracking systems that face abrupt, repeated changes by reusing past data more effectively to reduce errors over time.
- •For adaptive control engineers: Design control algorithms that better handle sudden shifts in system parameters by selectively incorporating earlier observations.
Authors
Tomer Gafni, Garud Iyengar, Assaf Zeevi
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.