# PAC-Bayesian Domain Adaptation Bounds for Multiclass Learners

Anthony Sicilia Intelligent Systems Program
University of Pittsburgh
Pittsburgh, Pennsylvania, USA  Katherine Atwell Department of Computer Science
University of Pittsburgh
Pittsburgh, Pennsylvania, USA  Malihe Alikhani Intelligent Systems Program
University of Pittsburgh
Pittsburgh, Pennsylvania, USA  Department of Computer Science
University of Pittsburgh
Pittsburgh, Pennsylvania, USA  Seong Jae Hwang

###### Abstract

Multiclass neural networks are a common tool in modern unsupervised domain
adaptation, yet an appropriate theoretical description for their non-uniform
sample complexity is lacking in the adaptation literature. To fill this gap,
we propose the first PAC-Bayesian adaptation bounds for multiclass learners.
We facilitate practical use of our bounds by also proposing the first
approximation techniques for the multiclass distribution divergences we
consider. For divergences dependent on a Gibbs predictor, we propose
additional PAC-Bayesian adaptation bounds which remove the need for
inefficient Monte-Carlo estimation. Empirically, we test the efficacy of our
proposed approximation techniques as well as some novel design-concepts which
we include in our bounds. Finally, we apply our bounds to analyze a common
adaptation algorithm that uses neural networks.

##  1 Introduction

††∗Corresponding Author

Multiclass neural networks are frequently used in implementation of many
unsupervised domain adaptation algorithms. For example, neural networks are
often employed for invariant feature learning algorithms [Ganin and Lempitsky,
2015b, Long et al., 2017, 2018, Zhang et al., 2019b], importance weighting
algorithms [Lipton et al., 2018b], or combinations of both techniques [Tachet
des Combes et al., 2020b]. While most of these adaptation algorithms are
motivated by theoretical bounds, recent literature has paid close attention to
the assumptions and failure-cases of some techniques [Zhao et al., 2019b, Wu
et al., 2019, Johansson et al., 2019b]. Namely, some learning algorithms
ignore key terms in the adaptation bounds on which they are based, and as a
result, may output solutions (i.e., learned models) that violate assumptions
and are guaranteed to fail at the adaptation task [Zhao et al., 2019b, Wu et
al., 2019]. Still, the story here is not totally complete. In particular,
there has not been much discussion of the non-uniform sample complexity of
these modern adaptation algorithms. Sample complexity, in fact, contributes an
additional “ignored” term in the theoretical bounds on which modern adaptation
algorithms are based.

In this paper, we propose the first multiclass adaptation bounds which allow
us to study this non-uniform sample complexity. Studying sample complexity is
important to our understanding of adaptation algorithms because it describes
how “data-hungry” an algorithm is. When this sample complexity is non-uniform
across an algorithm’s solution space, it allows us to study properties of a
solution as a function of its “data-hunger.” This is especially important for
adaptation algorithms, which as mentioned, can inadvertently output poor
solutions. Identifying a dynamic relationship between the properties of
solutions and their non-uniform sample-complexity can provide insight on how
to prevent these failure-cases in practice (e.g., by collecting sufficient
data for an algorithm). Non-uniform sample complexity (rather than uniform
complexity) can also help us to better quantify implicit regularization
inherent to our algorithm [Dziugaite and Roy, 2017b, Nagarajan and Kolter,
2019]. Accurately describing implicit regularization is especially important
when using neural networks [Neyshabur et al., 2014, Neyshabur, 2017, Keskar et
al., 2017, Zhang et al., 2017], since similar learning algorithms can lead to
solutions with distinct generalization performance and implicit regularization
is believed to be the cause of this phenomena.

Despite the importance of studying non-uniform sample complexity in modern
adaptation contexts, we are not aware of any multiclass adaptation bounds with
this capability. To fill this gap, we contribute the first PAC-Bayesian
adaptation bound for multiclass learners (Thm. 2). While PAC-Bayesian bounds
actually control error for stochastic models, we choose this framework for its
demonstrated empirical accuracy in describing neural network sample complexity
[Dziugaite and Roy, 2017b, Zhou et al., 2018, Jiang et al., 2019, Dziugaite et
al., 2020, 2021b, Pérez-Ortiz et al., 2021b]. Compared to existing bounds, we
design our proposals to be more sensitive to the solution output by our
learning algorithm as well as the data sample available for estimating key
quantities. The former is vital in studying non-uniform complexity of
adaptation algorithms (as discussed), while the latter is important for
facilitating empirical study. To make our bound useful in practice, we also
propose the first approximation techniques for the divergence terms in our
bound. In one case, this involves proposal of a novel surrogate for optimizing
01-loss (Thm. 4). In another, we show a standard technique for computing
divergence fails to generalize to the mutliclass setting without additional
constraints (Thm. 5). Working in the PAC-Bayesian framework, some divergences
we study are also expressed as expectations with no known analytic solution.
For these, we propose additional bounds (Thm. 6, Cor. 1) which allow us to
avoid inefficient Monte-Carlo estimation by introduction of a new flatness
assumption related to the well-known flat-minima hypothesis [Hochreiter and
Schmidhuber, 1997]. To conclude, we conduct extensive empirical study of more
than 12K models learned across 5 diverse adaptation datasets.

##  2 Background

###  2.1 Notation and Assumptions

Consider the space $\mathcal{X}\times\mathcal{Y}$ for some finite
$\mathcal{Y}$ with $|\mathcal{Y}|>2$ unless otherwise noted. Colloquially, we
call $\mathcal{X}$ the feature space and $\mathcal{Y}$ the label space. For a
distribution $\mathbb{D}$ over $\mathcal{X}\times\mathcal{Y}$, we are
interested in the risk functional
$\mathbf{R}_{\mathbb{D}}:\mathcal{Y}^{\mathcal{X}}\to[0,1]$

$\small\mathbf{R}_{\mathbb{D}}(h)\operatorname*{\ \overset{\mathrm{def}}{=}\
}\mathbf{Pr}(h(X)\neq Y);\qquad(X,Y)\sim\mathbb{D}$ (1)

applied to some hypothesis (i.e., model)
$h\in\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$. The risk functional
$\mathbf{R}_{\mathbb{D}}$ precisely gives the error rate of the hypothesis $h$
when tasked with modelling the relationship between $\mathcal{X}$ and
$\mathcal{Y}$ described by $\mathbb{D}$. In PAC-Bayes, we also consider the
risk of stochastic (Gibbs) predictors. For a distribution $\mathbb{Q}$ over
$\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$, the Gibbs risk is the
expectation

$\small\mathbf{R}_{\mathbb{D}}(\mathbb{Q})\operatorname*{\
\overset{\mathrm{def}}{=}\ }\mathbf{E}[\mathbf{R}_{\mathbb{D}}(H)];\qquad
H\sim\mathbb{Q}.$ (2)

For neural networks, a common stochastic formulation is to sample weights from
the distribution $\mathbb{Q}$ before inference – e.g., the Bayesian neural
networks of Blundell et al. [2015].

Throughout this paper, we assume a source distribution $\mathbb{S}$ over
$\mathcal{X}\times\mathcal{Y}$ and a target distribution $\mathbb{T}$ over
$\mathcal{X}\times\mathcal{Y}$. We assume observation of an i.i.d. random
sample $S\sim\mathbb{S}^{n}$ and an i.i.d. random sample
$T_{X}\sim\mathbb{T}_{X}^{m}$ where the subscript $X$ denotes the
$\mathcal{X}$-marginal of a distribution. In this context, an algorithm for
the unsupervised adaptation problem we study is a function $(S,T_{X})\mapsto
h\in\mathcal{H}$. We are interested in bounds on $\mathbf{R}_{\mathbb{T}}(h)$
for such algorithms.

Interchangeably, we think of the sample $S$ as both a random variable with
distribution $\mathbb{S}^{n}$ and a (random) distribution itself, since any
observation of a sample $S$ uniquely defines its own empirical distribution
over $\mathcal{X}\times\mathcal{Y}$ by the pmf

$\small(x,y)\mapsto
n^{-1}\sum\nolimits_{i=1}^{n}\mathbf{1}_{\\{(x_{i},y_{i})\\}}\\{(x,y)\\}$ (3)

where $\mathbf{1}$ is the indicator function. So, $\mathbf{R}_{S}$ is well-
defined by this identification.
$\mathbf{R}_{S}(\mathbb{Q})=\mathbf{E}_{H\sim\mathbb{Q}}[\mathbf{R}_{S}(H)]$
is also defined – the observation of $S$ is used, not integrated out.

Finally, we also use distribution divergences based on the
$\mathcal{H}$-divergence proposed by Ben-David et al. [2007b]. This divergence
is a specification of the $\mathcal{A}$-distance [Kifer et al., 2004] which
relaxes the total variation distance by considering only a subset
$\mathcal{A}$ of measurable sets when taking the supremum. In particular, the
$\mathcal{H}$-divergence considers sets identifiable by a class
$\mathcal{H}\subseteq\\{0,1\\}^{\mathcal{X}}$

$\small\mathbf{d}_{\mathcal{H}}(\mathbb{D}_{1},\mathbb{D}_{2})\operatorname*{\
\overset{\mathrm{def}}{=}\
}\sup\nolimits_{h\in\mathcal{H}}\big{\lvert}\mathbf{E}[h(X_{1})]-\mathbf{E}[h(X_{2})]\big{\rvert}$
(4)

where $X_{i}\sim\mathbb{D}_{i}$. While it is typically defined with a factor
of 2, we omit this for convenience. Given a class
$\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$, we first study the
$\mathcal{H}\Delta\mathcal{H}$-divergence based on the class

$\small\begin{split}\mathcal{H}\Delta\mathcal{H}&\operatorname*{\
\overset{\mathrm{def}}{=}\ }\big{\\{}x\mapsto
1-\mathbf{1}_{\\{h(x)\\}}\\{h^{\prime}(x)\\}\mid(h,h^{\prime})\in\mathcal{H}^{2}\big{\\}}.\end{split}$
(5)

This is a multiclass generalization, which simplifies to the original binary
definition of Ben-David et al. when $|\mathcal{Y}|=2$.

###  2.2 Some Existing Adaptation Bounds

In this section, we discuss two adaptation bounds. More detailed knowledge of
these bounds will be useful later for comparison with our proposed bounds.
First, we discuss the seminal uniform convergence bound proposed by Ben-David
et al. [2007b, 2010b]. Second, we discuss a PAC-Bayesian bound proposed by
Germain et al. [2020b].

####  2.2.1 Adaptation Based on Uniform Convergence

######  Theorem 1.

[Ben-David et al., 2010b] Let $\mathcal{Y}$ be binary. For all $\delta>0$,
w.p. at least $1-\delta$, for all $h\in\mathcal{H}$

$\small\begin{split}&\mathbf{R}_{\mathbb{T}}(h)\leq\lambda+\mathbf{R}_{S}(h)+\mathbf{d}_{\mathcal{H}\Delta\mathcal{H}}(S_{X},T_{X})\\\
&+4\sqrt{\tfrac{4\nu\ln(2m)-\ln(\delta/4)}{m}}+2\sqrt{\tfrac{8\nu\ln(em/\nu)-2\ln(\delta/4)}{m}}\end{split}$
(6)

where
$\lambda=\min_{\eta\in\mathcal{H}}\mathbf{R}_{\mathbb{S}}(\eta)+\mathbf{R}_{\mathbb{T}}(\eta)$
and $\nu=\mathrm{VCDim}(\mathcal{H})$.

The seminal result above is the standard adaptation bound on which many newer
results are based. Still, this uniform convergence bound is not well-suited
for every application. We discuss some limitations below.

##### Uniform Sample Complexity

Simply put, uniform convergence is too conservative: it assigns the same
sample complexity to each outcome of our learning algorithm, regardless of the
solution quality. As discussed in Section 1, this prevents us from studying
important properties of a model as a function of its sample complexity.

##### Model-Independent Divergence

In general, divergence is meant to characterize the similarity in feature
distributions under the source $\mathbb{S}$ and the target $\mathbb{T}$.
Similar to above, independence of the divergence
$\mathbf{d}_{\mathcal{H}\Delta\mathcal{H}}$ and the model $h$ is overly
conservative and makes this term insensitive to changes in the outcome of our
learning algorithm. For example, when $\mathcal{H}$ is fixed, this divergence
cannot distinguish between a random initialization and a carefully trained
solution.

##### Sample-Independent Adaptability

The term $\lambda$ is often called the adaptability. It is a measure of
similarity in the labeling functions of $\mathbb{S}$ and $\mathbb{T}$,
characterizing the extent to which one hypothesis in $\mathcal{H}$ can do well
on both of these distributions. When no such hypothesis exists, it is unclear
how a learner could successfully adapt by minimizing risk on the source
distribution [Ben-David et al., 2010b]. Importantly, this term has been
central to the theoretical discussion of failure-cases in widely used DA
algorithms [Johansson et al., 2019b, Zhao et al., 2019b]. Meanwhile,
estimation of $\lambda$ remains an under-studied research area [Redko et al.,
2020b]. One problem, which we observe, is independence of $\lambda$ from the
samples $S$ and $T$. In particular, one cannot directly compute the population
statistic $\lambda$ in typical circumstances. Instead, one might estimate
using $\min_{\eta}\mathbf{R}_{S}(\eta)+\mathbf{R}_{T}(\eta)$, but this
requires verifying generalization of a learned model
$h^{*}\in\operatorname*{arg\,min}_{\eta}\mathbf{R}_{S}(\eta)+\mathbf{R}_{T}(\eta)$
using a holdout set or some other descriptor of generalization performance
(e.g., such as a learning bound). This is undesirable when, as in this paper,
we wish to study adaptability in an empirical context. As we show in later
experiments (Section 4), the extra generalization requirement typically
inflates our estimation of $\lambda$, and subsequently, mars the results we
would like to interpret.

##### Binary Label Space

It is also important to note that this bound was designed for binary learners.
Computation of the $\mathcal{H}\Delta\mathcal{H}$-divergence is the most
concerning issue, since existing algorithms for computation rely on symmetry
of $\mathcal{H}$ and ERM over the class $\mathcal{H}\Delta\mathcal{H}$. In
Section 3.2, we discuss these issues in detail and present some solutions.

####  2.2.2 A PAC-Bayesian Bound for Binary Learners

We give Thm. 7 in Appendix A.2, which is one of the first PAC-Bayesian
adaptation bounds. While Germain et al. [2013, 2016, 2020b] propose other
bounds, we focus on Thm. 7 because it is easiest to compare to the proposal of
Ben-David et al. [2010b]. While tailored to Thm. 7, the weaknesses discussed
below are generally applicable to other bounds of Germain et al.

##### Benefits Compared to Thm. 1

One benefit of Thm. 7 is that the divergence employed in this bound is model-
dependent (rather than independent); namely, it depends on the Gibbs predictor
$\mathbb{Q}$, whose target error we bound. As mentioned, model-independence is
an overly conservative quality and Germain et al. [2020b] show this formally
by proving their divergence actually lowerbounds
$\mathbf{d}_{\mathcal{H}\Delta\mathcal{H}}$ for all $\mathbb{Q}$ and
$\mathcal{H}$. Another primary benefit is that Thm. 7 employs a non-uniform
sample complexity. Specifically, complexity is measured through a KL-
divergence $\mathrm{KL}(\mathbb{Q}\mid\mid\mathbb{P})$, which explicitly
depends on the outcome of the learning algorithm $\mathbb{Q}$. Simply put, a
model is complex if it deviates much from our prior knowledge, which is
captured in the prior $\mathbb{P}$.

##### Weaknesses Shared with Thm. 1

Despite its benefits over Thm. 1, Thm. 7 also shares some weaknesses. First,
the proposed adaptability term is also sample-independent. Second, the bound
is still designed for a binary label space $\mathcal{Y}$. Unlike the case of
Thm. 1, it is not computation of the bound that causes concern, but the
validity of the bound in mutliclass settings. In particular, the problem
arises because the proof of Thm. 7 relies on a decomposition of the risk which
assumes $|\mathcal{Y}|=2$. This decomposition does not hold, in general, when
$\mathcal{Y}$ is larger. In fact, Germain et al. [2020b], themselves, observe
Thm. 7 is not easily extended to multiclass settings, leaving the
investigation of such PAC-Bayes bounds as an open problem. For some additional
empirical study of Thm. 7, see Appendix D.3.

###  2.3 Other Related Works

Besides those works discussed above, there are some additional works, which
propose alternate theories of adaptation. Some theories of adaptation use
distinct integral probability metrics in place of the $\mathcal{H}$-divergence
[Redko et al., 2017b, Shen et al., 2018b, Johansson et al., 2019b], while
others have sought to generalize and modify the $\mathcal{H}$-divergence
[Mansour et al., 2009b, Kuroki et al., 2019b, Zhang et al., 2019b]. Meanwhile,
others focus on assumptions distinct from small adaptability. These include
covariate shift [Sugiyama et al., 2007b, You et al., 2019b], label shift
[Lipton et al., 2018b] and generalized label shift [Tachet des Combes et al.,
2020b]. The DA problem can also be modeled through causal graphs [Zhang et
al., 2015b, Magliacane et al., 2018b] and some extensions to DA consider a
meta-distribution over targets [Blanchard et al., 2021b, Albuquerque et al.,
2020a, Deng et al., 2020b]. Notably, most assumptions are untestable in
practice and not many works consider such testing, even in controlled research
settings where it might be possible. As we are aware, we are the first to use
a sample-dependent adaptability, which improves estimation in empirical study.

In adaptation, PAC-Bayesian results are almost exclusively due to Germain et
al. [2013, 2016, 2020b]. Albeit, in transfer learning some work does exist [Li
and Bilmes, 2007b, McNamara and Balcan, 2017b]. Most directly, our work
employs the PAC-Bayes bound of Maurer [2004b] in proofs as well as some
techniques of Langford and Caruana [2001], Dziugaite and Roy [2017b], and
Pérez-Ortiz et al. [2021b] in empirical study. Most notably, ours is the only
PAC-Bayesian work to propose multiclass adaptation bounds. A more in depth
coverage of relevant literature – for adaptation and PAC-Bayes – is available
in Appendix B.

