論文の概要: Robust recovery for stochastic block models
- arxiv url: http://arxiv.org/abs/2111.08568v1
- Date: Tue, 16 Nov 2021 15:43:00 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-17 14:09:08.119968
- Title: Robust recovery for stochastic block models
- Title（参考訳）: 確率ブロックモデルに対するロバスト回復
- Authors: Jingqiu Ding, Tommaso d'Orsi, Rajai Nasser, David Steurer
- Abstract要約: ブロックモデルのロバストバージョンにおいて、弱い回復のための効率的なアルゴリズムを開発する。
その結果,ブロックモデルにロバストさの代償はないことがわかった。
- 参考スコア（独自算出の注目度）: 16.74630355427558
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We develop an efficient algorithm for weak recovery in a robust version of
the stochastic block model. The algorithm matches the statistical guarantees of
the best known algorithms for the vanilla version of the stochastic block
model. In this sense, our results show that there is no price of robustness in
the stochastic block model. Our work is heavily inspired by recent work of
Banks, Mohanty, and Raghavendra (SODA 2021) that provided an efficient
algorithm for the corresponding distinguishing problem. Our algorithm and its
analysis significantly depart from previous ones for robust recovery. A key
challenge is the peculiar optimization landscape underlying our algorithm: The
planted partition may be far from optimal in the sense that completely
unrelated solutions could achieve the same objective value. This phenomenon is
related to the push-out effect at the BBP phase transition for PCA. To the best
of our knowledge, our algorithm is the first to achieve robust recovery in the
presence of such a push-out effect in a non-asymptotic setting. Our algorithm
is an instantiation of a framework based on convex optimization (related to but
distinct from sum-of-squares), which may be useful for other robust matrix
estimation problems. A by-product of our analysis is a general technique that
boosts the probability of success (over the randomness of the input) of an
arbitrary robust weak-recovery algorithm from constant (or slowly vanishing)
probability to exponentially high probability.
- Abstract（参考訳）: 確率ブロックモデルのロバストなバージョンにおける弱い回復のための効率的なアルゴリズムを開発する。
このアルゴリズムは確率ブロックモデルのバニラバージョンに対する最もよく知られたアルゴリズムの統計的保証と一致する。
この意味では、確率ブロックモデルにロバスト性の価格がないことを示している。
我々の研究は、銀行、mohanty、raghavendra(soda 2021)の最近の研究に強く触発され、対応する識別問題の効率的なアルゴリズムを提供した。
我々のアルゴリズムとその解析は、ロバストな回復のために以前のものから大きく離れている。
植えられた分割は、完全に無関係な解が同じ目的の値を達成することができるという意味では、最適とはほど遠いかもしれない。
この現象は、PCAのBBP相転移におけるプッシュアウト効果と関連している。
私たちの知る限りでは、このアルゴリズムは非漸近的な環境でこのようなプッシュアウト効果の存在下でロバストな回復を達成する最初の方法です。
我々のアルゴリズムは凸最適化に基づくフレームワークのインスタンス化であり、他の頑健な行列推定問題に有用かもしれない。
我々の分析の副産物は、任意の頑健な弱回復アルゴリズムの成功確率(入力のランダム性よりも)を一定(あるいは徐々に消える)確率から指数関数的に高い確率に上げる一般的な手法である。
関連論文リスト
- Rigorous Probabilistic Guarantees for Robust Counterfactual Explanations [80.86128012438834]
モデルシフトに対する反ファクトの堅牢性を計算することはNP完全であることを示す。
本稿では,頑健性の厳密な推定を高い保証で実現する新しい確率論的手法を提案する。
論文 参考訳（メタデータ） (2024-07-10T09:13:11Z) - Semi-Bandit Learning for Monotone Stochastic Optimization [20.776114616154242]
モノトーン」問題のクラスに対して汎用的なオンライン学習アルゴリズムを提供する。
我々のフレームワークは、預言者、Pandoraのボックスナップサック、不等式マッチング、部分モジュラー最適化など、いくつかの基本的な最適化問題に適用できる。
論文 参考訳（メタデータ） (2023-12-24T07:46:37Z) - A Novel Framework for Improving the Breakdown Point of Robust Regression
Algorithms [1.9594639581421422]
本稿では,頑健な回帰アルゴリズムの分解点を改善するための効果的なフレームワークを提案する。
反復局所探索(CORALS)を用いた一貫した頑健な回帰アルゴリズムを導出する。
論文 参考訳（メタデータ） (2023-05-20T15:59:33Z) - Exploring the Algorithm-Dependent Generalization of AUPRC Optimization
with List Stability [107.65337427333064]
AUPRC(Area Under the Precision-Recall Curve)の最適化は、機械学習にとって重要な問題である。
本研究では, AUPRC最適化の単依存一般化における最初の試行について述べる。
3つの画像検索データセットの実験は、我々のフレームワークの有効性と健全性に言及する。
論文 参考訳（メタデータ） (2022-09-27T09:06:37Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - Towards Feature-Based Performance Regression Using Trajectory Data [0.9281671380673306]
ブラックボックス最適化は非常に活発な研究領域であり、毎年多くの新しいアルゴリズムが開発されている。
アルゴリズムの多様性はメタプロブレム(メタプロブレム):どのアルゴリズムが与えられた問題を選択するか?
過去の研究では、探索ランドスケープ分析に基づくインスタンスごとのアルゴリズム選択が、このメタプロブレムに取り組むための効率的な手段であることが示されている。
論文 参考訳（メタデータ） (2021-02-10T10:19:13Z) - Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
敵対的レジリエントな分散最適化。
機械は独立して勾配を計算し 協力することができます
私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。
それは非常に実用的です:それはないときすべての前の方法の性能を改善します。
セッティングマシンがあります。
論文 参考訳（メタデータ） (2020-12-28T17:19:32Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Kidney Exchange with Inhomogeneous Edge Existence Uncertainty [33.17472228570093]
我々は一致したサイクルとチェーンパッキングの問題の最大化を目指しており、そこでは障害の端まで有向グラフ内の構造を識別することを目的としている。
ユナイテッド・フォー・シェアリング(SUNO)のデータに対する我々のアプローチは、SAAベースの手法と同じ重み付けでより良いパフォーマンスを提供する。
論文 参考訳（メタデータ） (2020-07-07T04:08:39Z) - Active Model Estimation in Markov Decision Processes [108.46146218973189]
マルコフ決定過程(MDP)をモデル化した環境の正確なモデル学習のための効率的な探索の課題について検討する。
マルコフに基づくアルゴリズムは,本アルゴリズムと極大エントロピーアルゴリズムの両方を小サンプル方式で上回っていることを示す。
論文 参考訳（メタデータ） (2020-03-06T16:17:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。