Fast Agnostic Learners in the Plane

Talya Eden, Ludmila Glinskih, Sofya Raskhodnikova

We investigate the computational efficiency of agnostic learning for several fundamental geometric concept classes in the plane. While the sample complexity of agnostic learning is…