Help Privacy Policy Disclaimer
  Advanced SearchBrowse





Robust Learning under Strong Noise via SQs


Gouleakis,  Themis
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Preprint), 511KB

Supplementary Material (public)
There is no public supplementary material available

Anagnostides, I., Gouleakis, T., & Marashian, A. (2020). Robust Learning under Strong Noise via SQs. Retrieved from https://arxiv.org/abs/2010.09106.

Cite as: https://hdl.handle.net/21.11116/0000-0007-8B5D-5
This work provides several new insights on the robustness of Kearns'
statistical query framework against challenging label-noise models. First, we
build on a recent result by \cite{DBLP:journals/corr/abs-2006-04787} that
showed noise tolerance of distribution-independently evolvable concept classes
under Massart noise. Specifically, we extend their characterization to more
general noise models, including the Tsybakov model which considerably
generalizes the Massart condition by allowing the flipping probability to be
arbitrarily close to $\frac{1}{2}$ for a subset of the domain. As a corollary,
we employ an evolutionary algorithm by \cite{DBLP:conf/colt/KanadeVV10} to
obtain the first polynomial time algorithm with arbitrarily small excess error
for learning linear threshold functions over any spherically symmetric
distribution in the presence of spherically symmetric Tsybakov noise. Moreover,
we posit access to a stronger oracle, in which for every labeled example we
additionally obtain its flipping probability. In this model, we show that every
SQ learnable class admits an efficient learning algorithm with OPT + $\epsilon$
misclassification error for a broad class of noise models. This setting
substantially generalizes the widely-studied problem of classification under
RCN with known noise rate, and corresponds to a non-convex optimization problem
even when the noise function -- i.e. the flipping probabilities of all points
-- is known in advance.