Proceedings

Learning Linear and Kernel Predictors with the 0-1 Loss Function

Shai Shalev-Shwartz, Ohad Shamir, Karthik Sridharan

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 2740-2744.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-456

Abstract

Some of the most successful machine learning algorithms, such as Support Vector Machines, are based on learning linear and kernel predictors with respect to a convex loss function, such as the hinge loss. For classification purposes, a more natural loss function is the 0-1 loss. However, using it leads to a non-convex problem for which there is no known efficient algorithm. In this paper, we describe and analyze a new algorithm for learning linear or kernel predictors with respect to the 0-1 loss function. The algorithm is parameterized by L, which quantifies the effective width around the decision boundary in which the predictor may be uncertain. We show that without any distributional assumptions, and for any fixed $L$, the algorithm runs in polynomial time, and learns a classifier which is worse than the optimal such classifier by at most ε. We also prove a hardness result, showing that under a certain cryptographic assumption, no algorithm can learn such classifiers in time polynomial in L.

Shai Shalev-Shwartz, Ohad Shamir, and Karthik Sridharan. 2011. Learning Linear and Kernel Predictors with the 0-1 Loss Function. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 2740–2744. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-456
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards