Agnostic Learning of a Single Neuron with Gradient Descent
Agnostic Learning of a Single Neuron with Gradient Descent
复制标题
DOI：
--
复制
发表时间：
2020-05
期刊：
影响因子：
--
通讯作者：
Spencer Frei;Yuan Cao;Quanquan Gu
中科院分区：
文献类型：
--
作者：
Spencer Frei;Yuan Cao;Quanquan Gu
我们考虑学习最合适的单神经元的问题，如预期的平方损失$ \ mathbb {e} _ {（x，x，y）\ sim \ sim \ mathcal {d}} [（\ sigma（w^\ top x） ）-y）^2] $在某些未知的联合分配上$ \ MATHCAL {D} $，通过使用梯度下降来最大程度地减少一组经验风险I.I.D.样本$ s \ sim \ Mathcal {d}^n $。激活函数$ \ sigma $是任意的Lipschitz和非降低功能，通常使优化问题非凸和非平滑纸，并且涵盖了典型的神经网络激活功能，并且在广义线性模型设置中涵盖了典型的神经网络激活功能和倒数链接函数。在不可知论的PAC学习环境中，在标签$ y $和输入$ x $之间的关系的情况下，如果最佳人口风险为$ \ Mathsf {opt} $，我们表明该梯度下降可以达到人口的风险$ O（\ Mathsf {opt}^{1/2}）+\ epsilon $在多项式时间和样本复杂性中。当标签以$ y = \ sigma（v^\ top x） + \ xi $表示零均值的sub-gaussian噪声$ \ xi $时，我们表明梯度下降达到人口风险$ \ mathsf {opt} + \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ Epsilon $。我们的样本复杂性和运行时保证是（几乎）独立的，并且当$ \ sigma $严格增加和Lipschitz时，不需要超越界限的分配假设。对于Relu，我们在非修复性假设下显示了输入边际分布的相同结果。据我们所知，这是使用梯度下降对单个神经元的不可知论学习的第一个结果。
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}^{1/2})+\epsilon$ in polynomial time and sample complexity. When labels take the form $y = \sigma(v^\top x) + \xi$ for zero-mean sub-Gaussian noise $\xi$, we show that gradient descent achieves population risk $\mathsf{OPT} + \epsilon$. Our sample complexity and runtime guarantees are (almost) dimension independent, and when $\sigma$ is strictly increasing and Lipschitz, require no distributional assumptions beyond boundedness. For ReLU, we show the same results under a nondegeneracy assumption for the marginal distribution of the input. To the best of our knowledge, this is the first result for agnostic learning of a single neuron using gradient descent.