論文の概要: Computational Lower Bounds for Graphon Estimation via Low-degree
Polynomials
- arxiv url: http://arxiv.org/abs/2308.15728v1
- Date: Wed, 30 Aug 2023 03:11:42 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-31 14:51:58.581987
- Title: Computational Lower Bounds for Graphon Estimation via Low-degree
Polynomials
- Title(参考訳): 低次多項式によるグラフェン推定のための計算下限
- Authors: Yuetian Luo and Chao Gao
- Abstract要約: 低次推定器の場合、その推定誤差は幅広いパラメータの下でUSVTの推定値よりも著しく優れていることが示される。
また,コミュニティ数の増加に伴い,SBMにおけるコミュニティ検出誤差の計算下限も提供する。
- 参考スコア(独自算出の注目度): 17.611893473432133
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Graphon estimation has been one of the most fundamental problems in network
analysis and has received considerable attention in the past decade. From the
statistical perspective, the minimax error rate of graphon estimation has been
established by Gao et al (2015) for both stochastic block model (SBM) and
nonparametric graphon estimation. The statistical optimal estimators are based
on constrained least squares and have computational complexity exponential in
the dimension. From the computational perspective, the best-known
polynomial-time estimator is based on universal singular value thresholding
(USVT), but it can only achieve a much slower estimation error rate than the
minimax one. It is natural to wonder if such a gap is essential. The
computational optimality of the USVT or the existence of a computational
barrier in graphon estimation has been a long-standing open problem. In this
work, we take the first step towards it and provide rigorous evidence for the
computational barrier in graphon estimation via low-degree polynomials.
Specifically, in both SBM and nonparametric graphon estimation, we show that
for low-degree polynomial estimators, their estimation error rates cannot be
significantly better than that of the USVT under a wide range of parameter
regimes. Our results are proved based on the recent development of low-degree
polynomials by Schramm and Wein (2022), while we overcome a few key challenges
in applying it to the general graphon estimation problem. By leveraging our
main results, we also provide a computational lower bound on the clustering
error for community detection in SBM with a growing number of communities and
this yields a new piece of evidence for the conjectured Kesten-Stigum threshold
for efficient community recovery.
- Abstract(参考訳): グラフオン推定はネットワーク解析における最も基本的な問題の一つであり、過去10年間にかなりの注目を集めてきた。
統計的観点からは、gao et al (2015) によって確率的ブロックモデル(sbm)と非パラメトリックなグラフェン推定の両方において、グラフェン推定の最小誤差率は確立されている。
統計的最適推定子は制約された最小二乗に基づいており、次元において計算複雑性が指数関数的である。
計算の観点からは、多項式時間推定器は普遍特異値しきい値(USVT)に基づいているが、最小値よりもはるかに遅い推定誤差率しか達成できない。
そのようなギャップが不可欠かどうか疑問に思うのは当然だ。
USVTの計算最適性や、グラノン推定における計算障壁の存在は、長年の未解決問題であった。
本研究では,その第一歩を踏み出し,低次多項式によるグラフェン推定における計算障壁の厳密な証拠を提供する。
特に, sbm および非パラメトリックグラフェン推定では, 低次多項式推定器では, その推定誤差率は, 広範囲のパラメータレジームの下では usvt のそれよりも著しく改善できないことが示されている。
我々の結果は、Schramm と Wein (2022) による最近の低次多項式の発展に基づいて証明されている。
また,本研究の主な成果を生かして,SBMにおけるコミュニティ検出におけるクラスタリング誤差の計算的下限も提供し,コミュニティの効率的な回復のためのケステン・スティグムしきい値の新たな証拠を得た。
関連論文リスト
- Efficient Graph Laplacian Estimation by Proximal Newton [12.05527862797306]
グラフ学習問題は、精度行列の最大極大推定(MLE)として定式化することができる。
いくつかのアルゴリズム的特徴を利用した効率的な解法を得るための2次手法を開発した。
論文 参考訳(メタデータ) (2023-02-13T15:13:22Z) - Kernel-based off-policy estimation without overlap: Instance optimality
beyond semiparametric efficiency [53.90687548731265]
本研究では,観測データに基づいて線形関数を推定するための最適手順について検討する。
任意の凸および対称函数クラス $mathcalF$ に対して、平均二乗誤差で有界な非漸近局所ミニマックスを導出する。
論文 参考訳(メタデータ) (2023-01-16T02:57:37Z) - Semi-Supervised Clustering of Sparse Graphs: Crossing the
Information-Theoretic Threshold [3.6052935394000234]
ブロックモデルは、ネットワーク構造データのクラスタリングとコミュニティ検出のための標準ランダムグラフモデルである。
ネットワークトポロジに基づく推定器は、モデルパラメータが一定の閾値以下である場合、スパースグラフの確率よりも大幅に向上する。
パラメータ領域全体でラベルの任意の部分で実現可能であることを示す。
論文 参考訳(メタデータ) (2022-05-24T00:03:25Z) - Learning to Estimate Without Bias [57.82628598276623]
ガウスの定理は、重み付き最小二乗推定器は線形モデルにおける線形最小分散アンバイアスド推定(MVUE)であると述べている。
本稿では、バイアス制約のあるディープラーニングを用いて、この結果を非線形設定に拡張する第一歩を踏み出す。
BCEの第二の動機は、同じ未知の複数の推定値が平均化されてパフォーマンスが向上するアプリケーションにおいてである。
論文 参考訳(メタデータ) (2021-10-24T10:23:51Z) - Statistical and computational thresholds for the planted $k$-densest
sub-hypergraph problem [13.808053718325635]
我々は,$d$-uniform ハイパーグラフ上に$k$-densest サブハイパーグラフを植え付けることで回復する問題を考察する。
この根本的な問題は、例えば、コミュニティの検出、平均ケースの複雑さ、神経科学の応用など、様々な文脈に現れる。
論文 参考訳(メタデータ) (2020-11-23T16:02:12Z) - Rao-Blackwellizing the Straight-Through Gumbel-Softmax Gradient
Estimator [93.05919133288161]
一般的なGumbel-Softmax推定器のストレートスルー変量の分散は、ラオ・ブラックウェル化により減少できることを示す。
これは平均二乗誤差を確実に減少させる。
これは分散の低減、収束の高速化、および2つの教師なし潜在変数モデルの性能向上につながることを実証的に実証した。
論文 参考訳(メタデータ) (2020-10-09T22:54:38Z) - Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
本研究では,隠れ構造物の存在を検知する作業において,低次構造物のパワーについて検討する。
大規模な「信号+雑音」問題に対して、任意の程度に達成可能な最良の平均二乗誤差に対して、ユーザフレンドリな下界を与える。
応用として,植込みサブマトリクスに対する低次平均2乗誤差の厳密な評価と高密度サブグラフ問題について述べる。
論文 参考訳(メタデータ) (2020-08-05T17:52:10Z) - One-Bit Compressed Sensing via One-Shot Hard Thresholding [7.594050968868919]
1ビット圧縮センシングの問題は、いくつかのバイナリ測定からスパース信号を推定することである。
広範に使われている非制約の幅の概念から遠ざかる、斬新で簡潔な分析法を提案する。
論文 参考訳(メタデータ) (2020-07-07T17:28:03Z) - Learning Minimax Estimators via Online Learning [55.92459567732491]
確率分布のパラメータを推定するミニマックス推定器を設計する際の問題点を考察する。
混合ケースナッシュ平衡を求めるアルゴリズムを構築した。
論文 参考訳(メタデータ) (2020-06-19T22:49:42Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳(メタデータ) (2020-05-21T17:51:30Z) - An Optimal Statistical and Computational Framework for Generalized
Tensor Estimation [10.899518267165666]
本稿では,低ランクテンソル推定問題に対するフレキシブルなフレームワークについて述べる。
計算画像、ゲノミクス、ネットワーク解析の応用から多くの重要な例を含む。
論文 参考訳(メタデータ) (2020-02-26T01:54:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。