Fixed-Confidence Multiple Change Point Identification under Bandit Feedback

• URL: http://arxiv.org/abs/2507.08994v1
• Date: Fri, 11 Jul 2025 19:52:11 GMT
• Title: Fixed-Confidence Multiple Change Point Identification under Bandit Feedback
• Abstract summary: 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.
• Score: 4.373803477995854
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Piecewise constant functions describe a variety of real-world phenomena in domains ranging from chemistry to manufacturing. In practice, it is often required to confidently identify the locations of the abrupt changes in these functions as quickly as possible. For this, we introduce a fixed-confidence piecewise constant bandit problem. Here, we sequentially query points in the domain and receive noisy evaluations of the function under bandit feedback. We provide instance-dependent lower bounds for the complexity of change point identification in this problem. These lower bounds illustrate that an optimal method should focus its sampling efforts adjacent to each of the change points, and the number of samples around each change point should be inversely proportional to the magnitude of the change. Building on this, we devise a simple and computationally efficient variant of Track-and-Stop and prove that it is asymptotically optimal in many regimes. We support our theoretical findings with experimental results in synthetic environments demonstrating the efficiency of our method.

Related papers

• Unveiling the Entropy Dynamics of Chain-of-Thought Reasoning [81.57028614960576]
  We show that the Confidence Region possesses two critical properties: 1) High Reliability -- answers in the confidence region become highly accurate and stable, and 2) High Redundancy -- models generate unnecessary tokens long after reaching the correct answer.<n>These properties unlock more efficient and reliable inference strategies.
  arXiv  Detail & Related papers  (2026-06-01T10:11:14Z)
• The Sample Complexity of Multiple Change Point Identification under Bandit Feedback [1.0312968200748118]
  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 $$.
  arXiv  Detail & Related papers  (2026-05-13T09:35:19Z)
• Conformal changepoint localization [36.191356601153146]
  We study the problem of offline changepoint localization in a distribution-free setting.<n>We produce a finite-sample confidence set for the index at which the change occurs without making any other assumptions.<n>Experiments suggest that CONCH delivers precise confidence sets even in challenging settings involving images or text.
  arXiv  Detail & Related papers  (2026-02-05T23:50:53Z)
• Variation-Bounded Loss for Noise-Tolerant Learning [105.20373602308284]
  We introduce the Variation Ratio as a novel property related to the robustness of loss functions.<n>We propose a new family of robust loss functions, termed Variation-Bounded Loss (VBL), which is characterized by a bounded variation ratio.
  arXiv  Detail & Related papers  (2025-11-15T10:15:29Z)
• Theoretical guarantees for change localization using conformal p-values [36.191356601153146]
  We provide theoretical guarantees for a method to achieve distribution-free changepoint localization with finite-sample validity.<n>We also present various finite sample and properties of the conformal $p$-value in the distribution change setup.<n>Our contributions offer a comprehensive and theoretically principled approach to distribution-free changepoint inference.
  arXiv  Detail & Related papers  (2025-10-09T19:05:47Z)
• Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up [29.55535031689754]
  We show that Scaffold achieves linear speed-up in the number of clients up to higher-order terms in the step size.<n>Our analysis reveals that Scaffold retains a higher-order bias, similar to FedAvg, that does not decrease as the number of clients increases.
  arXiv  Detail & Related papers  (2025-03-10T17:56:19Z)
• 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)
• 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)
• Inference for Change Points in High Dimensional Mean Shift Models [10.307668909650449]
  We consider the problem of constructing confidence intervals for the locations of change points in a high-dimensional mean shift model. We develop a locally refitted least squares estimator and obtain component-wise and simultaneous rates of estimation of the underlying change points. The results are established under a high dimensional scaling, allowing in the presence of diverging number of change points and under subexponential errors.
  arXiv  Detail & Related papers  (2021-07-19T20:56:15Z)
• 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)
• Change Point Detection in Time Series Data using Autoencoders with a Time-Invariant Representation [69.34035527763916]
  Change point detection (CPD) aims to locate abrupt property changes in time series data. Recent CPD methods demonstrated the potential of using deep learning techniques, but often lack the ability to identify more subtle changes in the autocorrelation statistics of the signal. We employ an autoencoder-based methodology with a novel loss function, through which the used autoencoders learn a partially time-invariant representation that is tailored for CPD.
  arXiv  Detail & Related papers  (2020-08-21T15:03:21Z)
• 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)
• Making Affine Correspondences Work in Camera Geometry Computation [62.7633180470428]
  Local features provide region-to-region rather than point-to-point correspondences. We propose guidelines for effective use of region-to-region matches in the course of a full model estimation pipeline. Experiments show that affine solvers can achieve accuracy comparable to point-based solvers at faster run-times.
  arXiv  Detail & Related papers  (2020-07-20T12:07:48Z)
• Optimal Change-Point Detection with Training Sequences in the Large and Moderate Deviations Regimes [72.68201611113673]
  This paper investigates a novel offline change-point detection problem from an information-theoretic perspective. We assume that the knowledge of the underlying pre- and post-change distributions are not known and can only be learned from the training sequences which are available.
  arXiv  Detail & Related papers  (2020-03-13T23:39:40Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  We propose a novel technique for analyzing adaptive sampling called the em Simulator. We prove the first instance-based lower bounds the top-k problem which incorporate the appropriate log-factors. Our new analysis inspires a simple and near-optimal for the best-arm and top-k identification, the first em practical of its kind for the latter problem.
  arXiv  Detail & Related papers  (2017-02-16T23:42:02Z)

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.