mlsanityData to 14 Oct 2026

Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noise

arXiv 2411.06697 ↗First posted 11 Nov 2024cs.LG cs.DS math.OCcited by 2

Not on the map. Why?

Abstract (arXiv)

We study the problem of learning a single neuron with respect to the L22-loss in the presence of adversarial distribution shifts, where the labels can be arbitrary, and the goal is to find a ``best-fit'' function. More precisely, given training samples from a reference distribution p0, the goal is to approximate the vector w^* which minimizes the squared loss with respect to the worst-case distribution that is close in chi2-divergence to p0. We design a computationally efficient algorithm that recovers a vector hatw satisfying mathbbEp^* (σ(hatw · x) - y)2 ≤ C , mathbbEp^* (σ(w^* · x) - y)2 + ε, where C>1 is a dimension-independent constant and (w^*, p^*) is the witness attaining the min-max risk minw~:~|w| ≤ W maxp mathbbE(x, y) ~ p (σ(w · x) - y)2 - nu chi2(p, p0). Our algorithm follows a primal-dual framework and is designed by directly bounding the risk with respect to the original, nonconvex L22 loss. From an optimization standpoint, our work opens new avenues for the design of primal-dual algorithms under structured nonconvexity.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 47 of its 81 references that are in the map. First posted on arXiv 11 Nov 2024.

Builds on

47 of 81 references.

References · 47

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,364
  2. 2021Just Train Twice: Improving Group Robustness without Training Group Informationcited by 523
  3. 2018A Survey on Deep Transfer Learningcited by 419
  4. 2018Fairness Without Demographics in Repeated Loss Minimizationcited by 364
  5. 2017Certifying Some Distributional Robustness with Principled Adversarial Trainingcited by 337
  6. 2018Learning Models with Uniform Performance via Distributionally Robust Optimizationcited by 335
  7. 2016Statistics of Robust Optimization: A Generalized Empirical Likelihood Approachcited by 183
  8. 2019Wasserstein Distributionally Robust Optimization: Theory and Applications in Machine Learningcited by 170
  9. 2016Variance-based regularization with convex objectivescited by 155
  10. 2019Distributionally Robust Language Modelingcited by 143
  11. 2016The Landscape of Empirical Risk for Non-convex Lossescited by 86
  12. 2019Distributionally Robust Optimization: A Reviewcited by 76
35 more
  1. 2019Distributionally Robust Optimization and Generalization in Kernel Methodscited by 73
  2. 2020Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginalscited by 57
  3. 2021DORO: Distributional and Outlier Robust Optimizationcited by 56
  4. 2017Learning ReLUs via Gradient Descentcited by 54
  5. 2021The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginalscited by 52
  6. 2020Learning a Single Neuron with Gradient Methodscited by 50
  7. 2020Statistical-Query Lower Bounds via Functional Gradientscited by 50
  8. 2020Agnostic Learning of a Single Neuron with Gradient Descentcited by 46
  9. 2021Distributionally Robust Learningcited by 44
  10. 2020An Online Method for A Class of Distributionally Robust Optimization with Non-Convex Objectivescited by 42
  11. 2023A Finite Sample Complexity Bound for Distributionally Robust Q-learningcited by 36
  12. 2020Approximation Schemes for ReLU Regressioncited by 34
  13. 2022Doubly Robust Distributionally Robust Off-Policy Evaluation and Learningcited by 34
  14. 2013Understanding Alternating Minimization for Matrix Completioncited by 32
  15. 2019Time/Accuracy Tradeoffs for Learning a ReLU with respect to Gaussian Marginalscited by 32
  16. 2023Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginalscited by 31
  17. 2020Class-Weighted Classification: Trade-offs and Robust Approachescited by 30
  18. 2017Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applicationscited by 29
  19. 2017The Approximate Duality Gap Technique: A Unified Theory of First-Order Methodscited by 27
  20. 2021Statistical Analysis of Wasserstein Distributionally Robust Estimatorscited by 27
  21. 2024Distributionally Robust Optimization and Robust Statisticscited by 24
  22. 2022Learning a Single Neuron with Adversarial Label Noise via Gradient Descentcited by 20
  23. 2023Agnostically Learning Single-Index Models using Omnipredictorscited by 16
  24. 2020Risk-Aware Planning and Assignment for Ground Vehicles using Uncertain Perception from Aerial Vehiclescited by 12
  25. 2022Agnostic Learning of General ReLU Activation Using Gradient Descentcited by 12
  26. 2023Robustly Learning a Single Neuron via Sharpnesscited by 12
  27. 2024Robustly Learning Single-Index Models via Alignment Sharpnesscited by 11
  28. 2019Fitting ReLUs via SGD and Quantized SGDcited by 10
  29. 2021Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sumscited by 10
  30. 2021ReLU Regression with Massart Noisecited by 10
  31. 2021Coordinate Linear Variance Reduction for Generalized Linear Programmingcited by 10
  32. 2020Kernel Distributionally Robust Optimizationcited by 6
  33. 2022On the Complexity of a Practical Primal-Dual Coordinate Methodcited by 6
  34. 2015Learning Halfspaces and Neural Networks with Random Initializationcited by 4
  35. 2022A Fast Scale-Invariant Algorithm for Non-negative Least Squares with Non-negative Datacited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 1.

2 papers.

  1. 2025Linear Regression under Missing or Corrupted Coordinatescited by 1
  2. 2026Robust Learning of a Group DRO Neuroncited by 0