# Iterative thresholding for non-linear learning in the strong varepsilon-contamination model

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 29 references that are in the map.
- First posted on arXiv 5 Sep 2024.

## Builds on (most cited first, 18 of 18)

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Sever: A Robust Meta-Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1803.02815/) (2018)
- [Tilted Empirical Risk Minimization](https://mlsanity.com/paper/2007.01162/) (2020)
- [The Landscape of Empirical Risk for Non-convex Losses](https://mlsanity.com/paper/1607.06534/) (2016)
- [Robust Estimation via Robust Gradient Estimation](https://mlsanity.com/paper/1802.06485/) (2018)
- [Learning One-hidden-layer ReLU Networks via Gradient Descent](https://mlsanity.com/paper/1806.07808/) (2018)
- [Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers](https://mlsanity.com/paper/1703.04940/) (2017)
- [Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection](https://mlsanity.com/paper/1906.11366/) (2019)
- [Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minima](https://mlsanity.com/paper/1712.00779/) (2017)
- [Robust Regression via Hard Thresholding](https://mlsanity.com/paper/1506.02428/) (2015)
- [Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packing](https://mlsanity.com/paper/2006.06980/) (2020)
- [Faster Algorithms for High-Dimensional Robust Covariance Estimation](https://mlsanity.com/paper/1906.04661/) (2019)
- [Robust Regression via Mutivariate Regression Depth](https://mlsanity.com/paper/1702.04656/) (2017)
- [High-Dimensional Robust Mean Estimation via Gradient Descent](https://mlsanity.com/paper/2005.01378/) (2020)
- [Globally-convergent Iteratively Reweighted Least Squares for Robust Regression Problems](https://mlsanity.com/paper/2006.14211/) (2020)
- [A Unified Approach to Robust Mean Estimation](https://mlsanity.com/paper/1907.00927/) (2019)
- [Outlier Robust Adversarial Training](https://mlsanity.com/paper/2309.05145/) (2023)
- [Robust Risk Minimization for Statistical Learning](https://mlsanity.com/paper/1910.01544/) (2019)

## Abstract (arXiv)

We derive approximation bounds for learning single neuron models using thresholded gradient descent when both the labels and the covariates are possibly corrupted adversarially. We assume the data follows the model y = σ(w* · x) + xi, where σ is a nonlinear activation function, the noise xi is Gaussian, and the covariate vector x is sampled from a sub-Gaussian distribution. We study sigmoidal, leaky-ReLU, and ReLU activation functions and derive a O(nu√εlog(1/ε)) approximation bound in ℓ2-norm, with sample complexity O(d/ε) and failure probability e-Omega(d). We also study the linear regression problem, where σ(x) = x. We derive a O(nuεlog(1/ε)) approximation bound, improving upon the previous O(nu) approximation bounds for the gradient-descent based iterative thresholding algorithms of Bhatia et al. (NeurIPS 2015) and Shen and Sanghavi (ICML 2019). Our algorithm has a O(textrmpolylog(N,d)log(R/ε)) runtime complexity when |w*|2 ≤ R, improving upon the O(polylog(N,d)/ε2) runtime complexity of Awasthi et al. (NeurIPS 2022).