# Bagging Provides Assumption-free Stability

Jake A. Soloff  Department of Statistics, University of Chicago  Rina Foygel
Barber  Department of Statistics, University of Chicago  Rebecca Willett
Department of Statistics, University of Chicago  Department of Computer
Science, University of Chicago

###### Abstract

Bagging is an important technique for stabilizing machine learning models. In
this paper, we derive a finite-sample guarantee on the stability of bagging
for any model. Our result places no assumptions on the distribution of the
data, on the properties of the base algorithm, or on the dimensionality of the
covariates. Our guarantee applies to many variants of bagging and is optimal
up to a constant. Empirical results validate our findings, showing that
bagging successfully stabilizes even highly unstable base algorithms.

##  1 Introduction

Algorithmic stability—that is, how perturbing training data influences a
learned model—is fundamental to modern data analysis. In learning theory,
certain forms of stability are necessary and sufficient for generalization
(Bousquet and Elisseeff,, 2002; Poggio et al.,, 2004; Shalev-Shwartz et al.,,
2010). In model selection, stability measures can reliably identify important
features (Meinshausen and Bühlmann,, 2010; Shah and Samworth,, 2013; Ren et
al.,, 2021). In scientific applications, stable methods promote
reproducibility, a prerequisite for meaningful inference (Yu,, 2013). In
distribution-free prediction, stability is a key assumption for the validity
of jackknife prediction intervals (Barber et al.,, 2021; Steinberger and
Leeb,, 2023).

Anticipating various benefits of stability, Breiman, 1996a ; Breiman, 1996b
proposed bagging as an ensemble meta-algorithm to stabilize any base learning
algorithm. Bagging, short for bootstrap aggregating, refits the base algorithm
to many perturbations of the training data and averages the resulting
predictions. Breiman’s vision of bagging as off-the-shelf stabilizer motivates
our main question: _How stable is bagging on an arbitrary base algorithm,
placing no assumptions on the data generating distribution?_ In this paper, we
first answer this question for the case of base algorithms with bounded
outputs and then show extensions to the unbounded case.

Figure 1: Distribution of leave-one-out perturbations for logistic regression
(red) and subbagged logistic regression (blue), with $n=500$ and $d=250$. (See
Section 6 for details on this simulation.)

###  1.1 Preview of Main Results

We will study the following notion of algorithmic stability:

######  Definition 1 (Stability—informal version).

An algorithm is $(\varepsilon,\delta)$-stable if, for any training data set
$\mathcal{D}$ with $n$ data points, and any test point $x$,

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\mathbf{1}\left\\{|\hat{f}(x)-\hat{f}^{\setminus
i}(x)|>\varepsilon\right\\}\leq\delta,$ (1)

where $\hat{f}$ is the model trained on the entire data set $\mathcal{D}$,
while $\hat{f}^{\setminus i}$ is trained on the data set $\mathcal{D}$ with
the $i$th data point removed.

In other words, this definition requires that, for any data set, if we drop
one training point at random, then the resulting prediction produced by the
algorithm is typically insensitive to this perturbation of the training data.

It is well known that, empirically, bagging and other ensembling procedures
tend to improve the stability of an unstable base algorithm. For example,
Figure 1 shows the histograms of leave-one-out perturbations
$|\hat{f}(x)-\hat{f}^{\setminus i}(x)|$ for two different algorithms: logistic
regression and logistic regression with subbagging (given by
$\hat{f}_{B}(x):=\frac{1}{B}\sum_{b=1}^{B}\hat{f}^{(b)}(x)$, where each
$\hat{f}^{(b)}$ is a model fitted on $m=n/2$ out of $n$ training data points
sampled at random without replacement). We can clearly see that this
perturbation is often far larger for logistic regression than for its
subbagged version.

In this paper, we prove that stability (in the sense of Definition 1) is
automatically achieved by the bagged version of any algorithm—with no
assumptions on either the algorithm itself or on the training and test data,
aside from requiring that the output predictions lie in a bounded range. A
special case of our main result can be informally summarized as follows:

######  Theorem 2 (Main result—informal version).

Fix any algorithm with bounded output, and consider its subbagged version with
$m$ samples drawn without replacement,

$\hat{f}_{B}(x):=\frac{1}{B}\sum_{b=1}^{B}\hat{f}^{(b)}(x),$

where $B$ is sufficiently large. Then the subbagged algorithm satisfies
Definition 1 for any pair $(\varepsilon,\delta)$ satisfying

$\delta\varepsilon^{2}\gtrsim\frac{1}{n}\cdot\frac{p}{1-p}$ (2)

where $p=\frac{m}{n}$.

(The formal version of Theorem 2, including many other forms of bagging, can
be found in Section 4 below. We extend our main result to the unbounded case
in Section 5.)

In the existing literature, relatively little is known about bagging’s
stabilization properties without additional assumptions on the base
algorithm.111We defer a more extensive discussion of prior work in this area
to Section 7.3. In this work, our stability guarantees (previewed in Theorem
2) will:

  * •

apply to general base algorithms which may be highly unstable,

  * •

hold for finite sample sizes,

  * •

provide bounds that are optimal (up to constants), and

  * •

hold deterministically, allowing for out-of-distribution test points and non-
exchangeable data.

##  2 Algorithmic Stability

Consider a supervised learning setting with real responses. Formally, a
learning algorithm $\mathcal{A}$ is a function that inputs a data set
$\mathcal{D}=(Z_{i})_{i=1}^{n}$ of pairs $Z_{i}=(X_{i},Y_{i})$ of covariates
$X_{i}\in\mathcal{X}$ and responses $Y_{i}\in\mathcal{Y}$ and an auxiliary
random variable $\xi\sim\textnormal{Unif}([0,1])$ and produces a fitted
regression function $\hat{f}:\mathcal{X}\to\hat{\mathcal{Y}}$, given by
$\hat{f}=\mathcal{A}\Big{(}\mathcal{D};\xi\Big{)}$. While many results in the
literature consider only symmetric algorithms $\mathcal{A}$ (i.e., invariant
to the ordering of the $n$ training points in $\mathcal{D}$), here we do not
constrain $\mathcal{A}$ to be symmetric.

The auxiliary random variable $\xi$ may be viewed as a random seed, allowing
for randomization in $\mathcal{A}$, if desired. For example, in many
applications, we may wish to optimize an objective such as empirical risk, and
then the resulting algorithm $\mathcal{A}$ consists of the specific numerical
operations applied to the training data—e.g., $T$ steps of stochastic gradient
descent (SGD) with a specific learning rate and batch size, with the random
seed $\xi$ used for drawing the random batches in SGD. Our notation also
allows for deterministic algorithms, since $\mathcal{A}$ is free to ignore the
input argument $\xi$ and depend only on the data.

There are many ways to define the stability of a learning algorithm. As noted
by Shalev-Shwartz et al., (2010), every definition of stability quantifies the
sensitivity of the output of $\mathcal{A}$ to small changes in the training
set $\mathcal{D}$, but they all define ‘sensitivity of the output’ and ‘small
changes in the training set’ differently. We present our main results for two
definitions of stability and extend our results to many related notions in
Section 5.3. One of the strongest possibilities is to require, for all data
sets and all test points, that every prediction be insensitive to dropping any
single observation. The following definition is closely related to _uniform
prediction stability_ (see, e.g., Dwork and Feldman,, 2018).

######  Definition 3.

An algorithm $\mathcal{A}$ is worst-case $(\varepsilon,\delta)$-stable if, for
all data sets $\mathcal{D}=(Z_{i})_{i=1}^{n}$ and test points
$x\in\mathcal{X}$,

$\displaystyle\max_{i\in[n]}\mathbb{P}_{\xi}\left\\{|\hat{f}(x)-\hat{f}^{\setminus
i}(x)|>\varepsilon\right\\}\leq\delta,$ (3)

where $\hat{f}=\mathcal{A}(\mathcal{D};\xi)$, $\hat{f}^{\setminus
i}=\mathcal{A}(\mathcal{D}^{\setminus i};\xi)$ and $\mathcal{D}^{\setminus
i}=(Z_{j})_{j\neq i}$.

In many settings, however, this requirement is too stringent, since it forces
$\mathcal{A}$ to be stable even when the most influential observation is
dropped. A relaxation of this definition is the notion of average-case
stability, where the perturbation comes from dropping one observation at
random. Since we are primarily interested in average-case stability in this
paper, we will refer to it simply as ‘$(\varepsilon,\delta)$-stable’.

######  Definition 4.

An algorithm $\mathcal{A}$ is $(\varepsilon,\delta)$-stable if, for all data
sets $\mathcal{D}=(Z_{i})_{i=1}^{n}$ and test points $x\in\mathcal{X}$,

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\mathbb{P}_{\xi}\left\\{|\hat{f}(x)-\hat{f}^{\setminus
i}(x)|>\varepsilon\right\\}\leq\delta,$ (4)

where $\hat{f}=\mathcal{A}(\mathcal{D};\xi)$, $\hat{f}^{\setminus
i}=\mathcal{A}(\mathcal{D}^{\setminus i};\xi)$ and $\mathcal{D}^{\setminus
i}=(Z_{j})_{j\neq i}$.

This is the formal version of Definition 1, stated informally earlier—the
difference here (aside from introducing notation) lies in the presence of the
randomization term $\xi$.

The terminology ‘ _$\mathcal{A}$ is $(\varepsilon,\delta)$-stable_’ in
Definition 4 (or ‘$\mathcal{A}$ is worst-case $(\varepsilon,\delta)$-stable,
in Definition 3) suppresses the dependence on the sample size $n$. Since we
are performing a non-asymptotic stability analysis, we treat $n$ as a fixed
positive integer throughout.

Clearly, Definition 4 is implied by Definition 3, but not vice versa; average-
case stability thus relaxes worst-case stability to allow some small fraction
of observations to have large leave-one-out perturbation. Average-case
stability is a more permissive condition, and yet it is often sufficient for
statistical inference. Indeed, if data points $Z_{i}$ are exchangeable and
$\mathcal{A}$ is symmetric, Condition (4) implies

$\mathbb{P}_{\mathcal{D},X_{n+1},\xi}\left\\{|\hat{f}(X_{n+1})-\hat{f}^{\setminus
i}(X_{n+1})|>\varepsilon\right\\}\leq\delta$

for all $i$ and for a new test point $X_{n+1}$, which is the condition of
“out-of-sample stability” used by papers on distribution-free prediction
mentioned in Section 1 (when $Z_{n+1}=(X_{n+1},Y_{n+1})$ is a new test point
that is exchangeable with the training data). Of course, our definition is a
stronger property, as it is required to hold uniformly over any training set
and any test point.

In fact, worst-case stability ensures an even stronger property—for a training
sample $Z_{1},\dots,Z_{n}$, it must hold that

$\mathbb{P}_{\mathcal{D},\xi}\left\\{|\hat{f}(X_{i})-\hat{f}^{\setminus
i}(X_{i})|>\varepsilon\right\\}\leq\delta$

which is sometimes known as “in-sample stability”; informally, this bound
implies that $\hat{f}$ is not “overfitted” to the training data, since its
prediction $\hat{f}(X_{i})$ at the $i$th training point is only slightly
influenced by $Z_{i}$. On the other hand, average-case stability is not
sufficient to ensure this type of bound, even on average over $i=1,\ldots,n$.

In many lines of the literature it is more standard to define stability with
respect to a loss function $\ell(\hat{f}(x),y)$. Define
$(\varepsilon,\delta)$-stability with respect to the loss $\ell$ as

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\mathbb{P}_{\xi}\left\\{|\ell(\hat{f}(x),y)-\ell(\hat{f}^{\setminus
i}(x),y)|>\varepsilon\right\\}\leq\delta.$

If an algorithm $\mathcal{A}$ is $(\varepsilon,\delta)$-stable in the sense of
Definition 4, then it is $(\varepsilon/L,\delta)$-stable with respect to any
loss function $\ell$ that is $L$-Lipschitz in its first argument. Hence, our
stability guarantees immediately apply to any Lipschitz loss.222Assuming the
loss $\ell$ is Lipschitz is standard in the literature—see, e.g., Elisseeff et
al., (2005); Hardt et al., (2016).

Similarly, in the stability literature, it is more standard to control the
expected value of the leave-one-out perturbation
$|\hat{f}(x)-\hat{f}^{\setminus i}(x)|$ rather than controlling a tail
probability. However, tail bounds can be easily converted to bounds in
expectation using the standard identity

$\mathbb{E}\left|\hat{f}(x)-\hat{f}^{\setminus
i}(x)\right|=\int_{0}^{\infty}\mathbb{P}\left\\{|\hat{f}(x)-\hat{f}^{\setminus
i}(x)|>\varepsilon\right\\}\text{d}\varepsilon.$

In Section 5.3, we define various related notions of stability more formally,
and will consider the implications of our main result for these alternative
definitions of stability.

##  3 Bagging and its Variants

Bagging has a rich history in the machine learning literature (Breiman, 1996a,
; Dietterich,, 2000; Valentini and Masulli,, 2002) and is widely used in a
variety of practical algorithms; random forests are a notable example
(Breiman,, 2001).

The theoretical properties of bagging have also been widely explored. For
example, the stabilization properties of bagging have been studied for some
specific base algorithms, such as trees (Basu et al.,, 2018) or $k$-means
(Ben-David et al.,, 2007). Poggio et al., (2002) compared the stabilizing
properties of bagging to those of ridge regression; LeJeune et al., (2020,
2022) recently established some deeper connections between the asymptotic
risks of bagging and ridge regression. Additional prior works have addressed
the stability of bagging by proving that bagging, under certain conditions,
increases the stability of an already stable algorithm (Elisseeff et al.,,
2005). In contrast, our results establish stability for bagging when applied
to an arbitrary (and possibly highly unstable) base algorithm. We defer a more
detailed discussion of prior work in this area to Section 7.3, where we will
be able to compare to our own results.

