論文の概要: Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials
- arxiv url: http://arxiv.org/abs/2308.15728v4
- Date: Mon, 12 Aug 2024 23:05:48 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-14 23:24:38.612615
- Title: Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials
- Title（参考訳）: 低次多項式によるグラフオン推定のための計算下界
- Authors: Yuetian Luo, Chao Gao,
- Abstract要約: 低次推定器の場合、その推定誤差はUSVTの推定値よりもかなり良くないことを示す。
この結果は、Schramm と Wein (2022) による近年の低次展開に基づいて証明され、一般グラフトン推定問題に適用する際のいくつかの重要な課題を克服する。
- 参考スコア（独自算出の注目度）: 14.908056172167052
- 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 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 universal singular value thresholding, but it can only achieve a much slower estimation error rate than the minimax one. 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 provide rigorous evidence for the computational barrier in graphon estimation via low-degree polynomials. Specifically, in SBM 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 and in nonparametric graphon estimation, we show low-degree polynomial estimators achieve estimation error rates strictly slower than the minimax rate. 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. Finally, we extend our computational lower bounds to sparse graphon estimation and biclustering.
- Abstract（参考訳）: グラフオン推定は、ネットワーク分析における最も基本的な問題の一つであり、過去10年間にかなりの注目を集めてきた。
統計的観点からは、確率ブロックモデルと非パラメトリックグラフトン推定の両方について、Gao et al (2015) により、グラノン推定の最小誤差速度が確立されている。
統計的最適推定子は制約された最小二乗に基づいており、次元において計算複雑性が指数関数的である。
計算の観点からは、最もよく知られた多項式時間推定器は普遍特異値しきい値のしきい値に基づいているが、最小値よりもはるかに遅い推定誤差率しか達成できない。
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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。