論文の概要: Agnostic Learning of a Single Neuron with Gradient Descent
- arxiv url: http://arxiv.org/abs/2005.14426v3
- Date: Mon, 31 Aug 2020 17:19:08 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-26 23:04:49.216585
- Title: Agnostic Learning of a Single Neuron with Gradient Descent
- Title（参考訳）: 勾配の老化を伴う単一ニューロンの認識学習
- Authors: Spencer Frei and Yuan Cao and Quanquan Gu
- Abstract要約: 期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
- 参考スコア（独自算出の注目度）: 92.7662890047311
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of learning the best-fitting single neuron as
measured by the expected square loss $\mathbb{E}_{(x,y)\sim
\mathcal{D}}[(\sigma(w^\top x)-y)^2]$ over some unknown joint distribution
$\mathcal{D}$ by using gradient descent to minimize the empirical risk induced
by a set of i.i.d. samples $S\sim \mathcal{D}^n$. The activation function
$\sigma$ is an arbitrary Lipschitz and non-decreasing function, making the
optimization problem nonconvex and nonsmooth in general, and covers typical
neural network activation functions and inverse link functions in the
generalized linear model setting. In the agnostic PAC learning setting, where
no assumption on the relationship between the labels $y$ and the input $x$ is
made, if the optimal population risk is $\mathsf{OPT}$, we show that gradient
descent achieves population risk $O(\mathsf{OPT})+\epsilon$ in polynomial time
and sample complexity when $\sigma$ is strictly increasing. For the ReLU
activation, our population risk guarantee is $O(\mathsf{OPT}^{1/2})+\epsilon$.
When labels take the form $y = \sigma(v^\top x) + \xi$ for zero-mean
sub-Gaussian noise $\xi$, we show that the population risk guarantees for
gradient descent improve to $\mathsf{OPT} + \epsilon$. Our sample complexity
and runtime guarantees are (almost) dimension independent, and when $\sigma$ is
strictly increasing, require no distributional assumptions beyond boundedness.
For ReLU, we show the same results under a nondegeneracy assumption for the
marginal distribution of the input.
- Abstract（参考訳）: 期待される二乗損失 $\mathbb{E}_{(x,y)\sim \mathcal{D}}[(\sigma(w^\top x)-y)^2]$ で測定された最も適した単一ニューロンを学習する問題を考える。
アクティベーション関数 $\sigma$ は任意のリプシッツおよび非減少関数であり、最適化問題を非凸および非滑らかにし、一般化線形モデル設定における典型的なニューラルネットワーク活性化関数と逆リンク関数をカバーする。
ラベル $y$ と入力 $x$ の関係を仮定しないpac学習設定では、最適な人口リスクが $\mathsf{opt}$ である場合、勾配降下が多項式時間および$\sigma$ が厳密に増加するときのサンプル複雑性において、人口リスク $o(\mathsf{opt})+\epsilon$ を達成することが示されている。
ReLU 活性化の場合、我々の集団リスク保証は$O(\mathsf{OPT}^{1/2})+\epsilon$である。
ラベルが y = \sigma(v^\top x) + \xi$ for zero-mean sub-gaussian noise $\xi$ という形を取ると、勾配降下に対する人口リスクの保証は $\mathsf{opt} + \epsilon$ となる。
サンプルの複雑さとランタイムの保証は(ほぼ)次元独立であり、$\sigma$ が厳密に増加すると、境界を超えた分布的仮定は必要なくなる。
reluの場合、入力の限界分布に対する非退化仮定の下で同じ結果を示す。
関連論文リスト
- Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models [37.42736399673992]
シングルインデックスモデル (SIM) は $sigma(mathbfwast cdot mathbfx)$ という形式の関数であり、$sigma: mathbbR to mathbbR$ は既知のリンク関数であり、$mathbfwast$ は隠れ単位ベクトルである。
適切な学習者が$L2$-error of $O(mathrmOPT)+epsilon$。
論文 参考訳（メタデータ） (2024-11-08T17:10:38Z) - Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-01T17:59:53Z) - Iterative thresholding for non-linear learning in the strong $\varepsilon$-contamination model [3.309767076331365]
閾値降下を用いた単一ニューロンモデル学習のための近似境界を導出する。
線形回帰問題も研究し、$sigma(mathbfx) = mathbfx$ となる。
論文 参考訳（メタデータ） (2024-09-05T16:59:56Z) - Sharp Rates in Dependent Learning Theory: Avoiding Sample Size Deflation for the Square Loss [33.18537822803389]
L2$ と $Psi_p$ の位相が我々の仮説クラス $mathscrF$, $mathscrF$ に同値であるときにいつでも、$mathscrF$ は弱準ガウス類であることを示す。
以上の結果から, 混合への直接的な依存は高次項に還元されるため, この問題は実現可能か否かを判断できる。
論文 参考訳（メタデータ） (2024-02-08T18:57:42Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - A Fast Algorithm for Adaptive Private Mean Estimation [5.090363690988394]
我々は、$Sigma$に適応する$(varepsilon, delta)$-differentially privateアルゴリズムを設計する。
推定子は、誘導されたマハラノビスノルム $|cdot||_Sigma$ に対して最適な収束率を達成する。
論文 参考訳（メタデータ） (2023-01-17T18:44:41Z) - 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) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and
ReLUs under Gaussian Marginals [49.60752558064027]
ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。
我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
論文 参考訳（メタデータ） (2020-06-29T17:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。