論文の概要: The Sample Complexity of Multiple Change Point Identification under Bandit Feedback
- arxiv url: http://arxiv.org/abs/2605.13252v1
- Date: Wed, 13 May 2026 09:35:19 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-14 23:30:27.948323
- Title: The Sample Complexity of Multiple Change Point Identification under Bandit Feedback
- Title（参考訳）: 帯域フィードバックによる多重変化点同定の複雑さ
- Authors: Maximilian Graf, Victor Thuot,
- Abstract要約: 帯域フィードバックによる複数の変化点の局所化について検討する。
コンパクト区間上の未知のピースワイズ・コンスタント関数は、適応的に選択された入力で順次クエリすることができる。
目標は、所定の数の不連続点(変更点)を目標精度$$で識別することである。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: 帯域フィードバックによる複数の変化点の局所化について検討する。
コンパクト区間上の未知のピースワイズ・コンスタント関数は、適応的に選択された入力で順次クエリされ、各クエリは関数のノイズ評価を返す。
目標は、変更点と呼ばれる所定の数の不連続性を、可能な限り少数のサンプルを使用しながら、目標精度$η$と信頼レベル$1-δ$で識別することである。
本稿では,まず変化点を含む可能性のある区間を検出し,その位置を精度$η$に改良する適応アルゴリズムを提案する。
サンプル予算の非漸近上界とそれに対応する下界を定めている。
以前の研究は、ジャンプ等級だけで漸近的なサンプルの複雑さを$δ\to 0$と決定していることを示している。
この図は、この体制を超えて不完全であることが明らかになる。
我々は、経験的かつ理論的に、一般の$δ$と$η$に対して、複雑さは変化点のジャンプと相対的な位置によって共同で支配されることを示した。
関連論文リスト
- Fixed-Confidence Multiple Change Point Identification under Bandit Feedback [4.373803477995854]
哲学的な定数関数は、化学から製造までの領域における様々な実世界の現象を表現している。
実際には、これらの機能の急激な変化の場所をできるだけ早く特定することが要求されることが多い。
ここでは,領域内の点を逐次問合せし,帯域幅フィードバックによる関数のノイズ評価を行う。
論文 参考訳（メタデータ） (2025-07-11T19:52:11Z) - Post-detection inference for sequential changepoint localization [29.43493007296859]
本研究では、任意の逐次検出アルゴリズムが変更を宣言するデータ依存停止時間までのデータのみを用いて、未知の変更点に対する信頼セットを構築するフレームワークを開発する。
我々のフレームワークは非パラメトリックであり、複合的なポストチェンジクラス、観測空間、あるいは使用されるシーケンシャルな検出手順を仮定せず、漸近的に有効である。
論文 参考訳（メタデータ） (2025-02-10T02:01:30Z) - Fixed-Budget Change Point Identification in Piecewise Constant Bandits [4.373803477995854]
本稿では,帯域フィードバックによる平均報酬関数の急激な変化を特定するために設計されたポリシーの非漸近解析を行う。
本研究では,大小の予算体制下で問題を調査し,両設定でエラー確率の低い境界を設定する。
本稿では,小規模・大規模両予算の両立に最適な適応型アルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-01-22T15:30:44Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - E-detectors: a nonparametric framework for sequential change detection [86.15115654324488]
逐次的変化検出のための基本的かつ汎用的なフレームワークを開発する。
私たちの手順は、平均走行距離のクリーンで無症状な境界が伴います。
統計的および計算効率の両方を達成するために,これらの混合物を設計する方法を示す。
論文 参考訳（メタデータ） (2022-03-07T17:25:02Z) - Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and
Beyond [63.59034509960994]
シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。
ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。
我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
論文 参考訳（メタデータ） (2021-10-20T02:25:25Z) - Instance-optimality in optimal value estimation: Adaptivity via
variance-reduced Q-learning [99.34907092347733]
本稿では,マルコフ決定過程における最適な$Q$値関数を離散状態と動作で推定する問題を解析する。
局所的なミニマックスフレームワークを用いて、この関数は任意の推定手順の精度の低い境界に現れることを示す。
他方,Q$ラーニングの分散還元版を解析することにより,状態と行動空間の対数的要因まで,下位境界のシャープさを確立する。
論文 参考訳（メタデータ） (2021-06-28T00:38:54Z) - Optimal network online change point localisation [73.93301212629231]
オンラインネットワーク変化点検出の問題点について検討する。
この設定では、独立したベルヌーイネットワークの集合が順次収集され、基礎となる変化点が生じる。
目的は、虚偽のアラームの数または確率の制約に応じて、それが存在する場合、変更点をできるだけ早く検出することです。
論文 参考訳（メタデータ） (2021-01-14T07:24:39Z) - Stochastic Multi-level Composition Optimization Algorithms with
Level-Independent Convergence Rates [12.783783498844022]
目的関数が$T$関数のネスト合成であるような,スムーズな多層合成最適化問題について検討する。
citeGhaRuswan20を$T$のレベルで一般化した最初のアルゴリズムは、$mathcalO (1/epsilon$6) のサンプル複雑性を実現することができることを示す。
これは、(アン)マルチレベル設定のために設計されたオンラインアルゴリズムが、標準仮定の下で同じサンプル複雑性を得るのはこれが初めてである。
論文 参考訳（メタデータ） (2020-08-24T15:57:50Z) - Multinomial Sampling for Hierarchical Change-Point Detection [0.0]
本稿では,検出率を向上し,遅延を低減する多項サンプリング手法を提案する。
実験の結果, 基準法よりも優れた結果が得られ, また, 人間の行動研究を指向した事例も提示した。
論文 参考訳（メタデータ） (2020-07-24T09:18:17Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳（メタデータ） (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。