The Sample Complexity of Multiple Change Point Identification under Bandit Feedback

arXiv:2605.13252 · stat.ML, cs.LG, math.ST, stat.TH · Submitted 2026-05-13 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: We're looking at the paper: "The Sample Complexity of Multiple Change Point Identification under Bandit Feedback".

Jane: Here's the gist of the paper. The gist The authors propose an adaptive algorithm, LocalizeChangePoints, for identifying multiple change points in a piecewise-constant function under bandit feedback, establishing non-asymptotic sample complexity bounds that depend jointly on jump magnitudes and relative positions of the change points.

Tom: Problem Formulation The problem involves identifying a prescribed number of discontinuities within a target precision η and confidence level 1 − δ using adaptively chosen inputs to an unknown piecewise-constant function f:

0, 1: → R with m change points at positions 0 The learner sequentially and adaptively queries points xt ∈

0, 1: and observes yt = f(xt) + εt, where εt is sub-Gaussian noise<ref:2605.13252#pg5> Given a target number of change points N ⩽ m, a precision η ∈ (0, 1), and an error rate δ ∈ (0, 1), the goal is to output N estimates within distance η of true change points with probability at least 1−δ<ref:2605.13252#pg5> The sample complexity, denoted by T, is the total number of evaluations required to achieve this guarantee<ref:2605.13252#pg5> Algorithm and Guarantees The proposed algorithm, LocalizeChangePoints (Algorithm 2), decomposes the task into two main parts: (i) detecting intervals likely to contain change points and (ii) sequential refinement by binary search<ref:2605.13252#pg5> The overall budget bound is given by Theorem 1, which states that the budget T for localizing N change points among m is bounded, up to logarithmic terms independent of δ and η<ref:2605.13252#pg5> Specifically, the high-probability bound on the required budget when δexplore = δ is T ≤ c · ω1H(m)detect log 1/δ + ω2 + H(N)localize log 1/η + ω3<ref:2605.13252#pg5> The expectation bound is E

T: ≤ c · ω1H(m)detectω2 + H(N)localize log 1/η + ω3<ref:2605.13252#pg5> Complexity Measures The sample complexity is governed by two main components: H(m)detect and H(N)localize<ref:2605.13252#pg5> The detection complexity term is defined as H(m)detect = max i=1, m 1/E 2i<ref:2605.13252#pg5> The localization complexity term is H(N)localize = PN i=1 1/Delta 2(i)<ref:2605.13252#pg5> The paper demonstrates that the complexity is driven by the N largest jumps in the asymptotic regime δ → 0, but for general δ and η, it is jointly governed by the jumps and the relative positions of the change points<ref:2605.13252#pg5> Key Insights The analysis reveals that energy E 2i = siDelta 2i also matters in the active setting, leading to a detection complexity term H(m)detect = max i=1, m 1/E 2i<ref:2605.13252#pg5> This is shown to be at least as large as 1/2H(N)localize<ref:2605.13252#pg5> The algorithm adapts to local spacings si, which is practically significant when change points may be arbitrarily close and the spacing is unknown<ref:2605.13252#pg5> This adaptation allows the dependence on precision η to be logarithmic, namely log(1/η), which is exponentially better than the linear dependence on the discretization grid K ≃ 1/η inherent to discrete approaches<ref:2605.13252#pg5> Lower Bounds and Optimality The information-theoretic lower bounds show that the asymptotic rate in (1) is overly optimistic<ref:2605.13252#pg5> Theorem 2 establishes a lower bound on the budget T for any (δ, η, m)-correct algorithm π when N = m<ref:2605.13252#pg5> The lower bound is given by Pπ,ν'Tπ ⩾ 1/4H(m,ν)detect log 1/8δ + 1/2H(m,ν)localize log 1/8δ + Xm i=1 1/Delta 2i log+ si 16η!<ref:2605.13252#pg5> The case N = m also yields a rate-optimal sample complexity in the limit δ → 0<ref:2605.13252#pg5> Numerical Validation Numerical experiments validate the theory, showing that for moderate choices of δ, asking for a small precision (or considering many arms in the discrete case) does not limit the performance of LCP, in contrast to MCPI<ref:2605.13252#pg5> Experiment 3 shows that for LCP, there is only a small increase of the budget when η decreases, compared to MCPI<ref:2605.13252#pg5> The work demonstrates that the total complexity splits into a detection cost H(m)detect and a localization cost H(N)localize log 1/η<ref:2605.13252#pg5> The algorithm provides non-asymptotic guarantees that depend on both jump magnitudes and local spacings si, highlighting the additional role of spacing between CP<ref:2605.13252#pg5> The results confirm that adaptation to local spacings is essential for outperforming methods like MCPI for moderate values of s<ref:2605.13252#pg5> How it works The algorithm follows a doubling schedule where at each stage k, it performs four steps: (i) Detection using DetectIntervals (Algorithm 1), which uses multiscale endpoint tests to find intervals likely to contain a change point<ref:2605.13252#pg5> (ii) Jump estimation using EstimateJumps (Algorithm 3), which adaptively estimates jump magnitudes on candidate intervals<ref:2605.13252#pg5> (iii) Refinement of localization using SHB, which uses Sequential Halving with Backtracking to localize a single change point up to precision η under a fixed budget constraint<ref:2605.13252#pg5> (iv) Verification using VerifyCP (Algorithm 5), which performs a two-sample test at the neighborhood of an estimated change point to certify its presence with high probability<ref:2605.13252#pg5> Key Components 1.

