# Chebyshev-Cantelli PAC-Bayes-Bennett Inequality for the Weighted Majority
Vote

Yi-Shan Wu
University of Copenhagen
<EMAIL_ADDRESS>
&Andrés R. Masegosa
University of Almería
<EMAIL_ADDRESS>
&Stephan S. Lorenzen
University of Copenhagen
<EMAIL_ADDRESS>
&Christian Igel
University of Copenhagen
<EMAIL_ADDRESS>
&Yevgeny Seldin
University of Copenhagen
<EMAIL_ADDRESS>

###### Abstract

We present a new second-order oracle bound for the expected risk of a weighted
majority vote. The bound is based on a novel parametric form of the Chebyshev-
Cantelli inequality (a.k.a. one-sided Chebyshev’s), which is amenable to
efficient minimization. The new form resolves the optimization challenge faced
by prior oracle bounds based on the Chebyshev-Cantelli inequality, the
C-bounds (Germain et al., 2015), and, at the same time, it improves on the
oracle bound based on second order Markov’s inequality introduced by Masegosa
et al. (2020). We also derive the PAC-Bayes-Bennett inequality, which we use
for empirical estimation of the oracle bound. The PAC-Bayes-Bennett inequality
improves on the PAC-Bayes-Bernstein inequality by Seldin et al. (2012). We
provide an empirical evaluation demonstrating that the new bounds can improve
on the work by Masegosa et al. (2020). Both the parametric form of the
Chebyshev-Cantelli inequality and the PAC-Bayes-Bennett inequality may be of
independent interest for the study of concentration of measure in other
domains.

##  1 Introduction

Weighted majority vote is a central technique for combining predictions of
multiple classifiers. It is an integral part of random forests (Breiman, 1996,
2001), boosting (Freund and Schapire, 1996), gradient boosting (Friedman,
1999, 2001; Mason et al., 1999; Chen and Guestrin, 2016), and it is also used
to combine predictions of heterogeneous classifiers. It is part of the winning
strategies in many machine learning competitions. The power of the majority
vote is in the cancellation of errors effect: when the errors of individual
classifiers are independent or anticorrelated and the error probability of
individual classifiers is smaller than $0.5$, then the errors average out and
the majority vote tends to outperform the individual classifiers.

Generalization bounds for weighted majority vote and theoretically-grounded
approaches to weight tuning are decades-old research topics. Berend and
Kontorovich (2016) derived an optimal solution under the assumption of known
error rates and independence of errors of individual classifiers, but neither
of the two assumptions is typically satisfied in practice.

In absence of the independence assumption, the most basic result is the first
order oracle bound, which is based on Markov’s inequality and bounds the
expected loss of $\rho$-weighted majority vote by twice the $\rho$-weighted
average of expected losses of the individual classifiers. This finding is so
old and basic that Langford and Shawe-Taylor (2002) call it “the folk
theorem”. The $\rho$-weighted average of the expected losses is then bounded
using PAC-Bayesian bounds, turning the oracle bound into an empirical bound
(McAllester, 1998; Seeger, 2002; Langford and Shawe-Taylor, 2002). While the
translation from oracle to empirical bound is quite tight (Germain et al.,
2009; Thiemann et al., 2017), the first order oracle bound ignores the
correlation of errors, which is the main power of the majority vote. As a
result, its minimization overconcentrates the weights on the best-performing
classifiers, effectively reducing the majority vote to a very few or even just
a single best classifier, which leads to a significant deterioration of the
test error on hold-out data (Lorenzen et al., 2019; Masegosa et al., 2020).

In order to take correlation of errors into account, Lacasse et al. (2007)
derived second order oracle bounds, the C-bounds, which are based on the
Chebyshev-Cantelli inequality. The ideas were further developed by Laviolette
et al. (2011), Germain et al. (2015), and Laviolette et al. (2017). However,
they were only able to optimize the bounds in highly restrictive settings and,
additionally, second order oracle quantities in the denominator of the oracle
bounds led to looseness in translation to empirical bounds.

Masegosa et al. (2020) proposed an alternative second-order oracle bound, the
tandem bound, based on second order Markov’s inequality. While the second
order Markov’s inequality is weaker than the Chebyshev-Cantelli inequality,
the resulting bound has no oracle quantities in the denominator, which allows
tight translation to an empirical bound. Additionally, Masegosa et al.
proposed an efficient procedure for minimization of their empirical bound.
They have shown that minimization of the empirical bound does not lead to
deterioration of the test error.

Our work can be seen as a bridge between the tandem bound and the C-bounds,
and as an improvement of both. The key novelty is a new parametric form of
Chebyshev-Cantelli inequality, which preserves the tightness of Chebyshev-
Cantelli, but avoids oracle quantities in the denominator. This allows both
efficient translation to empirical bounds and efficient minimization. We
derive two new second order oracle bounds based on the new inequality, one
using the tandem loss and the other using the tandem loss with an offset. For
empirical estimation of the latter we derive a PAC-Bayes-Bennett inequality.
The overall contributions can be summarized as follows:

  1. 1.

We propose a new parametric form of the Chebyshev-Cantelli inequality, which
has no variance in the denominator and preserves tightness of the original
bound. The new form allows efficient minimization and empirical estimation.

  2. 2.

We propose two new second order oracle bounds for the weighted majority vote
based on the new form of the Chebyshev-Cantelli inequality. The bounds have
two advantages: (1) they are amenable to tight translation to empirical
bounds; and (2) the resulting empirical bounds are amenable to efficient
minimization.

  3. 3.

We derive a PAC-Bayes-Bennett inequality, which improves on the PAC-Bayes-
Bernstein inequality by Seldin et al. (2012). The inequality is used for
bounding the tandem loss with an offset.

##  2 Problem setup

The problem setup and notations are borrowed from Masegosa et al. (2020).

##### Multiclass classification.

We let $S=\\{(X_{1},Y_{1}),\ldots,(X_{n},Y_{n})\\}$ be an independent
identically distributed sample from $\cal{X}\times\cal{Y}$, drawn according to
an unknown distribution $D$, where $\cal{Y}$ is finite and $\cal{X}$ is
arbitrary. A hypothesis is a function $h:\cal{X}\rightarrow\cal{Y}$, and $\cal
H$ denotes a space of hypotheses. We evaluate the quality of $h$ using the
zero-one loss $\ell(h(X),Y)=\mathds{1}{\left(h(X)\neq Y\right)}$, where
$\mathds{1}{\left(\cdot\right)}$ is the indicator function. The expected loss
of $h$ is denoted by $L(h)=\mathbb{E}_{(X,Y)\sim D}[\ell(h(X),Y)]$ and the
empirical loss of $h$ on a sample $S$ of size $n$ is denoted by
$\hat{L}(h,S)=\frac{1}{n}\sum_{i=1}^{n}\ell(h(X_{i}),Y_{i})$.

##### Randomized classifiers.

A _randomized classifier_ (a.k.a. Gibbs classifier) associated with a
distribution $\rho$ on $\cal{H}$, for each input $X$ randomly draws a
hypothesis $h\in{\cal H}$ according to $\rho$ and predicts $h(X)$. The
expected loss of a randomized classifier is given by
$\mathbb{E}_{h\sim\rho}[L(h)]$ and the empirical loss by
$\mathbb{E}_{h\sim\rho}[\hat{L}(h,S)]$. To simplify the notation we use
$\mathbb{E}_{D}[\cdot]$ as a shorthand for $\mathbb{E}_{(X,Y)\sim D}[\cdot]$
and $\mathbb{E}_{\rho}[\cdot]$ as a shorthand for
$\mathbb{E}_{h\sim\rho}[\cdot]$.

##### Ensemble classifiers and majority vote.

Ensemble classifiers predict by taking a weighted aggregation of predictions
by hypotheses from ${\cal H}$. The $\rho$-weighted majority vote
$\operatorname{MV}_{\rho}$ predicts
$\operatorname{MV}_{\rho}(X)=\arg\max_{y\in{\cal
Y}}\mathbb{E}_{\rho}[\mathds{1}{\left(h(X)=y\right)}]$, where ties can be
resolved arbitrarily.

##  3 A review of prior first and second order oracle bounds

If majority voting makes an error, we know that at least a $\rho$-weighted
half of the classifiers have made an error and, therefore,
$\ell(\operatorname{MV}_{\rho}(X),Y)\leq\mathds{1}{\left(\mathbb{E}_{\rho}[\mathds{1}{\left(h(X)\neq
Y\right)}]\geq 0.5\right)}$. This observation leads to the well-known first
order oracle bound for the loss of weighted majority vote.

######  Theorem 1 (First Order Oracle Bound).

$L(\operatorname{MV}_{\rho})\leq 2\mathbb{E}_{\rho}[L(h)].$

###### Proof.

We have
$L(\operatorname{MV}_{\rho})=\mathbb{E}_{D}[\ell(\operatorname{MV}_{\rho}(X),Y)]\leq\mathbb{P}{\left(\mathbb{E}_{\rho}[\mathds{1}{\left(h(X)\neq
Y\right)}]\geq 0.5\right)}$. By applying Markov’s inequality to random
variable $Z=\mathbb{E}_{\rho}[\mathds{1}{\left(h(X)\neq Y\right)}]$ we have:

$L(\operatorname{MV}_{\rho})\leq\mathbb{P}{\left(\mathbb{E}_{\rho}[\mathds{1}{\left(h(X)\neq
Y\right)}]\geq 0.5\right)}\leq
2\mathbb{E}_{D}[\mathbb{E}_{\rho}[\mathds{1}{\left(h(X)\neq
Y\right)}]]=2\mathbb{E}_{\rho}[L(h)].\qed$

PAC-Bayesian analysis can be used to bound $\mathbb{E}_{\rho}[L(h)]$ in
Theorem 1 in terms of $\mathbb{E}_{\rho}[\hat{L}(h,S)]$, thus turning the
oracle bound into an empirical one. The disadvantage of the first order
approach is that $\mathbb{E}_{\rho}[L(h)]$ ignores correlations of
predictions, which is the main power of the majority vote.

Masegosa et al. (2020) have used second order Markov’s inequality, by which
for a non-negative random variable $Z$ and $\varepsilon>0$

$\mathbb{P}{\left(Z\geq\varepsilon\right)}=\mathbb{P}{\left(Z^{2}\geq\varepsilon^{2}\right)}\leq\frac{\mathbb{E}\left[Z^{2}\right]}{\varepsilon^{2}}.$

For pairs of hypotheses $h$ and $h^{\prime}$ they have defined _tandem loss_
$\ell(h(X),h^{\prime}(X),Y)=\mathds{1}{\left(h(X)\neq Y\wedge
h^{\prime}(X)\neq Y\right)}=\mathds{1}{\left(h(X)\neq
Y\right)}\mathds{1}{\left(h^{\prime}(X)\neq Y\right)}$, also termed joint
error by Lacasse et al. (2007), which counts an error only if both $h$ and
$h^{\prime}$ err on a sample $(X,Y)$. The corresponding _expected tandem loss_
is defined by

$L(h,h^{\prime})=\mathbb{E}_{D}[\mathds{1}{\left(h(X)\neq
Y\right)}\mathds{1}{\left(h^{\prime}(X)\neq Y\right)}].$

Lacasse et al. (2007) and Masegosa et al. (2020) have shown that expectation
of the second moment of the weighted loss equals expectation of the tandem
loss. Using $\rho^{2}$ as a shorthand for the product distribution
$\rho\times\rho$ over $\mathcal{H}\times\mathcal{H}$ and
$\mathbb{E}_{\rho^{2}}[L(h,h^{\prime})]$ as a shorthand for
$\mathbb{E}_{h\sim\rho,h^{\prime}\sim\rho}[L(h,h^{\prime})]$, the result is
the following.

######  Lemma 2 (Masegosa et al., 2020).

In multiclass classification

$\mathbb{E}_{D}[\mathbb{E}_{\rho}[\mathds{1}{\left(h(X)\neq
Y\right)}]^{2}]=\mathbb{E}_{\rho^{2}}[L(h,h^{\prime})].$

By combining second order Markov’s inequality with Lemma 2, Masegosa et al.
have shown the following result.

######  Theorem 3 (Masegosa et al., 2020).

In multiclass classification

$L(\operatorname{MV}_{\rho})\leq 4\mathbb{E}_{\rho^{2}}[L(h,h^{\prime})].$

Lacasse et al. (2007) have used the Chebyshev-Cantelli inequality to derive a
different form of a second order oracle bound. We use
$\mathbb{V}\left[Z\right]$ to denote the variance of $Z$ in the statement of
Chebyshev-Cantelli inequality.

######  Theorem 4 (Chebyshev-Cantelli inequality).

For $\varepsilon>0$

$\mathbb{P}{\left(Z-\mathbb{E}\left[Z\right]\geq\varepsilon\right)}\leq\frac{\mathbb{V}\left[Z\right]}{\varepsilon^{2}+\mathbb{V}\left[Z\right]}.$

Theorem 4 together with Lemma 2 leads to the following result, known as the
_C-bound_.

######  Theorem 5 (Lacasse et al., 2007; Masegosa et al., 2020).

If $\mathbb{E}_{\rho}[L(h)]\leq\frac{1}{2}$, then

$L(\operatorname{MV}_{\rho})\leq\frac{\mathbb{E}_{\rho^{2}}[L(h,h^{\prime})]-\mathbb{E}_{\rho}[L(h)]^{2}}{\frac{1}{4}+\mathbb{E}_{\rho^{2}}[L(h,h^{\prime})]-\mathbb{E}_{\rho}[L(h)]}.$

Masegosa et al. have shown that the Chebyshev-Cantelli inequality is always at
least as tight as second order Markov’s inequality (below we provide an
alternative and more intuitive proof of this fact) and, therefore, the oracle
bound in Theorem 5 is always at least as tight as the oracle bound in Theorem
3. However, the presence of $\mathbb{E}_{\rho^{2}}[L(h,h^{\prime})]$ and
$\mathbb{E}_{\rho}[L(h)]$ in the denominator make empirical estimation and
optimization of the bound in Theorem 5 impractical, and Theorem 3 was the only
practically applicable second order bound so far.

##  4 Main Contributions

We present three main contributions: (1) a new form of the Chebyshev-Cantelli
inequality, which is convenient for optimization; (2) an application of the
inequality to the analysis of weighted majority vote; and (3) a PAC-Bayes-
Bennett inequality, which is used to bound the risk with an offset in the
bound for weighted majority vote. We start with the new form of Chebyshev-
Cantelli inequality, which can be seen as a refinement of second order
Markov’s inequality or as an intermediate step in the proof of the Chebyshev-
Cantelli inequality.

######  Theorem 6.

For any $\varepsilon>0$ and $\mu<\varepsilon$

$\mathbb{P}{\left(Z\geq\varepsilon\right)}\leq\frac{\mathbb{E}\left[(Z-\mu)^{2}\right]}{(\varepsilon-\mu)^{2}}.$

###### Proof.

$\mathbb{P}{\left(Z\geq\varepsilon\right)}=\mathbb{P}{\left(Z-\mu\geq\varepsilon-\mu\right)}\leq\mathbb{P}{\left((Z-\mu)^{2}\geq(\varepsilon-\mu)^{2}\right)}\leq\frac{\mathbb{E}\left[(Z-\mu)^{2}\right]}{(\varepsilon-\mu)^{2}}.\qed$

The inequality can also be written as

