論文の概要: Optimistic search strategy: Change point detection for large-scale data via adaptive logarithmic queries

• arxiv url: http://arxiv.org/abs/2010.10194v2
• Date: Sat, 21 Nov 2020 23:50:55 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-05 06:45:36.696156
• Title: Optimistic search strategy: Change point detection for large-scale data via adaptive logarithmic queries
• Title（参考訳）: 最適探索戦略:適応対数クエリによる大規模データの点変化検出
• Authors: Solt Kov\'acs, Housen Li, Lorenz Haubner, Axel Munk, Peter B\"uhlmann
• Abstract要約: 変更点検出は、データセグメント化時の適合性の改善を記述したゲイン関数の最大値の探索として、しばしば定式化される。 我々は、ゲイン関数の特定の構造を利用した楽観的な探索戦略を$O(log T)$で提案する。
• 参考スコア（独自算出の注目度）: 1.3212010735248336
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: As a classical and ever reviving topic, change point detection is often formulated as a search for the maximum of a gain function describing improved fits when segmenting the data. Searching through all candidate split points on the grid for finding the best one requires $O(T)$ evaluations of the gain function for an interval with $T$ observations. If each evaluation is computationally demanding (e.g. in high-dimensional models), this can become infeasible. Instead, we propose optimistic search strategies with $O(\log T)$ evaluations exploiting specific structure of the gain function. Towards solid understanding of our strategies, we investigate in detail the classical univariate Gaussian change in mean setup. For some of our proposals we prove asymptotic minimax optimality for single and multiple change point scenarios. Our search strategies generalize far beyond the theoretically analyzed univariate setup. We illustrate, as an example, massive computational speedup in change point detection for high-dimensional Gaussian graphical models. More generally, we demonstrate empirically that our optimistic search methods lead to competitive estimation performance while heavily reducing run-time.
• Abstract（参考訳）: 古典的で復活するトピックとして、変更点検出は、データをセグメント化する際の適合性を改善するゲイン関数の最大値の探索として、しばしば定式化される。 最良点を見つけるためにグリッド上の全ての候補分割点を探索するには$O(T)$の利得関数の評価を$T$の観測で行う必要がある。 各評価が計算的に要求される場合(例えば、高次元モデル)、これは実現不可能になる。 代わりに、ゲイン関数の特定の構造を利用した$o(\log t)$評価による楽観的な探索戦略を提案する。 戦略のしっかりした理解に向けて, 古典的不定形ガウス的変化を, 平均設定で詳細に検討した。 いくつかの提案では、単一および複数変更点シナリオに対する漸近的最小限の最適性を証明する。 我々の探索戦略は理論的に解析された単変量設定を超えて一般化される。 例えば、高次元ガウス図形モデルにおける変化点検出における大規模な計算速度向上を示す。 より一般に、我々の楽観的な探索手法が、実行時間を大幅に削減しつつ、競争力のある推定性能をもたらすことを実証的に示す。

関連論文リスト

• Optimizing Posterior Samples for Bayesian Optimization via Rootfinding [2.94944680995069]
  我々は,グローバルなルートフィンディングに基づく後方サンプルの効率的な大域的最適化手法を提案する。 内ループ最適化と外ループ最適化の両方において顕著な改善が示された。 GP-TSのサンプル平均定式化も提案する。
  論文  参考訳（メタデータ） (2024-10-29T17:57:16Z)
• Gaussian Process Thompson Sampling via Rootfinding [2.94944680995069]
  トンプソンサンプリング(Thompson sample, TS)は、ベイズ決定における単純かつ効果的な政策である。 連続最適化では、目的関数の後方はしばしばガウス過程(GP)であり、サンプルパスは多数の局所最適値を持つ。 本稿では,勾配に基づくマルチスタートの開始点を慎重に選択するGP-TSの効率的なグローバル最適化手法を提案する。
  論文  参考訳（メタデータ） (2024-10-10T16:06:45Z)
• Planning and Learning with Adaptive Lookahead [74.39132848733847]
  ポリシーイテレーション(PI)アルゴリズムは、欲求の一段階の改善と政策評価を交互に行う。 近年の文献では、複数段階のルックアヘッドポリシーの改善が、イテレーション毎の複雑さの増加を犠牲にして、よりコンバージェンス率の向上につながることが示されている。 本研究では,多段階の地平線を状態と推定値の関数として動的に適応する手法を初めて提案する。
  論文  参考訳（メタデータ） (2022-01-28T20:26:55Z)
• Local policy search with Bayesian optimization [73.0364959221845]
  強化学習は、環境との相互作用によって最適な政策を見つけることを目的としている。 局所探索のための政策勾配は、しばしばランダムな摂動から得られる。 目的関数の確率モデルとその勾配を用いたアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-06-22T16:07:02Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。 本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。 これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
  論文  参考訳（メタデータ） (2021-04-19T17:22:11Z)
• Using Distance Correlation for Efficient Bayesian Optimization [0.0]
  本論文では,$textsfGP-DC$というベイズ最適化手法を提案する。 探索と搾取を自動的にバランスさせ、手動のパラメータチューニングを必要としない。 ベンチマーク関数で$textsfgp-dc$を評価し、最先端メソッドよりも優れています。
  論文  参考訳（メタデータ） (2021-02-17T19:37:35Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。 標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
  論文  参考訳（メタデータ） (2020-06-24T06:01:24Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• Stochastic Proximal Gradient Algorithm with Minibatches. Application to Large Scale Learning Models [2.384873896423002]
  非滑らかな成分を持つ汎用合成対象関数に対する勾配アルゴリズムのミニバッチ変種を開発し解析する。 我々は、最小バッチサイズ$N$に対して、$mathcalO(frac1Nepsilon)$$epsilon-$subityが最適解に期待される二次距離で達成されるような、定数および変数のステップサイズ反復ポリシーの複雑さを提供する。
  論文  参考訳（メタデータ） (2020-03-30T10:43:56Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。