The Power of Localization for Efficiently Learning Linear Separators with Noise

Pranjal Awasthi, Maria Florina Balcan, Philip M. Long

We introduce a new approach for designing computationally efficient learning algorithms that are tolerant to noise, and demonstrate its effectiveness by designing algorithms with i…