論文の概要: Quickest change detection with unknown parameters: Constant complexity
and near optimality
- arxiv url: http://arxiv.org/abs/2106.05061v1
- Date: Wed, 9 Jun 2021 13:29:26 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-10 15:21:57.931046
- Title: Quickest change detection with unknown parameters: Constant complexity
and near optimality
- Title（参考訳）: 未知パラメータによる最短変化検出:一定の複雑さとほぼ最適性
- Authors: Firas Jarboui, Viannet Perchet
- Abstract要約: 変化前分布と後分布の両方のパラメータが未知である場合、最も早い変化検出問題を考える。
我々は、より複雑なマルコフ設定に適応した$mathcalO(1)$で実行する、ほぼ最適な性能を持つスケーラブルな近似アルゴリズムを導出する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the quickest change detection problem where both the parameters
of pre- and post- change distributions are unknown, which prevents the use of
classical simple hypothesis testing. Without additional assumptions, optimal
solutions are not tractable as they rely on some minimax and robust variant of
the objective. As a consequence, change points might be detected too late for
practical applications (in economics, health care or maintenance for instance).
Available constant complexity techniques typically solve a relaxed version of
the problem, deeply relying on very specific probability distributions and/or
some very precise additional knowledge. We consider a totally different
approach that leverages the theoretical asymptotic properties of optimal
solutions to derive a new scalable approximate algorithm with near optimal
performance that runs~in~$\mathcal{O}(1)$, adapted to even more complex
Markovian settings.
- Abstract（参考訳）: 我々は,変更前の分布と変更後の分布のパラメータが不明な,最も早い変化検出問題を考える。
追加の仮定がなければ、最適な解は、目的のminimaxとロバストな変種に依存するため、扱いにくいものではない。
その結果、実用的な用途(経済学、医療、メンテナンスなど)には変更点が遅すぎる可能性がある。
利用可能な定数複雑性技法は一般に、非常に特定の確率分布と、あるいは非常に正確な追加知識に深く依存し、緩和された問題の解法である。
我々は、最適解の理論的漸近性を利用して、より複雑なマルコフ設定に適応した~in~$\mathcal{o}(1)$を実行する、ほぼ最適性能に近い新しいスケーラブルな近似アルゴリズムを導出する全く異なるアプローチを考える。
関連論文リスト
- Approximation Algorithms for Combinatorial Optimization with Predictions [3.7235228254732524]
従来のアルゴリズムの近似保証よりも高い精度で予測を行う。
我々のアルゴリズムは、完璧な予測が得られたときに最適解を生成する。
この種の問題全体に対して最適なアプローチを示すが、個々の問題の特定の構造的特性を利用して改善された境界を求める可能性はある。
論文 参考訳（メタデータ） (2024-11-25T17:31:34Z) - Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
機械学習の幅広い問題にまたがる正規化誤差フィードバックアルゴリズムに対する収束の最初の証明を提供する。
提案手法では,許容可能なステップサイズが大きくなったため,新しい正規化エラーフィードバックアルゴリズムは,各種タスクにおける非正規化エラーよりも優れていた。
論文 参考訳（メタデータ） (2024-10-22T10:19:27Z) - Distributed Fractional Bayesian Learning for Adaptive Optimization [7.16937736207894]
本稿では,各エージェントが共通パラメータを持つローカルコスト関数にのみアクセス可能な分散適応最適化問題について考察する。
分散最適化問題におけるパラメータの不確実性に対処し、同時に最適解を見つけるための貴重な洞察を提供することを目的としている。
論文 参考訳（メタデータ） (2024-04-17T13:09:33Z) - High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise [96.80184504268593]
グラデーション、クリッピングは、優れた高確率保証を導き出すアルゴリズムの鍵となる要素の1つである。
クリッピングは、合成および分散最適化の一般的な方法の収束を損なう可能性がある。
論文 参考訳（メタデータ） (2023-10-03T07:49:17Z) - Smoothing the Edges: Smooth Optimization for Sparse Regularization using Hadamard Overparametrization [10.009748368458409]
本稿では、(構造化された)空間性に対して、明示的に正規化された目的を円滑に最適化するためのフレームワークを提案する。
提案手法は,完全微分可能近似自由最適化を実現し,深層学習におけるユビキタス勾配降下パラダイムと互換性がある。
論文 参考訳（メタデータ） (2023-07-07T13:06:12Z) - Analyzing Inexact Hypergradients for Bilevel Learning [0.09669369645900441]
暗黙の関数定理と自動微分/バックプロパゲーションに基づいて既存の手法を一般化する過次計算のための統一的なフレームワークを提案する。
計算結果から,高次アルゴリズムの選択は低次解法の選択と同等に重要であることが明らかとなった。
論文 参考訳（メタデータ） (2023-01-11T23:54:27Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - Instance-optimality in optimal value estimation: Adaptivity via
variance-reduced Q-learning [99.34907092347733]
本稿では,マルコフ決定過程における最適な$Q$値関数を離散状態と動作で推定する問題を解析する。
局所的なミニマックスフレームワークを用いて、この関数は任意の推定手順の精度の低い境界に現れることを示す。
他方,Q$ラーニングの分散還元版を解析することにより,状態と行動空間の対数的要因まで,下位境界のシャープさを確立する。
論文 参考訳（メタデータ） (2021-06-28T00:38:54Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳（メタデータ） (2020-12-11T08:28:51Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。