在有限样本下精准定位多个突变点，揭示位置关系对检测难度的关键影响。
The Sample Complexity of Multiple Change Point Identification under Bandit Feedback
- 自适应选择查询点，先定位可能含突变点的区间，再精细逼近位置。
- 理论与实验表明，样本复杂度由跳跃大小和突变点相对位置共同决定。
- 适用于需要高精度突变检测且样本成本敏感的动态系统分析场景。
我们研究在贝叶斯反馈下的多突变点定位问题。一个未知的分段常数函数在紧区间上可逐次自适应查询，每次查询返回函数的带噪评估值。目标是在给定精度η和置信度1−δ下，识别出指定数量的不连续点（即突变点），同时最小化采样次数。本文提出一种自适应算法：首先检测可能包含突变点的区间，然后精炼其位置至η精度。我们建立了非渐近的样本预算上界，并给出了相应的下界。已有研究指出，当δ→0时，跳跃幅度决定渐近样本复杂度。本文揭示，在一般δ和η条件下，复杂度由跳跃大小与突变点相对位置共同决定。
原文摘要 · Abstract (English)
We study multiple change point localization under bandit feedback. An unknown piecewise-constant function on a compact interval can be queried sequentially at adaptively chosen inputs, and each query returns a noisy evaluation of the function. The goal is to identify a prescribed number of discontinuities, known as change points, within a target precision $η$ and confidence level $1-δ$, while using as few samples as possible. We propose an adaptive algorithm that first detects intervals likely to contain change points and then refines their locations to precision $η$. We establish non-asymptotic upper bounds on its sample budget, together with corresponding lower bounds. Prior work shows that jump magnitudes alone determine the asymptotic sample complexity as $δ\to 0$. We reveal that this picture is incomplete beyond this regime. We demonstrate, both empirically and theoretically, that for general $δ$ and $η$, the complexity is jointly governed by the jumps and the relative positions of the change points.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。