Bagging applies resampling methods to reduce variance, smooth discontinuities,
and induce stability in a base algorithm $\mathcal{A}$. The meta-algorithm
repeatedly samples ‘bags’ from the training data $\mathcal{D}$, runs the base
algorithm $\mathcal{A}$ on each bag, and averages the resulting models.
Different resampling methods lead to some common variants:

  * •

Classical bagging (Breiman, 1996a, ; Breiman, 1996b, ) samples $m$ indices
with replacement from $[n]=\\{1,\dots,n\\}$.

  * •

Subbagging (Andonova et al.,, 2002) samples $m$ indices without replacement
from $[n]$ (where $m\leq n$).

We distinguish ‘classical bagging,’ which employs sampling with replacement,
from the more general ‘bagging,’ which we use to refer to any resampling
method. For classical bagging, Breiman, 1996a ; Breiman, 1996b  originally
proposed using the nonparametric bootstrap (Efron,, 1979), i.e., $m=n$, but
$m\ll n$ is often computationally advantageous.

In both of the above strategies, because there are exactly $m$ observations in
each bag, this induces weak negative correlation between observations (i.e.,
between the event that data point $i$ is in the bag, and that data point $j$
is in the bag). Randomizing the size of each bag is a standard trick that
decorrelates these events:

  * •

Poissonized bagging (Oza and Russell,, 2001; Agarwal et al.,, 2014) samples
$M$ indices with replacement from $[n]$, where $M\sim\textnormal{Poisson}(m)$.

  * •

Bernoulli subbagging (Harrington,, 2003) samples $M$ indices without
replacement from $[n]$, where $M\sim\textnormal{Binomial}(n,\frac{m}{n})$.

Our stability results are quite flexible to the choice of resampling method,
and in particular, apply to all four methods described above. In order to
unify our results, we now present a generic version of bagging that includes
all four of these variants as special cases.

###  3.1 Generic Bagging

Bagging is a procedure that converts any base algorithm $\mathcal{A}$ into a
new algorithm, its bagged version $\widetilde{\mathcal{A}}_{B}$. Define

$\textnormal{seq}_{[n]}\coloneqq\\{(i_{1},\ldots,i_{k}):k\geq
0,i_{1},\ldots,i_{k}\in[n]\\},$

which is the set of finite sequences (of any length) consisting of indices in
$[n]$. We will refer to any $r\in\textnormal{seq}_{[n]}$ as a “bag”. Let
$\mathcal{Q}_{n}$ denote a distribution on $\textnormal{seq}_{[n]}$. For
example, subbagging $m$ out of $n$ points corresponds to the uniform
distribution over the set of length-$m$ sequences $(i_{1},\ldots,i_{m})$ with
distinct entries. Given a bag $r=(i_{1},\dots,i_{m})\in\textnormal{seq}_{[n]}$
and a data set $\mathcal{D}=(Z_{1},\dots,Z_{n})$, define a new data set
$\mathcal{D}_{r}=(Z_{i_{1}},\dots,Z_{i_{m}})$ selecting the datapoints
according to the bag $r$.

Algorithm 1 Generic Bagging $\widetilde{\mathcal{A}}_{B}$

0: Base algorithm $\mathcal{A}$; data set $\mathcal{D}$ with $n$ training
points; number of bags $B\geq 1$; resampling distribution $\mathcal{Q}_{n}$

for $b=1,\dots,B$ do

Sample bag $r^{(b)}=(i_{1}^{(b)},\ldots,i_{n_{b}}^{(b)})\sim\mathcal{Q}_{n}$

Sample seed $\xi^{(b)}\sim\textnormal{Unif}([0,1])$

Fit model $\hat{f}^{(b)}=\mathcal{A}(\mathcal{D}_{r^{(b)}};\xi^{(b)})$

end for

Averaged model $\hat{f}$ defined by
$\textstyle\hat{f}_{B}(x)=\frac{1}{B}\sum_{b=1}^{B}\hat{f}^{(b)}(x)$

To construct the bagged algorithm $\widetilde{\mathcal{A}}_{B}$ using
$\mathcal{A}$ as a base algorithm, we first draw bags $r^{(1)},\dots,r^{(B)}$
from the resampling distribution $\mathcal{Q}_{n}$, then fit a model on each
bag using $\mathcal{A}$, and average the resulting models for the final fitted
function. Algorithm 1 summarizes this procedure.

Generic bagging treats the base algorithm $\mathcal{A}$ as a ‘black-box,’ in
that it only accesses the base algorithm by querying it on different training
sets and different random seeds. We will write $\widetilde{\mathcal{A}}_{B}$
to denote the resulting algorithm obtained by applying generic bagging with
$\mathcal{A}$ as the base algorithm.

Our theoretical analysis of bagging is simplified by considering an idealized
version of generic bagging as the number of bags $B$ tends to infinity. Our
tactic is to directly study the stability of this large-$B$ limit, and then
derive analogous results for $\widetilde{\mathcal{A}}_{B}$ using simple
concentration inequalities. To facilitate our theoretical analysis, we define
in Algorithm 2 the limiting version of generic bagging.

Algorithm 2 Derandomized Bagging $\widetilde{\mathcal{A}}_{\infty}$

0: Base algorithm $\mathcal{A}$; data set $\mathcal{D}$ with $n$ training
points; resampling distribution $\mathcal{Q}_{n}$

0: Averaged model $\hat{f}_{\infty}$ defined by
$\hat{f}_{\infty}(x)=\mathbb{E}_{r,\xi}\left[\mathcal{A}(\mathcal{D}_{r};\xi)(x)\right]$
where the expectation is taken with respect to $r\sim\mathcal{Q}_{n}$ and
$\xi\sim\textnormal{Unif}([0,1])$.

Note that the algorithm $\mathcal{A}$ may be a randomized algorithm, but
derandomized bagging averages over any randomness in $\mathcal{A}$ (coming
from the random seed $\xi$) as well as the randomness of the bags drawn from
$\mathcal{Q}_{n}$.333For $\widetilde{\mathcal{A}}_{\infty}$ to be defined, we
assume that the expectation
$\mathbb{E}_{r,\xi}\left[\mathcal{A}(\mathcal{D}_{r};\xi)(x)\right]$ exists
for all data sets $\mathcal{D}$ and test points $x$. For instance, the
derandomized form of classical bagging averages uniformly over $n^{m}$
possible subsets of the data; in practice, since we generally cannot afford
$n^{m}$ many calls to $\mathcal{A}$, we would instead run classical bagging
with some large $B$ as the number of randomly sampled bags.

###  3.2 The Resampling Distribution $\mathcal{Q}_{n}$

To simplify the statement of the main results, we will make a symmetry
assumption on the resampling method $\mathcal{Q}_{n}$. All the variants we
have described above (classical bagging, subbagging, Poissonized bagging,
Bernoulli subbagging) satisfy this assumption.

######  Assumption 5.

The resampling method $\mathcal{Q}_{n}$ satisfies

$\mathcal{Q}_{n}\\{(i_{1},\ldots,i_{m})\\}=\mathcal{Q}_{n}\\{(\sigma(i_{1}),\ldots,\sigma(i_{m}))\\},$

for all $m$, $i_{1},\ldots,i_{m}\in[n]$, and permutations
$\sigma\in\mathcal{S}_{n}$.

Intuitively, this symmetry assumption requires the bagging algorithm to treat
the indices $(1,\ldots,n)$ as exchangeable (e.g., bags $(1,2,2)$ and $(3,4,4)$
are equally likely).

Different bagging methods will attain different degrees of stability. For
instance, consider a degenerate case where $\mathcal{Q}_{n}$ returns a random
permutation of $(1,\ldots,n)$ (i.e., subbagging with $m=n$). Then
$\hat{f}_{\infty}$ is simply the result of running the base algorithm on
shuffled versions of the data. In this case, the bagged algorithm is only as
stable as the base algorithm. Our bounds on the stability of bagging depend on
specific parameters of the resampling method $\mathcal{Q}_{n}$.

######  Definition 6.

For $\mathcal{Q}_{n}$ satisfying Assumption 5, let

$\displaystyle p$
$\displaystyle\coloneqq\mathbb{P}_{r\sim\mathcal{Q}_{n}}\\{i\in r\\},$ (5)
$\displaystyle q$
$\displaystyle\coloneqq-\textnormal{Cov}_{r\sim\mathcal{Q}_{n}}(\mathbf{1}_{i\in
r},\mathbf{1}_{j\in r}),$

for any $i\neq j\in[n]$.

Here for a sequence $r=(i_{1},\dots,i_{m})\in\textnormal{seq}_{[n]}$, we write
$i\in r$ to denote the event that $i_{k}=i$ for some $k$. Assumption 5 ensures
that the value of $p$ (and of $q$) are shared across all $i$ (respectively,
across all $i\neq j$).

We make the following restrictions on these parameters:

Algorithm |  Resampling method $\mathcal{Q}_{n}$ | $p=\mathbb{P}\\{i\in r\\}$ | $q=-\textnormal{Cov}[i\in r,j\in r]$
---|---|---|---
Subbagging |  |  $r=(i_{1},\ldots,i_{m})$ drawn
---
uniformly w/o replacement
$\frac{m}{n}$ | $\frac{m(n-m)}{n^{2}(n-1)}$
Bernoulli subbagging |  | $M\sim\textnormal{Binomial}(n,\frac{m}{n})$
---
$r=(i_{1},\ldots,i_{M})$ drawn
uniformly w/o replacement
$\frac{m}{n}$ | 0
Classical bagging | $r\sim\textnormal{Unif}\left\\{[n]^{m}\right\\}$ | $1-\left(1-\frac{1}{n}\right)^{m}$ | $\left(1-\frac{1}{n}\right)^{2m}-\left(1-\frac{2}{n}\right)^{m}$
Poissonized bagging |  | $M\sim\textnormal{Poisson}(m)$
---
$r\mid M\sim\textnormal{Unif}\left\\{[n]^{M}\right\\}$
$1-e^{-m/n}$ | 0
Table 1: Parameters $p$ and $q$ from Definition 6 for various sampling schemes
$\mathcal{Q}_{n}$.

######  Assumption 7.

$\mathcal{Q}_{n}$ satisfies $p\in(0,1)$ and $q\geq 0$.

The constraint $p\in(0,1)$ is a nondegeneracy assumption that guarantees a
nonzero probability that any given observation $Z_{i}$ will be excluded from
some bags and included in others. The constraint $q\geq 0$ forces non-positive
correlation between observations, i.e., $i\in r$ does not increase the
probability of $j\in r$ for $i\neq j$.

Table 1 provides values of $p$ and $q$ for the four different sampling schemes
discussed above, which all satisfy Assumption 7. Classical bagging and
subbagging both have a small positive $q$ due to weak negative correlation
between the events $i\in r$ and $j\in r$, while Poissonized bagging and
Bernoulli subbagging decorrelate these events and so $q=0$.

Since algorithmic stability compares a model fit on $n$ observations to a
model fit on $n-1$ observations, we need to specify resampling distributions
at both sample sizes, i.e., $\mathcal{Q}_{n}$ and $\mathcal{Q}_{n-1}$;
naturally, to guarantee stability, these two distributions must be similar to
each other. Specifically, we will consider the setting where

$\textnormal{$\mathcal{Q}_{n-1}$ is given by the distribution of
}\textnormal{$r\sim\mathcal{Q}_{n}$ conditional on the event
$r\in\textnormal{seq}_{[n-1]}$},$ (6)

i.e., we are conditioning on the event that the $n$th data point is not
contained in the bag. For example, if $\mathcal{Q}_{n}$ is chosen to be
subbagging $m$ out of $n$ points (for some fixed $m\leq n-1$), then
$\mathcal{Q}_{n-1}$ is equal to the distribution obtained by subbagging $m$
out of $n-1$ points.

##  4 Stability Guarantees for Bagging

In this section, we first present our main stability guarantee when the
prediction range $\hat{\mathcal{Y}}$ is a bounded interval. We then show that
this guarantee cannot be improved in general, up to a small multiplicative
factor.

###  4.1 Main Result: Guarantee for Average-case Stability

We turn to our bound quantifying the average-case stability of derandomized
bagging. In this section, we restrict our attention to settings where the
output regression function $\hat{f}$ is bounded. We will consider the
unbounded case in Section 5.1.

To examine the stability of $\widetilde{\mathcal{A}}_{\infty}$ (obtained by
applying derandomized bagging to a base algorithm $\mathcal{A}$) our stability
results will compare the models:

  * •

$\hat{f}_{\infty}$, obtained by running derandomized bagging (Algorithm 2)
with base algorithm $\mathcal{A}$, data set $\mathcal{D}$, and sampling
distribution $\mathcal{Q}_{n}$; and

  * •

$\hat{f}_{\infty}^{\setminus i}$, obtained by running derandomized bagging
(Algorithm 2) with base algorithm $\mathcal{A}$, data set
$\mathcal{D}^{\setminus i}$, and sampling distribution $\mathcal{Q}_{n-1}$,
constructed as in (6).

######  Theorem 8.

Let $\hat{\mathcal{Y}}=[0,1]$.444All theoretical results in this section are
stated for $\hat{\mathcal{Y}}=[0,1]$ for simplicity, but it is straightforward
to generalize to the case $\hat{\mathcal{Y}}=[a,b]$ by simply replacing
$(\varepsilon,\delta)$-stability with $(\varepsilon(b-a),\delta)$-stability in
the guarantee. Fix a distribution $\mathcal{Q}_{n}$ on
$\textnormal{seq}_{[n]}$ satisfying Assumptions 5 and 7, and let
$\mathcal{Q}_{n-1}$ be defined as in (6). For any algorithm $\mathcal{A}$,
derandomized bagging $\widetilde{\mathcal{A}}_{\infty}$ is
$(\varepsilon,\delta)$-stable provided

