Given a, e, we study the time complexity required to improperly learn a halfs-pace with misclassification error rate of at most (1 + a) L _γ~* + ∈, where L _γ~* is the optimal 7-margin error rate. For α = 1/γ, polynomial time and sample complexity is achievable using the hinge-loss. For α = 0, Shalev-Shwartz et al. [2011] showed that poly(l/γ) time is impossible, while learning is possible in time exp(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 α = 0(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.
展开▼
