論文の概要: Computational Lower Bounds for Graphon Estimation via Low-degree
Polynomials
- arxiv url: http://arxiv.org/abs/2308.15728v2
- Date: Wed, 27 Sep 2023 18:58:43 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-29 19:59:30.997621
- 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におけるコミュニティ検出におけるクラスタリング誤差の計算的下限も提供し,コミュニティの効率的な回復のためのケステン・スティグムしきい値の新たな証拠を得た。
関連論文リスト
- Kernel-based off-policy estimation without overlap: Instance optimality
beyond semiparametric efficiency [53.90687548731265]
本研究では,観測データに基づいて線形関数を推定するための最適手順について検討する。
任意の凸および対称函数クラス $mathcalF$ に対して、平均二乗誤差で有界な非漸近局所ミニマックスを導出する。
論文 参考訳（メタデータ） (2023-01-16T02:57:37Z) - Variance estimation in graphs with the fused lasso [7.732474038706013]
一般グラフの分散を連続的に推定できる相補的ケースに対する線形時間推定器を開発する。
我々の推定器は,平均信号が標準スケーリングと全く異なる場合,チェーンと2次元グリッドグラフの最小値が得られることを示す。
論文 参考訳（メタデータ） (2022-07-26T03:50:51Z) - Optimal Estimation and Computational Limit of Low-rank Gaussian Mixtures [12.868722327487752]
本稿では,各行列値の観測値に低ランク構造が植え付けられていることを前提として,低ランクガウス混合モデル(LrMM)を提案する。
一般に計算不可能な最大極大推定器の最小極大最適性を証明する。
以上の結果から,ミニマックス誤差率と統計的-計算的ギャップの相転移が明らかとなった。
論文 参考訳（メタデータ） (2022-01-22T12:43:25Z) - Learning to Estimate Without Bias [57.82628598276623]
ガウスの定理は、重み付き最小二乗推定器は線形モデルにおける線形最小分散アンバイアスド推定(MVUE)であると述べている。
本稿では、バイアス制約のあるディープラーニングを用いて、この結果を非線形設定に拡張する第一歩を踏み出す。
BCEの第二の動機は、同じ未知の複数の推定値が平均化されてパフォーマンスが向上するアプリケーションにおいてである。
論文 参考訳（メタデータ） (2021-10-24T10:23:51Z) - Non asymptotic estimation lower bounds for LTI state space models with
Cram\'er-Rao and van Trees [1.14219428942199]
本研究では,未知の共分散のガウス励起を持つ線形時間不変(LTI)状態空間モデルに対する推定問題について検討する。
予測される推定誤差と最小二乗推定器の平均二乗推定リスクに対して非下界を与える。
その結果, 推定リスクを期待して, 既存の下限を下限に拡張し, 改善した。
論文 参考訳（メタデータ） (2021-09-17T15:00:25Z) - Robust W-GAN-Based Estimation Under Wasserstein Contamination [8.87135311567798]
Wasserstein汚染モデルに基づくいくつかの推定問題について検討し,生成ネットワーク(GAN)を動機とする計算可能なトラクタブル推定器を提案する。
具体的には,逆位置推定,共分散行列推定,線形回帰のためのwasserstein ganに基づく推定器の特性を分析する。
提案する推定器は,多くのシナリオにおいて最小限最適である。
論文 参考訳（メタデータ） (2021-01-20T05:15:16Z) - Rao-Blackwellizing the Straight-Through Gumbel-Softmax Gradient
Estimator [93.05919133288161]
一般的なGumbel-Softmax推定器のストレートスルー変量の分散は、ラオ・ブラックウェル化により減少できることを示す。
これは平均二乗誤差を確実に減少させる。
これは分散の低減、収束の高速化、および2つの教師なし潜在変数モデルの性能向上につながることを実証的に実証した。
論文 参考訳（メタデータ） (2020-10-09T22:54:38Z) - Learning Minimax Estimators via Online Learning [55.92459567732491]
確率分布のパラメータを推定するミニマックス推定器を設計する際の問題点を考察する。
混合ケースナッシュ平衡を求めるアルゴリズムを構築した。
論文 参考訳（メタデータ） (2020-06-19T22:49:42Z) - Instability, Computational Efficiency and Statistical Accuracy [101.32305022521024]
我々は,人口レベルでのアルゴリズムの決定論的収束率と,$n$サンプルに基づく経験的対象に適用した場合の(不安定性)の間の相互作用に基づいて,統計的精度を得るフレームワークを開発する。
本稿では,ガウス混合推定,非線形回帰モデル,情報的非応答モデルなど,いくつかの具体的なモデルに対する一般結果の応用について述べる。
論文 参考訳（メタデータ） (2020-05-22T22:30:52Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。