論文の概要: Optimal network online change point localisation
- arxiv url: http://arxiv.org/abs/2101.05477v1
- Date: Thu, 14 Jan 2021 07:24:39 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-29 00:43:34.785633
- Title: Optimal network online change point localisation
- Title（参考訳）: 最適ネットワークオンライン変化点局所化
- Authors: Yi Yu, Oscar Hernan Madrid Padilla, Daren Wang and Alessandro Rinaldo
- Abstract要約: オンラインネットワーク変化点検出の問題点について検討する。
この設定では、独立したベルヌーイネットワークの集合が順次収集され、基礎となる変化点が生じる。
目的は、虚偽のアラームの数または確率の制約に応じて、それが存在する場合、変更点をできるだけ早く検出することです。
- 参考スコア（独自算出の注目度）: 73.93301212629231
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of online network change point detection. In this
setting, a collection of independent Bernoulli networks is collected
sequentially, and the underlying distributions change when a change point
occurs. The goal is to detect the change point as quickly as possible, if it
exists, subject to a constraint on the number or probability of false alarms.
In this paper, on the detection delay, we establish a minimax lower bound and
two upper bounds based on NP-hard algorithms and polynomial-time algorithms,
i.e., \[ \mbox{detection delay} \begin{cases} \gtrsim \log(1/\alpha)
\frac{\max\{r^2/n, \, 1\}}{\kappa_0^2 n \rho},\\ \lesssim \log(\Delta/\alpha)
\frac{\max\{r^2/n, \, \log(r)\}}{\kappa_0^2 n \rho}, & \mbox{with NP-hard
algorithms},\\ \lesssim \log(\Delta/\alpha) \frac{r}{\kappa_0^2 n \rho}, &
\mbox{with polynomial-time algorithms}, \end{cases} \] where $\kappa_0, n,
\rho, r$ and $\alpha$ are the normalised jump size, network size, entrywise
sparsity, rank sparsity and the overall Type-I error upper bound. All the model
parameters are allowed to vary as $\Delta$, the location of the change point,
diverges. The polynomial-time algorithms are novel procedures that we propose
in this paper, designed for quick detection under two different forms of Type-I
error control. The first is based on controlling the overall probability of a
false alarm when there are no change points, and the second is based on
specifying a lower bound on the expected time of the first false alarm.
Extensive experiments show that, under different scenarios and the
aforementioned forms of Type-I error control, our proposed approaches
outperform state-of-the-art methods.
- Abstract（参考訳）: オンラインネットワーク変化点検出の問題点について検討する。
この設定では、独立したベルヌーイネットワークの集合を順次収集し、変更点が発生したときにその下層分布が変化する。
目標は、変更点をできるだけ早く検出することであり、もし存在すれば、偽アラームの数や可能性の制約を受ける。
In this paper, on the detection delay, we establish a minimax lower bound and two upper bounds based on NP-hard algorithms and polynomial-time algorithms, i.e., \[ \mbox{detection delay} \begin{cases} \gtrsim \log(1/\alpha) \frac{\max\{r^2/n, \, 1\}}{\kappa_0^2 n \rho},\\ \lesssim \log(\Delta/\alpha) \frac{\max\{r^2/n, \, \log(r)\}}{\kappa_0^2 n \rho}, & \mbox{with NP-hard algorithms},\\ \lesssim \log(\Delta/\alpha) \frac{r}{\kappa_0^2 n \rho}, & \mbox{with polynomial-time algorithms}, \end{cases} \] where $\kappa_0, n, \rho, r$ and $\alpha$ are the normalised jump size, network size, entrywise sparsity, rank sparsity and the overall Type-I error upper bound.
すべてのモデルパラメータは、変更点の位置である$\Delta$として変更することができる。
多項式時間アルゴリズムは,2種類のタイプi誤り制御を高速に検出するために設計した新しい手法である。
第1は、変更点がない場合の偽アラームの全体的な確率を制御し、第2は、第1の偽アラームの期待時刻の下限を特定することに基づく。
提案手法は,異なるシナリオと前述のType-Iエラー制御形態において,最先端の手法よりも優れていることを示す。
関連論文リスト
- Gradient Norm Regularization Second-Order Algorithms for Solving Nonconvex-Strongly Concave Minimax Problems [2.3721580767877257]
提案手法は,非強弱畳み込みミニマックス問題の解法である。
本稿では,提案アルゴリズムが$mathcalを達成することを示す。
スティロン
2階ノルムは上向きであることが証明されている。
tk
400ドルだ
400ドルだ
400ドルだ
400ドルだ
400ドルだ
400ドルだ
400ドルだ
400ドルだ
400ドルだ
400ドルだ
$k
論文 参考訳（メタデータ） (2024-11-24T09:46:36Z) - Finite-Time Error Bounds for Greedy-GQ [20.51105692499517]
We show that Greedy-GQ algorithm converges fast-time error。
我々の分析は、ステップサイズを選択するために、より高速な収束ステップサイズを提供する。
論文 参考訳（メタデータ） (2022-09-06T15:04:57Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳（メタデータ） (2022-06-16T17:10:57Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-02-23T02:39:04Z) - Inferring Hidden Structures in Random Graphs [13.031167737538881]
本研究では,ランダムなグラフ上に植えられた群集群集の検出と復元の2つの推論問題について検討する。
我々は、パラメータ $(n,k,q)$ や $Gamma_k$ の特定の性質の観点から、構造を検出・復元するための下限を導出し、これらの下限を達成するための計算学的に最適なアルゴリズムを示す。
論文 参考訳（メタデータ） (2021-10-05T09:39:51Z) - Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。
次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。
頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文 参考訳（メタデータ） (2021-07-22T14:25:16Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Optimal $\delta$-Correct Best-Arm Selection for Heavy-Tailed
Distributions [2.2940141855172036]
我々は、$delta$-correctアルゴリズムを用いて、最大平均値を持つものを識別する問題を考察する。
$delta$-correctアルゴリズムの下位境界はよく知られている。
我々は,下界の$delta$-correctアルゴリズムを提案し,$delta$を0に還元する。
論文 参考訳（メタデータ） (2019-08-24T05:31:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。