# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Robust Learning under Strong Noise via SQs

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:2010.09106.pdf

(Preprint), 511KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

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

##### Abstract

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.

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.