Learning Halfspaces with the Zero-One Loss: Time-Accuracy Tradeoffs

Abstract

Given ,, we study the time complexity required to improperly learn a halfspace with misclassification error rate of at most (1+)\,L^*_ + , where L^*_ is the optimal -margin error rate. For = 1/, polynomial time and sample complexity is achievable using the hinge-loss. For = 0, ShalevShSr11 showed that (1/) time is impossible, while learning is possible in time (O(1/)). An immediate question, which this paper tackles, is what is achievable if (0,1/). We derive positive results interpolating between the polynomial time for = 1/ and the exponential time for =0. In particular, we show that there are cases in which = o(1/) but the problem is still solvable in polynomial time. Our results naturally extend to the adversarial online learning model and to the PAC learning with malicious noise model.

Tasks

Reproductions