$\displaystyle\delta\varepsilon^{2}\geq\frac{1}{4n}\left(\frac{p}{1-p}+\frac{q}{(1-p)^{2}}\right).$
(7)

We prove Theorem 8, along with all subsequent results, in Appendix A.555The
proof shows a slightly stronger notion of stability, where
$\mathbb{P}_{\xi}\left\\{|\hat{f}(x)-\hat{f}^{\setminus
i}(x)|>\varepsilon\right\\}$ in Equation 4 is replaced with
$\mathbb{P}_{\xi}\left\\{|\hat{f}(x)-\hat{f}^{\setminus
i}(x)|\geq\varepsilon\right\\}$. For both classical bagging and subbagging,
the term involving $q$ in Equation 7 is relatively insignificant: in both
cases, Equation 7 is implied by the simpler condition

$\delta\varepsilon^{2}\geq\frac{1}{4(n-1)}\frac{p}{1-p}.$

A simple application of Hoeffding’s inequality leads to a similar stability
guarantee for generic bagging. In this result, we compare the models:

  * •

$\hat{f}_{B}$, obtained by running generic bagging (Algorithm 1) with base
algorithm $\mathcal{A}$, data set $\mathcal{D}$, and resampling distribution
$\mathcal{Q}_{n}$; and

  * •

$\hat{f}_{B}^{\setminus i}$, obtained by running generic bagging (Algorithm 1)
with base algorithm $\mathcal{A}$, data set $\mathcal{D}^{\setminus i}$, and
resampling distribution $\mathcal{Q}_{n-1}$, constructed as in (6).

######  Theorem 9.

Let $\hat{\mathcal{Y}}=[0,1]$. Fix a distribution $\mathcal{Q}_{n}$ on
$\textnormal{seq}_{[n]}$ satisfying Assumptions 5 and 7, and let
$\mathcal{Q}_{n-1}$ be defined as in (6). For any algorithm $\mathcal{A}$ and
any $B\geq 1$, generic bagging $\widetilde{\mathcal{A}}_{B}$ is
$\left(\varepsilon+\sqrt{\frac{2}{B}\log\left(\frac{4}{\delta^{\prime}}\right)},\delta+\delta^{\prime}\right)$-stable
for any $(\varepsilon,\delta)$ satisfying Condition (7) and any
$\delta^{\prime}>0$.

For instance, if derandomized bagging is guaranteed to satisfy
$(\varepsilon,\delta)$ stability via (7), then we may take
$B\geq\frac{2}{\varepsilon^{2}}\log\left(\frac{4}{\delta}\right)$ to guarantee
$(2\varepsilon,2\delta)$-stability of generic bagging. More generally, for any
fixed $B$, the result accounts for the Monte Carlo error in the generic
bagging algorithm.

####  4.1.1 Sampling Regimes for Subbagging

The results of Theorem 8 cover a wide range of regimes. In this section, we
give some concrete examples in the case of subbagging, to build intuition:

_Proportional subsampling with $m\propto n$:_ Suppose we employ subbagging
with $m=n/2$. The stability condition (7) in the theorem simplifies to
$\delta\varepsilon^{2}\geq\frac{1}{4(n-1)}$. Hence, our stability result
applies in a variety of regimes. For instance, if $\delta>0$ does not depend
on $n$, bagging satisfies average-case $(\varepsilon,\delta)$-stability with
$\varepsilon=O(n^{-1/2})$. We may also take $\varepsilon>0$ fixed and
$\delta=O(n^{-1})$, or even $\delta=\varepsilon=O(n^{-1/3})$ going to zero
simultaneously.

_Massive subsampling with $m=o(n)$:_ For massive data sets, it may be
computationally advantageous to subsample a very small fraction of the data
(Kleiner et al.,, 2014). _Massive subsampling_ , where we take bags of size
$m=n^{\beta}$ for some $\beta\in(0,1)$, can be seen to further enhance
stability via our result above. In this case, condition (7) becomes
$\delta\varepsilon^{2}\gtrsim\frac{1}{n^{1+\beta}}$. See Section 7.3 for a
discussion of results in the literature in this regime.

_Minimal subsampling with $m=n-o(n)$:_ Massive subsampling, or even
subsampling a constant fraction of the data, often comes with some loss of
statistical efficiency. To avoid this, our result even allows for resampling
schemes with $m=n-o(n)$, i.e., each subsample contains nearly the entire data
set. For example, taking $m=n-n^{\beta}$ for some $\beta\in(0,1)$, condition
(7) becomes $\delta\varepsilon^{2}\gtrsim\frac{1}{n^{\beta}}$.

###  4.2 Tightness of Stability Guarantee

In the special case of subbagging, we show that Theorem 8 cannot be improved
(beyond a constant factor) without assuming more about the base algorithm. We
only state this result in the ideal, derandomized case, since this will
typically be more stable than its finite $B$ counterpart.

######  Theorem 10.

Let $\hat{\mathcal{Y}}=[0,1]$. Fix $n>m\geq 1$ and $\delta\in(0,1/2)$. There
is a base algorithm $\mathcal{A}^{\sharp}$ such that subbagging
$\widetilde{\mathcal{A}}^{\sharp}_{\infty}$ with $m$ out of $n$ observations
is not $(\varepsilon,\delta)$-stable for any

$\varepsilon<\left(1-\delta-n^{-1}\right)p\,\mathbb{P}\left\\{H=\Big{\lfloor}p\left(1+\lfloor
n\delta\rfloor\right)\Big{\rfloor}\right\\},$ (8)

where $p=\frac{m}{n}$ and where probability is taken with respect to
$H\sim\textnormal{HyperGeometric}(n-1,m,\lfloor n\delta\rfloor)$.

To see how this result compares to the guarantee given in Theorem 8, consider
a simple case where $n\delta$ and $m\delta=np\delta$ are integers, and take
$p<1$. Then

$\mathbb{P}\left\\{H=\Big{\lfloor}p\left(1+\lfloor
n\delta\rfloor\right)\Big{\rfloor}\right\\}=\mathbb{P}\left\\{H=np\delta\right\\}=\frac{{n\delta\choose
np\delta}\cdot{n(1-\delta)-1\choose np(1-\delta)}}{{n-1\choose
np}}\approx\frac{1}{\sqrt{2\pi n\delta(1-\delta)p(1-p)}},$

where the last step holds by taking Stirling’s approximation to each factorial
term in each Binomial coefficient (and the approximation is accurate as long
as $n\cdot\min\\{\delta,1-\delta\\}\cdot\min\\{p,1-p\\}$ is large). Thus the
right-hand side of (8) is approximately

$\approx\frac{1}{\sqrt{2\pi
n}}\cdot\sqrt{\frac{1-\delta}{\delta}\cdot\frac{p}{1-p}}.$

Since we have assumed $\delta<1/2$, we therefore see that stability fails for
$\mathcal{A}^{\sharp}$ when (approximately)

$\delta\varepsilon^{2}<\frac{1}{4\pi n}\cdot\frac{p}{1-p}.$

Up to a constant, this matches the leading term of the stability guarantee in
Theorem 8, demonstrating the tightness of our guarantee.

In Figure 2, we plot a phase diagram comparing the stability guarantee (7)
with the tightness condition (8) for finite $n$. We take $n=500,p=1/2$, and
$q=p(1-p)/(n-1)=1/1996$, which are the values of $p$ and $q$ for subbagging
with $m=n/2$ (see Table 1). The blue line shows, for each $\delta$, the
minimum $\varepsilon$ satisfying (7), and the shaded blue region shows
additional $(\varepsilon,\delta)$ pairs satisfying the inequality. This means
that, for any base algorithm $\mathcal{A}$ with outputs in
$\hat{\mathcal{Y}}=[0,1]$, its subbagged version is guaranteed to satisfy
$(\varepsilon,\delta)$-stability for any pair $(\varepsilon,\delta)$ in the
blue shaded region. Similarly, the red line shows, for each $\delta$, the
maximum $\varepsilon$ satisfying (8). This means that, for any
$(\varepsilon,\delta)$ in the red shaded region, we can construct an algorithm
$\mathcal{A}^{\sharp}$, again with outputs in $\hat{\mathcal{Y}}=[0,1]$, such
that its subbagged version fails to be $(\varepsilon,\delta)$-stable. The
narrow white region between the two conditions illustrates the small gap
between the two results.

Figure 2: Phase diagram comparing Theorems 8 and 10.

##  5 Extensions

In this section, we consider various extensions of our main result. We first
discuss two approaches to the case of unbounded outputs. Next, we show a
hardness result explaining why we cannot obtain a similar guarantee for worst-
case stability. Finally, we consider the implications of our main result for
various alternative definitions of stability.

###  5.1 Unbounded Outputs

We next extend our main result to algorithms $\mathcal{A}$ with unbounded
output $\hat{\mathcal{Y}}=\mathbb{R}$. For derandomized bagging
$\widetilde{\mathcal{A}}_{\infty}$ to be well-defined, we assume that the
expectation

$\mathbb{E}_{r,\xi}\left[\mathcal{A}(\mathcal{D}_{r};\xi)(x)\right]$

exists. For instance, for classical bagging, subbagging, and Bernoulli
subbagging, the average over $r\sim\mathcal{Q}_{n}$ constitutes a finite sum,
so we are simply assuming that expectation over the random seed

$\mathbb{E}_{\xi}\left[\mathcal{A}(\mathcal{D};\xi)(x)\right]$

exists for any fixed data set $\mathcal{D}$.

In order to establish some control over the scale of the outputs of the fitted
model, we extend our definition of average-case stability to allow for a data-
dependent component. Consider for instance any algorithm $\mathcal{A}$ with
$\hat{\mathcal{Y}}=[0,1]$, and define a new algorithm $\mathcal{A}^{\prime}$
scaling the outputs by $R>0$, i.e.
$\mathcal{A}^{\prime}(\mathcal{D};\xi)=R\cdot\mathcal{A}(\mathcal{D};\xi)$. If
the original algorithm $\mathcal{A}$ is $(\varepsilon,\delta)$-stable, then
the scaled algorithm $\mathcal{A}^{\prime}$ is $(\varepsilon
R,\delta)$-stable.

We might hope that we can take $R$ to be the empirical range of the algorithm,

$R=\textnormal{Range}(\mathcal{D},x)=\sup_{r:\mathcal{Q}_{n}(\\{r\\})>0}\mathbb{E}_{\xi}\left[\mathcal{A}(\mathcal{D}_{r};\xi)(x)\right]-\inf_{r:\mathcal{Q}_{n}(\\{r\\})>0}\mathbb{E}_{\xi}\left[\mathcal{A}(\mathcal{D}_{r};\xi)(x)\right].$

However, since this quantity depends (in general) on $\mathcal{D}$ and on $x$,
it would not be well-defined to claim that $\mathcal{A}$ is $(\varepsilon
R,\delta)$-stable universally across all $\mathcal{D}$ and all $x$.

Instead, to allow for a data set-dependent range, we consider scaling
$\varepsilon$ by a data-dependent scale parameter $R(\mathcal{D},x)$, where

$R:\bigcup_{n\geq
0}(\mathcal{X}\times\mathcal{Y})^{n}\times\mathcal{X}\to\mathbb{R}_{+}.$

We now define $(\varepsilon,\delta,R)$-stability to account for data-dependent
changes in scale.

######  Definition 11.

Let $\varepsilon,\delta\geq 0$ and let $R$ denote a data-dependent range
(formally defined above). An algorithm $\mathcal{A}$ is
$(\varepsilon,\delta,R)$-stable if, for all data sets
$\mathcal{D}=(Z_{i})_{i=1}^{n}$ of size $n$ and all test points
$x\in\mathcal{X}$,

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\mathbb{P}_{\xi}\left\\{|\hat{f}(x)-\hat{f}^{\setminus
i}(x)|>\varepsilon\,R(\mathcal{D},x)\right\\}\leq\delta,$ (9)

where $\hat{f}=\mathcal{A}(\mathcal{D};\xi)$, $\hat{f}^{\setminus
i}=\mathcal{A}(\mathcal{D}^{\setminus i};\xi)$ and $\mathcal{D}^{\setminus
i}=(Z_{j})_{j\neq i}$.

Inspecting the proof of Theorem 8, we only use boundedness to control the
variance of our model predictions
$\mathbb{E}_{\xi}\left[\mathcal{A}(\mathcal{D}_{r};\xi)(x)\right]$ as a
function of the random bag $r\sim\mathcal{Q}_{n}$. This observation leads to
the following, more general result.

######  Theorem 12.

Let $\hat{\mathcal{Y}}=\mathbb{R}$. Fix a distribution $\mathcal{Q}_{n}$ on
$\textnormal{seq}_{[n]}$ satisfying Assumptions 5 and 7, and let
$\mathcal{Q}_{n-1}$ be defined as in (6). Let $(\varepsilon,\delta)$ satisfy
Equation 7. For any algorithm $\mathcal{A}$, derandomized bagging
$\widetilde{\mathcal{A}}_{\infty}$ is $(\varepsilon,\delta,R^{*})$-stable,
where

$\displaystyle
R^{*}(\mathcal{D},x):=2\sqrt{\textnormal{Var}_{r\sim\mathcal{Q}_{n}}\Big{(}\mathbb{E}_{\xi}\left[\mathcal{A}(\mathcal{D}_{r};\xi)(x)\right]\Big{)}}\leq\textnormal{Range}(\mathcal{D},x).$
(10)

