論文の概要: SQ Lower Bounds for Learning Single Neurons with Massart Noise

• arxiv url: http://arxiv.org/abs/2210.09949v1
• Date: Tue, 18 Oct 2022 15:58:00 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-19 14:20:59.873868
• Title: SQ Lower Bounds for Learning Single Neurons with Massart Noise
• Title（参考訳）: マスアートノイズによる単一ニューロン学習のためのSQ下界
• Authors: Ilias Diakonikolas, Daniel M. Kane, Lisheng Ren, Yuxin Sun
• Abstract要約: マスアートノイズの存在下で単一ニューロンを学習するPAC。 我々は、任意の定数係数内で最適な誤差を近似できる効率的なSQアルゴリズムが存在しないことを証明した。
• 参考スコア（独自算出の注目度）: 40.1662767099183
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of PAC learning a single neuron in the presence of Massart noise. Specifically, for a known activation function $f: \mathbb{R} \to \mathbb{R}$, the learner is given access to labeled examples $(\mathbf{x}, y) \in \mathbb{R}^d \times \mathbb{R}$, where the marginal distribution of $\mathbf{x}$ is arbitrary and the corresponding label $y$ is a Massart corruption of $f(\langle \mathbf{w}, \mathbf{x} \rangle)$. The goal of the learner is to output a hypothesis $h: \mathbb{R}^d \to \mathbb{R}$ with small squared loss. For a range of activation functions, including ReLUs, we establish super-polynomial Statistical Query (SQ) lower bounds for this learning problem. In more detail, we prove that no efficient SQ algorithm can approximate the optimal error within any constant factor. Our main technical contribution is a novel SQ-hard construction for learning $\{ \pm 1\}$-weight Massart halfspaces on the Boolean hypercube that is interesting on its own right.
• Abstract（参考訳）: 我々は,Massartノイズの存在下で単一ニューロンを学習するPACの問題について検討した。 具体的には、既知の活性化関数 $f: \mathbb{r} \to \mathbb{r}$ に対して、学習者はラベル付き例 $(\mathbf{x}, y) \in \mathbb{r}^d \times \mathbb{r}$ へのアクセスを与える。 学習者の目標は、仮説 $h: \mathbb{R}^d \to \mathbb{R}$ を小さな正方形損失で出力することである。 ReLUを含む様々なアクティベーション関数に対して、この学習問題に対して超多項式統計クエリ(SQ)の下位境界を確立する。 より詳しくは、任意の定数係数内で最適な誤差を近似できる効率的なSQアルゴリズムが存在しないことを証明する。 我々の主な技術的貢献は、Booleanハイパーキューブ上の$\{ \pm 1\}$-weight Massartハーフスペースを学ぶための新しいSQハード構成である。

関連論文リスト

• 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)
• Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
  我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。 情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
  論文  参考訳（メタデータ） (2020-12-17T16:43:11Z)
• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals [49.60752558064027]
  ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。 我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
  論文  参考訳（メタデータ） (2020-06-29T17:10:10Z)

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

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