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

arXiv: https://arxiv.org/abs/2411.06697 · HTML: https://mlsanity.com/paper/2411.06697/

## 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 (most cited first, 30 of 47)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Just Train Twice: Improving Group Robustness without Training Group Information](https://mlsanity.com/paper/2107.09044/) (2021)
- [A Survey on Deep Transfer Learning](https://mlsanity.com/paper/1808.01974/) (2018)
- [Fairness Without Demographics in Repeated Loss Minimization](https://mlsanity.com/paper/1806.08010/) (2018)
- [Certifying Some Distributional Robustness with Principled Adversarial Training](https://mlsanity.com/paper/1710.10571/) (2017)
- [Learning Models with Uniform Performance via Distributionally Robust Optimization](https://mlsanity.com/paper/1810.08750/) (2018)
- [Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach](https://mlsanity.com/paper/1610.03425/) (2016)
- [Wasserstein Distributionally Robust Optimization: Theory and Applications in Machine Learning](https://mlsanity.com/paper/1908.08729/) (2019)
- [Variance-based regularization with convex objectives](https://mlsanity.com/paper/1610.02581/) (2016)
- [Distributionally Robust Language Modeling](https://mlsanity.com/paper/1909.02060/) (2019)
- [The Landscape of Empirical Risk for Non-convex Losses](https://mlsanity.com/paper/1607.06534/) (2016)
- [Distributionally Robust Optimization: A Review](https://mlsanity.com/paper/1908.05659/) (2019)
- [Distributionally Robust Optimization and Generalization in Kernel Methods](https://mlsanity.com/paper/1905.10943/) (2019)
- [Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals](https://mlsanity.com/paper/2006.16200/) (2020)
- [DORO: Distributional and Outlier Robust Optimization](https://mlsanity.com/paper/2106.06142/) (2021)
- [Learning ReLUs via Gradient Descent](https://mlsanity.com/paper/1705.04591/) (2017)
- [The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals](https://mlsanity.com/paper/2102.04401/) (2021)
- [Learning a Single Neuron with Gradient Methods](https://mlsanity.com/paper/2001.05205/) (2020)
- [Statistical-Query Lower Bounds via Functional Gradients](https://mlsanity.com/paper/2006.15812/) (2020)
- [Agnostic Learning of a Single Neuron with Gradient Descent](https://mlsanity.com/paper/2005.14426/) (2020)
- [Distributionally Robust Learning](https://mlsanity.com/paper/2108.08993/) (2021)
- [An Online Method for A Class of Distributionally Robust Optimization with Non-Convex Objectives](https://mlsanity.com/paper/2006.10138/) (2020)
- [A Finite Sample Complexity Bound for Distributionally Robust Q-learning](https://mlsanity.com/paper/2302.13203/) (2023)
- [Approximation Schemes for ReLU Regression](https://mlsanity.com/paper/2005.12844/) (2020)
- [Doubly Robust Distributionally Robust Off-Policy Evaluation and Learning](https://mlsanity.com/paper/2202.09667/) (2022)
- [Understanding Alternating Minimization for Matrix Completion](https://mlsanity.com/paper/1312.0925/) (2013)
- [Time/Accuracy Tradeoffs for Learning a ReLU with respect to Gaussian Marginals](https://mlsanity.com/paper/1911.01462/) (2019)
- [Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals](https://mlsanity.com/paper/2302.06512/) (2023)
- [Class-Weighted Classification: Trade-offs and Robust Approaches](https://mlsanity.com/paper/2005.12914/) (2020)
- [Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applications](https://mlsanity.com/paper/1706.04957/) (2017)

## Built on by (most cited first, 2 of 2)

- [Linear Regression under Missing or Corrupted Coordinates](https://mlsanity.com/paper/2509.19242/) (2025)
- [Robust Learning of a Group DRO Neuron](https://mlsanity.com/paper/2601.18115/) (2026)

## 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.