Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models

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

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-11
Main Authors: Wang, Puqian, Zarifis, Nikos, Diakonikolas, Ilias, Diakonikolas, Jelena
Format: Article
Language:English
Subjects:
Algorithms
Computational efficiency
Learning
Lower bounds
Normal distribution
Random noise
Robustness
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422