The Sample Complexity of Multiple Change Point Identification under Bandit Feedback

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.