# Rejection via Learning Density Ratios

Alexander Soen$\diamond$, † Hisham Husain$\diamond$ Philip Schulz$\diamond$ Vu
Nguyen$\diamond$
Amazon$\diamond$ Australian National University†

###### Abstract

Classification with rejection emerges as a learning paradigm which allows
models to abstain from making predictions. The predominant approach is to
alter the supervised learning pipeline by augmenting typical loss functions,
letting model rejection incur a lower loss than an incorrect prediction.
Instead, we propose a different distributional perspective, where we seek to
find an idealized data distribution which maximizes a pretrained model’s
performance. This can be formalized via the optimization of a loss’s risk with
a $\varphi$-divergence regularization term. Through this idealized
distribution, a rejection decision can be made by utilizing the density ratio
between this distribution and the data distribution. We focus on the setting
where our $\varphi$-divergences are specified by the family of
$\alpha$-divergence. Our framework is tested empirically over clean and noisy
datasets.

##  1 Introduction

Forcing Machine Learning (ML) models to always make a prediction can lead to
costly consequences. Indeed, in real-world domains such as automated driving,
product inspection, and medical diagnosis, inaccurate prediction can cause
significant real-world harm [16, 26, 44, 41]. To deal with such a dilemma,
selective prediction and classification with rejection were proposed to modify
the standard supervised learning setting [15, 17, 58]. The idea is to allow
for a model to explicitly reject making a prediction whenever the underlying
prediction would be either inaccurate and / or uncertain.

In classification, a _confidence-based_ approach can be utilized, where a
classifier is trained to output a “margin” which is used as a confidence score
for rejection [7, 28, 57, 47, 44]. Given a threshold value, the model rejects
whenever this confidence score is lower than the threshold value. A key
component of these confidence-based approaches is that they rely on providing
good class probability estimates $\Pr(\mathsf{Y}\mid\mathsf{X}=x)$ [48],
_i.e_., being calibrated [57, 44]. Some approaches avoid explicit estimation
of probabilities, however, these are usually restricted to binary
classification [7, 28, 38].

Another _classification-rejection_ approach aim to simultaneously train a
prediction and rejection model in tandem [16, 17, 44]. These approaches are
theoretically driven by the construction of surrogate loss functions, but in
the multiclass classification case many of these loss functions have been
shown to not be suitable [44]. For the multiclass classification setting, one
approach connects classification with rejection to cost-sensitive
classification [14]. In practice, these classification-rejection approaches
require models to be trained from scratch using their specific loss function
and architecture — if there is an existing classifier for the dataset, it must
be discarded. A recent approach proposes to learn a rejector on top of a
pretrained classifier via surrogate loss functions [39].

In this work, to learn rejectors we shift from a loss function perspective to
a _distributional_ perspective. Given a model and a corresponding loss
function, we find a distribution where the model and loss _performs “best”_
and compare it against the data input distribution to make rejection decisions
(see Fig. 1). As such, the set of rejectors that we propose creates a
rejection decision by considering the _density ratio_ [55] between a “best”
case (idealized) distribution and the data distribution, which can be
thresholded by different values $\tau$ to provide different accuracy vs
rejection percentage trade-offs. To learn these density ratios for rejection,
we consider a risk minimization problem which is regularized by
$\varphi$-divergences [1, 19]. We study a particular type of
$\varphi$-divergences as our regularizer: the family of $\alpha$-divergences
which generalizes the KL-divergence. To this end, one of our core
contributions in this work is providing various methods for constructing and
approximating idealized distributions, in particular those constructed by
$\alpha$-divergences. The idealized distributions that we consider are
connected to adversarial distributions examined in _Distributionally Robust
Optimization_ (DRO) [51] and the distributions learned in _Generalized
Variational Inference_ (GVI) [34]; and, as such, the closed formed solutions
found for our idealized distribution have utility outside of the rejection
setting. Furthermore, when utilizing the KL-divergence and Bayes optimal
models, we recover the well known optimal rejection policies, _i.e_., Chow’s
rule [15, 58]. Our rejectors are then examined empirically by examining the
classification learning setting with calibrated classifiers.

In summary, our contributions are the following:

  * •

We present a new framework for learning with rejection involving the density
ratios of idealized distributions which mirrors the distributions learned in
DRO and GVI;

  * •

We show that rejection policies learned in our framework can theoretically
recover optimal rejection policies, _i.e_., Chow’s rule;

  * •

We derive optimal idealized distributions generated from $\alpha$-divergences;

  * •

We present a set of simplifying assumptions such that our framework can be
utilized in practice and verify this empirically.

$x$Data Distribution $\mathrm{P}$Idealized Distribution $\mathrm{Q}$Reject if
$\rho=\frac{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathrm{d}\mathrm{Q}}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathrm{d}\mathrm{P}}(x)\leq\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}\tau$
Figure 1: We first learn an _idealized distribution_
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathrm{Q}$
which _minimizes_ the loss function of a model. We then compare the
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathrm{Q}$
with the original data distribution
$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathrm{P}$
via calculating the density ratio
$\rho={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathrm{d}\mathrm{Q}}/{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathrm{d}\mathrm{P}}$.
This is then used to define a rejection criteria via threshold value
$\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}\tau$.

#### Notation

Let $\mathcal{X}$ be a domain of inputs and $\mathcal{Y}$ be output targets.
We primarily consider the case where $\mathcal{Y}$ is a finite set of $N$
labels $[N]$, where
$[N]\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\\{0,\ldots,N-1\\}$. We will also
consider output domains $\mathcal{Y}^{\prime}$ which is not necessarily the
same as the output data $\mathcal{Y}$, _e.g_., class probabilities estimates
in the classification setting. We further denote the underlying (usually
unknown) input distribution as $\mathrm{P}_{\rm x,\rm
y}\in\mathcal{D}(\mathcal{X}\times\mathcal{Y})$. The marginals of a joint
distribution are denoted by subscript, _e.g_., $\mathrm{P}_{\rm
y}\in\mathcal{D}(\mathcal{Y})$ for the marginal on the label space. Similarly,
we denote conditional distributions, _e.g_., $\mathrm{P}_{\rm x\mid\rm y}$.
For marginals on $\mathcal{D}(\mathcal{X})$, we make the subscripting of $\rm
x$ implicit with $\mathrm{P}=\mathrm{P}_{\rm x}$. The empirical distributions
of $\mathrm{P}$ are denoted by $\hat{\mathrm{P}}_{N}$, with $N$ denoting the
number of samples used to generate it. Furthermore, denote the Iverson bracket
$\llbracket p\rrbracket=1$ if the predicate $p$ is true and $\llbracket
p\rrbracket=0$ otherwise [35]. The maximum
$[z]_{+}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\max\\{0,z\\}$ is shorthanded.

##  2 Preliminaries

#### Learning with Rejection

We first recall the standard _risk minimization_ setting for learning. Suppose
that we are given a (point-wise) loss function
$\ell\colon\mathcal{Y}\times\mathcal{Y}^{\prime}\rightarrow\mathbb{R}_{\geq
0}$ which measures the level of disagreement between predictions and data.
Given a data distribution $\mathrm{P}_{\rm x,\rm y}$ and a hypothesis set of
models $h\in\mathcal{H}$, we aim to minimize the expected risk w.r.t.
$h\colon\mathcal{X}\rightarrow\mathcal{Y}^{\prime}$,

$\displaystyle\operatorname*{argmin}_{h\in\mathcal{H}}\;\;\mathbb{E}_{\mathrm{P}_{\rm
x,\rm y}}[\ell(\mathsf{Y},h(\mathsf{X}))].$ (1)

One way of viewing learning with rejection is to augment the risk minimization
framework by learning an addition rejection function
$r\colon\mathcal{X}\rightarrow\\{0,1\\}$. This can be formally defined using a
regularization term $c\in\mathbb{R}_{\geq 0}$ which controls the rate of
rejection:

$\displaystyle\operatorname*{argmin}_{(h,r)\in\mathcal{H}\times\mathcal{R}}\;\;\mathbb{E}_{\mathrm{P}_{\rm
x,\rm
y}}[(1-r(\mathsf{X}))\ell(\mathsf{Y},h(\mathsf{X}))]+c\cdot\mathrm{P}[r(\mathsf{X})=1],$
(2)

where $\mathcal{R}$ denotes a hypothesis set of rejection functions.

Suppose that $\mathcal{R}$ is complete (contains all possible rejectors). In
such a case, one can see that setting $c=\infty$ reduces Eq. 2 to standard
risk minimization setting given by Eq. 1. Furthermore, setting $c=0$ will
result in $r$ _always_ rejecting, _i.e_., the case where there is no rejection
cost. Some values of $c\in\mathbb{R}_{\geq 0}$ can be redundant. If the loss
$\ell$ is bounded above by $B$, then any $c>B$ is equivalent to setting $c=B$
— the optimal $r^{\star}$ will be to _never_ reject. In classification, where
$\ell$ is taken to be the zero-one-loss, $c$ is typically restricted to values
in $(0,0.5)$ as otherwise low confidence prediction can be accepted [44] — our
work only considers this case. Ramaswamy et al. [47] explores the
$c\in[0.5,1]$ scenario.

Once minimized, a combined model with rejection can be defined by,

$f(x)=\begin{cases}\circledR&\textrm{if }r(x)=1\\\ h(x)&\textrm{if
}r(x)=0,\end{cases}$ (3)

where $\circledR$ denotes a rejection token $f$ makes to abstain from making a
prediction.

So far, the learning task has been left general. By considering _Class
Probability Estimation_ (CPE) [49], we recover familiar optimal rejection and
classifier pairs.

######  Theorem 2.1 (Optimal CPE Rejection / Chow’s Rule).

Let us consider the binary CPE setting, where $\mathcal{Y}=\\{0,1\\}$,
$\mathcal{Y}^{\prime}=[0,1]$, and $\ell$ be any proper111Properness ensures
that the true class probability is the minimizer of the loss in expectation.
loss function [48] (_e.g_., log loss). Then w.r.t. Eq. 2, the optimal
classifier is given by $h^{\star}(x)=\mathrm{P}(\mathsf{Y}=1\mid\mathsf{X}=x)$
and the optimal rejector is given by
$r^{\star}(x)=\llbracket\mathbb{E}_{\mathsf{Y}\sim{h^{\star}(\mathsf{X}=x)}}[\ell(\mathsf{Y},h^{\star}(x))]\geq
c\rrbracket$.

The theorem can easily be generalized to non-binary cases. We note that
Theorem 2.1 is a generalization of the well known Chow’s rule of
classification with rejection [15, 14]. Indeed, taking $\ell$ to be the zero-
one-loss function, we get
$r^{\star}(x)=\llbracket|2\cdot\mathrm{P}(\mathsf{Y}=1\mid\mathsf{X}=x)-1|\geq
1-c\rrbracket$. One can further clarify this by noticing that
$\Pr[r(\mathsf{X})=1]=\mathbb{E}_{\mathrm{P}}[r(\mathsf{X})]$. In the general
proper loss case, the optimal rejector is thresholding a generalized entropy
function (known as the conditional Bayes risk [48]). This would also
correspond to thresholding the class probabilities
$\mathrm{P}(\mathsf{Y}=y\mid\mathsf{X}=x)$, but with different thresholding
values per class $y\in\mathcal{Y}$ (unless $\ell$ is a symmetric loss
function).

#### Generalized Variational Inference

Generalized Variational Inference (GVI) [34] provides a framework for a
generalized set of entropy regularized risk minimization problem. In
particular, GVI generalizes Bayes’ rule by interpreting the Bayesian posterior
as the solution to a minimization problem [59]. The Bayes’ rule minimization
is given by,

$\operatorname*{argmin}_{\mathrm{Q}\in\mathcal{D}(\Theta)}\;\;\mathbb{E}_{\theta\sim\mathrm{Q}}\left[-\sum_{i=1}^{N}\log
p(z_{i}\mid\theta)\right]+\textsc{KL}(\mathrm{P}\mathrel{\|}\mathrm{Q}),$ (4)

where $\theta\sim\mathrm{Q}$ denotes a set of model parameters with likelihood
function $p(x\mid\theta)$ and $\\{z_{i}\\}$ denotes data. Here,
$\mathrm{P}\in\mathcal{D}(\Theta)$ denotes the prior and the optimal
$\mathrm{Q}^{\star}$ denotes the posterior in Bayes’ rule.

For GVI, we generalize a number of quantities. For instance, the ‘loss’
considered can be altered from the log-likelihood $\log p(z\mid\theta)$ to an
alternative loss function over samples $\\{z_{i}\\}$. The divergence function
$\textsc{KL}(\mathrm{P}\mathrel{\|}\mathrm{Q})$ can also be altered to change
the notion of distributional distance. Furthermore, the set of distributions
being minimized $\mathcal{D}(\Theta)$ can also be altered to, _e.g_., reduce
the computational cost of the minimization problem. One can thus alter Eq. 4
to give the following:

$\operatorname*{argmin}_{\mathrm{Q}\in\mathcal{Q}}\;\;L(\mathrm{Q})+\lambda\cdot
D(\mathrm{P}\mathrel{\|}\mathrm{Q}),$ (5)

where $\lambda>0$ and $L$, $D$, and $\mathcal{Q}$ denote the generalized loss,
divergence, and set of distribution, respectively. Here $\lambda$ seeks to act
as a regularization constant which can be tuned.

In our work, we will consider a GVI problem which changes the loss function
and divergence to define an entropy regularized risk minimization problem. Our
loss function corresponds to the learning setting. For the change in
divergence, we consider $\varphi$-divergence [1, 19], which are otherwise
referred to as $f$-divergences [50] or the Csiszár divergence [18].

######  Definition 2.2.

Let $\varphi\colon\mathbb{R}\to(-\infty,\infty]$ be a convex lower semi-
continuous function with $\varphi(1)=0$ then the corresponding
$\varphi$-divergence over non-negative measures for
${\mathrm{P}},{\mathrm{Q}}$ is defined as:

$D_{\varphi}({\mathrm{P}}\mathrel{\|}{\mathrm{Q}})\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\int_{\mathcal{X}}\varphi\left(\frac{{\mathrm{d}\mathrm{Q}}}{{\mathrm{d}\mathrm{P}}}\right){\mathrm{d}\mathrm{P}},\textrm{\quad
if ${\mathrm{Q}}\ll{\mathrm{P}}$; \quad\quad otherwise,
\quad$D_{\varphi}({\mathrm{P}}\mathrel{\|}{\mathrm{Q}})=+\infty$.}$ (6)

