論文の概要: 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年)は、ある種の高次元仮説テスト問題に対して、多項式時間アルゴリズムはデータ内の低次多項式であるいわゆる「単純な統計」を上回ることができないことを仮定している。
この予想は、統計対計算のトレードオフを理解しようとする最近の研究のラインを取り巻く信念を、低次度比で定式化する。
この研究において、ホプキンスの予想に反論する。
しかしながら、我々の反例は、この予想で使われるノイズ演算子の特異点を決定的に活用し、我々の反例を除外するために予想を変更する簡単な方法を指摘した。
また、上記の修正の後でさえ、予想における対称性の仮定が不可欠であることを示す例を示す。
これらの結果は、計算下界の低次フレームワークを損なうものではなく、それが適用可能な問題の種類をよりよく理解することを目的としている。
関連論文リスト
- Mathematical conjecture generation using machine intelligence [0.0]
f の型 f の厳密な不等式に焦点をあて、それらをベクトル空間に関連付ける。
我々は、この多様体の線型自己同型を研究することによって、この予想空間の構造的理解を発展させる。
幾何勾配勾配を用いた新しい予想を生成するアルゴリズムパイプラインを提案する。
論文 参考訳(メタデータ) (2023-06-12T17:58:38Z) - 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) - Deconfounding Scores: Feature Representations for Causal Effect
Estimation with Weak Overlap [140.98628848491146]
推定対象の偏りを伴わずに高い重なりを生じさせる,デコンファウンディングスコアを導入する。
分離スコアは観測データで識別可能なゼロ共分散条件を満たすことを示す。
特に,この手法が標準正規化の魅力的な代替となることを示す。
論文 参考訳(メタデータ) (2021-04-12T18:50:11Z) - 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) - Compressing Large Sample Data for Discriminant Analysis [78.12073412066698]
判別分析フレームワーク内での大きなサンプルサイズに起因する計算問題を考察する。
線形および二次判別分析のためのトレーニングサンプル数を削減するための新しい圧縮手法を提案する。
論文 参考訳(メタデータ) (2020-05-08T05:09:08Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。