Fugu-MT 論文翻訳(概要): Robust Estimation for Random Graphs

論文の概要: Robust Estimation for Random Graphs

arxiv url: http://arxiv.org/abs/2111.05320v1
Date: Tue, 9 Nov 2021 18:43:25 GMT
ステータス: 処理完了
システム内更新日: 2021-11-10 16:21:11.164419
Title: Robust Estimation for Random Graphs
Title（参考訳）: ランダムグラフのロバスト推定
Authors: Jayadev Acharya, Ayush Jain, Gautam Kamath, Ananda Theertha Suresh, Huanyu Zhang
Abstract要約: 我々は、$n$ノード上のErdHos-R'enyiランダムグラフのパラメータ$p$を頑健に推定する問題について検討する。情報理論の限界であるすべての$gamma 1/2$に対して、同様の精度で非効率なアルゴリズムを与える。
参考スコア（独自算出の注目度）: 47.07886511972046
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study the problem of robustly estimating the parameter $p$ of an Erd\H{o}s-R\'enyi random graph on $n$ nodes, where a $\gamma$ fraction of nodes may be adversarially corrupted. After showing the deficiencies of canonical estimators, we design a computationally-efficient spectral algorithm which estimates $p$ up to accuracy $\tilde O(\sqrt{p(1-p)}/n + \gamma\sqrt{p(1-p)} /\sqrt{n}+ \gamma/n)$ for $\gamma < 1/60$. Furthermore, we give an inefficient algorithm with similar accuracy for all $\gamma <1/2$, the information-theoretic limit. Finally, we prove a nearly-matching statistical lower bound, showing that the error of our algorithms is optimal up to logarithmic factors.
Abstract（参考訳）: 我々は、$n$ノード上のErd\H{o}s-R\'enyiランダムグラフのパラメータ$p$を頑健に推定する問題について検討する。標準推定器の欠陥を示した後、計算効率の良いスペクトルアルゴリズムを設計し、$\tilde O(\sqrt{p(1-p)}/n + \gamma\sqrt{p(1-p)} /\sqrt{n}+ \gamma/n)$ for $\gamma < 1/60$と見積もる。さらに、情報理論の限界である$\gamma <1/2$ に対して、同様の精度の非効率なアルゴリズムを与える。最後に,アルゴリズムの誤差が対数係数まで最適であることを示すため,ほぼ一致した統計的下界を証明した。

関連論文リスト

Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination [42.526664955704746]
本研究では,平均推定,PCA,線形回帰に着目したハマー汚染モデルにおけるスパース推定タスクについて検討する。それぞれのタスクに対して、最適なエラー保証を備えた最初のサンプルと計算効率の良い頑健な推定器を与える。技術レベルでは、スパース方式における新しい多次元フィルタリング法を開発し、他の応用を見出すことができる。
論文参考訳（メタデータ） (2024-03-15T15:51:27Z)
Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文参考訳（メタデータ） (2023-07-13T18:59:28Z)
Moments, Random Walks, and Limits for Spectrum Approximation [40.43008834125277]
我々は、ワッサーシュタイン1距離において精度$epsilon$に近似できない$[-1,1]$に分布が存在することを示す。正規化グラフ隣接行列のスペクトルに対する$epsilon$-accurate近似を一定の確率で計算することはできない。
論文参考訳（メタデータ） (2023-07-02T05:03:38Z)
Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
論文参考訳（メタデータ） (2023-04-17T10:38:08Z)
Tight Bounds for $\gamma$-Regret via the Decision-Estimation Coefficient [88.86699022151598]
任意の構造化バンディット問題に対する$gamma$-regretの統計的特徴を与える。この$gamma$-regretは、関数クラス$mathcalF$上の構造化バンディット問題に現れる。
論文参考訳（メタデータ） (2023-03-06T17:54:33Z)
Globally Optimal Algorithms for Fixed-Budget Best Arm Identification [16.500749121196986]
すべての可能なパラメータに対する大域的最適化の結果,最適速度を特徴付ける。遅延最適追跡(DOT)と呼ばれる概念的アルゴリズムを導入することで、この速度が実際に達成可能であることを示す。
論文参考訳（メタデータ） (2022-06-09T17:42:19Z)
Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文参考訳（メタデータ） (2022-06-07T16:49:54Z)
Structure Learning in Graphical Models from Indirect Observations [17.521712510832558]
本稿では、パラメータ法と非パラメトリック法の両方を用いて、Rp$における$p$次元ランダムベクトル$Xのグラフィカル構造を学習する。温和な条件下では、グラフ構造推定器が正しい構造を得ることができることを示す。
論文参考訳（メタデータ） (2022-05-06T19:24:44Z)
Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。 O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
論文参考訳（メタデータ） (2021-10-15T00:54:04Z)
A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
論文参考訳（メタデータ） (2020-06-02T16:38:36Z)

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