We note that for $\varphi$-divergences, the regularization constant in Eq. 5
can be absorbed into the $\varphi$-divergence generator, _i.e_., $\lambda\cdot
D_{\varphi}(\mathrm{P}\mathrel{\|}\mathrm{Q})=D_{\lambda\cdot\varphi}(\mathrm{P}\mathrel{\|}\mathrm{Q})$.

#### Distributionally Robust Optimization

A related piece of literature, is Distributionally Robust Optimization (DRO)
[51], where the goal is to find a distribution that maximizes (or minimizes)
the expectation of a function from a prescribed uncertainty set. Popular
candidates for these uncertainty sets include all distributions that are a
certain radius away from a fixed distribution by some divergence.
$\varphi$-divergences have been used to define such uncertainty set [8, 22,
36]. Given radius $\varepsilon>0$, define
$B^{\varphi}_{\varepsilon}({\mathrm{P}})\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\left\\{{\mathrm{Q}}\in\mathcal{D}(\mathcal{X}\times\mathcal{Y}):D_{\varphi}({\mathrm{P}}\mathrel{\|}{\mathrm{Q}})<\varepsilon\right\\}$.
Given a point-wise loss function
$\ell\colon\mathcal{Y}\times\mathcal{Y}^{\prime}\rightarrow\mathbb{R}$, DRO
alters risk minimization, as per Eq. 1, to solve the following optimization
problem:

$\min_{h\in\mathcal{H}}\;\max_{\bar{\mathrm{Q}}_{\rm x,\rm y}\in
B_{\varepsilon}(\mathrm{P})}\;\;\mathbb{E}_{\bar{\mathrm{Q}}_{\rm x,\rm
y}}\left[\ell(\mathsf{Y},h(\mathsf{X}))\right].$ (7)

The maximization over $\bar{\mathrm{Q}}$ is typically over the target space
$\mathcal{Y}$. That is,
$\bar{\mathrm{Q}}(x,y)=\mathrm{Q}(y)\cdot\mathrm{P}(x\mid y)$ and the
maximization is adversarial over the marginal label distribution [60]. We note
that by converting the $\varepsilon$-ball constraint into a Lagrange
multiplier, the inner optimization over $\mathrm{Q}$ in Eq. 7 becomes a
optimization problem which mirrors Eq. 5. The connection between GVI and
adversarial robustness has been previously noted [31].

Typically in DRO and related learning settings, the construction of the
adversarial distribution defined by the inner maximization problem is
implicitly solved. For example, when $\varphi$ is twice differentiable, it has
been shown that the inner maximization can be reduced to a variance
regularization expression [22, 21]; whereas other choices of divergences such
as kernel Maximum Mean Discrepancy (MMD) yields kernel regularization [54] and
Integral Probability Metrics (IPM) correspond to general regularizers [30].
Another popular choice is the Wasserstein distance which has shown strong
connections to point-wise adversarial robustness [10, 11, 52].

The aforementioned work, however, seek only to find the value of the inner
maximization in Eq. 7 without considering the form the optimal adversarial
distribution takes.

##  3 Rejection via Idealized Distributions

We propose learning rejection functions
$r\colon\mathcal{X}\rightarrow\\{0,1\\}$ by comparing data distributions
$\mathrm{P}$ to a learned idealized distribution $\mathrm{Q}$ (as per Fig. 1).
An idealized distribution (w.r.t. model $h$) is a distribution which when
taken as data results in low risk (per Eq. 1). $\mathrm{Q}$ are idealized
rather than ‘ideal’ as they do not solely rely on a model’s performance, but
are also regularized by their distance from the data distribution
$\mathrm{P}$. Formally, we define our idealized distribution via a GVI
minimization problem.

######  Definition 3.1.

Given a data distribution $\mathrm{P}_{\rm x,\rm
y}\in\mathcal{D}(\mathcal{X}\times\mathcal{Y})$ and a $\varphi$-divergence, an
_idealized distribution_ $\mathrm{Q}\in\mathcal{D}(\mathcal{X})$ for a fixed
model $h$ and loss $\ell$ is a distribution given by

$\operatorname*{arginf}_{\mathrm{Q}\in\mathcal{D}(\mathcal{X})}\;\;L(\mathrm{Q})+\lambda\cdot
D_{\varphi}(\mathrm{P}\mathrel{\|}\mathrm{Q}),$ (8)

where
$L(\mathrm{Q})\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\mathbb{E}_{\mathrm{Q}}[L^{\prime}(\mathsf{X})]$
and
$L^{\prime}(x)\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\mathbb{E}_{\mathrm{P}_{\rm
y\mid\rm x}}\left[\ell(\mathsf{Y},h(x))\right]$.

Given the objective of Eq. 8, an idealized distribution $\mathrm{Q}$ will have
high mass when $L^{\prime}(x)$ is small and low mass when $L^{\prime}(x)$ is
large. The $\varphi$-divergence regularization term prevents the idealized
distributions from collapsing to a point mass. Indeed, without regularization
the distance from $\mathrm{P}$, idealized distributions would simply be Dirac
deltas at values of $x\in\mathcal{X}$ which minimize $L^{\prime}(x)$.

With an idealized distribution $\mathrm{Q}$, a rejection can be made via the
density ratio [55] w.r.t. $\mathrm{P}$.

######  Definition 3.2.

Given a data distribution $\mathrm{P}$ and an idealized distribution
$\mathrm{Q}\ll\mathrm{P}$, the $\tau$-ratio-rejector w.r.t. $\mathrm{Q}$ is
given by
$r_{\tau}(x)\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\left\llbracket\rho(x)\leq\tau\right\rrbracket$,
where
$\rho(x)\stackrel{{\scriptstyle\mathrm{.}}}{{=}}{\mathrm{d}\mathrm{Q}}/{\mathrm{d}\mathrm{P}}(x)$.

Definition 3.2 aims to reject inputs where the idealized rejection
distribution has lower mass than the original data distribution. Given
Definition 3.1 for idealized distribution, small values of $\rho(x)$
corresponds to regions of the input space $\mathcal{X}$ where having lower
data probability would decrease the expected risk of the model. Note that we
do not reject on regions with high density ratio $\rho$ as $L^{\prime}(x)$
would be necessarily small or the likelihood of occurrence $\mathrm{P}(x)$
would be relatively small. We restrict the value of $\tau$ to $(0,1]$ to
ensure that rejection is focused regions where $L^{\prime}(x)$ is high with
high probability w.r.t. $\mathrm{P}(x)$ — further noting that $\tau=0$ always
rejects.

Although Definitions 3.1 and 3.2 suggests that we should learn distributions
$\mathrm{Q}$ (and $\mathrm{P}$) separately to make our rejection decision, in
practice, we can learn the density ratio
${\mathrm{d}\mathrm{Q}}/{\mathrm{d}\mathrm{P}}$ directly. Indeed, through the
definition of Definition 2.2, we have that equivalent minimization problem:

$\operatorname*{argmin}_{\rho\colon\mathcal{X}\rightarrow\mathbb{R}_{+}}\;\;\mathbb{E}_{\mathrm{P}_{\rm
x,\rm
y}}\left[\rho(\mathsf{X})\cdot\ell(\mathsf{Y},h(\mathsf{X}))+\lambda\cdot\varphi(\rho(\mathsf{X}))\right];\quad\quad\mathrm{s.t.}\quad\mathbb{E}_{\mathrm{P}}\left[\rho(\mathsf{X})\right]=1.$
(9)

Such an equivalence has been utilized in DRO previously [23, Proof of Theorem
1]. Notice that the learning density ratio $\rho$ in Eq. 9 is analogous to the
acceptor $1-r(x)$ in Eq. 2. Indeed, ignoring the normalization constraint
$\mathbb{E}_{\mathrm{P}}\left[\rho(\mathsf{X})\right]=1$, by restricting
$\rho(x)\in\\{0,1\\}$, letting $\lambda=c$, and letting $\varphi(z)=\llbracket
z=0\rrbracket$, the objective function of Eq. 9 can be reduced to:

$\displaystyle\mathbb{E}_{\mathrm{P}_{\rm x,\rm
y}}\left[\rho(\mathsf{X})\cdot\ell(\mathsf{Y},h(\mathsf{X}))\right]+c\cdot\mathrm{P}\left(\rho(\mathsf{X})=0\right).$
(10)

Given the restriction of $\rho$ to binary outputs $\\{0,1\\}$ (and Definition
3.2), we have that $r_{\tau}(x)=1-\rho(x)$. As such, Eq. 10 in this setting is
equivalent to the minimization of $r$ in Eq. 2 (with $\mathcal{R}$ as all
possible functions $\mathcal{X}\rightarrow\\{0,1\\}$). Through the specific
selection of $\varphi$ and restriction of $r$, we have shown that rejection
via idealized distributions generalizes the typical learning with rejection
objective Eq. 2.

By utilizing form of $\varphi$-divergences, we find the form of the idealized
rejection distributions $\mathrm{Q}$ and their corresponding density ratio
$\rho$ used for rejection.

######  Theorem 3.3.

Given Definition 3.1, the optimal density ratio function $\rho$ of Eq. 9 is of
the form,

$\rho^{\varphi}_{\lambda}(x)=(\varphi^{\prime})^{-1}\left(\frac{a(x)-L^{\prime}(x)+b}{\lambda}\right),$
(11)

where $a(x)$ are Lagrange multipliers to ensure non-negativity
$\rho^{\varphi}(\cdot)\geq 0$; and $b$ is a Lagrange multiplier to ensure the
constraint
$\mathbb{E}_{\mathrm{P}}\left[\rho^{\varphi}_{\lambda}(\mathsf{X})\right]=1$
is satisfied. Furthermore, the optimal idealized rejection distribution is
given by:
$\mathrm{Q}^{\varphi}(x)=\mathrm{P}(x)\cdot\rho^{\varphi}_{\lambda}(x)$.

#### Connections to GVI and DRO

The formulation and solutions to the optimization of idealized distributions
has several connections to GVI and DRO. In contrast to the setting of GVI,
Eqs. 4 and 5, the support of the idealized distributions being learned in
Definition 3.1 is w.r.t. inputs $\mathcal{X}$ instead of parameters.
Furthermore, the inner maximization of the DRO optimization problem, Eq. 7,
seeks to solve a similar form of optimization. For idealized distributions,
the maximization is switched to minimization and we consider a distribution
over inputs $\mathcal{X}$ instead of targets $\mathcal{Y}$. Indeed, notice
that the explicit inner optimization of DRO (in Eq. 7) over $\mathrm{Q}$ can
be expressed as the following via the Fan’s minimax Theorem [25, Theorem 2]:

$\sup_{\lambda>0}\;\inf_{\mathrm{Q}_{\lambda}\in\mathcal{D}(\mathcal{X})}\;\;-L(\mathrm{Q}_{\lambda})+\lambda\cdot(D_{\varphi}(\mathrm{Q}_{\lambda}\mathrel{\|}\mathrm{P})-\varepsilon).$
(12)

Notably, the loss $L(\mathrm{Q})$ in Eq. 7 can be simply negated to make the
optimization over $\mathrm{Q}$ in Eq. 12 equivalent to DRO Eq. 8 (noting the
only requirement for Eq. 7 to Eq. 12 is that $L(\mathrm{Q})$ is a linear
functional of $\mathrm{Q}$). This shows that switching the sign of the loss
function changes idealized distributions of Definition 3.1 to DRO adversarial
distributions. Indeed, through the connection between our idealized
distributions and DRO adversarial distributions, the distributions
$\mathrm{Q}^{\varphi}(x)$ will have the same form as the optimal rejection
distributions implicitly learned in DRO.

######  Corollary 3.4.

Suppose $\mathrm{Q}^{\varphi}_{\lambda}$ denotes the optimal idealized
distribution in Theorem 3.3 (switching $L(\mathrm{Q})$ to $-L(\mathrm{Q})$)
for a fixed $\lambda>0$. Further let
$\lambda^{\star}\in\operatorname*{arginf}_{\lambda>0}\left\\{-L(\mathrm{Q}^{\varphi}_{\lambda})+\lambda\cdot(D_{\varphi}(\mathrm{Q}^{\varphi}_{\lambda}\mathrel{\|}\mathrm{P})-\varepsilon)\right\\}$.
Then the optimal adversarial distribution in the inner minimization for DRO
(Eq. 7) is $\mathrm{Q}^{\varphi}_{\lambda^{\star}}$.

As such, the various optimal idealized distributions (w.r.t. Definition 3.1)
for rejection we will present in the sequel can be directly used to obtain the
optimal adversarial distributions for DRO.

##  4 Learning Idealized Distributions

In the following section, we explore optimal closed-form density ratio
rejectors. We first examine the easiest example — the KL-divergence — and then
consider the more general $\alpha$-divergences.

#### KL Divergence

Let us first consider the KL-divergence [2] for constructing density ratio
rejectors.

######  Corollary 4.1.

Let $\varphi(z)=z\log z-z+1$ and $\lambda>0$. The optimal density ratio of
Definition 3.1 is,

$\displaystyle\rho_{\lambda}^{\textsc{KL}}(x)$
$\displaystyle=\frac{1}{Z}\cdot\exp\left(\frac{-L^{\prime}(x)}{\lambda}\right),\quad\quad\textrm{where
}Z=\mathbb{E}_{\mathrm{P}}\left[\exp\left(\frac{-L^{\prime}(x)}{\lambda}\right)\right].$
(13)

One will notice that $\rho^{\textsc{KL}}_{\lambda}$ corresponds to an
exponential tilt [24] of $\mathrm{P}$ to yield a _Gibbs distribution_
$\mathrm{Q}^{\textsc{KL}}$. The KL density ratio rejectors are significant in
a few ways. First, from a closed-form solution perspective, due to the
properties of ‘$\log$’ and complementary slackness, $\alpha(y)=0$. Secondly,
due to the properties of $\exp$, the normalization term $b$ has a closed form
solution given by the typical log-normalizer term of exponential families.

Another notable property of utilizing a KL idealized distribution is that it
recovers the previously mentioned optimal rejection policies for classical
modelling with rejection via cost penalty.