As long as $\mathbb{E}_{\xi}\left[\mathcal{A}(\mathcal{D}_{r};\xi)(x)\right]$
is well-defined for every $r$, the range $R^{*}(\mathcal{D})$ is automatically
finite for any $\mathcal{Q}_{n}$ with finite support. Furthermore, Theorem 12
strictly generalizes the stability guarantee of Theorem 8, since
$R^{*}(\mathcal{D},x)\leq\textnormal{Range}(\mathcal{D},x)\leq 1$ in the case
$\hat{\mathcal{Y}}=[0,1]$. We present a weaker result for the finite-$B$
regime in Appendix B.

####  5.1.1 Alternative Approach: Adaptive Clipping

In some settings, e.g., with heavy tailed responses, the range in the previous
display or the standard deviation in Equation 10 may be prohibitively large.
One way to reduce the standard deviation $R^{*}(\mathcal{D},x)$ is to post-
process the algorithm $\mathcal{A}$. We next consider the advantages of
clipping the output of $\mathcal{A}$ to secure greater stabilty.

Given an interval $I=[l,u]$ and a response $\hat{y}\in\mathbb{R}$, the clipped
response $\textnormal{Clip}_{I}(\hat{y})$ is defined as

$\displaystyle\textnormal{Clip}_{I}(\hat{y})\coloneqq\max\\{l,\min\\{\hat{y},u\\}\\}.$
(11)

In Algorithm 3, we define a variant of the derandomized bagging algorithm that
allows the individual bagged predictions $\hat{f}_{\infty}^{(r)}(x)$ to be
clipped to some interval $I=I(\mathcal{D})$ that depends on the full data set.
We write $\widetilde{\mathcal{A}}_{B,I}$ to denote the algorithm obtained by
applying adaptively clipped bagging with $\mathcal{A}$ as the base algorithm.
Stability of Algorithm 3 does not follow immediately from Theorem 12 because
$I(\mathcal{D})$ may not be the same as $I(\mathcal{D}^{\setminus i})$, so the
algorithm being bagged is itself changing when we perturb the training data.
For simplicity, we state our result for the derandomized limit
$\widetilde{\mathcal{A}}_{\infty,I}$ and give a finite $B$ version in Appendix
B.

Algorithm 3 Adaptively Clipped Bagging

0: Base algorithm $\mathcal{A}$; data set $\mathcal{D}$ with $n$ training
points; number of bags $B\geq 1$; resampling distribution $\mathcal{Q}_{n}$;
data-dependent range $I(\cdot)$

for $b=1,\dots,B$ do

Sample bag $r^{(b)}=(i_{1}^{(b)},\ldots,i_{n_{b}}^{(b)})\sim\mathcal{Q}_{n}$

Sample seed $\xi^{(b)}\sim\textnormal{Unif}([0,1])$

Fit model $\hat{f}^{(b)}=\mathcal{A}(\mathcal{D}_{r^{(b)}};\xi^{(b)})$

end for

Averaged model $\hat{f}_{B,I}$ defined by
$\textstyle\hat{f}_{B,I}(x)=\frac{1}{B}\sum_{b=1}^{B}\textnormal{Clip}_{I(\mathcal{D})}(\hat{f}^{(b)}(x))$

######  Theorem 13.

Let $\hat{\mathcal{Y}}=\mathbb{R}$. Fix a distribution $\mathcal{Q}_{n}$ on
$\textnormal{seq}_{[n]}$ satisfying Assumptions 5 and 7, and let
$\mathcal{Q}_{n-1}$ be defined as in (6). Suppose the mapping to intervals
$I(\cdot)$ from data sets to intervals satisfies

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\mathbf{1}\\{I(\mathcal{D})\neq
I(\mathcal{D}^{\setminus i})\\}\leq\delta_{I}.$ (12)

Let $R(\mathcal{D},x)=\textnormal{length}(I(\mathcal{D}))$ and let
$(\varepsilon,\delta)$ satisfy Equation 7. For any algorithm $\mathcal{A}$,
derandomized adaptively clipped bagging $\widetilde{\mathcal{A}}_{\infty,I}$
is $(\varepsilon,\delta+\delta_{I},R)$-stable.

As a special case, consider taking $I(D)$ to be the observed range, i.e.,
$I(\mathcal{D})=[\min_{i}Y_{i},\max_{i}Y_{i}]$. When $(Z_{i})_{i=1}^{n+1}$ are
exchangeable random variables, we can apply Theorem 13 with
$\delta^{\prime}=\frac{2}{n}$. Restricting to the empirical range of the
$Y_{i}$’s does not substantially limit the learned regression function
$\hat{f}_{\infty,I}$—it simply requires that predictions cannot lie outside
the observed range of the training data (which is already satisfied by many
base algorithms, such as nearest neighbors or regression trees, and typically
would not substantially alter the output of many other algorithms). More
generally, we can take $I(\mathcal{D})=[Y_{(k)},Y_{(n+1-k)}]$ for some fixed
$k<n/2$, where $Y_{(1)}\leq\cdots\leq Y_{(n)}$ denote the order statistics of
$Y_{1},\dots,Y_{n}$. In this case, we have $\delta^{\prime}=\frac{2k}{n}$ in
(12), which allows for some fraction $\delta^{\prime}$ of outliers to be
removed when constructing the data-dependent range, thus ensuring that
$R(\mathcal{D},x)$ will not be too large.

###  5.2 Hardness of Worst-case Stability

Our results above establish that $(\varepsilon,\delta)$-stability can be
guaranteed for any (bounded) base algorithm even for very small
$\varepsilon$—for instance, taking $p\in(0,1)$ to be a constant, we can choose
$\varepsilon=O(n^{-1/2})$. We will next see that no analogous result exists
for worst-case stability—indeed, for this stricter definition, stability
cannot be guaranteed for any $\varepsilon<p$, and therefore
$\varepsilon=O(n^{-1/2})$ can only be guaranteed via massively subsampling the
data with $p=O(n^{-1/2})$.

######  Theorem 14.

Fix $\mathcal{Q}_{n}$ and let $\hat{\mathcal{Y}}=[0,1]$.

  * (i)

For any algorithm $\mathcal{A}$, derandomized bagging is worst-case
$(p,\delta)$-stable for all $\delta$.

  * (ii)

If $|\mathcal{X}|>1$, there is a base algorithm $\mathcal{A}^{\dagger}$ such
that derandomized bagging is not worst-case $(\varepsilon,\delta)$-stable for
any $\varepsilon<p$ and $\delta<1$.

Part  _(i)_ of the theorem has appeared previously; in Section 7.3 we discuss
how this observation has led some authors on algorithmic stability to advocate
for subsampling a decreasing fraction of the data $m=o(n)$ as $n\to\infty$. In
contrast, by moving to average-case stability, our results allow $m=O(n)$ and
even $m=n-o(n)$, enabling far greater accuracy in the fitted models.

The base algorithm $\mathcal{A}^{\dagger}$ in the proof of part _(ii)_ of the
theorem memorizes the training data:

$\mathcal{A}^{\dagger}(\mathcal{D})(x):=\mathbf{1}\\{\exists(\tilde{x},\tilde{y})\in\mathcal{D}:\tilde{x}=x\\}.$

If $x=x_{i}$ for precisely one $i\in[n]$, then this training point
$(x_{i},y_{i})$ has maximal influence on the value of
$\hat{f}_{\infty}(x)$—every bag containing $(x_{i},y_{i})$ predicts 1, and
every bag not containing $(x_{i},y_{i})$ leads to a predicts 0. This
counterexample can be used to show an even stronger hardness result, for
average-case, “in-sample” stability (discussed earlier in Section 2): if
$x_{1},\ldots,x_{n}$ are all distinct,

$\frac{1}{n}\sum_{i=1}^{n}1\left\\{|\hat{f}_{\infty}^{\dagger}(x_{i})-\hat{f}_{\infty}^{\dagger\setminus
i}(x_{i})|>\varepsilon\right\\}=\begin{cases}1&\text{if }\varepsilon\leq p\\\
0&\text{if }\varepsilon>p\end{cases},$

where
$\hat{f}_{\infty}^{\dagger}=\mathcal{A}_{\infty}^{\dagger}(\mathcal{D})$.
Note, however, that for a fixed $x$, _at most one_ index $i\in[n]$ can change
the bagged prediction by $p$. This limitation of $\mathcal{A}^{\dagger}$
provides useful intuition for why we may expect a stronger result for our main
definition of $(\varepsilon,\delta)$-stability, Definition 4, where the test
point $x\in\mathcal{X}$ is fixed.

###  5.3 Alternative Frameworks for the Main Result

In this section, we discuss various implications of our main stability
guarantee for related criteria.

####  5.3.1 Stability in Expectation

In Definition 4, average-case algorithmic stability controls the tail of the
distribution of leave-one-out perturbations. Some authors (e.g., Bousquet and
Elisseeff,, 2002; Elisseeff et al.,, 2005) prefer to work with the expected
value of the leave-one-out perturbation. We can consider a version of average-
case stability that works with expected values rather than probabilities,
requiring that

$\displaystyle\frac{1}{n}$
$\displaystyle\sum_{i=1}^{n}\mathbb{E}_{\xi}\left|\hat{f}(x)-\hat{f}^{\setminus
i}(x)\right|\leq\beta,$ (13)

for all data sets $\mathcal{D}$ of size $n$ and test points $x\in\mathcal{X}$,
where $\hat{f}=\mathcal{A}(\mathcal{D};\xi)$ and $\hat{f}^{\setminus
i}=\mathcal{A}(\mathcal{D}^{\setminus i};\xi)$.

######  Corollary 15.

In the setting of Theorem 8, for any $B$, generic bagging
$\widetilde{\mathcal{A}}_{B}$ satisfies stability condition (13) at level
$\beta=\beta_{n,m,B}$, where

$\displaystyle\beta_{n,m,B}=\sqrt{\frac{1}{n}\left(\frac{p}{1-p}+\frac{q}{(1-p)^{2}}\right)}+\sqrt{\frac{2\pi}{B}}.$
(14)

Note that the scaling of $\beta$ in this result is comparable to the scaling
of $\varepsilon$ in Theorem 9 if we take $\delta,\delta^{\prime}$ to be
constant. The result holds for any $B$, including the case of derandomized
bagging by taking $B\to\infty$.

####  5.3.2 Stability in the Loss

Building on earlier definitions of stability (Kearns and Ron,, 1999; Bousquet
and Elisseeff,, 2002), Elisseeff et al., (2005, Definition 7) say that a
randomized algorithm $\mathcal{A}$ satisfies _random hypothesis stability_ at
level $\beta$ with respect to the loss function $\ell$ and distribution $P$ if
the following holds:

$\displaystyle\forall
i\in\\{1,\ldots,n\\},~{}\mathbb{E}_{(X_{i},Y_{i})_{i=1}^{n+1}\stackrel{{\scriptstyle\textnormal{iid}}}{{\sim}}P,\xi}\left|\ell(\hat{f}(X_{n+1}),Y_{n+1})-\ell(\hat{f}^{\setminus
i}(X_{n+1}),Y_{n+1})\right|\leq\beta,$ (15)

where $\hat{f}=\mathcal{A}(\mathcal{D};\xi)$, $\hat{f}^{\setminus
i}=\mathcal{A}(\mathcal{D}^{\setminus i};\xi)$,
$\mathcal{D}=(X_{i},Y_{i})_{i=1}^{n}$.

######  Corollary 16.

Let $\hat{\mathcal{Y}}=[0,1]$. Fix a distribution $\mathcal{Q}_{n}$ on
$\textnormal{seq}_{[n]}$ satisfying Assumptions 5 and 7, and let
$\mathcal{Q}_{n-1}$ be defined as in (6). Let $P$ denote any distribution on
$\mathcal{X}\times\mathcal{Y}$, and let
$\ell:\hat{\mathcal{Y}}\times\mathcal{Y}\to\mathbb{R}_{+}$ denote any loss
function that is $L$-Lipschitz in its first argument. For any algorithm
$\mathcal{A}$ and any $B$, generic bagging $\widetilde{\mathcal{A}}_{B}$
satisfies random hypothesis stability (15) at level $\beta=L\beta_{n,m,B}$,
where $\beta_{n,m,B}$ is defined as in Equation 14.

Of course, our result shows Equation 15 holds even _conditional on the
training data $\mathcal{D}$ and the test point $(X_{n+1},Y_{n+1})$_,
eliminating the assumption that the data are i.i.d.—in fact, in our result,
the test point can be adversarially chosen.

We now compare this result to the work of Elisseeff et al., (2005, Proposition
4.4), who also study the random hypothesis stability of subbagging with
respect to an $L$-Lipschitz loss $\ell$, showing

$\beta=Lp\beta_{\mathcal{A},m},$

where $\beta_{\mathcal{A},m}$ denotes the random hypothesis stability of the
base algorithm $\mathcal{A}$ with respect to $\ell_{1}$ loss (on data sets of
size $m$). Generally, we expect the stability of the base algorithm to improve
with the sample size (i.e., $\beta_{\mathcal{A},m}\geq\beta_{\mathcal{A},n}$
for $m\leq n$), so their result does not necessarily imply subbagging improves
upon the stability of running the base algorithm $\mathcal{A}$ on the full
data set. However, in practice we typically do not know the quantities
$\beta_{\mathcal{A},m}$ or $\beta_{\mathcal{A},n}$, but the result of
Elisseeff et al., (2005) shows that we can achieve random hypothesis stability
$\beta=O(n^{-1/2})$ by taking $p=O(n^{-1/2})$. By contrast, Corollary 16 shows
subbagging even half the data ($p=0.5$) can achieve random hypothesis
stability $\beta=O(n^{-1/2})$. We further compare to prior work on the
stability of bagging in Section 7.3.

####  5.3.3 Replace-one Stability