$\mathbb{P}{\left(Z\geq\varepsilon\right)}\leq\frac{\mathbb{E}\left[(Z-\mu)^{2}\right]}{(\varepsilon-\mu)^{2}}=\frac{\mathbb{E}\left[Z^{2}\right]-2\mu\mathbb{E}\left[Z\right]+\mu^{2}}{(\varepsilon-\mu)^{2}}.$
(1)

The bound is minimized by
$\mu^{*}=\mathbb{E}\left[Z\right]-\frac{\mathbb{V}\left[Z\right]}{\varepsilon-\mathbb{E}\left[Z\right]}$,
which can be verified by taking a derivative of the bound with respect to
$\mu$. Note that $\mu^{*}$ can take negative values. Substitution of $\mu^{*}$
into the bound and simple algebraic manipulations recover the Chebyshev-
Cantelli inequality, whereas $\mu=0$ recovers second order Markov’s
inequality. The main advantage of Theorem 6 over the Chebyshev-Cantelli
inequality is ease of estimation and optimization due to absence of the
variance term in the denominator.

Equation (1) leads to two new second order oracle bounds for the weighted
majority vote, given in Theorems 7 and 8.

######  Theorem 7.

In multiclass classification

$L(\operatorname{MV}_{\rho})\leq\frac{\mathbb{E}_{\rho^{2}}[L(h,h^{\prime})]-2\mu\mathbb{E}_{\rho}[L(h)]+\mu^{2}}{(0.5-\mu)^{2}}.$

###### Proof.

As in the previous section, we take
$Z=\mathbb{E}_{\rho}[\mathds{1}{\left(h(X)\neq Y\right)}]$, so that
$L(\operatorname{MV}_{\rho})\leq\mathbb{P}{}(Z\geq 0.5)$. The result follows
by (1) and the calculations of $\mathbb{E}\left[Z^{2}\right]$ and
$\mathbb{E}\left[Z\right]$ from the previous section. ∎

For $\mu=0$, Theorem 7 recovers Theorem 3, but if
$\mu^{*}=\mathbb{E}_{\rho}[L(h)]-\frac{\mathbb{E}_{\rho^{2}}[L(h,h^{\prime})]-\mathbb{E}\left[L(h)\right]^{2}}{0.5-\mathbb{E}_{\rho}[L(h)]}\neq
0$, then substitution of $\mu^{*}$ into the theorem yields a tighter oracle
bound. At the same time, substitution of $\mu^{*}$ recovers Theorem 5, but the
great advantage of Theorem 7 is that the bound allows easy empirical
estimation and optimization with respect to $\rho$, due to absence of
$\mathbb{E}_{\rho^{2}}[L(h,h^{\prime})]$ and $\mathbb{E}_{\rho}[L(h)]$ in the
denominator. Thus, Theorem 7 has the oracle tightness of Theorem 5 and the
ease of estimation and optimization of Theorem 3. The oracle quantities
$\mathbb{E}_{\rho^{2}}[L(h,h^{\prime})]$ and $\mathbb{E}_{\rho}[L(h)]$ can be
bounded using PAC-Bayes-kl or PAC-Bayes-$\lambda$ inequalities, as discussed
in the next section.

In order to present the second oracle bound we introduce a new quantity. For a
pair of hypotheses $h$ and $h^{\prime}$ and a constant $\mu$, we define
_tandem loss with $\mu$-offset_, for brevity _$\mu$ -tandem loss_, as

$\ell_{\mu}(h(X),h^{\prime}(X),Y)=(\mathds{1}{\left(h(X)\neq
Y\right)}-\mu)(\mathds{1}{\left(h^{\prime}(X)\neq Y\right)}-\mu).$ (2)

Note that it can take negative values. We denote its expectation by

$L_{\mu}(h,h^{\prime})=\mathbb{E}_{D}[\ell_{\mu}(h(X),h^{\prime}(X),Y)]=\mathbb{E}_{D}[(\mathds{1}{\left(h(X)\neq
Y\right)}-\mu)(\mathds{1}{\left(h^{\prime}(X)\neq Y\right)}-\mu)].$

With $Z=\mathbb{E}_{\rho}[\mathds{1}{\left(h(X)\neq Y\right)}]$ as before, we
have

$\displaystyle\mathbb{E}\left[(Z-\mu)^{2}\right]$
$\displaystyle=\mathbb{E}_{D}[(\mathbb{E}_{\rho}[(\mathds{1}{\left(h(X)\neq
Y\right)}-\mu)])^{2}]$
$\displaystyle=\mathbb{E}_{\rho^{2}}[\mathbb{E}_{D}[(\mathds{1}{\left(h(X)\neq
Y\right)}-\mu)(\mathds{1}{\left(h^{\prime}(X)\neq
Y\right)}-\mu)]]=\mathbb{E}_{\rho^{2}}[L_{\mu}(h,h^{\prime})].$

Now we present our second oracle bound.

######  Theorem 8.

In multiclass classification

$L(\operatorname{MV}_{\rho})\leq\frac{\mathbb{E}_{\rho^{2}}[L_{\mu}(h,h^{\prime})]}{(0.5-\mu)^{2}}.$

###### Proof.

The result follows by Theorem 6 and the calculation above. ∎

In order to discuss the advantage of Theorem 8, we define the variance of the
$\mu$-tandem loss

$\mathbb{V}_{\mu}(h,h^{\prime})=\mathbb{E}_{D}[\left((\mathds{1}{\left(h(X)\neq
Y\right)}-\mu)(\mathds{1}{\left(h^{\prime}(X)\neq
Y\right)}-\mu)-L_{\mu}(h,h^{\prime})\right)^{2}].$

If the variance of the $\mu$-tandem loss is small, we can use Bernstein-type
inequalities to obtain tighter estimates compared to kl-type inequalities.

We bound the $\mu$-tandem loss using our next contribution, the PAC-Bayes-
Bennett inequality, which improves on the PAC-Bayes-Bernstein inequality
derived by Seldin et al. (2012) and may be of independent interest. The
inequality holds for any loss function bounded from above, we use
$\tilde{\ell}$ and matching tilde-marked quantities to distinguish it from the
zero-one loss $\ell$. We let
$\tilde{L}(h)=\mathbb{E}_{D}[\tilde{\ell}(h(X),Y)]$ and
$\tilde{}\mathbb{V}(h)=\mathbb{E}_{D}[(\tilde{\ell}(h(X),Y)-\tilde{L}(h))^{2}]$
be the expected tilde-loss of $h$ and its variance and let
$\hat{\tilde{L}}(h,S)=\frac{1}{n}\sum_{i=1}^{n}\tilde{\ell}(h(X_{i}),Y_{i})$
be the empirical tilde-loss of $h$ on a sample $S$.

######  Theorem 9 (PAC-Bayes-Bennett inequality).

Let $\tilde{\ell}(\cdot,\cdot)$ be an arbitrary loss function bounded from
above by $b$ and assume that $\tilde{\mathbb{V}}(h)$ is finite for all $h$.
Let $\phi(x)=e^{x}-x-1$. Then for any distribution $\pi$ on $\mathcal{H}$ that
is independent of $S$ and any $\gamma>0$ and $\delta\in(0,1)$, with
probability at least $1-\delta$ over a random draw of $S$, for all
distributions $\rho$ on $\mathcal{H}$ simultaneously:

$\mathbb{E}_{\rho}[\tilde{L}(h)]\leq\mathbb{E}_{\rho}[\hat{\tilde{L}}(h,S)]+\frac{\phi(\gamma
b)}{\gamma
b^{2}}\mathbb{E}_{\rho}[\tilde{}\mathbb{V}(h)]+\frac{\operatorname{KL}(\rho\|\pi)+\ln\frac{1}{\delta}}{\gamma
n}.$

The proof is based on a change of measure argument combined with Bennett’s
inequality, the details are provided in Appendix A. Note that the result holds
for a fixed (but arbitrary) $\gamma$. In case of optimization with respect to
$\gamma$ a union bound has to be applied. For a fixed $\rho$ the bound is
convex in $\gamma$ and for a fixed $\gamma$ it is convex in $\rho$, although
it is not necessarily jointly convex in $\rho$ and $\gamma$. See Appendix D
for optimization details. The PAC-Bayes-Bennett inequality is identical to the
PAC-Bayes-Bernstein inequality by Seldin et al. (2012, Theorem 7), except that
in the latter the coefficient in front of
$\mathbb{E}_{\rho}[\tilde{}\mathbb{V}\left[h\right]]$ is $(e-2)\gamma$ instead
of $\frac{\phi(\gamma b)}{\gamma b^{2}}$. The result improves on the result by
Seldin et al. in three ways. First, it requires only one-sided instead of two-
sided boundedness of the loss. Second, in the result by Seldin et al. $\gamma$
is restricted to the $(0,1/b]$ interval, whereas in our result $\gamma$ is
unrestricted from above. And finally, we can rewrite the coefficient in front
of the variance as $\frac{\phi(\gamma b)}{\gamma b^{2}}=\frac{\phi(\gamma
b)}{\gamma^{2}b^{2}}\gamma$, and $\frac{\phi(\gamma b)}{\gamma^{2}b^{2}}$ is a
monotonically increasing function of $\gamma$, which in the interval
$\gamma\in(0,1/b]$ satisfies $\lim_{\gamma\to 0}\frac{\phi(\gamma
b)}{\gamma^{2}b^{2}}=\frac{1}{2}$ and for $\gamma=1/b$ gives
$\frac{\phi(\gamma b)}{\gamma^{2}b^{2}}=(e-2)$. Thus, PAC-Bayes-Bennett is
always at least as tight as PAC-Bayes-Bernstein and, at the same time, for
$\gamma<1/b$ it improves the constant coefficient in front of the variance
from $(e-2)\approx 0.72$ down to 0.5 for $\gamma\to 0$.

##  5 From oracle to empirical bounds

We obtain empirical bounds on the oracle quantities
$\mathbb{E}_{\rho^{2}}[L(h,h^{\prime})]$ and $\mathbb{E}_{\rho}[L(h)]$ in
Theorem 7 and $\mathbb{E}_{\rho^{2}}[L_{\mu}(h,h^{\prime})]$ in Theorem 8 by
using PAC-Bayesian inequalities. The empirical counterpart of the expected
tandem loss is the empirical tandem loss

$\hat{L}(h,h^{\prime},S)=\frac{1}{n}\sum_{i=1}^{n}\mathds{1}{\left(h(X_{i})\neq
Y_{i}\right)}\mathds{1}{\left(h^{\prime}(X_{i})\neq Y_{i}\right)}.$

For bounding $\mathbb{E}_{\rho^{2}}[L(h,h^{\prime})]$ and
$\mathbb{E}_{\rho}[L(h)]$ we use either PAC-Bayes-kl or PAC-Bayes-$\lambda$
inequalities, both cited below. We use $\operatorname{KL}(\rho\|\pi)$ to
denote the Kullback-Leibler divergence between distributions $\rho$ and $\pi$
on $\mathcal{H}$ and $\operatorname{kl}(p\|q)$ to denote the Kullback-Leibler
divergence between two Bernoulli distributions with biases $p$ and $q$.

######  Theorem 10 (PAC-Bayes-kl Inequality, Seeger, 2002).

For any probability distribution $\pi$ on ${\cal H}$ that is independent of
$S$ and any $\delta\in(0,1)$, with probability at least $1-\delta$ over a
random draw of a sample $S$, for all distributions $\rho$ on ${\cal H}$
simultaneously:

$\operatorname{kl}\left(\mathbb{E}_{\rho}[\hat{L}(h,S)]\middle\|\mathbb{E}_{\rho}\left[L(h)\right]\right)\leq\frac{\operatorname{KL}(\rho\|\pi)+\ln(2\sqrt{n}/\delta)}{n}.$
(3)

######  Theorem 11 (PAC-Bayes-$\lambda$ Inequality, Thiemann et al., 2017).

For any probability distribution $\pi$ on ${\cal H}$ that is independent of
$S$ and any $\delta\in(0,1)$, with probability at least $1-\delta$ over a
random draw of a sample $S$, for all distributions $\rho$ on ${\cal H}$ and
all $\lambda\in(0,2)$ and $\gamma>0$ simultaneously:

$\displaystyle\mathbb{E}_{\rho}\left[L(h)\right]$
$\displaystyle\leq\frac{\mathbb{E}_{\rho}[\hat{L}(h,S)]}{1-\frac{\lambda}{2}}+\frac{\operatorname{KL}(\rho\|\pi)+\ln(2\sqrt{n}/\delta)}{\lambda\left(1-\frac{\lambda}{2}\right)n},$
(4) $\displaystyle\mathbb{E}_{\rho}\left[L(h)\right]$
$\displaystyle\geq\left(1-\frac{\gamma}{2}\right)\mathbb{E}_{\rho}[\hat{L}(h,S)]-\frac{\operatorname{KL}(\rho\|\pi)+\ln(2\sqrt{n}/\delta)}{\gamma
n}.$ (5)

The PAC-Bayes-$\lambda$ inequality is an optimization-friendly relaxation of
the PAC-Bayes-kl inequality. Therefore, for optimization of $\rho$ we use the
PAC-Bayes-$\lambda$ inequality, the upper bound for
$\mathbb{E}_{\rho^{2}}[L(h,h^{\prime})]$ and the lower bound for
$\mathbb{E}_{\rho}[L(h)]$, but once we have converged to a solution we use
PAC-Bayes-kl to compute the final bound. The kl form provides both an upper
and a lower bound through the upper and lower inverse of the kl. We note that
$\operatorname{KL}(\rho^{2}\|\pi^{2})=2\operatorname{KL}(\rho\|\pi)$ (Germain
et al., 2015, Page 814). Taking the oracle bound from Theorem 7 and bounding
the oracle quantities using Theorem 11 we obtain the following result.

######  Theorem 12.

For any parameter grid $\\{\mu_{1},\dots,\mu_{k}\\}$, any distribution $\pi$
on $\mathcal{H}$ that is independent of $S$, and any $\delta\in(0,1)$, with
probability at least $1-\delta$ over a random draw of $S$, for all
distributions $\rho$ on $\mathcal{H}$, all $\lambda\in(0,2)$, all $\gamma>0$,
and all values of $\mu$ in the grid simultaneously:

$L(\operatorname{MV}_{\rho})\leq\frac{1}{(0.5-\mu)^{2}}\bigg{(}\frac{\mathbb{E}_{\rho^{2}}[\hat{L}(h,h^{\prime},S)]}{1-\frac{\lambda}{2}}+\frac{2\operatorname{KL}(\rho\|\pi)+\ln(4k\sqrt{n}/\delta)}{\lambda\left(1-\frac{\lambda}{2}\right)n}\\\
-2\mu\left(\left(1-\frac{\gamma}{2}\right)\mathbb{E}_{\rho}[\hat{L}(h,S)]-\frac{\operatorname{KL}(\rho\|\pi)+\ln(4k\sqrt{n}/\delta)}{\gamma
n}\right)+\mu^{2}\bigg{)}.$

###### Proof.

The result follows by substitution of the bounds on
$\mathbb{E}_{\rho^{2}}[L(h,h^{\prime})]$ and $\mathbb{E}_{\rho}[L(h)]$ by
Theorem 11 into Theorem 7. The $4k$ factor comes from a union bound over the
grid and the two empirical bounds. ∎

We note that both the loss and the tandem loss are Bernoulli random variables
and that Bernoulli random variables have the maximal variance given the range
and expectation. Therefore, PAC-Bayes-kl is tighter than PAC-Bayes-Bennett in
this case. However, the empirical counterpart of the expected $\mu$-tandem
loss is the empirical $\mu$-tandem loss

