Learning Halfspaces with the Zero-One Loss: Time-Accuracy Tradeoffs Aharon Birnbaum and Shai Shalev-Shwartz School of Computer Science and Engineering The Hebrew University Jerusalem, Israel

Mar-14-2024, 09:50:06 GMT–Neural Information Processing Systems 

For α = 1/γ, polynomial time and sample complexity is achievable using the hinge-loss.