######  Theorem 4.2 (Informal).

Given the CPE setting Theorem 2.1, if $h=h^{\star}$ is optimal, then there
exists a $r^{\textsc{KL}}_{\tau}$ which is equivalent to the optimal rejectors
in Theorem 2.1.

Theorem 4.2 states that the KL density rejectors (with correctly specified
$\lambda$ and $\tau$) with optimal predictors $h^{\star}$ recovers the optimal
rejectors of the typical rejection setting, _i.e_., Chow’s rule.

Until now, we have implicitly assumed that the true data distribution
$\mathrm{P}$ is accessible. In practice, we only have access empirical
$\hat{\mathrm{P}}_{N}$, defining subsequent rejectors
$\hat{\rho}_{\lambda,N}$. We show that for the KL rejector,
$\hat{\mathrm{P}}_{N}$ is enough given the following generalization bound.

######  Theorem 4.3.

Assume we have bounded loss $|\ell(\cdot,\cdot)|\leq B$ for $B>0$,
${\hat{\mathrm{P}}}_{N}\subset\mathrm{P}$ with _h.p_., and
$\mathcal{T}\subset\mathrm{Supp}(\mathrm{P})$. Suppose
$M=|\mathcal{T}|<+\infty$, then with probability $1-\delta$, we have that

$\sup_{x\in\mathcal{T}}\left|\rho_{\lambda}^{\textsc{KL}}(x)-\hat{\rho}_{\lambda,N}^{\textsc{KL}}(x)\right|\leq
C\cdot\sqrt{\frac{2}{N}\log\left(\frac{2M}{\delta}\right)},$

where
$C=\exp\left({B}/{\lambda}\right)^{3}\cdot\sinh\left({B}/{\lambda}\right)$.

Looking at Theorem 4.3, essentially we pay a price in generalization $M$ for
each element $x\in\mathcal{T}$ we are testing for rejection. For
generalization, it is useful to consider how $N,M$ changes our rate in Theorem
4.3. If we assume that the test set $\mathcal{T}$ is small in comparison to
the $N$ samples used to generate empirical distribution $\hat{\mathrm{P}}$,
then the $\mathcal{O}(1/\sqrt{N})$ rate will dominate. A concrete example of
this case is when $|\mathcal{X}|$ is finite. A less advantaged scenario is
when $M\approx N$, yielding $\mathcal{O}(\log(N)/\sqrt{N})$ — the scenario
where we test approximately the same number of data points as that used to
learn the rejector. This rate will still decrease with $N\rightarrow\infty$,
although with a $\log N$ price.

####  $\bm{\alpha}$-Divergences

Although the general case of finding idealized rejection distributions for
$\varphi$-divergences is difficult, we examine a specific generalization of
the KL case, the $\alpha$-divergences [3].

######  Definition 4.4.

For $\alpha\in\mathbb{R}$, the $\alpha$-divergence $D_{\alpha}$ is defined as
the $\varphi_{\alpha}$-divergence, where

$\varphi_{\alpha}(z)\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\begin{cases}\frac{4}{1-\alpha^{2}}\left(1-z^{\frac{1+\alpha}{2}}\right)-\frac{2}{1-\alpha}(z-1)&\textrm{if
}\alpha\neq\pm 1\\\ -\log z+(z-1)&\textrm{if }\alpha=-1\\\ z\log
z-(z-1)&\textrm{if }\alpha=1\end{cases}.$

We further define $\psi_{\alpha}$, where
$\psi_{\alpha}(z)=z^{\frac{1-\alpha}{2}}$ when $\alpha\neq 1$ and
$\psi_{\alpha}(z)=\log z$ when $\alpha=1$.

Note that taking $\alpha=1$ recover the KL-divergence. The $\alpha$-divergence
covers a wide range of divergences including the Pearson $\chi^{2}$ divergence
$(\alpha=3)$. For the density ratio, $\alpha$-divergences with $\alpha\neq 1$
(_i.e_. not KL) can be characterized as the following.

######  Theorem 4.5.

Let $\alpha\neq 1$ and $\lambda>0$. For $\varphi_{\alpha}$, the optimal
density ratio rejector $\rho_{\lambda}^{\alpha}(x)$ is,

$\displaystyle\rho^{\alpha}_{\lambda}(x)$
$\displaystyle=\psi^{-1}_{\alpha}\left(\frac{2}{\alpha-1}\cdot\left(a(x)-\frac{L^{\prime}(x)}{\lambda}+b\right)^{-1}\right)$
(14)

$a(x)$ are Lagrange multipliers for positivity; and $b$ is a Lagrange
multiplier for normalization.

One major downside of using general $\varphi$-divergences is that solving the
Lagrange multipliers for the idealized rejection distribution is often
difficult. Indeed, the “$\log$” and “$\exp$” ensures non-negativity of the
idealized distribution when the input data $\mathrm{P}$ is in the interior of
the simplex; and also provides a convenient normalization calculation. For
$\alpha$-divergences, the non-negative Lagrange multipliers $a(\cdot)$ can be
directly solved given certain conditions.

######  Corollary 4.6.

Suppose $\alpha>1$ and $\lambda>0$, then Eq. 14 simplifies to,

$\rho^{\alpha}_{\lambda}(x)=\left[\left(\frac{\alpha-1}{2}\cdot\left(b-\frac{L^{\prime}(x)}{\lambda}\right)\right)^{\frac{2}{\alpha-1}}\right]_{+},$
(15)

where we take non-integer powers of negative values as 0.

On the other hand, for $\alpha\leq-1$,
$D_{\alpha}(\mathrm{P}\mathrel{\|}\mathrm{Q})=\infty$ whenever $\mathrm{Q}$ is
on the boundary whenever $\mathrm{P}$ is not on the boundary [3, Section
3.4.1]. As such, we can partially simplify Eq. 14 for $\alpha\leq-1$.

######  Corollary 4.7.

Suppose $\alpha\leq-1$, $\lambda>0$, and $\mathrm{P}$ lies in the simplex
interior, then $a(\cdot)=0$ in Eq. 14.

Both Corollaries 4.6 and 4.7 can provide a unique rejector policy than the KL-
divergence variant. Corollary 4.7 can provide a similar effect when $a(x)\neq
0$ for all $x$. Nevertheless, having to determine which inputs $a(x)\neq 0$
and solving these values are difficult in practice. As such, we focus on
$\alpha>0$. If there are values of $L^{\prime}(x)$ with high risk, the $\max$
will flatten these inputs to $0$ in Corollary 4.6. However, if the original
model $h$ performs well and $L^{\prime}(x)$ is relatively small for all $x$,
then it is possible that the $\max$ is not utilized. In such a case, the
$\alpha$-divergence rejectors can end up being similar — this follows the fact
that (as $\varphi_{\alpha}^{\prime\prime}(1)>0$) locally all
$\alpha$-divergences will be similar to the $\chi^{2}$ /
$(\alpha=3)$-divergence [46, Theorem 7.20]. This ultimately results in
$\alpha$-divergences being similar to, _e.g_., Chow’s rule when
$h_{y}(x)\approx\Pr(\mathsf{Y}=y\mid\mathsf{X}=x)$ in classification via
Theorem 2.1.

Among the $\alpha>0$ cases, we examine the $\chi^{2}$-divergence ($\alpha=3$)
which results in closed form for bounded loss functions and sufficient large
regularizing parameter $\lambda$.

######  Corollary 4.8.

Suppose that $\ell(\cdot,\cdot)\leq B$ and
$\lambda>\max_{x}L^{\prime}(x)-\mathbb{E}_{\mathrm{P}}[L^{\prime}(x)]$. Then,

$\rho_{\lambda}^{\alpha=3}(x)=1+\frac{\mathbb{E}_{\mathrm{P}}[L^{\prime}(x)]-L^{\prime}(x)}{\lambda}.$
(16)

The condition on $\lambda$ for Corollary 4.8 is equivalent to rescaling
bounded loss functions $\ell$. Indeed, by fixing $\lambda=1$, we can achieve a
similar Theorem with suitable rescaling of $\ell$. Nevertheless, Eq. 16
provides a convenient form to allow for generalization bounds to be
established.

######  Theorem 4.9.

Assume we have bounded loss $|\ell(\cdot,\cdot)|\leq B$ for $B>0$,
$\lambda>2B$, ${\hat{\mathrm{P}}}_{N}\subset\mathrm{P}$ with _h.p_., and
$\mathcal{T}\subset\mathrm{Supp}(\mathrm{P})$. Suppose
$M=|\mathcal{T}|<+\infty$, then with probability $1-\delta$, we have that

$\sup_{x\in\mathcal{T}}\left|\rho_{\lambda}^{\alpha=3}(x)-\hat{\rho}_{\lambda}^{\alpha=3}(x)\right|\leq\frac{B}{\lambda}\cdot\sqrt{\frac{2}{N}\log\left(\frac{2M}{\delta}\right)}.$

Notice that Theorem 4.9’s sample complexity is equivalent to Theorem 4.3 up to
constant multiplication. Hence, the analysis of Theorem 4.3 regarding the
scales of $N,M$ hold for Theorem 4.9.

A question pertaining to DRO is what would be the generalization capabilities
of the corresponding adversarial distributions
${\hat{\mathrm{Q}}}_{\lambda,N}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}{\hat{\mathrm{P}}}_{N}\cdot\hat{\rho}_{\lambda,N}$
(through Corollary 3.4). On a finite domain, via Theorems 4.3 and 4.9 and a
simple triangle inequality, one can immediately bound the total variation
$\textsc{TV}({\hat{\mathrm{Q}}}_{\lambda,N},{\mathrm{Q}}_{\lambda})\leq\mathcal{O}(1/\sqrt{N})$,
see Appendix M for further details.

#### Practical Rejection

In the following, we consider practical concerns for utilizing rejector for
the KL-or $(\alpha>1)$-divergence case, Eqs. 13 and 15. To do so, we need to
estimate the loss $L^{\prime}(x)=\mathbb{E}_{\mathrm{P}_{\rm y\mid\rm
x}}\left[\ell(\mathsf{Y},h(x))\right]$ and rejector normalizer $Z$ or $b$.

_Loss_ : The former is tricky, we require an estimate to evaluate
$\mathbb{E}_{\mathrm{P}_{\rm y\mid\rm x}}\left[\ell(\mathsf{Y},h(x))\right]$
over any possible $x\in\mathcal{X}$ to allow us to make a rejection decision.
Implicitly, this requires us to have a high quality estimate of
$\mathrm{P}_{\rm y\mid\rm x}$. In a general learning setting, this can be
difficult to obtain — in fact it is just the overall objective that we are
trying to learning, _i.e_., predicting a target $y$ given an input $x$.
However, in the case of CPE (classification), it is not unreasonable to obtain
an _calibrated estimate_ of $\mathrm{P}_{\rm y\mid\rm x}$ via the classifier
$h\colon\mathcal{X}\rightarrow\mathcal{D}(\mathcal{Y})$ [45]. In Section 5, we
utilize temperature scaling to calibrate the neural networks we learn to
provide such an estimate [29]. Hence, we set
$L^{\prime}(x)=\mathbb{E}_{{\mathsf{Y}\sim
h(x)}}\left[\ell(\mathsf{Y},h(x))\right]$. For proper CPE loss functions,
$\mathbb{E}_{{\mathsf{Y}\sim h(x)}}\left[\ell(\mathsf{Y},h(x))\right]$ acts as
a generalized entropy function. As such, the rejectors Eqs. 13 and 15 act as
functions over said generalized entropy functions.

_Normalization_ : For the latter, we utilize a sample based estimate (over the
dataset used to train the rejector) of
$\mathbb{E}_{\mathrm{P}}\left[\rho_{\lambda}^{\varphi}(\mathsf{X})\right]$ is
utilized to solve the normalizers $Z$ and $b$. In the case of the KL-
divergence rejector, this is all that is required due to the convenient
function form of the Gibbs distribution, _i.e_., the normalizer $Z$ can be
simply estimated by a sample mean. However, for $\alpha>1$-divergences $b$
needs to be found to determine the normalization. Practically, we find $b$
through bisection search of

${\mathbb{E}}_{\hat{\mathrm{P}}}\left[\left(\frac{\alpha-1}{2}\cdot\left(b-\frac{L^{\prime}(x)}{\lambda}\right)\right)^{\frac{2}{\alpha-1}}\right]_{+}-1=0.$

This practically works as the optimization $b$ is over a single dimension.
Furthermore, we can have that
$b>\min_{x}\left\\{{L^{\prime}(x)}/{\lambda}\right\\}$. As an upper bound over
the possible values of $b$, we utilize a heuristic where we multiple the
corresponding maximum of ${L^{\prime}(x)}/{\lambda}$ with a constant.

_Cut-off $\tau$_: In addition to learning the density ratio, an additional
consideration is how to tune $\tau$ in the rejection decision, Definition 3.2.
Given a fixed density estimator $\rho$, change $\tau$ amounts to changing the
rate of rejection. We note that this problem is not limited to our density
ratio rejectors, where approaches with rejectors $r\in\mathcal{R}$ via a
(surrogate) minimization of Eq. 2 may be required multiple rounds of training
with different rejection costs $c$ to find an accept rate of rejection. In our
case, we have a fixed $\rho$ which allows easy tuning of $\tau$ given a
validation dataset, similar to other confidence based rejection approaches,
_e.g_., tuning a threshold for the margin of a classifier [7].

##  5 Experiments

Figure 2: Accuracy vs coverage plots across all datasets and approaches, with
50 equidistant $\tau\in(0,1]$ and $c\in[0,0.5)$ values (sorted by coverage).
The black horizontal line depicts base models trained without rejection.
Missing approaches in the plots indicates that the model rejects more than 60%
of test points or has accuracy below the base model. Shaded region indicates
$\pm 1$ s.t.d. region.

In this section, we evaluate our distributional approach to rejection across a
number of datasets. In particular, we consider the standard classification
setting with an addition setting where uniform label noise is introduced [4,
27]. For our density ratio rejectors, we evaluate the KL-divergence based
rejector (Corollary 4.1) and $(\alpha=3)$-based rejectors (Corollary 4.6) with
50 equidistant $\tau\in(0,1]$ values. For our tests, we fix $\lambda=1$.
Throughout our evaluation, we assume that a neural network (NN) model without
rejection is accessible for all (applicable) approaches and this model is
calibrated via temperature scaling [29]. As such, we use the practical
considerations discussed in Section 4 for our density ratio rejectors. For our
density ratio rejectors, we utilize the log-loss.

