2022/06/17 by Ilias Diakonikolas, Vasilis Kontonis, Diakonikolas, Ilias +5 · 1 citation
Computer Science · #Adversarial Robustness in Machine Learning #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Machine Learning and Data Classification #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2206.08918
openalex publication_date 2022/06/17 · openalex created_date 2022/06/22 · openalex updated_date 2026/07/28
We study the fundamental problem of learning a single neuron, i.e., a function of the form x↦σ(w\cdotx) for monotone activations σ:ℝ↦ℝ, with respect to the L22-loss in the presence of adversarial label noise. Specifically, we are given labeled examples from a distribution D on (x, y)∈ℝd × ℝ such that there exists w^∗∈ℝd achieving F(w^∗)=ε, where F(w)=E(x,y)∼ D[(σ(w⋅ x)-y)2]. The goal of the learner is to output a hypothesis vector w such that F(\mathbbw)=C ε 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 \widetildeO(d/ε), which is tight within polylogarithmic factors. For the ReLU activation, we give an efficient algorithm with sample complexity O(d \polylog(1/ε)). Prior to our work, the best known constant-factor approximate learner had sample complexity Ω(d/ε). In both of these settings, our algorithms are simple, performing gradient-descent on the (regularized) L22-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.