$\hat{L}_{\mu}(h,h^{\prime},S)=\frac{1}{n}\sum_{i=1}^{n}(\mathds{1}{\left(h(X_{i})\neq
Y_{i}\right)}-\mu)(\mathds{1}{\left(h^{\prime}(X_{i})\neq Y_{i}\right)}-\mu),$

and the $\mu$-tandem losses are not Bernoulli. Therefore, we use the PAC-
Bayes-Bennett inequality, which provides an advantage if the variance of the
$\mu$-tandem losses happens to be small. The expected and empirical variance
of the $\mu$-tandem losses of a pair of hypotheses $h$ and $h^{\prime}$ are,
respectively, defined by

$\displaystyle\mathbb{V}_{\mu}(h,h^{\prime})$
$\displaystyle=\mathbb{E}_{D}[\left((\mathds{1}{\left(h(X)\neq
Y\right)}-\mu)(\mathds{1}{\left(h^{\prime}(X)\neq
Y\right)}-\mu)-L_{\mu}(h,h^{\prime})\right)^{2}],$
$\displaystyle\hat{}\mathbb{V}_{\mu}(h,h^{\prime},S)$
$\displaystyle=\frac{1}{n-1}\sum_{i=1}^{n}\left((\mathds{1}{\left(h(X_{i})\neq
Y_{i}\right)}-\mu)(\mathds{1}{\left(h^{\prime}(X_{i})\neq
Y_{i}\right)}-\mu)-\hat{L}_{\mu}(h,h^{\prime},S)\right)^{2}.$

The empirical variance $\hat{}\mathbb{V}_{\mu}(h,h^{\prime},S)$ is an unbiased
estimate of $\mathbb{V}_{\mu}(h,h^{\prime})$.

Since the PAC-Bayes-Bennett inequality is stated in terms of the oracle
variance $\mathbb{E}_{\rho}[\tilde{\mathbb{V}}(h)]$, we use the result by
Tolstikhin and Seldin (2013, Equation (15)) to bound it in terms of the
empirical variance. For a general loss function $\tilde{\ell}(\cdot,\cdot)$
(not necessarily within $[0,1]$), we define the empirical variance of the loss
of $h$ by
$\hat{\tilde{\mathbb{V}}}(h,S)=\frac{1}{n-1}\sum_{i=1}^{n}(\tilde{\ell}(h(X_{i}),Y_{i})-\tilde{L}(h))^{2}$.
We recall that $\tilde{L}$, $\tilde{\mathbb{V}}$, and $\hat{\tilde{L}}$ were
defined above Theorem 9. We note that the result of Tolstikhin and Seldin
assumes that the losses are bounded in the $[0,1]$ interval. Rescaling to a
general range introduces the squared range factor $c^{2}$ in front of the last
term in the inequality, since scaling a random variable by $c$ scales the
variance by $c^{2}$.

######  Theorem 13 (Tolstikhin and Seldin, 2013).

Let $\tilde{\ell}(\cdot,\cdot)$ be an arbitrary loss function with range $c$.
Then for any distribution $\pi$ on $\mathcal{H}$ that is independent of $S$,
any $\lambda\in\left(0,\frac{2(n-1)}{n}\right)$, and any $\delta\in(0,1)$,
with probability at least $1-\delta$ over a random draw of the sample $S$, for
all distributions $\rho$ on $\mathcal{H}$ simultaneously:

$\mathbb{E}_{\rho}[\tilde{\mathbb{V}}(h)]\leq\frac{\mathbb{E}_{\rho}[\hat{\tilde{\mathbb{V}}}(h)]}{1-\frac{\lambda
n}{2(n-1)}}+\frac{c^{2}\left(\operatorname{KL}(\rho\|\pi)+\ln\frac{1}{\delta}\right)}{n\lambda\left(1-\frac{\lambda
n}{2(n-1)}\right)}.$

We note that, similar to the PAC-Bayes-Bennett inequality, but in contrast to
the PAC-Bayes-kl and PAC-Bayes-$\lambda$ inequalities, the inequality above
holds for a fixed value of $\lambda$ and in case of optimization over
$\lambda$ a union bound has to be applied.

The last thing that is left is to bound the value and range of $\mu$-tandem
losses defined in equation (2).

######  Lemma 14.

For $\mu<0.5$ the range of the $\mu$-tandem loss
$\ell_{\mu}(\cdot,\cdot,\cdot)$ is $K_{\mu}=\max\\{1-\mu,1-2\mu\\}$ and it is
upper bounded $\ell_{\mu}(\cdot,\cdot,\cdot)\leq(1-\mu)^{2}$.

A proof is provided in Appendix B. Taking together the results of Theorems 8,
9, 13, and Lemma 14 we obtain the following result.

######  Theorem 15.

For any parameter grid $\\{\mu_{1},\dots,\mu_{k_{\mu}}\\}$,
$\\{\gamma_{1},\dots,\gamma_{k_{\gamma}}\\}$, and
$\\{\lambda_{1},\dots,\lambda_{k_{\lambda}}\\}$ any distribution $\pi$ on
$\mathcal{H}$ that is independent of $S$, and any $\delta\in(0,1)$, with
probability at least $1-\delta$ over a random draw of $S$, for all
distributions $\rho$ on $\mathcal{H}$, and all values of $\mu$, $\gamma$, and
$\lambda$ in the corresponding grids simultaneously:

$L(\operatorname{MV}_{\rho})\leq\frac{1}{(0.5-\mu)^{2}}\Bigg{(}\mathbb{E}_{\rho^{2}}[\hat{L}_{\mu}(h,h^{\prime},S)]+\frac{2\operatorname{KL}(\rho\|\pi)+\ln\frac{2k_{\mu}k_{\gamma}k_{\lambda}}{\delta}}{\gamma
n}\\\
+\frac{\phi(\gamma(1-\mu)^{2})}{\gamma(1-\mu)^{4}}\left(\frac{\mathbb{E}_{\rho^{2}}[\hat{\mathbb{V}}_{\mu}(h,h^{\prime},S)]}{1-\frac{\lambda
n}{2(n-1)}}+\frac{K_{\mu}^{2}\left(2\operatorname{KL}(\rho\|\pi)+\ln\frac{2k_{\mu}k_{\gamma}k_{\lambda}}{\delta}\right)}{n\lambda\left(1-\frac{\lambda
n}{2(n-1)}\right)}\right)\Bigg{)}.$

###### Proof.

The result follows by reverse substitution of the result of Lemma 14 into
Theorem 13, then into Theorem 9, and finally into Theorem 8. The factor
$2k_{\mu}k_{\gamma}k_{\lambda}$ comes from a union bound over the parameter
grid and the bounds in Theorems 9 and 13. ∎

Figure 1: Theorem 7 vs. Theorem 3

##  6 Experiments

We start with a simulated comparison of the oracle bounds and then present an
empirical evaluation on real data.

#### Comparison of the oracle bounds

Figure 1 depicts a comparison of the second order oracle bound based on the
Chebyshev-Cantelli inequality (Theorems 5, 7 and 8, which, as oracle bounds,
are equivalent) and the second order oracle bound based on the second order
Markov’s inequality (Theorem 3). We plot the ratio of the right hand side of
the bound in Theorem 7 for the optimal value
$\mu^{*}=\mathbb{E}_{\rho}[L(h)]-\frac{\mathbb{E}_{\rho^{2}}[L(h,h^{\prime})]-\mathbb{E}_{\rho}[L(h)]^{2}}{0.5-\mathbb{E}_{\rho}[L(h)]}$
to the value of the right hand side of the bound in Theorem 3. A simple
calculation shows that if
$\mathbb{E}_{\rho^{2}}[L(h,h^{\prime})]=0.5\mathbb{E}_{\rho}[L(h)]$, then
$\mu^{*}=0$, which recovers the bound in Theorem 3. The line
$\mathbb{E}_{\rho^{2}}[L(h,h^{\prime})]=0.5\mathbb{E}_{\rho}[L(h)]$ is shown
in black in Figure 1. We also note that
$\mathbb{E}_{\rho}[L(h)]^{2}\leq\mathbb{E}_{\rho^{2}}[L(h,h^{\prime})]\leq\mathbb{E}_{\rho}[L(h)]$,
which defines the feasible region in Figure 1. Whenever
$\mathbb{E}_{\rho^{2}}[L(h,h^{\prime})]\neq 0.5\mathbb{E}_{\rho}[L(h)]$ the
Chebyshev-Cantelli inequality provides an improvement over second order
Markov’s inequality. The region above the black line, where
$\mathbb{E}_{\rho^{2}}[L(h,h^{\prime})]>0.5\mathbb{E}_{\rho}[L(h)]$, is the
region of high correlation of errors and in this case majority vote yields
little improvement over individual classifiers. In this region the first order
oracle bound is tighter than the second order oracle bounds (see Appendix C).
The region below the black line, where
$\mathbb{E}_{\rho^{2}}[L(h,h^{\prime})]<0.5\mathbb{E}_{\rho}[L(h)]$, is the
region of low correlation of errors. In this region the second order oracle
bounds are tighter than the first order oracle bound. Note that the potential
for improvement below the black line is much higher than above it.

#### Empirical evaluation on real datasets

We studied the empirical performance of the bounds using standard random
forest (Breiman, 2001) and a combination of heterogeneous classifiers on a
subset of data sets from UCI and LibSVM repositories (Dua and Graff, 2019;
Chang and Lin, 2011). An overview of the data sets is given in Appendix E.1.
The number of points varied from 3000 to 70000 with dimensions $d<1000$. For
each data set, we set aside 20% of the data for the test set
$\operatorname{S_{test}}$ and used the remaining data $S$ for ensemble
construction, weight optimization and bound evaluation. We evaluate the
classifiers and bounds obtained by minimizing the tandem bound
$\operatorname{TND}$ (Masegosa et al., 2020, Theorem 9), which is the
empirical bound on the oracle tandem bound in Theorem 3, the $\mu$-tandem
bound $\operatorname{C\mu TND}$ (Theorem 12), and the tandem bound with an
offset $\operatorname{COTND}$ (Theorem 15). We made 5 repetitions of each
experiment.

##### Ensemble construction and minimization of the bounds.

We follow the construction used by Masegosa et al. (2020). The idea is to
generate multiple random splits of the data set $S$ into pairs of subsets
$S=T_{h}\cup S_{h}$, such that $T_{h}\cap S_{h}=\emptyset$. Each hypothesis is
trained on $T_{h}$ and the empirical loss on $S_{h}$ provides an unbiased
estimate of its expected loss. Note that the splits cannot depend on the data.
For our experiments, we generate these splits by bagging, where out-of-bag
(OOB) samples $S_{h}$ provide unbiased estimates of expected losses of
individual hypotheses $h$. The resulting set of hypotheses produces an
ensemble. As in the work of Masegosa et al., two modifications are required to
apply the bounds: the empirical losses $\hat{L}(h,S)$ in the bounds are
replaced by the validation losses $\hat{L}(h,S_{h})$, and the sample size $n$
is replaced by the minimal validation size $\min_{h}|S_{h}|$. For pairs of
hypotheses $(h,h^{\prime})$, we take the overlaps of their validation sets
$S_{h}\cap S_{h^{\prime}}$ to calculate an unbiased estimate of their tandem
loss $\hat{L}(h,h^{\prime},S_{h}\cap S_{h^{\prime}})$, $\mu$-tandem loss
$\hat{L}_{\mu}(h,h^{\prime},S_{h}\cap S_{h^{\prime}})$, and the variance of
the $\mu$-tandem loss $\hat{}\mathbb{V}_{\mu}(h,h^{\prime},S_{h}\cap
S_{h^{\prime}})$, which replaces the corresponding empirical losses in the
bounds. The sample size is then replaced by $\min_{h,h^{\prime}}|S_{h}\cap
S_{h^{\prime}}|$. The details on bound minimization are provided in Appendix
D.

##### Optimizing weighted random forest.

In the first experiment we compare $\operatorname{TND}$, $\operatorname{C\mu
TND}$, and $\operatorname{COTND}$ bounds in the setting studied by Masegosa et
al. (2020). We take 100 fully grown trees, use the Gini criterion for
splitting, and consider $\sqrt{d}$ features in each split. Figure 2(a)
compares the loss of the random forest on $\operatorname{S_{test}}$ using
either uniform weighting $\rho_{u}$ or optimized weighting $\rho^{*}$ found by
minimization of the three bounds (we exclude the first order bound from the
comparison, since it was shown by Masegosa et al. that it significantly
deteriorates the test error of the ensemble). While $\operatorname{C\mu TND}$
often performs similar or slightly worse than $\operatorname{TND}$, we find
that optimizing using $\operatorname{COTND}$ rarely degrades, but often
improves accuracy. Figure 2(b) compares the tightness of the optimized
$\operatorname{C\mu TND}$ and $\operatorname{COTND}$ bounds to the optimized
$\operatorname{TND}$ bound. The $\operatorname{C\mu TND}$ is generally
comparable to $\operatorname{TND}$, while $\operatorname{COTND}$ is
consistently looser than $\operatorname{TND}$, mainly due to the union bounds.
Numerical values for loss and bounds can be found in Tables 2 and 3 in
Appendix E.2.

(a)

(b)

(c)

(d)

Figure 2:  (a,b) Optimized weighted random forest. (c,d) Ensembles with
heterogeneous classifiers. The median, 25%, and 75% quantiles of: (a,c) the
ratio
$\hat{L}(\operatorname{MV}_{\rho^{*}},\operatorname{S_{test}})/\hat{L}(\operatorname{MV}_{u},\operatorname{S_{test}})$
of the test loss of the majority vote with optimized weighting $\rho^{*}$
generated by $\operatorname{TND}$, $\operatorname{C\mu TND}$ and
$\operatorname{COTND}$ to the test loss of majority vote with uniform
weighting, and (b,d) the ratio
$\operatorname{BOUND}(\rho^{\star})/\operatorname{TND}(\rho^{\star}_{\scriptscriptstyle{\operatorname{TND}}})$
of the $\operatorname{C\mu TND}$ and $\operatorname{COTND}$ bounds to the
$\operatorname{TND}$ bound with the corresponding optimized weighting . The
plots are on a logarithmic scale. Values above 1 represent degradation and
values below 1 represent improvement. Data sets with
$L(\operatorname{MV}_{u},\operatorname{S_{test}})=0$ are left out in (a,c).

##### Ensembles with heterogeneous classifiers.

In the second experiment, we consider ensembles of heterogeneous classifiers
(Linear Discriminant Analysis, $k$-Nearest Neighbors, Decision Tree, Logistic
Regression, and Gaussian Naive Bayes). A detailed description is provided in
Appendix E.3. Compared to random forests, the variation in performance of
ensemble members is larger here.

Figure 2(c) compares the ratio of the loss of the majority vote with optimized
weighting to the loss of majority vote with uniform weighting on
$\operatorname{S_{test}}$ for $\rho^{*}$ found by minimization of the first
order bound ($\operatorname{FO}$), $\operatorname{TND}$, $\operatorname{C\mu
TND}$, and $\operatorname{COTND}$. The numerical values are given in Table 4
in the supplementary material. We observed that optimizing the
$\operatorname{FO}$ tends to improve the ensemble accuracy in some cases but
degrade in others. However, $\operatorname{TND}$, $\operatorname{C\mu TND}$,
and $\operatorname{COTND}$ almost always improve the performance w.r.t. the
uniform weighting. Table 4 also shows that choosing the best single hypothesis
gives almost identical results as optimizing $\operatorname{FO}$. Figure 2(d)
compares the tightness of the $\operatorname{C\mu TND}$ and
$\operatorname{COTND}$ bounds relative to the $\operatorname{TND}$ bound. The
numerical values are given in Table 5 in the supplementary material. In this
case, we have that $\operatorname{C\mu TND}$ is usually tighter than
$\operatorname{TND}$, while $\operatorname{COTND}$ is usually looser than
$\operatorname{TND}$.