The stability definitions in this paper concern the leave-one-out perturbation
$|\hat{f}(x)-\hat{f}^{\setminus i}(x)|$. Alternative definitions, used for
example by Shalev-Shwartz et al., (2010), are obtained by considering a
‘replace-one’ perturbation $|\hat{f}(x)-\hat{f}^{(i)}(x)|$, where

$\hat{f}^{(i)}=\mathcal{A}(\mathcal{D}^{(i)};\xi)\qquad\text{and}\qquad\mathcal{D}^{(i)}=\mathcal{D}^{\setminus
i}\cup(Z_{i}^{\prime}).$

We say that a randomized algorithm $\mathcal{A}$ satisfies _random replace-one
hypothesis stability_ $\beta$ with respect to the loss function $\ell$ and
distribution $P$ if the following holds:

$\displaystyle\forall
i\in\\{1,\ldots,n\\},~{}\mathbb{E}_{(X_{i},Y_{i})_{i=1}^{n},(X_{i}^{\prime},Y_{i}^{\prime})\stackrel{{\scriptstyle\textnormal{iid}}}{{\sim}}P,\xi}\left|\ell(\hat{f}_{B}(x),y)-\ell(\hat{f}_{B}^{(i)}(x),y)\right|\leq\beta.$
(16)

Stability to leave-one-out perturbations is typically stronger than stability
to replace-one perturbations. To see this, note that, by the triangle
inequality, the replace-one perturbation can be bounded as

$|\hat{f}(x)-\hat{f}^{(i)}(x)|\leq|\hat{f}(x)-\hat{f}^{\setminus
i}(x)|+|\hat{f}^{(i)}(x)-\hat{f}^{\setminus i}(x)|,$

where both terms on the right-hand-side are leave-one-out perturbations. A
guarantee for replace-one stability thus follows immediately from Corollary
15.

######  Corollary 17.

In the setting of Corollary 16, generic bagging satisfies random replace-one
hypothesis stability at level $\beta=2L\beta_{n,m,B}$, where $\beta_{n,m,B}$
is defined in Equation 14 and $\hat{f}_{B}^{(i)}$ is obtained by running
generic bagging (Algorithm 1) with base algorithm $\mathcal{A}$, data set
$\mathcal{D}^{(i)}$, and resampling distribution $\mathcal{Q}_{n}$.

##  6 Experiments

Figure 3: Simulation results comparing the stability of subbagging
$\widetilde{\mathcal{A}}_{B}$ to that of the corresponding base algorithm
$\mathcal{A}$. Left: Histogram of leave-one-out perturbations. Right: for each
$\varepsilon$, the smallest $\delta$ such that the algorithm is
$(\varepsilon,\delta)$-stable in the sense of Definition 4. Higher curves thus
represent greater instability. In all settings, $m=n/2$ and $B=10000$.

In this section, we study the stability of subbagging in simulation
experiments. We use scikit-learn (Pedregosa et al.,, 2011). Code to reproduce
all experiments is available at https://jake-soloff.github.io/subbagging-
experiments.zip.

###  6.1 Data and Methods

We consider four simulation settings:

  * •

Setting 1: We simulate from the following data generating process:

$X_{i}\stackrel{{\scriptstyle\textnormal{iid}}}{{\sim}}\mathcal{N}(0,I_{d}),\
Y_{i}\stackrel{{\scriptstyle\textnormal{iid}}}{{\sim}}\textnormal{Bernoulli}\left(\frac{1}{2}\right),$

with sample size $n=500$ and dimension $d=250$. The base algorithm
$\mathcal{A}$ is the output of $L_{2}$-regularized logistic regression, given
by
$\mathcal{A}(\mathcal{D})(x)=\hat{f}_{\hat{\beta}}(x):=\frac{1}{1+e^{-x^{\prime}\hat{\beta}}}$,
where

$\hat{\beta}=\operatorname*{argmin}_{\beta\in\mathbb{R}^{d}}\left\\{C\sum_{i=1}^{n}(-Y_{i}\log(\hat{f}_{\beta}(X_{i}))-(1-Y_{i})\log(1-\hat{f}_{\beta}(X_{i})))+\frac{1}{2}\|\beta\|_{2}^{2}\right\\}.$

We use `sklearn.linear_model.LogisticRegression`, setting `penalty=‘l2’`,
`C=1e3/n` and `fit_intercept=False`, leaving all other parameters at their
default values.

  * •

Setting 2: Same as Setting 1, changing only the sample size to $n=1000$.

  * •

Setting 3: Same as Setting 1, changing only the base algorithm $\mathcal{A}$
to a neural network with a single hidden layer. We use
`sklearn.neural_network.MLPClassifier`, setting `hidden_layer_sizes=(40,)`,
`solver="sgd"`, `learning_rate_init=0.2`, `max_iter=8`, and `alpha=1e-4`,
leaving all other parameters at their default values.

  * •

Setting 4: We simulate from the following data generating process:

$\displaystyle(X_{i},\alpha_{i},\beta_{i})$
$\displaystyle\stackrel{{\scriptstyle\textnormal{iid}}}{{\sim}}\textnormal{Unif}([0,1]^{d})\times\textnormal{Unif}([-.25,.25])\times\textnormal{Unif}([0,1]),$
$\displaystyle Y_{i}$
$\displaystyle=\sum_{j=1}^{d}\sin\left(\frac{X_{ij}}{j}\right)+\alpha_{i}\mathbf{1}\\{i=1\
(\mathrm{mod}\ 3)\\}+\beta_{i}\mathbf{1}\\{i=1\ (\mathrm{mod}\ 4)\\},$

with $n=500$ and $d=40$. We apply `sklearn.tree.DecisionTreeRegressor` to
train the regression trees, setting `max_depth=50` and leaving all other
parameters at their default values.

###  6.2 Results

Our results are shown in Figure 3. In each setting, we apply the base
algorithm $\mathcal{A}$ as well as subbagging $\widetilde{\mathcal{A}}_{B}$
with $m=n/2$ samples in each bag, using $B=10000$ bags. The left panels of
Figure 3 show the histogram of leave-one-out perturbations
$|\hat{f}(x)-\hat{f}^{\setminus i}(x)|$ for $i\in\\{1,\ldots,n\\}$. In the
right panels of Figure 3, for a fixed data set and algorithm, we measure
stability by plotting, for each value of $\varepsilon$, the smallest value of
$\delta$ such that the algorithm is $(\varepsilon,\delta)$-stable:

$\delta=\frac{1}{n}\sum_{i=1}^{n}1_{|\hat{f}(x)-\hat{f}^{\setminus
i}(x)|>\varepsilon}.$

In each case, the test point $x=X_{n+1}$ is generated from the same
distribution as $X_{1},\ldots,X_{n}$.

For logistic regression (Settings 1 and 2), we see that the subbagged
algorithm is highly stable for both values of $n$—in particular, the blue
curves lie below the black dotted line, showing that subbagged logistic
regression satisfies the theoretical guarantee of Theorem 8. By contrast, for
$n=500$ and $d=250=n/2$ (Setting 1), the red curve lies much higher in the
plot, showing greater instability; this reveals that the base algorithm,
logistic regression (with extremely small regularization), is highly unstable
in the $d=n/2$ regime (see, e.g., Candès and Sur,, 2020). For $n=1000$ and
$d=250=n/4$ (Setting 2), on the other hand, we see that the base algorithm is
quite stable—indeed, in this setting, each bag is highly unstable (since
$d=m/2$), but the stability of subbagging is still comparable to that of the
base algorithm. These first two settings illustrate our theory by showing that
the subbagged algorithm satisfies the stability guarantee regardless of
whether the base algorithm is stable.

In Setting 3, we repeat the same experiment where the base algorithm is a
neural network. Similar to logistic regression in the $d=n/2$ regime, the
neural network base algorithm is also highly unstable. We also observe a
similar level of stability after subbagging.

In Setting 4, we simulate from a more complex data generating process, where
the response $Y_{i}$ is actually related to the covariates $X_{i}$. We again
see that the subbagged algorithm is highly stable—in particular, the blue
curve lies below the black dotted line, showing that subbagged regression
trees satisfy the theoretical guarantee of Theorem 8. By contrast, the red
curve lies much higher in the plot, showing greater instability; this reveals
that the base algorithm, a regression tree with a maximum depth of $50$, is
highly unstable.

##  7 Discussion and Related Work

In this section, we first discuss some of the important practical implications
of algorithmic stability. Next, we compare our main question to a prior work
attempting to certify stability using hypothesis testing (Kim and Barber,,
2021). Finally, we situate our work in the broader literature on the stability
of bagging, and give some concluding remarks on the implications of this work.

###  7.1 The Importance of Stability

Stability guarantees are central in a variety of contexts, despite the fact
that many widely-used practical algorithms are not stable (Xu et al.,, 2011).
For instance, Bousquet and Elisseeff, (2002) establish generalization bounds
for stable learning algorithms, and Mukherjee et al., (2006) show that
stability is necessary and sufficient for empirical risk minimization to be
consistent; related works include (Poggio et al.,, 2004; Kutin and Niyogi,,
2002; Freund et al.,, 2004). Shalev-Shwartz et al., (2010) identify stability
as a necessary and sufficient condition for learnability. Stability is further
relevant to differential privacy guarantees; assuming worst-case stability
(often called “sensitivity” in the privacy literature) is a standard starting
point for constructing differentially private algorithms (Dwork,, 2008). In
the field of conformal prediction, distribution-free coverage guarantees rely
upon the stability of the underlying estimators; (e.g., Steinberger and Leeb,,
2016, 2023; Ndiaye,, 2022; Barber et al.,, 2021). We will now discuss
applications of algorithmic stability to generalization and conformal
inference in greater detail.

####  7.1.1 Stability and Generalization

In a landmark work, Bousquet and Elisseeff, (2002) greatly expand our
understanding of the connection between stability and generalization. In their
telling, what distinguishes algorithmic stability from the pervasive uniform
convergence theory is the following: whereas the latter aims to control the
complexity of the space of learning rules an algorithm $\mathcal{A}$ searches
over, the former emphasizes how the algorithm explores that space. Algorithmic
stability notably first emerged as an invaluable tool to obtain generalization
bounds for $k$-nearest neighbors (Rogers and Wagner,, 1978), for which the
underlying function class has unbounded complexity. For algorithms like
bagging and nearest neighbors, where the strongest (nontrivial) guarantees
hold for out-of-sample stability, the empirical risk is not necessarily
reflective of test error and instead generalization holds with respect to the
leave-one-out error—that is, the average leave-one-out error is a provably
accurate estimate of the expected prediction error,

$\frac{1}{n}\sum_{i=1}^{n}\ell(\hat{f}^{\setminus
i}(X_{i}),Y_{i})\approx\mathbb{E}[\ell(\hat{f}(X),Y)],$

where the expected value is taken with respect to a new draw of $(X,Y)$ while
treating $\hat{f}$ as fixed. For an example of how random hypothesis stability
(covered in Corollary 16) leads to polynomial bounds on the generalization
error, see Elisseeff et al., (2005, Theorem 9).

####  7.1.2 Predictive Uncertainty Quantification

Algorithmic stability also plays an important role in the problem of
predictive uncertainty quantification. Suppose $(X_{i},Y_{i})_{i=1}^{n+1}$ are
iid draws from an unknown distribution $P$, and $Y_{n+1}$ is unobserved. We
wish to construct a prediction interval
$\hat{C}_{n,\alpha}=\hat{C}_{n,\alpha}(X_{n+1})$ (based on the training data
$\mathcal{D}=(X_{i},Y_{i})_{i=1}^{n}$, test covariate $X_{n+1}$ and learning
algorithm $\mathcal{A}$) that has guaranteed predictive coverage, i.e.,

$\displaystyle\mathbb{P}\left\\{Y_{n+1}\in\hat{C}_{n,\alpha}(X_{n+1})\right\\}\geq
1-\alpha,$ (17)

without any restrictions on $\mathcal{A}$ or $P$. If we wish to use an
interval of the form
$\hat{C}_{n,\alpha}(x)=[\hat{f}(x)-\hat{c},\hat{f}(x)+\hat{c}]$, centered at
the learning algorithm’s prediction $\hat{f}(x)$, a natural approach to
calibrating the radius $\hat{c}$ is to use the leave-one-out errors
$R_{i}:=|\hat{f}^{\setminus i}(X_{i})-Y_{i}|$ as representative of the test
error $|\hat{f}(X_{n+1})-Y_{n+1}|$. This leads naturally to the classical
leave-one-out technique known as the jackknife:

$\hat{C}_{n,\alpha}^{\textnormal{Jack}}(x):=[\hat{f}(x)-\hat{c}_{\alpha},\hat{f}(x)+\hat{c}_{\alpha}],$

where $\hat{c}_{\alpha}:=Q_{1-\alpha}(\\{R_{i}\\}_{i=1}^{n})$ is the
$1-\alpha$ quantile of the leave-one-out errors $R_{i}$.

If the base algorithm $\mathcal{A}$ is _unstable_ the leave-one-out errors
need not be representative of test error at all. In fact, Barber et al.,
(2021) construct a pathological example for which that the jackknife has no
coverage, i.e.,

$\mathbb{P}\left\\{Y_{n+1}\in\hat{C}^{\textnormal{Jack}}_{n,\alpha}(X_{n+1})\right\\}=0.$

Barber et al., (2021) go on to show that if the base algorithm $\mathcal{A}$
is $(\varepsilon,\delta)$-stable, then coverage can be restored by inflating
the radius to $\hat{c}_{\alpha}^{\prime}:=\hat{c}_{\alpha}+\varepsilon$ and
running the procedure at level $\alpha^{\prime}=\alpha-2\sqrt{\delta}$.

###  7.2 Is Bagging Needed for Stability?

