Research map / Learning theory and algorithms / Sample complexity

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

NeurIPS 2024 · Learning theory and algorithms › Sample complexity · approach: Learning halfspaces under noise · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives the first polynomial-sample, polynomial-time primal-dual algorithm for learning a single neuron (monotone unbounded convex activations such as ReLU/SoftPlus) under chi-squared distributionally robust agnostic label noise, with a dimension-independent constant-factor guarantee.

Problem

Learning a single neuron under the L2^2 loss when labels are adversarial and the reference distribution can be adversarially shifted within a chi-squared ambiguity set (distributionally robust, agnostic setting).

Approach

A primal-dual method with extrapolation that directly bounds the nonconvex square-loss DRO risk (not a convex surrogate), using chi-squared regularization to get a closed form for the worst-case distribution, and a sharpness property transferred from the target distribution to the empirical worst-case distribution.

Key results

• Algorithm recovers w_hat with ||w_hat - w*||^2 <= C*OPT + epsilon after O~(d log(1/epsilon)) iterations, with sample size N = O~(d/epsilon^2) per the informal theorem.
• Under margin and subexponential assumptions, the output satisfies E_{p*}[l(w_k)] <= (2 + 20 B beta^2 C_3^2) OPT + 10 beta^2 B epsilon and a DRO risk gap of C_4 (OPT + epsilon).

Surprising findings

• The DRO gap function is not nonnegative in general (counterexample with ReLU and nu=0), so an explicit lower bound on the gap is required.

Limitations

• Requires margin and subexponential concentration assumptions on the target distribution and bounded covariates/labels.
• Requires nu sufficiently large so chi-squared distance to the reference is small; analysis tied to chi-squared divergence and convex activations.
• Only single neuron; does not extend directly to multi-neuron networks or unknown activations.

Experimental setup

Metrics: squared loss parameter error

Builds on: Diakonikolas et al. agnostic learning of single neurons primal-dual gap analysis with acceleration Bregman divergence

Closest papers by meaning

• Robustly Learning a Single Neuron via Sharpness (ICML 2023 · similarity 0.92)
• Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models (NeurIPS 2024 · similarity 0.87)
• Tolerant Algorithms for Learning with Arbitrary Covariate Shift (NeurIPS 2024 · similarity 0.86)
• $\epsilon$-Softmax: Approximating One-Hot Vectors for Mitigating Label Noise (NeurIPS 2024 · similarity 0.86)
• Kernel Learning with Adversarial Features: Numerical Efficiency and Adaptive Regularization (NeurIPS 2025 · similarity 0.86)
• Robustly Learning Monotone Single-Index Models (NeurIPS 2025 · similarity 0.86)