Jane: Detection of Change Points: Algorithm 1 uses multiple-scale endpoint tests to flag intervals based on empirical jump exceeding a Hoeffding threshold βd<ref:2605.13252#pg5> 2.

Tom: Jump Estimation: Algorithm 3 employs an adaptive estimation routine where active intervals receive more samples as they are considered, allowing large jumps to be accepted early<ref:2605.13252#pg5> 3.

Title and authors: Tom: The title itself, "The Sample Complexity of Multiple Change Point Identification under Bandit Feedback", tells you right away that this isn't just about finding one change point anymore. It focuses on how many total samples you need when there are multiple discontinuities involved.

Jane: And they brought in these authors, Maximilian Graf and Victor Thuot, from institutions like the Institut für Mathematik at Universität Potsdam and INRAE in Montpellier.

Lu: They seem to be coming from a strong math background, which makes sense since this whole paper is deeply rooted in establishing formal bounds on how many samples are needed.

Tom: Right. The title signals that they aren't just looking for any solution, but they are rigorously defining the limits of what's possible with this adaptive approach.

The paper's summary: Jane: So, what’s the actual mechanism they’re proposing? They introduce Algorithm two which starts by detecting intervals likely to contain change points and then uses a sequential refinement method called binary search <ref:2605.13252#pg3,detecting intervals likely to contain change points and>.

Tom: That detection step is crucial because it cuts down on the total number of samples you have to check across the whole interval.

Lu: The key innovation they point out is that their non-asymptotic sample complexity bounds actually depend on two things: the size of the jumps themselves, which they call i, and how close those change points are to each other, which they call local spacings s i.

Jane: That means their theoretical guarantees aren't just based on the biggest jump you see; it also account for how tightly packed the changes might be.

The paper's improvements: Tom: What’s interesting is how they move beyond previous work, like MCPI, which they mention. They show that relying only on the jump magnitudes alone isn't enough to understand the complexity when you are not in that extreme asymptotic regime where delta goes to zero.

Jane: They prove that their new algorithm provides a budget bound T that depends on both those jump magnitudes and the local spacings, which they formalize using terms like E i and i.

Lu: This is significant because it suggests that energy, defined as E two i = s i two i, matters in the active setting, meaning we should prioritize sampling change points with higher energy or smaller spacings <ref:2605.13252#pg3>.

Conclusion: Tom: So, to wrap up this discussion on "The Sample Complexity of Multiple Change Point Identification under Bandit Feedback," the paper gives us a budget T that is bounded by terms related to detection complexity and localization complexity, which explicitly include those jump magnitudes and local spacings we just talked about.

Jane: It confirms that the adaptive approach of LocalizeChangePoints is more robust because it doesn't just focus on the largest jumps but also respects how close those change points are packed together.

Lu: And from a theoretical standpoint, the information-theoretic lower bounds they present, like Theorem two actually show that some previous asymptotic rates were too optimistic for what was achievable <ref:2605.13252#pg3>.

Meng: From a deployment view, it means if you're running this at scale and need to deploy it on real traffic where change points might be clustered in weird ways, you have to account for these local spacings s i because ignoring them could lead to way more samples than you think.

Lalam: I can confirm that the paper provides non-asymptotic upper bounds for both the high-probability regime and the expected budget regime, tying everything together with these two main complexity components.

Tom: That’s a lot of math packed into one idea about how much data we need to find multiple changes in a sequence.

Jane: It definitely shifts the focus from just getting an asymptotic rate when delta is tiny to understanding the real-world trade-offs involving precision and clustering.

Maximilian Graf, Victor Thuot

Institut für Mathematik, University Potsdam · INRAE · Institut Agro, Univ Montpellier

stat.ML, cs.LG, math.ST, stat.TH

Submitted: 2026-05-13

Updated: 2026-10-21

