Learning a Single Neuron with Adversarial Label Noise via Gradient Descent
Learning a Single Neuron with Adversarial Label Noise via Gradient Descent
复制标题
DOI：
10.48550/arxiv.2206.08918
复制
发表时间：
2022-06
期刊：
影响因子：
--
通讯作者：
Ilias Diakonikolas;Vasilis Kontonis;Christos Tzamos;Nikos Zarifis
中科院分区：
文献类型：
--
作者：
Ilias Diakonikolas;Vasilis Kontonis;Christos Tzamos;Nikos Zarifis
我们研究学习单个神经元的基本问题，即$ \ mathbf {x} \ mapsto \ sigma（\ Mathbf {w} \ cdot \ cdot \ cdot \ mathbf {x}）$单调激活$ \ sigma：\ sigma：\ sigma： \ Mathbb {r} \ mapsto \ Mathbb {r} $，相对于$ L_2^2 $ -LOSS，在存在对抗标签噪声的情况下。具体来说，我们将在$（\ MathBf {x}，y）\ in \ Mathbb {r}^d \ times \ times \ mathbb {r} $上给我们从$（\ mathbf {x}，y）\ on a发行$ d $中的标记示例。 }^\ ast \ in \ Mathbb {r}^d $ achieving $ f（\ mathbf {w}^\ ast）= \ epsilon $，其中$ f（\ mathbf {w}）= \ \ m马理bf {e} _ {e} _ {e} _ { （\ Mathbf {x}，y）\ sim d} [（\ sigma（\ Mathbf {w} \ cdot \ mathbf {x}） - y）^2] $。学习者的目标是输出假设矢量$ \ mathbf {w} $，以使$ f（\ m athbb {w}）= c \，\ epsilon $具有很高的可能性，其中$ c> 1 $是通用的常数。作为我们的主要贡献，我们为广泛的分布（包括对数 - 循环分布）和激活功能提供有效的恒定因子近似学习者。具体地说，对于各向同性对数凸出分布的类别，我们获得以下重要的推论：对于逻辑激活，我们获得了第一个多项式时间常数因子近似（即使在高斯分布下）。我们的算法具有样品复杂性$ \ widetilde {o}（d/\ epsilon）$，这在多毛体因子中很紧。对于relu激活，我们给出了一个有效的算法，带有样本复杂性$ \ tilde {o}（d \，\ polylog（1/\ epsilon））$。在我们工作之前，最著名的常数因子近似学习者具有样本复杂性$ \ tilde {\ omega}（d/\ epsilon）$。在这两个设置中，我们的算法很简单，在（正规）$ l_2^2 $ -loss上表现出渐变的表现。我们的算法的正确性取决于我们确定的新结构结果，表明（本质上是基本上的）基础非凸损失的固定点大约是最佳的。
We study the fundamental problem of learning a single neuron, i.e., a function of the form $\mathbf{x}\mapsto\sigma(\mathbf{w}\cdot\mathbf{x})$ for monotone activations $\sigma:\mathbb{R}\mapsto\mathbb{R}$, with respect to the $L_2^2$-loss in the presence of adversarial label noise. Specifically, we are given labeled examples from a distribution $D$ on $(\mathbf{x}, y)\in\mathbb{R}^d \times \mathbb{R}$ such that there exists $\mathbf{w}^\ast\in\mathbb{R}^d$ achieving $F(\mathbf{w}^\ast)=\epsilon$, where $F(\mathbf{w})=\mathbf{E}_{(\mathbf{x},y)\sim D}[(\sigma(\mathbf{w}\cdot \mathbf{x})-y)^2]$. The goal of the learner is to output a hypothesis vector $\mathbf{w}$ such that $F(\mathbb{w})=C\, \epsilon$ with high probability, where $C>1$ is a universal constant. As our main contribution, we give efficient constant-factor approximate learners for a broad class of distributions (including log-concave distributions) and activation functions. Concretely, for the class of isotropic log-concave distributions, we obtain the following important corollaries: For the logistic activation, we obtain the first polynomial-time constant factor approximation (even under the Gaussian distribution). Our algorithm has sample complexity $\widetilde{O}(d/\epsilon)$, which is tight within polylogarithmic factors. For the ReLU activation, we give an efficient algorithm with sample complexity $\tilde{O}(d\, \polylog(1/\epsilon))$. Prior to our work, the best known constant-factor approximate learner had sample complexity $\tilde{\Omega}(d/\epsilon)$. In both of these settings, our algorithms are simple, performing gradient-descent on the (regularized) $L_2^2$-loss. The correctness of our algorithms relies on novel structural results that we establish, showing that (essentially all) stationary points of the underlying non-convex loss are approximately optimal.