論文の概要: Fixed-Confidence Multiple Change Point Identification under Bandit Feedback
- arxiv url: http://arxiv.org/abs/2507.08994v1
- Date: Fri, 11 Jul 2025 19:52:11 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-15 18:48:22.066593
- Title: Fixed-Confidence Multiple Change Point Identification under Bandit Feedback
- Title（参考訳）: 帯域フィードバックによる信頼度多重変化点同定
- Authors: Joseph Lazzaro, Ciara Pike-Burke,
- Abstract要約: 哲学的な定数関数は、化学から製造までの領域における様々な実世界の現象を表現している。
実際には、これらの機能の急激な変化の場所をできるだけ早く特定することが要求されることが多い。
ここでは,領域内の点を逐次問合せし,帯域幅フィードバックによる関数のノイズ評価を行う。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: 哲学的な定数関数は、化学から製造までの領域における様々な実世界の現象を表現している。
実際には、これらの機能の急激な変化の場所をできるだけ早く特定することが要求されることが多い。
これに対し、固定信頼区間定数バンドイット問題を導入する。
ここでは,領域内の点を逐次問合せし,帯域幅フィードバックによる関数のノイズ評価を行う。
この問題において、変更点識別の複雑さに対して、インスタンス依存の低い境界を提供する。
これらの下限は、最適な方法は各変化点に隣接するサンプリング作業に集中すべきであり、各変化点周辺のサンプル数は、変化の大きさに逆比例するべきであることを示している。
これに基づいて、トラック・アンド・ストップの単純で効率的な変種を考案し、多くの制度において漸近的に最適であることを証明した。
提案手法の効率性を示す合成環境において,実験結果を用いて理論的結果を支持する。
関連論文リスト
- Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up [29.55535031689754]
我々は,Scaffoldがステップサイズで高次項までのクライアント数の線形高速化を実現することを示す。
分析の結果,ScaffoldはFedAvgと同様,クライアント数の増加に伴って低下しない高次バイアスを保っていることがわかった。
論文 参考訳（メタデータ） (2025-03-10T17:56:19Z) - 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) - 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) - Inference for Change Points in High Dimensional Mean Shift Models [10.307668909650449]
本研究では,高次元平均シフトモデルにおいて,変化点の位置に対する信頼区間を構築することの問題点を考察する。
局所的に再適合した最小二乗推定器を開発し、基礎となる変化点の推定のコンポーネントワイドおよび同時レートを得る。
結果は高次元のスケーリングの下で確立され、変化点の数や指数以下の誤差が生じる。
論文 参考訳（メタデータ） (2021-07-19T20:56:15Z) - Instance-optimality in optimal value estimation: Adaptivity via
variance-reduced Q-learning [99.34907092347733]
本稿では,マルコフ決定過程における最適な$Q$値関数を離散状態と動作で推定する問題を解析する。
局所的なミニマックスフレームワークを用いて、この関数は任意の推定手順の精度の低い境界に現れることを示す。
他方,Q$ラーニングの分散還元版を解析することにより,状態と行動空間の対数的要因まで,下位境界のシャープさを確立する。
論文 参考訳（メタデータ） (2021-06-28T00:38:54Z) - Change Point Detection in Time Series Data using Autoencoders with a
Time-Invariant Representation [69.34035527763916]
変化点検出(CPD)は、時系列データにおける急激な特性変化を見つけることを目的としている。
近年のCDD法は、深層学習技術を用いる可能性を示したが、信号の自己相関統計学におけるより微妙な変化を識別する能力に欠けることが多い。
我々は、新しい損失関数を持つオートエンコーダに基づく手法を用い、使用済みオートエンコーダは、CDDに適した部分的な時間不変表現を学習する。
論文 参考訳（メタデータ） (2020-08-21T15:03:21Z) - Multinomial Sampling for Hierarchical Change-Point Detection [0.0]
本稿では,検出率を向上し,遅延を低減する多項サンプリング手法を提案する。
実験の結果, 基準法よりも優れた結果が得られ, また, 人間の行動研究を指向した事例も提示した。
論文 参考訳（メタデータ） (2020-07-24T09:18:17Z) - Making Affine Correspondences Work in Camera Geometry Computation [62.7633180470428]
局所的な特徴は、ポイント・ツー・ポイント対応ではなく、リージョン・ツー・リージョンを提供する。
本稿では,全モデル推定パイプラインにおいて,地域間マッチングを効果的に活用するためのガイドラインを提案する。
実験により、アフィンソルバはより高速な実行時にポイントベースソルバに匹敵する精度を達成できることが示された。
論文 参考訳（メタデータ） (2020-07-20T12:07:48Z) - Optimal Change-Point Detection with Training Sequences in the Large and
Moderate Deviations Regimes [72.68201611113673]
本稿では,情報理論の観点から,新しいオフライン変化点検出問題について検討する。
基礎となる事前および変更後分布の知識は分かっておらず、利用可能なトレーニングシーケンスからのみ学習できると仮定する。
論文 参考訳（メタデータ） (2020-03-13T23:39:40Z) - The Simulator: Understanding Adaptive Sampling in the
Moderate-Confidence Regime [52.38455827779212]
エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。
適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。
我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
論文 参考訳（メタデータ） (2017-02-16T23:42:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。