論文の概要: Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions

• arxiv url: http://arxiv.org/abs/2305.10227v1
• Date: Wed, 17 May 2023 14:03:47 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-18 15:39:57.185012
• Title: Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions
• Title（参考訳）: ノード破壊下の確率ブロックモデルにおけるケステン・スティグアム閾値に達する
• Authors: Jingqiu Ding, Tommaso d'Orsi, Yiding Hua, David Steurer
• Abstract要約: 本研究では,ノード故障を考慮したブロックモデルを用いて,ロバストなコミュニティ検出について検討する。 本稿では,ケステン・スティグムしきい値の弱い回復を実現するアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 7.512896457568841
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study robust community detection in the context of node-corrupted stochastic block model, where an adversary can arbitrarily modify all the edges incident to a fraction of the $n$ vertices. We present the first polynomial-time algorithm that achieves weak recovery at the Kesten-Stigum threshold even in the presence of a small constant fraction of corrupted nodes. Prior to this work, even state-of-the-art robust algorithms were known to break under such node corruption adversaries, when close to the Kesten-Stigum threshold. We further extend our techniques to the $Z_2$ synchronization problem, where our algorithm reaches the optimal recovery threshold in the presence of similar strong adversarial perturbations. The key ingredient of our algorithm is a novel identifiability proof that leverages the push-out effect of the Grothendieck norm of principal submatrices.
• Abstract（参考訳）: 我々は,ノード分割確率ブロックモデルの文脈において,すべてのエッジインシデントをn$頂点のごく一部に任意に修正できるロバストなコミュニティ検出法について検討した。 本稿では,ケステン・スティグラムしきい値において,破壊ノードの定数が小さい場合においても弱回復を実現する最初の多項式時間アルゴリズムを提案する。 この研究の前には、最先端のロバストアルゴリズムでさえ、ケステン・スティグムしきい値に近づくと、そのようなノード破壊の敵に破られることが知られていた。 さらに,本手法を$z_2$同期問題にまで拡張し,類似の強い逆摂動が存在する場合に最適回復しきい値に達する。 本アルゴリズムの重要な要素は,主行列のGrothendieckノルムの押し出し効果を利用した新しい識別可能性証明である。

関連論文リスト

• Robust Q-Learning under Corrupted Rewards [2.07180164747172]
  本稿では,Q-Learningアルゴリズムの強汚染攻撃モデルに対する堅牢性について検討する。 本研究では,実演的ベルマン演算子を構築するために,履歴報酬データを用いた新しい頑健な同期Q-ラーニングアルゴリズムを開発した。 我々の結果は、真の報酬分布が無限に支持されたとしても、有界な第2モーメントを許容するならば、維持され続ける。
  論文  参考訳（メタデータ） (2024-09-05T04:37:02Z)
• Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processes [59.61248760134937]
  本稿では,$tildeO(sqrtT+zeta)$を後悔するアルゴリズムを提案する。 提案アルゴリズムは、最近開発された線形文脈帯域からの不確実性重み付き最小二乗回帰に依存する。 本稿では,提案アルゴリズムをエピソディックなMDP設定に一般化し,まず汚職レベル$zeta$への付加的依存を実現する。
  論文  参考訳（メタデータ） (2022-12-12T15:04:56Z)
• A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Bandits [118.22458816174144]
  そこで本稿では,エポックで動作するロバストな除去型アルゴリズムを提案し,探索と頻繁な切替を併用して,小さなアクションサブセットを選択し,各アクションを複数タイミングで実行する。 我々のアルゴリズムであるGP Robust Phased Elimination (RGP-PE) は、探索とエクスプロイトによる汚職に対するロバストネスのバランスに成功している。 GPバンディット設定におけるロバスト性の最初の実証的研究を行い,アルゴリズムが様々な敵攻撃に対してロバストであることを示す。
  論文  参考訳（メタデータ） (2022-02-03T21:19:36Z)
• Robust recovery for stochastic block models [16.74630355427558]
  ブロックモデルのロバストバージョンにおいて、弱い回復のための効率的なアルゴリズムを開発する。 その結果,ブロックモデルにロバストさの代償はないことがわかった。
  論文  参考訳（メタデータ） (2021-11-16T15:43:00Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• On Optimal Robustness to Adversarial Corruption in Online Decision Problems [27.68461396741871]
  最適ロバスト性は汚損量に対する平方根依存性によって表現できることを示す。 多武装バンディット問題に対しては、対数係数までほぼ狭い下界も提供する。
  論文  参考訳（メタデータ） (2021-09-22T18:26:45Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  敵対的レジリエントな分散最適化。 機械は独立して勾配を計算し 協力することができます 私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。 それは非常に実用的です:それはないときすべての前の方法の性能を改善します。 セッティングマシンがあります。
  論文  参考訳（メタデータ） (2020-12-28T17:19:32Z)
• Sparse PCA: Algorithms, Adversarial Perturbations and Certificates [9.348107805982604]
  標準統計モデルにおけるスパースPCAの効率的なアルゴリズムについて検討する。 私たちのゴールは、小さな摂動に耐性を持ちながら、最適な回復保証を達成することです。
  論文  参考訳（メタデータ） (2020-11-12T18:58:51Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。 本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
  論文  参考訳（メタデータ） (2020-08-20T03:48:14Z)
• Corruption-Tolerant Gaussian Process Bandit Optimization [130.60115798580136]
  未知(典型的には非生成)関数を有界ノルムで最適化する問題を考察する。 我々は「高速だが非ローバスト」と「スロー」に基づく高速スローGP-UCBに基づくアルゴリズムを提案する。 ある種の依存関係は、汚職レベルによっては要求できない、と我々は主張する。
  論文  参考訳（メタデータ） (2020-03-04T09:46:58Z)

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

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