##  7 Discussion

We derived an optimization-friendly form of the Chebyshev-Cantelli inequality
and applied it to derive two new forms of second order oracle bounds for the
weighted majority vote. The new oracle bounds bridge between the C-bounds
(Germain et al., 2015) and the tandem bound (Masegosa et al., 2020) and take
the best of both: the tightness of the Chebyshev-Cantelli inequality and the
optimization and estimation convenience of the tandem bound. We also derived
the PAC-Bayes-Bennett inequality, improving on the PAC-Bayes-Bernstein
inequality by Seldin et al. (2012).

Our paper opens several directions for future research. One of them is a
better treatment of parameter search in parametric bounds that would be
tighter than a union bound over a grid. It would also be interesting to find
other applications for the new form of Chebyshev-Cantelli inequality and the
PAC-Bayes-Bennett inequality.

## Acknowledgments and Disclosure of Funding

This project has received funding from European Union’s Horizon 2020 research
and innovation programme under the Marie Skłodowska-Curie grant agreement No
801199. YW and YS acknowledge support by the Independent Research Fund
Denmark, grant number 0135-00259B. SSL acknowledges funding by the Danish
Ministry of Education and Science, Digital Pilot Hub and Skylab Digital. CI
acknowledges support by the Villum Foundation through the project Deep
Learning and Remote Sensing for Unlocking Global Ecosystem Resource Dynamics
(DeReEco). AM is funded by the Spanish Ministry of Science, Innovation and
Universities and by the regional government of Andalucía, grant numbers
PID2019-106758GB-C32 and P20-00091, respectively.

## References

  * Berend and Kontorovich (2016) Daniel Berend and Aryeh Kontorovich.  A finite sample analysis of the naive Bayes classifier.  _Journal of Machine Learning Research_ , 2016.
  * Boucheron et al. (2013) Stéphane Boucheron, Gábor Lugosi, and Pascal Massart.  _Concentration Inequalities A Nonasymptotic Theory of Independence_.  Oxford University Press, 2013.
  * Breiman (1996) Leo Breiman.  Bagging predictors.  _Machine learning_ , 24(2), 1996.
  * Breiman (2001) Leo Breiman.  Random forests.  _Machine learning_ , 45(1), 2001.
  * Chang and Lin (2011) Chih-Chung Chang and Chih-Jen Lin.  LIBSVM: A library for support vector machines.  _ACM Transactions on Intelligent Systems and Technology_ , 2, 2011\.
  * Chen and Guestrin (2016) Tianqi Chen and Carlos Guestrin.  XGBoost: A scalable tree boosting system.  In _Proceedings of the International Conference on Knowledge Discovery and Data Mining (ACM SIGKDD)_ , pages 785–794, 2016.
  * Corless et al. (1996) Robert M Corless, Gaston H Gonnet, David EG Hare, David J Jeffrey, and Donald E Knuth.  On the lambertw function.  _Advances in Computational mathematics_ , 5(1), 1996.
  * Dua and Graff (2019) Dheeru Dua and Casey Graff.  UCI machine learning repository, 2019.  URL http://archive.ics.uci.edu/ml.
  * Florescu and Igel (2018) Ciprian Florescu and Christian Igel.  Resilient backpropagation (rprop) for batch-learning in tensorflow.  In _International Conference on Learning Representations (ICLR) Workshop_ , 2018.
  * Freund and Schapire (1996) Yoav Freund and Robert E. Schapire.  Experiments with a new boosting algorithm.  In _Proceedings of the International Conference on Machine Learning (ICML)_ , 1996.
  * Friedman (1999) Jerome H. Friedman.  Stochastic gradient boosting.  _Computational Statistics and Data Analysis_ , 38, 1999.
  * Friedman (2001) Jerome H Friedman.  Greedy function approximation: a gradient boosting machine.  _Annals of Statistics_ , pages 1189–1232, 2001.
  * Germain et al. (2009) Pascal Germain, Alexandre Lacasse, François Laviolette, and Mario Marchand.  PAC-Bayesian learning of linear classifiers.  In _Proceedings of the International Conference on Machine Learning (ICML)_ , 2009.
  * Germain et al. (2015) Pascal Germain, Alexandre Lacasse, François Laviolette, Mario Marchand, and Jean-Francis Roy.  Risk bounds for the majority vote: From a PAC-Bayesian analysis to a learning algorithm.  _Journal of Machine Learning Research_ , 16, 2015.
  * Igel and Hüsken (2003) Christian Igel and Michael Hüsken.  Empirical evaluation of the improved rprop learning algorithms.  _Neurocomputing_ , 50, 2003.
  * Lacasse et al. (2007) Alexandre Lacasse, François Laviolette, Mario Marchand, Pascal Germain, and Nicolas Usunier.  PAC-Bayes bounds for the risk of the majority vote and the variance of the Gibbs classifier.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2007.
  * Langford and Shawe-Taylor (2002) John Langford and John Shawe-Taylor.  PAC-Bayes & margins.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2002.
  * Laviolette et al. (2011) François Laviolette, Mario Marchand, and Jean-Francis Roy.  From PAC-Bayes bounds to quadratic programs for majority votes.  In _Proceedings of the International Conference on Machine Learning (ICML)_ , 2011.
  * Laviolette et al. (2017) François Laviolette, Emilie Morvant, Liva Ralaivola, and Jean-Francis Roy.  Risk upper bounds for general ensemble methods with an application to multiclass classification.  _Neurocomputing_ , 219, 2017.
  * Lorenzen et al. (2019) Stephan Sloth Lorenzen, Christian Igel, and Yevgeny Seldin.  On PAC-Bayesian bounds for random forests.  _Machine Learning_ , 2019.
  * Masegosa et al. (2020) Andrés R. Masegosa, Stephan S. Lorenzen, Christian Igel, and Yevgeny Seldin.  Second order PAC-Bayesian bounds for the weighted majority vote.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2020.
  * Mason et al. (1999) Llew Mason, Jonathan Baxter, Peter Bartlett, and Marcus Frean.  Boosting algorithms as gradient descent.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 1999.
  * McAllester (1998) David McAllester.  Some PAC-Bayesian theorems.  In _Proceedings of the Conference on Learning Theory (COLT)_ , 1998\.
  * Seeger (2002) Matthias Seeger.  PAC-Bayesian generalization error bounds for Gaussian process classification.  _Journal of Machine Learning Research_ , 3, 2002.
  * Seldin et al. (2012) Yevgeny Seldin, François Laviolette, Nicolò Cesa-Bianchi, John Shawe-Taylor, and Peter Auer.  PAC-Bayesian inequalities for martingales.  _IEEE Transactions on Information Theory_ , 58, 2012.
  * Thiemann et al. (2016) Niklas Thiemann, Christian Igel, and Yevgeny Seldin.  PAC-Bayesian aggregation without cross-validation.  http://arxiv.org/abs/1608.05610, 2016.
  * Thiemann et al. (2017) Niklas Thiemann, Christian Igel, Olivier Wintenberger, and Yevgeny Seldin.  A strongly quasiconvex PAC-Bayesian bound.  In _Proceedings of the International Conference on Algorithmic Learning Theory (ALT)_ , 2017.
  * Tolstikhin and Seldin (2013) Ilya Tolstikhin and Yevgeny Seldin.  PAC-Bayes-Empirical-Bernstein inequality.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2013.

##  Appendix A A proof of the PAC-Bayes-Bennett inequality (Theorem 9) and a
comparison with the PAC-Bayes-Bernstein inequality

In this section we provide a proof of Theorem 9 and a numerical comparison
with the PAC-Bayes-Bernstein inequality. The proof is based on the standard
change of measure argument. We use the following version by Tolstikhin and
Seldin [2013].

######  Lemma 16 (PAC-Bayes Lemma).

For any function $f_{n}:\mathcal{H}\times({\cal X}\times{\cal
Y})^{n}\to\mathbb{R}$ and for any distribution $\pi$ on $\mathcal{H}$, such
that $\pi$ is independent of $S$, with probability at least $1-\delta$ over a
random draw of $S$, for all distributions $\rho$ on $\mathcal{H}$
simultaneously:

$\mathbb{E}_{\rho}[f_{n}(h,S)]\leq\operatorname{KL}(\rho\|\pi)+\ln\frac{1}{\delta}+\ln\mathbb{E}_{\pi}[\mathbb{E}_{S^{\prime}}[e^{f_{n}(h,S^{\prime})}]].$

The second ingredient is Bennett’s lemma, which is a bound on the moment
generating function used in the proof of Bennett’s inequality. Since we are
unaware of a reference, we provide a proof below, which is essentially an
intermediate step in the proof of Bennett’s inequality [Boucheron et al.,
2013, Theorem 2.9].

######  Lemma 17 (Bennett’s Lemma).

Let $b>0$ and let $Z_{1},\dots,Z_{n}$ be i.i.d.  _zero-mean_ random variables
with finite variance, such that $Z_{i}\leq b$ for all $i$. Let
$M_{n}=\sum_{i=1}^{n}Z_{i}$ and
$V_{n}=\sum_{i=1}^{n}\mathbb{E}\left[Z_{i}^{2}\right]$. Let
$\phi(u)=e^{u}-u-1$. Then for any $\lambda>0$:

$\mathbb{E}\left[e^{\lambda
M_{n}-\frac{\phi(b\lambda)}{b^{2}}V_{n}}\right]\leq 1.$

###### Proof.

Since $u^{-2}\phi(u)$ is a non-decreasing function of $u\in\mathbb{R}$ (where
at zero we continuously extend the function), for all $i\in[n]$ and
$\lambda>0$ we have

$e^{\lambda Z_{i}}-\lambda Z_{i}-1\leq Z_{i}^{2}\frac{\phi(b\lambda)}{b^{2}},$

which implies

$\mathbb{E}\left[e^{\lambda Z_{i}}\right]\leq
1+\lambda\mathbb{E}\left[Z_{i}\right]+\frac{\phi(b\lambda)}{b^{2}}\mathbb{E}\left[Z_{i}^{2}\right]\leq
e^{\frac{\phi(b\lambda)}{b^{2}}\mathbb{E}\left[Z_{i}^{2}\right]},$

where the second inequality uses the assumption that
$\mathbb{E}\left[Z_{i}\right]=0$ and the fact that $1+x\leq e^{x}$ for all
$x\in\mathbb{R}$. By the above inequality and independence of the random
variables,

$\displaystyle\mathbb{E}\left[e^{\lambda
M_{n}-\frac{\phi(b\lambda)}{b^{2}}V_{n}}\right]$
$\displaystyle=\mathbb{E}\left[\prod_{i=1}^{n}e^{\lambda
Z_{i}-\frac{\phi(b\lambda)}{b^{2}}\mathbb{E}\left[Z_{i}^{2}\right]}\right]=\prod_{i=1}^{n}\mathbb{E}\left[e^{\lambda
Z_{i}-\frac{\phi(b\lambda)}{b^{2}}\mathbb{E}\left[Z_{i}^{2}\right]}\right]\leq
1.$

∎

Now we are ready to prove the theorem.

###### Proof of Theorem 9.

We take $f_{n}(h,S)=\gamma
n\left(\tilde{L}(h)-\tilde{\hat{L}}(h,S)\right)-\frac{\phi(\gamma
b)}{b^{2}}n\tilde{\mathbb{V}}(h)$. Then by Lemma 17 we have
$\mathbb{E}_{S}[e^{f_{n}(h,S)}]\leq 1$. By plugging this into Lemma 16,
normalizing by $\gamma n$, and changing sides, we obtain the result. ∎

#### Numerical comparison of the PAC-Bayes-Bennett and PAC-Bayes-Bernstein
bound

Figure 3 provides a numerical comparison of the PAC-Bayes-Bennett and PAC-
Bayes-Bernstein inequalities (Theorem 9 and Theorem 7 by Tolstikhin and Seldin
[2013]).

(a) $n=1000$

(b) $n=10000$

Figure 3: The ratio of PAC-Bayes Bennett to PAC-Bayes Bernstein bound as a
function of $\mathbb{E}_{\rho}[\hat{\tilde{L}}(h,S)]$ and
$\mathbb{E}_{\rho}[\tilde{\mathbb{V}}(h)]$. We set
$\operatorname{KL}(\rho\|\pi)=5$ and $\delta=0.05$. The value of $n$ is
provided in the captions of the subfigures.

##  Appendix B Proof of Lemma 14

###### Proof.

Recall that

$\ell_{\mu}(h(X),h^{\prime}(X),Y)=(\mathds{1}{\left(h(X)\neq
Y\right)}-\mu)(\mathds{1}{\left(h^{\prime}(X)\neq
Y\right)}-\mu)\in\left\\{(1-\mu)^{2},-\mu(1-\mu),\mu^{2}\right\\}.$

For $\mu<0.5$, we have $-\mu(1-\mu)<(1-\mu)^{2}$ and $\mu^{2}<(1-\mu)^{2}$.
Therefore, $\ell_{\mu}(h(X),h^{\prime}(X),Y)\leq(1-\mu)^{2}$.

Furthermore, for $\mu<0$ we have $\mu^{2}<-\mu(1-\mu)$, and for $\mu>0$ we
have $-\mu(1-\mu)\leq\mu^{2}$. Therefore, for $\mu<0.5$ we have
$\ell_{\mu}(h(X),h^{\prime}(X),Y)\geq\min\\{-\mu(1-\mu),\mu^{2}\\}$.

By combining the upper and the lower bound, we obtain

$\displaystyle K_{\mu}$
$\displaystyle=(1-\mu)^{2}-\min\\{-\mu(1-\mu),\mu^{2}\\}$
$\displaystyle=\max\\{(1-\mu)^{2}-(-\mu(1-\mu)),(1-\mu)^{2}-\mu^{2}\\}$
$\displaystyle=\max\\{1-\mu,1-2\mu\\}.$

∎

##  Appendix C Comparison of the first and second order oracle bounds

In this section we show that if $\mathbb{E}_{\rho}[L(h)]<0.5$ and
$\mathbb{E}_{\rho^{2}}[L(h,h^{\prime})]>0.5\mathbb{E}_{\rho}[L(h)]$, then the
first order oracle bound is tighter than the second order oracle bounds, and
if $\mathbb{E}_{\rho}[L(h)]<0.5$ and
$\mathbb{E}_{\rho^{2}}[L(h,h^{\prime})]<0.5\mathbb{E}_{\rho}[L(h)]$, then it
is the other way around.

For comparison of the first order oracle bound
$L(\operatorname{MV}_{\rho})\leq 2\mathbb{E}_{\rho}[L(h)]$ vs. the second
order oracle tandem bound $L(\operatorname{MV}_{\rho})\leq
4\mathbb{E}_{\rho^{2}}[L(h,h^{\prime})]$ the statement above is evident.

For the second order oracle bounds based on the Chebyshev-Cantelli inequality
we have

