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

• arxiv url: http://arxiv.org/abs/2207.14266v1
• Date: Thu, 28 Jul 2022 17:50:53 GMT
• ステータス: 処理完了
• システム内更新日: 2022-07-29 13:06:23.431285
• Title: Cryptographic Hardness of Learning Halfspaces with Massart Noise
• Title（参考訳）: マスアートノイズを伴う学習用ハーフスペースの暗号ハードネス
• Authors: Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi, Lisheng Ren
• Abstract要約: マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。 我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
• 参考スコア（独自算出の注目度）: 59.8587499110224
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the complexity of PAC learning halfspaces in the presence of Massart noise. In this problem, we are given i.i.d. labeled examples $(\mathbf{x}, y) \in \mathbb{R}^N \times \{ \pm 1\}$, where the distribution of $\mathbf{x}$ is arbitrary and the label $y$ is a Massart corruption of $f(\mathbf{x})$, for an unknown halfspace $f: \mathbb{R}^N \to \{ \pm 1\}$, with flipping probability $\eta(\mathbf{x}) \leq \eta < 1/2$. The goal of the learner is to compute a hypothesis with small 0-1 error. Our main result is the first computational hardness result for this learning problem. Specifically, assuming the (widely believed) subexponential-time hardness of the Learning with Errors (LWE) problem, we show that no polynomial-time Massart halfspace learner can achieve error better than $\Omega(\eta)$, even if the optimal 0-1 error is small, namely $\mathrm{OPT} = 2^{-\log^{c} (N)}$ for any universal constant $c \in (0, 1)$. Prior work had provided qualitatively similar evidence of hardness in the Statistical Query model. Our computational hardness result essentially resolves the polynomial PAC learnability of Massart halfspaces, by showing that known efficient learning algorithms for the problem are nearly best possible.
• Abstract（参考訳）: マスアート雑音の存在下でのpac学習半空間の複雑性について検討する。 この問題において、ラベル付き例 $(\mathbf{x}, y) \in \mathbb{r}^n \times \{ \pm 1\}$, ここで、$\mathbf{x}$ の分布は任意で、ラベル $y$ は、未知の半空間 $f: \mathbb{r}^n \to \{ \pm 1\}$, with flipping probability $\eta(\mathbf{x}) \leq \eta < 1/2$ のマッサート的腐敗である。 学習者の目標は、0-1エラーの少ない仮説を計算することである。 我々の主な成果は、この学習問題に対する最初の計算硬度結果である。 具体的には、誤差付き学習(lwe)問題の(広く信じられている)部分指数時間硬さを仮定すると、任意の普遍定数 $c \in (0, 1)$ に対して$\mathrm{opt} = 2^{-\log^{c} (n)}$ という最適な 0-1 誤差が小さい場合でも、多項式時間マッサート半空間学習者は$\omega(\eta)$ 以上のエラーを達成できない。 以前の研究は、統計クエリモデルにおける硬さの質的類似の証拠を提供していた。 計算硬度の結果は、Massartハーフスペースの多項式PAC学習可能性を本質的に解決し、その問題に対する既知の効率的な学習アルゴリズムが最善であることを示す。

関連論文リスト

• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals [43.0867217287089]
  ガウス分布の下で半空間を不可知的に学習する作業について検討する。 この課題に対して,ほぼ最適計算硬度を証明した。
  論文  参考訳（メタデータ） (2023-02-13T16:46:23Z)
• SQ Lower Bounds for Learning Single Neurons with Massart Noise [40.1662767099183]
  マスアートノイズの存在下で単一ニューロンを学習するPAC。 我々は、任意の定数係数内で最適な誤差を近似できる効率的なSQアルゴリズムが存在しないことを証明した。
  論文  参考訳（メタデータ） (2022-10-18T15:58:00Z)
• 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)
• Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability [39.01599245403753]
  特に、Massartノイズ下でのハーフスペースの学習問題を$eta$で検討する。 我々は任意のSQアルゴリズムが$mathsfOPT + epsilon$を達成するのに超ポリノミカルな多くのクエリを必要とすることを示した。 また、Massartノイズ下でハーフスペースを学習するためのアルゴリズムを実証的に研究し、いくつかの魅力的なフェアネス特性を示すことを示した。
  論文  参考訳（メタデータ） (2020-06-08T17:59:11Z)

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

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