Review for NeurIPS paper: Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Evolvability

In this work, a vastly simpler proper halfspace learning algorithm is proposed, as well as algorithms for learning generalized linear models under Massart noise. These algorithms can only guarantee accuracy up to the (maximum) noise rate. This work also presents a connection between learning under Massart noise and (correlational) statistical query algorithms/evolvability, and shows that no distribution-independent algorithm that makes only a polynomial number of queries can match the error rate of the optimal halfspace (which may be lower than the noise rate). Finally, some experiments are presented, demonstrating that different (Massart-style) noise rates on different populations can lead standard classifiers to produce different error rates across populations, but that the algorithm presented here (along with the uninterpretable random forest) is resilient to this effect.