論文の概要: Hardness of Learning Halfspaces with Massart Noise

• arxiv url: http://arxiv.org/abs/2012.09720v1
• Date: Thu, 17 Dec 2020 16:43:11 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-02 07:31:37.354625
• Title: Hardness of Learning Halfspaces with Massart Noise
• Title（参考訳）: マスアート雑音による半空間学習の難易度
• Authors: Ilias Diakonikolas and Daniel M. Kane
• Abstract要約: 我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。 情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
• 参考スコア（独自算出の注目度）: 56.98280399449707
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the complexity of PAC learning halfspaces in the presence of Massart (bounded) noise. Specifically, given labeled examples $(x, y)$ from a distribution $D$ on $\mathbb{R}^{n} \times \{ \pm 1\}$ such that the marginal distribution on $x$ is arbitrary and the labels are generated by an unknown halfspace corrupted with Massart noise at rate $\eta<1/2$, we want to compute a hypothesis with small misclassification error. Characterizing the efficient learnability of halfspaces in the Massart model has remained a longstanding open problem in learning theory. Recent work gave a polynomial-time learning algorithm for this problem with error $\eta+\epsilon$. This error upper bound can be far from the information-theoretically optimal bound of $\mathrm{OPT}+\epsilon$. More recent work showed that {\em exact learning}, i.e., achieving error $\mathrm{OPT}+\epsilon$, is hard in the Statistical Query (SQ) model. In this work, we show that there is an exponential gap between the information-theoretically optimal error and the best error that can be achieved by a polynomial-time SQ algorithm. In particular, our lower bound implies that no efficient SQ algorithm can approximate the optimal error within any polynomial factor.
• Abstract（参考訳）: マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。 具体的には、ラベル付き例 $(x, y)$ が分布 $D$ on $\mathbb{R}^{n} \times \{ \pm 1\}$ から与えられたとき、$x$ の辺分布は任意であり、そのラベルはマッサルトノイズが速度 $\eta<1/2$ で崩壊した未知の半空間によって生成されるので、小さな誤分類誤差で仮説を計算したい。 マッサートモデルにおける半空間の効率的な学習可能性の特徴付けは、学習理論における長年の未解決問題である。 最近の研究は、この問題の多項式時間学習アルゴリズムをエラー$\eta+\epsilon$で与えた。 この誤差上限は、情報理論的に最適な$\mathrm{OPT}+\epsilon$の境界から遠く離れることができる。 より最近の研究は、"em exact learning}、すなわちエラー $\mathrm{opt}+\epsilon$ を達成することは統計クエリ(sq)モデルでは難しいことを示した。 本研究では,情報理論の最適誤差と多項式時間SQアルゴリズムで達成できる最良の誤差との間には指数的ギャップが存在することを示す。 特に、我々の下界は、効率的なSQアルゴリズムが任意の多項式係数内で最適誤差を近似できないことを意味する。

関連論文リスト

• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• 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)
• SQ Lower Bounds for Learning Single Neurons with Massart Noise [40.1662767099183]
  マスアートノイズの存在下で単一ニューロンを学習するPAC。 我々は、任意の定数係数内で最適な誤差を近似できる効率的なSQアルゴリズムが存在しないことを証明した。
  論文  参考訳（メタデータ） (2022-10-18T15:58:00Z)
• Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
  マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。 我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
  論文  参考訳（メタデータ） (2022-07-28T17:50:53Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability [39.01599245403753]
  特に、Massartノイズ下でのハーフスペースの学習問題を$eta$で検討する。 我々は任意のSQアルゴリズムが$mathsfOPT + epsilon$を達成するのに超ポリノミカルな多くのクエリを必要とすることを示した。 また、Massartノイズ下でハーフスペースを学習するためのアルゴリズムを実証的に研究し、いくつかの魅力的なフェアネス特性を示すことを示した。
  論文  参考訳（メタデータ） (2020-06-08T17:59:11Z)

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

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