Comments: Accepted at NeurIPS 2026. 43 pages. v2: camera-ready version (extended related work, refined comparison with MCPI, corrected Lemma 1/Lemma 4 statements, code release)

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 83/100

The gist: The gist The authors propose an adaptive algorithm, LocalizeChangePoints, for identifying multiple change points in a piecewise-constant function under bandit feedback, establishing non-asymptotic

Key concepts

LocalizeChangePoints: An adaptive algorithm designed to find multiple change points in a function. It works by first detecting likely intervals and then sequentially refining their locations using binary search. This approach minimizes the total number of evaluations needed to achieve high precision.
Sample Complexity Bounds: Mathematical guarantees on the minimum number of queries (samples) required to reliably identify the change points within a certain error margin and confidence level. The paper derives bounds that depend on both how large the jumps are and how close together or far apart the change points are located.
Energy Measure E^2i: A measure used to model the difficulty of detecting a specific change point, defined as s_i * Delta^2_i. This term captures how much influence a jump has on the overall complexity, particularly when considering the local spacing (s_i) between potential change points.
Precision-Dependent Budget Allocation: The strategy of allocating samples based on the inverse squared estimated jump magnitude. This ensures that as required precision (eta) gets smaller, the budget scales logarithmically with 1/eta, which is much more efficient than methods that rely on a fixed discretization grid.

Terminology

Sample Complexity — 2× in this paper · explained in 20 episodes
Adaptive Algorithm — 1× in this paper

Summary

The gist The authors propose an adaptive algorithm, LocalizeChangePoints, for identifying multiple change points in a piecewise-constant function under bandit feedback, establishing non-asymptotic sample complexity bounds that depend jointly on jump magnitudes and relative positions of the change points.

Problem Formulation

The problem involves identifying a prescribed number of discontinuities within a target precision η and confidence level 1 − δ using adaptively chosen inputs to an unknown piecewise-constant function f: [0, 1] → R with m change points at positions 0 The learner sequentially and adaptively queries points xt ∈ [0, 1] and observes yt = f(xt) + εt, where εt is sub-Gaussian noise<ref:2605.13252#pg5> Given a target number of change points N ⩽ m, a precision η ∈ (0, 1), and an error rate δ ∈ (0, 1), the goal is to output N estimates within distance η of true change points with probability at least 1−δ<ref:2605.13252#pg5> The sample complexity, denoted by T, is the total number of evaluations required to achieve this guarantee<ref:2605.13252#pg5>

Algorithm and Guarantees

The proposed algorithm, LocalizeChangePoints (Algorithm 2), decomposes the task into two main parts: (i) detecting intervals likely to contain change points and (ii) sequential refinement by binary search<ref:2605.13252#pg5> The overall budget bound is given by Theorem 1, which states that the budget T for localizing N change points among m is bounded, up to logarithmic terms independent of δ and η<ref:2605.13252#pg5> Specifically, the high-probability bound on the required budget when δexplore = δ is T ≤ c · ω1H(m)detect log 1/δ + ω2 + H(N)localize log 1/η + ω3<ref:2605.13252#pg5> The expectation bound is E[T] ≤ c · ω1H(m)detectω2 + H(N)localize log 1/η + ω3<ref:2605.13252#pg5>

Complexity Measures

The sample complexity is governed by two main components: H(m)detect and H(N)localize<ref:2605.13252#pg5> The detection complexity term is defined as H(m)detect = max i=1, m 1/E 2i<ref:2605.13252#pg5> The localization complexity term is H(N)localize = PN i=1 1/Delta 2(i)<ref:2605.13252#pg5> The paper demonstrates that the complexity is driven by the N largest jumps in the asymptotic regime δ → 0, but for general δ and η, it is jointly governed by the jumps and the relative positions of the change points<ref:2605.13252#pg5>

Key Insights

The analysis reveals that energy E 2i = siDelta 2i also matters in the active setting, leading to a detection complexity term H(m)detect = max i=1, m 1/E 2i<ref:2605.13252#pg5> This is shown to be at least as large as 1/2H(N)localize<ref:2605.13252#pg5> The algorithm adapts to local spacings si, which is practically significant when change points may be arbitrarily close and the spacing is unknown<ref:2605.13252#pg5> This adaptation allows the dependence on precision η to be logarithmic, namely log(1/η), which is exponentially better than the linear dependence on the discretization grid K ≃ 1/η inherent to discrete approaches<ref:2605.13252#pg5>

Lower Bounds and Optimality