Various learning algorithms are known to possess stability guarantees, such as
$k$-nearest neighbors (Rogers and Wagner,, 1978; Devroye and Wagner, 1979a, ),
some regularized regression methods such as ridge regression (Bousquet and
Elisseeff,, 2002; Wibisono et al.,, 2009), and models trained with stochastic
gradient descent under smoothness assumptions (Hardt et al.,, 2016).
Restricting to algorithms that are theoretically known to be stable can be
quite limiting and can sacrifice accuracy in many settings.

We might instead ask whether it is possible to validate empirically that an
algorithm $\mathcal{A}$ is stable with respect to a given data generating
distribution. However, Kim and Barber, (2021) show that it is essentially
impossible to construct powerful hypothesis tests certifying
$(\varepsilon,\delta)$-stability, without imposing assumptions on the
algorithm or on distribution of the data. In their framework, we observe
i.i.d. random variables $\mathcal{D}=(Z_{i})_{i=1}^{N}$ where
$Z_{i}\stackrel{{\scriptstyle\textnormal{iid}}}{{\sim}}P$. We wish to
construct a test $\hat{T}$ that returns an answer 1 if we are confident that
$\mathcal{A}$ is $(\varepsilon,\delta)$-stable, or a 0 otherwise. Suppose we
require that $\hat{T}$ obeys the following constraints:

  1. (a)

$\hat{T}$ satisfies a universal bound on falsely declaring stability, i.e.,
$\mathbb{P}\\{\hat{T}=1\\}\leq\alpha$ for any $\mathcal{A}$ that is _not_
$(\varepsilon,\delta)$-stable (with respect to distribution $P$ and sample
size $n$), and

  2. (b)

$\hat{T}$ is a _black-box_ test (see Kim and Barber,, 2021, Definition 2),
roughly meaning that $\hat{T}$ is only constructed using zeroth order oracle
access to the algorithm $\mathcal{A}$. That is, we may base our accept/reject
decision on evaluating the model $\mathcal{A}$ on data
$\widetilde{\mathcal{D}}$ that is simulated or resampled from the training
data $\mathcal{D}$, and compute predictions at test points $x$ that are
generated similarly, an unlimited number of times.

If a test $\hat{T}$ satisfies both properties (a) and (b) with no further
assumptions on the distribution $P$ or on the algorithm $\mathcal{A}$, their
results imply that the power of $\hat{T}$ is upper bounded by

$\mathbb{P}\\{\hat{T}=1\\}\leq(1-\delta)^{-N/n}\alpha,$

for any $\mathcal{A}$ that _is_ $(\varepsilon,\delta)$-stable (with respect to
distribution $P$ and sample size $n$). In particular, any universally valid
black-box test has low power, unless the available data set size $N$ is far
larger than the sample size $n$ for which we want to test stability.

In light of this impossibility result, a natural question is whether it is
possible to _convert_ any algorithm $\mathcal{A}$ into an
$(\varepsilon,\delta)$-stable algorithm $\widetilde{\mathcal{A}}$. Our work
establishes the possibility of _black-box stabilization_ , i.e., guaranteeing
some quantifiable level of stability with no knowledge of the inner workings
of the base algorithm. Our results support the use of bagging in such settings
by certifying a certain level of $(\varepsilon,\delta)$-stability.

###  7.3 Prior Work on the Stability of Bagging

Bühlmann and Yu, (2002) suggest (sub)bagging is most successful as a smoothing
operation, softening hard threshold rules. They measure the instability of a
procedure by its asymptotic variance: $\mathcal{A}$ is stable at
$x\in\mathcal{X}$ if $\hat{f}(x)\stackrel{{\scriptstyle p}}{{\to}}f(x)$ as
$n\to\infty$, for some fixed $f$. For some hard thresholding rules, they show
bagging can reduce asymptotic variance. See also Buja and Stuetzle, (2000).

Grandvalet, (2004, 2006) exposes some limitations of the variance-reduction
perspective. In particular, bagging need not reduce variance, and in simple
examples its improvement over the base procedure need not relate to the
original procedure’s variance. Grandvalet, illustrates through experiments a
robustness property of bagging: highly influential data points are
systematically de-emphasized. The role of $p$ in our main result, Theorem 8,
underscores Grandvalet,’s observation that the main stabilizing effect of
bagging comes from the removal of high-leverage data points from a certain
fraction of bags.

Elisseeff et al., (2005) generalize standard notions of algorithmic stability
(Bousquet and Elisseeff,, 2002) to randomized algorithms and study
(sub)bagging in this context. The authors focus on improving upon the
stability of an already-stable base algorithm $\mathcal{A}$: to ensure
$(\varepsilon,\delta)$-stability of the bagged algorithm
$\tilde{\mathcal{A}}$, they require the base algorithm $\mathcal{A}$ to be
$(\varepsilon\frac{n}{m},\delta)$-stable.

Several works consider the stability of subbagging for much smaller bags than
our guarantees require. Poggio et al., (2002) show that bagging yields
algorithmic stability when $m$ and $B$ are chosen so that each data point lies
in one bag on average. Chen et al., (2022, Theorem 5) consider subbagging when
$m=o(\sqrt{n})$ and with i.i.d. data, guaranteeing stability at the level
$\varepsilon=o(n^{-1/2})$. By contrast, our result does not require i.i.d.
data, and gives a faster rate $\varepsilon=o(n^{-3/4})$ for fixed $\delta$ and
$m=o(\sqrt{n})$ (as well as results for larger $m$, e.g., for $m=O(n)$).

###  7.4 Conclusion

Distribution-free uncertainty quantification yields principled statistical
tools which input black-box machine learning models and produce predictions
with statistical guarantees, such as distribution-free prediction or
calibration. Assumption-free stability is an important addition to this list,
with a number of practical implications. Our work establishes assumption-free
stability for bagging applied to any base algorithm with bounded outputs.
These results suggest several avenues for future investigations, including
formalizing lower bounds for distribution-free, black-box stabilization and
characterizing the (sub)optimality of bagging.

## Acknowledgements

RFB was supported by the National Science Foundation via grants DMS-1654076
and DMS-2023109, and by the Office of Naval Research via grant
N00014-20-1-2337. JAS was supported by NSF DMS-2023109. RW was supported by
NSF DMS-2023109, AFOSR FA9550-18-1-0166, and NSF DMS-1925101.

##  Appendix A Proofs

This sections contains proofs of all theoretical results from the main paper.

###  A.1 Proof of Theorem 8

We will abbreviate predicted values using
$\hat{y}\coloneqq\hat{f}_{\infty}(x)$ and $\hat{y}^{\setminus
i}\coloneqq\hat{f}_{\infty}^{\setminus i}(x)$. Define

$\mathcal{K}\coloneqq\left\\{i\in[n]:\left|\hat{y}-\hat{y}^{\setminus
i}\right|>\varepsilon\right\\},$

the set of data points with large leave-one-out perturbation, and let
$K=|\mathcal{K}|$. From Definition 4, we want to show $K\leq n\delta$. Summing
all the inequalities defining $\mathcal{K}$ gives

$K\varepsilon\leq\sum_{i\in\mathcal{K}}\left|\hat{y}-\hat{y}^{\setminus
i}\right|=:L_{1}(\mathcal{K}).$

We will now bound the error $L_{1}(\mathcal{K})$ on the right-hand side.

_Step 1: Simplifying the leave-one-out perturbation._ For any bag
$r\in\textnormal{seq}_{[n]}$, denote the value of our prediction using data
$\mathcal{D}_{r}$ by

$\hat{y}^{(r)}:=\mathbb{E}_{\xi}[\mathcal{A}(\mathcal{D}_{r};\xi)(x)].$

The aggregate prediction $\hat{y}$ can be expressed as

$\hat{y}=\mathbb{E}_{r\sim\mathcal{Q}_{n},\xi}\big{[}\mathcal{A}(\mathcal{D}_{r};\xi)(x)\big{]}=\mathbb{E}_{r\sim\mathcal{Q}_{n},\xi}\big{[}\hat{y}^{(r)}\big{]},$

while $\hat{y}^{\setminus i}$ can be expressed as

$\hat{y}^{\setminus
i}=\mathbb{E}_{r\sim\mathcal{Q}_{n-1},\xi}\big{[}\mathcal{A}((\mathcal{D}^{\setminus
i})_{r};\xi)(x)\big{]}=\mathbb{E}_{r\sim\mathcal{Q}_{n}}\big{[}\hat{y}^{(r)}\,\big{|}\,i\not\in
r\big{]},$

where the last step holds by symmetry (5). Using the definition of conditional
expectation, we have

$\displaystyle\hat{y}-\hat{y}^{\setminus i}$
$\displaystyle=\mathbb{E}_{r\sim\mathcal{Q}_{n}}\left[\hat{y}-\hat{y}^{(r)}\,\middle|\,i\not\in
r\right]$
$\displaystyle=\frac{1}{1-p}\mathbb{E}_{r\sim\mathcal{Q}_{n}}\left[(\hat{y}-\hat{y}^{(r)})\mathbf{1}\\{i\not\in
r\\}\right].$

_Step 2: Expressing $L_{1}(\mathcal{K})$ as an expectation._ Define

$s_{i}:=\textnormal{sign}(\hat{y}-\hat{y}^{\setminus
i})\cdot\mathbf{1}_{i\in\mathcal{K}}.$

For each $i\in\mathcal{K}$, $|\hat{y}-\hat{y}^{\setminus
i}|=s_{i}(\hat{y}-\hat{y}^{\setminus i})$, so by Step 1,

$\displaystyle
L_{1}(\mathcal{K})=\frac{1}{1-p}\mathbb{E}_{r\sim\mathcal{Q}_{n}}\left[(\hat{y}-\hat{y}^{(r)})\sum_{i}s_{i}\mathbf{1}_{i\not\in
r}\right].$ (18)

_Step 3: Bounding $L_{1}(\mathcal{K})$._ Since $\hat{y}^{(r)}\in[0,1]$ has
mean $\hat{y}$, applying Cauchy–Schwarz to the right-hand side of (18),

$\displaystyle L_{1}(\mathcal{K})$
$\displaystyle\leq\frac{1}{2(1-p)}\sqrt{\textnormal{Var}\left(\sum_{i}s_{i}\mathbf{1}_{i\not\in
r}\right)}.$ (19)

We calculate the variance as

$\displaystyle\textnormal{Var}\left(\sum_{i}s_{i}\mathbf{1}_{i\not\in
r}\right)$ $\displaystyle=p(1-p)\sum_{i}s_{i}^{2}-q\sum_{i\neq j}s_{i}s_{j}$
$\displaystyle=\left(p(1-p)+q\right)\sum_{i}s_{i}^{2}-q\Big{(}\sum_{i}s_{i}\Big{)}^{2}$
$\displaystyle\leq K\left(p(1-p)+q\right),$

since $q\geq 0$ and
$\sum_{i}s_{i}^{2}=\sum_{i}\mathbf{1}_{i\in\mathcal{K}}=K$. Combining
everything,

$\displaystyle K\varepsilon$
$\displaystyle\leq\frac{1}{2(1-p)}\sqrt{K(p(1-p)+q)}.$

Choosing $(\varepsilon,\delta)$ to satisfy (7) implies $K\leq n\delta$.

###  A.2 Proof of Theorem 9

Let $\hat{f}_{B}$ denote the result of bagging $\mathcal{A}$ on $\mathcal{D}$
with $B$ bags, and similarly $\hat{f}_{B}^{\setminus i}$ is the result of
bagging $\mathcal{A}$ on $\mathcal{D}^{\setminus i}$ with $B$ bags. We want to
show

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\mathbb{P}_{\boldsymbol{\xi},\boldsymbol{r}}\left\\{|\hat{f}_{B}(x)-\hat{f}_{B}^{\setminus
i}(x)|>\varepsilon+\sqrt{\frac{2}{B}\log\frac{4}{\delta^{\prime}}}\right\\}\leq\delta+\delta^{\prime},$

where $\boldsymbol{\xi}=(\xi^{(1)},\dots,\xi^{(B)})$ and
$\boldsymbol{r}=(r^{(1)},\dots,r^{(B)})$ capture the randomness in the
algorithm $\mathcal{A}$ and bagging, respectively. By the triangle inequality
and union bound,

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}$
$\displaystyle\mathbb{P}_{\boldsymbol{\xi},\boldsymbol{r}}\left\\{|\hat{f}_{B}(x)-\hat{f}_{B}^{\setminus
i}(x)|>\varepsilon+\sqrt{\frac{2}{B}\log\frac{4}{\delta^{\prime}}}\right\\}$
$\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}\mathbb{P}_{\boldsymbol{\xi},\boldsymbol{r}}\left\\{|\hat{f}_{B}(x)-\hat{f}_{\infty}(x)|>\sqrt{\frac{1}{2B}\log\frac{4}{\delta^{\prime}}}\right\\}$
$\displaystyle~{}~{}~{}~{}~{}+\frac{1}{n}\sum_{i=1}^{n}\mathbf{1}\left\\{|\hat{f}_{\infty}(x)-\hat{f}_{\infty}^{\setminus
i}(x)|>\varepsilon\right\\}$
$\displaystyle~{}~{}~{}~{}~{}+\frac{1}{n}\sum_{i=1}^{n}\mathbb{P}_{\boldsymbol{\xi},\boldsymbol{r}}\left\\{|\hat{f}_{\infty}^{\setminus
i}(x)-\hat{f}_{B}^{\setminus
i}(x)|>\sqrt{\frac{1}{2B}\log\frac{4}{\delta^{\prime}}}\right\\}.$

By Theorem 8 the middle term on the right-hand side is at most $\delta$. By
Hoeffding’s inequality,

$\mathbb{P}_{\boldsymbol{\xi},\boldsymbol{r}}\left\\{|\hat{f}_{B}(x)-\hat{f}_{\infty}(x)|>\sqrt{\frac{1}{2B}\log\frac{4}{\delta^{\prime}}}\right\\}\leq\frac{\delta^{\prime}}{2}$

