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

Abstract

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 = σ(\mathbf{w}^{*} \cdot \mathbf{x}) + ξ,$ where $σ$ is a nonlinear activation function, the noise $ξ$ is Gaussian, and the covariate vector $\mathbf{x}$ is sampled from a sub-Gaussian distribution. We study sigmoidal, leaky-ReLU, and ReLU activation functions and derive a $O(ν\sqrt{ε\log(1/ε)})$ approximation bound in $\ell_{2}$-norm, with sample complexity $O(d/ε)$ and failure probability $e^{-Ω(d)}$. We also study the linear regression problem, where $σ(\mathbf{x}) = \mathbf{x}$. We derive a $O(νε\log(1/ε))$ approximation bound, improving upon the previous $O(ν)$ 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(\textrm{polylog}(N,d)\log(R/ε))$ runtime complexity when $\|\mathbf{w}^{*}\|_2 \leq R$, improving upon the $O(\text{polylog}(N,d)/ε^2)$ runtime complexity of Awasthi et al. (NeurIPS 2022).