The Cost of Learning under Multiple Change Points

2026-02-13 · Source: stat.ML updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Data Science & Analytics · Depth: Expert, extended

Summary

This paper addresses online learning in environments with multiple change points, a scenario where traditional "high confidence" detection methods can fail due to "endogenous confounding." This phenomenon occurs when a learning algorithm's failure to detect a change causes outdated data to mix with new data, degrading the signal-to-noise ratio for subsequent change detection. To counter this, the authors propose a new class of horizon-free online algorithms called Anytime Tracking CUSUM (ATC). ATC implements a selective detection principle, balancing the need to ignore small, hard-to-detect shifts while reacting quickly to significant ones. The paper proves that a properly tuned ATC algorithm achieves nearly minimax-optimal performance, with its regret closely matching a novel information-theoretic lower bound. Experimental results on both synthetic and real-world data, including AWS CPU usage from the NAB dataset, validate these theoretical findings, demonstrating ATC's superior performance compared to sliding-window and discounted-mean baselines.

Key takeaway

For AI Scientists developing online learning systems in dynamic, non-stationary environments, this research highlights the critical challenge of endogenous confounding in multiple change-point scenarios. You should consider implementing adaptive algorithms like Anytime Tracking CUSUM (ATC) that employ selective detection and time-varying thresholds. This approach is crucial for maintaining low regret and robust performance, especially when dealing with unknown numbers of shifts or long time horizons, as it prevents cascading detection failures and ensures efficient resource allocation or data processing.

Key insights

Endogenous confounding in multiple change-point environments necessitates selective, adaptive detection to achieve optimal online learning.

Principles

• Not all changes require detection.
• Time-varying thresholds improve detection robustness.
• Minimax regret analysis offers worst-case performance guarantees.

Method

The Anytime Tracking CUSUM (ATC) algorithm uses a CUSUM-style statistic with a time-varying threshold to selectively detect significant mean shifts, restarting its estimator upon alarm without prior knowledge of horizon or number of changes.

In practice

• Apply ATC for real-time demand tracking.
• Use ATC for online data compression.
• Extend ATC to vector-valued observations.

Topics

• Online Learning
• Change Point Detection
• Anytime Tracking CUSUM
• Dynamic Regret
• Minimax Optimality

Best for: AI Scientist, AI Researcher, Research Scientist, AI Student

Related on AIssential

• Online Detection of Changes in Moment--Based Projections: When to Retrain Deep Learners or Update Portfolios? — Sequential monitoring of deep learning predictions can reduce retraining costs and enable green AI.
• Efficient Online Conformal Selection with Limited Feedback — The ACI update rule ensures valid and efficient conformal selection even with limited bandit feedback.
• LargeMonitor: Monitoring Online Task-Free Continual Learning via Large Pretrained Models — LargeMonitor uses foundation models to detect and diagnose data stream drift in TFCL, enabling adaptive learning strategies.
• Online LLM Selection via Constrained Bandits with Time-Varying Demand — Online LLM selection under dynamic demand and hard/soft constraints can be optimized using constrained bandit learning.
• Trajectory-Aware Adaptive Inference in Object Detection Models — Integrating trajectory data into YOLOv8's inference enables adaptive computation, reducing latency while preserving accuracy.
• A probabilistic framework for online test-time adaptation — A probabilistic framework for online test-time adaptation quantifies uncertainty and improves model performance under distributional shifts.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by stat.ML updates on arXiv.org.