To evaluate our density ratio rejectors and baselines, we compare accuracy and
acceptance coverage. Accuracy corresponds to the 0-1 loss in Eq. 1 and the
acceptance coverage is the percentage of non-rejections in the test set.
Ideally, a rejector smoothly trade-offs between accuracy and acceptance,
_i.e_., a higher accuracy can be achieved by decreasing the acceptance
coverage by rejecting more data. We study this trade-off by examining multiple
cut-off values $\tau$ and rejection costs $c$.

#### Dataset and Baselines

We consider 3 multiclass classification datasets. For tabular datasets, we
consider the gas drift dataset [56] and the human activity recognition (HAR)
dataset [5]. Each of these datasets consists of 6 class labels to predict.
Furthermore, we utilize a two hidden layer multilayer perceptron NN model for
these datasets. In addition we consider the MNIST image dataset [37], where we
utilize a convolutional NN. These prediction models are trained utilizing the
standard logistic / log-loss without rejection and then are calibrated. For
each of these datasets, we utilize a clean and noisy variant. For the noisy
variant, we flip the class labels of the train set with a rate of 25%. We note
that the test set is clean in both cases. All evaluation uses 5-fold cross
validation. All implementation are done using PyTorch and are trained using a
`p3.2xlarge` instance on AWS.

We consider 4 different baseline for comparison. Each baseline is trained with
50 equidistant costs $c\in[0,0.5)$. One baseline used in comparison is
Mozannar and Sontag [40]’s cross-entropy surrogate approach (DEFER) which
reduces the $C$ multi-class classification problem into a $C+1$ multi-class
classification problem, treating the rejection option as a separate class. A
generalization of DEFER is also considered [13] where we change the surrogate
loss of cross-entropy to generalized cross-entropy [61] (GCE). We also
consider a cost-sensitive classification reduction (CSS) of the classification
with rejection problem [14] utilizing the sigmoid loss function. The
aforementioned 3 baselines all learn a model with rejection simultaneously,
_i.e_., a pretrained model cannot be utilized. We also consider a two stage
predictor-rejector approach (PredRej) which learns a rejector from a
pretrained classifier [39].

#### Results

Fig. 2 presents a summary plot of the acceptance coverage versus model
accuracy after rejection on the test set. The plot is focused around the 60%
to 100% coverage region, with an extend plot presented in Appendix P. Over all
folds for MNIST our density ratio rejectors take approximately $\sim 1/2$ hour
to fit. A single baseline (fixed $c$) takes upwards of 2 hour for a single
fold. Overall, given that the underlying model is calibrated, we find that our
KL-divergence and $\alpha=3$-divergence density ratio rejector are either
competitive or superior to the baselines. The baselines seem to become more
competitive as noise increases, see Appendix P for further details.
Furthermore, one might notice that the aforementioned baselines do not or
provide poor trade-offs for coverage values $>95\%$. Indeed, to achieve
rejection with high coverage (without architecture tuning), approaches which
‘wrap’ a base classifier seem preferable, _i.e_., PredRej and our density
ratios rejectors. It should be noted that if large models are allowed to be
used for the rejector — as per the MNIST case — CSS, DEFER, and GCE can
provide superior accuracy vs acceptance coverage trade-offs (Noisy MNIST).

Among the approaches which ‘wrap’ the base classifier $h$, we find that these
approaches have higher variance ranges than the other approaches. In
particular, the randomness of the base model potentially magnifies the
randomness after rejection. The variance range of the base model tends to
increase as the noise increases (additional ranges of noise for HAR and Gas
Drift are presented in the Appendix). The influence on rejection is
unsurprising as these ‘wrapping’ approaches predict via a composition of the
original model (and hence inherits its randomness across folds). In general,
our density ratio rejector outperforms PredRej. However, it should be noted
that PredRej does not require a calibrated classifier. Among the density ratio
rejectors, between KL and $\alpha=3$, the only variation is in coverage region
that the $\tau\in(0,1]$ threshold covers. This follows from the fact that for
similar distributions, $\varphi$-divergences act similarly [46, Theorem 7.20].
We find this pattern holds for other values of $\alpha$.

##  6 Limitations and Conclusions

We propose a new framework for rejection by learning idealized density ratios.
Our proposed rejection framework links typically explored classification with
rejection to generalized variational inference and distributionally robust
optimization. It should be noted that although we have focused on
classification, $L^{\prime}(\mathrm{Q})$ could in theory be replaced by any
other loss functions. In this sense, one could adapt this approach to other
learning tasks such as regression, discussed in Appendix N. Furthermore,
although we have focused on $\varphi$-divergences, there are many alternative
ways idealized distribution can be constructed, _e.g_., integral probability
metrics [42, 9]. One limitation of our distributional way of rejecting is the
reliance on approximating $\mathrm{P}(\mathsf{Y}\mid\mathsf{X})$ with model
$h$. Alternatively, in future work, one may seek to approximate the density
ratio $\rho$ by explicitly learning densities $\mathrm{Q}$ and $\mathrm{P}$ or
via gradient based methods (for the latter, see Appendix O).

## References

  * Ali and Silvey [1966] Syed Mumtaz Ali and Samuel D Silvey.  A general class of coefficients of divergence of one distribution from another.  _Journal of the Royal Statistical Society: Series B (Methodological)_ , 28(1):131–142, 1966.
  * Amari and Nagaoka [2000] S.-I. Amari and H. Nagaoka.  _Methods of Information Geometry_.  Oxford University Press, 2000.
  * Amari [2016] Shun-ichi Amari.  _Information geometry and its applications_ , volume 194.  Springer, 2016.
  * Angluin and Laird [1988] Dana Angluin and Philip Laird.  Learning from noisy examples.  _Machine learning_ , 2:343–370, 1988.
  * Anguita et al. [2013] Davide Anguita, Alessandro Ghio, Luca Oneto, Xavier Parra, Jorge Luis Reyes-Ortiz, et al.  A public domain dataset for human activity recognition using smartphones.  In _Esann_ , volume 3, page 3, 2013.
  * Asuncion and Newman [2007] Arthur Asuncion and David Newman.  Uci machine learning repository, 2007.
  * Bartlett and Wegkamp [2008] Peter L Bartlett and Marten H Wegkamp.  Classification with a reject option using a hinge loss.  _Journal of Machine Learning Research_ , 9(8), 2008.
  * Ben-Tal et al. [2013] Aharon Ben-Tal, Dick Den Hertog, Anja De Waegenaere, Bertrand Melenberg, and Gijs Rennen.  Robust solutions of optimization problems affected by uncertain probabilities.  _Management Science_ , 59(2):341–357, 2013.
  * Birrell et al. [2022] Jeremiah Birrell, Paul Dupuis, Markos A Katsoulakis, Yannis Pantazis, and Luc Rey-Bellet.  $(f,\Gamma)$-Divergences: interpolating between $f$-divergences and integral probability metrics.  _The Journal of Machine Learning Research_ , 23(1):1816–1885, 2022.
  * Blanchet and Murthy [2019] Jose Blanchet and Karthyek Murthy.  Quantifying distributional model risk via optimal transport.  _Mathematics of Operations Research_ , 44(2):565–600, 2019.
  * Blanchet et al. [2019] Jose Blanchet, Yang Kang, and Karthyek Murthy.  Robust wasserstein profile inference and applications to machine learning.  _Journal of Applied Probability_ , 56(3):830–857, 2019.
  * Boucheron et al. [2013] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart.  _Concentration Inequalities: A Nonasymptotic Theory of Independence_.  Oxford University Press, 02 2013.  ISBN 9780199535255.  doi: 10.1093/acprof:oso/9780199535255.001.0001.  URL https://doi.org/10.1093/acprof:oso/9780199535255.001.0001.
  * Cao et al. [2022] Yuzhou Cao, Tianchi Cai, Lei Feng, Lihong Gu, Jinjie Gu, Bo An, Gang Niu, and Masashi Sugiyama.  Generalizing consistent multi-class classification with rejection to be compatible with arbitrary losses.  _Advances in Neural Information Processing Systems_ , 35:521–534, 2022.
  * Charoenphakdee et al. [2021] Nontawat Charoenphakdee, Zhenghang Cui, Yivan Zhang, and Masashi Sugiyama.  Classification with rejection based on cost-sensitive classification.  In _International Conference on Machine Learning_ , pages 1507–1517. PMLR, 2021.
  * Chow [1970] C Chow.  On optimum recognition error and reject tradeoff.  _IEEE Transactions on information theory_ , 16(1):41–46, 1970.
  * Cortes et al. [2016a] Corinna Cortes, Giulia DeSalvo, and Mehryar Mohri.  Boosting with abstention.  _Advances in Neural Information Processing Systems_ , 29, 2016a.
  * Cortes et al. [2016b] Corinna Cortes, Giulia DeSalvo, and Mehryar Mohri.  Learning with rejection.  In _Algorithmic Learning Theory: 27th International Conference, ALT 2016, Bari, Italy, October 19-21, 2016, Proceedings 27_ , pages 67–82. Springer, 2016b.
  * Csiszár [1964] Imre Csiszár.  Eine informationstheoretische ungleichung und ihre anwendung auf beweis der ergodizitaet von markoffschen ketten.  _Magyer Tud. Akad. Mat. Kutato Int. Koezl._ , 8:85–108, 1964.
  * Csiszár [1967] Imre Csiszár.  Information-type measures of difference of probability distributions and indirect observation.  _studia scientiarum Mathematicarum Hungarica_ , 2:229–318, 1967.
  * Csiszár et al. [2004] Imre Csiszár, Paul C Shields, et al.  Information theory and statistics: A tutorial.  _Foundations and Trends® in Communications and Information Theory_ , 1(4):417–528, 2004.
  * Duchi and Namkoong [2019] John Duchi and Hongseok Namkoong.  Variance-based regularization with convex objectives.  _The Journal of Machine Learning Research_ , 20(1):2450–2504, 2019.
  * Duchi et al. [2021] John C Duchi, Peter W Glynn, and Hongseok Namkoong.  Statistics of robust optimization: A generalized empirical likelihood approach.  _Mathematics of Operations Research_ , 46(3):946–969, 2021.
  * Dvijotham et al. [2019] Krishnamurthy Dj Dvijotham, Jamie Hayes, Borja Balle, Zico Kolter, Chongli Qin, Andras Gyorgy, Kai Xiao, Sven Gowal, and Pushmeet Kohli.  A framework for robustness certification of smoothed classifiers using f-divergences.  In _International Conference on Learning Representations_ , 2019.
  * Efron [2022] Bradley Efron.  _Exponential families in theory and practice_.  Cambridge University Press, 2022.
  * Fan [1953] Ky Fan.  Minimax theorems.  _Proceedings of the National Academy of Sciences of the United States of America_ , 39(1):42, 1953.
  * Geifman and El-Yaniv [2017] Yonatan Geifman and Ran El-Yaniv.  Selective classification for deep neural networks.  _Advances in neural information processing systems_ , 30, 2017.
  * Ghosh et al. [2015] Aritra Ghosh, Naresh Manwani, and PS Sastry.  Making risk minimization tolerant to label noise.  _Neurocomputing_ , 160:93–107, 2015.
  * Grandvalet et al. [2008] Yves Grandvalet, Alain Rakotomamonjy, Joseph Keshet, and Stéphane Canu.  Support vector machines with a reject option.  _Advances in neural information processing systems_ , 21, 2008.
  * Guo et al. [2017] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger.  On calibration of modern neural networks.  In _International conference on machine learning_ , pages 1321–1330. PMLR, 2017.
  * Husain [2020] Hisham Husain.  Distributional robustness with ipms and links to regularization and gans.  _Advances in Neural Information Processing Systems_ , 33:11816–11827, 2020.
  * Husain and Knoblauch [2022] Hisham Husain and Jeremias Knoblauch.  Adversarial interpretation of bayesian inference.  In _International Conference on Algorithmic Learning Theory_ , pages 553–572. PMLR, 2022.
  * Ioffe and Szegedy [2015] Sergey Ioffe and Christian Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  In _International conference on machine learning_ , pages 448–456. pmlr, 2015.
  * Kingma and Welling [2013] Diederik P Kingma and Max Welling.  Auto-encoding variational bayes.  _arXiv preprint arXiv:1312.6114_ , 2013.
  * Knoblauch et al. [2022] Jeremias Knoblauch, Jack Jewson, and Theodoros Damoulas.  An optimization-centric view on bayes’ rule: Reviewing and generalizing variational inference.  _The Journal of Machine Learning Research_ , 23(1):5789–5897, 2022.
  * Knuth [1992] Donald E Knuth.  Two notes on notation.  _The American Mathematical Monthly_ , 99(5):403–422, 1992.
  * Lam [2016] Henry Lam.  Robust sensitivity analysis for stochastic systems.  _Mathematics of Operations Research_ , 41(4):1248–1275, 2016.
  * LeCun [1998] Yann LeCun.  The mnist database of handwritten digits.  _http://yann. lecun. com/exdb/mnist/_ , 1998.
  * Manwani et al. [2015] Naresh Manwani, Kalpit Desai, Sanand Sasidharan, and Ramasubramanian Sundararajan.  Double ramp loss based reject option classifier.  In _Pacific-Asia Conference on Knowledge Discovery and Data Mining_ , pages 151–163. Springer, 2015.
  * Mao et al. [2024] Anqi Mao, Mehryar Mohri, and Yutao Zhong.  Predictor-rejector multi-class abstention: Theoretical analysis and algorithms.  In _International Conference on Algorithmic Learning Theory_ , pages 822–867. PMLR, 2024.
  * Mozannar and Sontag [2020] Hussein Mozannar and David Sontag.  Consistent estimators for learning to defer to an expert.  In _International Conference on Machine Learning_ , pages 7076–7087. PMLR, 2020.
  * Mozannar et al. [2023] Hussein Mozannar, Hunter Lang, Dennis Wei, Prasanna Sattigeri, Subhro Das, and David Sontag.  Who should predict? exact algorithms for learning to defer to humans.  In _International Conference on Artificial Intelligence and Statistics_ , pages 10520–10545. PMLR, 2023.
  * Müller [1997] Alfred Müller.  Integral probability metrics and their generating classes of functions.  _Advances in Applied Probability_ , 29(2):429–443, 1997.
  * Narasimhan et al. [2022] Harikrishna Narasimhan, Wittawat Jitkrittum, Aditya K Menon, Ankit Rawat, and Sanjiv Kumar.  Post-hoc estimators for learning to defer to an expert.  _Advances in Neural Information Processing Systems_ , 35:29292–29304, 2022.
  * Ni et al. [2019] Chenri Ni, Nontawat Charoenphakdee, Junya Honda, and Masashi Sugiyama.  On the calibration of multiclass classification with rejection.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Platt et al. [1999] John Platt et al.  Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods.  _Advances in large margin classifiers_ , 10(3):61–74, 1999.
  * Polyanskiy and Wu [2022] Yury Polyanskiy and Yihong Wu.  Information theory: From coding to learning.  _Book draft_ , 2022.
  * Ramaswamy et al. [2018] H. G. Ramaswamy, Ambuj Tewari, and Shivani Agarwal.  Consistent algorithms for multiclass classification with an abstain option.  _Electronic Journal of Statistics_ , 12:530–554, 2018.  URL https://api.semanticscholar.org/CorpusID:126332033.
  * Reid and Williamson [2010] Mark D Reid and Robert C Williamson.  Composite binary losses.  _The Journal of Machine Learning Research_ , 11:2387–2422, 2010.
  * Reid and Williamson [2011] Mark D Reid and Robert C Williamson.  Information, divergence and risk for binary experiments.  _Journal of Machine Learning Research_ , 12:731–817, 2011\.
  * Sason and Verdú [2016] Igal Sason and Sergio Verdú.  $f$-divergence inequalities.  _IEEE Transactions on Information Theory_ , 62(11):5973–6006, 2016.
  * Scarf [1957] Herbert E Scarf.  A min-max solution of an inventory problem.  Technical report, RAND CORP SANTA MONICA CALIF, 1957.
  * Sinha et al. [2018] Aman Sinha, Hongseok Namkoong, and John Duchi.  Certifiable distributional robustness with principled adversarial training.  In _International Conference on Learning Representations_ , 2018.  URL https://openreview.net/forum?id=Hk6kPgZA-.
  * Srivastava et al. [2014] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov.  Dropout: a simple way to prevent neural networks from overfitting.  _The journal of machine learning research_ , 15(1):1929–1958, 2014.
  * Staib and Jegelka [2019] Matthew Staib and Stefanie Jegelka.  Distributionally robust optimization and generalization in kernel methods.  In _Advances in Neural Information Processing Systems_ , pages 9131–9141, 2019.
  * Sugiyama et al. [2012] Masashi Sugiyama, Taiji Suzuki, and Takafumi Kanamori.  _Density ratio estimation in machine learning_.  Cambridge University Press, 2012.
  * Vergara et al. [2012] Alexander Vergara, Shankar Vembu, Tuba Ayhan, Margaret A Ryan, Margie L Homer, and Ramón Huerta.  Chemical gas sensor drift compensation using classifier ensembles.  _Sensors and Actuators B: Chemical_ , 166:320–329, 2012\.
  * Yuan and Wegkamp [2010] Ming Yuan and Marten Wegkamp.  Classification methods with reject option based on convex risk minimization.  _Journal of Machine Learning Research_ , 11(1), 2010.
  * Zaoui et al. [2020] Ahmed Zaoui, Christophe Denis, and Mohamed Hebiri.  Regression with reject option and application to knn.  _Advances in Neural Information Processing Systems_ , 33:20073–20082, 2020.
  * Zellner [1988] Arnold Zellner.  Optimal information processing and bayes’s theorem.  _American Statistician_ , pages 278–280, 1988.
  * Zhang et al. [2021] Jingzhao Zhang, Aditya Krishna Menon, Andreas Veit, Srinadh Bhojanapalli, Sanjiv Kumar, and Suvrit Sra.  Coping with label shift via distributionally robust optimisation.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=BtZhsSGNRNi.
  * Zhang and Sabuncu [2018] Zhilu Zhang and Mert Sabuncu.  Generalized cross entropy loss for training deep neural networks with noisy labels.  _Advances in neural information processing systems_ , 31, 2018.

