Can I read Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noise on EtoBox?

Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noise by Zhang, Chicheng; Li, Yinan is a scholarly article available to read on EtoBox.

What is Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noise about?

We give a computationally-efficient PAC active learning algorithm for $d$-dimensional homogeneous halfspaces that can tolerate Massart noise (Massart and N\'ed\'elec, 2006) and Tsybakov noise (Tsybakov, 2004). Specialized to the $\eta$-Massart noise setting, our algorithm achieves an information-theoretically near-optimal label complexity of $\tilde{O}\left( \frac{d}{(1-2\eta)^2} \mathrm{polylog}(\frac1\epsilon) \right)$ under a wide range of unlabeled data distributions (specifically, the family of "structured distributions" defined in Diakonikolas et al. (2020)). Under the more challenging Tsybakov noise condition, we identify two subfamilies of noise conditions, under which our efficient algorithm provides label complexity guarantees strictly lower than passive learning algorithms.

Author

Zhang, Chicheng; Li, Yinan

Published

2021

Language

EN