  We consider the problem of binary classification with abstention in the
relatively less studied \emph{bounded-rate} setting. We begin by obtaining a
characterization of the Bayes optimal classifier for an arbitrary input-label
distribution $P_{XY}$. Our result generalizes and provides an alternative proof
for the result first obtained by \cite{chow1957optimum}, and then re-derived by
\citet{denis2015consistency}, under a continuity assumption on $P_{XY}$. We
then propose a plug-in classifier that employs unlabeled samples to decide the
region of abstention and derive an upper-bound on the excess risk of our
classifier under standard \emph{H\"older smoothness} and \emph{margin}
assumptions. Unlike the plug-in rule of \citet{denis2015consistency}, our
constructed classifier satisfies the abstention constraint with high
probability and can also deal with discontinuities in the empirical cdf. We
also derive lower-bounds that demonstrate the minimax near-optimality of our
proposed algorithm. To address the excessive complexity of the plug-in
classifier in high dimensions, we propose a computationally efficient algorithm
that builds upon prior work on convex loss surrogates, and obtain bounds on its
excess risk in the \emph{realizable} case. We empirically compare the
performance of the proposed algorithm with a baseline on a number of UCI
benchmark datasets.

Machine Learning;Machine Learning