Minimax Classification with 0-1 Loss and Performance Guarantees
This addresses the challenge of robust classification with theoretical guarantees for practitioners, though it appears incremental as it builds on minimax principles without a paradigm shift.
The paper tackles the problem of supervised classification with 0-1 loss by introducing minimax risk classifiers (MRCs) that avoid reliance on surrogate losses and specific rule families, achieving efficient learning and generalization with performance guarantees as tight bounds for expected loss. It demonstrates competitive classification performance on benchmark datasets.
Supervised classification techniques use training samples to find classification rules with small expected 0-1 loss. Conventional methods achieve efficient learning and out-of-sample generalization by minimizing surrogate losses over specific families of rules. This paper presents minimax risk classifiers (MRCs) that do not rely on a choice of surrogate loss and family of rules. MRCs achieve efficient learning and out-of-sample generalization by minimizing worst-case expected 0-1 loss w.r.t. uncertainty sets that are defined by linear constraints and include the true underlying distribution. In addition, MRCs' learning stage provides performance guarantees as lower and upper tight bounds for expected 0-1 loss. We also present MRCs' finite-sample generalization bounds in terms of training size and smallest minimax risk, and show their competitive classification performance w.r.t. state-of-the-art techniques using benchmark datasets.