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

Given \alpha,\epsilon, we study the time complexity required to improperly learn a halfspace with misclassification error rate of at most (1 \alpha)\,L *_\gamma \epsilon, where L *_\gamma is the optimal \gamma -margin error rate. For \alpha 1/\gamma, polynomial time and sample complexity is achievable using the hinge-loss. An immediate question, which this paper tackles, is what is achievable if \alpha \in (0,1/\gamma) . We derive positive results interpolating between the polynomial time for \alpha 1/\gamma and the exponential time for \alpha 0 . In particular, we show that there are cases in which \alpha o(1/\gamma) but the problem is still solvable in polynomial time.