@online{Anagnostides_arXiv2010.09106,
TITLE = {Robust Learning under Strong Noise via {SQs}},
AUTHOR = {Anagnostides, Ioannis and Gouleakis, Themis and Marashian, Ali},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2010.09106},
EPRINT = {2010.09106},
EPRINTTYPE = {arXiv},
YEAR = {2020},
ABSTRACT = {This work provides several new insights on the robustness of Kearns'<br>statistical query framework against challenging label-noise models. First, we<br>build on a recent result by \cite{DBLP:journals/corr/abs-2006-04787} that<br>showed noise tolerance of distribution-independently evolvable concept classes<br>under Massart noise. Specifically, we extend their characterization to more<br>general noise models, including the Tsybakov model which considerably<br>generalizes the Massart condition by allowing the flipping probability to be<br>arbitrarily close to $\frac{1}{2}$ for a subset of the domain. As a corollary,<br>we employ an evolutionary algorithm by \cite{DBLP:conf/colt/KanadeVV10} to<br>obtain the first polynomial time algorithm with arbitrarily small excess error<br>for learning linear threshold functions over any spherically symmetric<br>distribution in the presence of spherically symmetric Tsybakov noise. Moreover,<br>we posit access to a stronger oracle, in which for every labeled example we<br>additionally obtain its flipping probability. In this model, we show that every<br>SQ learnable class admits an efficient learning algorithm with OPT + $\epsilon$<br>misclassification error for a broad class of noise models. This setting<br>substantially generalizes the widely-studied problem of classification under<br>RCN with known noise rate, and corresponds to a non-convex optimization problem<br>even when the noise function -- i.e. the flipping probabilities of all points<br>-- is known in advance.<br>},
}