An efficient, provably optimal algorithm for the 0-1 loss linear classification problem

Xi He, Max A. Little

Algorithms for solving the linear classification problem have a long history, dating back at least to 1936 with linear discriminant analysis. For linearly separable data, many algo…