論文の概要: Improved Hardness Results for Learning Intersections of Halfspaces
- arxiv url: http://arxiv.org/abs/2402.15995v1
- Date: Sun, 25 Feb 2024 05:26:35 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-27 15:51:45.922779
- Title: Improved Hardness Results for Learning Intersections of Halfspaces
- Title（参考訳）: ハーフスペースの学習区間における硬度改善
- Authors: Stefan Tiegel
- Abstract要約: 不適切な設定でハーフ空間の弱学習交差点に対して、強い(そして驚くほど単純な)下界を示す。
我々は、$omega(log log N)$ halfspaces を$N$で学習しても超多項式時間を要することを示すことで、このギャップを著しく狭めている。
具体的には、次元$N$の任意の$k$ハーフスペースに対して、精度$N-Omega(k)$、指数関数的に多くのクエリが必要であることを示す。
- 参考スコア（独自算出の注目度）: 2.1393480341554736
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We show strong (and surprisingly simple) lower bounds for weakly learning
intersections of halfspaces in the improper setting. Strikingly little is known
about this problem. For instance, it is not even known if there is a
polynomial-time algorithm for learning the intersection of only two halfspaces.
On the other hand, lower bounds based on well-established assumptions (such as
approximating worst-case lattice problems or variants of Feige's 3SAT
hypothesis) are only known (or are implied by existing results) for the
intersection of super-logarithmically many halfspaces [KS09,KS06,DSS16]. With
intersections of fewer halfspaces being only ruled out under less standard
assumptions [DV21] (such as the existence of local pseudo-random generators
with large stretch). We significantly narrow this gap by showing that even
learning $\omega(\log \log N)$ halfspaces in dimension $N$ takes
super-polynomial time under standard assumptions on worst-case lattice problems
(namely that SVP and SIVP are hard to approximate within polynomial factors).
Further, we give unconditional hardness results in the statistical query
framework. Specifically, we show that for any $k$ (even constant), learning $k$
halfspaces in dimension $N$ requires accuracy $N^{-\Omega(k)}$, or
exponentially many queries -- in particular ruling out SQ algorithms with
polynomial accuracy for $\omega(1)$ halfspaces. To the best of our knowledge
this is the first unconditional hardness result for learning a super-constant
number of halfspaces.
Our lower bounds are obtained in a unified way via a novel connection we make
between intersections of halfspaces and the so-called parallel pancakes
distribution [DKS17,BLPR19,BRST21] that has been at the heart of many lower
bound constructions in (robust) high-dimensional statistics in the past few
years.
- Abstract（参考訳）: 不適切な設定で半空間の交点を弱く学習するための強い(そして驚くほど単純な)下界を示す。
この問題についてはほとんど分かっていない。
例えば、2つの半空間の交叉を学ぶ多項式時間アルゴリズムが存在するかどうかさえ分かっていない。
一方、確立された仮定に基づく下界(最悪の格子問題やフェイジの3SAT仮説の変項の近似など)は、超対数的に多くのハーフ空間 [KS09,KS06,DSS16] の交叉についてのみ知られている(あるいは既存の結果によって示唆される)。
より少ない半空間の交叉は、[dv21] よりも小さい標準仮定でのみ除外される(例えば、大きなストレッチを持つ局所擬ランダム生成器の存在など)。
このギャップをかなり狭め、次元で$\omega(\log \log n)$のハーフスペースを学習しても、最悪の場合の格子問題の標準的な仮定の下で超多項時間を取る(つまり、svp と sivp は多項式因子内で近似することが難しい)。
さらに,統計クエリフレームワークにおいて,無条件のハードネス結果を与える。
具体的には、任意の$k$(定数であっても)に対して、k$ハーフスペースを次元$n$で学習するには、精度$n^{-\omega(k)}$、あるいは指数的に多くのクエリが必要であり、特に$\omega(1)$ハーフスペースの多項式精度を持つsqアルゴリズムを除外する必要がある。
私たちの知る限りでは、これは半空間の超定数数を学ぶための最初の無条件のハードネスの結果です。
我々の下界は、近年の高次元統計学における多くの下界構造の中心にある、ハーフスペースの交点といわゆる平行パンケーキ分布(DKS17,BLPR19,BRST21]の間の新しい接続を通じて統一的に得られる。
関連論文リスト
- Reliable Learning of Halfspaces under Gaussian Marginals [34.64644162448095]
本稿では,カライらの信頼的無知モデルにおけるPAC学習ハーフスペースの問題について検討する。
我々の主な肯定的な結果は、サンプルおよび計算複雑性を持つ$mathbbRd$上のガウス半空間の信頼性学習のための新しいアルゴリズムである。
論文 参考訳（メタデータ） (2024-11-18T02:13:11Z) - Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension [17.485243410774814]
教師付き学習の伝統的なモデルでは、学習者の目標は、あるクラスから最も適した概念の競争的($epsilon$以内)な仮説を出力することである。
学習者が最高の無知としか競合しないスムーズな分析フレームワークを導入する。
時間内に$k$-halfspacesの交点を前向きに学習する最初のアルゴリズムを得る。
論文 参考訳（メタデータ） (2024-07-01T04:58:36Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。
我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
論文 参考訳（メタデータ） (2022-07-28T17:50:53Z) - Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice
Problems [0.49495085874952904]
特に、この仮定の下では、必ずしもハーフスペースではなく、任意のバイナリ仮説を出力する効率的なアルゴリズムは存在しないことを示す。
これは、最悪の格子問題に基づいて、よく分離されたガウス混合を学習する難しさを示す最近の一連の研究から着想を得たものである。
論文 参考訳（メタデータ） (2022-07-28T11:44:39Z) - Near-Optimal Statistical Query Lower Bounds for Agnostically Learning
Intersections of Halfspaces with Gaussian Marginals [10.06689891744466]
本稿では,ガウス分布下での中間空間の学習に関するよく研究された問題について,難易度学習モデルを用いて考察する。
下界の2つの変種を証明し、それぞれがダイアコニコラスら (2021) の成分と、Boolean の設定に対する SQ 下界に対する異なる以前のアプローチ(拡張)を組み合わせた。
論文 参考訳（メタデータ） (2022-02-10T15:34:10Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。
情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
論文 参考訳（メタデータ） (2020-12-17T16:43:11Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。