##  3 Proposed Bounds

In this section, we give the proposed adaptation bounds for multiclass
learners. We also provide novel algorithms for computing two multiclass
divergence terms and compare these to existing approaches. Lastly, we give a
second adaptation bound which removes the need for inefficient Monte-Carlo
estimation of divergences dependent on a Gibbs predictor. Proof of all results
is given in Appendix A.

###  3.1 A PAC-Bayesian Adaptation Bound for Multiclass Learners

We begin by introducing a model-dependent class of hypotheses similar to
$\mathcal{H}\Delta\mathcal{H}$. Precisely, for $h\in\mathcal{H}$,

$\small h\Delta\mathcal{H}\operatorname*{\ \overset{\mathrm{def}}{=}\
}\big{\\{}x\mapsto 1-\mathbf{1}_{\\{h(x)\\}}\\{h^{\prime}(x)\\}\mid
h^{\prime}\in\mathcal{H}\big{\\}}.$ (7)

With it, we propose to use the $h\Delta\mathcal{H}$-divergence
$\mathbf{d}_{h\Delta\mathcal{H}}$ in our adaptation bounds. This divergence is
a model-dependent extension of the $\mathcal{H}\Delta\mathcal{H}$-divergence,
applicable in multiclass settings. It is easy to observe from the definitions
that this new divergence lowerbounds the
$\mathcal{H}\Delta\mathcal{H}$-divergence for all $\mathcal{H}$ and all $h$.
Both Zhang et al. [2019b] and Kuroki et al. [2019b] study similar divergences
for bounding 01-loss in the binary case, but we are first to use this
divergence with non-uniform sample complexity, and also, the first to use this
divergence in an adaptation bound for multiclass learners.111We discuss a
multiclass proposal of Zhang et al. [2019b] later, but it is based on margin
loss and used for uniform convergence. Our full proposal requires novel
technique and theoretical study to compute this divergence (see Section 3.2).

Next, we give the proposed adaptation bound. As alluded, the bound has a
number of notable features and we expand on these in comparison to Thms. 1 and
7 after its statement.

######  Theorem 2.

For any $\mathbb{P}$ over $\mathcal{H}$, all $\delta>0$, w.p. at least
$1-\delta$, for all $\mathbb{Q}$ over $\mathcal{H}$

$\small\begin{split}\mathbf{R}_{\mathbb{T}}(\mathbb{Q})&\leq\tilde{\lambda}_{S,T}+\mathbf{R}_{S}(\mathbb{Q})+\mathbf{E}_{H\sim\mathbb{Q}}[\mathbf{d}_{\mathcal{C}_{H}}(S_{X},T_{X})]\\\
&+\sqrt{\tfrac{\mathrm{KL}(\mathbb{Q}\mid\mid\mathbb{P})+\ln\sqrt{4m}-\ln(\delta)}{2m}}\end{split}$
(8)

where
$\tilde{\lambda}_{S,T}=\min_{\eta\in\mathcal{H}}\mathbf{R}_{S}(\eta)+\mathbf{R}_{T}(\eta)$
and we may choose either $\mathcal{C}_{h}=\mathcal{H}\Delta\mathcal{H}$ for
all $h$ as before or $\mathcal{C}_{h}=h\Delta\mathcal{H}$.

##### Comparison to Thms. 1 and 7

By design, the bound proposed above resolves the weaknesses mentioned in
Section 2.2. First and foremost, we remove the requirement that $\mathcal{Y}$
is binary. Second, we use a non-uniform notion of sample complexity; i.e.,
$\mathrm{KL}(\mathbb{Q}\mid\mid\mathbb{P})$. Third, Thm. 2 allows for either a
model-dependent or model-independent notion of data-distribution divergence.
While model-independent divergences do have some weaknesses, we retain them in
our bound since, as discussed later, they can be more efficient. Lastly, Thm.
2 employs a sample-dependent notion of adaptability. Compared to $\lambda$,
the new adaptability $\tilde{\lambda}_{S,T}$ is the smallest error achievable
on the samples. In research contexts wherein we assume access to target labels
for purpose of studying our assumptions, we later show that this quantity is
fairly easy to empirically bound.

###  3.2 Approximating Multiclass Divergence

####  3.2.1 The Multiclass $\mathcal{H}\Delta\mathcal{H}$-divergence

First, since the $\mathcal{H}\Delta\mathcal{H}$-divergence is model-
independent, the expectation with respect to the Gibbs predictor $\mathbb{Q}$
simplifies significantly. In particular, if
$\mathcal{C}_{h}=\mathcal{H}\Delta\mathcal{H}$, we have

$\small\mathbf{E}_{H\sim\mathbb{Q}}[\mathbf{d}_{\mathcal{C}_{H}}(S_{X},T_{X})]=\mathbf{d}_{\mathcal{H}\Delta\mathcal{H}}(S_{X},T_{X}).$
(9)

Thus, computation of this divergence simplifies to computing the
$\mathcal{H}\Delta\mathcal{H}$-divergence for multiclass learners.

##### Summary of Approach

In general, we take inspiration from the proposal of Ben-David et al. [2010b]
who compute $\mathcal{H}\Delta\mathcal{H}$-divergence when models in
$\mathcal{H}$ have binary output. Namely, we frame computation as minimization
of error in a specific classification problem. To adapt this strategy to the
multiclass setting, we do two primary things. First, we remove the assumption
that $\mathcal{H}$ is symmetric. This is important for multiclass settings
since we have no reason to believe $\mathcal{H}\Delta\mathcal{H}$ is typically
symmetric. We replace the symmetry in $\mathcal{H}\Delta\mathcal{H}$ with a
symmetry in our classification problems. Second, for score-based classifiers
such as neural networks, we give an optimization procedure for approximating
ERM over this class based on a surrogate loss function. As we are aware, this
is the first algorithm for approximating ERM over
$\mathcal{H}\Delta\mathcal{H}$ when models in $\mathcal{H}$ have multiclass
output.

##### Reduction to ERM

######  Theorem 3.

Let $\mathcal{C}=\mathcal{H}\Delta\mathcal{H}$. Almost surely,

$\small\mathbf{d}_{\mathcal{C}}(S_{X},T_{X})=\max\begin{rcases}\begin{dcases}1-\min_{\varphi\in\mathcal{C}}\mathbf{R}_{P}(\varphi)+\mathbf{R}_{Q}(\varphi),\\\
1-\min_{\varphi\in\mathcal{C}}\mathbf{R}_{U}(\varphi)+\mathbf{R}_{V}(\varphi)\end{dcases}\end{rcases}$
(10)

where

$\small\begin{split}P&=\big{(}(X_{i},1)\mid X_{i}\in S_{X}\big{)},\
Q=\big{(}(\tilde{X}_{i},0)\mid\tilde{X}_{i}\in T_{X}\big{)},\\\
U&=\big{(}(X_{i},0)\mid X_{i}\in S_{X}\big{)},\
V=\big{(}(\tilde{X}_{i},1)\mid\tilde{X}_{i}\in T_{X}\big{)}.\end{split}$ (11)

Notice, pooled samples $P+_{\mathrm{c}}Q$ and $U+_{\mathrm{c}}V$ define binary
classification problems ($+_{\mathrm{c}}$ is concatenation). Namely, they
represent an identification problem wherein the learner must distinguish
between the samples $S_{X}$ and $T_{X}$. To compute divergence as above, we
need only select $\varphi$ to minimize the sum of class-conditional error
rates for these problems. Even in simple cases, risk-minimization can be
computationally hard [Shalev-Shwartz and Ben-David, 2014b]. Thus, we instead
select $\varphi$ by optimizing a surrogate loss.

##### Approximate Minimization via Surrogate

WLOG, $\mathcal{Y}=\\{1,\ldots,C\\}$. We consider a score-based class
$\mathcal{S}$ written

$\small\mathcal{S}\operatorname*{\ \overset{\mathrm{def}}{=}\
}\big{\\{}\Psi_{\mathbf{f}}\mid\mathbf{f}\in\mathcal{F}\big{\\}};\quad\Psi_{\mathbf{f}}(x)\operatorname*{\
\overset{\mathrm{def}}{=}\
}\operatorname*{arg\,max}\nolimits_{\ell\in[C]}\mathbf{f}_{\ell}(x)$ (12)

with
$\mathcal{F}\subseteq\\{\mathbf{f}\mid\mathbf{f}_{\ell}:\mathcal{X}\to\mathbb{R},\
\ell\in[C]\\}$ a class of scoring-functions. In case of ties, suppose
$\operatorname*{arg\,max}$ returns the least label. Using the naïve definition
in Eq. (5),

$\small\mathcal{S}\Delta\mathcal{S}\operatorname*{\ \overset{\mathrm{def}}{=}\
}\big{\\{}x\mapsto
1-\mathbf{1}_{\\{\Psi_{\mathbf{f}}(x)\\}}\\{\Psi_{\mathbf{g}}(x)\\}\mid(\mathbf{f},\mathbf{g})\in\mathcal{F}^{2}\big{\\}}.$
(13)

At first glance, it is unclear how to pick
$\varphi\in\mathcal{S}\Delta\mathcal{S}$ to minimize error on a given dataset.
So, in place of this obscure definition, the following result gives a
surrogate loss which upperbounds the 01-loss on the original problem. Thus, we
indirectly reduce the error by minimizing the surrogate.

######  Theorem 4.

Suppose $\tau:\mathbb{R}\to\mathbb{R}_{\geq 0}$ is differentiable and monotone
increasing. Let
$\mathbf{A}=\big{(}\tau\circ\mathbf{g}(x)\big{)}\cdot\big{(}\tau\circ\mathbf{f}(x)^{\mathrm{T}}\big{)}$
with $\tau$ applied element-wise and $\mathbf{f},\mathbf{g}\in\mathcal{F}$.
Set

$\small\begin{split}z(x)&\operatorname*{\ \overset{\mathrm{def}}{=}\
}\max\nolimits_{(j,k)\in[C]^{2}}\mathbf{A}_{jk}-\max\nolimits_{i\in[C]}\mathbf{A}_{ii},\\\
\mathcal{L}(z,y)&\operatorname*{\ \overset{\mathrm{def}}{=}\
}\ln(1+\exp(-(2y-1)\cdot z))/\ln(2).\end{split}$ (14)

Then, if
$\varphi(x)=1-\mathbf{1}_{\\{\Psi_{\mathbf{f}}(x)\\}}\\{\Psi_{\mathbf{g}}(x)\\}$,
we have

$\small\mathbf{R}_{\mathbb{D}}(\varphi)\leq\mathbf{E}_{(X,Y)\sim\mathbb{D}}\
\mathcal{L}(z(X),Y)$ (15)

for any distribution $\mathbb{D}$ s.t. $\mathbf{f}(X)$ has no repeated scores
and $\mathbf{g}(X)$ has no repeated scores, almost surely.222This stipulation
on $\mathbb{D}$ is not too strict. It only assumes ties in the scores of
$\mathbf{f}$ or $\mathbf{g}$ are very unlikely, so these ties can be ignored.

We point out the log loss $\mathcal{L}(z,y)$ is differentiable with respect to
$z$ and $z(x)$ is differentiable with respect to $\mathbf{f}$ and
$\mathbf{g}$. In practice, functions in $\mathcal{F}$ – such as $\mathbf{f}$
and $\mathbf{g}$ – are typically differentiable with respect to a real-
parameter vector, which also defines the function. For example, this is
precisely the case for neural networks. In these contexts, since composition
preserves differentiability, the output of the surrogate $\mathcal{L}$ is
differentiable with respect to the real-parameter vector. So, the RHS of Eq.
(15) may be approximately minimized using batch SGD. At this point, the
proposed algorithm should be familiar to the typical practitioner. It is
equivalent to the manner in which we usually optimize a neural network, except
for the new surrogate $(\mathbf{f},\mathbf{g},x,y)\mapsto\mathcal{L}(z(x),y)$.

####  3.2.2 The Multiclass $h\Delta\mathcal{H}$-divergence

When $\mathcal{C}_{h}=h\Delta\mathcal{H}$ the divergence term is model-
dependent and the expectation with respect to the Gibbs predictor $\mathbb{Q}$
becomes a challenge. For neural networks, even the Gibbs risk
$\mathbf{R}_{S}(\mathbb{Q})$ does not have a known analytic solution. Instead,
it is common to approximate using Monte-Carlo sampling [Langford and Caruana,
2001, Dziugaite and Roy, 2017b, Dziugaite et al., 2021b, Pérez-Ortiz et al.,
2021b]. By Hoeffding’s Inequality, w.p. at least $1-\delta$, we approximate

$\small\underset{H\sim\mathbb{Q}}{\mathbf{E}}[\mathbf{d}_{\mathcal{C}_{H}}(S_{X},T_{X})]\leq\frac{1}{k}\sum_{i=1}^{k}\mathbf{d}_{\mathcal{C}_{H_{i}}}(S_{X},T_{X})+\sqrt{\tfrac{\ln
2/\delta}{2k}}$ (16)

where $(H_{i})_{i=1}^{k}\sim\mathbb{Q}^{k}$. Using the RHS as an
approximation, our computation reduces to computing
$\mathbf{d}_{\mathcal{C}_{h}}$ for any deterministic $h\in\mathcal{H}$. Upon
sampling from $\mathbb{Q}$, we can apply the algorithm for computing
$\mathbf{d}_{\mathcal{C}_{h}}$ to each point in the sample. In light of this,
the next part focuses on computing $\mathbf{d}_{\mathcal{C}_{h}}$ for
deterministic $h$. We proceed as before, reducing computation to risk-
minimization for a specific classification problem.

Reduction to ERM with Constrained Labeling Function

######  Theorem 5.

Almost surely, for all $h\in\mathcal{H}$

$\small\mathbf{d}_{\mathcal{C}_{h}}(S_{X},T_{X})=\max\begin{rcases}\begin{dcases}1-\underset{\bar{h}\in\Upsilon}{\min_{\varphi\in\mathcal{H},}}\mathbf{R}_{P}(\varphi)+\mathbf{R}_{Q}(\varphi),\\\
1-\underset{\bar{h}\in\Upsilon}{\min_{\varphi\in\mathcal{H},}}\mathbf{R}_{U}(\varphi)+\mathbf{R}_{V}(\varphi)\end{dcases}\end{rcases}$
(17)

where $\mathcal{C}_{h}=h\Delta\mathcal{H}$ and

$\small\begin{split}P({\bar{h}})&=\big{(}(X_{i},\bar{h}(X_{i}))\mid X_{i}\in
S_{X}\big{)},\\\
Q&=\big{(}(\tilde{X}_{i},h(\tilde{X}_{i}))\mid\tilde{X}_{i}\in
T_{X}\big{)},\\\ U&=\big{(}(X_{i},h(X_{i}))\mid X_{i}\in S_{X}\big{)},\\\
V({\bar{h}})&=\big{(}(\tilde{X}_{i},\bar{h}(\tilde{X}_{i}))\mid\tilde{X}_{i}\in
T_{X}\big{)}\end{split}$ (18)

and $\Upsilon=\\{\bar{h}\in\mathcal{Y}^{\mathcal{X}}\mid\bar{h}(x)\neq h(x),\
\forall x\in\mathcal{X}\\}$.

As before, the result describes two classification problems. This time, the
learner’s goal is to agree with $h$ on one sample, while disagreeing with $h$
(in the way specified by $\bar{h}$) on the other sample. We minimize the
class-conditional error rates by selecting from the class $\mathcal{H}$ used
for the original prediction task, rather than $\mathcal{H}\Delta\mathcal{H}$.
So, we make the obvious proposal: re-use whichever approximation technique we
used to select $h$ in the first place. In our experiments, since $\mathcal{H}$
is a space of neural networks, we use batch SGD on an NLL loss.

##### A Heuristic for Selecting from $\Upsilon$

Reduction to ERM in the multiclass setting also requires specification of
$\bar{h}\in\Upsilon$. Specifically, $\bar{h}$ should aid in minimizing the
class-conditional error rates. In our experiments, we found a simple strategy
to be fairly effective. Namely, we specify $\bar{h}$ by always picking the
label with the second-highest confidence according to $h$. So, $\bar{h}$
disagrees with $h$ on all of $\mathcal{X}$, but does so in the “most
reasonable” way according to the probabilities output by $h$. This approach
uses the probabilities output by $h$ to rank similarity of labeling functions
and supposes the most “similiar” labeling function in $\Upsilon$ will be
easiest for another hypothesis in $\mathcal{H}$ to simultaneously learn.
Mathematically, our solution satisfies

$\small\bar{h}\in\operatorname*{arg\,max}\nolimits_{\upsilon\in\Upsilon}\sum\nolimits_{x\in\mathcal{X}}h_{\upsilon(x)}(x)$
(19)

where $h_{\ell}(x)$ is the score assigned to the label $\ell$. This heuristic
is a practical solution that avoids search over $\Upsilon$, which will
typically be unknown, unless we inefficiently enumerate using membership
constraints. As we are aware, there is no known algorithm to efficiently
select minimizers from $\Upsilon$ and $\mathcal{H}$, simultaneously, as called
for by Thm. 5. Besides the heuristic, we leave this problem as future work.

##### Comparison to Some Related Approaches

Considering a binary label space $\mathcal{Y}$, Kuroki et al. [2019b] propose
a similar algorithm. The multiclass setting we consider does require some
differences, primarily, related to the distinct degrees of freedom in
multiclass and binary classification. First, our proposal removes the
requirement that $\mathcal{\mathcal{H}}$ is symmetric since, as we are aware,
this concept is not well-defined for hypotheses with multiclass output.
Similar to before, we replace the symmetry required of $\mathcal{H}$ with
symmetry in our classification problems. Second, in multiclass settings, the
reduction strategy necessitates a new parameter to optimize: the labeling
function $\bar{h}$. Besides our proposed heuristic for optimization, proof of
this fact is not a straightforward extension of the work of Kuroki et al.
[2019b]. In fact, it requires a different proof-technique (see Appendix A.6).
In a multiclass setting, Zhang et al. [2019b] also propose an approach for
approximating a mutliclass divergence. In general, our two techniques require
different consideration because their divergence is based on a margin loss,
rather than 01-loss. Notably, the multiclass bounds of Zhang et al. [2019b]
use uniform sample complexity, unlike our proposed non-uniform approach.
Further, working directly with 01-loss, as we do, avoids any loosening of the
bound via the margin penalty.

###  3.3 Efficiency Through Flat-Minima

In full view of Section 3.2.2, the reader may rightfully be concerned about
the efficiency of the proposed technique for approximating
$\mathbf{E}_{H}[\mathbf{d}_{\mathcal{C}_{H}}(\cdot,\cdot)]$. In particular,
the suggestion requires training $k$ distinct neural networks: one for each
$H_{i}\sim\mathbb{Q}$. Typically, $k$ will be large – e.g., larger than 100 –
to control the size of the upperbound in Eq. (16), so this is not
computationally feasible for practical applications. This problem is not
totally unique to the model-dependent $h\Delta\mathcal{H}$-divergence, either.
Common invariant feature-learning algorithms – e.g., DANN [Ganin and
Lempitsky, 2015b] – actually modify the feature distribution over which the
classifier learns. In these cases, even the
$\mathcal{H}\Delta\mathcal{H}$-divergence becomes dependent on the model
[Johansson et al., 2019b]. In particular, supposing every model
$h\in\mathcal{H}$ is the composition $c_{h}\circ f_{h}$ of a classifier
$c_{h}$ and a feature extractor $f_{h}$, the modified
$\mathcal{H}\Delta\mathcal{H}$-divergence results from the following
restriction

$\small[\mathcal{H}\Delta\mathcal{H}]_{h}\operatorname*{\
\overset{\mathrm{def}}{=}\ }\\{1-\mathbf{1}_{\\{c_{p}\circ
f_{h}(\cdot)\\}}\\{c_{q}\circ f_{h}(\cdot)\\}\mid(p,q)\in\mathcal{H}^{2}\\}.$
(20)

A similar restriction can be defined for the class $h\Delta\mathcal{H}$

$\small[h\Delta\mathcal{H}]_{h}\operatorname*{\ \overset{\mathrm{def}}{=}\
}\\{1-\mathbf{1}_{\\{c_{h}\circ f_{h}(\cdot)\\}}\\{c_{q}\circ
f_{h}(\cdot)\\}\mid q\in\mathcal{H}\\}.$ (21)

In both cases, due to the dependence on $h$, the expectation over $\mathbb{Q}$
cannot be avoided as in Section 3.2.1. To resolve this frequent issue, we
propose a new adaptation bound, which relies on an assumption related to
flatness of the 01-loss over a (weighted) region in parameter space defined by
$\mathbb{Q}$. Flatness assumptions are not unusual in PAC-Bayes and we develop
this connection next.

####  3.3.1 Flat-Minima and PAC-Bayes

An SGD solution lies in a flat-minimum if its parameters are robust to
perturbation: changing the parameters (slightly) does not change the trained
network’s already low error rate. To put it another way, all parameter
configurations near the SGD solution have identically low error. So, flatness
here is an absence of “elevation” in error as our model moves about some
region of parameter space. Hochreiter and Schmidhuber [1997] first discussed
“flatness” as it relates to neural network generalization, hypothesizing that
models lying in a large flat-minimum generalize well. More recently, the idea
has been validated empirically at large scale. In particular, notions of the
sharpness of minima are often good empirical descriptors of an SGD-trained
neural network’s generalization performance [Jiang et al., 2019, Dziugaite et
al., 2020]. The motivation for using PAC-Bayes bounds is very often based on
the hypothesis that flat-minima generalize well. This is because PAC-Bayes
bounds implicitly encode the existence of flat-minima [Neyshabur et al., 2017,
Dziugaite and Roy, 2017b]. In details, for a bound to be small for some
predictor $\mathbb{Q}$, both its Gibbs risk and its KL-divergence with the
prior $\mathbb{P}$ must be small. Because the prior $\mathbb{P}$ typically has
some variance, we know $\mathbb{Q}$ should have variance too, or else the KL-
divergence will be large. Further, the variance of $\mathbb{Q}$ ensures a
region of non-zero probability away from the mean. Thus, if the Gibbs risk is
also small, it is required that models in this region away from the mean all
have identically low error (i.e., form a flat-minimum). Otherwise, the Gibbs
risk would be inflated by probable parameter configurations with high error as
illustrated in Figure 1. In this sense, PAC-Bayes bounds and flat-minima go
hand-in-hand. If the former is small, we know the latter exists.333This
argument fails for some pathological cases. It works best with unimodal
continuous $\mathbb{Q}$; e.g., the Gaussians used in Section 4.

Figure 1: Informal illustration of flat-minimum (right) and sharp-minimum
(left). For “flat” regions in parameter space, a unimodal Gibbs predictor
$\mathbb{Q}$ with some variance has consistently low error across probable
samples from $\mathbb{Q}$. Otherwise, when a region is “sharp”, there is non-
negligible likelihood of sampling a hypothesis from $\mathbb{Q}$ with high
error. The expected error over $\mathbb{Q}$ is thus inflated by these likely
regions of high error.

####  3.3.2 A More Efficient Adaptation Bound

######  Definition 1.

Let $\mathfrak{D}(\mathcal{H})$ be the space of distributions over
$\mathcal{H}$ and fix a function
$\mu:\mathfrak{D}(\mathcal{H})\to\mathcal{H}$. The Gibbs predictor
$\mathbb{Q}$ is $\rho$-flat on the distribution $\mathbb{D}$ if
$\lvert\mathbf{R}_{\mathbb{D}}(\mathbb{Q})-\mathbf{R}_{\mathbb{D}}(\mu(\mathbb{Q}))\rvert\leq\rho.$

We call the function $\mu:\mathfrak{D}(\mathcal{H})\to\mathcal{H}$ a summary
function and call the image of $\mu$ a summary. When $\mathbb{Q}$ is implied,
we typically abuse notation by writing $\mu=\mu(\mathbb{Q})$. Often, as in the
definition above, we will refer to the “flatness” of a Gibbs predictor
$\mathbb{Q}$ when it would be more precise to refer to the flatness of the
(weighted) region in parameter space that this predictor defines (i.e., a
around the summary $\mu$). In this sense, the above definition quantifies the
flatness of a region in parameter space by the ability of the error in this
region to be represented by a single hypothesis $\mu$ from that region.
Intuitively, this echoes physical properties of flatness: a topographic map
requires many more numbers to describe a mountainous terrain than a flat
prairie. That is, each change in elevation for the mountainous terrain must be
demarcated by individual numbers, while the flat prairie may only need one
number to summarize the elevation. Similarly for the region around $\mu$
defined by the predictor $\mathbb{Q}$, a region is only “flat” if the error at
$\mu$ is a good representative of the error across the whole region. Next, we
give the proposed bound.

######  Theorem 6.

For any $\mathbb{P}$ over $\mathcal{H}$, all $\delta>0$, w.p. at least
$1-\delta$, for all $\mathbb{Q}$ over $\mathcal{H}$ s.t. $\mathbb{Q}$ is
$\rho_{S}$-flat on $S$ and $\rho_{T}$-flat on $T$

$\small\begin{split}\mathbf{R}_{\mathbb{T}}(\mathbb{Q})&\leq\rho+\tilde{\lambda}_{S,T}+\mathbf{R}_{S}(\mathbb{Q})+\mathbf{d}_{\mathcal{C}_{\mu}}(S_{X},T_{X})\\\
&+\sqrt{\tfrac{\mathrm{KL}(\mathbb{Q}\mid\mid\mathbb{P})+\ln\sqrt{4m}-\ln(\delta)}{2m}}\end{split}$
(22)

where $\mu$ is the summary of $\mathbb{Q}$, $\rho=\rho_{S}+\rho_{T}$, and
$\mathcal{C}_{\mu}=\mu\Delta\mathcal{H}$.

######  Corollary 1.

To study algorithms like DANN, we can instead choose
$\mathcal{C}_{\mu}=[\mathcal{H}\Delta\mathcal{H}]_{\mu}$ or
$\mathcal{C}_{\mu}=[\mu\Delta\mathcal{H}]_{\mu}$ in Thm. 6. The adaptability
$\tilde{\lambda}_{S,T}$ is then dependent on $\mu$ as below

$\small\small\tilde{\lambda}_{S,T}^{\mu}=\min\nolimits_{g\in\mathcal{H}}\Big{\\{}\mathbf{R}_{S}(c_{g}\circ
f_{\mu})+\mathbf{R}_{T}(c_{g}\circ f_{\mu})\Big{\\}}.$ (23)

The main bound is identical to Thm. 2 except that we assume $\mathbb{Q}$ is
flat on both $S$ and $T$, then use this assumption to introduce a
deterministic summary $\mu$ in the divergence. This deterministic summary
replaces the expectation over $\mathbb{Q}$ whose estimation was inefficient,
but the new cost is inflation of the bound by $\rho$. Unfortunately, similar
to adaptability terms, we cannot expect to compute $\rho$ outside of
controlled research contexts, since labels are required to estimate the
flatness of $\mathbb{Q}$ on $T$ (according to Def. 1). Instead, for the bound
to be practically useful, we propose to assume $\rho$ is small. This, for
example, is often the suggestion when it comes to adaptability as well.
Albeit, the caveats of carelessly making assumptions on adaptation problems
should be noted [Zhao et al., 2019b, Johansson et al., 2019b].

We argue the assumption of small $\rho$ is not an overly strong (or careless)
assumption to make. To begin with, PAC-Bayes bounds and flat-minima are
already related. The only addition we make to the usual connection (see
Section 3.3.1) is that flat regions remain flat when we transfer across data
distributions (or, samples). Note, we do not even require the transferred
region to remain a minimum, since the size of $\rho$ is only dictated by the
difference in the Gibbs risk and the summary risk: the Gibbs risk can be high
on $T$ as long as the summary risk is as well. Thus, if one is willing to
accept the usual assumptions, then our additional assumption merely begs the
question: Do flat regions transfer?

In the next section, empirically, we test this question along with the other
proposals given in this text.

##  4 Experiments

Figure 2: Adaptability (left) and dependent/independent divergences (right)
for DANN on Digits. Solid line is median. Scatter describes unique
$(S,T,\mathbb{Q})$, limited to $95\%$ or more data to filter extreme values.
$\mathbb{Q}$ is a multivariate Gaussian and $\mu$ is its mean. Figure 3:
Histogram of $\rho$ estimates. Rug plot above $0.04$ displays infrequent
occurrences. Each datum describes unique $(S,T,\mathbb{Q})$. $\mathbb{Q},\mu$
are defined as in Figure 2. See Appendix C.7 for details. Figure 4: Sample-
dependent (left) and independent adaptability. Each datum is for unique
$(S,T,\mathcal{H})$. See Appendix C.5 for details.

###  4.1 Setup

##### Datasets

We use a wide-array of datasets from vision and NLP: Digits [Ganin and
Lempitsky, 2015b], PACS [Li et al., 2017b], Office-Home [Venkateswara et al.,
2017b], Amazon Reviews [Blitzer et al., 2007b], and Discourse sense
classification datasets [Prasad et al., 2008b, Ramesh and Yu, 2010b, Zeyrek et
al., 2020b]. For Digits, we use the image as feature, while for Amazon
Reviews, we use uni-gram and bi-gram features. For other datasets, we use pre-
trained ResNet-50 [He et al., 2016b] or BERT [Devlin et al., 2019b] features.

##### Models

For Digits, we use a 4-layer CNN. For all other datasets, we use both a linear
model and a 4-layer fully-connected network. For simplicity, our larger scale
experiments use a simple adaptation algorithm (SA) which optimizes models to
minimize risk on $S$. On Digits, we also study the DANN algorithm proposed by
Ganin and Lempitsky [2015b], modified to train Gibbs predictors with varied
regularization using PBB [Pérez-Ortiz et al., 2021b]. We pick Digits,
specifically, because it exhibits shift in the marginal label distributions,
which can cause DANN to fail [Zhao et al., 2019b]. More training details are
given in Appendix C.

##### Experiments

The data points in our results are each individual experiments done on a
source dataset $S$ and target dataset $T$ using a classifier $h$ or Gibbs
predictor $\mathbb{Q}$. The pair $S$ and $T$ are taken from a set of data
splits using the datasets discussed above (details in Appendix C). Across
these splits, we consider various scenarios including: single-source, multi-
source, and within-distribution adaptation (i.e., $\mathbb{S}=\mathbb{T}$)
using multiple random data splits. On Digits, we also consider natural shifts
(i.e., noise and rotation) and unnatural shifts (i.e., transfer to random
data). In general, we restrict the pair $(S,T$) to have a common label space.

###  4.2 Results

##### Sample-Dependent Adaptability

As mentioned, estimation of sample-independent adaptability (e.g., $\lambda$
in Thm. 1) requires verification of generalization. In particular, to estimate
$\lambda$ one can learn $\eta\in\mathcal{H}$ which has small sum of risks over
the observed samples $S$ and $T$. In our experiments, we do so using batch SGD
on a weighted NLL loss – a common surrogate. Because $\lambda$ is a population
statistic for $\mathbb{S}$ and $\mathbb{T}$, we cannot directly report the
errors on $S$ and $T$ – this is incorrect, like using training error as a
validation metric. Instead, we should check the performance of $\eta$ on a
heldout data subset (for example). This is the strategy we take in Figure 4,
using Hoeffding’s Inequality to produce a valid upperbound on $\lambda$.
Comparably, estimating sample-dependent adaptability is much easier. By
design, we can report error on the samples $S$ and $T$ used for training
$\eta$. Doing so, produces a valid upperbound:

$\small\forall\eta\in\mathcal{H}\ :\
\tilde{\lambda}_{S,T}\leq\mathbf{R}_{S}(\eta)+\mathbf{R}_{T}(\eta)\quad\text{(by
definition).}$ (24)

As is visible in Figure 4, this strategy for estimating $\tilde{\lambda}$ is
much more effective than the sample-independent strategy in revealing
important information. We see from the histogram of upperbounds on
$\tilde{\lambda}$ that adaptability is very often small and concentrated near
0, although this is not always the case. Comparatively, upperbounds for
$\lambda$ are spread out with notable mass at large values; we miss out on the
interpretation that adaptability very often is small (as we might like to
assume, in practice). In the rest of our discussion, all adaptability will be
sample-dependent. Note, additional experiments on adaptability are available
in Appendix D.1.

Table 1: Correlation of $h$-dependent and -independent divergence with $|\mathbf{R}_{h}(S)-\mathbf{R}_{h}(T)|$. Columns delineate data subsets. Each datum describes unique $(S,T,h)$. See Appendix C.6 for details. | All | Digi. | Disc. | PACS+OH | Amaz.
---|---|---|---|---|---
model-ind. | 0.54 | 0.15 | 0.70 | 0.41 | -0.05
model-dep. | 0.58 | 0.23 | 0.78 | 0.14 | 0.41

##### Divergence and Approximation

In Table 1, we give results for our approximation techniques applied to the
model-dependent $h\Delta\mathcal{H}$-divergence and the model-independent
$\mathcal{H}\Delta\mathcal{H}$-divergence. The models used in these
experiments are trained using SA. Since there is actually no ground-truth to
compare too, we report performance of our approximations on a ranking task.
That is, we compare our approximations to absolute difference in risks on the
source and target and compute the Spearman rank correlation. According to our
adaptation bounds, smaller divergence should predict smaller difference in
risk and larger divergence should predict larger difference in risk as in the
ranking task we study. Any effective approximation of divergence should also
mimic this behavior, allowing us to conduct an indirect evaluation. In
aggregate, we observe both divergences are capable of ranking performance
similarity on the source and target, which validates our approximations to
some extent. For reference, a recent statistic designed for shift-detection
[Rabanser et al., 2019] achieves correlation 0.29 on all data. We also observe
the model-dependent divergence typically ranks “better” than the model-
independent divergence. This, also, is to be expected according to our theory,
since the model-independent divergence does not account for variation in $h$
and should thus perform worse. Overall, the nuanced agreement of our
approximations with our theoretical expectations is suggestive that these
techniques are effective.

##### Do Flat Regions Transfer?

As noted, one stipulation of practical use for Thm. 6 is a small flatness
value $\rho$. This is not unlike the common assumption that $\lambda$ is small
and, as discussed, is related to the flat-minma hypothesis. To estimate $\rho$
and test our assumption, we select $\rho_{S}$ and $\rho_{T}$ to be the
smallest values so that Def. 1 is satisfied on $S$ and $T$ using a Monte-Carlo
estimate for the Gibbs Risk.444A penalty based on Hoeffding Inequality could
be added to this estimate to create a valid upperbound. We do not consider
this since a penalty is also added if we use the strategy in Eq. (16). We
train $\mathbb{Q}$ using a variant of SA based on the technique of Pérez-Ortiz
et al. [2021b]. Our results indicate $\rho$ is typically small as desired with
mean 0.007 and SD 0.01 across 4K+ experiments. See Figure 3 for a
visualization.

##### Analysis of Assumptions after DANN

Our results in Figure 2 show an interesting relationship between the sample
complexity of $\mathbb{Q}$ – as measured by
$\mathrm{KL}(\mathbb{Q}\mid\mid\mathbb{P})$ – and our assumption on
adaptability. Namely, we can be more confident in the assumption
$\tilde{\lambda}$ is small when the sample complexity of our solution
increases. A similar observation holds for the flatness term $\rho$ (see
Appendix D.4 Figure 8). Our analysis suggests DANN may be a data-hungry
algorithm, since solutions with properties we desire have large sample
complexity. The practical suggestion is to use large quantities of unlabeled
data when applying DANN, which is reasonable since unlabeled data can be
“cheap” to acquire.

##### Analysis of Divergence after DANN

In Figure 2, according to the (more sensitive) model-dependent divergence,
DANN reduces data-distribution divergence as it is designed to do. Still, it
does not reduce divergence to the degree one might expect and, as the sample
complexity of the solution increases, the gap between divergences – before and
after DANN – begins to wane. This is interesting because it shows reduction of
divergence and reduction of adaptability / flatness may be competing
objectives. Further, this finding echoes theoretical hypotheses in recent
literature [Zhao et al., 2019b, Wu et al., 2019, Johansson et al., 2019b],
while also revealing the role of sample complexity in this story. To meet our
assumptions when using DANN, we should use large amounts of unlabeled data and
allow an unconstrained solution, but to ensure DANN reduces distribution
divergence significantly, we should instead constrain our solution to lower
complexity (e.g., via regularization). Depending on problem context, there may
be some optimum between these extremes, but in any case, these opposing
relationships are an interesting take-away from the application of our theory.

##  5 Conclusion

In this work, we proposed the first adaptation bounds capable of studying the
non-uniform sample complexity of adaptation algorithms using multiclass neural
networks. Empirically, we validated the novel design-concepts in our
adaptation bounds and showed our approximation techniques for some multiclass
divergences were effective. In culmination, we applied our bounds to study
sample complexity of a common domain-invariant learning algorithm. Our
findings revealed unexpected relationships between sample complexity and
important properties of the algorithm we studied. Code for reproducing our
experiments is publicly available at
https://github.com/anthonysicilia/pacbayes-adaptation-UAI2022.

Besides what has been done in this work, we also identify some areas of
potential future work:

##### Assumptions and Heuristics

As with previous adaptation bounds, the nature of the adaptation problem
requires us to be imprecise in some cases. For one, we make a number of
assumptions on adaptability and flatness. Also, our divergence computation
does require some heuristics. While we study these imperfections empirically
with promising results, we anticipate both shortcomings can be improved. In
particular, restriction of scope to specific domains or hypothesis classes
should reveal exploitable problem structure.

##### Generalized Loss

While we have focused on multiclass learners in this work, a PAC-Bayesian
adaptation bound for general learners (e.g., with bounded loss functions)
remains an open-problem. Possibly, applying our strategies to the more general
framework of Mansour et al. [2009b] would be fruitful. Albeit, since
algorithms for computing divergence have traditionally been loss-specific, we
expect additional theoretical derivation to be required for each new loss.

###### Acknowledgements.

We thank the anonymous reviewers for helpful feedback. S. Hwang was supported
by Institute of Information & communications Technology Planning & Evaluation
(IITP) grant funded by the Korea government (MSIT), Artificial Intelligence
Graduate Program, Yonsei University (2020-0-01361-003), and the Yonsei
University Research Fund of 2022 (2022-22-0131).

## References

  * Albuquerque et al. [2020a] Isabela Albuquerque, João Monteiro, Tiago H Falk, and Ioannis Mitliagkas.  Adversarial target-invariant representation learning for domain generalization.  _arXiv:1911.00804_ , 2020a.
  * Albuquerque et al. [2020b] Isabela Albuquerque, João Monteiro, Tiago H Falk, and Ioannis Mitliagkas.  Adversarial target-invariant representation learning for domain generalization.  _arXiv:1911.00804_ , 2020b.
  * Ambroladze et al. [2007] Amiran Ambroladze, Emilio Parrado-Hernández, and John Shawe-Taylor.  Tighter pac-bayes bounds.  _NeurIPS_ , 19:9, 2007.
  * Ben-David et al. [2007a] Shai Ben-David, John Blitzer, Koby Crammer, Fernando Pereira, et al.  Analysis of representations for domain adaptation.  _NeurIPS_ , 19:137, 2007a.
  * Ben-David et al. [2007b] Shai Ben-David, John Blitzer, Koby Crammer, Fernando Pereira, et al.  Analysis of representations for domain adaptation.  _NeurIPS_ , 19:137, 2007b.
  * Ben-David et al. [2010a] Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan.  A theory of learning from different domains.  _Machine learning_ , 79(1):151–175, 2010a.
  * Ben-David et al. [2010b] Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan.  A theory of learning from different domains.  _Machine learning_ , 79(1):151–175, 2010b.
  * Ben-David et al. [2010c] Shai Ben-David, Tyler Lu, Teresa Luu, and Dávid Pál.  Impossibility theorems for domain adaptation.  In _AISTATS_ , pages 129–136. JMLR Workshop and Conference Proceedings, 2010c.
  * Blanchard et al. [2021a] Gilles Blanchard, Aniket Anand Deshmukh, Ürün Dogan, Gyemin Lee, and Clayton Scott.  Domain generalization by marginal transfer learning.  _JMLR_ , 22:2–1, 2021a.
  * Blanchard et al. [2021b] Gilles Blanchard, Aniket Anand Deshmukh, Ürün Dogan, Gyemin Lee, and Clayton Scott.  Domain generalization by marginal transfer learning.  _JMLR_ , 22:2–1, 2021b.
  * Blitzer et al. [2007a] John Blitzer, Mark Dredze, and Fernando Pereira.  Biographies, bollywood, boom-boxes and blenders: Domain adaptation for sentiment classification.  In _ACL_ , pages 440–447, 2007a.
  * Blitzer et al. [2007b] John Blitzer, Mark Dredze, and Fernando Pereira.  Biographies, bollywood, boom-boxes and blenders: Domain adaptation for sentiment classification.  In _ACL_ , pages 440–447, 2007b.
  * Blundell et al. [2015] Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra.  Weight uncertainty in neural network.  In _ICML_ , pages 1613–1622. PMLR, 2015.
  * Braud et al. [2017] Chloé Braud, Maximin Coavoux, and Anders Søgaard.  Cross-lingual rst discourse parsing.  _arXiv:1701.02946_ , 2017.
  * Carlson et al. [2003] Lynn Carlson, Daniel Marcu, and Mary Ellen Okurowski.  Building a discourse-tagged corpus in the framework of rhetorical structure theory.  In _Current and new directions in discourse and dialogue_ , pages 85–112. Springer, 2003.
  * Catoni [2007] Olivier Catoni.  PAC-Bayesian supervised classification: the thermodynamics of statistical learning.  _arXiv:0712.0248v1_ , 2007.
  * Crammer et al. [2007] Koby Crammer, Michael Kearns, and Jennifer Wortman.  Learning from multiple sources.  In _NeurIPS_ , pages 321–328, 2007.
  * Deng et al. [2020a] Zhun Deng, Frances Ding, Cynthia Dwork, Rachel Hong, Giovanni Parmigiani, Prasad Patil, and Pragya Sur.  Representation via representations: Domain generalization via adversarially learned invariant representations.  _arXiv:2006.11478_ , 2020a.
  * Deng et al. [2020b] Zhun Deng, Frances Ding, Cynthia Dwork, Rachel Hong, Giovanni Parmigiani, Prasad Patil, and Pragya Sur.  Representation via representations: Domain generalization via adversarially learned invariant representations.  _arXiv:2006.11478_ , 2020b.
  * Devlin et al. [2019a] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _NAACL-HLT_ , pages 4171–4186. ACL, 2019a.
  * Devlin et al. [2019b] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _NAACL-HLT_ , pages 4171–4186. ACL, 2019b.
  * Dziugaite and Roy [2017a] Gintare Karolina Dziugaite and Daniel M Roy.  Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data.  _arXiv:1703.11008_ , 2017a.
  * Dziugaite and Roy [2017b] Gintare Karolina Dziugaite and Daniel M Roy.  Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data.  _arXiv:1703.11008_ , 2017b.
  * Dziugaite et al. [2020] Gintare Karolina Dziugaite, Alexandre Drouin, Brady Neal, Nitarshan Rajkumar, Ethan Caballero, Linbo Wang, Ioannis Mitliagkas, and Daniel M Roy.  In search of robust measures of generalization.  _NeurIPS_ , 33, 2020.
  * Dziugaite et al. [2021a] Gintare Karolina Dziugaite, Kyle Hsu, Waseem Gharbieh, Gabriel Arpino, and Daniel Roy.  On the role of data in pac-bayes.  In _AISTATS_ , pages 604–612. PMLR, 2021a.
  * Dziugaite et al. [2021b] Gintare Karolina Dziugaite, Kyle Hsu, Waseem Gharbieh, Gabriel Arpino, and Daniel Roy.  On the role of data in pac-bayes.  In _AISTATS_ , pages 604–612. PMLR, 2021b.
  * Ganin and Lempitsky [2015a] Yaroslav Ganin and Victor Lempitsky.  Unsupervised domain adaptation by backpropagation.  In _ICML_ , pages 1180–1189. PMLR, 2015a.
  * Ganin and Lempitsky [2015b] Yaroslav Ganin and Victor Lempitsky.  Unsupervised domain adaptation by backpropagation.  In _ICML_ , pages 1180–1189. PMLR, 2015b.
  * Germain et al. [2009] Pascal Germain, Alexandre Lacasse, François Laviolette, and Mario Marchand.  PAC-Bayesian learning of linear classifiers.  In _ICML_ , 2009.
  * Germain et al. [2013] Pascal Germain, Amaury Habrard, François Laviolette, and Emilie Morvant.  A pac-bayesian approach for domain adaptation with specialization to linear classifiers.  In _ICML_ , pages 738–746. PMLR, 2013.
  * Germain et al. [2015] Pascal Germain, Alexandre Lacasse, Francois Laviolette, Mario March, and Jean-Francis Roy.  Risk Bounds for the Majority Vote: From a PAC-Bayesian Analysis to a Learning Algorithm.  _JMLR_ , 16:787–860, 2015.
  * Germain et al. [2016] Pascal Germain, Amaury Habrard, François Laviolette, and Emilie Morvant.  A new pac-bayesian perspective on domain adaptation.  In _ICML_ , pages 859–868. PMLR, 2016.
  * Germain et al. [2020a] Pascal Germain, Amaury Habrard, François Laviolette, and Emilie Morvant.  Pac-bayes and domain adaptation.  _Neurocomputing_ , 379:379–397, 2020a.
  * Germain et al. [2020b] Pascal Germain, Amaury Habrard, François Laviolette, and Emilie Morvant.  Pac-bayes and domain adaptation.  _Neurocomputing_ , 379:379–397, 2020b.
  * Gretton et al. [2012] Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola.  A kernel two-sample test.  _JMLR_ , 13(1):723–773, 2012.
  * Guedj [2019] Benjamin Guedj.  A primer on PAC-Bayesian learning.  _arXiv:1901.05353v3_ , 2019.
  * He et al. [2016a] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _CVPR_ , 2016a.
  * He et al. [2016b] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _CVPR_ , 2016b.
  * Hochreiter and Schmidhuber [1997] Sepp Hochreiter and Jürgen Schmidhuber.  Flat minima.  _Neural computation_ , 9(1):1–42, 1997.
  * Hull [1994] J. J. Hull.  A database for handwritten text recognition research.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 16(5):550–554, 1994.  10.1109/34.291440.
  * Jiang et al. [2019] Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio.  Fantastic generalization measures and where to find them.  In _ICLR_ , 2019.
  * Johansson et al. [2019a] Fredrik D Johansson, David Sontag, and Rajesh Ranganath.  Support and invertibility in domain-invariant representations.  In _AISTATS_ , pages 527–536. PMLR, 2019a.
  * Johansson et al. [2019b] Fredrik D Johansson, David Sontag, and Rajesh Ranganath.  Support and invertibility in domain-invariant representations.  In _AISTATS_ , pages 527–536. PMLR, 2019b.
  * Keskar et al. [2017] Nitish Shirish Keskar, Jorge Nocedal, Ping Tak Peter Tang, Dheevatsa Mudigere, and Mikhail Smelyanskiy.  On large-batch training for deep learning: Generalization gap and sharp minima.  In _ICLR 2017_ , 2017.
  * Kifer et al. [2004] Daniel Kifer, Shai Ben-David, and Johannes Gehrke.  Detecting change in data streams.  In _VLDB_ , volume 4, pages 180–191, 2004.
  * Kishimoto et al. [2020] Yudai Kishimoto, Yugo Murawaki, and Sadao Kurohashi.  Adapting BERT to implicit discourse relation classification with a focus on discourse connectives.  In _LREC_ , pages 1152–1158, Marseille, France, May 2020. European Language Resources Association.  ISBN 979-10-95546-34-4.  URL https://aclanthology.org/2020.lrec-1.145.
  * Kuroki et al. [2019a] Seiichi Kuroki, Nontawat Charoenphakdee, Han Bao, Junya Honda, Issei Sato, and Masashi Sugiyama.  Unsupervised domain adaptation based on source-guided discrepancy.  In _AAAI_ , volume 33, pages 4122–4129, 2019a.
  * Kuroki et al. [2019b] Seiichi Kuroki, Nontawat Charoenphakdee, Han Bao, Junya Honda, Issei Sato, and Masashi Sugiyama.  Unsupervised domain adaptation based on source-guided discrepancy.  In _AAAI_ , volume 33, pages 4122–4129, 2019b.
  * Langford and Caruana [2001] John Langford and Rich Caruana.  (not) bounding the true error.  _NeurIPS_ , 14, 2001.
  * Langford and Seeger [2001] John Langford and Matthias Seeger.  Bounds for averaging classifiers.  _CMU Technical Report_ , 2001.
  * LeCun and Cortes [2010] Yann LeCun and Corinna Cortes.  MNIST handwritten digit database.  _web_ , 2010.  URL http://yann.lecun.com/exdb/mnist/.
  * Li et al. [2017a] Da Li, Yongxin Yang, Yi-Zhe Song, and Timothy M Hospedales.  Deeper, broader and artier domain generalization.  In _IEEE ICCV_ , pages 5542–5550, 2017a.
  * Li et al. [2017b] Da Li, Yongxin Yang, Yi-Zhe Song, and Timothy M Hospedales.  Deeper, broader and artier domain generalization.  In _IEEE ICCV_ , pages 5542–5550, 2017b.
  * Li and Bilmes [2007a] Xiao Li and Jeff Bilmes.  A bayesian divergence prior for classiffier adaptation.  In _AISTATS_ , pages 275–282. PMLR, 2007a.
  * Li and Bilmes [2007b] Xiao Li and Jeff Bilmes.  A bayesian divergence prior for classiffier adaptation.  In _AISTATS_ , pages 275–282. PMLR, 2007b.
  * Lipton et al. [2018a] Zachary Lipton, Yu-Xiang Wang, and Alexander Smola.  Detecting and correcting for label shift with black box predictors.  In _ICML_ , pages 3122–3130. PMLR, 2018a.
  * Lipton et al. [2018b] Zachary Lipton, Yu-Xiang Wang, and Alexander Smola.  Detecting and correcting for label shift with black box predictors.  In _ICML_ , pages 3122–3130. PMLR, 2018b.
  * Long et al. [2017] Mingsheng Long, Han Zhu, Jianmin Wang, and Michael I Jordan.  Deep transfer learning with joint adaptation networks.  In _ICML_ , pages 2208–2217. PMLR, 2017.
  * Long et al. [2018] Mingsheng Long, Zhangjie Cao, Jianmin Wang, and Michael I Jordan.  Conditional adversarial domain adaptation.  In _NeurIPS_ , pages 1647–1657, 2018.
  * Magliacane et al. [2018a] Sara Magliacane, Thijs van Ommen, Tom Claassen, Stephan Bongers, Philip Versteeg, and Joris M Mooij.  Domain adaptation by using causal inference to predict invariant conditional distributions.  In _NeurIPS_ , 2018a.
  * Magliacane et al. [2018b] Sara Magliacane, Thijs van Ommen, Tom Claassen, Stephan Bongers, Philip Versteeg, and Joris M Mooij.  Domain adaptation by using causal inference to predict invariant conditional distributions.  In _NeurIPS_ , 2018b.
  * Mann and Thompson [1987] William C Mann and Sandra A Thompson.  _Rhetorical structure theory: A theory of text organization_.  University of Southern California, Information Sciences Institute Los Angeles, 1987.
  * Mansour et al. [2009a] Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh.  Domain adaptation: Learning bounds and algorithms.  _arXiv:0902.3430_ , 2009a.
  * Mansour et al. [2009b] Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh.  Domain adaptation: Learning bounds and algorithms.  _arXiv:0902.3430_ , 2009b.
  * Marcus et al. [1993] Mitchell Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz.  Building a large annotated corpus of english: The penn treebank.  _Computational Linguistics_ , 1993.
  * Maurer [2004a] Andreas Maurer.  A note on the pac bayesian theorem.  _arXiv cs/0411099_ , 2004a.
  * Maurer [2004b] Andreas Maurer.  A note on the pac bayesian theorem.  _arXiv cs/0411099_ , 2004b.
  * McAllester [2013] David McAllester.  A PAC-Bayesian tutorial with a dropout bound.  _arXiv:1307.2118v1_ , 2013.
  * McAllester [1999] David A McAllester.  Some PAC-Bayesian theorems.  _Machine Learning_ , 37:355–363, 1999.
  * McNamara and Balcan [2017a] Daniel McNamara and Maria-Florina Balcan.  Risk bounds for transferring representations with and without fine-tuning.  In _ICML_ , pages 2373–2381. PMLR, 2017a.
  * McNamara and Balcan [2017b] Daniel McNamara and Maria-Florina Balcan.  Risk bounds for transferring representations with and without fine-tuning.  In _ICML_ , pages 2373–2381. PMLR, 2017b.
  * Nagarajan and Kolter [2019] Vaishnavh Nagarajan and J Zico Kolter.  Uniform convergence may be unable to explain generalization in deep learning.  _NeurIPS_ , 32, 2019.
  * Netzer et al. [2011] Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng.  Reading digits in natural images with unsupervised feature learning.  _NeurIPS Workshop on Deep Learning and Unsupervised Feature Learning 2011_ , 2011.
  * Neyshabur [2017] Behnam Neyshabur.  Implicit regularization in deep learning.  _arXiv:1709.01953_ , 2017.
  * Neyshabur et al. [2014] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro.  In search of the real inductive bias: On the role of implicit regularization in deep learning.  _arXiv:1412.6614_ , 2014.
  * Neyshabur et al. [2017] Behnam Neyshabur, Srinadh Bhojanapalli, David Mcallester, and Nati Srebro.  Exploring generalization in deep learning.  _NeurIPS_ , 30:5947–5956, 2017.
  * Parrado-Hernández et al. [2012] Emilio Parrado-Hernández, Amiran Ambroladze, John Shawe-Taylor, and Shiliang Sun.  PAC-Bayes bounds with data dependent priors.  _JMLR_ , 13:3507–3531, 2012.
  * Pérez-Ortiz et al. [2021a] Marıa Pérez-Ortiz, Omar Rivasplata, John Shawe-Taylor, and Csaba Szepesvári.  Tighter risk certificates for neural networks.  _JMLR_ , 22, 2021a.
  * Pérez-Ortiz et al. [2021b] Marıa Pérez-Ortiz, Omar Rivasplata, John Shawe-Taylor, and Csaba Szepesvári.  Tighter risk certificates for neural networks.  _JMLR_ , 22, 2021b.
  * Prasad et al. [2008a] Rashmi Prasad, Nikhil Dinesh, Alan Lee, Eleni Miltsakaki, Livio Robaldo, Aravind K Joshi, and Bonnie L Webber.  The penn discourse treebank 2.0.  In _LREC_. Citeseer, 2008a.
  * Prasad et al. [2008b] Rashmi Prasad, Nikhil Dinesh, Alan Lee, Eleni Miltsakaki, Livio Robaldo, Aravind K Joshi, and Bonnie L Webber.  The penn discourse treebank 2.0.  In _LREC_. Citeseer, 2008b.
  * Rabanser et al. [2019] Stephan Rabanser, Stephan Günnemann, and Zachary C Lipton.  Failing loudly: an empirical study of methods for detecting dataset shift.  In _NeurIPS_ , pages 1396–1408, 2019.
  * Ramesh and Yu [2010a] Balaji Polepalli Ramesh and Hong Yu.  Identifying discourse connectives in biomedical text.  In _AMIA Annual Symposium Proceedings_ , volume 2010, page 657. American Medical Informatics Association, 2010a.
  * Ramesh and Yu [2010b] Balaji Polepalli Ramesh and Hong Yu.  Identifying discourse connectives in biomedical text.  In _AMIA Annual Symposium Proceedings_ , volume 2010, page 657. American Medical Informatics Association, 2010b.
  * Redko et al. [2017a] Ievgen Redko, Amaury Habrard, and Marc Sebban.  Theoretical analysis of domain adaptation with optimal transport.  In _ECML PKDD_ , pages 737–753. Springer, 2017a.
  * Redko et al. [2017b] Ievgen Redko, Amaury Habrard, and Marc Sebban.  Theoretical analysis of domain adaptation with optimal transport.  In _ECML PKDD_ , pages 737–753. Springer, 2017b.
  * Redko et al. [2020a] Ievgen Redko, Emilie Morvant, Amaury Habrard, Marc Sebban, and Younès Bennani.  A survey on domain adaptation theory.  _ArXiv_ , abs/2004.11829, 2020a.
  * Redko et al. [2020b] Ievgen Redko, Emilie Morvant, Amaury Habrard, Marc Sebban, and Younès Bennani.  A survey on domain adaptation theory.  _ArXiv_ , abs/2004.11829, 2020b.
  * Reimers and Gurevych [2019] Nils Reimers and Iryna Gurevych.  Sentence-bert: Sentence embeddings using siamese bert-networks.  _arXiv:1908.10084_ , 2019.
  * Shalev-Shwartz and Ben-David [2014a] Shai Shalev-Shwartz and Shai Ben-David.  _Understanding machine learning: From theory to algorithms_.  Cambridge university press, 2014a.
  * Shalev-Shwartz and Ben-David [2014b] Shai Shalev-Shwartz and Shai Ben-David.  _Understanding machine learning: From theory to algorithms_.  Cambridge university press, 2014b.
  * Shawe-Taylor and Williamson [1997] John Shawe-Taylor and Robert C Williamson.  A PAC analysis of a Bayesian estimator.  In _COLT_ , 1997.
  * Shen et al. [2018a] Jian Shen, Yanru Qu, Weinan Zhang, and Yong Yu.  Wasserstein distance guided representation learning for domain adaptation.  In _AAAI_ , 2018a.
  * Shen et al. [2018b] Jian Shen, Yanru Qu, Weinan Zhang, and Yong Yu.  Wasserstein distance guided representation learning for domain adaptation.  In _AAAI_ , 2018b.
  * Sugiyama et al. [2007a] Masashi Sugiyama, Matthias Krauledat, and Klaus-Robert Müller.  Covariate shift adaptation by importance weighted cross validation.  _JMLR_ , 8(5), 2007a.
  * Sugiyama et al. [2007b] Masashi Sugiyama, Matthias Krauledat, and Klaus-Robert Müller.  Covariate shift adaptation by importance weighted cross validation.  _JMLR_ , 8(5), 2007b.
  * Tachet des Combes et al. [2020a] Remi Tachet des Combes, Han Zhao, Yu-Xiang Wang, and Geoffrey J Gordon.  Domain adaptation with conditional distribution matching and generalized label shift.  _NeurIPS_ , 33, 2020a.
  * Tachet des Combes et al. [2020b] Remi Tachet des Combes, Han Zhao, Yu-Xiang Wang, and Geoffrey J Gordon.  Domain adaptation with conditional distribution matching and generalized label shift.  _NeurIPS_ , 33, 2020b.
  * Venkateswara et al. [2017a] Hemanth Venkateswara, Jose Eusebio, Shayok Chakraborty, and Sethuraman Panchanathan.  Deep hashing network for unsupervised domain adaptation.  In _IEEE CVPR_ , pages 5018–5027, 2017a.
  * Venkateswara et al. [2017b] Hemanth Venkateswara, Jose Eusebio, Shayok Chakraborty, and Sethuraman Panchanathan.  Deep hashing network for unsupervised domain adaptation.  In _IEEE CVPR_ , pages 5018–5027, 2017b.
  * Wu et al. [2019] Yifan Wu, Ezra Winston, Divyansh Kaushik, and Zachary Lipton.  Domain adaptation with asymmetrically-relaxed distribution alignment.  In _ICML_ , pages 6872–6881. PMLR, 2019.
  * You et al. [2019a] Kaichao You, Ximei Wang, Mingsheng Long, and Michael Jordan.  Towards accurate model selection in deep unsupervised domain adaptation.  In _ICML_ , pages 7124–7133. PMLR, 2019a.
  * You et al. [2019b] Kaichao You, Ximei Wang, Mingsheng Long, and Michael Jordan.  Towards accurate model selection in deep unsupervised domain adaptation.  In _ICML_ , pages 7124–7133. PMLR, 2019b.
  * Zeldes [2017] Amir Zeldes.  The gum corpus: Creating multilayer resources in the classroom.  _LREC_ , 51(3):581–612, 2017.
  * Zeyrek et al. [2020a] Deniz Zeyrek, Amália Mendes, Yulia Grishina, Murathan Kurfalı, Samuel Gibbon, and Maciej Ogrodniczuk.  Ted multilingual discourse bank (ted-mdb): a parallel corpus annotated in the pdtb style.  _LREC_ , 54(2):587–613, 2020a.
  * Zeyrek et al. [2020b] Deniz Zeyrek, Amália Mendes, Yulia Grishina, Murathan Kurfalı, Samuel Gibbon, and Maciej Ogrodniczuk.  Ted multilingual discourse bank (ted-mdb): a parallel corpus annotated in the pdtb style.  _LREC_ , 54(2):587–613, 2020b.
  * Zhang et al. [2017] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals.  Understanding deep learning requires rethinking generalization.  In _ICLR 2017_. OpenReview.net, 2017.
  * Zhang et al. [2015a] Kun Zhang, Mingming Gong, and Bernhard Schölkopf.  Multi-source domain adaptation: A causal view.  In _AAAI_ , 2015a.
  * Zhang et al. [2015b] Kun Zhang, Mingming Gong, and Bernhard Schölkopf.  Multi-source domain adaptation: A causal view.  In _AAAI_ , 2015b.
  * Zhang et al. [2019a] Yuchen Zhang, Tianle Liu, Mingsheng Long, and Michael Jordan.  Bridging theory and algorithm for domain adaptation.  In _ICML_ , pages 7404–7413. PMLR, 2019a.
  * Zhang et al. [2019b] Yuchen Zhang, Tianle Liu, Mingsheng Long, and Michael Jordan.  Bridging theory and algorithm for domain adaptation.  In _ICML_ , pages 7404–7413. PMLR, 2019b.
  * Zhao et al. [2019a] Han Zhao, Remi Tachet Des Combes, Kun Zhang, and Geoffrey Gordon.  On learning invariant representations for domain adaptation.  In _ICML_ , pages 7523–7532. PMLR, 2019a.
  * Zhao et al. [2019b] Han Zhao, Remi Tachet Des Combes, Kun Zhang, and Geoffrey Gordon.  On learning invariant representations for domain adaptation.  In _ICML_ , pages 7523–7532. PMLR, 2019b.
  * Zhou et al. [2020] Kaiyang Zhou, Yongxin Yang, Timothy Hospedales, and Tao Xiang.  Deep domain-adversarial image generation for domain generalisation.  _arXiv:2003.06054_ , 2020.
  * Zhou et al. [2018] Wenda Zhou, Victor Veitch, Morgane Austern, Ryan P Adams, and Peter Orbanz.  Non-vacuous generalization bounds at the imagenet scale: a pac-bayesian compression approach.  In _ICLR_ , 2018.

##  Appendix A Proofs

###  A.1 Theorem 1

###### Proof.

This is Thm. 2 of Ben-David et al. [2010a] with added bound on
$\mathbf{R}_{S}(h)-\mathbf{R}_{\mathbb{S}}(h)$ by standard uniform convergence
arguments; e.g., Ch. 28.1 of Shalev-Shwartz and Ben-David [2014a]. Boole’s
Inequality is used to combine bounds. ∎

###  A.2 Theorem 7 (Theorem 7 of Germain et al. [2020])

######  Theorem 7.

[Germain et al., 2020a] Let $\mathcal{Y}$ be binary, $\mathbb{P}$ any
distribution over $\mathcal{H}$, and $\omega>0$. For all $\delta>0$, w.p. at
least $1-\delta$, for all distributions $\mathbb{Q}$ over $\mathcal{H}$,

$\small\begin{split}&\mathbf{R}_{\mathbb{T}}(\mathbb{Q})\leq\omega^{\prime}(\mathbf{R}_{S}(\mathbb{Q})+|\mathrm{d}_{S}(\mathbb{Q})-\mathrm{d}_{T}(\mathbb{Q})|)+|\mathrm{e}_{\mathbb{S}}(\mathbb{Q})-\mathrm{e}_{\mathbb{T}}(\mathbb{Q})|+2\omega\tfrac{\mathrm{KL}(\mathbb{Q}\mid\mid\mathbb{P})-\ln(\delta/3)}{m\omega^{\prime}}+2(\omega^{\prime}-1)\end{split}$
(25)

where $\omega^{\prime}=2\omega/(1-\exp(-2\omega))$ and for
$H_{i}\sim(\mathbb{Q})_{i}$, $(X,Y)\sim\mathbb{S}$ we have

$\small\begin{split}&\mathrm{e}_{\mathbb{S}}(\mathbb{Q})\operatorname*{\
\overset{\mathrm{def}}{=}\
}\mathbf{E}[(1-\mathbf{1}_{\\{H_{1}(X)\\}}\\{Y\\})(1-\mathbf{1}_{\\{H_{2}(X)\\}}\\{Y\\})],\\\
&\mathrm{d}_{\mathbb{S}}(\mathbb{Q})\operatorname*{\
\overset{\mathrm{def}}{=}\
}\mathbf{E}[1-\mathbf{1}_{\\{H_{1}(X)\\}}\\{H_{2}(X)\\}].\end{split}$ (26)

In comparison to Thm. 1, the absolute difference in disagreement $\mathrm{d}$
is most similar to the $\mathcal{H}\Delta\mathcal{H}$-divergence and the
absolute difference in joint-error $\mathrm{e}$ is most similar to the
adaptability $\lambda$ [Germain et al., 2020a]. For this reason, in our
discussion in Section 2, we refer to the former as the “divergence” and the
latter as the “adaptability”.

###### Proof.

As noted, this is a simplification of Thm. 7 of Germain et al. [2020a]. We set
$\omega=a$ in the original notation and use the fact that
$\omega/(1-\exp(-\omega))$ is increasing for $\omega>0$. ∎

###  A.3 Theorem 2

Before diving into the proof, we setup some helpful notation and Lemmas.

####  A.3.1 Notation

Frequently in our proofs, we use the error gap, defined for any distributions
$\mathbb{S},\mathbb{T}$ and hypothesis $h$

$\Delta_{h}(\mathbb{S},\mathbb{T})\operatorname*{\ \overset{\mathrm{def}}{=}\
}\lvert\mathbf{R}_{\mathbb{S}}(h)-\mathbf{R}_{\mathbb{T}}(h)\rvert.$ (27)

By the identification in Eq. (3), we observe that $\Delta_{h}(S,T)$ is also
well-defined for any random samples $S$ and $T$. Also, using the usual
definition of the Gibbs risk, $\Delta_{\mathbb{Q}}(\mathbb{S},\mathbb{T})$ is
well-defined for any distribution $\mathbb{Q}$ over a hypothesis space
$\mathcal{H}$. Occasionally, we also use two-subscripts on the error-gap
$\Delta$. The intended meaning is intuitive:

$\Delta_{q,p}(\mathbb{S},\mathbb{T})\operatorname*{\
\overset{\mathrm{def}}{=}\
}\lvert\mathbf{R}_{\mathbb{S}}(q)-\mathbf{R}_{\mathbb{T}}(p)\rvert.$ (28)

This notation will be especially useful in proofs since
$\Delta_{q,p}(\mathbb{S},\mathbb{T})$ obeys a triangle-inequality with respect
to the subscripts and arguments. Further, any bound on
$\Delta_{\mathbb{Q}}(S,\mathbb{T})$ trivially yields a PAC-Bayesian adaptation
bound for the Gibbs predictor $\mathbb{Q}$ by definition of the absolute
value.

As another short-hand in proofs, we frequently use the following more
evocative expressions for the indicator function:

$1[a=b]\operatorname*{\ \overset{\mathrm{def}}{=}\
}\mathbf{1}_{\\{a\\}}\\{b\\};\qquad 1[a\neq b]\operatorname*{\
\overset{\mathrm{def}}{=}\ }1-\mathbf{1}_{\\{a\\}}\\{b\\}.$ (29)

Now, we can proceed with the employed Lemmas.

####  A.3.2 Lemmas

In this section, we build to the proof of Theorem 2. These results consist of
most of the “real” work in proving the result. They range in degree of novelty
and we provide some exposition on this point here. Lemma 1 is an adaptation of
the triangle-inequality for 01-loss [Crammer et al., 2007, Ben-David et al.,
2007a] to the multiclass setting. Similarly, Lemma 2 is an adaptation of the
main inequality of Ben-David et al. [2010a] to the multiclass setting. The
former requires some work to verify the logic, while our overall strategy for
the latter is similar to the binary case. Next, Lemma 3 uses the
identification in Eq. (3) to apply Lemma 2 to the random samples $S$ and $T$.
While it is a simple insight, it is extremely important, since it enables us
to introduce the sample-dependent adaptability $\tilde{\lambda}$. The next
result, Lemma 4, is well-known in PAC-Bayes. Meanwhile, the final result,
Lemma 5, is a new result which allows us to apply Lemma 3 to Gibbs predictors.
When broken down in this manner, as is our intention, the individual pieces
that build to our bound may appear simple. Still, it is important to remember
that PAC-Bayesian bounds have never previously been combined with multiclass
variants of the results of Ben-David et al. [2007a, 2010a]. After some trial
and error, we’ve found our primary innovations – the use of sample-independent
adaptability, along with Lemma 5 – are vital to introducing the desired non-
uniform notion of sample complexity. In any case, we now proceed by stating
and proving each of the discussed Lemmas.

######  Lemma 1.

For any $(h,h^{\prime})\in\mathcal{H}^{2}$ and any
$(x,y)\in\mathcal{X}\times\mathcal{Y}$,

$1[h(x)\neq y]\leq 1[h(x)\neq h^{\prime}(x)]+1[h^{\prime}(x)\neq y]$ (30)

and

$1[h(x)\neq h^{\prime}(x)]\leq 1[h^{\prime}(x)\neq y]+1[y\neq h(x)].$ (31)

###### Proof.

We begin with Eq. (30). We use proof by exhaustion. If $h(x)=y$, then the LHS
is 0 and the RHS will always be non-negative so the equation is true. If
$h(x)\neq y$ and $h(x)\neq h^{\prime}(x)$, then the equation evaluates to
$1\leq 1+c$ for $c\geq 0$ which is true. If $h(x)\neq y$ and
$h(x)=h^{\prime}(x)$, then $h^{\prime}(x)\neq y$, and $1\leq 1$ which is true.
This concludes the argument.

Next, we consider Eq. (31). Again, we use proof by exhaustion. If
$h(x)=h^{\prime}(x)$, the LHS is 0. If $h(x)\neq h^{\prime}(x)$ and $h(x)=y$,
we have $h^{\prime}(x)\neq y$ and the equation evaluates to $1\leq 1$ which is
true. If $h(x)\neq h^{\prime}(x)$ and $h(x)\neq y$, it evaluates to $1\leq
1+c$ for $c\geq 0$ which is true and concludes the argument. ∎

Note, one observation is that the function
$\tilde{d}(y,y^{\prime})\operatorname*{\ \overset{\mathrm{def}}{=}\
}1[y^{\prime}\neq y]$ for any arguments $y,y^{\prime}\in\mathcal{Y}$ is
identical to a well-known function called the trivial metric or the discrete
metric. As implied by the name, the tuple $(\mathcal{Y},\tilde{d})$ forms a
metric space, and subsequently, Lemma 1 above is a simple consequence of this
fact. Nonetheless, we maintain the proof above to keep our discussion
relatively self-contained.

######  Lemma 2.

For any distributions $\mathbb{D}_{1}$ and $\mathbb{D}_{2}$ over
$\mathcal{X}\times\mathcal{Y}$, for any $h\in\mathcal{H}$

$\mathbf{R}_{\mathbb{D}_{1}}(h)\leq\mathbf{R}_{\mathbb{D}_{2}}(h)+\mathbf{d}_{\mathcal{C}_{h}}((\mathbb{D}_{1})_{X},(\mathbb{D}_{2})_{X})+\min_{\eta\in\mathcal{H}}\Big{\\{}\mathbf{R}_{\mathbb{D}_{1}}(\eta)+\mathbf{R}_{\mathbb{D}_{2}}(\eta)\Big{\\}}$
(32)

where $\mathcal{C}_{h}=\mathcal{H}\Delta\mathcal{H}$ or
$\mathcal{C}_{h}=h\Delta\mathcal{H}$ and $(\mathbb{D}_{i})_{X}$ is the
$\mathcal{X}$-marginal of $\mathbb{D}_{i}$.555In a formal sense,
$(\mathbb{D}_{i})_{X}$ is the pushforward distribution
$\mathbb{D}_{i}\circ\pi^{-1}$of the projection
$\pi:\mathcal{X}\times\mathcal{Y}\to\mathcal{X}$ defined $\pi(x,y)=x$.

###### Proof.

Let $\mathbb{D}_{1}$, $\mathbb{D}_{2}$, and $h$ as assumed.

Recall by Lemma 1 Eq. (30), for any $h^{\prime}$ in $\mathcal{H}$ and any
$(x,y)\in\mathcal{X}\times\mathcal{Y}$

$1[h(x)\neq y]\leq 1[h(x)\neq h^{\prime}(x)]+1[h^{\prime}(x)\neq y].$ (33)

Then, by monotonicity and linearity of the expectation, for any choice of
$h^{\prime}$,

$\begin{split}\mathbf{R}_{\mathbb{D}_{1}}(h)&\leq\mathbf{E}[1[h(X_{1})\neq
h^{\prime}(X_{1})]]+\mathbf{R}_{\mathbb{D}_{1}}(h^{\prime});\qquad
X_{1}\sim(\mathbb{D}_{1})_{X}\\\ &\leq\mathbf{E}[1[h(X_{2})\neq
h^{\prime}(X_{2})]]+\mathbf{R}_{\mathbb{D}_{1}}(h^{\prime})+\xi;\qquad
X_{2}\sim(\mathbb{D}_{2})_{X}\end{split}$ (34)

where

$\begin{split}\xi&=\big{\lvert}\mathbf{E}[1[h(X_{2})\neq
h^{\prime}(X_{2})]]-\mathbf{E}[1[h(X_{1})\neq
h^{\prime}(X_{1})]]\big{\rvert}\\\
&\leq\mathbf{d}_{\mathcal{C}_{h}}((\mathbb{D}_{1})_{X},(\mathbb{D}_{2})_{X}))\qquad\text{(by
definition of supremum, for either choice of }\mathcal{C}_{h}).\end{split}$
(35)

Alternatively, by Lemma 1 Eq. (31), for any choice of $h^{\prime},x,y$,

$1[h(x)\neq h^{\prime}(x)]\leq 1[h^{\prime}(x)\neq y]+1[y\neq h(x)].$ (36)

Using monotonicty and linearity of the expectation as before, we have

$\mathbf{E}[1[h(X_{2})\neq
h^{\prime}(X_{2})]]\leq\mathbf{R}_{\mathbb{D}_{2}}(h^{\prime})+\mathbf{R}_{\mathbb{D}_{2}}(h);\qquad
X_{2}\sim(\mathbb{D}_{2})_{X}.$ (37)

As the above holds for any $h^{\prime}\in\mathcal{H}$, select $h^{\prime}$ to
be minimizer of the quantity
$\mathbf{R}_{\mathbb{D}_{1}}(h^{\prime})+\mathbf{R}_{\mathbb{D}_{2}}(h^{\prime})$.

This yields the desired result. ∎

######  Lemma 3.

Almost surely, w.r.t samples $S$ and $T$,

$\small\forall h\in\mathcal{H}\ :\
\Delta_{h}(S,T)\leq\tilde{\lambda}+\mathbf{d}_{\mathcal{C}_{h}}(S_{X},T_{X})$
(38)

where $\tilde{\lambda}\operatorname*{\ \overset{\mathrm{def}}{=}\
}\min_{h\in\mathcal{H}}\mathbf{R}_{S}(h)+\mathbf{R}_{T}(h)$ and the bound
holds for both $\mathcal{C}_{h}=\mathcal{H}\Delta\mathcal{H}$ and
$\mathcal{C}_{h}=h\Delta\mathcal{H}$.

###### Proof.

The statement asserts the following holds with probability 1 according to the
random draws of $S$ and $T$:

$\forall h\in\mathcal{H}\ :\
\Delta_{h}(S,T)\leq\tilde{\lambda}+\mathbf{d}_{\mathcal{C}_{h}}(S_{X},T_{X})$
(39)

It is sufficient to show the statement holds for any realization of $S$ and
$T$. Recall, for any realization, $S$ and $T$ themselves define distributions
by the identification in Eq. (3). So, Lemma 2 may be applied. Doing so twice
and interchanging the roles of $S$ and $T$ gives

$\forall h\in\mathcal{H}\ :\
\mathbf{R}_{h}(S)-\mathbf{R}_{h}(T)\leq\tilde{\lambda}+\mathbf{d}_{\mathcal{C}_{h}}(S_{X},T_{X})\qquad\text{and}\qquad\mathbf{R}_{h}(T)-\mathbf{R}_{h}(S)\leq\tilde{\lambda}+\mathbf{d}_{\mathcal{C}_{h}}(S_{X},T_{X}).$
(40)

So, the absolute difference between $\mathbf{R}_{h}(S)$ and
$\mathbf{R}_{h}(T)$ is also bounded and we have our result. ∎

######  Lemma 4.

[Maurer, 2004a] For any distribution $\mathbb{P}$ over $\mathcal{H}$, for any
$\delta>0$,

$\mathbf{Pr}\Big{(}\forall\ \mathbb{Q}\ :\
\Delta_{\mathbb{Q}}(T,\mathbb{T})\leq\sqrt{\tfrac{\mathrm{KL}(\mathbb{Q}\mid\mid\mathbb{P})+\ln\sqrt{4m}-\ln(\delta)}{2m}}\
\Big{)}\geq 1-\delta.$ (41)

###### Proof.

This is the result of Maurer [2004a] given below

$\mathbf{Pr}\Bigg{(}\mathrm{kl}(\mathbf{R}_{T}(\mathbb{Q})\mid\mid\mathbf{R}_{\mathbb{T}}(\mathbb{Q}))\leq\frac{\mathrm{KL}(\mathbb{Q}||\mathbb{P})-\ln\delta+\ln\sqrt{4m}}{m}\
\Bigg{)}\geq 1-\delta,$ (42)

where the “little” $\mathrm{kl}$ is the KL-divergence between Bernoulli
distributions parameterized by its arguments. The above bound implies the
stated result by application of Pinsker’s Inequality. ∎

######  Lemma 5.

For any distribution $\mathbb{Q}$, almost surely w.r.t samples $S$ and $T$,

$\Delta_{\mathbb{Q}}(S,T)\leq\tilde{\lambda}+\mathbf{E}_{H}[\mathbf{d}_{\mathcal{C}_{H}}(S_{X},T_{X})]$
(43)

where $\tilde{\lambda}$ and $\mathcal{C}_{H}$ are defined as in Lemma 3.

###### Proof.

We apply Lemma 3. By Jensen’s Inequality, monotonicity of $\mathbf{E}$, and
linearity of $\mathbf{E}$, we have

$\Delta_{\mathbb{Q}}(S,T)\leq\mathbf{E}_{H}[\Delta_{H}(S,T)]\leq\tilde{\lambda}+\mathbf{E}_{H}[\mathbf{d}_{\mathcal{C}_{H}}(S_{X},T_{X})]$
(44)

almost surely. In more details, for any realization of $S$ and $T$,

$\displaystyle\Delta_{\mathbb{Q}}(S,T)$
$\displaystyle=\big{\lvert}\mathbf{R}_{\mathbb{Q}}(S)-\mathbf{R}_{\mathbb{Q}}(T)\big{\rvert}$
$\displaystyle=\big{\lvert}\mathbf{E}[\mathbf{R}_{S}(H)]-\mathbf{E}[\mathbf{R}_{T}(H)]\big{\rvert}$
$\displaystyle(H\sim\mathbb{Q},\ S\ \text{fixed},\ T\ \text{fixed})$
$\displaystyle=\Big{\lvert}\mathbf{E}\Big{[}\mathbf{R}_{S}(H)-\mathbf{R}_{T}(H)\Big{]}\Big{\rvert}$
$\displaystyle\text{(Linearity of }\mathbf{E})$
$\displaystyle\leq\mathbf{E}\big{[}\Delta_{H}(S,T)\big{]}$ (Jensen’s
Inequality)
$\displaystyle\leq\mathbf{E}\big{[}\tilde{\lambda}+\mathbf{d}_{\mathcal{C}_{H}}(S_{X},T_{X})\big{]}$
$\displaystyle\text{(Lemma\leavevmode\nobreak\ \ref{lem:simple-da-bendavid}
and monotonicity of }\mathbf{E})$
$\displaystyle\leq\tilde{\lambda}+\mathbf{E}[\mathbf{d}_{\mathcal{C}_{H}}(S_{X},T_{X})]$
$\displaystyle\text{(Linearity of }\mathbf{E}).$

∎

####  A.3.3 Proof

We give the final proof of Theorem 2 below. Admittedly, it is a bit
underwhelming, since most of the work has gone into the Lemmas above. The
remaining component we rely on is our notation for the error-gap $\Delta$. By
design, this notation exhibits a triangle-inequality.

###### Proof.

Observe,

$\Delta_{\mathbb{Q}}(S,\mathbb{T})\leq\Delta_{\mathbb{Q}}(S,T)+\Delta_{\mathbb{Q}}(T,\mathbb{T}).$
(45)

To bound the former, we use Lemma 5. To bound the latter, we use Lemma 4. We
use Boole’s Inequality to combine to the desired result. ∎

###  A.4 Theorem 3

As noted in the main text, we employ the overall strategy of Ben-David et al.
[2010a]. The main distinction in our result below is the removal of any
symmetry assumption on $\mathcal{H}$.

###### Proof.

As before, we show the statement holds for any realization of $S_{X}$ and
$T_{X}$.

Let $\mathcal{C}=\mathcal{H}\Delta\mathcal{H}$ and expand the divergence as
below

$\begin{split}&\mathbf{d}_{\mathcal{C}}(S_{X},T_{X})=\max_{\varphi\in\mathcal{H}\Delta\mathcal{H}}\big{\lvert}\mathbf{E}[\varphi(X)]-\mathbf{E}[\varphi(\tilde{X})]\big{\rvert}=\max_{\varphi\in\mathcal{H}\Delta\mathcal{H}}\big{\lvert}\mathbf{Pr}(\varphi(X)=1)-\mathbf{Pr}(\varphi(\tilde{X})=1)\big{\rvert}\end{split}$
(46)

where $X\sim S_{X}$, $\tilde{X}\sim T_{X}$. Note, we substitute $\max$ for
$\sup$ because both $S_{X}$ and $T_{X}$ are finitely supported, and thus, some
$\varphi\in\mathcal{C}$ does achieve the maximum. Then, we have

$\begin{split}&\max_{\varphi\in\mathcal{H}\Delta\mathcal{H}}\big{\lvert}\mathbf{Pr}(\varphi(X)=1)-\mathbf{Pr}(\varphi(\tilde{X})=1)\big{\rvert}\\\
&=\max_{\varphi\in\mathcal{H}\Delta\mathcal{H}}\max\begin{rcases}\begin{dcases}\mathbf{Pr}(\varphi(X)=1)-\mathbf{Pr}(\varphi(\tilde{X})=1),\\\
\mathbf{Pr}(\varphi(\tilde{X})=1)-\mathbf{Pr}(\varphi(X)=1)\end{dcases}\end{rcases}\\\
&=\max_{\varphi\in\mathcal{H}\Delta\mathcal{H}}\max\begin{rcases}\begin{dcases}1-\mathbf{Pr}(\varphi(X)=0)-\mathbf{Pr}(\varphi(\tilde{X})=1),\\\
1-\mathbf{Pr}(\varphi(\tilde{X})=0)-\mathbf{Pr}(\varphi(X)=1)\end{dcases}\end{rcases}\\\
&=\max\begin{rcases}\begin{dcases}1-\min_{\varphi\in\mathcal{H}\Delta\mathcal{H}}\Big{\\{}\mathbf{Pr}(\varphi(X)=0)+\mathbf{Pr}(\varphi(\tilde{X})=1)\Big{\\}},\\\
1-\min_{\varphi\in\mathcal{H}\Delta\mathcal{H}}\Big{\\{}\mathbf{Pr}(\varphi(\tilde{X})=0)+\mathbf{Pr}(\varphi(X)=1)\Big{\\}}\end{dcases}\end{rcases}.\\\
\end{split}$ (47)

The first equality follows by definition of absolute value, the second by law
of complements, and last because consecutive applications of the $\max$
operation may be interchanged. Taking $P,Q,U,V$ as assumed, the result follows
by the definition of risk; i.e., Eq. (1). ∎

###  A.5 Theorem 4

As we are aware, Theorem 4 is the first proposal for approximation of ERM over
the class $\mathcal{H}\Delta\mathcal{H}$ when $\mathcal{H}$ has multiclass
output. Our strategy is to identify an appropriate score-based surrogate
expression for any $\varphi\in\mathcal{S}\Delta\mathcal{S}$; i.e., which is
positive where $\varphi$ returns 1 and negative otherwise. Upon doing so, we
can use standard techniques for giving smooth upperbounds to the 01-loss.

###### Proof.

Let $x\in\mathcal{X}$, $\mathbf{f},\mathbf{g}\in\mathcal{F}$ and suppose
$\mathbf{f}(x)$ and $\mathbf{g}(x)$ have no repeated entries. Recall, for any
two sets of non-negative numbers $S_{1}$ and $S_{2}$ the following equality
holds666Suppose not. Then, WLOG $\max\\{a\cdot b\\}=d\cdot e>(\max
S_{1})\cdot(\max S_{1})$ for some $d\neq\max S_{1}$ or some $e\neq\max S_{2}$.
But, we also have $d\cdot e\leq d\cdot\max S_{2}\leq(\max S_{1})\cdot(\max
S_{2})$, a contradiction.

$\max\\{a\cdot b\mid a\in S_{1},b\in S_{2}\\}=(\max S_{1})\cdot(\max S_{2}).$
(48)

From this and the fact that $\tau$ is non-negative and order-preserving, we
know $\mathbf{A}_{ii}\geq\mathbf{A}_{jk}$ for some $i\in[C]$ and all
$(j,k)\in[C]^{2}$ if and only if

$i=\operatorname*{arg\,max}_{\ell\in
C}\mathbf{f}_{\ell}(x)=\operatorname*{arg\,max}_{\ell\in
C}\mathbf{g}_{\ell}(x).$ (49)

Notice, ties are impossible due to the assumed uniqueness of the scores. So,
by this same logic, we observe

$\begin{split}&\operatorname*{arg\,max}_{\ell\in
C}\mathbf{f}_{\ell}(x)\neq\operatorname*{arg\,max}_{\ell\in
C}\mathbf{g}_{\ell}(x)\\\ \mathrm{iff}\quad&\forall\ i\in[C],\ \exists\
(j,k)\in[C]^{2}\ :\mathbf{A}_{ii}<\mathbf{A}_{jk}\\\
\mathrm{iff}\quad&\max_{i\in[C]}\mathbf{A}_{ii}<\max_{(j,k)\in[C]^{2}}\mathbf{A}_{jk}\\\
\mathrm{iff}\quad&0<\max_{(j,k)\in[C]^{2}}\mathbf{A}_{jk}-\max_{i\in[C]}\mathbf{A}_{ii}=z(x)\end{split}$
(50)

So, under the current assumptions, the score $z(x)$ is positive if and only if
$\hat{y}=1-\mathbf{1}_{\\{\Psi_{\mathbf{f}}(x)\\}}\\{\Psi_{\mathbf{g}}(x)\\}=1$.
Using this fact, it is easy to verify $\mathcal{L}(z(x),y)\geq 1[\hat{y}\neq
y]$ for each case $(\hat{y},y)\in\\{(0,0),(0,1),(1,0),(1,1)\\}$. The loss
$\mathcal{L}$ is actually a standard surrogate – i.e., the cross-entropy –
multiplied by a constant factor as in Dziugaite and Roy [2017a] to turn it
into a propper upperbound on the 01-loss. The main novelty here comes from
defining $z(x)$ to be positive whenever $\hat{y}$ is.

Notice, the inequality holds on all but a set of measure 0, according to
$\mathbb{D}$. Thus, monotonicity of $\mathbf{E}$ gives the result. ∎

###  A.6 Theorem 5

As noted in the main text, Theorem 5 is conceptually similar to a result – in
the binary case – given by Kuroki et al. [2019a]. Unfortunately, their
strategy does not simply extend to the multiclass case: there is a loss of
precision due to the increased degrees of freedom in multiclass
classification. As a result, we observe the need to add additional constraints
on the labeling function for the classification problem. Specifically, we
introduce the class $\Upsilon$ for use in our reduction. Careful attention is
paid to show the constrained labeling function can be independent of the
classifier we wish to learn $\varphi\in\mathcal{H}$, which enables our appeal
to a simple heuristic that is also independent of $\varphi$. Otherwise, in
simpler formulations, this dependence produces a more complicated minimization
problem.

###### Proof.

We show the statement holds for any realization of $S_{X}$ and $T_{X}$.

Let $h\in\mathcal{H}$ arbitrarily and let $\mathcal{C}=h\Delta\mathcal{H}$. We
proceed by expanding the divergence:

$\begin{split}&\mathbf{d}_{\mathcal{C}}(S_{X},T_{X})=\max_{\nu\in
h\Delta\mathcal{H}}\big{\lvert}\mathbf{Pr}(\nu(X)=1)-\mathbf{Pr}(\nu(\tilde{X})=1)\big{\rvert}\\\
&=\max\begin{rcases}\begin{dcases}1-\min_{\nu\in
h\Delta\mathcal{H}}\Big{\\{}\mathbf{Pr}(\nu(X)=0)+\mathbf{Pr}(\nu(\tilde{X})=1)\Big{\\}},\\\
1-\min_{\nu\in
h\Delta\mathcal{H}}\Big{\\{}\mathbf{Pr}(\nu(\tilde{X})=0)+\mathbf{Pr}(\nu(X)=1)\Big{\\}}\end{dcases}\end{rcases}\\\
&=\max\begin{rcases}\begin{dcases}1-\min_{\varphi\in\mathcal{H}}\Big{\\{}\mathbf{Pr}(h(X)=\varphi(X))+\mathbf{Pr}(h(\tilde{X})\neq\varphi(\tilde{X}))\Big{\\}},\\\
1-\min_{\varphi\in\mathcal{H}}\Big{\\{}\mathbf{Pr}(h(\tilde{X})=\varphi(\tilde{X}))+\mathbf{Pr}(h(X)\neq\varphi(X))\Big{\\}}\end{dcases}\end{rcases}\end{split}$
(51)

where $X\sim S_{X}$ and $\tilde{X}\sim T_{X}$. The first and second lines
follow from an identical expansion as in the proof of Theorem 3. The last
follows by definition of $h\Delta\mathcal{H}$.

Next, we observe

$\forall\varphi\in\mathcal{H},\ \forall\bar{h}\in\Upsilon\ :\
\mathbf{Pr}(h(X)=\varphi(X))+\mathbf{Pr}(h(\tilde{X})\neq\varphi(\tilde{X}))\leq\mathbf{Pr}(\bar{h}(X)\neq\varphi(X))+\mathbf{Pr}(h(\tilde{X})\neq\varphi(\tilde{X})).$
(52)

The inequality follows by the monotonicity of probability and the fact

$\\{x\mid
h(x)=\varphi(x)\\}\subseteq\\{x\mid\bar{h}(x)\neq\varphi(x)\\}\qquad\text{(by
definition of }\bar{h}).$ (53)

Meanwhile, setting

$\bar{h}^{*}_{\varphi}(x)\operatorname*{\ \overset{\mathrm{def}}{=}\
}\begin{cases}\varphi(x),&\text{if}\ \varphi(x)\neq h(x)\\\
\max\\{\ell\in[C]\mid\ell\neq\varphi(x)\\},&\text{else}\end{cases}$ (54)

implies $\bar{h}^{*}_{\varphi}\in\Upsilon$ and $\\{x\mid
h(x)=\varphi(x)\\}=\\{x\mid\bar{h}^{*}_{\varphi}(x)\neq\varphi(x)\\}$. So, we
also have

$\forall\varphi\in\mathcal{H}\ :\
\mathbf{Pr}(h(X)=\varphi(X))+\mathbf{Pr}(h(\tilde{X})\neq\varphi(\tilde{X}))=\mathbf{Pr}(\bar{h}^{*}_{\varphi}(X)\neq\varphi(X))+\mathbf{Pr}(h(\tilde{X})\neq\varphi(\tilde{X})).$
(55)

Considering that $\bar{h}^{*}_{\varphi}\in\Upsilon$, Eq. (52) and Eq. (55) in
combination tell us

$\forall\varphi\in\mathcal{H}\ :\
\mathbf{Pr}(h(X)=\varphi(X))+\mathbf{Pr}(h(\tilde{X})\neq\varphi(\tilde{X}))=\min\nolimits_{\bar{h}\in\Upsilon}\Big{\\{}\mathbf{Pr}(\bar{h}(X)\neq\varphi(X))+\mathbf{Pr}(h(\tilde{X})\neq\varphi(\tilde{X}))\Big{\\}}.$
(56)

To see this, it’s easiest to use the definition of a set’s $\min$ element as
that which attains the greatest lower bound; i.e., the $\inf$ or infimum.
Then, Eq. (52) implies the $\min$ upperbounds the LHS of Eq. (56), and Eq.
(55) implies the $\min$ lowerbounds the LHS of Eq. (56). In combination, these
bounds prove equality.

Note, an identical argument also gives,

$\forall\varphi\in\mathcal{H}\ :\
\mathbf{Pr}(h(\tilde{X})=\varphi(\tilde{X}))+\mathbf{Pr}(h(X)\neq\varphi(X))=\min\nolimits_{\bar{h}\in\Upsilon}\Big{\\{}\mathbf{Pr}(\bar{h}(\tilde{X})\neq\varphi(\tilde{X}))+\mathbf{Pr}(h(X)\neq\varphi(X))\Big{\\}}.$
(57)

To continue, we apply Eq. (56) and Eq. (57) to Eq. (51). Specifically, we have

$\begin{split}&\max\begin{rcases}\begin{dcases}1-\min_{\varphi\in\mathcal{H}}\Big{\\{}\mathbf{Pr}(h(X)=\varphi(X))+\mathbf{Pr}(h(\tilde{X})\neq\varphi(\tilde{X}))\Big{\\}},\\\
1-\min_{\varphi\in\mathcal{H}}\Big{\\{}\mathbf{Pr}(h(\tilde{X})=\varphi(\tilde{X}))+\mathbf{Pr}(h(X)\neq\varphi(X))\Big{\\}}\end{dcases}\end{rcases}\\\
&=\max\begin{rcases}\begin{dcases}1-\underset{\bar{h}\in\Upsilon}{\min_{\varphi\in\mathcal{H},}}\Big{\\{}\mathbf{Pr}(\bar{h}(X)\neq\varphi(X))+\mathbf{Pr}(h(\tilde{X})\neq\varphi(\tilde{X}))\Big{\\}},\\\
1-\underset{\bar{h}\in\Upsilon}{\min_{\varphi\in\mathcal{H},}}\Big{\\{}\mathbf{Pr}(\bar{h}(\tilde{X})\neq\varphi(\tilde{X}))+\mathbf{Pr}(h(X)\neq\varphi(X))\Big{\\}}\end{dcases}\end{rcases}.\end{split}$
(58)

Taking $P,Q,U,V$ as assumed, the desired result follows by the definition of
risk in Eq. (1). ∎

###  A.7 Theorem 6

As noted in the main text, this result introduces a deterministic reference to
avoid costly Monte-Carlo estimation. It is the consequence of a series of
triangle-inequalities and some of the Lemmas disucssed in proof of Thm. 2.

###### Proof.

Observe, for any $h_{*}$,

$\begin{split}\Delta_{\mathbb{Q}}(S,\mathbb{T})&\leq\Delta_{\mathbb{Q},h_{*}}(S,T)+\Delta_{h_{*},\mathbb{Q}}(T,\mathbb{T})\\\
&\leq\Delta_{h_{*}}(S,T)+\Delta_{\mathbb{Q},h_{*}}(S,S)+\Delta_{\mathbb{Q}}(T,\mathbb{T})+\Delta_{\mathbb{Q},h_{*}}(T,T)\\\
&\leq\rho+\Delta_{h_{*}}(S,T)+\Delta_{\mathbb{Q}}(T,\mathbb{T})\end{split}$
(59)

Use Lemma 3 and Lemma 4, respectively, to bound the latter two terms.
Application of Boole’s Inequality and selection of $h_{*}=\mu$ gives the
result. ∎

###  A.8 Corollary 1

Conceptually, this result relies on the same proof-technique as Theorem 6, but
the proof is still a bit more technically involved than a typical “Corollary”
because it requires the measure-theoretic notion of a pushforward. We consider
pushfowards of empirical distributions, which are finitely supported, so there
is no need to discuss issues of measurability.

###### Proof.

Following the proof of Theorem 6, we have
$\Delta_{\mathbb{Q}}(S,\mathbb{T})\leq\rho+\Delta_{\mu}(S,T)+\Delta_{\mathbb{Q}}(T,\mathbb{T})$.
Now, recalling $\mu$ is the composition of a classifier $c_{\mu}$ and a
feature extractor $f_{\mu}$, we have

$\Delta_{\mu}(S,T)=\Delta_{c_{\mu}}(S\circ f_{\mu}^{-1},T\circ f_{\mu}^{-1})$
(60)

where we abuse notation and write $\mathbb{D}\circ g^{-1}$ for the pushforward
of a distribution $\mathbb{D}$ on $\mathcal{X}\times\mathcal{Y}$ by the
function $\Phi_{g}(x,y)=(g(x),y)$. In details, setting
$\ell(h,(x,y))=1[h(x)\neq y]$ and assuming $f_{\mu}:\mathcal{X}\to\mathcal{Z}$
and $c_{\mu}:\mathcal{Z}\to\mathcal{Y}$, Eq. (60) follows because

$\mathbf{R}_{\mathbb{D}}(\mu)=\int_{\mathcal{X}\times\mathcal{Y}}\ell(c_{\mu}\circ
f_{\mu},v)\mathbb{D}(\mathrm{d}v)=\int\ell(c_{\mu},\Phi_{f_{\mu}}(v))\mathbb{D}(\mathrm{d}v)=\int_{\mathcal{Z}\times\mathcal{Y}}\ell(c_{\mu},w)\mathbb{D}\circ
f_{\mu}^{-1}(\mathrm{d}w)=\mathbf{R}_{\mathbb{D}\circ f_{\mu}^{-1}}(c_{\mu})$
(61)

for any distribution $\mathbb{D}$ over $\mathcal{X}\times\mathcal{Y}$. After
applying the equality in Eq. (60), we can conclude our argument as in the
proof of Theorem 2 using Lemma 3. Although, it should be noted the adaptation
problem has changed slightly, since we now consider the hypothesis space
$\mathcal{W}=\\{c_{h}\mid
h\in\mathcal{H}\\}\subseteq\mathcal{Y}^{\mathcal{Z}}$, the source distribution
$\mathbb{S}\circ f_{\mu}^{-1}$ over $\mathcal{Z}\times\mathcal{Y}$, and the
target distribution $\mathbb{T}\circ f_{\mu}^{-1}$ over
$\mathcal{Z}\times\mathcal{Y}$. Of course, Lemma 3 still applies in this case,
so this does not present an issue.

After this, to arrive at the result in the main text, we simplify terms to
remove any discussion of pushforward distributions. For any risks, this is
accomplished by reversing the steps in Eq. (61). For any divergences, a
similar equality holds and can be applied. In particular, for any
$\mathcal{Q}\subseteq\mathcal{Y}^{\mathcal{Z}}$, any function
$p:\mathcal{X}\to\mathcal{Z}$, and any distributions $\mathbb{S}$ and
$\mathbb{T}$ over $\mathcal{X}\times\mathcal{Y}$, we use the expansion below:

$\begin{split}\mathbf{d}_{\mathcal{Q}}((\mathbb{S}\circ
p^{-1})_{Z},(\mathbb{T}\circ
p^{-1})_{Z})&=\sup_{q\in\mathcal{Q}}\lvert\mathbf{E}_{Z\sim(\mathbb{S}\circ
p^{-1})_{Z}}[q(Z)]-\mathbf{E}_{Z\sim(\mathbb{T}\circ
p^{-1})_{Z}}[q(Z)]\rvert\\\
&=\sup_{q\in\mathcal{Q}}\lvert\mathbf{E}_{X\sim\mathbb{S}_{X}}[(q\circ
p)(X)]-\mathbf{E}_{X\sim\mathbb{T}_{X}}[(q\circ
p)(X)]\rvert\qquad(\text{similiar to Eq.\leavevmode\nobreak\ \eqref{eqn:pf-
expl}})\\\ &=\sup_{r\in\mathcal{Q}\circ
p^{-1}}\lvert\mathbf{E}_{X\sim\mathbb{S}_{X}}[r(X)]-\mathbf{E}_{X\sim\mathbb{T}_{X}}[r(X)]\rvert\qquad(\mathcal{Q}\circ
p^{-1}\operatorname*{\ \overset{\mathrm{def}}{=}\ }\\{q\circ p\mid
q\in\mathcal{Q}\\})\\\ &=\mathbf{d}_{\mathcal{Q}\circ
p^{-1}}(S_{X},T_{X}).\end{split}$ (62)

Taking
$\mathcal{Q}=\\{1-\mathbf{1}_{\\{c(\cdot)\\}}\\{c^{\prime}(\cdot)\\}\mid(c,c^{\prime})\in\mathcal{W}\\}$
and $p=f_{\mu}$, we end up with $\mathcal{Q}\circ
p^{-1}=[\mathcal{H}\Delta\mathcal{H}]_{\mu}$ as defined in the main text.
Likewise, taking
$\mathcal{Q}=\\{1-\mathbf{1}_{\\{c_{\mu}(\cdot)\\}}\\{c^{\prime}(\cdot)\\}\mid
c^{\prime}\in\mathcal{W}\\}$ and $p=f_{\mu}$, we end up with $\mathcal{Q}\circ
p^{-1}=[\mu\Delta\mathcal{H}]_{\mu}$. ∎

##  Appendix B Extended Related Works

Here, we give an extended version of the related works (Section 2.3). First,
we discuss theoretical adaptation work. We compartmentalize relevant
contributions based on some key-terms common to adaptation bounds. Following
this, we discuss related works in PAC-Bayes, in which, we give a more in depth
history of these bounds.

##### Divergence

Many bounds use a modified, or generalized, divergence term. Mansour et al.
[2009a] define divergence for any loss function (i.e., in addition to the
01-loss we consider). With some restrictions on hypothesis space, Redko et al.
[2017a] show a Wasserstein metric may be used to bound error. Shen et al.
[2018a] extend this to more general settings. As noted by Redko et al.
[2020a], bounds based on Wasserstein metric imply bounds based on MMD [Gretton
et al., 2012] due to a general relationship between the two. Johansson et al.
[2019a] give another bound based on an integral probability metric. Note, none
of these works consider approximation of divergences used to bound 01-loss in
multiclass settings. In this regard, the closest work to ours is Zhang et al.
[2019a] who approximate a divergence used to bound a multiclass margin loss,
which in turn, bounds the 01-loss we consider. As noted, the primary
difference between our work and the work of Zhang et al. [2019a] is the use of
uniform sample-complexity in the latter. Possibly, bounds in the latter could
be extended to PAC-Bayesian contexts as well, but our choice of divergences
allows us to work directly with 01-loss and avoid any loosening of the bound
via the margin penalty.

##### Adaptability

Besides requiring small adaptability term, some theoretical DA works consider
other possible assumptions. For example, a covariate shift assumption can be
made: the marginal feature distributions disagree, but the feature-conditional
label distributions are identical. This assumption is useful, for example, in
designing model-selection algorithms [Sugiyama et al., 2007a, You et al.,
2019a], but Ben-David et al. [2010c] show this assumption (on its own) is not
enough for the general DA problem. Another frequent assumption is label-shift:
the marginal label distributions disagree, but the label-conditional feature
distributions remain the same. As mentioned, Zhao et al. [2019a] show failure-
cases in this context, while Lipton et al. [2018a] propose techniques for
detecting and correcting shift in this case. Similarly, Tachet des Combes et
al. [2020a] propose generalized label-shift and motivate new algorithms in
this context. The DA problem can also be modeled through causal graphs [Zhang
et al., 2015a, Magliacane et al., 2018a] and some extensions to DA consider a
meta-distribution over targets [Blanchard et al., 2021a, Albuquerque et al.,
2020b, Deng et al., 2020a]. Notably, most assumptions are untestable in
practice, but not many works consider this. As we are aware, we are the first
work to use a sample-dependent adaptability term, which improves estimation in
empirical study.

##### PAC-Bayes

For completeness, besides what is discussed here, readers are directed to the
work of Catoni [2007], McAllester [2013], Germain et al. [2009, 2015], and the
primer by Guedj [2019]. While PAC-Bayes is often attributed to McAllester
[1999] with early ideas by Shawe-Taylor and Williamson [1997], the particular
bound we use is due to Maurer [2004a]. A similar result was first shown by
Langford and Seeger [2001] for 01-loss. In experiments, we use data-dependent
priors, perhaps first conceptualized by Ambroladze et al. [2007], Parrado-
Hernández et al. [2012]. Besides the previously discussed work of Germain et
al., PAC-Bayes has also been used in theories for transfer learning [Li and
Bilmes, 2007a, McNamara and Balcan, 2017a]. As mentioned, our bounds are the
first PAC-Bayesian multiclass adaptation bounds.

##  Appendix C Experimental Details

###  C.1 Datasets and Models

As noted in the main text, we consider a collection of common adaptation
datasets from both computer vision and NLP. Each dataset consists of a number
of component domains which are themselves distinct datasets that all share a
common label space. In this way, we can simulate transfer of some model from
one domain to another. The datasets and models we consider are as follows:

  1. 1.

Digits: Digits consists of collection of digit classification datasets
including: USPS [Hull, 1994], MNIST [LeCun and Cortes, 2010], and SVHN [Netzer
et al., 2011]. We use only the training sets. The number images in each is
about 7K, 60K, and 70K, respectively. We select $\mathcal{X}$ to be the space
of 28$\times$28 grayscale images (i.e., the original feature space for MNIST).
For USPS and SVHN, this is accomplished through image transformation. The
label space $\mathcal{Y}$ consists of the digits 0-9. As we are aware, this
collection was first used by Ganin and Lempitsky [2015a]. For this task, we
consider $\mathcal{H}$ to be a space of CNNs of a fixed 4-layer architecture.

  2. 2.

PACS: PACS is an image-classification, domain generalization dataset where
each domain has a different style. It was proposed by Li et al. [2017a] to be
a more challenging task compared to existing generalization datasets. The
domains consist of images in style of: Photo, Art Painting, Cartoon, or
Sketch. There are about 10K total labeled images with some slight imbalance in
the liklihood of each style. The label space $\mathcal{Y}$ consists of 7
common object categories: dog, elephant, giraffe, guitar, horse, house, and
person. The feature space $\mathcal{X}$ is selected to be space of real-
vectors of dimension $2048$; i.e., $\mathbb{R}^{2048}$. To map to the feature
space from an image, we use the hidden-layer output of an image passed through
a pre-trained ResNet-50 [He et al., 2016a]. For this task, we consider
$\mathcal{H}$ to be either the space of linear classifiers or the space of
4-layer FCNs of a fixed architecture (fully-connected networks).

  3. 3.

Office-Home: Office-Home was originally proposed by Venkateswara et al.
[2017a], but we use the smaller preprocessed version given by Zhou et al.
[2020]. The dataset is similar to PACS. It also contains 4 different styles as
its component domains across about 15K total images: Art, Clipart, Product,
and Real-World. Unlike PACS, it has a much larger number of classes. In
particular, the label space $\mathcal{Y}$ contains 65 categories of different
daily objects. Like PACS, we use the outputs of ResNet-50 to map to the real
vector space $\mathcal{X}$. We let $\mathcal{H}$ be either a linear model or a
4-layer FCN as before.

  4. 4.

Amazon Reviews: Amazon Reviews is a text-classification dataset introduced by
Blitzer et al. [2007a]. We use the Books, DVD, Electronics, and Kitchen
domains preprocessed as in Blitzer et al. This totals about 4000 reviews which
are labeled as having positive or negative sentiment. The feature space
$\mathcal{X}$ is the space $\mathbb{N}^{4096}$; i.e., the space of bag-of-word
representations. For each review, the non-zero vector components correspond to
counts for words found within the review. Implicitly, this limits our
vocabulary to the 4095 most frequent words and leaves one special token for
out-of-vocabulary words. As noted, the label space $\mathcal{Y}$ is a binary
space whose elements denote the sentiment of the review. We let $\mathcal{H}$
be either a linear model or a 4-layer FCN as before.

  5. 5.

Discourse A (PDTB Labels): The Penn Discourse Treebank (PDTB) [Prasad et al.,
2008a] is an NLP dataset containing a subset of Wall Street Journal articles
from the Penn Treebank [Marcus et al., 1993] which are tagged with shallow
discourse coherence relations (i.e., relations that hold only between the
argument pairs and do not have any hierarchy or graph structure). These
coherence relations can be explicitly signaled by discourse _connectives_ such
as _and_ , _so_ , and _but_ , or could require the insertion of an _implicit_
connective. In this paper, we focus on the task of implicit discourse sense
classification which is the most difficult task for discourse parsers. To form
a DA dataset, we also used implicit relations from two parallel corpora: the
TED-MDB [Zeyrek et al., 2020a] which contains tagged TED talks and the BioDRB
[Ramesh and Yu, 2010a] which contains tagged scientific articles. These three
mentioned datasets form our component domains. Our feature space $\mathcal{X}$
is selected to be space of real-vectors of dimension 728. Within this space,
we try three different feature representations for the discourse
relations.777We only experiment within each representation type and do not
attempt to transfer across different representations. In the first two cases,
the feature is made up of the argument pairs which have been concatenated and
encoded using a BERT model [Devlin et al., 2019a]. We use either the pooled
output or the average of the hidden states. In the last case, we use Sentence-
BERT [Reimers and Gurevych, 2019] to encode our features. Our label space
$\mathcal{Y}$ consists of the 4 level 1 discourse sense classes contained in
the Penn Discourse Treebank. We let $\mathcal{H}$ be either a linear model or
a 4-layer FCN as before.

  6. 6.

Discourse B (GUM Labels): The GUM corpus [Zeldes, 2017] contains text
documents from 8 different genres: Academic, Biography, Fiction, Interview,
News, Reddit, How-To, and Travel. These genres form our component domains.
Documents within the corpus are annotated using the discourse framework of
Rhetorical Structure Theory [Mann and Thompson, 1987] in which discourse
coherence relations are organized in a hierarchical tree structure. The sense
hierarchy used for the GUM corpus is similar to that of the RST Discourse
Treebank [Carlson et al., 2003]. In order to focus on coherence relations only
between two argument pairs (without the additional hierarchical structure), we
removed all relations where one or both nodes was not a leaf node. To form the
label space, we mapped the twenty GUM labels to the conventional RST discourse
treebank top-level labels where only three GUM labels did not have an existing
mapping encoded in the RST. We mapped these three in the following manner,
following Braud et al. [2017]: _preparation_ to BACKGROUND, _justify_ and
_motivation_ to EXPLANATION, and _solutionhood_ to TOPIC-COMMENT. Given this
mapping, our final label space $\mathcal{Y}$ consists of the 13 different RST
discourse sense classes that were mapped to by the GUM corpus classes. Our
features are encoded the same way as the PDTB features. We let $\mathcal{H}$
be either a linear model or a 4-layer FCN as before.

##### Random Data Splits

To simulate variability due to sampling and also to consider more mild forms
of dataset shift, we split each component domain within each dataset into two
disjoint sets of (roughly) equal size. So, for a dataset with 4 component
domains, the new number of component domains will be 8. Some of these
component domains should now follow a fairly similiar distribution; i.e.,
splits coming from the same original component. This process is done randomly
and all adaptation scenarios (see Section C.4) test 3 different seeds for this
split.

###  C.2 Model Training for Divergence Approximation, Adaptability
Upperbounds, and Simple Algorithm (SA)

We train a number of deterministic models throughout our experimentation;
e.g., for divergence approximation, to compute risks for the ranking task, and
to compute upperbounds on $\lambda$. To avoid individual parameter selection
for more than 12,000 models all trained in our experimentation, we use the
optimization parameters given below in most cases. For Gibbs predictors, we
use a slightly modified technique which is also discussed below. For the DANN
algorithm, we use different parameters which were more carefully selected
(details discussed in Section C.3). While this “one size fits all” approach is
arguably simplistic, we found these settings worked well for a majority of
cases in our preliminary experiments. For divergence approximation and
upperbounds on adaptability this is visible in the main text results. In
Appendix D.2, we also report statistics on the transfer (target) error of some
hypotheses trained to minimize error on the source sample (i.e., the Simple
Algorithm SA). These provide a sanity check that our simple optimization
procedure is indeed selecting non-trivial hypotheses in a majority of cases.
Notably, the point of this work is to study global trends rather than to
achieve optimal performance on any one dataset. The “one size fits all”
approach we take is reflective of this; it allows us to use our limited
computational resources to study more datasets and models, rather than do
rigorous parameter search on just a few.

##### Optimization Parameters

All models are trained using SGD on an NLL loss with momentum set to $0.9$.
The NLL loss is sometimes weighted to correctly replicate the importance of
multiple risks (e.g., when minimizing a sum of two risks). For example, if we
have the objective $\min_{h}\mathbf{R}_{S}(h)+\mathbf{R}_{T}(h)$ and $S$ has
more samples than $T$, the NLL loss will weight examples in $T$ higher to give
them equal importance during optimization, as described by the objective. We
start training with a learning of $1\times 10^{-2}$ for 100 epochs. Then, we
train for another 50 epochs using a learning rate of $1\times 10^{-3}$. If a
model ever achieves a training error lower than $5\times 10^{-4}$, we
terminate training. In all cases, we use a batch size of $250$.

##### Gibbs Predictors

To learn a Gibbs predictor (stochastic model) $\mathbb{Q}$ we need to use a
slightly different approach. In all cases, $\mathbb{Q}$ will be a multivariate
normal distribution with diagonal covariance and we will minimize Gibbs risk
on a source sample $S$ with intention to transfer to a target sample $T$. We
use PAC-Bayes-by-Backprop (PBB) to learn the parameters of our normal
distribution. PBB is an SGD-based technique proposed by Pérez-Ortiz et al.
[2021a] to learn stochastic models that optimize PAC-Bayes bounds. The
approach requires specification of a particular PAC-Bayes bound to use as the
objective and a particular distribution $\mathbb{P}$ to use as the prior. For
the former, we use the variational bound proposed by Dziugaite et al. [2021a].
For the latter, we use a multivariate normal distribution: the mean is a
(trained) deterministic model (i.e., its parameter vector) and the covariance
matrix is $\sigma\mathbf{I}$ where $\sigma=0.01$ and $\mathbf{I}$ is the
identity matrix. We train the deterministic model to minimize the error on $S$
using the same optimization parameters discussed previously. Note, this may
seem taboo to one familiar with PAC-Bayes, since the prior $\mathbb{P}$ is
typically required to be independent of the data used in the bound. Contrary
to this, in our setting, it is perfectly valid to select $\mathbb{P}$ based on
the data in (only) $S$. This is clear in the proofs of Theorem 2 and Theorem 6
because the prior $\mathbb{P}$ is only used to bound the generalization gap
between $T$ and $\mathbb{T}$. Thus, this choice is reflective of a realistic
scenario where one wishes to compute a PAC-Bayes bound with $\mathbb{Q}$. The
approach we describe essentially corresponds to the idea of using a data-
dependent prior (see Section B). The prior $\mathbb{P}$ is learned using data
that is not used in any part of the bound which depends on $\mathbb{P}$. For
optimization parameters of PBB not discussed here (e.g., learning rate), we
default to the previously discussed choices.

###  C.3 DANN Model Training

For Digits, we study a PAC-Bayes variant of the invariant feature learning
algorithm DANN (Domain Adversarial Neural Network) proposed by Ganin and
Lempitsky [2015a]. The output of our variation is a Gibbs predictor
$\mathbb{Q}$, so we again employ PBB as discussed above in Section C.2. While
many parameters are similar to those used above – including the prior and the
PAC-Bayes bound –, we highlight some differences here. Most notably, we re-
weight the KL divergence in the PAC-Bayes bound by a dampening factor to
reduce its regularizing impact during training. For example, if the KL
divergence was 46K and the dampening factor was 0.1, the effective KL
divergence during training is 4.6K. We explore a range of different dampening
factors to get a breadth of different “complexities” for interpretation; i.e.,
this variability produces the movement along the horizontal axes of Figure 2.
In our experiments, we let the dampening factor range in the set
$\\{0.1,0.05,0.01,0\\}$. We did not use any dampening factor to recover the
original PAC-Bayes bound (i.e., 1) because we found this setting to be too
restrictive in preliminary experiments. Due to the increased training time
involved in this parameter sweep, we down-sampled the Digits dataset discussed
above so that neither $S$ nor $T$ have more than 5K examples. We selected the
learning rate by manual inspection, varying the learning rate (and number of
epochs accordingly) until we did not observe frequent gradient explosion /
vanishing. We ended up using an initial learning rate of $1\times 10^{-3}$ for
112 epochs (75% of 150) and $5\times 10^{-4}$ for the remaining 38 epochs. We
also reduced the batch size to 128, but most other parameters remained the
same. It is important to note that the instability we experienced (i.e.,
related to gradient explosion / vanishing) is somewhat common when training
adversarial methods such as DANN. As an additional measure to combat this
issue, we slowly eased in the adversarial loss by weighting it using the
parameter $\beta_{p}=2/(1+\exp(-10p))$ where $p$ is the progress ratio of the
current epoch in training; e.g., $p=0.1$ corresponds epoch 15 out of 150. This
approach was first proposed by Ganin and Lempitsky [2015a] for the same
purpose. Besides the adversarial loss, we also multiply the KL divergence
dampening factor by this weight to ease in the regularization component as
well. As a final measure, we used multiple restarts with a new neural network
initialization (up to 25 attempts), which proved to be the most effective
measure. Among about 32K statistics computed during these experiments, only 21
statistics were unable to be computed due to instability. These consisted of
restricted model-independent divergences (i.e., using class
$[\mathcal{H}\Delta\mathcal{H}]_{\mu}$) and were ignored in plots. Roughly 5%
of the data points still had “extreme” values that did not match any other
trend, so we removed these in Figure 2 to help with visual interpretation.

###  C.4 Adaptation Pairs

We now discuss the different adaptation scenarios we consider. Instances of
each scenario produce the collection of $(S,T)$ pairs we consider in our
histograms in the main text. Recall, we randomly split each component domain
into two halves (see Section C.1). This will be important for understanding
our adaptation scenarios.

##### Single-Source

For all datasets except Discourse B, we consider a single-source adaptation
scenario: each component domain in a dataset is paired with each distinct
component domain. So, for a dataset with 8 components, this forms 64 $(S,T)$
pairs. For example, one pair might take $S$ to be the first random half of
SVHN and $T$ to be the first random half of USPS. Another pair might take $S$
to be the first random half of SVHN and $T$ to be the second random half of
SVHN. So, as we see from this example, this implies that components derived
from the same domain (i.e., through our random splitting procedure) will be
paired. Note, these should follow a fairly similar (or identical)
distribution. This is purposeful and provides a number of instances of within-
distribution shift. These milder forms of shift allow us to test a broader
range of realistic scenarios. The random splitting procedure also allows us to
test variability in the outcome of a transfer task due to sampling; e.g., the
first and second random half of SVHN will both be paired with every other
dataset.

##### Multi-Source

We also consider multi-source scenarios for all datasets except Discourse A.
In these cases, we group all but one component of the dataset into a single
pooled sample. The single component which was left out is chosen to be the
target. So, for a dataset with 4 components, this forms 4 $(S,T)$ pairs. For
example, for PACS, one pair might take $S$ to be the union of Art, Cartoon,
and Sketch while $T$ consists of only Photo. Importantly, we only use one of
the random splits from each component type; e.g., for PACS, although we split
photo into two disjoint sets, we only use one of these two sets. Otherwise, in
every $(S,T)$ pair, $S$ would contain some data coming from a similar
distribution as $T$. Informally speaking, this likely to weaken the adaptation
difficulty. Note, the adaptation bounds we give implicitly cover multi-source
contexts, since we can view the single source $\mathbb{S}$ as a mixture
distribution.

##### Digits-Specific Scenarios

The Digits dataset is particular interesting because the feature space
$\mathcal{X}$ is well-understood by humans. Thus, we can use our experience to
design some natural distribution shifts. In particular, we consider the case
where $S$ is some component of Digits and $T$ is the same sample except every
image is randomly rotated up to $360^{\circ}$. We also consider the case where
$S$ is some component of Digits and $T$ is the same sample except every image
is blurred with random white noise. We can also consider a very unnatural
shift. In particular, we consider transfer to randomly generated data. Here,
$S$ is some component of Digits (as before) and every image in $T$ is a
$28\times 28$ grid of randomly generated pixels which is assigned a random
label. For these scenarios, we use the entirety of the components in the
Digits sets without doing any random splitting.

###  C.5 Details for For Figure 4

Each dataum in Figure 4 corresponds to an upperbound for one of the adaptation
pairs described in Section C.4 using one of the compatible hypothesis spaces
described in Section C.1. We describe the process for computing each type of
upperbound below. In all cases, we compute the upperbound using 3 different
random seeds; i.e., this will effect things like the model-training and
subsequently the final bound. We report the smallest upperbound of these
seeds. This is logical since the smallest upperbound is still a valid
upperbound. In case of $\lambda$, this is actually overly optimistic since the
confidence parameter should be changed to account for all 3 bounds.

##### Upperbound for $\tilde{\lambda}$

This bound is computed just as described in the main text. For each adaptation
pair $(S,T)$ and each hypothesis space $\mathcal{H}$ which is compatible with
$S$ and $T$, we train a model to minimize the summed risks on $S$ and $T$
using the approach described in Section C.2. If this approach returns the
hypothesis $h$, we report $\mathbf{R}_{S}(h)+\mathbf{R}_{T}(h)$. As noted in
the main text, this is a valid upperbound for $\tilde{\lambda}$.

##### Upperbound for $\lambda$

For each adaptation pair $(S,T)$ and each hypothesis space $\mathcal{H}$ which
is compatible with $S$ and $T$, we randomly split $S$ and $T$ using an 80/20
train/test split. Denote train splits for $S$ and $T$ by $S_{\mathrm{tr}}$ and
$T_{\mathrm{tr}}$, respectively. Denote the test splits for $S$ and $T$ by
$S_{\mathrm{ho}}$ and $T_{\mathrm{ho}}$, respectively. We train a model to
minimize summed risks on $S_{\mathrm{tr}}$ and $T_{\mathrm{tr}}$ using the
approach described in Section C.2. If this approach returns the hypothesis
$h$, we then report the quantity

$\mathbf{R}_{S_{\mathrm{ho}}}(h)+\mathbf{R}_{T_{\mathrm{ho}}}(h)+\sqrt{\ln(4/\delta)/(2m)}+\sqrt{\ln(4/\delta)/(2n)}$
(63)

where $m=|T_{\mathrm{ho}}|$, $n=|S_{\mathrm{ho}}|$, and $\delta=0.05$. This is
a valid upperbound for $\lambda$ which holds (i.e., prior to observing data)
with probability $1-\delta$. It is easily derived using Hoeffding’s Inequality
to bound both $\Delta_{h}(S_{\mathrm{ho}},\mathbb{S})$ and
$\Delta_{h}(T_{\mathrm{ho}},\mathbb{T})$, and then, using Boole’s Inequality
to combine the bounds.

###  C.6 Details for For Table 1

Each dataum used to compute the correlations in Table 1 corresponds to a
divergence approximation for an $(S,T,h)$ triple. The datasets $S$ and $T$ are
given by one of the adaptation pairs described in Section C.4, and
conceptually, we pick $h$ to be the hypothesis whose error we would like to
bound in the simulated transfer from $S$ to $T$. Specifically, for each
adaptation pair $(S,T)$ and each compatible hypothesis space $\mathcal{H}$, we
select $h$ using SA. We then approximate either the
$\mathcal{H}\Delta\mathcal{H}$\- or $h\Delta\mathcal{H}$-divergence using the
(appropriate) technique described in Section 3.2. The Spearman rank