and similarly for $|\hat{f}_{B}^{\setminus i}(x)-\hat{f}_{\infty}^{\setminus
i}(x)|$.

###  A.3 Proof of Theorem 10

Let $K=1+\lfloor\delta n\rfloor$ and $\eta=\frac{K}{n}>\delta$. For any
positive integer $m$, define

$\mathcal{A}^{\sharp}\Big{(}(X_{1},Y_{1}),\ldots,(X_{m},Y_{m})\Big{)}(x)\coloneqq\mathbf{1}\left\\{\sum_{i=1}^{m}X_{i}>\frac{mK}{n}\right\\}.$

Define $\mathcal{D}=\\{(x_{i},y_{i})\\}_{i=1}^{n}$ where $x_{i}=1$ for $i\leq
K$ and $x_{i}=0$ for $i>K$. For a bag $r$ consisting of $m$ indices sampled
without replacement, the algorithm $\mathcal{A}^{\sharp}$ therefore returns
the prediction $\hat{y}(r)=\mathbf{1}\\{\sum_{i\in r}X_{i}>\frac{mK}{n}\\}$.
Let $\hat{y}$ denote the average prediction, i.e., the result of subbagging
$\mathcal{A}^{\sharp}$, and let $\hat{y}^{\setminus i}$ denote the average
prediction over bags excluding $i$. It suffices to show that
$|\hat{y}-\hat{y}^{\setminus i}|>\varepsilon$ for each $i$ with $x_{i}=1$,
since we then have

$\frac{1}{n}\sum_{i=1}^{n}\mathbf{1}\left\\{|\hat{y}-\hat{y}^{\setminus
i}|>\varepsilon\right\\}\geq\frac{K}{n}=\eta>\delta,$

verifying that $\mathcal{A}^{\sharp}$ fails to be
$(\varepsilon,\delta)$-stable. Let $\hat{y}^{i}$ denote the average over all
bags containing $i$. Then for any $i\leq K$ and $j>K$ (i.e., $X_{i}=1$ and
$X_{j}=0$), by symmetry we can calculate

$\displaystyle\hat{y}$
$\displaystyle=\mathbb{E}_{r\sim\mathcal{Q}_{n}}[\hat{y}(r)]$
$\displaystyle=\frac{K}{n}\mathbb{E}_{r\sim\mathcal{Q}_{n}}[\hat{y}(r)\mid
i_{1}\leq K]+\frac{n-K}{n}\mathbb{E}_{r\sim\mathcal{Q}_{n}}[\hat{y}(r)\mid
i_{1}>K]$ $\displaystyle=\eta\mathbb{E}_{r\sim\mathcal{Q}_{n}}[\hat{y}(r)\mid
i_{1}=i]+(1-\eta)\mathbb{E}_{r\sim\mathcal{Q}_{n}}[\hat{y}(r)\mid i_{1}=j]$
$\displaystyle=\eta\mathbb{E}_{r\sim\mathcal{Q}_{n}}[\hat{y}(r)\mid i\in
r]+(1-\eta)\mathbb{E}_{r\sim\mathcal{Q}_{n}}[\hat{y}(r)\mid j\in r]$
$\displaystyle=\eta\hat{y}^{i}+\left(1-\eta\right)\hat{y}^{j}.$

Similarly, we have

$\displaystyle\hat{y}$
$\displaystyle=\mathbb{E}_{r\sim\mathcal{Q}_{n}}[\hat{y}(r)]$
$\displaystyle=p\mathbb{E}_{r\sim\mathcal{Q}_{n}}[\hat{y}(r)\mid i\in
r]+(1-p)\mathbb{E}_{r\sim\mathcal{Q}_{n}}[\hat{y}(r)\mid i\notin r]$
$\displaystyle=p\hat{y}^{i}+(1-p)\hat{y}^{\setminus i}.$

Combining these calculations,

$\hat{y}-\hat{y}^{\setminus
i}=\frac{p}{1-p}(\hat{y}^{i}-\hat{y})=\frac{p}{1-p}\left(1-\eta\right)(\hat{y}^{i}-\hat{y}^{j}).$

Similarly, noting that $\mathbb{P}\\{j\in r\mid i\in r\\}=\frac{m-1}{n-1}$, we
have

$\hat{y}^{i}=\frac{m-1}{n-1}\hat{y}^{ij}+\frac{n-m}{n-1}\hat{y}^{i\setminus
j},$

where $\hat{y}^{ij}$ averages $\hat{y}(r)$ over bags containing both $i$ and
$j$, and similarly $\hat{y}^{i\setminus j}$ averages over bags containing $i$
and not $j$. Similarly,
$\hat{y}^{j}=\frac{m-1}{n-1}\hat{y}^{ij}+\frac{n-m}{n-1}\hat{y}^{j\setminus
i}$, and therefore,
$\hat{y}^{i}-\hat{y}^{j}=\frac{n-m}{n-1}(\hat{y}^{i\setminus
j}-\hat{y}^{j\setminus i})$. We write $\hat{y}^{i\setminus j}$ and
$\hat{y}^{j\setminus i}$ as hypergeometric tail probabilities:

$\displaystyle\hat{y}^{i\setminus j}$
$\displaystyle=\mathbb{P}_{H\sim\textnormal{HyperGeometric}(n-2,m-1,K-1)}\left\\{1+H>\frac{mK}{n}\right\\}$
$\displaystyle\hat{y}^{j\setminus i}$
$\displaystyle=\mathbb{P}_{H\sim\textnormal{HyperGeometric}(n-2,m-1,K-1)}\left\\{H>\frac{mK}{n}\right\\}.$

Combining our findings,

$\displaystyle\hat{y}-\hat{y}^{\setminus i}$
$\displaystyle=\frac{p\left(1-\eta\right)}{1-p}\frac{n-m}{n-1}(\hat{y}^{i\setminus
j}-\hat{y}^{j\setminus i})$
$\displaystyle=\frac{m\left(1-\eta\right)}{n-1}\mathbb{P}_{H\sim\textnormal{HyperGeometric}(n-2,m-1,K-1)}\left\\{H=\left\lfloor\frac{mK}{n}\right\rfloor\right\\}$
$\displaystyle=\frac{m-\left\lfloor\frac{mK}{n}\right\rfloor}{n}\mathbb{P}_{H\sim\textnormal{HyperGeometric}(n-1,m,K-1)}\left\\{H=\left\lfloor\frac{mK}{n}\right\rfloor\right\\}$
$\displaystyle\geq(1-\delta-n^{-1})p\mathbb{P}_{H\sim\textnormal{HyperGeometric}(n-1,m,K-1)}\left\\{H=\lfloor
p(1+\lfloor n\delta\rfloor)\rfloor\right\\}$ $\displaystyle>\varepsilon,$

where the last step holds by assumption on $\varepsilon$. This verifies that
$(\varepsilon,\delta)$-stability fails to hold, and thus completes the proof.

###  A.4 Proof of Theorem 12

This result follows from the proof of Theorem 8 if we substitute Equation 19
with

$L_{1}(\mathcal{K})\leq\frac{R^{*}(\mathcal{D},x)}{2(1-p)}\sqrt{\textnormal{Var}\left(\sum_{i}s_{i}\mathbf{1}_{i\not\in
r}\right)}.$

###  A.5 Proof of Theorem 13

By the triangle inequality,

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}$
$\displaystyle\mathbf{1}\left\\{|\hat{f}_{\infty,I}(x)-\hat{f}_{\infty,I}^{\setminus
i}(x)|>\varepsilon\,\textnormal{length}(I(\mathcal{D}))\right\\}$
$\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}\mathbf{1}\left\\{\frac{|\hat{f}_{\infty,I}(x)-\hat{f}_{\infty,I}^{\setminus
i}(x)|}{R(\mathcal{D},x)}>\varepsilon,I(\mathcal{D})=I(\mathcal{D}^{\setminus
i})\right\\}$
$\displaystyle~{}~{}~{}~{}~{}+\frac{1}{n}\sum_{i=1}^{n}\mathbf{1}\left\\{I(\mathcal{D})\neq
I(\mathcal{D}^{\setminus i})\right\\}.$

It suffices to show that the first term on the right-hand side is at most
$\delta$.

Let $I_{0}:=I(\mathcal{D})$ denote the interval based on the full data set.
Define a new algorithm $\mathcal{A}^{*}$ that clips the output to $I_{0}$
regardless of the input data set. That is, for any data set
$\mathcal{D}^{\prime}$ and test point $x\in\mathcal{X}$,

$\mathcal{A}^{*}(\mathcal{D}^{\prime})(x):=\frac{\mathbb{E}_{\xi}\left[\textnormal{Clip}_{I_{0}}(\mathcal{A}(\mathcal{D}^{\prime};\xi)(x))\right]-\inf
I_{0}}{\textnormal{length}(I_{0})}.$

This modified base algorithm has bounded outputs—that is,
$\mathcal{A}^{*}(\mathcal{D}^{\prime})(x)\in[0,1]$. Let
$\hat{f}_{\infty}^{*}=\widetilde{\mathcal{A}}^{*}_{\infty}(\mathcal{D})$
denote the result of derandomized bagging (Algorithm 2) on the modified base
algorithm $\mathcal{A}^{*}$, and similarly let $\hat{f}_{\infty}^{*\setminus
i}=\widetilde{\mathcal{A}}^{*}_{\infty}(\mathcal{D}^{\setminus i})$. For any
$i\in[n]$, on the event $I(\mathcal{D})=I(\mathcal{D}^{\setminus i})$, we have

$\frac{|\hat{f}_{\infty,I}(x)-\hat{f}_{\infty,I}^{\setminus
i}(x)|}{R(\mathcal{D},x)}=|\hat{f}_{\infty}^{*}(x)-\hat{f}_{\infty}^{*\setminus
i}(x)|.$

Hence, applying Theorem 8 to the modified base algorithm $\mathcal{A}^{*}$,

$\frac{1}{n}\sum_{i=1}^{n}\mathbf{1}\left\\{\frac{|\hat{f}_{\infty,I}(x)-\hat{f}_{\infty,I}^{\setminus
i}(x)|}{R(\mathcal{D},x)}>\varepsilon,I(\mathcal{D})=I(\mathcal{D}^{\setminus
i})\right\\}\leq\frac{1}{n}\sum_{i=1}^{n}\mathbf{1}\left\\{|\hat{f}_{\infty}^{*}(x)-\hat{f}_{\infty}^{*\setminus
i}(x)|>\varepsilon\right\\}\leq\delta,$

completing the proof.

###  A.6 Proof of Theorem 14

_(i)_ Fix $\mathcal{A},\mathcal{D},x$, and let
$\hat{f}_{\infty}^{i}=\mathbb{E}_{r\sim\mathcal{Q}_{n},\xi}[\hat{f}^{(r)}\mid
i\in r]$. Observe that
$\hat{f}=p\hat{f}_{\infty}^{i}+(1-p)\hat{f}_{\infty}^{\setminus i}$, so

$|\hat{f}_{\infty}(x)-\hat{f}_{\infty}^{\setminus
i}(x)|=p|\hat{f}_{\infty}^{i}(x)-\hat{f}_{\infty}^{\setminus i}(x)|\leq p$

for all $i$. This proves $(p,0)$-stability, and therefore,
$(p,\delta)$-stability holds for all $\delta$.

_(ii)_ Let
$\mathcal{A}^{\dagger}(\mathcal{D})(x)=\mathbf{1}\\{\exists(\tilde{x},\tilde{y})\in\mathcal{D}:\tilde{x}=x\\}$—i.e.,
the algorithm checks whether $x$ belongs to the training bag. Take
$\mathcal{D}=(x_{i},y_{i})_{i=1}^{n}$ such that every $x_{i}$ is unique. Then,
for each $i$, $\hat{f}_{\infty}^{\setminus i}(x_{i})=0$, whereas
$\hat{f}_{\infty}(x_{i})=p$.

###  A.7 Proof of Corollary 15

Integrating Hoeffding’s inequality,

$\mathbb{E}_{\boldsymbol{\xi},\boldsymbol{r}}|\hat{f}_{B}(x)-\hat{f}_{\infty}(x)|\leq\int_{0}^{1}2\exp\left(-2Bt^{2}\right)\text{d}t\leq\sqrt{\frac{\pi}{2B}},$

and similarly for $|\hat{f}_{B}^{\setminus i}(x)-\hat{f}_{\infty}^{\setminus
i}(x)|$.

By Theorem 8,

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\left|\hat{f}_{\infty}(x)-\hat{f}_{\infty}^{\setminus
i}(x)\right|=\int_{0}^{1}\frac{1}{n}\sum_{i=1}^{n}1\Big{\\{}\left|\hat{f}_{\infty}(x)-\hat{f}_{\infty}^{\setminus
i}(x)\right|>\varepsilon\Big{\\}}\;\textnormal{d}\varepsilon$
$\displaystyle\leq\int_{0}^{1}\min\left\\{1,\frac{1}{4n\varepsilon^{2}}\left(\frac{p}{1-p}+\frac{q}{(1-p)^{2}}\right)\right\\}\;\textnormal{d}\varepsilon\leq\sqrt{\frac{1}{n}\left(\frac{p}{1-p}+\frac{q}{(1-p)^{2}}\right)}.$

Combining these bounds via the triangle inequality completes the proof.

###  A.8 Proof of Corollary 16

Since the loss is $L$-Lipschitz,

