Theory and algorithms for learning with rejection in binary classification

Corinna Cortes, Giulia DeSalvo, Mehryar Mohri

Research output: Contribution to journalArticlepeer-review


We introduce a novel framework for classification with a rejection option that consists of simultaneously learning two functions: a classifier along with a rejection function. We present a full theoretical analysis of this framework including new data-dependent learning bounds in terms of the Rademacher complexities of the classifier and rejection families as well as consistency and calibration results. These theoretical guarantees guide us in designing new algorithms that can exploit different kernel-based hypothesis sets for the classifier and rejection functions. We compare our general framework with the special case of confidence-based rejection for which we also devise alternative loss functions and algorithms. We report the results of several experiments showing that our kernel-based algorithms can yield a notable improvement over the best existing confidence-based rejection algorithm.

Original languageEnglish (US)
JournalAnnals of Mathematics and Artificial Intelligence
StateAccepted/In press - 2023


  • Abstention
  • Confidence-based models
  • Kernels
  • Rejection

ASJC Scopus subject areas

  • Applied Mathematics
  • Artificial Intelligence


Dive into the research topics of 'Theory and algorithms for learning with rejection in binary classification'. Together they form a unique fingerprint.

Cite this