$\displaystyle\frac{\mathbb{E}_{\rho^{2}}[L(h,h^{\prime})]-\mathbb{E}_{\rho}[L(h)]^{2}}{0.25+\mathbb{E}_{\rho^{2}}[L(h,h^{\prime})]-\mathbb{E}_{\rho}[L(h)]}~{}~{}~{}~{}~{}$
$\displaystyle\text{vs.}~{}~{}~{}~{}~{}2\mathbb{E}_{\rho}[L(h)],$
$\displaystyle\mathbb{E}_{\rho^{2}}[L(h,h^{\prime})]-\mathbb{E}_{\rho}[L(h)]^{2}~{}~{}~{}~{}~{}$
$\displaystyle\text{vs.}~{}~{}~{}~{}~{}0.5\mathbb{E}_{\rho}[L(h)]+2\mathbb{E}_{\rho}[L(h)]\mathbb{E}_{\rho^{2}}[L(h,h^{\prime})]-2\mathbb{E}_{\rho}[L(h)]^{2},$
$\displaystyle\mathbb{E}_{\rho^{2}}[L(h,h^{\prime})](1-2\mathbb{E}_{\rho}[L(h)])~{}~{}~{}~{}~{}$
$\displaystyle\text{vs.}~{}~{}~{}~{}~{}0.5\mathbb{E}_{\rho}[L(h)](1-2\mathbb{E}_{\rho}[L(h)]),$
$\displaystyle\mathbb{E}_{\rho^{2}}[L(h,h^{\prime})]~{}~{}~{}~{}~{}$
$\displaystyle\text{vs.}~{}~{}~{}~{}~{}0.5\mathbb{E}_{\rho}[L(h)],$

where under the assumption that $\mathbb{E}_{\rho}[L(h)]<0.5$ we can cancel
$(1-2\mathbb{E}_{\rho}[L(h)])$, since it is positive, and the result is again
evident.

##  Appendix D Minimization of the bounds

In this section we provide technical details on minimization of the bounds in
Theorems 12 and 15.

###  D.1 Parameter grid construction

We start with the details on construction of the grid of $\mu$ and, in the
case of Theorem 15, $\lambda$ and $\gamma$.

####  D.1.1 The $\mu$ grid for Theorems 12 and 15

First, we consider the relevant range of $\mu$. By Theorem 6, we have
$\mu<0.5$. At the same time,
$\mu^{*}=\frac{0.5\mathbb{E}_{\rho}[L(h)]-\mathbb{E}_{\rho^{2}}[L(h,h)]}{0.5-\mathbb{E}_{\rho}[L(h)]}$,
and in Section 6 we have shown that the primary region of interest is where
$\mathbb{E}_{\rho^{2}}[L(h,h^{\prime})]<0.5\mathbb{E}_{\rho}[L(h)]$, which
corresponds to $\mu^{*}>0$. However, since $\mathbb{E}_{\rho^{2}}[L(h,h)]$ and
$\mathbb{E}_{\rho}[L(h)]$ are unobserved and we use an upper bound for the
first and a lower bound for the second instead, we take a broader range of
$\mu$. By making a mild assumption that the upper bound for the tandem loss
$\mathbb{E}_{\rho^{2}}[L(h,h^{\prime})]$ is at most 0.25 and the lower bound
for the Gibbs loss $\mathbb{E}_{\rho}[L(h)]$ is at most 0.5, we have
$\mu\in[-0.5,0.5)$. We take 200 uniformly spaced points in the selected range
for both the C$\mu$TND bound and the COTND bound.

####  D.1.2 The $\lambda$ grid for Theorem 15

The parameter $\lambda$ comes from Theorem 13. The theorem is identical to the
result by Tolstikhin and Seldin [2013, Equation (15)], except rescaling, but
rescaling happens on top of the bound and has no effect on the $\lambda$-grid.
Therefore, we use the grid proposed by Tolstikhin and Seldin. Namely, we take

$\lambda_{i}=c_{1}^{i-1}\frac{2(n-1)}{n}\left(\sqrt{\frac{n-1}{\ln(1/\delta_{1})}+1}+1\right)^{-1}$

for $i\in\\{1,\dots,k_{\lambda}\\}$ and

$k_{\lambda}=\left\lceil\frac{1}{\ln
c_{1}}\ln\left(\frac{1}{2}\sqrt{\frac{n-1}{\ln(1/\delta_{1})}+1}+\frac{1}{2}\right)\right\rceil.$

In the experiments we took $c_{1}=1.05$ and $\delta_{1}=\delta/(2k_{\mu})$.

####  D.1.3 The $\gamma$ grid for Theorem 15

The parameter $\gamma$ comes from Theorem 9. By taking the first two
derivatives we can verify that for a fixed $\rho$ the PAC-Bayes-Bennett bound
is convex in $\gamma$ and at the minimum point the optimal value of $\gamma$
satisfies

$e^{(\gamma_{\rho}^{*}b-1)}\left(\gamma_{\rho}^{*}b-1\right)=\frac{1}{e}\left(\frac{b^{2}\left(\operatorname{KL}(\rho\|\pi)+\ln\frac{1}{\delta_{2}}\right)}{n\mathbb{E}_{\rho}[\tilde{\mathbb{V}}(h)]}-1\right).$

Thus, the optimal value of $\gamma$ is given by

$\gamma_{\rho}^{*}=\frac{1}{b}\left(W_{0}\left(\frac{1}{e}\left(\frac{b^{2}\left(\operatorname{KL}(\rho\|\pi)+\ln\frac{1}{\delta_{2}}\right)}{n\mathbb{E}_{\rho}[\tilde{\mathbb{V}}(h)]}-1\right)\right)+1\right),$

where $W_{0}$ is the principal branch of the Lambert W function, which is
defined as the inverse of the function $f(x)=xe^{x}$.

In order to define a grid for $\gamma$ we first determine the relevant range
for $\gamma_{\rho}^{*}$. We note that the variance
$\mathbb{E}_{\rho}[\tilde{\mathbb{V}}(h)]$ is estimated using Theorem 13,
which assumes that the range of the loss $\tilde{\ell}(\cdot,\cdot)$ is $c$.
The loss range provides a trivial upper bound on the variance
$\mathbb{E}_{\rho}[\tilde{\mathbb{V}}(h)]\leq\frac{c^{2}}{4}$. At the same
time, we have $\lambda\left(1-\frac{\lambda
n}{2(n-1)}\right)\leq\frac{n-1}{2n}$ (it is a downward-pointing parabola) and,
therefore, the right hand side of the bound in Theorem 13 is at least the
value of its second term, which is at least
$\frac{2c^{2}\ln\frac{1}{\delta_{1}}}{n-1}$, since
$\operatorname{KL}(\rho\|\pi)\geq 0$. Thus, we obtain that the estimate of
$\mathbb{E}_{\rho}[\tilde{\mathbb{V}}(h)]$ is in the range
$\left[\frac{2c^{2}\ln\frac{1}{\delta_{1}}}{n-1},\frac{c^{2}}{4}\right]$. We
use $V_{\min}=\frac{2c^{2}\ln\frac{1}{\delta_{1}}}{n-1}$ to denote the lower
bound of this range.

Since $W_{0}(\cdot)$ is a monotonically increasing function,
$\operatorname{KL}(\rho\|\pi)\geq 0$, and the estimate of
$\mathbb{E}_{\rho}[\tilde{\mathbb{V}}(h)]$ is at most $\frac{c^{2}}{4}$, we
obtain that $\gamma_{\rho}^{*}$ satisfies

$\displaystyle\gamma_{\rho}^{*}$
$\displaystyle=\frac{1}{b}\left(W_{0}\left(\frac{1}{e}\left(\frac{b^{2}\left(\operatorname{KL}(\rho\|\pi)+\ln\frac{1}{\delta_{2}}\right)}{n\mathbb{E}_{\rho^{2}}[\tilde{\mathbb{V}}(h)]}-1\right)\right)+1\right)$
$\displaystyle\geq\frac{1}{b}\left(W_{0}\left(\frac{1}{e}\left(\frac{4b^{2}}{nc^{2}}\ln\frac{1}{\delta_{2}}-1\right)\right)+1\right)\stackrel{{\scriptstyle
def}}{{=}}\gamma_{\min}.$

For an upper bound we observe that since $\mathbb{E}_{\rho}[\tilde{L}(h)]$ is
trivially bounded by $b$, the bound in Theorem 13 is only interesting if it is
smaller than $b$ and, in particular, $\frac{\phi(\gamma b)}{\gamma
b^{2}}\mathbb{E}_{\rho}[\tilde{\mathbb{V}}(h)]\leq b$. This gives

$b\geq\frac{\phi(\gamma b)}{\gamma
b^{2}}\mathbb{E}_{\rho}[\tilde{\mathbb{V}}(h)]\geq\frac{\phi(\gamma b)}{\gamma
b^{2}}V_{\min}.$

Thus, $\gamma$ should satisfy

$\phi(\gamma b)\leq\frac{\gamma b^{3}}{V_{\min}},$

which gives that the maximal value of $\gamma$, denoted $\gamma_{max}$, is the
positive root of

$H(\gamma)=e^{\gamma b}-\gamma b\left(1+\frac{b^{2}}{V_{\min}}\right)-1=0.$

Let $\alpha=\left(1+b^{2}/V_{\min}\right)^{-1}\in(0,1)$, and $x=-\gamma
b-\alpha$. Then the above problem is equivalent to finding the root of
$f(x)=xe^{x}-d$ for $d=-\alpha e^{-\alpha}$, which can again be solved by
applying the Lambert W function. Since for $\alpha\in(0,1)$, we have
$d\in(-1/e,0)$, which indicates that there are two roots [Corless et al.,
1996]. We denote the root greater than $-1$ as $W_{0}(d)$ and the root less
than $-1$ as $W_{-1}(d)$. It is obvious that $W_{0}(d)=-\alpha$. However,
$W_{0}(d)$ is not the desired solution, since for $b>0$, $x=-\alpha$ implies
$\gamma=0$, but we assume $\gamma>0$. Hence, $W_{-1}(d)$ is the desired root,
which gives the corresponding $\gamma=-\frac{1}{b}(W_{-1}(d)+\alpha)>0$. Thus,
we obtain

$\gamma_{max}=-\frac{1}{b}\left(W_{-1}\left(-\frac{1}{1+\frac{b^{2}}{V_{\min}}}\cdot
e^{-\frac{1}{1+\frac{b^{2}}{V_{\min}}}}\right)+\frac{1}{1+\frac{b^{2}}{V_{\min}}}\right).$

We construct the grid by taking $\gamma_{i}=c_{2}^{i-1}\gamma_{\min}$ for
$i\in\\{1,\dots,k_{\gamma}\\}$, were
$k_{\gamma}=\lceil\ln(\gamma_{max}/\gamma_{\min})/\ln c_{2}\rceil$. In the
experiments we took $c_{2}=1.05$, and
$\delta_{1}=\delta_{2}=\delta/(2k_{\mu})$.

###  D.2 Minimization of the bound in Theorem 12

As discussed in Section 6, we build a set of data-dependent hypotheses by
splitting the data set $S$ into pairs of subsets $S=T_{h}\cup S_{h}$, such
that $T_{h}\cap S_{h}=\emptyset$, training $h$ on $T_{h}$ and calculating an
unbiased loss estimate $\hat{L}(h,S_{h})$ on $S_{h}$. For tandem losses we
compute the unbiased estimates $\hat{L}(h,h^{\prime},S_{h}\cap
S_{h^{\prime}})$ on the intersections of the corresponding sets $S_{h}$ and
$S_{h^{\prime}}$. The adjustment of the bound from Theorem 12 to this
construction is

$L(\operatorname{MV}_{\rho})\leq\frac{1}{(0.5-\mu)^{2}}\bigg{(}\frac{\mathbb{E}_{\rho^{2}}[\hat{L}(h,h^{\prime},S_{h}\cap
S_{h^{\prime}})]}{1-\frac{\lambda}{2}}+\frac{2\operatorname{KL}(\rho\|\pi)+\ln(4k\sqrt{m}/\delta)}{\lambda\left(1-\frac{\lambda}{2}\right)m}\\\
-2\mu\left(\left(1-\frac{\gamma}{2}\right)\mathbb{E}_{\rho}[\hat{L}(h,S_{h})]-\frac{\operatorname{KL}(\rho\|\pi)+\ln(4k\sqrt{n}/\delta)}{\gamma
n}\right)+\mu^{2}\bigg{)},$

where $m=\min_{h,h^{\prime}}|S_{h}\cap S_{h^{\prime}}|$ and
$n=\min_{h}|S_{h}|$. Below we derive update rules for $\mu$, $\lambda$,
$\gamma$, and $\rho$ for alternating minimization of this bound.

##### Optimal $\lambda$ given $\rho$

Minimization of the bound with respect to $\lambda$ is identical to
minimization of the tandem bound by Masegosa et al. [2020, Theorem 9].
Masegosa et al. derive the optimal value of $\lambda$:

$\displaystyle\lambda_{\rho}^{*}=\frac{2}{\sqrt{\frac{2m\mathbb{E}_{\rho^{2}}[\hat{L}(h,h^{\prime},S_{h}\cap
S_{h^{\prime}})]}{2\operatorname{KL}(\rho||\pi)+\ln\frac{4k\sqrt{m}}{\delta}}+1}+1}.$

##### Optimal $\gamma$ given $\rho$

Minimization of the bound with respect to $\gamma$ is analogous to
minimization of the bound by Masegosa et al. [2020, Theorem 10] with respect
to $\gamma$. Masegosa et al. derive the optimal value of $\gamma$:

$\displaystyle\gamma_{\rho}^{*}$
$\displaystyle=\sqrt{\frac{2\operatorname{KL}(\rho||\pi)+\ln(16k^{2}n/\delta^{2})}{n\mathbb{E}_{\rho}[\hat{L}(h,S_{h})]}}.$

##### Optimal $\mu$ given $\rho$

Given $\rho$, we can compute the optimal $\lambda_{\rho}^{*}$ and
$\gamma_{\rho}^{*}$ by the above formulas. Let

$\displaystyle U_{T}(\rho)$
$\displaystyle:=\frac{\mathbb{E}_{\rho^{2}}[\hat{L}(h,h^{\prime},S_{h}\cap
S_{h^{\prime}})]}{1-\frac{\lambda_{\rho}^{*}}{2}}+\frac{2\operatorname{KL}(\rho\|\pi)+\ln(4k\sqrt{m}/\delta)}{\lambda_{\rho}^{*}\left(1-\frac{\lambda_{\rho}^{*}}{2}\right)m},$
$\displaystyle L_{G}(\rho)$
$\displaystyle:=\left(1-\frac{\gamma_{\rho}^{*}}{2}\right)\mathbb{E}_{\rho}[\hat{L}(h,S_{h})]-\frac{\operatorname{KL}(\rho\|\pi)+\ln(4k\sqrt{n}/\delta)}{\gamma_{\rho}^{*}n}.$

Then the optimal $\mu$ is

$\mu_{\rho}^{*}=\frac{\frac{1}{2}L_{G}(\rho)-U_{T}(\rho)}{\frac{1}{2}-L_{G}(\rho)}.$

##### Gradient w.r.t. $\rho$ given $\lambda$, $\gamma$ and $\mu$

Minimization of the bound w.r.t. $\rho$ is equivalent to constrained
optimization of $f(\rho)=a\mathbb{E}_{\rho^{2}}[\hat{L}(h,h^{\prime},S_{h}\cap
S_{h^{\prime}})]-2b\mathbb{E}_{\rho}[\hat{L}(h,S_{h})]+2c\operatorname{KL}(\rho||\pi)$,
where $a=1/(1-\lambda/2)$, $b=\mu(1-\gamma/2)$ and
$c=1/(\lambda(1-\lambda/2)m)+\mu/(\gamma n)$, and the constraint is that
$\rho$ is a probability distribution. We optimize $\rho$ by projected gradient
descent, where we iteratively take steps in the direction of the negative
gradient of $f$ and project the result onto the probability simplex.