Supplementary Material

This is the Supplementary Material to Paper "Rejection via Learning Density
Ratios". To differentiate with the numberings in the main file, the numbering
of Theorems is letter-based (A, B, …).

## Table of contents

Proof
$\hookrightarrow$ Appendix A: Proof of Theorem 2.1 Pg A
$\hookrightarrow$ Appendix B: Proof of Theorem 3.3 Pg B
$\hookrightarrow$ Appendix C: Proof of Corollary 3.4 Pg C
$\hookrightarrow$ Appendix D: Proof of Corollary 4.1 Pg D
$\hookrightarrow$ Appendix E: Proof of Theorem 4.2 Pg E
$\hookrightarrow$ Appendix F: Proof of Theorem 4.3 Pg F
$\hookrightarrow$ Appendix G: Proof of Theorem 4.5 Pg G
$\hookrightarrow$ Appendix H: Proof of Corollary 4.6 Pg H
$\hookrightarrow$ Appendix I: Proof of Corollary 4.7 Pg I
$\hookrightarrow$ Appendix J: Proof of Corollary 4.8 Pg J
$\hookrightarrow$ Appendix K: Proof of Theorem 4.9 Pg K

Deferred Content
$\hookrightarrow$ Appendix L: Broader Impact Pg L
$\hookrightarrow$ Appendix M: Distribution Generalization Bounds Pg M
$\hookrightarrow$ Appendix N: Rejection for Regression Pg N
$\hookrightarrow$ Appendix O: Gradient of Density Ratio Objective Pg O
$\hookrightarrow$ Appendix P: Additional Experimental Details Pg P

##  Appendix A Proof of Theorem 2.1

###### Proof.

We first rewrite the coverage probability as an expectation:

$\displaystyle\mathbb{E}_{\mathrm{P}}[(1-r(\mathsf{X}))\cdot\ell(\mathsf{Y},h(\mathsf{X}))]+c\cdot\Pr[r(\mathsf{X})=1]$
$\displaystyle=\mathbb{E}_{\mathrm{P}}[(1-r(\mathsf{X}))\cdot\ell(\mathsf{Y},h(\mathsf{X}))+c\cdot
r(\mathsf{X})].$

We note that point-wise, the _proper_ loss $\ell$ is minimized by taking the
Bayes optimal classifier $\eta^{\star}(x)=\Pr[\mathsf{Y}=+1\mid\mathsf{X}=x]$.
Thus taking the $\operatorname*{argmin}$ over all possible CPE classifiers,
$h^{\star}=\eta^{\star}$. We note that the point-wise risk taken by the Bayes
optimal classifier is typical denoted as the Bayes point-wise risk
$\underline{L}(x)=\mathbb{E}_{\mathrm{P}_{\rm y\mid\rm
x=x}}[\ell(\mathsf{Y},\eta^{\star}(x))]$ [48, 49].

As such, we are left to minimize $r$ over,

$\displaystyle\mathbb{E}_{\mathrm{P}}[(1-r(\mathsf{X}))\cdot\ell(\mathsf{Y},\eta^{\star}(\mathsf{X}))+c\cdot
r(\mathsf{X})]$ $\displaystyle=\mathbb{E}_{\mathrm{P}_{\rm
x}}\mathbb{E}_{\mathrm{P}_{\rm y\mid\rm
x=\mathsf{X}}}[(1-r(\mathsf{X}))\cdot\ell(\mathsf{Y},\eta^{\star}(\mathsf{X}))+c\cdot
r(\mathsf{X})]$ $\displaystyle=\mathbb{E}_{\mathrm{P}_{\rm
x}}[(1-r(\mathsf{X}))\cdot\underline{L}(\mathsf{X})+c\cdot r(\mathsf{X})]$
$\displaystyle=\mathbb{E}_{\mathrm{P}_{\rm
x}}[\underline{L}(\mathsf{X})]+\mathbb{E}_{\mathrm{P}_{\rm
x}}\left[r(\mathsf{X})\cdot\left(c-\underline{L}(\mathsf{X})\right)\right].$

Thus, we immediately get the optimal
$r^{\star}(x)=\left\llbracket\underline{L}(x)\geq c\right\rrbracket$. ∎

##  Appendix B Proof of Theorem 3.3

###### Proof.

We use the theory of Lagrange multipliers to make different constraints
explicit optimization problems.

Let us first consider the reduction from learing explicit distributions Eq. 8
to density ratios Eq. 9. First note that the objective Eq. 8 can be written as
follows:

$\displaystyle L(\mathrm{Q})+\lambda\cdot
D_{\varphi}(\mathrm{P}\mathrel{\|}\mathrm{Q})$ $\displaystyle=\int
L^{\prime}(x)\mathrm{d}\mathrm{Q}(x)+\lambda\cdot\int\varphi\left(\frac{\mathrm{d}\mathrm{Q}}{\mathrm{d}\mathrm{P}}\right)\mathrm{d}\mathrm{P}(x)$
$\displaystyle=\int
L^{\prime}(x)\frac{\mathrm{d}\mathrm{Q}}{\mathrm{d}\mathrm{P}}(x)\mathrm{d}\mathrm{P}(x)+\lambda\cdot\int\varphi\left(\frac{\mathrm{d}\mathrm{Q}}{\mathrm{d}\mathrm{P}}(x)\right)\mathrm{d}\mathrm{P}(x)$
$\displaystyle=\mathbb{E}_{\mathrm{P}}\left[L^{\prime}(x)\cdot\frac{\mathrm{d}\mathrm{Q}}{\mathrm{d}\mathrm{P}}(x)+\lambda\cdot\varphi\left(\frac{\mathrm{d}\mathrm{Q}}{\mathrm{d}\mathrm{P}}(x)\right)\right]$

The reduction to Eq. 9 now follows from a reduction from minimizing over
$\mathrm{Q}$ to $\mathrm{d}\mathrm{Q}/\mathrm{d}\mathrm{P}$, noting that
$\mathrm{Q}$ is restricted to be on the simplex. As such, the simplex
constraints are transfered to:

$\frac{\mathrm{d}\mathrm{Q}}{\mathrm{d}\mathrm{P}}\geq
0\quad\textrm{and}\quad\int\mathrm{d}\mathrm{P}(x)\cdot\frac{\mathrm{d}\mathrm{Q}}{\mathrm{d}\mathrm{P}}(x)=\mathbb{E}_{\mathrm{P}}\left[\frac{\mathrm{d}\mathrm{Q}}{\mathrm{d}\mathrm{P}}(\mathsf{X})\right]=1,$

where the former is the non-negativity of simplex elements and the latter is
the normalization requirement. Hence, taking
$\rho=\rho_{\lambda}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\frac{\mathrm{d}\mathrm{Q}}{\mathrm{d}\mathrm{P}}$
completes the reduction. (we remove the subscript “$\lambda$” for the rest of
the proof)

As such we have the optimization problem in Eq. 9, where we will convert the
constraints into Lagrange multipliers, defining,

$\displaystyle\mathcal{L}(\rho;a,b)$
$\displaystyle=\mathbb{E}_{\mathrm{P}}\left[\rho(\mathsf{X})\cdot
L^{\prime}(\mathsf{X})+\lambda\cdot\varphi(\rho(\mathsf{X}))\right]-\int
a^{\prime}(x)\rho(x)\mathrm{d}\mathrm{}x+b\cdot\left(1-\mathbb{E}_{\mathrm{P}}[\rho(\mathsf{X})]\right)$
$\displaystyle=\mathbb{E}_{\mathrm{P}}\left[\rho(\mathsf{X})\cdot
L^{\prime}(\mathsf{X})+\lambda\cdot\varphi\left(\rho(\mathsf{X})\right)-a(\mathsf{X})\cdot\rho(\mathsf{X})-b\cdot\rho(\mathsf{X})\right]+b,$

where $a(x)=a^{\prime}(x)\cdot\mathrm{P}(x)$.

We can obtain the first order optimality conditions by taking the functional
derivative. Suppose that $\delta>0$ and
$h\colon\mathcal{X}\rightarrow\mathbb{R}$ is any function. The functional
derivative is given by,

$\displaystyle\frac{\mathrm{d}\mathrm{}}{\mathrm{d}\mathrm{}\delta}\mathcal{L}(\rho+\delta\cdot
h;a,b)\Bigg{|}_{\delta=0}$
$\displaystyle=\mathbb{E}_{\mathrm{P}}\left[h(\mathsf{X})\cdot\left(L^{\prime}(\mathsf{X})+\lambda\cdot\varphi^{\prime}\left(\rho(\mathsf{X})+\delta\cdot
h(\mathsf{X})\right)-a(\mathsf{X})-b\right)\right]\bigg{|}_{\delta=0}$
$\displaystyle=\mathbb{E}_{\mathrm{P}}\left[h(\mathsf{X})\cdot\left(L^{\prime}(\mathsf{X})+\lambda\cdot\varphi^{\prime}\left(\rho(\mathsf{X})\right)-a(\mathsf{X})-b\right)\right].$

Thus, the first order condition is,

$\displaystyle
0=\frac{\mathrm{d}\mathrm{}}{\mathrm{d}\mathrm{}\delta}\mathcal{L}(\rho+\delta\cdot
h;a,b)\Bigg{|}_{\delta=0}=\mathbb{E}_{\mathrm{P}}\left[h(\mathsf{X})\cdot\left(L^{\prime}(\mathsf{X})+\lambda\cdot\varphi^{\prime}\left(\rho(\mathsf{X})\right)-a(\mathsf{X})-b\right)\right],$

for all $h\colon\mathcal{X}\rightarrow\mathbb{R}$. As the condition must hold
for all $h$ for an optimal $\rho^{\star}$, we have that for all
$x\in\mathcal{X}$,

$\displaystyle 0$
$\displaystyle=L^{\prime}(x)+\lambda\cdot\varphi^{\prime}\left(\rho^{\star}(x)\right)-a(x)-b$
$\displaystyle\iff$
$\displaystyle\varphi^{\prime}\left(\rho^{\star}(x)\right)$
$\displaystyle=\frac{b+a(x)-L^{\prime}(x)}{\lambda}$ $\displaystyle\iff$
$\displaystyle\rho^{\star}(x)$
$\displaystyle=(\varphi^{\prime})^{-1}\left(\frac{b-L^{\prime}(x)+a(x)}{\lambda}\right).$

