論文の概要: Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and
ReLUs under Gaussian Marginals
- arxiv url: http://arxiv.org/abs/2006.16200v1
- Date: Mon, 29 Jun 2020 17:10:10 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-15 14:32:02.044361
- Title: Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and
ReLUs under Gaussian Marginals
- Title（参考訳）: gaussian marginalsにおける半空間とrelusを無知に学習するための近最適sq下限
- Authors: Ilias Diakonikolas, Daniel M. Kane, Nikos Zarifis
- Abstract要約: ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。
我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
- 参考スコア（独自算出の注目度）: 49.60752558064027
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the fundamental problems of agnostically learning halfspaces and
ReLUs under Gaussian marginals. In the former problem, given labeled examples
$(\mathbf{x}, y)$ from an unknown distribution on $\mathbb{R}^d \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. In the latter problem, given labeled examples
$(\mathbf{x}, y)$ from an unknown distribution on $\mathbb{R}^d \times
\mathbb{R}$, 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 square loss $\mathrm{OPT}+\epsilon$, where $\mathrm{OPT}$ is
the square loss of the best-fitting ReLU. We prove Statistical Query (SQ) lower
bounds of $d^{\mathrm{poly}(1/\epsilon)}$ for both of these problems. Our SQ
lower bounds provide strong evidence that current upper bounds for these tasks
are essentially best possible.
- Abstract（参考訳）: 半空間とrelusをgaussian marginalsの下で無知に学習する根本的な問題について検討する。
前者問題では、ラベル付き例 $(\mathbf{x}, y)$ が$\mathbb{r}^d \times \{ \pm 1\}$ 上の未知の分布から与えられた場合、$\mathbf{x}$ の限界分布は標準ガウス分布であり、$y$ は任意であるので、目標は 0-1 の損失 $\mathrm{opt}+\epsilon$ の仮説を出力することである。
後者の問題では、ラベル付き例 $(\mathbf{x}, y)$ が未知分布上の未知分布 $\mathbb{R}^d \times \mathbb{R}$ に与えられたとき、$\mathbf{x}$ 上の余剰分布は標準ガウス分布であり、ラベル $y$ は任意の値であり、その目標は平方損失 $\mathrm{OPT}+\epsilon$ の仮説を出力することであり、$\mathrm{OPT}$ は最も適した ReLU の正則損失である。
これらの問題に対して、統計的クエリ (SQ) の$d^{\mathrm{poly}(1/\epsilon)} の下位境界を証明した。
我々の SQ 下位境界は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
関連論文リスト
- Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noise [38.551072383777594]
本研究では, 対向分布シフトの存在下でのL2$損失に対して, 単一ニューロンを学習する問題について検討した。
ベクトルベクトル二乗損失を$chi2$divergenceから$mathcalp_0$に近似するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2024-11-11T03:43:52Z) - 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) - 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) - Beyond Independent Measurements: General Compressed Sensing with GNN
Application [4.924126492174801]
我々は、ノイズコーン観測からmathbbRn$の構造化信号$mathbfxを復元する問題を考察する。
実効的な$mathbfB$は測定値のサロゲートとして用いられる可能性がある。
論文 参考訳（メタデータ） (2021-10-30T20:35:56Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - Efficient Statistics for Sparse Graphical Models from Truncated Samples [19.205541380535397]
i) スパースガウス図形モデルの推論と (ii) スパース線形モデルの回復支援の2つの基本的問題と古典的問題に焦点をあてる。
疎線型回帰については、$(bf x,y)$ が生成されるが、$y = bf xtopOmega* + MathcalN(0,1)$ と $(bf x, y)$ は、truncation set $S subseteq mathbbRd$ に属する場合にのみ見られる。
論文 参考訳（メタデータ） (2020-06-17T09:21:00Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。