論文の概要: Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces
and ReLU Regression under Gaussian Marginals
- arxiv url: http://arxiv.org/abs/2302.06512v1
- Date: Mon, 13 Feb 2023 16:46:23 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-14 14:54:53.996840
- Title: Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces
and ReLU Regression under Gaussian Marginals
- Title（参考訳）: ガウスマルジナルの半空間学習とReLU回帰の準最適暗号ハードネス
- Authors: Ilias Diakonikolas, Daniel M. Kane, Lisheng Ren
- Abstract要約: ガウス分布の下で半空間を不可知的に学習する作業について検討する。
この課題に対して,ほぼ最適計算硬度を証明した。
- 参考スコア（独自算出の注目度）: 43.0867217287089
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the task of agnostically learning halfspaces under the Gaussian
distribution. Specifically, given labeled examples $(\mathbf{x},y)$ from an
unknown distribution on $\mathbb{R}^n \times \{ \pm 1\}$, whose marginal
distribution on $\mathbf{x}$ is the standard Gaussian and the labels $y$ can be
arbitrary, the goal is to output a hypothesis with 0-1 loss
$\mathrm{OPT}+\epsilon$, where $\mathrm{OPT}$ is the 0-1 loss of the
best-fitting halfspace. We prove a near-optimal computational hardness result
for this task, under the widely believed sub-exponential time hardness of the
Learning with Errors (LWE) problem. Prior hardness results are either
qualitatively suboptimal or apply to restricted families of algorithms. Our
techniques extend to yield near-optimal lower bounds for related problems,
including ReLU regression.
- Abstract（参考訳）: ガウス分布の下で半空間を無知に学習するタスクについて検討する。
具体的には、ラベル付き例 $(\mathbf{x},y)$ が $\mathbb{R}^n \times \{ \pm 1\}$ 上の未知の分布から与えられたとき、$\mathbf{x}$ 上の限界分布は標準ガウス分布であり、ラベル $y$ は任意であり、その目標は 0-1 の損失を持つ仮説を $\mathrm{OPT}+\epsilon$ で出力することである。
この課題に対して,Learning with Errors (LWE) 問題において,広く信じられている部分指数時間硬度の下で,ほぼ最適計算硬度を証明した。
事前硬度結果は定性的に最適か、あるいは制限されたアルゴリズムの族に適用される。
提案手法は,relu回帰を含む関連する問題に対して,ほぼ最適下限を与えるように拡張する。
関連論文リスト
- Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds [9.036777309376697]
Klivans、Stavropoulos、Vasilyanは、分散シフトを伴うテスト可能な学習の研究を始めた。
それらのモデルは、$mathcalD'$に仮定されないという点で、以前のすべての作業から逸脱している。
論文 参考訳（メタデータ） (2024-04-02T23:34:39Z) - 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) - 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) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文 参考訳（メタデータ） (2020-05-29T07:20:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。