As required. ∎

##  Appendix C Proof of Corollary 3.4

###### Proof.

First notice that the inner maximization in the DRO optimization Eq. 7 can be
simplified as follows:

$\displaystyle\mathop{\sup}_{\mathrm{Q}\in
B_{\varepsilon}(\mathrm{P})}L(\mathrm{Q})$
$\displaystyle=-\left(\mathop{\inf}_{\mathrm{Q}\in
B_{\varepsilon}(\mathrm{P})}-L(\mathrm{Q})\right)$
$\displaystyle=-\left(\mathop{\inf}_{\mathrm{Q}\in\mathcal{D}(\mathcal{X})}\;\sup_{\lambda\geq
0}-L(\mathrm{Q}_{\lambda})-\lambda\cdot(\varepsilon-
D_{\varphi}(\mathrm{P}\mathrel{\|}\mathrm{Q}_{\lambda}))\right)$
$\displaystyle=-\left(\sup_{\lambda\geq
0}\;\mathop{\inf}_{\mathrm{Q}_{\lambda}\in\mathcal{D}(\mathcal{X})}-L(\mathrm{Q}_{\lambda})-\lambda\cdot(\varepsilon-
D_{\varphi}(\mathrm{P}\mathrel{\|}\mathrm{Q}_{\lambda}))\right),$

where the last inequality follows from Fan’s minimax Theorem [25, Theorem 2]
noting that $\mathrm{Q}\mapsto L(\mathrm{Q}_{\lambda})$ is linear and the
selected $\varphi$ per Definition 2.2 makes $\mathrm{Q}\mapsto
D(\mathrm{P}\mathrel{\|}\mathrm{Q}_{\lambda})$ a convex lower semi-continuous
function.

Now notice that the inner minimization of this simplification is exactly our
idealized rejection distribution objective Eq. 8 when we negate the loss. As
such, noticing that solutions to Eq. 8 are exactly given by
$\mathrm{P}\cdot\rho$ yields the result after optimizing for the ‘arguments’
in the above DRO objective for both $\lambda$ and $\mathrm{Q}_{\lambda}$. ∎

##  Appendix D Proof of Corollary 4.1

We defer the proof of Corollary 4.1 to Appendix G, which covers any $\alpha$
including KL ($\alpha=1$).

##  Appendix E Proof of Theorem 4.2

We breakdown Theorem 4.2 into two sub-theorems Theorem E.1 for each of the
settings.

######  Theorem E.1.

Given the binary CPE setting presented in Theorem 2.1 and that we are given
the optimal classifier
$h^{\star}(x)=\mathrm{P}(\mathsf{Y}=1\mid\mathsf{X}=x)$, for any $\lambda>0$
there exists a $\tau>0$ such that the $r^{\textsc{KL}}_{\tau}$ rejector
generated the optimal density ratio in Corollary 4.1 is equivalent to the
optimal rejector in Theorem 2.1.

The proofs of each are similar. We first make the observation that the
rejector function $r^{\textsc{KL}}_{\tau}$ can be simplified as follows:

$r^{\textsc{KL}}_{\tau}=\left\llbracket L^{\prime}(x)\leq-\lambda\left(\log
Z+\log\tau\right)\right\rrbracket,$

Now we note that given a fixed $\lambda>0$ (which also fixes $Z$), the RHS
term has a one-to-one mapping from $\mathbb{R}_{+}$ to $\mathbb{R}$. Thus all
that is to verify is that thresholding $L^{\prime}(x)$ is equivalent to the
rejectors of Theorems 2.1 and N.1.

###### Proof.

