Minimax Classification with 0-1 Loss and Performance Guarantees

Supervised classification techniques use training samples to find classification rules with small expected 0-1 loss. Conventional methods ac hieve efficient learning and out-of-sample generalization by minimizing surrog ate losses over specific families of rules. This paper presents minimax risk classifi ers (MRCs) that do not rely on a choice of surrogate loss and family of rules. MRCs ac hieve efficient learning and out-of-sample generalization by minimizing w orst-case expected 0-1 loss w.r.t.