We use $\hat{L}$ to denote the vector of empirical losses and
$\hat{L}_{\operatorname{tnd}}$ to denote the matrix of tandem losses. Let
$\nabla f$ denote the gradient of $f$ w.r.t. $\rho$ and $(\nabla f)_{h}$ the
$h$-th coordinate of the gradient. We have:

$\displaystyle(\nabla f)_{h}$
$\displaystyle=2\left(a\sum_{h^{\prime}}\rho(h^{\prime})\hat{L}(h,h^{\prime},S_{h}\cap
S_{h^{\prime}})-b\hat{L}(h,S_{h})+c\left(1+\ln\frac{\rho(h)}{\pi(h)}\right)\right),$
$\displaystyle\nabla f$
$\displaystyle=2\left(a\hat{L}_{\operatorname{tnd}}\rho-b\hat{L}+c\left(1+\ln\frac{\rho}{\pi}\right)\right).$

##### Gradient descent optimization w.r.t. $\rho$

To optimize the weighting $\rho$, we applied iRProp+ for the gradient based
optimization, a first order method with adaptive individual step sizes [Igel
and Hüsken, 2003, Florescu and Igel, 2018], until the bound did not improve
for 10 iterations.

##### Alternating optimization procedure

We applied an alternating optimization procedure w.r.t. the weighting $\rho$,
and the parameters $\lambda$, $\gamma$, and $\mu$. More explicitly, starting
from $\rho=\pi$, we computed the corresponding $\lambda,\gamma$, as well as
$\mu$. Then, given $\lambda,\gamma$, and $\mu$, we applied iterative gradient-
based optimization to $\rho$. The alternating procedure was stopped when the
improvement in the bound was smaller than $10^{-9}$.

###  D.3 Minimization of the bound in Theorem 15

The adjustment of the bound in Theorem 15 to our hypothesis space
construction, as described above, is: We minimize the bound without
considering $k_{\gamma}$ and $k_{\lambda}$ since we define the grid without
taking them into consideration. However, we put back $k_{\gamma}$ and
$k_{\lambda}$ when computing the generalization bound as

$L(\operatorname{MV}_{\rho})\leq\frac{1}{(0.5-\mu)^{2}}\Bigg{(}\mathbb{E}_{\rho^{2}}[\hat{L}_{\mu}(h,h^{\prime},S_{h}\cap
S_{h^{\prime}})]+\frac{2\operatorname{KL}(\rho\|\pi)+\ln\frac{2k}{\delta}}{\gamma
n}\\\
+\frac{\phi(\gamma(1-\mu)^{2})}{\gamma(1-\mu)^{4}}\left(\frac{\mathbb{E}_{\rho^{2}}[\hat{\mathbb{V}}_{\mu}(h,h^{\prime},S_{h}\cap
S_{h^{\prime}})]}{1-\frac{\lambda
n}{2(n-1)}}+\frac{K_{\mu}^{2}\left(2\operatorname{KL}(\rho\|\pi)+\ln\frac{2k}{\delta}\right)}{n\lambda\left(1-\frac{\lambda
n}{2(n-1)}\right)}\right)\Bigg{)},$

where $n=\min_{h,h^{\prime}}|S_{h}\cap S_{h^{\prime}}|$ and
$k=k_{\mu}k_{\lambda}k_{\gamma}$. When doing the optimization we take
$k=k_{\mu}$, because we believe that the union bound is overly conservative,
but when we compute the bound we take the proper
$k=k_{\mu}k_{\lambda}k_{\gamma}$.

##### Optimal $\lambda$ given $\mu$ and $\rho$

Given $\mu$ and $\rho$, $\lambda$ can be computed in the same way as in the
optimization of Theorem 13, since the optimization problem is the same, and
get

$\lambda_{\mu,\rho}^{*}=\frac{2(n-1)}{n}\left(\sqrt{\frac{2(n-1)\mathbb{E}_{\rho^{2}}[\hat{}\mathbb{V}_{\mu}(h,h^{\prime},S_{h}\cap
S_{h^{\prime}})]}{K_{\mu}^{2}(2\operatorname{KL}(\rho\|\pi)+\ln\frac{2k}{\delta})}+1}+1\right)^{-1}.$

In our implementation at every optimization step we took the closest $\lambda$
to the above value from the $\lambda$-grid.

##### Optimal $\gamma$ given $\mu$ and $\rho$

Given $\mu$ and $\rho$, the bound for the variance is obtained by plugging in
the optimal $\lambda_{\mu,\rho}^{*}$ computed above. Let

$U_{\mathbb{V}}(\rho,\mu)=\frac{\mathbb{E}_{\rho^{2}}[\hat{\mathbb{V}}_{\mu}(h,h^{\prime},S_{h}\cap
S_{h^{\prime}})]}{1-\frac{\lambda_{\mu,\rho}^{*}n}{2(n-1)}}+\frac{K_{\mu}^{2}\left(2\operatorname{KL}(\rho\|\pi)+\ln\frac{2k}{\delta}\right)}{n\lambda_{\mu,\rho}^{*}\left(1-\frac{\lambda_{\mu,\rho}^{*}n}{2(n-1)}\right)}.$

Then

$\gamma^{*}=\frac{1}{(1-\mu)^{2}}\left(W_{0}\left(\frac{1}{e}\left(\frac{(1-\mu)^{4}\left(2\operatorname{KL}(\rho\|\pi)+\ln\frac{2k}{\delta}\right)}{nU_{\mathbb{V}}(\rho,\mu)}-1\right)\right)+1\right),$

where $W_{0}$ is the principal branch of the Lambert W function, which is
defined as the inverse of the function $f(x)=xe^{x}$. In our implementation at
every optimization step we took the closest $\gamma$ to the above value from
the $\gamma$-grid.

##### Gradient w.r.t. $\rho$ given $\lambda$, $\gamma$, and $\mu$

Optimizing the bound w.r.t. $\rho$ is equivalent to constrained optimization
of
$f(\rho)=\mathbb{E}_{\rho^{2}}[\hat{L}_{\mu}(h,h^{\prime},S^{\prime})]+a\mathbb{E}_{\rho^{2}}[\hat{V}_{\mu}(h,h^{\prime},S^{\prime})]+2b\operatorname{KL}(\rho||\pi)$,
where

$a=\frac{\phi((1-\mu)^{2}\gamma)}{(1-\mu)^{4}\gamma}\frac{1}{1-\frac{n\lambda}{2(n-1)}},\quad
b=\frac{1}{\gamma
n}+\frac{\phi((1-\mu)^{2}\gamma)}{(1-\mu)^{4}\gamma}\frac{K_{\mu}^{2}}{n\lambda(1-\frac{n\lambda}{2(n-1)})},$

and the constraint is that $\rho$ must be a probability distribution. We
optimize $\rho$ in the same way as presented in Appendix D.2. We use
$\hat{L}_{\mu}$ to denote the matrix of empirical $\mu$-tandem losses and
$\hat{\mathbb{V}}_{\mu}$ to denote the matrix of empirical variance of the
$\mu$-tandem losses. Then, the gradient w.r.t. $\rho$ is given by:

$\displaystyle(\nabla f)_{h}$
$\displaystyle=2\left(\sum_{h^{\prime}}\rho(h^{\prime})(\hat{L}_{\mu}(h,h^{\prime},S^{\prime})+a\hat{}\mathbb{V}\mu(h,h^{\prime},S^{\prime}))+b\left(1+\ln\frac{\rho(h)}{\pi(h)}\right)\right),$
$\displaystyle\nabla f$
$\displaystyle=2\left(\hat{L}_{\mu}\rho+a\hat{\mathbb{V}}_{\mu}\rho+b\left(1+\ln\frac{\rho}{\pi}\right)\right).$

We applied gradient descent in the same way as presented in Appendix D.2.

##### Optimization w.r.t. $\mu$

We were unable to find a closed-form solution for minimization of the bound
w.r.t. $\mu$ and applied a heuristic. Empirically we observed that the bound
was quasiconvex in $\mu$ (we were unable to prove that it is always the case)
and applied binary search for $\mu$ in the grid
$\\{\mu_{1},\dots,\mu_{k_{\mu}}\\}$. For each value of $\mu$ selected by the
binary search we minimized the bound w.r.t. $\rho$, $\lambda$, and $\gamma$,
starting from $\rho=\pi$ and using the update ruled described above until the
improvement in the bound was smaller than $10^{-9}$. Then, we continued to the
next value of $\mu$ proposed by the binary search, until convergence on the
$\mu$-grid.

##  Appendix E Experiments

###  E.1 Data sets

As mentioned, we considered data sets from the UCI and LibSVM repositories
[Dua and Graff, 2019, Chang and Lin, 2011], as well as Fashion-MNIST (Fashion)
from Zalando Research111https://research.zalando.com/welcome/mission/research-
projects/fashion-mnist/. We used data sets with size $3000\leq N\leq 70000$
and dimension $d\leq 1000$. These relatively large data sets were chosen in
order to provide meaningful bounds in the standard bagging setting, where
individual trees are trained on $n=0.8N$ randomly subsampled points with
replacement and the size of the overlap of out-of-bag sets is roughly $n/9$.
An overview of the data sets is given in Table 1.

Table 1: Data set overview. $c_{\min}$ and $c_{\max}$ denote the minimum and maximum class frequency. Data set | $N$ | $d$ | $c$ | $c_{\min}$ | $c_{\max}$ | Source
---|---|---|---|---|---|---
Adult | 32561 | 123 | 2 | 0.2408 | 0.7592 | LIBSVM (a1a)
Cod-RNA | 59535 | 8 | 2 | 0.3333 | 0.6667 | LIBSVM
Connect-4 | 67557 | 126 | 3 | 0.0955 | 0.6583 | LIBSVM
Fashion | 70000 | 784 | 10 | 0.1000 | 0.1000 | Zalando Research
Letter | 20000 | 16 | 26 | 0.0367 | 0.0406 | UCI
MNIST | 70000 | 780 | 10 | 0.0902 | 0.1125 | LIBSVM
Mushroom | 8124 | 22 | 2 | 0.4820 | 0.5180 | LIBSVM
Pendigits | 10992 | 16 | 10 | 0.0960 | 0.1041 | LIBSVM
Phishing | 11055 | 68 | 2 | 0.4431 | 0.5569 | LIBSVM
Protein | 24387 | 357 | 3 | 0.2153 | 0.4638 | LIBSVM
SVMGuide1 | 3089 | 4 | 2 | 0.3525 | 0.6475 | LIBSVM
SatImage | 6435 | 36 | 6 | 0.0973 | 0.2382 | LIBSVM
Sensorless | 58509 | 48 | 11 | 0.0909 | 0.0909 | LIBSVM
Shuttle | 58000 | 9 | 7 | 0.0002 | 0.7860 | LIBSVM
Splice | 3175 | 60 | 2 | 0.4809 | 0.5191 | LIBSVM
USPS | 9298 | 256 | 10 | 0.0761 | 0.1670 | LIBSVM
w1a | 49749 | 300 | 2 | 0.0297 | 0.9703 | LIBSVM

For all experiments, we removed patterns with missing entries and made a
stratified split of the data set. For data sets with a training and a test set
(SVMGuide1, Splice, Adult, w1a, MNIST, Shuttle, Pendigits, Protein, SatImage,
USPS) we combined the training and test sets and shuffled the entire set
before splitting.

###  E.2 Optimized weighted random forest

#### Experimental Setting

This section describes in detail the settings and the results of the empirical
evaluation using random forest (RF) majority vote classifiers.

We construct the ensemble from decision trees available in scikit-learn. For
each data set, an ensemble of 100 trees is trained using bagging (as described
in Section 6). For each tree, the Gini criterion is used for splitting and
$\sqrt{d}$ features are considered in each split.

We compare the RF using the default uniform weighting $\rho_{u}$ and the
optimized weighting obtained by $\operatorname{FO}$ [Thiemann et al., 2016],
$\operatorname{TND}$ [Masegosa et al., 2020], $\operatorname{C\mu TND}$
(Theorem 12) and $\operatorname{COTND}$ (Theorem 15). Optimization is based on
the out-of-bag sets (see Section 6). For each optimized RF, we also compute
the optimized bound.

#### Numerical Results

This section lists the numerical results for the empirical evaluation using
RF.

Table 2: Numerical values of the test loss obtained by the RFs with optimized
weighting. The smallest loss is highlighted in bold, while the smallest
optimized loss is highlighted using underscore.

Data set $L(\operatorname{MV}_{u})$ $L(\operatorname{MV}_{\rho_{\lambda}})$
$L(\operatorname{MV}_{\rho_{\operatorname{TND}}})$
$L(\operatorname{MV}_{\rho_{\operatorname{C\mu TND}}})$
$L(\operatorname{MV}_{\rho_{\operatorname{COTND}}})$ SVMGuide1 0.0283 (0.0009)
0.0358 (0.0041) 0.0283 (0.0016) 0.0284 (0.0019) 0.0281 (0.0023) Phishing
0.0274 (0.0018) 0.0344 (0.0078) 0.0275 (0.0019) 0.0271 (0.0016) 0.027 (0.0018)
Mushroom 0.0 (0.0) 0.0 (0.0) 0.0 (0.0) 0.0 (0.0) 0.0 (0.0) Splice 0.028
(0.0113) 0.1143 (0.0225) 0.0293 (0.0119) 0.0315 (0.0117) 0.0293 (0.0101) w1a
0.0107 (0.0006) 0.0174 (0.0014) 0.0107 (0.0005) 0.0108 (0.0006) 0.0107
(0.0005) Cod-RNA 0.04 (0.0011) 0.07 (0.009) 0.0392 (0.0015) 0.0392 (0.0011)
0.0392 (0.0014) Adult 0.168 (0.0033) 0.1896 (0.0154) 0.1692 (0.0038) 0.1697
(0.0028) 0.169 (0.0032) Protein 0.3254 (0.005) 0.4802 (0.038) 0.3312 (0.0059)
0.3469 (0.0044) 0.3252 (0.0035) Connect-4 0.1713 (0.0029) 0.275 (0.0225)
0.1692 (0.0015) 0.1705 (0.0013) 0.1697 (0.0022) Shuttle 0.0002 (0.0001) 0.0004
(0.0002) 0.0002 (0.0001) 0.0002 (0.0001) 0.0002 (0.0001) Pendigits 0.0107
(0.0021) 0.0523 (0.0093) 0.0106 (0.0015) 0.011 (0.0017) 0.0108 (0.0022) Letter
0.0367 (0.0049) 0.1161 (0.0248) 0.0378 (0.005) 0.04 (0.0052) 0.0367 (0.0042)
SatImage 0.0853 (0.0086) 0.1293 (0.0324) 0.0858 (0.0081) 0.0875 (0.0088)
0.0847 (0.0086) Sensorless 0.0015 (0.0004) 0.015 (0.0017) 0.0012 (0.0004)
0.0012 (0.0004) 0.0013 (0.0003) USPS 0.039 (0.0049) 0.1244 (0.0301) 0.0392
(0.0057) 0.0413 (0.0057) 0.0399 (0.0048) MNIST 0.0317 (0.0021) 0.1738 (0.0116)
0.0319 (0.0019) 0.0322 (0.0022) 0.0316 (0.0016) Fashion 0.1181 (0.002) 0.2194
(0.0267) 0.1203 (0.0024) 0.1215 (0.0023) 0.1187 (0.0022)