For the CPE case, from assumptions, we have that
$L^{\prime}(x)=\mathbb{E}_{\mathsf{Y}\sim\mathrm{P}(\mathsf{Y}\mid\mathsf{X}=x)}[\ell(\mathsf{Y},h^{\star}(x))]=\mathbb{E}_{\mathsf{Y}\sim
h^{\star}(\mathsf{X}=x)}[\ell(\mathsf{Y},h^{\star}(x))$ as $h^{\star}$ is
optimal. Thus thresholding used in $r^{\textsc{KL}}_{\tau}$ is equivalent to
thresholding $L^{\prime}(x)$ by keeping $\lambda$ fixed and changine $\tau$
appropriately. ∎

##  Appendix F Proof of Theorem 4.3

To prove the theorem, we will be using the standard Hoeffding’s inequality
[12].

######  Theorem F.1 (Hoeffding’s Inequality [12, Theorem 2.8]).

Let $\mathsf{X}_{1},\ldots,\mathsf{X}_{n}$ be independent random variables
such that $\mathsf{X}_{i}$ takes values in $[a_{i},b_{i}]$ almost surely for
all $i\leq n$. Defining $\mathsf{X}=\sum_{i}\mathsf{X}_{i}-\mathbb{E}X_{i}$,
then for every $t>0$,

$\Pr\left(\mathsf{X}\geq
t\right)\leq\exp\left(-\frac{2t^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}\right).$

###### Proof.

Let us denote $Z$ to be the normalizer with the true expectation
$\mathbb{E}_{\mathrm{P}}$ and $\hat{Z}$ to be the normalizer with the
empirical expectation $\mathbb{E}_{\hat{\mathrm{P}}}$.

As $\ell$ is bounded, we take note of the following bounds,

$\displaystyle\exp(-B/\lambda)\leq\max\left\\{\exp\left(\frac{-L^{\prime}(x)}{\lambda}\right),Z,\hat{Z}\right\\}\leq\exp(B/\lambda).$

This can be simply verified by taking the smallest and largest values of the
$\exp$.

Now we simply have

$\displaystyle|\rho^{\textsc{KL}}(x)-\hat{\rho}^{\textsc{KL}}(x)|$
$\displaystyle=\exp\left(\frac{-L^{\prime}(x)}{\lambda}\right)\cdot\left|\frac{1}{Z}-\frac{1}{\hat{Z}}\right|$
$\displaystyle\leq\exp\left(\frac{B}{\lambda}\right)\cdot\left|\frac{1}{Z}-\frac{1}{\hat{Z}}\right|$
$\displaystyle=\exp\left(\frac{B}{\lambda}\right)\cdot\frac{|Z-\hat{Z}|}{|Z\cdot\hat{Z}|}$
$\displaystyle\leq\exp\left(\frac{B}{\lambda}\right)^{3}\cdot|Z-\hat{Z}|.$

Notice that $|Z-\hat{Z}|$ can be bounded via concentration inequality on
(bounded) random variable
$\exp\left(\frac{-L^{\prime}(\mathsf{X})}{\lambda}\right)$.

Thus, we have that by Theorem F.1

$\displaystyle\Pr\left(\left|\mathbb{E}_{\mathrm{P}}\left[\exp\left(\frac{-L^{\prime}(x)}{\lambda}\right)\right]-\mathbb{E}_{\mathrm{P}}\left[\exp\left(\frac{-L^{\prime}(x)}{\lambda}\right)\right]\right|>t\right)\leq
2\exp\left(\frac{-2\cdot N\cdot t^{2}}{(b-a)^{2}}\right),$

where
$(b-a)^{2}=(\exp(B/\lambda)-\exp(-B/\lambda))^{2}=4\sinh^{2}(B/\lambda)$.

Taking a union bound over $\mathcal{T}$, we have that

$\displaystyle\Pr\left(\exists
x\in\mathcal{T}:\left|\mathbb{E}_{\mathrm{P}}\left[\exp\left(\frac{-L^{\prime}(x)}{\lambda}\right)\right]-\mathbb{E}_{\mathrm{P}}\left[\exp\left(\frac{-L^{\prime}(x)}{\lambda}\right)\right]\right|>t\right)\leq
2M\exp\left(\frac{-N\cdot t^{2}}{2\sinh^{2}(B/\lambda)}\right).$

Thus taking
$t=\sinh(B/\lambda)\cdot\sqrt{\frac{2}{N}\cdot\log\left(\frac{2M}{\delta}\right)}$,
we have that with probability $1-\delta$ for $\delta>0$, for any
$x\in\mathcal{T}$,

$\displaystyle|\rho^{\textsc{KL}}(x)-\hat{\rho}^{\textsc{KL}}(x)|$
$\displaystyle\leq\exp\left(\frac{B}{\lambda}\right)^{3}\cdot|Z-\hat{Z}|$
$\displaystyle\leq\exp\left(\frac{B}{\lambda}\right)^{3}\cdot\sinh(B/\lambda)\cdot\sqrt{\frac{2}{N}\cdot\log\left(\frac{2M}{\delta}\right)}.$

As required.

∎

##  Appendix G Proof of Theorem 4.5

Before proving the theorems, we first state some basic properties of
$\psi_{\alpha}$.

######  Lemma G.1.

For $\alpha\neq-1$, $\psi_{\alpha}(u\cdot
v)=\psi_{\alpha}(u)\cdot\psi_{\alpha}(v)$ and
$\psi_{\alpha}(1/v)=1/\psi_{\alpha}(v)$. Furthermore, these statements hold
when $\psi_{\alpha}$ is replaced with $\psi_{\alpha}^{-1}$.

######  Lemma G.2.

$\psi_{\alpha}^{-1}(z)=\begin{cases}z^{\frac{2}{1-\alpha}}&\textrm{if
}\alpha\neq 1\\\ \exp(z)&\textrm{otherwise}\end{cases}.$ (17)

The above statements follows directly from definition and simple calculation.
The next statement directly connects $\varphi_{\alpha}^{\prime}$ to
$\psi_{\alpha}$.

######  Lemma G.3.

For $\alpha\neq 1$,

$(\varphi_{\alpha}^{\prime})(z)=\frac{2}{\alpha-1}\cdot{\psi_{\alpha}(1/z)}.$
(18)

###### Proof.

We prove this via cases.

$\bullet\quad\alpha=-1$:

$\displaystyle\varphi_{-1}^{\prime}(z)=\frac{\mathrm{d}\mathrm{}}{\mathrm{d}\mathrm{}z}(-\log
z)=-z^{-1}=-1\cdot
z^{-\frac{1-\alpha}{2}}=\frac{2}{\alpha-1}\cdot\psi_{\alpha}(1/z).$

$\bullet\quad\alpha\neq\pm 1$:

$\displaystyle\varphi_{\alpha}^{\prime}(z)=\frac{\mathrm{d}\mathrm{}}{\mathrm{d}\mathrm{}z}\left(\frac{4}{1-\alpha^{2}}\cdot\left(1-z^{\frac{1+\alpha}{2}}\right)\right)=-\frac{2}{1-\alpha}z^{\frac{\alpha-1}{2}}=-\frac{2}{1-\alpha}\cdot
z^{-\frac{1-\alpha}{2}}=\frac{2}{\alpha-1}\cdot\psi_{\alpha}(1/z)$

∎

We now define the following constants depending on $\alpha$:

$c_{\alpha}=\begin{cases}\psi^{-1}_{\alpha}\left(-\frac{2}{1-\alpha}\right)&\textrm{if
}\alpha\neq 1\\\
\psi^{-1}_{\alpha}(-1)=\exp(-1)&\textrm{otherwise}.\end{cases}$ (19)

######  Lemma G.4.

For $\alpha\neq 1$,

$(\varphi_{\alpha}^{\prime})^{-1}(z)=c_{\alpha}\cdot\frac{1}{\psi^{-1}_{\alpha}(z)}.$
(20)

###### Proof.

We prove this via cases.

$\bullet\quad\alpha=-1$:

$\displaystyle\varphi_{-1}^{\prime}(z)=\frac{\mathrm{d}\mathrm{}}{\mathrm{d}\mathrm{}z}(-\log
z)=-z^{-1}=-1\cdot z^{-\frac{1-\alpha}{2}}=-1\cdot\psi_{\alpha}(1/z).$

Then,

$\displaystyle(\varphi_{-1}^{\prime})^{-1}=\frac{1}{\psi^{-1}_{\alpha}\left(-1\cdot
z\right)}=\psi^{-1}_{\alpha}\left(\frac{1}{-1\cdot
z}\right)=\psi^{-1}_{\alpha}\left(-1\right)\cdot\frac{1}{\psi^{-1}_{\alpha}\left(z\right)}.=c_{\alpha}\cdot\frac{1}{\psi^{-1}_{\alpha}\left(z\right)}.$

$\bullet\quad\alpha\neq\pm 1$:

$\displaystyle\varphi_{\alpha}^{\prime}(z)=\frac{\mathrm{d}\mathrm{}}{\mathrm{d}\mathrm{}z}\left(\frac{4}{1-\alpha^{2}}\cdot\left(1-z^{\frac{1+\alpha}{2}}\right)\right)=-\frac{2}{1-\alpha}z^{\frac{\alpha-1}{2}}=-\frac{2}{1-\alpha}\cdot
z^{-\frac{1-\alpha}{2}}=-\frac{2}{1-\alpha}\cdot\psi_{\alpha}(1/z)$

Then,

$\displaystyle(\varphi_{\alpha}^{\prime})^{-1}=\frac{1}{\psi^{-1}_{\alpha}\left(-\frac{1-\alpha}{2}\cdot
z\right)}=\frac{1}{\psi^{-1}_{\alpha}\left(-\frac{1-\alpha}{2}\right)\cdot\psi^{-1}_{\alpha}\left(z\right)}=\psi^{-1}_{\alpha}\left(-\frac{2}{1-\alpha}\right)\cdot\frac{1}{\psi^{-1}_{\alpha}\left(z\right)}=c_{\alpha}\cdot\frac{1}{\psi^{-1}_{\alpha}\left(z\right)}$

∎

######  Lemma G.5.

For $\alpha=1$,

$(\varphi_{\alpha}^{\prime})^{-1}(z)=c_{\alpha}\cdot{\psi^{-1}_{\alpha}(z)}.$
(21)

###### Proof.

$\bullet\quad\alpha=1$:

$\displaystyle\varphi_{1}^{\prime}(z)=\frac{\mathrm{d}\mathrm{}}{\mathrm{d}\mathrm{}z}\left(z\log
z\right)=\log z+1$

Then,

$\displaystyle(\varphi_{-1}^{\prime})^{-1}=\exp(z-1)=\exp(-1)\cdot\exp(z)=\psi^{-1}_{1}(-1)\cdot\psi^{-1}_{1}(z)=c_{\alpha}\cdot\psi^{-1}_{\alpha}(z)$

∎

Thus now via Lemmas G.4 and G.5, we can prove the Theorems.

###### Proof of Corollaries 4.1 and 4.5.

The proof follows from utilizing either Lemmas G.4 and G.5 in conjunction with
Theorem 3.3.

$\bullet\quad\alpha=1$: We have that,

$\displaystyle\rho^{\varphi}_{\lambda}(x)$
$\displaystyle=(\varphi^{\prime})^{-1}\left(\frac{a(x)-L^{\prime}(x)+b}{\lambda}\right)$
$\displaystyle=c_{\alpha}\cdot\psi^{-1}_{\alpha}\left(\frac{a(x)-L^{\prime}(x)+b}{\lambda}\right)$
$\displaystyle=\exp\left(\frac{a(x)-L^{\prime}(x)+b-1}{\lambda}\right).$

As $\rho^{\varphi}_{\lambda}(x)$ for $\alpha=1$ is already positive by
‘$\exp$’, by complementary slackness, the Lagrange multipliers $a(\cdot)=0$.
Hence, we can further simplify the above,

$\displaystyle\rho^{\varphi}_{\lambda}(x)$
$\displaystyle=\exp\left(\frac{-L^{\prime}(x)+b-\lambda}{\lambda}\right).$

The normalizer then can be easily calculated, renaming $b^{\prime}=b-\lambda$,
we simplify have that

$\displaystyle\rho^{\varphi}_{\lambda}(x)$
$\displaystyle=\exp\left(\frac{-L^{\prime}(x)+b^{\prime}}{\lambda}\right)$
$\displaystyle=\frac{1}{\exp(-b^{\prime}/\lambda)}\cdot\exp\left(\frac{-L^{\prime}(x)}{\lambda}\right),$

which by normalization condition and setting
$Z\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\exp(-b^{\prime}/\lambda)$,

$\displaystyle 1$
$\displaystyle=\mathbb{E}\left[\frac{1}{Z}\cdot\exp\left(\frac{-L^{\prime}(x)}{\lambda}\right)\right]$
$\displaystyle\iff\quad Z$
$\displaystyle=\mathbb{E}\left[\exp\left(\frac{-L^{\prime}(x)}{\lambda}\right)\right],$

which completes the case (Corollary 4.1).

$\bullet\quad\alpha\neq 1$: We have that,

$\displaystyle\rho^{\varphi}_{\lambda}(x)$
$\displaystyle=(\varphi^{\prime})^{-1}\left(\frac{a(x)-L^{\prime}(x)+b}{\lambda}\right)$
$\displaystyle=c_{\alpha}\cdot\left(\psi^{-1}_{\alpha}\left(\frac{a(x)-L^{\prime}(x)+b}{\lambda}\right)\right)^{-1}$
$\displaystyle\overset{(a)}{=}\psi^{-1}_{\alpha}\left(\frac{2}{\alpha-1}\right)\cdot\left(\psi^{-1}_{\alpha}\left(\frac{a(x)-L^{\prime}(x)+b}{\lambda}\right)\right)^{-1}$
$\displaystyle=\psi^{-1}_{\alpha}\left(\frac{2}{\alpha-1}\right)\cdot\psi^{-1}_{\alpha}\left(\left(\frac{a(x)-L^{\prime}(x)+b}{\lambda}\right)^{-1}\right)$
$\displaystyle=\psi^{-1}_{\alpha}\left(\frac{2}{\alpha-1}\cdot\left(\frac{a(x)-L^{\prime}(x)+b}{\lambda}\right)^{-1}\right),$

where $(a)$ we exploit the that
$(\psi^{-1}_{\alpha}(z))^{-1}=\psi^{-1}_{\alpha}(1/z)$ via Lemma G.1. ∎

##  Appendix H Proof of Corollary 4.6

###### Proof.

First we simplify the density ratio rejector.

$\displaystyle\rho^{\alpha}_{\lambda}(x)$
$\displaystyle=\psi^{-1}_{\alpha}\left(\frac{2}{\alpha-1}\cdot\left(a(x)-\frac{L^{\prime}(x)}{\lambda}+b\right)^{-1}\right)$
$\displaystyle=\left(\frac{\alpha-1}{2}\cdot\left(a(x)-\frac{L^{\prime}(x)}{\lambda}+b\right)\right)^{\frac{\alpha-1}{2}}.$

We suppose that it is possible for

$\left(\frac{\alpha-1}{2}\cdot\left(a(x)-\frac{L^{\prime}(x)}{\lambda}+b\right)\right)^{\frac{\alpha-1}{2}}<0$

for values of $a(x)$, $b$, and $\lambda$. Otherwise, $\alpha(x)=0$ and we are
done due to the above equation’s non-negativity.

Let $x\in\mathcal{X}$ be arbitrary. Suppose that $a(x)=0$. Then by
complementary slackness, we have that

$\displaystyle\left(\frac{\alpha-1}{2}\cdot\left(-\frac{L^{\prime}(x)}{\lambda}+b\right)\right)^{\frac{\alpha-1}{2}}>0\iff$
$\displaystyle\quad b-\frac{L^{\prime}(x)}{\lambda}>0.$

By contra-positive, we have that $b-L^{\prime}(x)/\lambda\leq 0$ implies that
$a(x)\neq 0$. By prime feasibility, in this case we also have $\rho(x)=0$. We
can solve either case by using the maximum as stated. ∎

##  Appendix I Proof of Corollary 4.7

###### Proof of Corollary 4.6.

The proof directly follows from a property of the $\alpha$-divergence when one
of the measure have disjoint support. From [3] we have.

######  Theorem I.1 (Amari [3, Section 3.4.1 (4)]).

For $\alpha$-divergences, we have that

  1. 1.

For $\alpha\leq-1$, $D_{\alpha}(\mathrm{P}\mathrel{\|}\mathrm{Q})=\infty$ when
$\mathrm{P}(x)\neq 0$ and $\mathrm{Q}(x)=0$ for some $x\in\mathcal{X}$.

This result immediately gives the result, as otherwise the objective function
is $\infty$. ∎

##  Appendix J Proof of Corollary 4.8

###### Proof.

We first note simplifying $\rho^{\alpha=3}_{\lambda}$ via Corollary 4.6
yields:

$\rho^{\alpha=3}_{\lambda}(x)=\max\left\\{0,b-\frac{L^{\prime}(x)}{\lambda}\right\\}.$

Thus our goal is to solve $b$ to give
$\mathbb{E}_{\mathrm{P}}[\rho^{\alpha=3}_{\lambda}(\mathsf{X})]=1$.

Now, consider the following,

$\displaystyle
1+\frac{\mathbb{E}_{\mathrm{P}}\left[L^{\prime}(\mathsf{X})\right]}{\lambda}-\frac{L^{\prime}(x)}{\lambda}>0\iff\lambda>L^{\prime}(x)-\mathbb{E}_{\mathrm{P}}\left[L^{\prime}(\mathsf{X})\right],$

where the latter holds uniformly for all $x$ from assumptions on $\lambda$.

Thus setting
$b=1+\frac{\mathbb{E}_{\mathrm{P}}\left[L^{\prime}(\mathsf{X})\right]}{\lambda}$,
we simplify

$\displaystyle\int\max\left\\{0,1+\frac{\mathbb{E}_{\mathrm{P}}\left[L^{\prime}(\mathsf{X})\right]}{\lambda}-\frac{L^{\prime}(\mathsf{X})}{\lambda}\right\\}\mathrm{d}\mathrm{P}(x)$
$\displaystyle=\int
1+\frac{\mathbb{E}_{\mathrm{P}}\left[L^{\prime}(\mathsf{X})\right]}{\lambda}-\frac{L^{\prime}(\mathsf{X})}{\lambda}\mathrm{d}\mathrm{P}(x)$
$\displaystyle=1.$

As such,
$b=1+\frac{\mathbb{E}_{\mathrm{P}}\left[L^{\prime}(\mathsf{X})\right]}{\lambda}$
solves the required normalization. Substituting $b$ back into
$\rho^{\alpha=3}_{\lambda}(x)$ yields the Theorem. ∎

##  Appendix K Proof of Theorem 4.9

###### Proof.

First we note that for any meas $\mathrm{R}$, $\lambda>2B$ implies that
$\lambda>L^{\prime}(x)-\mathbb{E}_{\mathrm{R}}\left[L^{\prime}(\mathsf{X})\right]$
(taking largest and smallest values of $\ell$.

As such, for both $\mathrm{P},{\hat{\mathrm{P}}}$ have closed forms Corollary
4.8

Thus, the bound can be simply shown to have,

$\displaystyle|\rho^{\alpha=3}_{\lambda}(x)-\hat{\rho}^{\alpha=3}_{\lambda}(x)|$
$\displaystyle=\frac{1}{\lambda}\cdot\left|\mathbb{E}_{\mathrm{P}}\left[L^{\prime}(\mathsf{X})\right]-\mathbb{E}_{\hat{\mathrm{P}}}\left[L^{\prime}(\mathsf{X})\right]\right|.$

Thus by Hoeffding’s inequality Theorem F.1 and union bound (see for instance
the proof of Theorem 4.3), setting
$t=B\cdot\sqrt{\frac{2}{N}\log\left(\frac{2M}{\delta}\right)}$, we have that
with probability $1-\delta$ for all $x\in\mathcal{T}$,

$\displaystyle|\rho^{\alpha=3}_{\lambda}(x)-\hat{\rho}^{\alpha=3}_{\lambda}(x)|\leq\frac{B}{\lambda}\cdot\sqrt{\frac{2}{N}\log\left(\frac{2M}{\delta}\right)}.$

As required. ∎

##  Appendix L Broader Impact

The paper presents work which reinterprets the classification with rejection
problem in terms of learning distributions and density ratios. Beyond
advancing Machine Learning in general, potential societal consequences include
enhancing the understanding of the rejection paradigm and, consequentially,
the human-in-the-loop paradigm. The general rejection setting aims to prevent
models from making prediction when they are not confident, which can have
societal significance when deployed in high stakes real life scenarios —
allowing for human intervention.

##  Appendix M Distribution Generalization Bounds

In the following, we seek to provide generalization bounds on
${\hat{\mathrm{Q}}}_{\lambda,N}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}{\hat{\mathrm{P}}}_{N}\cdot\hat{\rho}_{\lambda,N}$.
That is, one seeks to know that as $N\rightarrow\infty$ how and if
${\hat{\mathrm{Q}}}_{\lambda,N}\rightarrow\mathrm{Q}$. A natural measure of
distance for probability measures is _total variation_ [20],

$\textsc{TV}(\mathrm{P},\mathrm{Q})\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\frac{1}{2}\cdot\|\mathrm{P}-\mathrm{Q}\|_{1}=\int|\mathrm{Q}(x)-\mathrm{P}(x)|\;\mathrm{d}\mathrm{}x.$

Let us also define

$\|\mathrm{P}-\mathrm{Q}\|_{\infty}=\sup_{x\in\mathcal{X}}|\mathrm{Q}(x)-\mathrm{P}(x)|.$

One immediately gets a rate if we assume that $|\mathcal{X}|$ is finite and we
have a bound for $\hat{\rho}_{\lambda,N}$.

######  Theorem M.1.

Suppose that $|\mathcal{X}|=M<\infty$ is finite and bounded density ratio
$|\hat{\rho}_{\lambda,N}|\leq B^{\prime}$ for $B^{\prime}>0$. Then, if we have
that with probability $1-\delta$ that ,

$\|\rho(x)-\hat{\rho}_{N,\lambda}(x)\|_{\infty}\leq
C\cdot\left(\sqrt{\frac{1}{N}\cdot\log\frac{2M}{\delta}+C^{\prime}}\right),$

for some $C,C^{\prime}>0$, then we have that

$\textsc{TV}(\mathrm{Q},\hat{\mathrm{Q}}_{\lambda,N})=\mathcal{O}\left(\sqrt{\frac{M^{2}\log
M}{N}}\right).$ (22)

###### Proof.

Noting that the empirical distribution is a sum of Dirac deltas
$\hat{\mathrm{P}}_{N}(x)=\sum_{i\in[N]}\delta(x-x_{i})$, we can establish a
simple bound via a consequence of Hoeffding’s Theorem Theorem F.1 (also noting
that $\mathrm{P}=\mathbb{E}\hat{\mathrm{P}}_{N}$). We have that,

$\displaystyle\Pr(|\mathrm{P}(x)-\hat{\mathrm{P}}_{N}(x)|\geq t)\leq
2\exp\left(-2Nt^{2}\right).$

Thus,

$\displaystyle\Pr(\forall
x\in\mathcal{X}:|\mathrm{P}_{N}(x)-\hat{\mathrm{P}}_{N}(x)|\geq t)\leq
2M\exp\left(-2Nt^{2}\right).$

Setting $t=\sqrt{\frac{1}{2N}\log\frac{2M}{\delta}}$, we have with probability
$1-\delta$

$\|\mathrm{P}-\hat{\mathrm{P}}_{N}\|_{\infty}\leq\sqrt{\frac{1}{2N}\log\frac{2M}{\delta}}.$

We now consider the following:

$\displaystyle\|\mathrm{Q}-\hat{\mathrm{Q}}_{\lambda,N}\|_{\infty}$
$\displaystyle=\|\mathrm{P}\cdot\mathrm{\rho}-\hat{\mathrm{P}}_{N}\cdot\hat{\rho}_{\lambda,N}\|_{\infty}$
$\displaystyle=\|\mathrm{P}\cdot(\mathrm{\rho}-\hat{\mathrm{\rho}_{\lambda,N}})+(\mathrm{P}-\hat{\mathrm{P}}_{N})\cdot\hat{\rho}_{\lambda,N}\|_{\infty}$
$\displaystyle\leq\|\mathrm{P}\cdot(\mathrm{\rho}-\hat{\mathrm{\rho}}_{\lambda,N})\|_{\infty}+\|(\mathrm{P}-\hat{\mathrm{P}}_{N})\cdot\hat{\rho}_{\lambda,N}\|_{\infty}$
$\displaystyle\leq\|(\mathrm{\rho}-\hat{\mathrm{\rho}}_{\lambda,N})\|_{\infty}+B^{\prime}\cdot\|(\mathrm{P}-\hat{\mathrm{P}}_{N})\|_{\infty}.$

Taking a union bound of the above inequality and our assumption, we have that,
for some $C>0$, with probability $1-\delta$,

$\displaystyle\|\mathrm{Q}-\hat{\mathrm{Q}}_{\lambda,N}\|_{\infty}$
$\displaystyle\leq\|(\mathrm{\rho}-\hat{\mathrm{\rho}}_{\lambda,N})\|_{\infty}+B^{\prime}\cdot\|(\mathrm{P}-\hat{\mathrm{P}}_{N})\|_{\infty}$
$\displaystyle\leq
C\cdot\sqrt{\frac{1}{N}\log\frac{4M}{\delta}+C^{\prime}}+B^{\prime}\cdot\sqrt{\frac{1}{2N}\log\frac{4M}{\delta}}$
$\displaystyle=\mathcal{O}\left(\sqrt{\frac{\log M}{N}}\right).$

Converting the bound to TV amounts to simply summing over $\mathcal{X}$, which
gives
$\textsc{TV}(\mathrm{Q},\hat{\mathrm{Q}}_{\lambda,N})=\mathcal{O}(\sqrt{(M^{2}\log
M)/N})$, as required. ∎

Notably, with appropriate assumptions, Theorems 4.3 and 4.9 can be used with
Theorem M.1 to get bounds for $\hat{\mathrm{Q}}^{\textsc{KL}}_{\lambda,N}$ and
$\hat{\mathrm{Q}}^{\alpha=3}_{\lambda,N}$.

##  Appendix N Rejection for Regression

In the main-text of the paper we have focused on classification. However, many
of the idea discussed can be extended for the regression setting. For
instance, similar to Chow’s Rule in Theorem 2.1 we can express the regression
equivalent to the optimal solution of Eq. 2.

######  Theorem N.1 (Optimal Regression Rejection [58]).

Let us consider the regression setting, where
$\mathcal{Y}=\mathcal{Y}^{\prime}=\mathbb{R}$ and
$\ell(y,y^{\prime})=\frac{1}{2}(y-y^{\prime})^{2}$. Then w.r.t. Eq. 2, the
optimal model is given by
$h^{\star}(x)=\mathbb{E}_{\mathrm{P}}[\mathsf{Y}\mid\mathsf{X}=x]$ and the
optimal rejector is given by $r^{\star}(x)=\llbracket\sigma^{2}(x)\leq
c\rrbracket$, where $\sigma^{2}(x)$ is the conditional variance of
$\mathsf{Y}$ given $\mathsf{X}=x$.

For regression, there is no clear analogous notion of output “confidence
score” unless the model explicitly outputs probabilities. Indeed, rejection
method for regression explicitly requires the estimation of the target
variable’s conditional variance [58].

Similar to the CPE case, our KL density ratio rejector can provide a rejection
policy equivalent to the typical case.

######  Theorem N.2.

Given the regression setting presented in Theorem N.1 and that we are given
optimal regressor
$h^{\star}(x)=\mathbb{E}_{\mathrm{P}}[\mathsf{Y}\mid\mathsf{X}=x]$, for any
$\lambda>0$ there exists a $\tau>0$ such that the $r^{\textsc{KL}}_{\tau}$
rejector generated the optimal density ratio in Corollary 4.1 is equivalent to
the optimal rejector in Theorem N.1.

###### Proof.

The proof follows similarly to the proof of Theorem E.1. The regression case
follows almost identically, by noticing that $L^{\prime}(x)=\sigma^{2}(x)$ is
the variance. This is similar to the proof of Theorem N.1 [58]. ∎

Despite the equivalence, there is a difficult in using the density ratio
rejectors, as per the closed form equations of Section 4, for regression.
Estimating $L^{\prime}(x)=\sigma^{2}(x)$ is challenging. Unlike classification
where learning calibrated classifiers has a variety of approaches, learning a
regression model which explicitly outputs probabilities is quite difficult. As
such, approximating $\mathrm{P}(\mathsf{Y}\mid\mathsf{X}=x)$ with the model
$h(x)$ cannot be done.

##  Appendix O Gradient of Density Ratio Objective

As an alternative to the closed-form rejectors explored in the main-text, one
may want to explore a method to learn $\rho$ iteratively. We consider the
gradients of the optimization problem in Eq. 9. In practice, we found that we
were unable to learn such rejectors via taking gradient updates and thus leave
a concrete implementation of the idea for future work.

The idea comes from utilizing the “variational” aspect of the GVI formulation
(which was not explored in the main-text). We suppose that the rejectors we
are interested in come from a parameterized family. In particular, we consider
the self-normalizing family $\rho_{\vartheta}/Z_{\vartheta}$, where
$Z_{\vartheta}=\mathbb{E}_{\mathrm{P}}[\pi_{\vartheta}(\mathsf{X})]$
normalizes the rejector such that
$\mathbb{E}_{\mathrm{P}}[\rho_{\vartheta}(\mathsf{X})]=1$. Having the
$Z_{\vartheta}$ normalizing term means that the constraint in Eq. 9 is
satisfied for any $\vartheta$. The only constraint that we must have for
$\pi_{\vartheta}$ is non-negativity, _i.e_., $\pi_{\vartheta}$ is a neural
network with exponential last activation functions from
$\mathcal{X}\rightarrow\mathbb{R}_{+}$. By setting a parametric form of
$\rho_{\vartheta}$, we implicitly restrict the set of idealized distributions
to $\mathrm{Q}_{\vartheta}=\mathrm{P}\cdot\rho_{\vartheta}$. The gradients of
such a parametric form can be calculated as follows.

######  Corollary O.1.

Let $\rho_{\vartheta}=\pi_{\vartheta}(x)/Z_{\vartheta}$. Then the gradient of
Eq. 9 w.r.t. $\vartheta$ is given by,

$\mathbb{E}_{\mathrm{P}_{\rm x,\rm
y}}\left[\nabla_{\vartheta}\left(\frac{\mathrm{\pi}_{\vartheta}(\mathsf{X})}{Z_{\vartheta}}\right)\cdot\left(\varphi^{\prime}\left(\frac{\mathrm{\pi}_{\vartheta}(\mathsf{X})}{Z_{\vartheta}}\right)+\lambda\cdot\ell(\mathsf{Y},h(\mathsf{X}))\right)\right].$
(23)

###### Proof.

The proof is immediate from differentiation of Eq. 9. ∎

An alternative form of Eq. 23 can be found by noticing that $\nabla
f=f\cdot\nabla\log f$. This provides an expression in terms of the log density
ratio.

$\mathbb{E}_{\mathrm{P}_{\rm x,\rm
y}}\left[\frac{\mathrm{\pi}_{\vartheta}(\mathsf{X})}{Z_{\vartheta}}\cdot\nabla_{\vartheta}\log\left(\frac{\mathrm{\pi}_{\vartheta}(\mathsf{X})}{Z_{\vartheta}}\right)\cdot\left(\varphi^{\prime}\left(\frac{\mathrm{\pi}_{\vartheta}(\mathsf{X})}{Z_{\vartheta}}\right)+\lambda\cdot\ell(\mathsf{Y},h(\mathsf{X}))\right)\right].$

One will notice that the gradient is in-fact the log-likelihood of the
idealized distribution: noting $\mathrm{P}$ free of $\vartheta$, we have
$\nabla_{\vartheta}\log(\pi_{\vartheta}(\mathsf{X})/Z_{\vartheta})=\nabla_{\vartheta}\log(\mathrm{P}(\mathsf{X})\cdot\pi_{\vartheta}(\mathsf{X})/Z_{\vartheta})=\nabla_{\vartheta}\log\mathrm{Q}_{\vartheta}$.
As such, the gradient Eq. 23 is equivalent to the gradient of a weighted log-
likelihood.

Despite the potential nice form of the gradient, we found that learning
rejector through this was not possible. One limiting factor of computing such
gradients is that we need to estimate $Z_{\vartheta}$ at each gradient
calculation, _i.e_., this must happen whenever $\vartheta$ changes. This can
be particularly costly when $\mathcal{X}$ is high-dimensional. Secondly, we
suspect that the model capacity of $\pi_{\vartheta}$ was not sufficient: we
only tested on simple neural networks and convolutions neural networks,
mirroring the architecture of the base classifiers used in our experimental
setting.

##  Appendix P Additional Experimental Details

###  P.I Training Settings

The neural network architecture used to train the base classifiers and
baselines are almost identical. For the baseline approaches which have output
dimension which is different than the output of the original neural network,
we modify the last linear layer of the base classifier’s architecture to fit
the baseline’s requirements, _e.g_., adding an additional output dimension for
rejection in DEFER. Our architectures utilize batch normalization [32] and
dropout [53] in a variety of places. Training settings are mostly identical,
with some baselines requiring slight changes.

The base model’s architecture is as follows.

  * •

HAR (CC BY 4.0): We utilize a two hidden layer neural network with batch
normalization. Both hidden layer is $64$ neurons and the activation function
is the sigmoid function. We take a 64 batch size, 40 training epochs and a
0.0001 learning rate.

  * •

Gas Drift (CC BY 4.0): We utilize a two hidden layer neural network with batch
normalization. Both hidden layers are $64$ neurons and the activation function
is the sigmoid function. We take a 64 batch size, 40 training epochs and a
0.0001 learning rate.

  * •

MNIST (CC BY-SA 3.0): We utilize a convolutional neural network with two
convolutional layers and two linear layers. The architecture follows directly
from the MNIST example for PyTorch. We utilize the sigmoid function activation
function. We take a 256 batch size, 40 training epochs and a 0.0001 learning
rate.

For CSS, as noted in Ni et al. [44], batch normalization is needed at the
final layer to stabilize training.

All training utilizes the Adam [33] optimizer.

All datasets we consider are in the public domain, _e.g_., UCI [6].

###  P.II Extended Plots

Plots Figs. I, II and III show Fig. 2 over and extend region of acceptable
coverage percentages. In addition, we include a larger range of noise rates
for HAR and Gas Drift. For MNIST, we explore a larger range of noise rates for
MNIST in Fig. IV for our density ratio rejectors. We find that the findings in
the main text are extended to these additional noise rates. In particular, we
find that the our density ratio rejectors can be competitive with the various
baseline approaches. We find that our density ratio approaches can have more
fine-grained trade-offs at higher ranges of acceptance coverage. This is an
important region where the budge for rejection may be low (and only a few
examples, _e.g_. $<10\%$, can be rejected). Indeed, the baseline approaches
which do not ‘wrap’ a base model require a lower _maximum acceptance coverage_
as the noise rate increases (the approaches require a higher rejection % for
any type of rejection). Nevertheless, we do see a downside of the density
ratio approach: the quality of the density ratio rejectors is dependent on the
initial model. As such, at higher levels of noise there can be higher
variation in the quality of rejection, see Fig. II. Interestingly, for MNIST
the base model the density ratio rejectors are more robust across noise rates
than other models. This seems to be due to the default MNIST architecture
being robust against higher noise rates (notice that the s.t.d. range is also
quite small at 100% coverage).

Figure I: Extended plots for HAR of Fig. 2. Figure II: Extended plots for Gas
Drift of Fig. 2. Figure III: Extended plots for MNIST of Fig. 2. Figure IV:
MNIST with different noises for density ratio approaches.

###  P.III Smaller models case study

In the following, we consider the Gas Drift dataset when models are switched
to a base model with only a single hidden layer. First we make note of the
original setting explored in the main text. In Table I, we take note of the
number of tunable parameters in all approaches and baselines. Notably, these
default parameter / architecture sizes are similar to [14], with the HAR and
Gas Drift setting including an additional hidden layer than previously
utilized in the literature.

Table I: Default parameter sizes of experiments. Dataset | BaseClf | $\alpha\rm{-Rej}$ | $\rm DEFER$ | $\rm GCE$ | $\rm CSS$ | $\rm PredRej$
---|---|---|---|---|---|---
HAR | 40,647 | 40,648 | 40,646 | 40,711 | 40,711 | 80,968
Gas Drift | 12,935 | 12,936 | 12,934 | 12,999 | 12,999 | 25,544
MNIST | 1,199,883 | 1,199,884 | 1,200,138 | 1,200,011 | 1,200,267 | 2,398,860

In Table II, we note the setting we consider in this subsection. The parameter
sizes of the Gas Drift dataset is reduced to the originally explored model
sizes in Charoenphakdee et al. [14]. Notice that both the base models and the
baseline approaches have reduced parameter sizes. It should be noted that this
smaller parameter size setting can be useful in the related learning with
deferral setting [43], where having a small model to defer to a larger model
is needed.

Table II: Alternative parameter sizes of experiments. Dataset | BaseClf | $\alpha\rm{-Rej}$ | $\rm DEFER$ | $\rm GCE$ | $\rm CSS$ | $\rm PredRej$
---|---|---|---|---|---|---
HAR | 36,487 | 36,488 | 36,486 | 36,551 | 36,551 | 72,648
Gas Drift | 8,775 | 8,776 | 8,774 | 8,839 | 8,839 | 17,224

The results are reported in Figs. V and VI. We can see that in this setting,
PredRej and our density ratio approaches are more competitive. This might
indicate that for simple base models, approaches which ‘wrap’ a base model for
rejection can be quite effective (especially in higher coverage regimes). In
general, it seems with this smaller architecture regime, the ‘non-wrapping’
baseline approaches only provide rejection options when the acceptance
coverage is lower than $70\%$.

Figure V: Plots for HAR with smaller models. Figure VI: Plots for Gas Drift
with smaller models.

###  P.IV Parameter sweeps over $\alpha$ and $\lambda$

The following shows parameter sweeps over $\alpha$ and $\lambda$ for our
density ratio rejectors. These are given by Figs. VII and VIII respectively.
We find that increasing $\alpha$ compresses the trade-off curve from both
sides. While decrease $\lambda$ extends the trade-off curve on the left side.

Figure VII: $\alpha$ parameter sweep over dataset + noise combinations. S.t.d.
shade is not utilized, but instead end points of the trade-off curves for
$\tau\in(0,1]$ are shown via vertical bars Figure VIII: $\lambda$ parameter
sweep over dataset + noise combinations for KL rejector. S.t.d. shade is not
utilized, but instead end points of the trade-off curves for $\tau\in(0,1]$
are shown via vertical bars