The information-theoretic lower bounds show that the asymptotic rate in (1) is overly optimistic<ref:2605.13252#pg5> Theorem 2 establishes a lower bound on the budget T for any (δ, η, m)-correct algorithm π when N = m<ref:2605.13252#pg5> The lower bound is given by Pπ,ν'Tπ ⩾ 1/4H(m,ν)detect log 1/8δ + 1/2H(m,ν)localize log 1/8δ + Xm i=1 1/Delta 2i log+ si 16η!<ref:2605.13252#pg5> The case N = m also yields a rate-optimal sample complexity in the limit δ → 0<ref:2605.13252#pg5>

Numerical Validation

Numerical experiments validate the theory, showing that for moderate choices of δ, asking for a small precision (or considering many arms in the discrete case) does not limit the performance of LCP, in contrast to MCPI<ref:2605.13252#pg5> Experiment 3 shows that for LCP, there is only a small increase of the budget when η decreases, compared to MCPI<ref:2605.13252#pg5>

Conclusion

The work demonstrates that the total complexity splits into a detection cost H(m)detect and a localization cost H(N)localize log 1/η<ref:2605.13252#pg5> The algorithm provides non-asymptotic guarantees that depend on both jump magnitudes and local spacings si, highlighting the additional role of spacing between CP<ref:2605.13252#pg5> The results confirm that adaptation to local spacings is essential for outperforming methods like MCPI for moderate values of s<ref:2605.13252#pg5>

How it works

The algorithm follows a doubling schedule where at each stage k, it performs four steps: (i) Detection using DetectIntervals (Algorithm 1), which uses multiscale endpoint tests to find intervals likely to contain a change point<ref:2605.13252#pg5> (ii) Jump estimation using EstimateJumps (Algorithm 3), which adaptively estimates jump magnitudes on candidate intervals<ref:2605.13252#pg5> (iii) Refinement of localization using SHB, which uses Sequential Halving with Backtracking to localize a single change point up to precision η under a fixed budget constraint<ref:2605.13252#pg5> (iv) Verification using VerifyCP (Algorithm 5), which performs a two-sample test at the neighborhood of an estimated change point to certify its presence with high probability<ref:2605.13252#pg5>

Key Components

Detection of Change Points: Algorithm 1 uses multiple-scale endpoint tests to flag intervals based on empirical jump exceeding a Hoeffding threshold βd<ref:2605.13252#pg5>
Jump Estimation: Algorithm 3 employs an adaptive estimation routine where active intervals receive more samples as they are considered, allowing large jumps to be accepted early<ref:2605.13252#pg5>
Refinement of Localization: Algorithm 4 uses SHB to sequentially zoom into a candidate interval, allocating budget proportional to the inverse squared estimated jump, T(k)v = j/α(k)v · 2 k k/1<ref:2605.13252#pg5>
Verification: Algorithm 5 uses a two-sample test to check whether candidate points lie within distance η of true change points with confidence level δ(k)<ref:2605.13252#pg5>

Summary of Contributions

The contributions include the proposal of LocalizeChangePoints (Algorithm 2), which decomposes the task into detection and sequential refinement<ref:2605.13252#pg5> Derivation of non-asymptotic sample-complexity guarantees that depend on both jump magnitudes and local spacings through Ei and Deltai<ref:2605.13252#pg5> Derivation of information-theoretic lower bounds (Theorem 2) showing that the asymptotic rate in (1) is overly optimistic<ref:2605.13252#pg5> Numerical validation on synthetic data confirms the theoretical findings<ref:2605.13252#pg5>

Limitations

The lower bounds are limited to the case N = m, so the optimal trade-off when N < m is still an open question<ref:2605.

Improvements for AI systems

Adaptive Change Point Localization in Continuous Systems: The algorithm LocalizeChangePoints can be used to identify multiple change points in a piecewise-constant function on a continuous interval, minimizing total evaluations by first detecting likely intervals and then refining their locations to precision eta.
Energy-Based Complexity Modeling: AI systems can leverage the energy measure E2i = siDelta2i to understand the difficulty of detecting each change point, allowing for tailored sampling strategies that prioritize change points with higher energy or smaller local spacings.
Precision-Dependent Budget Allocation: The algorithm provides a method to allocate sample budget proportional to inverse squared estimated jump magnitudes, ensuring that the localization cost scales optimally with the required precision eta, leading to a dependence of log(1/eta) rather than linear dependence on discretization grid size K.
Robust Guarantees Under Confidence and Precision: The system offers non-asymptotic upper bounds on sample complexity T that explicitly depend on both jump magnitudes (Hdetect) and local spacings (Hlocalize), providing guarantees in both the high-probability regime (Theorem 1, point 2) and the expected budget regime (Theorem 1, point 3).
Optimal Trade-off Analysis: By analyzing information-theoretic lower bounds like Theorem 2, AI models can determine the optimal achievable dependence on precision eta and confidence level delta for active change point detection in continuous settings.

Sources

A review on minimax rates in change point detection and localisation