Table 3: Numerical values of the bounds for the RFs with optimized weighting. The tightest bound is highlighted in bold, while the tightest second-order bound is highlighted using underscore. Data set | $\operatorname{FO}(\rho_{\lambda})$ | $\operatorname{TND}(\rho_{\operatorname{TND}})$ | $\operatorname{C\mu TND}(\rho_{\operatorname{C\mu TND}})$ | $\operatorname{COTND}(\rho_{\operatorname{COTND}})$
---|---|---|---|---
SVMGuide1 | 0.1062 (0.0093) | 0.1835 (0.0048) | 0.2032 (0.0038) | 0.3315 (0.0044)
Phishing | 0.1201 (0.0015) | 0.1648 (0.0017) | 0.1835 (0.0013) | 0.2671 (0.0022)
Mushroom | 0.0068 (0.0001) | 0.0352 (0.0002) | 0.064 (0.0002) | 0.1654 (0.0005)
Splice | 0.3348 (0.0129) | 0.4113 (0.0061) | 0.4306 (0.0054) | 0.7623 (0.0076)
w1a | 0.0414 (0.0015) | 0.0637 (0.0009) | 0.0711 (0.001) | 0.0889 (0.0012)
Cod-RNA | 0.1634 (0.0018) | 0.1663 (0.0012) | 0.1778 (0.0012) | 0.1976 (0.0013)
Adult | 0.441 (0.0039) | 0.5712 (0.0055) | 0.5391 (0.004) | 0.6098 (0.0047)
Protein | 1.0 (0.0) | 1.0 (0.0) | 1.0 (0.0) | 1.0 (0.0)
Connect-4 | 0.5991 (0.0066) | 0.6831 (0.0025) | 0.6671 (0.0023) | 0.717 (0.002)
Shuttle | 0.0025 (0.0001) | 0.0077 (0.0002) | 0.0119 (0.0002) | 0.0254 (0.0002)
Pendigits | 0.1403 (0.0026) | 0.1435 (0.0018) | 0.1694 (0.0019) | 0.2494 (0.003)
Letter | 0.3864 (0.0064) | 0.45 (0.0042) | 0.4497 (0.0035) | 0.5323 (0.0045)
SatImage | 0.3765 (0.0086) | 0.4873 (0.0089) | 0.465 (0.006) | 0.6588 (0.0073)
Sensorless | 0.035 (0.0038) | 0.0256 (0.0008) | 0.0317 (0.0009) | 0.0443 (0.001)
USPS | 0.3395 (0.0069) | 0.4076 (0.0057) | 0.4108 (0.0044) | 0.548 (0.0056)
MNIST | 0.3786 (0.0038) | 0.3542 (0.0016) | 0.3699 (0.0016) | 0.3927 (0.0018)
Fashion | 0.4799 (0.0038) | 0.5432 (0.0029) | 0.5391 (0.0024) | 0.5795 (0.0025)

Table 2 provides the numerical values of the test loss obtained by the RFs
with uniform weighting and with weighting optimized by $\operatorname{FO}$,
$\operatorname{TND}$, $\operatorname{C\mu TND}$ and $\operatorname{COTND}$; a
visual presentation is given in Figure 2(a). As observed by Masegosa et al.
[2020], optimization using $\operatorname{FO}$ leads to overfitting, while the
second-order bounds does not significantly degrade the performance. Among the
second-order bounds, optimizing using $\operatorname{COTND}$ produces the best
classifier in most cases.

Table 3 provides the numerical values of the optimized bounds; a visual
presentation is given in Figure 2(b).

###  E.3 Ensemble of multiple heterogeneous classifiers

#### Experimental Setting

This section describes in detail the settings and the results of the
experimental evaluation using an ensemble of multiple heterogeneous
classifiers.

This ensemble is defined by a set of standard classifiers available in scikit-
learn:

  * •

Linear Discriminant Analysis, with default parameters, which includes a
singular value decomposition solver.

  * •

Three versions of k-Nearest Neighbors: (i) k=3 and uniform weights (i.e., all
points in each neighborhood are weighted equally); (ii) k=5 and uniform
weights; and (iii) k=5 where points are weighted by the inverse of their
distance. In all cases, it is employed the Euclidean distance.

  * •

Decision Tree, with default parameters, which includes Gini criterion for
splitting and no maximum depth.

  * •

Logistic Regression, with default parameters, which includes L2 penalization.

  * •

Gaussian Naive Bayes, with default parameters.

We included three versions of the kNN classifier to test if our bounds could
deal with a heterogeneous set of classifiers where some of them are expected
to provide highly correlated errors while others are expected to provide much
less correlated errors.

Each of the seven classifiers of the ensemble was learned from a bootstrap
sample of the training data set. We did it in that way to be able to compute
and optimize our bounds with the out-of-bag-samples as described in Section 6.

#### Numerical Results

This section lists the numerical results for the empirical evaluation using
ensembles of multiple heterogeneous classifiers.

Table 4 provides the numerical values of the test loss obtained by these
ensembles with uniform weighting and with weighting optimized by
$\operatorname{FO}$, $\operatorname{TND}$, $\operatorname{C\mu TND}$ and
$\operatorname{COTND}$; a visual presentation is given in Figure 2(c). In this
case, uniform voting is not a competitive weighting scheme. And second-order
bound performs much better than uniform weighting and than the weights
computed according to the first-order bound. There is any clear winner among
the second-order bounds.

Table 5 provides the numerical values of the optimized bounds; a visual
presentation is given in Figure 2(d).

Table 4: Numerical values of the test loss obtained by ensembles of multiple
heterogeneous classifiers with optimized weighting. The smallest loss is
highlighted in bold, while the smallest optimized loss is highlighted using
underscore.

Data set $L(\operatorname{MV}_{u})$ $L(h_{best})$
$L(\operatorname{MV}_{\rho_{\lambda}})$
$L(\operatorname{MV}_{\rho_{\operatorname{TND}}})$
$L(\operatorname{MV}_{\rho_{\operatorname{C\mu TND}}})$
$L(\operatorname{MV}_{\rho_{\operatorname{COTND}}})$ SVMGuide1 0.0357 (0.0006)
0.0426 (0.0034) 0.0426 (0.0034) 0.0358 (0.0024) 0.0355 (0.0026) 0.0357
(0.0006) Phishing 0.0342 (0.0028) 0.0438 (0.0056) 0.0438 (0.0056) 0.0343
(0.0035) 0.0337 (0.0033) 0.0342 (0.0028) Mushroom 0.0 (0.0) 0.0001 (0.0003)
0.0 (0.0) 0.0 (0.0) 0.0 (0.0) 0.0 (0.0) Splice 0.1068 (0.0147) 0.0743 (0.0109)
0.0743 (0.0109) 0.0746 (0.0111) 0.0743 (0.0109) 0.1068 (0.0147) w1a 0.0125
(0.0006) 0.0148 (0.0007) 0.0148 (0.0007) 0.0129 (0.0007) 0.0129 (0.0007)
0.0125 (0.0006) Cod-RNA 0.0698 (0.0014) 0.063 (0.002) 0.063 (0.002) 0.0541
(0.0018) 0.0541 (0.0019) 0.0698 (0.0014) Adult 0.1616 (0.0033) 0.1536 (0.0031)
0.1536 (0.0031) 0.1546 (0.0036) 0.1535 (0.0025) 0.1616 (0.0033) Protein 0.3499
(0.0068) 0.3269 (0.0045) 0.3269 (0.0045) 0.3199 (0.0032) 0.3269 (0.0045)
0.3499 (0.0068) Connect-4 0.2056 (0.0032) 0.2443 (0.0042) 0.2443 (0.0042)
0.201 (0.0024) 0.2011 (0.0028) 0.2056 (0.0032) Shuttle 0.0012 (0.0003) 0.0005
(0.0001) 0.0005 (0.0001) 0.0007 (0.0002) 0.0007 (0.0002) 0.0012 (0.0003)
Pendigits 0.0111 (0.001) 0.0084 (0.0012) 0.0084 (0.0012) 0.0076 (0.001) 0.0076
(0.0008) 0.0111 (0.001) Letter 0.0708 (0.003) 0.0663 (0.0032) 0.0663 (0.0032)
0.053 (0.0047) 0.0538 (0.0043) 0.0708 (0.003) SatImage 0.1035 (0.0016) 0.1037
(0.0056) 0.1035 (0.0059) 0.0957 (0.0041) 0.0968 (0.0047) 0.1035 (0.0016)
Sensorless 0.1911 (0.0218) 0.0224 (0.0014) 0.0224 (0.0014) 0.0224 (0.0014)
0.0224 (0.0014) 0.1911 (0.0218) USPS 0.0361 (0.0052) 0.0378 (0.0051) 0.0378
(0.0051) 0.0335 (0.0054) 0.0334 (0.0057) 0.0361 (0.0052) MNIST 0.0364 (0.0023)
0.0358 (0.0009) 0.0348 (0.0027) 0.0311 (0.001) 0.0312 (0.001) 0.0364 (0.0023)
Fashion 0.1344 (0.0028) 0.1544 (0.0028) 0.1544 (0.0028) 0.1326 (0.0036) 0.1354
(0.0038) 0.1344 (0.0028)

Table 5: Numerical values of the bounds for ensembles of multiple heterogeneous classifiers with optimized weighting. The tightest bound is highlighted in bold, while the tightest second-order bound is highlighted using underscore. Data set | $\operatorname{FO}(\rho_{\lambda})$ | $\operatorname{TND}(\rho_{\operatorname{TND}})$ | $\operatorname{C\mu TND}(\rho_{\operatorname{C\mu TND}})$ | $\operatorname{COTND}(\rho_{\operatorname{COTND}})$
---|---|---|---|---
SVMGuide1 | 0.1087 (0.0042) | 0.2181 (0.007) | 0.2294 (0.0053) | 0.4699 (0.0039)
Phishing | 0.1212 (0.0036) | 0.1954 (0.0033) | 0.2095 (0.0023) | 0.4301 (0.0047)
Mushroom | 0.0074 (0.0001) | 0.0406 (0.0006) | 0.068 (0.0011) | 0.3615 (0.0036)
Splice | 0.2274 (0.0204) | 0.4578 (0.0289) | 0.4227 (0.019) | 0.8277 (0.0159)
w1a | 0.0385 (0.0006) | 0.0692 (0.0022) | 0.0769 (0.0022) | 0.1917 (0.0075)
Cod-RNA | 0.1452 (0.0017) | 0.2169 (0.0025) | 0.2203 (0.0025) | 0.3414 (0.0018)
Adult | 0.3347 (0.008) | 0.5682 (0.0068) | 0.5226 (0.0054) | 0.6426 (0.0028)
Protein | 0.6949 (0.0044) | 1.0 (0.0) | 0.897 (0.006) | 1.0 (0.0)
Connect-4 | 0.5136 (0.0032) | 0.7319 (0.0052) | 0.6591 (0.0027) | 0.7582 (0.0106)
Shuttle | 0.0033 (0.0006) | 0.0106 (0.0007) | 0.0148 (0.0008) | 0.1657 (0.0038)
Pendigits | 0.035 (0.0021) | 0.0876 (0.004) | 0.106 (0.0037) | 0.3883 (0.0057)
Letter | 0.1593 (0.0027) | 0.2677 (0.0081) | 0.266 (0.0063) | 0.5718 (0.0039)
SatImage | 0.2707 (0.0107) | 0.4868 (0.0074) | 0.4363 (0.0067) | 0.6684 (0.0065)
Sensorless | 0.0523 (0.0028) | 0.1175 (0.0058) | 0.1229 (0.006) | 1.0 (0.0)
USPS | 0.1092 (0.0032) | 0.221 (0.0047) | 0.2269 (0.0041) | 0.4795 (0.0034)
MNIST | 0.0807 (0.0023) | 0.1397 (0.0044) | 0.1437 (0.0041) | 0.3206 (0.0035)
Fashion | 0.3295 (0.0035) | 0.4945 (0.0075) | 0.4648 (0.0055) | 0.5703 (0.0062)


# Fractional quantum Hall states in charge-imbalanced bilayer systems

N. Thiebaut1 N. Regnault2,3 and M.O. Goerbig1 1 Laboratoire de Physique des
Solides, CNRS UMR 8502, Univ. Paris-Sud, F-91405 Orsay cedex, France  2
Laboratoire Pierre Aigrain, ENS and CNRS, 24 rue Lhomond, 75005 Paris, France
3 Department of Physics, Princeton University, Princeton, NJ 08544
<EMAIL_ADDRESS>
###### Abstract

We study the fractional quantum Hall effect in a bilayer with charge-
distribution imbalance induced, for instance, by a bias gate voltage. The
bilayer can either be intrinsic or it can be formed spontaneously in wide
quantum wells, due to the Coulomb repulsion between electrons. We focus on
fractional quantum Hall effect in asymmetric bilayer systems at filling factor
$\nu=4/11$ and show that an asymmetric Halperin-like trial wavefunction gives
a valid description of the ground state of the system.

##  1 Introduction

In a two-dimensional electron gas subjected to a high magnetic field
repulsively interacting electrons may collectively form a gapped state
insensitive to small perturbations. Such states are called fractional quantum
Hall states (FQHS) and show up for partial (fractional) fillings of the
highest partially occupied Landau level, i.e. for rational values of the
filling factor $\nu$, which is the ratio of the number of electrons $N$ and
the number of magnetic flux quanta $N_{\phi}$ threading the system. Since the
discovery of the fractional quantum Hall effect (FQHE) in 1982 [1] new
experimental setups nourished our understanding of this multifaceted
phenomenon.

The bilayer system, which consists of two parallel 2D electron systems in a
semiconductor heterostructure exhibits FQHE at even-denominator filling
factors (such as $\nu=1/2$ [2]) is one of them. Though it is more common to
consider symmetric layers, for which charges are equally spread between the
two layers ($\nu_{\text{tot}}=2/n$), we are interested in a bilayer system
with charge imbalance, which is obtained by the application of an external
gate voltage (fig. 1). The strength of correlations between electrons that
belong to different layers depends on their distance $d$ and the energy
difference between the two layers $\Delta$ is proportional to the external
gate voltage $V_{G}$.

Beside its own richness, the FQHE in a bilayer system provides a model for its
counterpart in a wide quantum well [3, 4, 5], where even-denominator states
have also been observed [3, 4, 6]. In the latter, density functional theory
calculations indicate that the Coulomb repulsion favors an electron
concentration at the borders of the quantum well, which may thus be viewed as
a spontaneously formed bilayer system [7]. Charge-imbalanced bilayers can thus
depict wide quantum wells in which electrons split in two layers and populate
one of them preferentially, either spontaneously or under the influence of
external gate electrodes.

Here, we investigate the conditions for the existence of FQHS (at $\nu=4/11$)
in an imbalanced bilayer system by means of exact diagonalization. We
introduce asymmetric Halperin states and discuss their relevance for the
description of the ground state of the system.

Figure 1: Schematic view of the effect of a gate voltage on a bilayer system.
(Left) Setup. (Right) Effect of the gate voltage on the confinement potential.
We consider the limit where the width $w$ of each quantum well is small as
compared to the layer separation $d$, $w\ll d$.

##  2 Model

