Efficient and Noise-Tolerant PAC Learning of Multiclass Linear Classifiers

Noise-tolerant PAC learning of linear models has long been a central problem in machine learning. In this paper, we study the multiclass linear classfiers $\{h_w:x\mapsto \arg {\max }_{y\in [k]}{w}_y\cdot x,x\in {\mathbb{R}}^d,w\in {\mathbb{R}}^{kd}\}$ under the challenging nasty noise. We propose the first computationally-efficient algorithm under the assumption that the marginal distribution is a mixture of bounded variance distributions and the uncorrupted data sets satisfy a margin condition. Our algorithm consists of two main ingredients: a convex optimization program that prunes corrupted samples by bounding the pairwise squared distance, and a standard multiclass hinge loss minimization. We provide a multiclass gradient analysis and show that after the pruning, the hinge loss minimization naturally enjoys a strong robustness. Specially, we establish a deterministic condition that for any corrupted sample surviving the pruning, there exists a close-by reference point that enjoys the margin condition like a clean sample. As a result, we show that efficient PAC learning is possible with a sample complexity of $\tilde{O}(k^{2}d)$, where $\tilde{O}$ hides logarithmic terms, for the class of multiclass linear classifiers under a significant amount of nasty noise.