論文の概要: Counterexamples to the Low-Degree Conjecture

• arxiv url: http://arxiv.org/abs/2004.08454v1
• Date: Fri, 17 Apr 2020 21:08:11 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-12 13:42:13.318699
• Title: Counterexamples to the Low-Degree Conjecture
• Title（参考訳）: 低重力環境に対する反例
• Authors: Justin Holmgren, Alexander S. Wein
• Abstract要約: ホプキンスの予想は、ある高次元仮説テスト問題に対して、非時間アルゴリズムはいわゆる「単純な統計」よりも優れていると仮定する。 この予想は、統計対計算のトレードオフを理解しようとする最近の研究のラインを囲む信念を定式化する。
• 参考スコア（独自算出の注目度）: 80.3668228845075
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A conjecture of Hopkins (2018) posits that for certain high-dimensional hypothesis testing problems, no polynomial-time algorithm can outperform so-called "simple statistics", which are low-degree polynomials in the data. This conjecture formalizes the beliefs surrounding a line of recent work that seeks to understand statistical-versus-computational tradeoffs via the low-degree likelihood ratio. In this work, we refute the conjecture of Hopkins. However, our counterexample crucially exploits the specifics of the noise operator used in the conjecture, and we point out a simple way to modify the conjecture to rule out our counterexample. We also give an example illustrating that (even after the above modification), the symmetry assumption in the conjecture is necessary. These results do not undermine the low-degree framework for computational lower bounds, but rather aim to better understand what class of problems it is applicable to.
• Abstract（参考訳）: ホプキンスの予想(2018年)は、ある種の高次元仮説テスト問題に対して、多項式時間アルゴリズムはデータ内の低次多項式であるいわゆる「単純な統計」を上回ることができないことを仮定している。 この予想は、統計対計算のトレードオフを理解しようとする最近の研究のラインを取り巻く信念を、低次度比で定式化する。 この研究において、ホプキンスの予想に反論する。 しかしながら、我々の反例は、この予想で使われるノイズ演算子の特異点を決定的に活用し、我々の反例を除外するために予想を変更する簡単な方法を指摘した。 また、上記の修正の後でさえ、予想における対称性の仮定が不可欠であることを示す例を示す。 これらの結果は、計算下界の低次フレームワークを損なうものではなく、それが適用可能な問題の種類をよりよく理解することを目的としている。

関連論文リスト

• Mining Math Conjectures from LLMs: A Pruning Approach [0.0]
  本稿では,Large Language Models (LLMs) を用いた数理予想生成手法を提案する。 我々は、ChatGPT, Gemini, Claude などの LLM がどのようにして予想を生成するかを示す。 以上の結果から,LLM は,コード実行に制限があるにも関わらず,基本的ではないものの,正当性あるいは正当性がある,という予想を導出できる可能性が示唆された。
  論文  参考訳（メタデータ） (2024-12-09T19:00:38Z)
• Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
  我々は,PCAが信号の大きさの臨界値で計算的に困難になることを示す。 我々は、与えられた次数の不変量に対して明示的でほぼ直交的な基底を与える新しい対象の集合を定義する。 また、異なるアンサンブルを区別する新しい問題も分析できます。
  論文  参考訳（メタデータ） (2024-04-29T14:33:24Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Connes implies Tsirelson: a simple proof [91.3755431537592]
  コンヌ埋め込み問題は同期的ツィレルソン予想を意味することを示す。 また、コンネスの代数 $mathcalRomega$ の異なる構成もコンネス埋め込み問題に現れる。
  論文  参考訳（メタデータ） (2022-09-16T13:59:42Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• Learning Weakly Convex Sets in Metric Spaces [2.0618817976970103]
  機械学習理論における中心的な問題は、ゼロエラーを持つ一貫した仮説を効率的に見つけることができるかどうかである。 このアルゴリズムの一般的な考え方は、弱凸仮説の場合にまで拡張可能であることを示す。
  論文  参考訳（メタデータ） (2021-05-10T23:00:02Z)
• Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron [21.356438315715888]
  我々は、ニューラルネットワークの単純なモデルである対称バイナリパーセプトロンモデルを検討する。 このモデルのためのいくつかの予想を確立する。 この証明手法は,小さなグラフ条件付け手法の密な反部分に依存する。
  論文  参考訳（メタデータ） (2021-02-25T18:39:08Z)
• On a conjecture regarding quantum hypothesis testing [0.0]
  古典的な場合、最も達成可能な対称誤差指数は単に「ウォルストケース対」に対応する最も達成可能な対称エラー指数である。 数年前に提起された予想は、量子のケースでもこれが真実である、というものである。 私は新しい特別な場合を考えるが、一方では「非対称」でありながら解析的に計算可能である。
  論文  参考訳（メタデータ） (2020-11-05T18:31:28Z)
• Lower bounds in multiple testing: A framework based on derandomized proxies [107.69746750639584]
  本稿では, 各種コンクリートモデルへの適用例を示す, デランドマイズに基づく分析戦略を提案する。 これらの下界のいくつかを数値シミュレーションし、Benjamini-Hochberg (BH) アルゴリズムの実際の性能と密接な関係を示す。
  論文  参考訳（メタデータ） (2020-05-07T19:59:51Z)
• Lower Bounds for Non-Elitist Evolutionary Algorithms via Negative Multiplicative Drift [9.853329403413701]
  乗法的ドリフトシナリオに対する単純な負のドリフト定理は既存の解析を単純化できることを示す。 我々は、非エリート変異に基づく進化アルゴリズムのランタイムにおける下位境界を証明するための最も一般的なツールの1つである集団法において、Lehre's emph negative drift in populations法(PPSN 2010)についてより詳細に論じる。
  論文  参考訳（メタデータ） (2020-05-02T15:10:09Z)

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

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