Abstract

Given we study the time complexity required to improperly learn a halfspace with misclassification error rate of at most , where is the optimal -margin error rate. For , polynomial time and sample complexity is achievable using the hinge-loss. For Shalev-Shwartz et al. [2011] showed that poly time is impossible, while learning is possible in time exp An immediate question, which this paper tackles, is what is achievable if . We derive positive results interpolating between the polynomial time for and the exponential time for = 0. In particular, we show that there are cases in which 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.