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

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