$\displaystyle\mathbb{E}_{(Z_{i})_{i=1}^{n+1}\stackrel{{\scriptstyle\textnormal{iid}}}{{\sim}}P,\boldsymbol{\xi},\boldsymbol{r}}$
$\displaystyle\left|\ell(\hat{f}_{B}(X_{n+1}),Y_{n+1})-\ell(\hat{f}_{B}^{\setminus
i}(X_{n+1}),Y_{n+1})\right|$ $\displaystyle\leq
L\,\mathbb{E}_{(Z_{i})_{i=1}^{n+1}\stackrel{{\scriptstyle\textnormal{iid}}}{{\sim}}P,\boldsymbol{\xi},\boldsymbol{r}}\left|\hat{f}_{B}(X_{n+1})-\hat{f}_{B}^{\setminus
i}(X_{n+1})\right|$
$\displaystyle=L\,\mathbb{E}_{(Z_{i})_{i=1}^{n+1}\stackrel{{\scriptstyle\textnormal{iid}}}{{\sim}}P}\left[\frac{1}{n}\sum_{j=1}^{n}\mathbb{E}_{\boldsymbol{\xi},\boldsymbol{r}}\left|\hat{f}_{B}(X_{n+1})-\hat{f}_{B}^{\setminus
j}(X_{n+1})\right|\right]$

The result follows upon applying Corollary 15.

##  Appendix B Unbounded Outputs with Finite $B$

In this section, we present analogous results to Theorems 12 and 13 for the
finite $B$ case.

######  Theorem 18.

Let $\hat{\mathcal{Y}}=\mathbb{R}$. Fix a distribution $\mathcal{Q}_{n}$ on
$\textnormal{seq}_{[n]}$ satisfying Assumptions 5 and 7, and let
$\mathcal{Q}_{n-1}$ be defined as in (6). Let $(\varepsilon,\delta)$ satisfy
Equation 7 and fix $\delta^{\prime}>0$. For any algorithm $\mathcal{A}$,
generic bagging $\widetilde{\mathcal{A}}_{B}$ is
$(\varepsilon+\sqrt{\frac{2}{B}\log\left(\frac{4}{\delta^{\prime}}\right)},\delta+\delta^{\prime},\bar{R})$-stable,
where

$\displaystyle\bar{R}(\mathcal{D},x):=\sup_{r\in\textnormal{seq}_{[n]},\xi\in[0,1]}\mathcal{A}(\mathcal{D}_{r};\xi)(x)-\inf_{r\in\textnormal{seq}_{[n]},\xi\in[0,1]}\mathcal{A}(\mathcal{D}_{r};\xi)(x).$
(20)

Theorem 18 is proved the same way as Theorem 9, where we apply Theorem 12
instead of Theorem 8. Next we present our result for adaptively clipped
bagging in the finite-$B$ regime.

######  Theorem 19.

Let $\hat{\mathcal{Y}}=\mathbb{R}$. Fix a distribution $\mathcal{Q}_{n}$ on
$\textnormal{seq}_{[n]}$ satisfying Assumptions 5 and 7, and let
$\mathcal{Q}_{n-1}$ be defined as in (6). Suppose the mapping to intervals $I$
satisfies

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\mathbf{1}\\{I(\mathcal{D})\neq
I(\mathcal{D}^{\setminus i})\\}\leq\delta_{I}.$ (21)

Let $R(\mathcal{D},x)=\textnormal{length}(I(\mathcal{D}))$, let
$(\varepsilon,\delta)$ satisfy Equation 7 and fix $\delta^{\prime}>0$. For any
algorithm $\mathcal{A}$, adaptively clipped bagging
$\widetilde{\mathcal{A}}_{B,I}$ is
$\left(\varepsilon+\sqrt{\frac{2}{B}\log\left(\frac{4}{\delta^{\prime}}\right)},\delta_{I}+\delta+\delta^{\prime},R\right)$-stable.

###### Proof.

As in the proof of Theorem 13,

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}$
$\displaystyle\,\mathbb{P}\left\\{|\hat{f}_{B,I}(x)-\hat{f}_{B,I}^{\setminus
i}(x)|>\varepsilon\,R(\mathcal{D},x)\right\\}$
$\displaystyle\leq\delta_{I}+\frac{1}{n}\sum_{i=1}^{n}\mathbb{P}\left\\{\frac{|\hat{f}_{B,I}(x)-\hat{f}_{B,I}^{\setminus
i}(x)|}{R(\mathcal{D},x)}>\varepsilon,I(\mathcal{D})=I(\mathcal{D}^{\setminus
i})\right\\}.$

From this point on, following the same arguments as in the proof of Theorem
13, we complete the proof via an application of Theorem 9. ∎

## References

  * Agarwal et al., (2014) Agarwal, S., Milner, H., Kleiner, A., Talwalkar, A., Jordan, M., Madden, S., Mozafari, B., and Stoica, I. (2014).  Knowing when you’re wrong: building fast and reliable approximate query processing systems.  In International Conference on Management of Data (SIGMOD), pages 481–492.
  * Andonova et al., (2002) Andonova, S., Elisseeff, A., Evgeniou, T., and Pontil, M. (2002).  A simple algorithm for learning stable machines.  In European Conference on Artificial Intelligence (ECAI), pages 513–517.
  * Barber et al., (2021) Barber, R. F., Candes, E. J., Ramdas, A., and Tibshirani, R. J. (2021).  Predictive inference with the jackknife+.  The Annals of Statistics, 49(1):486–507.
  * Basu et al., (2018) Basu, S., Kumbier, K., Brown, J. B., and Yu, B. (2018).  Iterative random forests to discover predictive and stable high-order interactions.  Proceedings of the National Academy of Sciences, 115(8):1943–1948.
  * Ben-David et al., (2007) Ben-David, S., Pál, D., and Simon, H. U. (2007).  Stability of $k$-means clustering.  In International Conference on Computational Learning Theory (COLT), pages 20–34.
  * Bousquet and Elisseeff, (2002) Bousquet, O. and Elisseeff, A. (2002).  Stability and generalization.  The Journal of Machine Learning Research, 2:499–526.
  * (7) Breiman, L. (1996a).  Bagging predictors.  Machine learning, 24(2):123–140.
  * (8) Breiman, L. (1996b).  Heuristics of instability and stabilization in model selection.  The Annals of Statistics, 24(6):2350–2383.
  * Breiman, (2001) Breiman, L. (2001).  Random forests.  Machine learning, 45(1):5–32.
  * Bühlmann and Yu, (2002) Bühlmann, P. and Yu, B. (2002).  Analyzing bagging.  The Annals of Statistics, 30(4):927–961.
  * Buja and Stuetzle, (2000) Buja, A. and Stuetzle, W. (2000).  Smoothing effects of bagging.  Preprint. AT&T Labs-Research.
  * Candès and Sur, (2020) Candès, E. J. and Sur, P. (2020).  The phase transition for the existence of the maximum likelihood estimate in high-dimensional logistic regression.  The Annals of Statistics, 48(1):27 – 42.
  * Chen et al., (2022) Chen, Q., Syrgkanis, V., and Austern, M. (2022).  Debiased machine learning without sample-splitting for stable estimators.  In Advances in Neural Information Processing Systems (NeurIPS).
  * (14) Devroye, L. and Wagner, T. (1979a).  Distribution-free inequalities for the deleted and holdout error estimates.  IEEE Transactions on Information Theory, 25(2):202–207.
  * (15) Devroye, L. and Wagner, T. (1979b).  Distribution-free performance bounds for potential function rules.  IEEE Transactions on Information Theory, 25(5):601–604.
  * Dietterich, (2000) Dietterich, T. G. (2000).  Ensemble methods in machine learning.  In International workshop on multiple classifier systems, pages 1–15. Springer.
  * Dwork, (2008) Dwork, C. (2008).  Differential privacy: A survey of results.  In Theory and Applications of Models of Computation (TAMC), pages 1–19.
  * Dwork and Feldman, (2018) Dwork, C. and Feldman, V. (2018).  Privacy-preserving prediction.  In International Conference on Computational Learning Theory (COLT), pages 1693–1702.
  * Efron, (1979) Efron, B. (1979).  Bootstrap methods: another look at the jackknife.  The Annals of Statistics, 7(1):1 – 26.
  * Elisseeff et al., (2005) Elisseeff, A., Evgeniou, T., Pontil, M., and Kaelbing, L. P. (2005).  Stability of randomized learning algorithms.  Journal of Machine Learning Research, 6(1).
  * Freund et al., (2004) Freund, Y., Mansour, Y., and Schapire, R. E. (2004).  Generalization bounds for averaged classifiers.  The Annals of Statistics, 32(4):1698–1722.
  * Grandvalet, (2004) Grandvalet, Y. (2004).  Bagging equalizes influence.  Machine Learning, 55(3):251–270.
  * Grandvalet, (2006) Grandvalet, Y. (2006).  Stability of bagged decision trees.  In Scientific Meeting of the Italian Statistical Society (SIS), pages 221–230.
  * Hardt et al., (2016) Hardt, M., Recht, B., and Singer, Y. (2016).  Train faster, generalize better: Stability of stochastic gradient descent.  In International Conference on Machine Learning (ICML), pages 1225–1234. PMLR.
  * Harrington, (2003) Harrington, E. F. (2003).  Online ranking/collaborative filtering using the perceptron algorithm.  In International Conference on Machine Learning (ICML), pages 250–257.
  * Kearns and Ron, (1999) Kearns, M. and Ron, D. (1999).  Algorithmic stability and sanity-check bounds for leave-one-out cross vaildation.  Neural Computation, 11(6):1427–1453.
  * Kim and Barber, (2021) Kim, B. and Barber, R. F. (2021).  Black box tests for algorithmic stability.  arXiv preprint arXiv:2111.15546.
  * Kleiner et al., (2014) Kleiner, A., Talwalkar, A., Sarkar, P., and Jordan, M. I. (2014).  A scalable bootstrap for massive data.  Journal of the Royal Statistical Society: Series B: Statistical Methodology, pages 795–816.
  * Kutin and Niyogi, (2002) Kutin, S. and Niyogi, P. (2002).  Almost-everywhere algorithmic stability and generalization error.  In Conference on Uncertainty in Artificial Intelligence (UAI), page 275?282.
  * LeJeune et al., (2020) LeJeune, D., Javadi, H., and Baraniuk, R. (2020).  The implicit regularization of ordinary least squares ensembles.  In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 3525–3535. PMLR.
  * LeJeune et al., (2022) LeJeune, D., Patil, P., Javadi, H., Baraniuk, R. G., and Tibshirani, R. J. (2022).  Asymptotics of the sketched pseudoinverse.  arXiv preprint arXiv:2211.03751.
  * Meinshausen and Bühlmann, (2010) Meinshausen, N. and Bühlmann, P. (2010).  Stability selection.  Journal of the Royal Statistical Society: Series B (Statistical Methodology), 72(4):417–473.
  * Mukherjee et al., (2006) Mukherjee, S., Niyogi, P., Poggio, T., and Rifkin, R. (2006).  Learning theory: stability is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization.  Advances in Computational Mathematics, 25(1):161–193.
  * Ndiaye, (2022) Ndiaye, E. (2022).  Stable conformal prediction sets.  In International Conference on Machine Learning (ICML), pages 16462–16479. PMLR.
  * Oza and Russell, (2001) Oza, N. C. and Russell, S. J. (2001).  Online bagging and boosting.  In International Workshop on Artificial Intelligence and Statistics, pages 229–236. PMLR.
  * Pedregosa et al., (2011) Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., and Duchesnay, E. (2011).  Scikit-learn: Machine learning in Python.  Journal of Machine Learning Research, 12:2825–2830.
  * Poggio et al., (2004) Poggio, T., Rifkin, R., Mukherjee, S., and Niyogi, P. (2004).  General conditions for predictivity in learning theory.  Nature, 428(6981):419–422.
  * Poggio et al., (2002) Poggio, T., Rifkin, R., Mukherjee, S., and Rakhlin, A. (2002).  Bagging regularizes.  Technical report, MIT.
  * Ren et al., (2021) Ren, Z., Wei, Y., and Candès, E. (2021).  Derandomizing knockoffs.  Journal of the American Statistical Association, pages 1–11.
  * Rogers and Wagner, (1978) Rogers, W. H. and Wagner, T. J. (1978).  A finite sample distribution-free performance bound for local discrimination rules.  The Annals of Statistics, pages 506–514.
  * Shah and Samworth, (2013) Shah, R. D. and Samworth, R. J. (2013).  Variable selection with error control: another look at stability selection.  Journal of the Royal Statistical Society: Series B (Statistical Methodology), 75(1):55–80.
  * Shalev-Shwartz et al., (2010) Shalev-Shwartz, S., Shamir, O., Srebro, N., and Sridharan, K. (2010).  Learnability, stability and uniform convergence.  The Journal of Machine Learning Research, 11:2635–2670.
  * Steinberger and Leeb, (2016) Steinberger, L. and Leeb, H. (2016).  Leave-one-out prediction intervals in linear regression models with many variables.  arXiv preprint arXiv:1602.05801.
  * Steinberger and Leeb, (2023) Steinberger, L. and Leeb, H. (2023).  Conditional predictive inference for stable algorithms.  The Annals of Statistics, 51(1):290–311.
  * Valentini and Masulli, (2002) Valentini, G. and Masulli, F. (2002).  Ensembles of learning machines.  In Italian workshop on neural nets (WIRN), pages 3–20.
  * Wibisono et al., (2009) Wibisono, A., Rosasco, L., and Poggio, T. (2009).  Sufficient conditions for uniform stability of regularization algorithms.  Computer Science and Artificial Intelligence Laboratory Technical Report, MIT-CSAIL-TR-2009-060.
  * Xu et al., (2011) Xu, H., Caramanis, C., and Mannor, S. (2011).  Sparse algorithms are not stable: A no-free-lunch theorem.  IEEE transactions on pattern analysis and machine intelligence, 34(1):187–193.
  * Yu, (2013) Yu, B. (2013).  Stability.  Bernoulli, 19(4):1484–1500.