We restrict the electron dynamics to the lowest Landau level, which amounts to
considering the limit in which adjacent Landau levels are separated by a large
cyclotron gap, as compared to the characteristic Coulomb energy scale,
$e^{2}/4\pi l_{B}$. FQHS are often fully polarized due to the Coulomb
repulsion between electrons in a flat Landau energy level, and we consider
such states, that is we neglect the electron spin from now on. The effective
Hamiltonian of the bilayer system reads

$\hat{H}=\frac{1}{2}\sum_{\\{\sigma_{i}\\}}\sum_{\\{m_{i}\\}}V_{\\{m_{i}\\}}^{\\{\sigma_{i}\\}}c_{m_{1},\sigma_{1}}^{\dagger}c_{m_{2},\sigma_{2}}^{\dagger}c_{m_{4},\sigma_{4}}c_{m_{3},\sigma_{3}}+\Delta\sum_{m}(c_{m,\downarrow}^{\dagger}c_{m,{\downarrow}}-c_{m,\uparrow}^{\dagger}c_{m,{\uparrow}})\quad,$
(1)

where $\sigma=\uparrow,\downarrow$ is the layer index and $m_{i}$ the angular
momentum which labels the single-electron states in the symmetric gauge111Here
we assume that the confinement potential is sufficiently narrow (compared to
the layer separation, $w\ll d$) to avoid electrons from populating the first
excited state of the confinement potential. This permits to neglect the
wavefunction extent in the confinement direction, which assumption simplifies
the single particle Hilbert space as the layer index does not couple to the
orbital motion. [8]; $\Delta$ is the energy difference between the two layers,
controlled by the gate voltage $V_{G}$ in fig. 1. The first term on the right
hand side of eq. 1 is the usual interaction term, while the second one is a
Zeeman-like term proportional to the density imbalance. In real space the
interaction potential depends on the layer indices

$V^{\\{\sigma_{i}\\}}(r)=\left\\{\begin{array}[]{cl}\frac{e^{2}}{4\pi
r}&\mbox{ if electrons belong to the same layer (i.e. if
}\sigma_{1}=\sigma_{2}=\sigma_{3}=\sigma_{4}\text{)}\\\ &\\\
\frac{e^{2}}{4\pi\sqrt{r^{\,2}+d^{\,2}}}&\mbox{ if electrons belong to
different layers (i.e. if
}\sigma_{1}=\sigma_{3}\neq\sigma_{2}=\sigma_{4}\text{)}\\\ &\\\
0&\mbox{elsewise}\end{array}\right.$ (2)

##  3 Halperin’s wavefunctions

A large variety of FQHS in bilayer systems may be described with the help of a
generalization of Laughlin’s wavefunctions [9] to the case of electrons with
internal degrees of freedom, initially introduced by Halperin [10]. Those
wavefunctions have three integer parameters that characterise the interaction
strength between electrons in the $\uparrow$ and $\downarrow$ layers
($m_{\uparrow}$ and $m_{\downarrow}$), and electrons in different layers
($n$). In terms of the complex positions
$z_{i}^{\sigma}=x_{i}^{\sigma}-iy_{i}^{\sigma}$, for a system with
$N_{\sigma}$ electrons in the $\sigma$-layer, Halperin’s wavefunctions read

$\varPsi_{(m_{\uparrow},m_{\downarrow},n)}\big{(}\\{z_{i}^{\uparrow}\\},\\{z_{i}^{\downarrow}\\}\big{)}=\prod_{i<j\leq
N_{\uparrow}}(z_{i}^{\uparrow}-z_{j}^{\uparrow})^{m_{\uparrow}}\prod_{i<j\leq
N_{\downarrow}}(z_{i}^{\downarrow}-z_{j}^{\downarrow})^{m_{\downarrow}}\prod_{i\leq
N_{\uparrow},\,j\leq
N_{\downarrow}}(z_{i}^{\uparrow}-z_{j}^{\downarrow})^{n}\quad,$ (3)

where the normalization and usual Gaussian factors have been absorbed in a
redefinition of the Hilbert space measure
$d\mu(\\{z_{i}\\})=\prod_{i}dx_{i}dy_{i}\exp(-|z_{i}|^{2}/2l_{B}^{2})/(2\pi
l_{B}^{2})$, following Girvin and Jach [11]. Alternatively, we denote the
state represented by the Halperin wavefunction (3) the
$(m_{\uparrow},m_{\downarrow},n)$ state. Notice that not all Halperin state
(3) are capable of describing physically possible FQHS – it has been shown in
Ref. [12] within a generalization of Laughlin’s plasma analogy [9] that the
exponents must satisfy the condition

$m_{\uparrow}m_{\downarrow}\geq n^{2}$ (4)

in order to avoid phase separation of the electron species.

To compute the filling factor associated with a particular Halperin state, one
uses the fact that the maximum value of individual orbital momenta is given by
the number of flux quanta $N_{\phi}$ threading the system. The polynomial
expansion of eq. (3) yields a maximal exponent
$(N_{\sigma}-1)\;m_{\sigma}+N_{-\sigma}\;n$ for the position of the $i$-th
electron in the $\sigma$-layer that must equal $N_{\phi}$. This can be written
in matrix form as

$\begin{pmatrix}N_{\phi}+m_{\uparrow}\\\
N_{\phi}+m_{\downarrow}\end{pmatrix}=\begin{pmatrix}m_{\uparrow}&n\\\
n&m_{-}{\downarrow}\end{pmatrix}\begin{pmatrix}N_{\uparrow}\\\
N_{\downarrow}\end{pmatrix}\quad,$

and after inverting the matrix, one deduces the relationship between the total
number of electrons $N$ and $N_{\phi}$,

$N=N_{\uparrow}+N_{\downarrow}=\frac{1}{m_{\uparrow}m_{\downarrow}-n^{2}}\Big{[}(m_{\uparrow}+m_{\downarrow}-2n)N_{\phi}+2m_{\uparrow}m_{\downarrow}-n(m_{\uparrow}+m_{\downarrow})\Big{]}\quad.$
(5)

The filling factor $\nu$ is defined in the thermodynamic limit, for which we
obtain

$\nu=\lim_{N,N_{\phi}\rightarrow\infty}\frac{N}{N_{\phi}}=\frac{m_{\uparrow}+m_{\downarrow}-2n}{m_{\uparrow}m_{\downarrow}-n^{2}}\quad.$
(6)

We define the polarization as the population difference between the layers

$P_{z}=\frac{S_{z}}{N/2}$ (7)

in terms of the $z$-component of the total layer pseudospin

$S_{z}=\frac{N_{\uparrow}-N_{\downarrow}}{2}=\frac{(m_{\downarrow}-m_{\uparrow})(N_{\phi}-n)}{2(m_{\uparrow}m_{\downarrow}-n^{2})}\quad,$
(8)

which is zero for symmetric states (i.e. if $m_{\uparrow}=m_{\downarrow}$).

Now we focus on asymmetric Halperin states. More precisely we are interested
in the $(5,3,2)$ state, which satisfies the condition (4) since it is the
simplest (i.e. lowest correlation factors) asymmetric Halperin state for which
the filling factor $\nu_{532}=4/11$ does not belong to the usual composite-
fermions sequence $\nu_{\text{CF}}=p/(2sp\pm 1)$ [13]. It may thus describe
states the existence of which relies on layer asymmetry. Nevertheless it
should be mentioned that $\nu=4/11$ is also the filling factor of a second-
generation composite fermion state in monolayer systems [14, 15, 16, 17]
generated by interacting composite fermions that has been proposed as a
possible explanation for an experimentally observed FQHS at this filling [14].

##  4 Exact diagonalization

In order to check the physical relevance of the $(5,3,2)$ state we calculate,
with the help of exact diagonalization [18], two quantities for the Coulomb
interaction (2) in the lowest Landau level: the total angular momentum of the
ground state and its polarization as a function of the distance $d$ and of the
gate-induced energy difference $\Delta$ between the two layers. The
calculations are perfomed on the sphere geometry [19]. For the $(5,3,2)$
state, the relation between $N_{\Phi}$ and $N$ is given by
$N_{\Phi}=\frac{11}{4}N-\frac{7}{2}$. Finite-size systems induce a constraint
on the number of electrons [see eq. (5)]. Only sizes of the form $N=2+4n$,
$n\in\mathbb{N}$ can satisfy this constraint.

Here we will focus on $N=6$ and $N=10$ which are the only accessible sizes.
FQHS correspond to values of $d$ and $\Delta$ for which the gap is finite and
the total angular momentum equals zero. Finally we compute the overlap between
the $(5,3,2)$ state and the exact ground state for values of $d$ and $\Delta$
which correspond to a FQHS.

The polarization of the ground state is shown in fig. 2. For sufficiently high
values of $\Delta$ the system is fully polarized, i.e all electrons reside in
a single layer and one thus obtains the monolayer system with $\nu=4/11$,
studied in Refs. [15, 16, 17]. Conversely for large distances $d$ the
polarization tends to be zero. In this situation the potential
$V(r)=(r^{\,2}+d^{\,2})^{-1/2}$ between two electrons in different layers is
small and the system behaves as two uncorrelated layers with individual
filling factors $\nu=2/11$. It is likely that for such a low filling factor
the system tends to form a Wigner crystal [20, 21, 22], and FQHS may therefore
be ruled out.

(a) N=6: $P_{z}^{(532)}=-1/3$ (b) N=10: $P_{z}^{(532)}=-2/5$

Figure 2: Polarization of the bilayer system as a function of the distance
$d/l_{B}$ and energy shift $\Delta$ (energies are given in units of
$e^{2}/4\pi l_{B}$).

The polarization of the $(5,3,2)$ state can be computed directly from eq. (7)
and eq. (8)

$P_{z}^{(532)}=-\frac{1}{2}+\frac{1}{N}$ (9)

and may be compared with that obtained from exact diagonalization for $N=6$
and 10 particles, as a function of the layer separation $d/l_{B}$ and
$\Delta/(e^{2}/4\pi l_{B})$ (see fig. 2). Indeed, one finds that in
intermediate regimes the polarization of the ground state is the one of the
$(5,3,2)$ state (orange regions).

We now turn to the characterization of the exact ground state. Figure 3 shows
the total angular momentum $L$ of the ground state. This latest is
rotationally invariant when $L=0$, as required for an incompressible state. It
is zero in the region where the ground-state polarization matches that of the
$(5,3,2)$ state, except for large layer separations. As already mentioned in
the discussion above, for large distances inter-layer correlations are too
weak to allow the system to be in an incompressible state, and an
inhomogeneous density state is favored, such as one would for example expect
for a Wigner crystal ($d\gtrsim 3.8l_{B}$).

Figure 3: Total orbital momentum of the bilayer system for $N=6$ electrons as
a function of the distance $d/l_{B}$ and energy shift $\Delta$, in units of
$e^{2}/4\pi l_{B}$.

The results presented in figs. 2 and 3 indicate that in a certain range of
parameters $d/l_{B}$ and $\Delta/(e^{2}/4\pi l_{B})$, exact diagonalization
provides a ground state that matches some physical properties of the $(5,3,2)$
state. To corroborate the relevance of this state, we have calculated the
overlap between the exact ground state obtained for the interaction (2) and
the $(5,3,2)$ state. In order to obtain the $(5,3,2)$ state numerically, we
have used exact diagonalization for a model interaction given in terms of the
appropriate pseudopotentials [19]. The results are presented in fig. 4 as a
function of $d/l_{B}$. The overlap turns out to be high ($>85\%$) for
$d\lesssim 2l_{B}$, such that in regions of matching polarizations and for
sufficiently short interlayer distances the $(5,3,2)$ state gives a good
description of the ground state.

Figure 4: Overlap of the $(5,3,2)$ state with the exact ground state as a
function of $d/l_{B}$, in the corresponding polarization sector (9).

##  5 Conclusion

We have performed an exact-diagonalization study of the bilayer system for
various distances between the layers and energy shifts, i.e. the energy
difference between electrons in the two layers. The ground state is
incompressible over a certain range of parameters, which corresponds to an
interlayer distance of roughly three times the magnetic length. Asymmetry
between layers does not necessarily destroy the FQHS, and the FQHE at exotic
fractions may thus be observed in an asymmetric bilayer system. Asymmetric
Halperin’s wavefunctions are good candidates for the accurate description of
those states. Also, using the bilayer modeling of a wide quantum well, a
similar behavior could be expected in asymmetric wide quantum wells, the
asymmetry being induced, for instance, by a back gate voltage that enables one
to tune the electronic density of the system. Experimentalists reported a FQHE
at $\nu=4/11$ in a wide quantum well ($w\sim 3\;l_{B}$) in 2003 [14]. Since
this filling factor corresponds to the one of the $(5,3,2)$ state, one may
wonder about its relevance for the explanation of this experimental
observation. Within this picture this FQHS would be induced by the shape of
the confinement potential, in contrast to the picture of second-generation
composite fermions that have been proposed as an alternative explanation for
the 4/11 state [14, 15, 16, 17].

## References

  * [1] Tsui D C, Stormer H L and Gossard A C 1982 Phys. Rev. Lett. 48(22) 1559–1562
  * [2] Eisenstein J P, Boebinger G S, Pfeiffer L N, West K W and He S 1992 Phys. Rev. Lett. 68(9) 1383–1386
  * [3] Suen Y W, Santos M B and Shayegan M 1992 Phys. Rev. Lett. 69(24) 3551–3554
  * [4] Luhman D R, Pan W, Tsui D C, Pfeiffer L N, Baldwin K W and West K W 2008 Phys. Rev. Lett. 101(26) 266804
  * [5] Papić Z, Möller G, Milovanović M V, Regnault N and Goerbig M O 2009 Phys. Rev. B 79(24) 245325
  * [6] Shabani J, Gokmen T, Chiu Y T and Shayegan M 2009 Phys. Rev. Lett. 103(25) 256802
  * [7] Nuebler J, Friess B, Umansky V, Rosenow B, Heiblum M, von Klitzing K and Smet J 2012 Phys. Rev. Lett. 108(4) 046804
  * [8] Girvin S M 1984 Phys. Rev. B 29(10) 6012–6014
  * [9] Laughlin R B 1983 Phys. Rev. Lett. 50(18) 1395–1398
  * [10] Halperin B I 1983 Helv. Phys. Acta 56 75
  * [11] Girvin S M and Jach T 1984 Phys. Rev. B 29(10) 5617–5625
  * [12] de Gail R, Regnault N and Goerbig M O 2008 Phys. Rev. B 77(16) 165310
  * [13] Jain J K 1989 Phys. Rev. Lett. 63(2) 199–202
  * [14] Pan W, Stormer H L, Tsui D C, Pfeiffer L N, Baldwin K W and West K W 2003 Phys. Rev. Lett. 90(1) 016801
  * [15] Goerbig M O, Lederer P and Smith C M 2004 Phys. Rev. B 69(15) 155324
  * [16] López A and Fradkin E 2004 Phys. Rev. B 69(15) 155322
  * [17] Chang C C and Jain J K 2004 Phys. Rev. Lett. 92(19) 196806
  * [18] Diagham: http://nick-ux.lpa.ens.fr/diagham/wiki/
  * [19] Haldane F D M 1983 Phys. Rev. Lett. 51(7) 605–608
  * [20] Lam P K and Girvin S M 1984 Phys. Rev. B 30(1) 473–475
  * [21] Jiang H W, Willett R L, Stormer H L, Tsui D C, Pfeiffer L N and West K W 1990 Phys. Rev. Lett. 65(5) 633–636
  * [22] Jiang H W, Stormer H L, Tsui D C, Pfeiffer L N and West K W 1991 Phys. Rev. B 44(15) 8107–8114