論文の概要: Computational Barriers to Estimation from Low-Degree Polynomials
- arxiv url: http://arxiv.org/abs/2008.02269v2
- Date: Sat, 18 Jun 2022 23:30:54 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-02 18:47:05.609349
- Title: Computational Barriers to Estimation from Low-Degree Polynomials
- Title（参考訳）: 低次多項式による計算障壁の推定
- Authors: Tselil Schramm and Alexander S. Wein
- Abstract要約: 本研究では,隠れ構造物の存在を検知する作業において,低次構造物のパワーについて検討する。
大規模な「信号+雑音」問題に対して、任意の程度に達成可能な最良の平均二乗誤差に対して、ユーザフレンドリな下界を与える。
応用として,植込みサブマトリクスに対する低次平均2乗誤差の厳密な評価と高密度サブグラフ問題について述べる。
- 参考スコア（独自算出の注目度）: 81.67886161671379
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: One fundamental goal of high-dimensional statistics is to detect or recover
planted structure (such as a low-rank matrix) hidden in noisy data. A growing
body of work studies low-degree polynomials as a restricted model of
computation for such problems: it has been demonstrated in various settings
that low-degree polynomials of the data can match the statistical performance
of the best known polynomial-time algorithms. Prior work has studied the power
of low-degree polynomials for the task of detecting the presence of hidden
structures. In this work, we extend these methods to address problems of
estimation and recovery (instead of detection). For a large class of "signal
plus noise" problems, we give a user-friendly lower bound for the best possible
mean squared error achievable by any degree-D polynomial. To our knowledge,
these are the first results to establish low-degree hardness of recovery
problems for which the associated detection problem is easy. As applications,
we give a tight characterization of the low-degree minimum mean squared error
for the planted submatrix and planted dense subgraph problems, resolving (in
the low-degree framework) open problems about the computational complexity of
recovery in both cases.
- Abstract（参考訳）: 高次元統計の基本的な目標は、ノイズデータに隠された植木構造(低ランク行列など)を検知または回収することである。
このような問題に対する計算の制限モデルとして低次多項式を研究し、データの低次多項式が最もよく知られた多項式時間アルゴリズムの統計的性能と一致することが様々な環境で実証されている。
先行研究は隠れ構造の存在を検出するタスクのために低次多項式のパワーを研究した。
本研究では,これらの手法を拡張して,推定とリカバリの問題(検出に代えて)に対処する。
大規模な「信号+雑音」問題に対して、任意の次数D多項式で達成可能な最良の平均二乗誤差に対して、ユーザフレンドリな下界を与える。
我々の知る限り、これらは、関連する検出が容易な回復問題の低次硬度化を最初に達成した結果である。
応用として,植込みサブマトリクスの低次平均二乗誤差と高密度サブグラフ問題を厳密に評価し,両ケースにおける回復の計算複雑性に関する問題を解き放つ(低次フレームワークにおける)。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement
Learning [53.445068584013896]
低ランク構造を持つ強化学習(RL)における行列推定問題について検討した。
低ランク帯では、回収される行列は期待される腕の報酬を指定し、低ランクマルコフ決定プロセス(MDP)では、例えばMDPの遷移カーネルを特徴付ける。
簡単なスペクトルベースの行列推定手法は,行列の特異部分空間を効率よく復元し,ほぼ最小の入力誤差を示すことを示す。
論文 参考訳（メタデータ） (2023-10-10T17:06:41Z) - Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
低ランクマルコフ決定プロセスは、関数近似を持つRLに対して単純だが表現力のあるフレームワークを提供する。
既存のアルゴリズムは、(1)計算的に抽出可能であるか、または(2)制限的な統計的仮定に依存している。
提案手法は,低ランクMPPの探索のための最初の実証可能なサンプル効率アルゴリズムである。
論文 参考訳（メタデータ） (2023-07-08T15:41:48Z) - Sparse resultant based minimal solvers in computer vision and their
connection with the action matrix [17.31412310131552]
いくつかのカメラ幾何問題に対して、我々の余剰手法は、最先端のGrobnerベースベースの解法よりも小さく、より安定な解法をもたらすことを示した。
コンピュータビジョンにおける最小限の問題に対して、一般的なベースベースの方法に代わる競争力のある代替手段を提供する。
論文 参考訳（メタデータ） (2023-01-16T14:25:19Z) - Causal discovery under a confounder blanket [9.196779204457059]
観測データから因果関係を推定することは容易ではないが、高次元では特に難しい。
これらの仮定を緩和し、より重要な問題、すなわち有向非巡回部分グラフの回復に焦点を当てる。
これらの条件下で因果関係を同定し、テスト手順を実装するための完全なアルゴリズムを導出する。
論文 参考訳（メタデータ） (2022-05-11T18:10:45Z) - Minimax rate of consistency for linear models with missing values [0.0]
多くの実世界のデータセットでは、複数のソースが集約され、本質的に欠落した情報(センサーの故障、調査における未回答の疑問...)が欠落する。
本稿では,広範に研究された線形モデルに焦点をあてるが,不足する値が存在する場合には,非常に難しい課題であることが判明した。
最終的には、多くの学習タスクを解決し、入力機能の数を指数関数的にすることで、現在の現実世界のデータセットでは予測が不可能になる。
論文 参考訳（メタデータ） (2022-02-03T08:45:34Z) - Learning Mixtures of Low-Rank Models [89.39877968115833]
低ランクモデルの計算混合を学習する問題について検討する。
ほぼ最適サンプルを用いて未知の行列を復元することが保証されるアルゴリズムを開発する。
さらに,提案アルゴリズムはランダムノイズに対して確実に安定である。
論文 参考訳（メタデータ） (2020-09-23T17:53:48Z) - Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent [29.684442397855197]
我々は,高次元仮説テストの文脈において,最も普及している2つの制限された計算モデル,統計クエリフレームワークと低次コローラについて検討した。
テスト問題に関する穏やかな条件下では、2種類のアルゴリズムは本質的にはパワーで等価である。
提案手法では, スパースPCA, テンソルPCA, および植木クリッド問題のいくつかの変種に対して, 新たな統計的クエリローバウンドを求める。
論文 参考訳（メタデータ） (2020-09-13T22:55:18Z) - Reducibility and Statistical-Computational Gaps from Secret Leakage [19.25775832101647]
我々は, 秘密リークドライドドライド・ドライド(秘密リークドライド・ドライド・ドライド)の若干の一般化が, 様々な新しい平均ケース・リダクション技術をもたらすことを示した。
特定の種類の秘密漏れクランプに対する植込みクランプ予想の変種を用いて、厳密な統計計算トレードオフを導出する。
論文 参考訳（メタデータ） (2020-05-16T20:56:09Z) - High-Dimensional Robust Mean Estimation via Gradient Descent [73.61354272612752]
一定対向分数の存在下でのロバスト平均推定の問題は勾配降下によって解けることを示す。
我々の研究は、近辺の非補題推定とロバスト統計の間の興味深い関係を確立する。
論文 参考訳（メタデータ） (2020-05-04T10:48:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。