提出新算法应对多突变点环境下的学习难题，避免传统方法失效。
The Cost of Learning Under Multiple Change Points
- 设计无时域限制的ATC算法，选择性检测显著变化
- 理论证明其后悔值接近信息论下界，性能近乎最优
- 适用于动态环境中的在线学习，尤其适合突变频繁场景
我们研究存在多个变化点的在线学习问题。与广泛使用经典‘高置信度’检测方法的单变化点问题不同，多变化点环境带来了新的学习理论与算法挑战。我们发现，经典方法可能因称为‘内生混淆’的现象而出现灾难性失败（高后悔值）。为此，我们提出一类新型学习算法——任意时间跟踪CUSUM（ATC），其为无时域限制的在线算法，采用选择性检测原则，在忽略‘小’（难以检测）变动的同时快速响应显著变化。我们证明，经过恰当调参的ATC算法性能几乎达到最小最大最优；其后悔值可紧密逼近多变化点问题中任意学习算法可实现性能的新信息论下界。在合成数据和真实世界数据上的实验验证了上述理论结果。
原文摘要 · Abstract (English)
We consider an online learning problem in environments with multiple change points. In contrast to the single change point problem that is widely studied using classical "high confidence" detection schemes, the multiple change point environment presents new learning-theoretic and algorithmic challenges. Specifically, we show that classical methods may exhibit catastrophic failure (high regret) due to a phenomenon we refer to as endogenous confounding. To overcome this, we propose a new class of learning algorithms dubbed Anytime Tracking CUSUM (ATC). These are horizon-free online algorithms that implement a selective detection principle, balancing the need to ignore "small" (hard-to-detect) shifts, while reacting "quickly" to significant ones. We prove that the performance of a properly tuned ATC algorithm is nearly minimax-optimal; its regret is guaranteed to closely match a novel information-theoretic lower bound on the achievable performance of any learning algorithm in the multiple change point problem. Experiments on synthetic as well as real-world data validate the aforementioned theoretical findings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。