論文の概要: 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)$を実行する、ほぼ最適性能に近い新しいスケーラブルな近似アルゴリズムを導出する全く異なるアプローチを考える。
関連論文リスト
- High-Probability Convergence for Composite and Distributed Stochastic
Minimization and Variational Inequalities with Heavy-Tailed Noise [60.92108236919524]
グラデーション、クリッピングは、優れた高確率保証を導き出すアルゴリズムの鍵となる要素の1つである。
クリッピングは、合成および分散最適化の一般的な方法の収束を損なう可能性がある。
論文 参考訳(メタデータ) (2023-10-03T07:49:17Z) - Smoothing the Edges: A General Framework for Smooth Optimization in
Sparse Regularization using Hadamard Overparametrization [0.8029049649310213]
本稿では、()空間の正規化を$ell_q$ $ell_p,q$でスムーズに最適化するためのフレームワークを提案する。
ここでソリューションを見つけることは、オフザシェルフ()スパシティと互換性がある。
論文 参考訳(メタデータ) (2023-07-07T13:06:12Z) - Analyzing Inexact Hypergradients for Bilevel Learning [0.09669369645900441]
暗黙の関数定理と自動微分/バックプロパゲーションに基づいて既存の手法を一般化する過次計算のための統一的なフレームワークを提案する。
計算結果から,高次アルゴリズムの選択は低次解法の選択と同等に重要であることが明らかとなった。
論文 参考訳(メタデータ) (2023-01-11T23:54:27Z) - E-detectors: a nonparametric framework for sequential change detection [86.15115654324488]
逐次的変化検出のための基本的かつ汎用的なフレームワークを開発する。
私たちの手順は、平均走行距離のクリーンで無症状な境界が伴います。
統計的および計算効率の両方を達成するために,これらの混合物を設計する方法を示す。
論文 参考訳(メタデータ) (2022-03-07T17:25:02Z) - 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) - Practical Schemes for Finding Near-Stationary Points of Convex
Finite-Sums [45.91933657088324]
凸有限サムの近定常点探索におけるアルゴリズム手法の体系的研究を行う。
私たちの主な貢献は、いくつかのアルゴリズム的な発見です。
我々は,今後の発展を促進する新しいスキームのシンプルさと実用性を強調した。
論文 参考訳(メタデータ) (2021-05-25T16:46:35Z) - 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) - Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion
and Strong Solutions to Variational Inequalities [14.848525762485872]
非拡張写像、単調リプシッツ作用素、近位写像の間の接続を利用して、単調包含問題に対する準最適解を得る。
これらの結果は、変分不等式問題に対する強い解の近似、凸凸凹 min-max 最適化問題の近似、および min-max 最適化問題における勾配のノルムの最小化について、ほぼ最適に保証される。
論文 参考訳(メタデータ) (2020-02-20T17:12:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。