arXiv：cs.LG· Tomer Gafni, Garud Iyengar, Assaf Zeevi·· 4 小时前AI 评分29
非平稳学习中的数据复用：Exposure-Capped Reuse 算法
Data Reuse in Non-Stationary Learning
AI 导读
针对非平稳环境中参数在有限循环值间突变切换的在线学习问题，研究者提出 Exposure-Capped Reuse（ECR）算法，结合在线变化检测、兼容性测试与"污染"控制。ECR 在特定条件下 regret 随不同值的数量而非变化次数增长，并给出信息论下界证明其接近 minimax 最优。
正文
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.
| Subjects: | Machine Learning (stat.ML); Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.10340 [stat.ML] |
| (or arXiv:2610.10340v1 [stat.ML] for this version) | |
| https://doi.org/10.48550/arXiv.2610.10340 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Tomer Gafni [view email]
[v1]
Wed, 7 Oct 2026 16:20:23 UTC (755 KB)
来源：arXiv：cs.LG · arxiv.org