Learning Halfspaces with Tsybakov Noise

Understand

We study the efficient PAC learnability of halfspaces in the presence of Tsybakov noise.

• In the Tsybakov noise model, each label is independently flipped with some probability which is controlled by an adversary.
• This noise model significantly generalizes the Massart noise model, by allowing the flipping probabilities to be arbitrarily close to $1/2$ for a fraction of the samples.
• Our main result is the first non-trivial PAC learning algorithm for this problem under a broad family of structured distributions -- satisfying certain concentration and (anti-)anti-concentration properties -- including log-concave distributions.