@inproceedings{
wang2024sample,
title={Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models},
author={Puqian Wang and Nikos Zarifis and Ilias Diakonikolas and Jelena Diakonikolas},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=MN7d0S2i1d}
}
A single-index model (SIM) is a function of the form $\sigma(\mathbf{w}^{\ast} \cdot \mathbf{x})$, where
$\sigma: \mathbb{R} \to \mathbb{R}$ is a known link function and $\mathbf{w}^{\ast}$ is a hidden unit vector. 
We study the task of learning SIMs in the agnostic (a.k.a. adversarial label noise) model 
with respect to the $L^2_2$-loss under the Gaussian distribution. 
Our main result is a sample and computationally efficient agnostic proper learner 
that attains $L^2_2$-error of $O(\mathrm{OPT})+\epsilon$, where $\mathrm{OPT}$ is the optimal loss. The sample complexity of our algorithm is 
$\tilde{O}(d^{\lceil k^{\ast}/2\rceil}+d/\epsilon)$, where 
$k^{\ast}$ is the information-exponent of $\sigma$ 
corresponding to the degree of its first non-zero Hermite coefficient. 
This sample bound nearly matches known CSQ lower bounds, even in the realizable setting. 
Prior algorithmic work in this setting had focused 
on learning in the realizable case or in the presence 
of semi-random noise. Prior computationally efficient robust learners required 
significantly stronger assumptions on the link function.
Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models
Puqian Wang Nikos Zarifis Ilias Diakonikolas Jelena Diakonikolas