The Sample Complexity of Multiple Change Point Identification under Bandit Feedback

• URL: http://arxiv.org/abs/2605.13252v1
• Date: Wed, 13 May 2026 09:35:19 GMT
• Title: The Sample Complexity of Multiple Change Point Identification under Bandit Feedback
• Abstract summary: We study multiple change point localization under bandit feedback.<n>An unknown piecewise-constant function on a compact interval can be queried sequentially at adaptively chosen inputs.<n>The goal is to identify a prescribed number of discontinuities, known as change points, within a target precision $$.
• Score: 1.0312968200748118
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Almost Asymptotically Optimal Active Clustering Through Pairwise Observations [59.20614082241528]
  We propose a new analysis framework for clustering $M$ items into an unknown number of $K$ distinct groups using noisy and actively collected responses.<n>We establish a fundamental lower bound on the expected number of queries needed to achieve a desired confidence in the accuracy of the clustering.<n>We develop a computationally feasible variant of the Generalized Likelihood Ratio statistic and show that its performance gap to the lower bound can be accurately empirically estimated.
  arXiv  Detail & Related papers  (2026-02-05T14:16:47Z)
• Fixed-Confidence Multiple Change Point Identification under Bandit Feedback [4.373803477995854]
  Piecewise constant functions describe a variety of real-world phenomena in domains ranging from chemistry to manufacturing.<n>In practice, it is often required to confidently identify the locations of the abrupt changes in these functions as quickly as possible.<n>Here, we sequentially query points in the domain and receive noisy evaluations of the function under bandit feedback.
  arXiv  Detail & Related papers  (2025-07-11T19:52:11Z)
• Post-detection inference for sequential changepoint localization [29.43493007296859]
  We develop a framework to construct confidence sets for the unknown changepoint using only the data observed up to a data-dependent stopping time at which an arbitrary sequential detection algorithm declares a change.<n>Our framework is nonparametric, making no assumption on the composite post-change class, the observation space, or the sequential detection procedure used, and is nonasymptotically valid.
  arXiv  Detail & Related papers  (2025-02-10T02:01:30Z)
• Fixed-Budget Change Point Identification in Piecewise Constant Bandits [4.373803477995854]
  We provide the first non-asymptotic analysis of policies designed to locate abrupt changes in the mean reward function under bandit feedback.<n>We study the problem under a large and small budget regime, and for both settings establish lower bounds on the error probability.<n>We propose a regime adaptive algorithm which is near optimal for both small and large budgets simultaneously.
  arXiv  Detail & Related papers  (2025-01-22T15:30:44Z)
• On the Complexity of Finding Small Subgradients in Nonsmooth Optimization [37.300102993926046]
  We show that no dimension-free rate can be achieved by a deterministic algorithm.<n>We show how the convergence rate of finding $(delta,epsilon)$-stationary points can be improved in case the function is convex.
  arXiv  Detail & Related papers  (2022-09-21T13:30:00Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  We propose a novel method named Multi-block-probe Variance Reduced (MSVR) to alleviate the complexity of compositional problems. Our results improve upon prior ones in several aspects, including the order of sample complexities and dependence on strongity.
  arXiv  Detail & Related papers  (2022-07-18T12:03:26Z)
• E-detectors: a nonparametric framework for sequential change detection [86.15115654324488]
  We develop a fundamentally new and general framework for sequential change detection. Our procedures come with clean, nonasymptotic bounds on the average run length. We show how to design their mixtures in order to achieve both statistical and computational efficiency.
  arXiv  Detail & Related papers  (2022-03-07T17:25:02Z)
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond [63.59034509960994]
  We study shuffling-based variants: minibatch and local Random Reshuffling, which draw gradients without replacement. For smooth functions satisfying the Polyak-Lojasiewicz condition, we obtain convergence bounds which show that these shuffling-based variants converge faster than their with-replacement counterparts. We propose an algorithmic modification called synchronized shuffling that leads to convergence rates faster than our lower bounds in near-homogeneous settings.
  arXiv  Detail & Related papers  (2021-10-20T02:25:25Z)
• Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning [99.34907092347733]
  We analyze the problem of estimating optimal $Q$-value functions for a discounted Markov decision process with discrete states and actions. Using a local minimax framework, we show that this functional arises in lower bounds on the accuracy on any estimation procedure. In the other direction, we establish the sharpness of our lower bounds, up to factors logarithmic in the state and action spaces, by analyzing a variance-reduced version of $Q$-learning.
  arXiv  Detail & Related papers  (2021-06-28T00:38:54Z)
• Optimal network online change point localisation [73.93301212629231]
  We study the problem of online network change point detection. In this setting, a collection of independent Bernoulli networks is collected sequentially, and the underlying change point occurs. The goal is to detect the change point as quickly as possible, if it exists, subject to a constraint on the number or probability of false alarms.
  arXiv  Detail & Related papers  (2021-01-14T07:24:39Z)
• Stochastic Multi-level Composition Optimization Algorithms with Level-Independent Convergence Rates [12.783783498844022]
  We study smooth multi-level composition optimization problems, where the objective function is a nested composition of $T$ functions. We show that the first algorithm, which is a generalization of citeGhaRuswan20 to the $T$ level case, can achieve a sample complexity of $mathcalO (1/epsilon$6) This is the first time that such an online algorithm designed for the (un) multi-level setting, obtains the same sample complexity under standard assumptions.
  arXiv  Detail & Related papers  (2020-08-24T15:57:50Z)
• Multinomial Sampling for Hierarchical Change-Point Detection [0.0]
  We propose a multinomial sampling methodology that improves the detection rate and reduces the delay. Our experiments show results that outperform the baseline method and we also provide an example oriented to a human behavior study.
  arXiv  Detail & Related papers  (2020-07-24T09:18:17Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  We provide the first non-asymptotic analysis for finding stationary points of nonsmooth, nonsmooth functions. In particular, we study Hadamard semi-differentiable functions, perhaps the largest class of nonsmooth functions.
  arXiv  Detail & Related papers  (2020-02-10T23:23:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.