論文の概要: Low-Degree Method Fails to Predict Robust Subspace Recovery

• arxiv url: http://arxiv.org/abs/2603.02594v1
• Date: Tue, 03 Mar 2026 04:42:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-04 21:38:10.638512
• Title: Low-Degree Method Fails to Predict Robust Subspace Recovery
• Title（参考訳）: ロバスト部分空間の回復を予測できない低層法
• Authors: He Jia, Aravindan Vijayaraghavan,
• Abstract要約: 我々は,低度手法と低度モーメントが,アンチ集中に基づくアルゴリズムの捕捉に失敗したことを示す。 この結果は,計算障壁の予測因子としての普遍性に挑戦する。
• 参考スコア（独自算出の注目度）: 11.09360259927697
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The low-degree polynomial framework has been highly successful in predicting computational versus statistical gaps for high-dimensional problems in average-case analysis and machine learning. This success has led to the low-degree conjecture, which posits that this method captures the power and limitations of efficient algorithms for a wide class of high-dimensional statistical problems. We identify a natural and basic hypothesis testing problem in $\mathbb{R}^n$ which is polynomial time solvable, but for which the low-degree polynomial method fails to predict its computational tractability even up to degree $k=n^{Ω(1)}$. Moreover, the low-degree moments match exactly up to degree $k=O(\sqrt{\log n/\log\log n})$. Our problem is a special case of the well-studied robust subspace recovery problem. The lower bounds suggest that there is no polynomial time algorithm for this problem. In contrast, we give a simple and robust polynomial time algorithm that solves the problem (and noisy variants of it), leveraging anti-concentration properties of the distribution. Our results suggest that the low-degree method and low-degree moments fail to capture algorithms based on anti-concentration, challenging their universality as a predictor of computational barriers.
• Abstract（参考訳）: 低次多項式フレームワークは、平均ケース解析と機械学習における高次元問題に対する計算と統計のギャップを予測することに成功している。 この成功は、この手法が様々な高次元統計問題に対する効率的なアルゴリズムのパワーと限界を捉えていると仮定する低次予想に繋がった。 多項式時間分解可能な$\mathbb{R}^n$の自然かつ基本的な仮説テスト問題を特定するが、低次多項式法はその計算的トラクタビリティを$k=n^{Ω(1)}$まで予測できない。 さらに、低次モーメントはちょうど$k=O(\sqrt{\log n/\log\log n})$に一致する。 我々の問題は、よく研究された頑健な部分空間回復問題の特別な場合である。 下限は、この問題に対して多項式時間アルゴリズムが存在しないことを示唆している。 対照的に、分布の反集中性を利用して問題を解く単純で頑健な多項式時間アルゴリズムを与える。 この結果から,低次手法と低次モーメントは反集中に基づくアルゴリズムの捕捉に失敗し,計算障壁の予測手法としての普遍性に挑戦することが示唆された。

関連論文リスト

• Learning Intersections of Two Margin Halfspaces under Factorizable Distributions [56.51474048985742]
  ハーフスペースの交叉学習は計算学習理論における中心的な問題である。 たった2つのハーフスペースであっても、学習が時間内に可能かどうかという大きな疑問が残る。 本稿ではCSQ硬度障壁を確実に回避する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-11-13T00:28:24Z)
• Low-degree lower bounds via almost orthonormal bases [47.83594448785856]
  低次数は、様々な高次元統計モデルにまたがる統計的-計算的ギャップの証拠を提供するための強力なパラダイムとして現れてきた。 本研究では,より直接的な証明戦略を提案する。
  論文  参考訳（メタデータ） (2025-09-11T11:07:36Z)
• Low degree conjecture implies sharp computational thresholds in stochastic block model [3.7873597471903935]
  我々は(拡張)低次予想(対称ブロックモデルにおける[MW23]の最近の形式化)の影響について検討する。 我々は,Kesten-Stigum(KS)しきい値以下で,非リアルタイムアルゴリズムがコミュニティラベルを弱めに復元できることを確立した。 この結果から,ブロックモデルのパラメータの学習において,計算量と統計量との差があることが示唆された。
  論文  参考訳（メタデータ） (2025-02-20T20:21:03Z)
• Computational-Statistical Gaps in Reinforcement Learning [23.517741855454044]
  そこでは,CNF式を決定論的遷移,動作の定数数,低次元線形最適値関数を備えたMDP仮説に変換する。 この結果は線形関数近似を用いた強化学習における最初の計算統計的ギャップを示す。
  論文  参考訳（メタデータ） (2022-02-11T04:48:35Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• A Boosting Approach to Reinforcement Learning [59.46285581748018]
  複雑度が状態数に依存しない意思決定プロセスにおける強化学習のための効率的なアルゴリズムについて検討する。 このような弱い学習手法の精度を向上させることができる効率的なアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2021-08-22T16:00:45Z)
• Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent [29.684442397855197]
  我々は,高次元仮説テストの文脈において,最も普及している2つの制限された計算モデル,統計クエリフレームワークと低次コローラについて検討した。 テスト問題に関する穏やかな条件下では、2種類のアルゴリズムは本質的にはパワーで等価である。 提案手法では, スパースPCA, テンソルPCA, および植木クリッド問題のいくつかの変種に対して, 新たな統計的クエリローバウンドを求める。
  論文  参考訳（メタデータ） (2020-09-13T22:55:18Z)
• Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
  本研究では,隠れ構造物の存在を検知する作業において,低次構造物のパワーについて検討する。 大規模な「信号+雑音」問題に対して、任意の程度に達成可能な最良の平均二乗誤差に対して、ユーザフレンドリな下界を与える。 応用として,植込みサブマトリクスに対する低次平均2乗誤差の厳密な評価と高密度サブグラフ問題について述べる。
  論文  参考訳（メタデータ） (2020-08-05T17:52:10Z)
• Instability, Computational Efficiency and Statistical Accuracy [101.32305022521024]
  我々は,人口レベルでのアルゴリズムの決定論的収束率と,$n$サンプルに基づく経験的対象に適用した場合の(不安定性)の間の相互作用に基づいて,統計的精度を得るフレームワークを開発する。 本稿では,ガウス混合推定,非線形回帰モデル,情報的非応答モデルなど,いくつかの具体的なモデルに対する一般結果の応用について述べる。
  論文  参考訳（メタデータ） (2020-05-22T22:30:52Z)
• High-Dimensional Robust Mean Estimation via Gradient Descent [73.61354272612752]
  一定対向分数の存在下でのロバスト平均推定の問題は勾配降下によって解けることを示す。 我々の研究は、近辺の非補題推定とロバスト統計の間の興味深い関係を確立する。
  論文  参考訳（メタデータ） (2020-05-04T10:48:04Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。