# More Flexible PAC-Bayesian Meta-Learning by Learning Learning Algorithms

Hossein Zakerinia  Amin Behjati  Christoph H. Lampert

###### Abstract

We introduce a new framework for studying meta-learning methods using PAC-
Bayesian theory. Its main advantage over previous work is that it allows for
more flexibility in how the transfer of knowledge between tasks is realized.
For previous approaches, this could only happen indirectly, by means of
learning _prior distributions over models_. In contrast, the new
generalization bounds that we prove express the process of meta-learning much
more directly as learning the _learning algorithm_ that should be used for
future tasks. The flexibility of our framework makes it suitable to analyze a
wide range of meta-learning mechanisms and even design new mechanisms. Other
than our theoretical contributions we also show empirically that our framework
improves the prediction quality in practical meta-learning mechanisms.

Machine Learning, ICML

##  1 Introduction

Machine learning systems have remarkable success in solving complex tasks when
they are trained on large amounts of data. However, their success is still
limited when only little data is available for a task. One reason for this is
that common machine learning algorithms, such as minimizing training loss
through gradient-based optimization, are very generic. Tailored to be
applicable across a wide range of data sources and target tasks, the
underlying models need to have many degrees of freedom, and they require a lot
of training data to adjust these suitably. In contrast to this, natural
learning systems can learn new tasks from little task-specific data. They
achieve this by transferring and reusing information from their past
experience to new tasks, instead of learning a new model from scratch every
time.

_Meta-learning_ (also called _learning-to-learn_) is a principled way of also
giving machine learning systems the ability to share knowledge between related
learning tasks (Schmidhuber, 1987; Thrun & Pratt, 1998). Instead of learning
individual models for each task, a meta-learner learns a mechanism, a
_learning algorithm_ , that sets the model parameters given a (usually small)
amount of training data.

In practice, there are numerous possibilities to realize this step. _Model-
based_ approaches to meta-learning learn prototypical models which can
efficiently be adjusted (e.g. finetuned) to specific tasks (Finn et al., 2017;
Nichol et al., 2018). Relatedly, _regularization-based_ approaches learn
regularization terms that prevent future tasks from overfitting even if
trained on little data (Denevi et al., 2019). _Hypernetwork_ -based approaches
learn secondary networks that output the weights of task-specific models (Zhao
et al., 2020; Scott et al., 2023). _Representation-based_ approaches learn
(often low-dimensional) feature representations in which learning can be
performed with less training data than in the original input space (Maurer,
2009; Maurer et al., 2016; Lee et al., 2019). _Optimization-based_ approaches
learn the steps or (hyper)parameters of an optimization procedure (Hochreiter
et al., 2001; Ravi & Larochelle, 2017; Li et al., 2017).

All meta-learning methods strive for _generalization_ between previously seen
tasks and future ones. Unfortunately, most of the above methods are only
understood in terms of their empirical performance on example tasks, but they
lack theoretical guarantees on their generalization abilities.

_Meta-learning theory_ studies the theoretical properties of meta-learning
method. In particular, it aims at providing quantitative generalization
guarantees for them, in the form of high-probability upper bounds on the
quality of models learned on future tasks, even before data for these tasks is
available. Historically, the first attempts to do so had the form of classical
PAC guarantees, which were data-independent and had to be derived individually
for each method (Baxter, 2000; Maurer, 2009). However, starting with Pentina &
Lampert (2014), most recent works exploit PAC-Bayesian theory, which proved to
be more flexible and powerful. Not only does it allow deriving bounds that can
be instantiated for different meta-learning methods, but the generalization
guarantees are also data-dependent, and interpreting them as learning
objectives can inspire new meta-learning methods (Amit & Meir, 2018; Rothfuss
et al., 2021). Unfortunately, existing theoretical results still apply only to
a small number of actual meta-learning methods, namely those in which the
knowledge transfers from previous to future tasks can be expressed as a shift
of prior distributions over models. Of the ones we mention above, that
includes methods based on learning a model prototype or a regularization term,
but not the more flexible ones based on learning representations, optimizers,
or hypernetworks.

Our main contribution in this work is the introduction of new form of PAC-
Bayesian generalization bounds that provides theoretical guarantees for a much
broader class of meta-learning methods than previous ones. In particular, this
includes _all_ types of methods listed above. Specifically, the transfer of
knowledge from previous to future tasks is modeled not indirectly, using
distributions over models priors, but directly, using distributions over
_learning algorithms_. This viewpoint reflects the _learning-to-learn_ aspect
of meta-learning much better than previous ones, as it allows the meta-learner
to directly select which learning algorithms are meant to be executed on
future tasks. In contrast, the prior-based transfer of previous bounds allows
only an indirect influence by means of expressing a preference of some models
over others.

Besides our theoretical contributions, we also report on experiments in two
standard benchmark settings: we demonstrate that using our generalization
bound as a learning objective yields a meta-learning algorithm of improved
empirical performance compared to previous methods based on prior-based
transfer, and we show that even in the case where knowledge transfer can
actually be expressed as model priors, our bound is numerically tighter than
previous ones.

##  2 Background

There are many ways how the sharing of information between learning tasks can
be formalized. In this work, we adopt the meta-learning setting first proposed
in Baxter (2000) under the name of _learning to learn_. We call a tuple
$t=(D,S)$ a _task_ , where $D$ is a data distribution over a sample space
$\mathcal{Z}$, and $S=\\{z_{1},\dots,z_{m}\\}$ is a dataset sampled i.i.d.
according to this distribution. A _meta-learning method_ (or _meta-learner_)
has access to the training sets, $S_{1},\dots,S_{n}$ of a number of _training
tasks_ , $t_{1},\dots,t_{n}$, which themselves are i.i.d. sampled from an
unknown distribution, $\tau$, over a _task environment_. Let $\mathcal{F}$ be
a hypothesis set of possible models, and
$\ell:\mathcal{Z}\times\mathcal{F}\to[0,1]$ a loss function. For any set $X$,
we denote by $\mathcal{M}(X)$ the set of probability distributions over $X$,
and by $\mathcal{P}(X)$ the power set of $X$, where for our purposes, only
subsets of finite size matter.

The goal of meta-learning is to output (in some parameterized form) a
_learning algorithm_ , $A:\mathcal{P}(\mathcal{Z})\to\mathcal{F}$, i.e., a
mapping from the set of datasets to the set of models, with the goal to make
the _risk_ (expected loss) as small as possible in expectation when applying
the algorithm $A$ to a future task, i.e. minimize

$\displaystyle\operatorname*{\mathbb{E}}_{(D,S)\sim\tau}\mathcal{R}(A(S))\quad\text{for}\quad\mathcal{R}(f)=\operatorname*{\mathbb{E}}_{z\sim
D}\ell(z,f).$ (1)

Our main tool for analyzing such meta-learning methods theoretically will be
PAC-Bayesian learning theory. Before we apply this in the meta-learning
setting, we remind the reader of its main concepts in the standard setting.

###  2.1 PAC-Bayesian Learning

Classical PAC-Bayesian bounds (McAllester, 1998; Maurer, 2004) quantify the
generalization properties of _stochastic models_. A stochastic model is
parameterized by a distribution, $Q\in\mathcal{M}(\mathcal{F})$, over the
model space. For any input $z\in\mathcal{Z}$ it makes a stochastic predictions
by sampling $f\sim Q$ and outputting $f(z)$. We extend the loss function to
this as

$\displaystyle\ell(z,Q)$ $\displaystyle:=\operatorname*{\mathbb{E}}_{f\sim
Q}\ell(z,f).$ (2)

Now, let $t=(D,S)$ be the given task. The PAC-Bayesian framework provides an
upper bound on the _expected risk_ of a (stochastic) model, $Q$,

$\displaystyle\mathcal{R}(Q)$ $\displaystyle=\operatorname*{\mathbb{E}}_{z\sim
D}\ell(z,Q)$ (3) in terms of its _empirical risk_
$\displaystyle\widehat{\mathcal{R}}(Q)$ $\displaystyle=\frac{1}{|S|}\sum_{z\in
S}\ell(z,Q),$ (4)

and some complexity terms.

For example, from Maurer (2004) it follows that for any fixed $\delta>0$ and
any fixed prior distribution over models $P\in\mathcal{M}(\mathcal{F})$, with
probability at least $1-\delta$ over the sampling of the training dataset,
$S$, it holds that for all $Q\in\mathcal{M}(\mathcal{F})$,

$\displaystyle\mathcal{R}(Q)\leq\widehat{\mathcal{R}}(Q)+\sqrt{\frac{\operatorname{\mathbf{KL}}(Q\|P)+\log(\frac{2\sqrt{m}}{\delta})}{2m}},$
(5)

where $\operatorname{\mathbf{KL}}$ denotes the Kullback-Leibler divergence. In
words, the stochastic model $Q$ is guaranteed to generalize well, if it is
chosen sufficiently close to the prior, $P$.

Since their introduction by McAllester (1998), many similar bounds have been
derived that mostly differ the way they compare empirical and expected error,
the specific form of the complexity term, and with further assumptions they
make. See, , e.g., Guedj (2019); Alquier (2024); Hellström et al. (2023) for
surveys. However, the bounds have in common that the size of the complexity
term is mostly determined by the $\operatorname{\mathbf{KL}}$ divergence
between the posterior distribution $Q$ and a fixed data-independent prior $P$,
like it does in Equation (5). The bounds also have in common that they hold
uniformly with respect to $Q$. This means that one can use the right-hand side
of the inequality as a training objective, and the guarantees will still hold
for the (stochastic) model resulting from minimizing it.

###  2.2 PAC-Bayesian Meta-Learning

PAC-Bayesian bounds for meta-learning were pioneered by Pentina & Lampert
(2014). They assumed a fixed learning procedure that outputs a posterior
distribution over models, $Q(S,P)\in\mathcal{M}(\mathcal{F})$, depending on
the training data, $S$, as well as on a prior distribution,
$P\in\mathcal{M}(\mathcal{F})$. A canonical example of such a procedure would
be to return the stochastic model that minimizes the right hand side of (5).

For any prior, $P$, the expected risk on a new task,

$\displaystyle\mathcal{R}(P)=\operatorname*{\mathbb{E}}_{(S,D)\sim\tau}\operatorname*{\mathbb{E}}_{z\sim
D}\ell(z,Q(S,P)),$ (6)

provides a measure how suitable this choice of prior is for future tasks.
However, (6) cannot be computed, because it depends on unobserved quantities.
Under Baxter’s assumptions that the available training tasks are sampled from
the same task environment as future tasks, the _empirical multi-task risk_ ,

$\displaystyle\widehat{\mathcal{R}}(P)=\frac{1}{n}\sum_{i=1}^{n}\frac{1}{|S_{i}|}\sum_{z\in
S_{i}}\ell(z,Q(S_{i},P)),$ (7)

can serve as empirical proxy for $\mathcal{R}(P)$. The difference between (6)
and (7) can be bounded with PAC-Bayesian techniques, as long as the prior is
not simply chosen in a deterministic way, but by means of specifying its
posterior distribution, $\mathcal{Q}\in\mathcal{M}(\mathcal{M}(\mathcal{F}))$,
called the _hyper-posterior_. Overall, one obtains guarantees that
$\mathcal{R}(\mathcal{Q})=\operatorname*{\mathbb{E}}_{P\sim\mathcal{Q}}\mathcal{R}(P)$
is bounded by
$\widehat{\mathcal{R}}(\mathcal{Q})=\operatorname*{\mathbb{E}}_{P\sim\mathcal{Q}}\widehat{\mathcal{R}}(P)$
and some complexity terms that are increasing functions of
$\operatorname{\mathbf{KL}}(\mathcal{Q}\|\mathcal{P})$, where
$\mathcal{P}\in\mathcal{M}(\mathcal{M}(\mathcal{F}))$ is a data-independent
_hyper-prior_ , and of $\operatorname{\mathbf{KL}}(A(S_{i},P)\|P)$ in
expectation over $P\sim\mathcal{Q}$.

Numerous later works improved and extended these PAC-Bayesian meta-learning
bounds: Amit & Meir (2018) designed an optimization algorithm based on this
setup for neural networks, Liu et al. (2021) proved bounds with a different
form, Guan & Lu (2022) and Riou et al. (2023) proved fast rate bounds for this
setup, Friedman & Meir (2023) proved bounds based on data-dependent PAC-Bayes
bounds, and Rezazadeh (2022) provided a general framework for proving several
different form bounds. Rothfuss et al. (2021, 2023) generalized the setup to
unbounded loss functions, and developed a new algorithm for estimating optimal
hyper-posteriors. Ding et al. (2021); Tian & Yu (2023) studied this setup for
few-shot meta-learning, and Farid & Majumdar (2021) studied the connection
between PAC-Bayes and uniform stability in this setup.

While these works constitute substantial progress, all of them share a common
limitation that they inherited from the setup originally defined in Pentina &
Lampert (2014): they only apply to meta-learning methods that are expressible
as a single learning strategy parameterized by a prior distribution over
models. However, many practical meta-learning algorithms do not follow this
pattern, thereby preventing the existing PAC-Bayesian frameworks from studying
the generalization ability of these algorithms.

One exception is Pentina & Lampert (2015), which provided a bound over
transformation operators between tasks, but this situation applies only under
rather restrictive assumptions. Another one is the recent Scott et al. (2023),
which proved a related PAC-Bayesian bound in the context of personalized
federated learning. However, the result provides only rather weak guarantees,
because it assumes fixed prior distributions that have to be chosen without
any knowledge about the task environment instead of benefiting from
environment-dependent priors as the works above. As an alternative framework,
information-theoretic bounds have been derived (Hellström & Durisi, 2022;
Hellström et al., 2023). These, however, typically provide bounds in
expectation rather than with high probability over the training tasks, and
they are harder to compute than the PAC-Bayesian ones.

In this work, we introduce a new form of PAC-Bayesian meta-learning bounds
that overcomes the limitation of previous works. It works in a more general
setup that applies to any set of learning algorithms as well as allowing for
algorithm-specific hyper-posteriors.

Table 1: Notations $P\in\mathcal{M}(\mathcal{F})$ | Prior distribution
---|---
$Q\in\mathcal{M}(\mathcal{F})$ | Posterior distribution
$\pi\in\mathcal{M}(\mathcal{A})$ | Meta-Prior over algorithms
$\rho\in\mathcal{M}(\mathcal{A})$ | Meta-Posterior over algorithms
$\mathcal{P}(A)\in\mathcal{M}(\mathcal{M}(\mathcal{F}))$ | Hyper-Prior over priors
$\mathcal{Q}(A)\in\mathcal{M}(\mathcal{M}(\mathcal{F}))$ | Hyper-Posterior over priors

##  3 Main Results

In this section, we state and discuss our main result: a generalization bound
that holds for any meta-learning method that is expressible as a way to
_choose a learning algorithm for future tasks_.

Formally, let
$\mathcal{A}=\\{A:\mathcal{P}(\mathcal{Z})\to\mathcal{M}(\mathcal{F})\\}$ be a
_set of stochastic learning algorithms_ that take as input a dataset and
output a posterior distribution over models. Note that this algorithm set does
not have to be homogeneous. For example, $\mathcal{A}$, could contain
different architectures of neural networks, which are initialized in different
ways and adjusted to the training data by different optimizers, or decision
trees with different construction rules, or support vector machines with
different kernels, or prototype-based classifiers with different distance
measures, or all of the above together.

Given a set of training datasets, $S_{1},\dots,S_{n}$, the meta-learner
outputs a posterior distribution over the algorithms,
$\rho\in\mathcal{M}(\mathcal{A})$. We call $\rho$ the _meta-posterior
(distribution)_ , and we define its risk on future tasks as

$\displaystyle\mathcal{R}(\rho)=\operatorname*{\mathbb{E}}_{A\sim\rho}\operatorname*{\mathbb{E}}_{(S,D)\sim\tau}\operatorname*{\mathbb{E}}_{z\sim
D}\ell(z,A(S)).$ (8)

If this value is small then the meta-learner has done a good job at
identifying learning algorithms that work well on future tasks. As such,
Equation (8) describes the actual quantity of interest. However, it is not a
computable value. Therefore, we introduce the _empirical risk_ of the meta-
posterior, $\rho$, on the $n$ training tasks as

$\displaystyle\widehat{\mathcal{R}}(\rho)=\operatorname*{\mathbb{E}}_{A\sim\rho}\frac{1}{n}\sum_{i=1}^{n}\frac{1}{|S_{i}|}\sum_{z\in
S_{i}}\ell(z,A(S_{i})).$ (9)

Our main results, Theorems 3.1 and 3.2 below, provide upper bounds on
$\mathcal{R}(\rho)$ in terms of $\widehat{\mathcal{R}}(\rho)$ and suitable
complexity terms.

Before stating them, we introduce one additional source of flexibility that
our framework possesses. Remember that in the classical setting of Section
2.2, one fixed hyper-prior distribution over priors was given, and the meta-
learner was meant to learn one hyper-posterior distribution over priors. In
our setting, especially if the algorithm set is heterogeneous, it stands to
reason that different algorithms might benefit from different choices of prior
distributions. To express this, let
$\mathcal{P}:\mathcal{A}\to\mathcal{M}(\mathcal{M}(\mathcal{F}))$ now be a
fixed data-independent mapping of algorithms to hyper-priors, i.e. for each
algorithm, $A$, one hyper-prior,
$\mathcal{P}(A)\in\mathcal{M}(\mathcal{M}(\mathcal{F}))$, is associated in a
data-independent way. Analogously, denote by
$\mathcal{Q}:\mathcal{A}\to\mathcal{M}(\mathcal{M}(\mathcal{F}))$ a mapping of
algorithms to hyper-posteriors. As part of the meta-learning process, the
meta-leaner constructs $\mathcal{Q}$ by specifying a hyper-posterior
distribution, $\mathcal{Q}(A)\in\mathcal{M}(\mathcal{M}(\mathcal{F}))$, for
any learning algorithm $A\in\mathcal{A}$.

We now state our first main result: a generalization bound for
$\mathcal{R}(\rho)$ in terms of $\widehat{\mathcal{R}}(\rho)$ that holds with
high probability uniformly for all possible choices of $\rho$ and
$\mathcal{Q}$.

######  Theorem 3.1.

For any fixed meta-prior $\pi$, fixed hyper-prior mapping $\mathcal{P}$ and
any $\delta>0$, with probability at least $1-\delta$ over the sampling of the
training tasks, that for all distributions $\rho\in\mathcal{M}(\mathcal{A})$
over algorithms, and for all hyper-posterior mappings
$\mathcal{Q}:\mathcal{A}\to\mathcal{M}(\mathcal{M}(\mathcal{F}))$ it holds

$\displaystyle\mathcal{R}(\rho)\leq\widehat{\mathcal{R}}(\rho)+\sqrt{\frac{\operatorname{\mathbf{KL}}(\rho\|\pi)+\log(\frac{4\sqrt{n}}{\delta})}{2n}}$
(10)
$\displaystyle+\sqrt{\frac{\operatorname{\mathbf{KL}}(\rho||\pi)+\operatorname*{\mathbb{E}}_{A\sim\rho}[C_{1}(A,\mathcal{Q},\mathcal{P})]+\log(\frac{8mn}{\delta})+1}{2mn}},$

with

$\displaystyle\begin{split}C_{1}(A,\mathcal{Q},\mathcal{P})=&\operatorname{\mathbf{KL}}(\mathcal{Q}(A)\|\mathcal{P}(A))\\\
&+\operatorname*{\mathbb{E}}_{P\sim\mathcal{Q}(A)}\sum_{i=1}^{n}\operatorname{\mathbf{KL}}(A(S_{i})||P).\end{split}$
(11)

Our second main result is a tightened variant of Theorem 3.1 that holds in the
special case that all algorithms share the same hyper-prior, i.e.
$\mathcal{P}$ is constant.

######  Theorem 3.2.

For any fixed meta-prior $\pi$, fixed hyper-prior $\mathcal{P}$ and any
$\delta>0$ with probability at least $1-\delta$ over the sampling of the
datasets, that for all distributions $\rho\in\mathcal{M}(\mathcal{A})$ over
algorithms, and for all hyper-posterior functions
$\mathcal{Q}:\mathcal{A}\rightarrow\mathcal{M}(\mathcal{M}(\mathcal{F}))$ it
holds

$\displaystyle\mathcal{R}(\rho)$
$\displaystyle\leq\widehat{\mathcal{R}}(\rho)+\sqrt{\frac{\operatorname{\mathbf{KL}}(\rho||\pi)+\log(\frac{4\sqrt{n}}{\delta})}{2n}}$
(12) $\displaystyle\quad+\
\operatorname*{\mathbb{E}}_{A\sim\rho}\sqrt{\frac{C_{2}(A,\mathcal{Q},\mathcal{P})+\log(\frac{8mn}{\delta})+1}{2mn}}$
(13) $\displaystyle C_{2}(A,\mathcal{Q},\mathcal{P})$
$\displaystyle=\operatorname{\mathbf{KL}}(\mathcal{Q}(A)\|\mathcal{P})$ (14)
$\displaystyle\quad+\operatorname*{\mathbb{E}}_{P\sim\mathcal{Q}(A)}\sum_{i=1}^{n}\operatorname{\mathbf{KL}}(A(S_{i})||P)$

We provide proof sketches for both theorems in Section 4. For complete proofs,
see Appendix A.

###  3.1 Discussion

In this section, we discuss the properties of the bounds and explain the role
and benefits of different terms. We also highlight the differences between our
general setup with the more narrow setups of previous works and explain how
our algorithm applies to existing meta-learning methods.

#### Complexity terms

As it is common for PAC-Bayesian meta-learning, the bounds (10) and (13) each
contain two complexity terms, which reflect the two types of generalization
required for meta-learning guarantees: _task-level generalization_ , i.e.
generalization from the observed tasks to future tasks, and _within-task
generalization_ for all training tasks (also called _multi-task
generalization_). In the following, we first discuss (10) in detail and
afterwards discuss how (13) differs from it.

The first complexity term of (10) expresses the aspect of task-level
generalization: it contains the $\operatorname{\mathbf{KL}}$-divergence
between the data-dependent meta-posterior and the data-independent meta-prior
over algorithms. As such, it reflects directly how much the choice of learning
algorithm is influenced by the data. In addition, it contains an additional
logarithmic term that is small for all practical choices of $n$ and $\delta$.
Both terms are divided by $2n$, meaning that the first complexity term
decreases with the number of training tasks and vanishes (only) for
$n\to\infty$. It is not affected by the number of training samples per task,
$m$. Such a behavior makes sense: the uncertainty about the task environment,
i.e. what kind of tasks will appear in the future, is reduced with each
additional training task, but having more data points from the tasks available
does not provide new information about this aspect.

The second complexity term of Equation (10) contains the same
$\operatorname{\mathbf{KL}}$-divergence term as well as two additional ones:
in simplified form (ignoring the expectations over algorithms), the first term
relates the algorithm’s hyper-posterior, $\mathcal{Q}(A)$, to its hyper-prior,
$\mathcal{P}(A)$. This term reflects the amount by which the meta-learner’s
choice of priors depends on the observed data. However, the denominator for
this complexity term is $2nm$ instead of $2n$ for the first term, indicating
that the hyper-posterior can be adjusted rather flexibly without increasing
the size of this term too much. The final $\operatorname{\mathbf{KL}}$-term
relates each task’s predicted models, $A(S_{i})$, and its respective prior
distributions, $P$. The sum of these $n$ terms is divided by $2nm$, making the
term decrease with $m$ and vanish for $m\to\infty$. Once again, a term of this
type makes sense. It reflects the average uncertainty about the true risk for
models learned from finite data of each training task. When the number of
samples, $m$, per task grows, the uncertainty about each task is reduced. When
just the number, $n$, of training tasks grows, however, the amount of data per
task remains the same, so no reduction of the average per-task uncertainty can
be expected. The remaining terms in the numerator depend only logarithmically
on this number and $\delta$ and are negligible in most practical settings.

More precisely, Equation (10) contains the expectations of these terms over
the actually stochastic choice of algorithm and prior distribution.

#### Hyper-posteriors

A basic PAC-Bayes bound with a fixed prior would result in separate and
independent complexity terms for each task, independent of the environment,
and will not take into account the relation between training tasks. Instead,
we introduce algorithm-dependent hyper-posteriors, from which we sample
priors, and are learned specifically for each learning algorithm, shared
between all the tasks. Therefore, the $n$ complexity terms for each $A$ become
$\operatorname*{\mathbb{E}}_{P\sim\mathcal{Q}(A)}\sum_{i=1}^{n}\operatorname{\mathbf{KL}}(A(S_{i})||P)$
with the additional cost of
$\operatorname{\mathbf{KL}}(\mathcal{Q}(A)\|\mathcal{P}(A))$, which improves
$n$ terms at the cost of one extra term.

In this formulation, $\mathcal{Q}(A)$ can be seen as a similarity measure for
the output of the algorithm. The complexity measure is small if for the
outputs of the algorithm for $n$ tasks, there is a good hyper-posterior to
generate priors close to all posteriors. Note that we can learn different
hyper-posteriors for different algorithms, and capture these similarities
specifically for the outputs of each algorithm.

Note that the hyper-posterior is a mathematical notion, and the bound holds
for all hyper-posteriors at the same time (with high probability). Its role is
to help better capture the relations between tasks when using a specific
algorithm. For a future task, only the meta-posterior would apply and the role
of the hyper-posterior by default is implicit.

#### Difference between the theorems

The bound (13) differs from bound (10) most in the fact that the term
$\operatorname{\mathbf{KL}}(\rho\|\pi)$ does not appear in the second term,
and $\rho$ only appears in the second term as the distribution over algorithms
(when we take the expectation of algorithms in
$\operatorname*{\mathbb{E}}_{A\sim\rho}$). The expectation is also moved
outside of the square root, which makes the bound tighter (Jensen’s
inequality). We attribute the differences mainly to the fact that for an
algorithm-independent hyper-prior, some steps in the proof can be performed in
a tighter way. Generally, both bounds agree in their main behavior with
respect to the number of training tasks and samples.

#### Comparison with previous works

The setting of Section 3 is a strict generalization of the setup from previous
works where the meta-learner only learned priors. In fact, the latter setting
can be recovered from ours as follows: let $Q(S,P)$ be the fixed learning rule
of a prior-based meta-learning method. We then define a family of algorithms
as $\mathcal{A}=\\{Q(\cdot,P):P\in\mathcal{M}(\mathcal{F})\\}$. With each
element of $\mathcal{A}$ uniquely is determined by a prior $P$, choosing a
distribution of algorithms is equivalent to choosing a distribution over
priors. Now, by setting $\mathcal{Q}(A)=\mathcal{Q}(P)=\delta_{P}$ and
$\mathcal{P}(A)=\mathcal{P}(P)=\delta_{P}$, Theorem 3.1 is applicable. In
Section 5.1 we compare the resulting generalization bound numerically to prior
ones in this setting.

Similarly, we can recover the bounds of Scott et al. (2023), which transfer
algorithms but only allow for a single fixed choice of prior: for any
$A\in\mathcal{A}$ we set $\mathcal{Q}(A)=\delta_{P_{0}}$ and
$\mathcal{P}(A)=\delta_{P_{0}}$, where $P_{0}$ is the fixed prior. Again,
Theorem 3.2 is now applicable. This construction also shows that our result
not only recovers the bound of Scott et al. (2023) but improves over it. The
reason is that Theorem 3.2 holds uniformly over all (potentially data-
dependent) choices of $\mathcal{Q}$, of which the construction described above
is simply a single data-independent choice.

#### Recovering common meta-learning methods

As discussed in the introduction, previous works on meta-learning that rely on
transferring priors over models are not applicable to hypernetwork-based,
representation-based, or optimization-based meta-learning methods because
these require different parametrizations of their algorithm sets.

In our framework, expressing these methods is straight-forward. For the
hypernetwork-based methods (Zhao et al., 2020; Scott et al., 2023), the set of
algorithms is parametrized by the set of hypernetwork weights. Consequently,
learning the algorithm means training the hypernetwork. For representation-
based methods (Maurer, 2009; Maurer et al., 2016; Lee et al., 2019)
parametrizing each algorithm is a feature extractor, such as a linear
projection or a convolutional network. For optimization-based meta-learning
(Hochreiter et al., 2001; Ravi & Larochelle, 2017; Li et al., 2017), the
algorithm set can contain all hyperparameters to be learned, or the set of all
considered optimization procedures, e.g. in the form of the weights of a
recurrent network. In all cases, our bound can directly be applicable. In
fact, based on our bound one might even improve such methods by suggesting
appropriate (meta-)regulation term.

Another observation is that our framework also allows combining different
approaches. For example, the algorithm set could be parametrized by the
starting point of an optimization step (e.g. the initialization of a network),
as well as by a regularization term. The result is a hybrid of methods based
on model prototypes and on methods based on learning a regularizer. Prior
works were applicable to study either of these approaches individually, but
not their combination. Nevertheless, we provide an experimental demonstration
that such a hybrid approach can be beneficial in Section 5.

##  4 Proof sketch

We provide the proof sketch of Theorem 3.1. The full proof and the proof of
Theorem 3.2 are available in Appendix A.

For the proof we first define an intermediate objective that represents the
true risk of the training tasks,

$\displaystyle\widetilde{\mathcal{R}}(\rho)=\operatorname*{\mathbb{E}}_{A\sim\rho}\frac{1}{n}\sum_{i=1}^{n}\operatorname*{\mathbb{E}}_{z\sim
D_{i}}\ell(z,A(S_{i})).$ (15)

The proof is then divided into two parts. First, we bound the difference of
the true risks between training tasks and future tasks
$\mathcal{R}(\rho)-\widetilde{\mathcal{R}}(\rho)$. Second, we bound the
difference between the true risk and empirical risk of training tasks
$\widetilde{\mathcal{R}}(\rho)-\widehat{\mathcal{R}}(\rho)$. The final result
follows by combining the two bounds.

#### Part I

To bound $\mathcal{R}(\rho)-\widetilde{\mathcal{R}}(\rho)$ we use standard
PAC-Bayesian arguments, specifically the following lemma:

######  Lemma 4.1.

For all $\delta>0$ it holds with probability at least $1-\frac{\delta}{2}$
over the sampling of tasks for all meta-posteriors
$\rho\in\mathcal{M}(\mathcal{A})$:

$\displaystyle\mathcal{R}(\rho)-\widetilde{\mathcal{R}}(\rho)\leq\sqrt{\frac{\operatorname{\mathbf{KL}}(\rho||\pi)+\log(\frac{4\sqrt{n}}{\delta})}{2n}}.$
(16)

This lemma is an application of applying the standard PAC-Bayesian bounds
Maurer (2004); Pérez-Ortiz et al. (2021). For details, see Appendix A.

#### Part II

We define the following two functions which produce distributions over
$\mathcal{A}\times\mathcal{M}(\mathcal{F})\times\mathcal{F}^{\otimes n}$, i.e.
they assigns joint probabilities to tuples, $(A,P,f_{1},...,f_{n})$, which
contain an algorithm, a prior over models, and $n$ models.

_Posterior $\mathfrak{Q}(\rho,\mathcal{Q})$:_ given as input a meta-posterior
$\rho$ over algorithms and a hyper-posterior mapping $\mathcal{Q}$ as input,
it outputs the distribution over
$\mathcal{A}\times\mathcal{M}(\mathcal{F})\times\mathcal{F}^{\otimes n}$ with
the following generating process: _i)_ sample an algorithm $A\sim\rho$, _ii)_
sample a prior $P\sim\mathcal{Q}(A)$, _iii)_ for each task, $i=1,\dots,n$,
sample a model $f_{i}\sim A(S_{i})$.

_Prior $\mathfrak{P}(\pi,\mathcal{P})$:_ given as input a meta-prior $\pi$
over algorithms and a hyper-prior mapping $\mathcal{P}$ as input, it outputs
the distribution over
$\mathcal{A}\times\mathcal{M}(\mathcal{F})\times\mathcal{F}^{\otimes n}$ with
the following generating process: _i)_ sample an algorithm $A\sim\pi$, _ii)_
sample a prior $P\sim\mathcal{P}(A)$, _iii)_ for each task, $i=1,\dots,n$,
sample a model $f_{i}\sim P$.

Note that the inputs to $\mathfrak{Q}(\rho,\mathcal{Q})$ are data-dependent
and will be learned from data. In contrast, the input to
$\mathfrak{P}(\pi,\mathcal{P})$ are data-independent and need to be fixed
before seeing the data.

With these definitions, we state the following key lemma:

######  Lemma 4.2.

For any fixed meta-prior $\pi$, fixed hyper-prior function $\mathcal{P}$, any
$\delta>0$ and any $\lambda>0$, it holds with probability at least
$1-\frac{\delta}{2}$ over the sampling of the training datasets that for all
meta-posteriors $\rho\in\mathcal{M}(\mathcal{A})$ over algorithms, and for all
hyper-posterior functions
$\mathcal{Q}:\mathcal{A}\rightarrow\mathcal{M}(\mathcal{M}(\mathcal{F}))$:

$\displaystyle\begin{split}\widetilde{\mathcal{R}}(\rho)-\widehat{\mathcal{R}}(\rho)\leq&\
\
\frac{1}{\lambda}(\operatorname{\mathbf{KL}}(\mathfrak{Q}(\rho,\mathcal{Q})\|\mathfrak{P}(\pi,\mathcal{P})))\\\
&+\frac{1}{\lambda}\log(\frac{2}{\delta})+\frac{\lambda}{8nm}\end{split}$ (17)

###### Proof.

First for any task $i$ and any model $f_{i}$ we define:

$\displaystyle\Delta_{i}(f_{i})=\operatorname*{\mathbb{E}}_{z\sim
D_{i}}\ell(z,f_{i})-\frac{1}{|S_{i}|}\sum_{z\in S_{i}}\ell(z,f_{i}).$ (18)

By this definition and the definitions of $\widetilde{\mathcal{R}}$ and
$\widehat{\mathcal{R}}$ we have:

$\displaystyle\operatorname*{\mathbb{E}}_{(A,P,f_{1},\dots,f_{n})\sim\mathfrak{Q}(\rho,\mathcal{Q})}$
$\displaystyle\Big{[}\frac{1}{n}\sum_{i=1}^{n}\Delta_{i}(f_{i})\Big{]}=\widetilde{\mathcal{R}}(\rho)-\widehat{\mathcal{R}}(\rho)$
(19)

Using this equation and the _change of measure inequality_ (Seldin et al.,
2012) between the two distributions $\mathfrak{Q}(\rho,\mathcal{Q})$ and
$\mathfrak{P}(\pi,\mathcal{P})$, for any $\lambda>0$, any $\rho$ and any
$\mathcal{Q}$, we have:

$\displaystyle\begin{split}&\widetilde{\mathcal{R}}(\rho)-\widehat{\mathcal{R}}(\rho)-\frac{1}{\lambda}\operatorname{\mathbf{KL}}(\mathfrak{Q}(\rho,\mathcal{Q})||\mathfrak{P}(\pi,\mathcal{P}))\\\
&\leq\frac{1}{\lambda}\log\operatorname*{\mathbb{E}}_{(A,P,f_{1},\dots,f_{n})\sim\mathfrak{P}(\pi,\mathcal{P})}\prod_{i=1}^{n}e^{\frac{\lambda}{n}\Delta_{i}(f_{i})}\end{split}$
(20)

It remains to bound the right-hand of (20). Given that $\pi$ and $\mathcal{P}$
are data-independent, standard tools (in particular Hoeffding’s lemma and
Markov’s inequality) allow us to prove an upper bound that holds in high
probability with respect to the randomness of training datasets, from which
the statement in the lemma follows. Detailed steps are provided in Appendix A.
∎

The following lemma provides a split of the $\operatorname{\mathbf{KL}}$-term
from Lemma 4.2.

######  Lemma 4.3.

For the posterior and prior defined above we have:

$\displaystyle\operatorname{\mathbf{KL}}(\mathfrak{Q}(\rho,\mathcal{Q})||\mathfrak{P}(\pi,\mathcal{P}))=\operatorname{\mathbf{KL}}(\rho\|\pi)$
(21)
$\displaystyle+\operatorname*{\mathbb{E}}_{A\sim\rho}\Bigg{[}\operatorname{\mathbf{KL}}(\mathcal{Q}(A)\|\mathcal{P}(A))+\\!\\!\operatorname*{\mathbb{E}}_{P\sim\mathcal{Q}(A)}\sum_{i=1}^{n}\operatorname{\mathbf{KL}}(A(S_{i})||P)\Bigg{]}$

The proof makes use of the explicit construction of
$\mathfrak{P}(\pi,\mathcal{P})$ and $\mathfrak{Q}(\rho,\mathcal{Q})$. It can
be found in Appendix A.

#### Proof of Theorem 3.1

To get tight guarantees, we need to choose the value of $\lambda$ in Lemma 4.2
an optimal way dependent on the data. As the statement of the Lemma is not
uniform in $\lambda$, we do so approximately by allowing a fixed set of values
in the range $\\{1,...,4mn\\}$ and applying a union-bound argument for values
in this set. The theorem then follows by combining the result with Lemma 4.1
and using Lemma 4.3.

#### Proof sketch of Theorem 3.2

The proof is similar to the proof of Theorem 3.1. For the first part, we use
the same Lemma 4.1. For the second part, we use the fact that we have the same
data-independent prior for all algorithms. Due to this fact, we can remove
$\rho$ in the posterior function and prove a generalization bound that holds
uniformly for all algorithms applied to the datasets. Therefore we can bound
the multi-task generalization of all meta-posteriors $\rho$ without the term
$\operatorname{\mathbf{KL}}(\rho\|\pi)$, and the result is Theorem 3.2. For
the detailed proof, please see Appendix A.

##  5 Experimental Demonstration

While our main contribution in this work is theoretical, We also report on two
experimental studies that allow us to better relate our results to prior work.

###  5.1 Numerical evaluations of the bound

In this section, we numerically compare the tightness of our bound to those
from prior work, as far as this is possible. We adopt the same scenario as
Rothfuss et al. (2023), in which the goal is to improve the learning of linear
classifiers by means of meta-learning a distribution over priors.

In this experiment, each task is a binary classification task, which has a
task parameter $\mathbf{w}^{*}$ and given an input
$\mathbf{x}\sim{\mathcal{U}([-1,1]^{d})}$ outputs
$y=\mathbbm{1}({\mathbf{w}^{*}}^{\top}\mathbf{x}\leq 0)$. The task environment
is the set of vectors $\mathbf{w}^{*}\in\mathbb{R}^{d}$ with task distribution
$\tau=\mathcal{N}(\mathbf{w}^{*}|\mu_{\mathcal{T}},\sigma^{2}_{\mathcal{T}}\cdot\text{Id})$
for $\mu_{\mathcal{T}}=10\cdot\mathbf{1}$ and $\sigma_{\mathcal{T}}=3$. The
model set consists of linear classifiers,
$\mathcal{F}=\\{\mathbbm{1}(\mathbf{w}^{\top}\mathbf{x}\leq
0):\mathbf{w}\in\mathbb{R}^{d}\\}$, and the priors and posteriors are Gaussian
distributions over their weight vectors. Specifically, the priors have the
form $\mathcal{N}(\mathbf{w}|\mu_{P},\sigma_{P}^{2}\cdot\text{Id})$ with
$\sigma_{P}=10$, from which the posteriors are learned by minimizing a PAC-
Bayes bound with the logistic regression loss. The meta-learner learns a
Gaussian hyper-posterior over the mean of the priors ($\mu_{P})$, based on the
hyper-prior
$\mathcal{P}(\mu_{P})=\mathcal{N}(\mu_{P}|\mathbf{0},\sigma_{\mathcal{P}}^{2}\cdot\text{Id})$
with $\sigma_{\mathcal{P}}=20$. For background information on the experimental
setting, please see the original reference Rothfuss et al. (2023).

In Figure 1 we plot the numeric values of the right-hand side of our bound
(13), i.e. empirical loss plus the complexity terms, in the setting of $d=2$,
$m=5$, and different values of $n$. We also plot the corresponding values for
the bounds from Pentina & Lampert (2014); Amit & Meir (2018); Rothfuss et al.
(2021); Rezazadeh (2022); Guan & Lu (2022), as well as the actual quantities
of interest, the meta-test loss, and the meta-training loss. One can see that
our bound has the smallest value, i.e. is the tightest. It becomes non-vacuous
already for $n=10$ tasks, while the other bounds are still vacuous for $n<20$.

We would like to emphasize that this analysis compares the tightness of the
bounds just in the setting of prior-based meta-learning, because this is the
only setting in which previous works can provide a guarantee. The main
advantage of our result, however, is its applicability to many more settings,
where a numeric comparison is not possible, because previous works are not
applicable.

Figure 1: Numeric values of different meta-learning bounds (empirical loss
plus complexity terms) for the binary classification task described in Section
5.1. Values below $1$ are called _non-vacuous_.

###  5.2 Learning initialization as well as regularization

In Section 3.1 we argued that hybrid meta-learning scenarios can be
beneficial, for example, learning the initialization of a network as well as a
regularization term for its optimization. As empirical evidence for this
setting, we report on the standard experiments in the literature suggested by
Amit & Meir (2018), in which a stochastic neural network is learned for two
exemplary meta-learning scenarios, _shuffled pixel_ and _permuted labels_.
Both are image classification tasks based on the MNIST dataset (LeCun &
Cortes, 1998). In the former, tasks differ from each other by different
permutations of the input pixels at a fixed subset of locations. In the
latter, task differ from each other by different permutations of the label
space. In these experiments, there are 10 training tasks with 600 samples per
task. We evaluate the methods on 20 tasks with 100 samples per task. For
experimental details see Appendix B.

Previous works used this setting as a benchmark for PAC-Bayesian meta-learning
bounds in the following way: the learning rule, $Q(S,P)$, consists of first
initializing a stochastic network at the mean of the prior, $P$, and then
training the network by minimizing the right-hand side of a PAC-Bayes bound
using prior $P$, where the $\operatorname{\mathbf{KL}}$-divergence between the
prior and the learned model acts as a regularizer towards the prior mean. This
description shows that the prior is used in two different ways, for
initialization and as regularizer, even though it is not a priori clear why
the best choice for these two quantities would be to make them identical.

In our new framework the roles of initialization and regularization can easily
be separated, thereby allowing up to assess the above question quantitatively.
To explore this, we use a simple formalization, in which each algorithm
consists of two distributions $(P_{0},P_{1})$ over models. For learning a new
task, the stochastic neural network is initialized from $P_{0}$, and then
trained by minimizing a PAC-Bayes bound with $P_{1}$ as prior using gradient
descent. Formally, for each algorithm, we have
$\mathcal{Q}(A)=\mathcal{P}(A)=\delta_{P_{1}}$ , and $(\rho_{0},\rho_{1})$ as
meta-posterior, and $(\pi_{0},\pi_{1})$ as meta-prior, where
$\rho_{0},\pi_{0}$ are distributions over $P_{0}$ and $\rho_{1},\pi_{1}$ are
distributions over $P_{1}$.

For simplicity, we work with Gaussian distributions, and we learn their mean
and variance by the re-parametrization trick of Kingma et al. (2015). The
optimization is performed as in Amit & Meir (2018): one approximately
minimizes the meta-learning bound by optimizing for the hyper-posterior,
$\rho$ and for separate task posteriors, $Q_{1},\dots,Q_{n}$, for a fixed
number of epochs (originally 200). For our setup, we use the same
implementation, but with the difference that we have a meta-posterior over two
distributions.For the first 100 epoch we set them equal, mirroring the prior
work. Afterwards, however, fix the meta-posterior over $P_{0}$, initialize
$Q_{1},...,Q_{n}$ again by sampling from this distribution, and continue the
optimization for another 100 epochs. Note that this results in the same amount
of computation as the previous methods, but now split into first learn the
network initialization, and then the regularization term conditioned on the
learned initialization.

Table 2: Comparison between our mechanism with prior-based mechanisms. The
separation of initialization and regularization improves the performance for
_permuted labels (PL)_ , and achieves similar performance for the _shuffled
pixels (SP)_. Meta-Learning PAC Bayes Bounds: Test Error (%)
---
Bound | SP | PL
Independent learning |  28.9 $\pm$ 1.7 |  19.6 $\pm$ 1.5
(Amit & Meir, 2018) |  9.9 $\pm$ 0.9 | 13.7 $\pm$ 3.5
(Rezazadeh, 2022) | 11.2 $\pm$ 1.0 | 90.1 $\pm$ 5.6
(Guan & Lu, 2022) | 20.5 $\pm$ 1.1 | 89.9 $\pm$ 0.5
Ours |  9.9 $\pm$ 1.1 |  7.9 $\pm$ 1.7

We compare our results with the prior-based bounds of Amit & Meir (2018);
Rezazadeh (2022); Guan & Lu (2022), as well as independent learning. The
experimental results are shown in Table 2. One can see that for the _permuted
label_ setting, having different parameters reduce the test error. This shows
that the previous setups were indeed suboptimal, and it thereby confirms the
benefits of out framework’s added flexibility. In the _shuffled pixel_
setting, the added flexibility did not yield any benefits, as the system
learned almost identical parameters for the initialization and the
regularization term. Consequently, the results of our framework are
essentially the same as for previous ones. For more discussion on the results
we refer the reader to Appendix B.

##  6 Conclusion

We presented a new framework for the theoretical analysis of meta-learning (or
learning-to-learn) methods. Where previous approaches were limited to settings
that can be formulated as learning a prior distribution over models, our new
approach takes a more direct approach and formulates the knowledge transfer as
learning a preference for learning algorithms. Our main contributions are two
PAC-Bayesian generalization bounds that are applicable to essentially all
existing transfer mechanisms, including _model prototypes_ , _regularization_
, _representation learning_ , _hypernetworks_ , and the transfer of
_optimization methods_ or _hyperparameters_ , or combinations thereof. We
believe our approach will prove useful to put more practical meta-learning
methods onto solid theoretical foundation, and ideally to inspire improvement,
such as new forms of regularization, especially for the low-data regime.

## References

  * Alquier (2024) Alquier, P.  User-friendly introduction to PAC-Bayes bounds.  _Foundations and Trends in Machine Learning_ , 17(2):174–303, 2024.
  * Amit & Meir (2018) Amit, R. and Meir, R.  Meta-learning by adjusting priors based on extended PAC-Bayes theory.  In _International Conference on Machine Learning (ICML)_ , 2018.
  * Baxter (2000) Baxter, J.  A model of inductive bias learning.  _Journal of Artificial Intelligence Research (JAIR)_ , 12:149–198, 2000.
  * Denevi et al. (2019) Denevi, G., Ciliberto, C., Grazzi, R., and Pontil, M.  Learning-to-learn stochastic gradient descent with biased regularization.  In _International Conference on Machine Learning (ICML)_ , 2019.
  * Ding et al. (2021) Ding, N., Chen, X., Levinboim, T., Goodman, S., and Soricut, R.  Bridging the gap between practice and PAC-Bayes theory in few-shot meta-learning.  In _Conference on Neural Information Processing Systems (NeurIPS)_ , 2021.
  * Farid & Majumdar (2021) Farid, A. and Majumdar, A.  Generalization bounds for meta-learning via PAC-Bayes and uniform stability.  _Conference on Neural Information Processing Systems (NeurIPS)_ , 2021.
  * Finn et al. (2017) Finn, C., Abbeel, P., and Levine, S.  Model-agnostic meta-learning for fast adaptation of deep networks.  In _International Conference on Machine Learning (ICML)_ , 2017.
  * Friedman & Meir (2023) Friedman, L. and Meir, R.  Adaptive meta-learning via data-dependent PAC-Bayes bounds.  In _Conference on Lifelong Learning Agents (CoLLAs)_ , 2023.
  * Glorot & Bengio (2010) Glorot, X. and Bengio, Y.  Understanding the difficulty of training deep feedforward neural networks.  In _International Conference on Artificial Intelligence and Statistics (AISTATS)_ , 2010.
  * Guan & Lu (2022) Guan, J. and Lu, Z.  Fast-rate PAC-Bayesian generalization bounds for meta-learning.  In _International Conference on Machine Learning (ICML)_ , 2022.
  * Guedj (2019) Guedj, B.  A primer on PAC-Bayesian learning.  _arXiv preprint arXiv:1901.05353_ , 2019.
  * Hellström & Durisi (2022) Hellström, F. and Durisi, G.  Evaluated CMI bounds for meta learning: Tightness and expressiveness.  In _Conference on Neural Information Processing Systems (NeurIPS)_ , 2022.
  * Hellström et al. (2023) Hellström, F., Durisi, G., Guedj, B., and Raginsky, M.  Generalization bounds: Perspectives from information theory and PAC-Bayes.  _arXiv preprint arXiv:2309.04381_ , 2023.
  * Hochreiter et al. (2001) Hochreiter, S., Younger, A. S., and Conwell, P. R.  Learning to learn using gradient descent.  In _International Conference on Artificial Neural Networks (ICANN)_ , 2001.
  * Kingma et al. (2015) Kingma, D. P., Salimans, T., and Welling, M.  Variational dropout and the local reparameterization trick.  In _Conference on Neural Information Processing Systems (NeurIPS)_ , 2015.
  * LeCun & Cortes (1998) LeCun, Y. and Cortes, C.  MNIST handwritten digit database.  http://yann.lecun.com/exdb/mnist/, 1998.
  * Lee et al. (2019) Lee, K., Maji, S., Ravichandran, A., and Soatto, S.  Meta-learning with differentiable convex optimization.  In _IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019.
  * Li et al. (2017) Li, Z., Zhou, F., Chen, F., and Li, H.  Meta-SGD: Learning to learn quickly for few-shot learning.  _arXiv preprint arXiv:1707.09835_ , 2017.
  * Liu et al. (2021) Liu, T., Lu, J., Yan, Z., and Zhang, G.  PAC-Bayes bounds for meta-learning with data-dependent prior.  _arXiv preprint arXiv:2102.03748_ , 2021.
  * Maurer (2004) Maurer, A.  A note on the PAC Bayesian theorem.  _arXiv preprint arXiv:cs.LG/0411099_ , 2004.
  * Maurer (2009) Maurer, A.  Transfer bounds for linear feature learning.  _Machine Learning_ , 75(3):327–350, 2009.
  * Maurer et al. (2016) Maurer, A., Pontil, M., and Romera-Paredes, B.  The benefit of multitask representation learning.  _Journal of Machine Learning Research (JMLR)_ , 17(81):1–32, 2016.
  * McAllester (1998) McAllester, D. A.  Some PAC-Bayesian theorems.  In _Conference on Computational Learning Theory (COLT)_ , 1998.
  * Nichol et al. (2018) Nichol, A., Achiam, J., and Schulman, J.  On first-order meta-learning algorithms.  _arXiv preprint arXiv:1803.02999_ , 2018.
  * Pentina & Lampert (2014) Pentina, A. and Lampert, C. H.  A PAC-Bayesian bound for lifelong learning.  In _International Conference on Machine Learning (ICML)_ , 2014.
  * Pentina & Lampert (2015) Pentina, A. and Lampert, C. H.  Lifelong learning with non-iid tasks.  In _Conference on Neural Information Processing Systems (NeurIPS)_ , 2015.
  * Pérez-Ortiz et al. (2021) Pérez-Ortiz, M., Rivasplata, O., Shawe-Taylor, J., and Szepesvári, C.  Tighter risk certificates for neural networks.  _The Journal of Machine Learning Research_ , 22(1):10326–10365, 2021.
  * Ravi & Larochelle (2017) Ravi, S. and Larochelle, H.  Optimization as a model for few-shot learning.  In _International Conference on Learning Representations (ICLR)_ , 2017.
  * Rezazadeh (2022) Rezazadeh, A.  A unified view on PAC-Bayes bounds for meta-learning.  In _International Conference on Machine Learning (ICML)_ , 2022.
  * Riou et al. (2023) Riou, C., Alquier, P., and Chérief-Abdellatif, B.-E.  Bayes meets Bernstein at the meta level: an analysis of fast rates in meta-learning with PAC-Bayes.  _arXiv preprint arXiv:2302.11709_ , 2023.
  * Rothfuss et al. (2021) Rothfuss, J., Fortuin, V., Josifoski, M., and Krause, A.  PACOH: Bayes-optimal meta-learning with PAC-guarantees.  In _International Conference on Machine Learning (ICML)_ , 2021.
  * Rothfuss et al. (2023) Rothfuss, J., Josifoski, M., Fortuin, V., and Krause, A.  Scalable PAC-Bayesian Meta-Learning via the PAC-Optimal Hyper-Posterior: From Theory to Practice.  _Journal of Machine Learning Research (JMLR)_ , 2023.
  * Schmidhuber (1987) Schmidhuber, J.  Evolutionary principles in self-referential learning.  Diploma thesis, Technical University of Munich, Germany, 1987.
  * Scott et al. (2023) Scott, J., Zakerinia, H., and Lampert, C. H.  PeFLL: Personalized federated learning by learning to learn.  _arXiv preprint arXiv:2306.05515_ , 2023.
  * Seldin et al. (2012) Seldin, Y., Laviolette, F., Cesa-Bianchi, N., Shawe-Taylor, J., and Auer, P.  PAC-Bayesian inequalities for martingales.  _IEEE Transactions on Information Theory_ , 58(12):7086–7093, 2012.
  * Thrun & Pratt (1998) Thrun, S. and Pratt, L. (eds.).  _Learning to Learn_.  Kluwer Academic Press, 1998.
  * Tian & Yu (2023) Tian, P. and Yu, H.  Can we improve meta-learning model in few-shot learning by aligning data distributions?  _Knowledge-Based Systems_ , 277:110800, 2023.
  * Zhao et al. (2020) Zhao, D., Kobayashi, S., Sacramento, J., and von Oswald, J.  Meta-learning via hypernetworks.  In _NeurIPS Workshop on Meta-Learning (MetaLearn)_ , 2020.

##  Appendix A Proofs

In this section, we provide the proofs of the results in the main body of the
paper.

###  A.1 Proof of Theorem 3.1.

For the convenience of the reader we restate Theorem 3.1 here and then prove
it.

######  Theorem A.1.

For any fixed meta-prior $\pi\in\mathcal{M}(\mathcal{A})$, fixed hyper-prior
mapping $\mathcal{P}:\mathcal{A}\to\mathcal{M}(\mathcal{M}(\mathcal{F}))$ and
any $\delta>0$, it holds with probability at least $1-\delta$ over the
sampling of the training tasks, that for all meta-posterior distributions
$\rho\in\mathcal{M}(\mathcal{A})$ over algorithms, and for all hyper-posterior
mappings $\mathcal{Q}:\mathcal{A}\to\mathcal{M}(\mathcal{M}(\mathcal{F}))$ it
holds

$\displaystyle\mathcal{R}(\rho)\leq\widehat{\mathcal{R}}(\rho)+\sqrt{\frac{\operatorname{\mathbf{KL}}(\rho\|\pi)+\log(\frac{4\sqrt{n}}{\delta})}{2n}}+\sqrt{\frac{\operatorname{\mathbf{KL}}(\rho||\pi)+\operatorname*{\mathbb{E}}_{A\sim\rho}[C_{1}(A,\mathcal{Q},\mathcal{P})]+\log(\frac{8mn}{\delta})+1}{2mn}},$
(22)

with

$\displaystyle C_{1}(A,\mathcal{Q},\mathcal{P})=$
$\displaystyle\operatorname{\mathbf{KL}}(\mathcal{Q}(A)\|\mathcal{P}(A))+\operatorname*{\mathbb{E}}_{P\sim\mathcal{Q}(A)}\sum_{i=1}^{n}\operatorname{\mathbf{KL}}(A(S_{i})||P).$
(23)

The beginning of the proof coincides with the steps of the sketch in Section
4, while the later part provides additional details. As a reminder, we repeat
the definitions of our main objects of interest: the risk of a meta-posterior,
$\rho\in\mathcal{M}(\mathcal{A})$,

$\displaystyle\mathcal{R}(\rho)$
$\displaystyle=\operatorname*{\mathbb{E}}_{A\sim\rho}\operatorname*{\mathbb{E}}_{(S,D)\sim\tau}\operatorname*{\mathbb{E}}_{z\sim
D}\ell(z,A(S)),$ (24) its empirical analog,
$\displaystyle\widehat{\mathcal{R}}(\rho)$
$\displaystyle=\operatorname*{\mathbb{E}}_{A\sim\rho}\frac{1}{n}\sum_{i=1}^{n}\frac{1}{|S_{i}|}\sum_{z\in
S_{i}}\ell(z,A(S_{i}))$ (25) as well as the intermediate objective, which
represents the true risk of the training tasks:
$\displaystyle\widetilde{\mathcal{R}}(\rho)$
$\displaystyle=\operatorname*{\mathbb{E}}_{A\sim\rho}\frac{1}{n}\sum_{i=1}^{n}\operatorname*{\mathbb{E}}_{z\sim
D_{i}}\ell(z,A(S_{i})).$ (26)

We divide the proof into two parts. First, we bound the difference of the true
risks between training tasks and future tasks
$\mathcal{R}(\rho)-\widetilde{\mathcal{R}}(\rho)$. For the second part, we
bound the difference between the true risk and empirical risk of training
tasks $\widetilde{\mathcal{R}}(\rho)-\widehat{\mathcal{R}}(\rho)$, and by
combining the two bounds we obtain the final result.

#### Part I

For the first part we can use classical PAC-Bayes arguments, because
$\mathcal{R}(\rho)$ and $\widetilde{\mathcal{R}}(\rho)$ differ only in the
fact that one is an empirical average with respect to the tasks while the
other it is expectation. Consequently, one obtains:

######  Lemma A.2.

For all $\delta>0$ it holds with probability at least $1-\frac{\delta}{2}$
over the sampling of tasks that for all meta-posteriors
$\rho\in\mathcal{M}(\mathcal{A})$:

$\displaystyle\mathcal{R}(\rho)-\widetilde{\mathcal{R}}(\rho)\leq\sqrt{\frac{\operatorname{\mathbf{KL}}(\rho||\pi)+\log(\frac{4\sqrt{n}}{\delta})}{2n}}.$
(27)

###### Proof.

For each algorithm $A$ and task $T=(D,S)$ we define the loss as
$l_{\text{task}}(A,T)=\operatorname*{\mathbb{E}}_{z\sim D}\ell(z,A(S))$. For
this loss, $\widetilde{\mathcal{R}}(A)$ is the empirical risk, and
$\mathcal{R}(A)$ is the true risk. Applying the standard PAC-Bayes bounds
(Maurer, 2004; Pérez-Ortiz et al., 2021) to this setting results in this
lemma. ∎

#### Part II

We define the following two functions that produce distributions over
$\mathcal{A}\times\mathcal{M}(\mathcal{F})\times\mathcal{F}^{\otimes n}$, i.e.
they assigns joint probabilities to tuples, $(A,P,f_{1},...,f_{n})$, which
contain a algorithm, a prior over models, and $n$ models.

  * •

_Posterior $\mathfrak{Q}(\rho,\mathcal{Q})$:_ given as input a meta-posterior
$\rho$ over algorithms and a hyper-posterior mapping $\mathcal{Q}$ as input,
it outputs the distribution over
$\mathcal{A}\times\mathcal{M}(\mathcal{F})\times\mathcal{F}^{\otimes n}$ with
the following generating process: _i)_ sample an algorithm $A\sim\rho$, _ii)_
sample a prior $P\sim\mathcal{Q}(A)$, _iii)_ for each task, $i=1,\dots,n$,
sample a model $f_{i}\sim A(S_{i})$.

  * •

_Prior $\mathfrak{P}(\pi,\mathcal{P})$:_ given as input a meta-prior $\pi$
over algorithms and a hyper-prior mapping $\mathcal{P}$ as input, it outputs
the distribution over
$\mathcal{A}\times\mathcal{M}(\mathcal{F})\times\mathcal{F}^{\otimes n}$ with
the following generating process: _i)_ sample an algorithm $A\sim\pi$, _ii)_
sample a prior $P\sim\mathcal{P}(A)$, _iii)_ for each task, $i=1,\dots,n$,
sample a model $f_{i}\sim P$.

Note that the inputs to $\mathfrak{Q}(\rho,\mathcal{Q})$ are data-dependent
and will be learned using the data. In contrast, the input to
$\mathfrak{P}(\pi,\mathcal{P})$ are data-independent and need to be fixed
before seeing the data. With these definitions, we state the following key
lemma:

######  Lemma A.3.

For any fixed meta-prior $\pi\in\mathcal{M}(\mathcal{A})$, fixed hyper-prior
mapping $\mathcal{P}:\mathcal{A}\to\mathcal{M}(\mathcal{M}(\mathcal{F}))$, any
$\delta>0$, and any $\lambda>0$, it holds with probability at least
$1-\frac{\delta}{2}$ over the sampling of the training datasets that for all
meta-posteriors $\rho\in\mathcal{M}(\mathcal{A})$ over algorithms, and for all
hyper-posterior functions
$\mathcal{Q}:\mathcal{A}\rightarrow\mathcal{M}(\mathcal{M}(\mathcal{F}))$:

$\displaystyle\widetilde{\mathcal{R}}(\rho)-\widehat{\mathcal{R}}(\rho)$
$\displaystyle\leq\frac{1}{\lambda}\operatorname{\mathbf{KL}}\big{(}\mathfrak{Q}(\rho,\mathcal{Q})\|\mathfrak{P}(\pi,\mathcal{P})\big{)}+\frac{1}{\lambda}\log(\frac{2}{\delta})+\frac{\lambda}{8nm}.$
(28)

###### Proof.

First for any task $i$ and any model $f_{i}$ we define:

$\displaystyle\Delta_{i}(f_{i})=\operatorname*{\mathbb{E}}_{z\sim
D_{i}}\ell(z,f_{i})-\frac{1}{|S_{i}|}\sum_{z\in S_{i}}\ell(z,f_{i}).$ (29)

By this definition and the definitions of $\widetilde{\mathcal{R}}$ and
$\widehat{\mathcal{R}}$ we have:

$\displaystyle\operatorname*{\mathbb{E}}_{(A,P,f_{1},\dots,f_{n})\sim\mathfrak{Q}(\rho,\mathcal{Q})}$
$\displaystyle\Big{[}\frac{1}{n}\sum_{i=1}^{n}\Delta_{i}(f_{i})\Big{]}=\widetilde{\mathcal{R}}(\rho)-\widehat{\mathcal{R}}(\rho)$
(30)

Using this equation and the _change of measure inequality_ (Seldin et al.,
2012) between the two distributions $\mathfrak{Q}(\rho,\mathcal{Q})$ and
$\mathfrak{P}(\pi,\mathcal{P})$, for any $\lambda>0$, any
$\rho\in\mathcal{M}(\mathcal{A})$ and any $\mathcal{Q}$, we have:

$\displaystyle\begin{split}&\widetilde{\mathcal{R}}(\rho)-\widehat{\mathcal{R}}(\rho)-\frac{1}{\lambda}\operatorname{\mathbf{KL}}(\mathfrak{Q}(\rho,\mathcal{Q})||\mathfrak{P}(\pi,\mathcal{P}))\leq\frac{1}{\lambda}\log\operatorname*{\mathbb{E}}_{(A,P,f_{1},f_{2},...,f_{n})\sim\mathfrak{P}(\pi,\mathcal{P})}\prod_{i=1}^{n}e^{\frac{\lambda}{n}\Delta_{i}(f_{i})}\end{split}$
(31)

where the second inequality is due to the _change of measure inequality_
(Seldin et al., 2012).

By the construction of $\mathfrak{P}(\pi,\mathcal{P})$, we have

$\displaystyle\operatorname*{\mathbb{E}}_{S_{1},\dots,S_{n}}\operatorname*{\mathbb{E}}_{(A,P,f_{1},f_{2},...,f_{n})\sim\mathfrak{P}(\pi,\mathcal{P})}\prod_{i=1}^{n}e^{\frac{\lambda}{n}\Delta_{i}(f_{i})}=$
$\displaystyle\operatorname*{\mathbb{E}}_{S_{1},\dots,S_{n}}\operatorname*{\mathbb{E}}_{A\sim\pi}\operatorname*{\mathbb{E}}_{P\sim\mathcal{P}(A)}\operatorname*{\mathbb{E}}_{f_{1}\sim
P}\dots\operatorname*{\mathbb{E}}_{f_{n}\sim
P}\prod_{i=1}^{n}e^{\frac{\lambda}{n}\Delta_{i}(f_{i})},$ (32) and, because it
is independent of $S_{1},\dots,S_{n}$, we can rewrite this as
$\displaystyle=\operatorname*{\mathbb{E}}_{A\sim\pi}\operatorname*{\mathbb{E}}_{P\sim\mathcal{P}(A)}\operatorname*{\mathbb{E}}_{S_{1}}\operatorname*{\mathbb{E}}_{f_{1}\sim
P}e^{\frac{\lambda}{n}\Delta_{1}(f_{1})}\dots\operatorname*{\mathbb{E}}_{S_{n}}\operatorname*{\mathbb{E}}_{f_{n}\sim
P}e^{\frac{\lambda}{n}\Delta_{n}(f_{n})}.$ (33)
$\displaystyle=\operatorname*{\mathbb{E}}_{A\sim\pi}\operatorname*{\mathbb{E}}_{P\sim\mathcal{P}(A)}\prod_{i=1}^{n}\operatorname*{\mathbb{E}}_{S_{i}}\operatorname*{\mathbb{E}}_{f_{i}\sim
P}e^{\frac{\lambda}{n}\Delta_{i}(f_{i})}$ (34)

Each $\Delta_{i}(f_{i})$ is a bounded random variable with support in an
interval of size $1$. By Hoeffding’s lemma we have

$\displaystyle\operatorname*{\mathbb{E}}_{S_{i}}\operatorname*{\mathbb{E}}_{f_{i}\sim
P}e^{\frac{\lambda}{n}\Delta_{i}(f_{i})}\leq e^{\frac{\lambda^{2}}{8n^{2}m}}.$
(35)

Therefore, by combining (34) and (35) we have:

$\displaystyle\operatorname*{\mathbb{E}}_{S_{1},\dots,S_{n}}\operatorname*{\mathbb{E}}_{(A,P,f_{1},f_{2},...,f_{n})\sim\mathfrak{P}(\pi,\mathcal{P})}\prod_{i=1}^{n}e^{\frac{\lambda}{n}\Delta_{i}(f_{i})}\leq
e^{\frac{\lambda^{2}}{8nm}}.$ (36)

By Markov’s inequality, for any $\epsilon>0$ we have

$\displaystyle\mathbb{P}_{S_{1},\dots,S_{n}}\Big{(}\operatorname*{\mathbb{E}}_{(A,P,f_{1},f_{2},...,f_{n})\sim\mathfrak{P}(\pi,\mathcal{P})}\prod_{i=1}^{n}e^{\frac{\lambda}{n}\Delta_{i}(f_{i})}\geq
e^{\epsilon}\Big{)}\leq e^{\frac{\lambda^{2}}{8nm}-\epsilon}$ (37)

Hence by combining (31) and (37) we get for any $\epsilon$:

$\displaystyle\mathbb{P}_{S_{1},\dots,S_{n}}\Big{(}\exists{\rho,\mathcal{Q}}:\widetilde{\mathcal{R}}(\rho)-\widehat{\mathcal{R}}(\rho)-\frac{1}{\lambda}\operatorname{\mathbf{KL}}(\mathfrak{Q}(\rho,\mathcal{Q})||\mathfrak{P}(\pi,\mathcal{P}))\geq\frac{1}{\lambda}\epsilon\Big{)}\leq
e^{\frac{\lambda^{2}}{8nm}-\epsilon},$ (38)

or, equivalently, it holds for any $\delta>0$ with probability at least
$1-\frac{\delta}{2}$:

$\displaystyle\forall{\rho,\mathcal{Q}}:\widetilde{\mathcal{R}}(\rho)-\widehat{\mathcal{R}}(\rho)\leq\frac{1}{\lambda}\operatorname{\mathbf{KL}}(\mathfrak{Q}(\rho,\mathcal{Q})||\mathfrak{P}(\pi,\mathcal{P}))+\frac{1}{\lambda}\log(\frac{2}{\delta})+\frac{\lambda}{8nm}.$
(39)

∎

The following lemma splits the $\operatorname{\mathbf{KL}}$ term of (39) into
more interpretable quantities.

######  Lemma A.4.

For the posterior, $\mathfrak{Q}(\rho,\mathcal{Q})$, and prior,
$\mathfrak{P}(\pi,\mathcal{P})$, defined above it holds:

$\displaystyle\operatorname{\mathbf{KL}}(\mathfrak{Q}(\rho,\mathcal{Q})||\mathfrak{P}(\pi,\mathcal{P}))=\operatorname{\mathbf{KL}}(\rho\|\pi)+\operatorname*{\mathbb{E}}_{A\sim\rho}\Big{[}\operatorname{\mathbf{KL}}(\mathcal{Q}(A)\|\mathcal{P}(A))+\operatorname*{\mathbb{E}}_{P\sim\mathcal{Q}(A)}\sum_{i=1}^{n}\operatorname{\mathbf{KL}}(A(S_{i})||P)\Big{]}.$
(40)

###### Proof.

$\displaystyle\operatorname{\mathbf{KL}}(\mathfrak{Q}(\rho,\mathcal{Q})||\mathfrak{P}(\pi,\mathcal{P}))$
$\displaystyle=\operatorname*{\mathbb{E}}_{A\sim\rho}\Bigg{[}\operatorname*{\mathbb{E}}_{P\sim\mathcal{Q}(A)}\Big{[}\operatorname*{\mathbb{E}}_{f_{i}\sim
A(S_{i})}\ln\frac{\rho(A)\mathcal{Q}(A)(P)\prod_{i=1}^{n}A(S_{i})(f_{i})}{\pi(A)\mathcal{P}(A)(P)\prod_{i=1}^{n}P(f_{i})}\Big{]}\Bigg{]}$
(41)
$\displaystyle=\operatorname*{\mathbb{E}}_{A\sim\rho}\Big{[}\ln\frac{\rho(A)}{\pi(A)}\Big{]}+\operatorname*{\mathbb{E}}_{A\sim\rho}\Bigg{[}\operatorname*{\mathbb{E}}_{P\sim\mathcal{Q}(A)}\Big{[}\ln\frac{\mathcal{Q}(A)(P)}{\mathcal{P}(A)(P)}\Big{]}+\operatorname*{\mathbb{E}}_{P\sim\mathcal{Q}(A)}\Big{[}\sum_{i=1}^{n}\operatorname*{\mathbb{E}}_{f_{i}\sim
A(S_{i})}\ln\frac{A(S_{i})(f_{i})}{P(f_{i})}\Big{]}\Bigg{]}$ (42)
$\displaystyle=\operatorname{\mathbf{KL}}(\rho\|\pi)+\operatorname*{\mathbb{E}}_{A\sim\rho}\Bigg{[}\operatorname{\mathbf{KL}}(\mathcal{Q}(A)\|\mathcal{P}(A))+\operatorname*{\mathbb{E}}_{P\sim\mathcal{Q}(A)}\sum_{i=1}^{n}\operatorname{\mathbf{KL}}(A(S_{i})||P)\Bigg{]}.$
(43)

∎

#### Part III

We now combine the above parts to prove Theorem 3.1.

###### Proof.

To get tight guarantees, we need to choose the value of $\lambda$ in Lemma A.3
an optimal data-dependent way, but the statement of the Lemma holds only for
individual values of $\lambda$. Therefore, we first create an version of
inequality (28) by instantiating it for each $\lambda\in\Lambda$ with
$\Lambda=\\{1,\dots,4mn\\}$, and then applying a union-bound. It follows that

$\displaystyle\mathbb{P}_{S_{1},\dots,S_{n}}$
$\displaystyle\Big{(}\forall{\rho,\mathcal{Q},\lambda\in\Lambda}:\widetilde{\mathcal{R}}(\rho)-\widehat{\mathcal{R}}(\rho)\leq\frac{1}{\lambda}\Big{[}\operatorname{\mathbf{KL}}\big{(}\mathfrak{Q}(\rho,\mathcal{Q})||\mathfrak{P}(\pi,\mathcal{P})\big{)}+\frac{1}{\lambda}\log(\frac{8mn}{\delta})\Big{]}+\frac{\lambda}{8nm}\Big{)}\geq
1-\frac{\delta}{2}$ (44)

Note that for real-valued $\lambda>1$, it holds that
$\lfloor\lambda\rfloor\leq\lambda$ and
$\frac{1}{\lfloor\lambda\rfloor}\leq\frac{1}{\lambda-1}$. Thereby, we can
allow real-valued $\lambda$ and obtain

$\displaystyle\mathbb{P}_{S_{1},\dots,S_{n}}$
$\displaystyle\Big{(}\forall{\rho,\mathcal{Q},\lambda\in(1,4mn]}:\widetilde{\mathcal{R}}(\rho)-\widehat{\mathcal{R}}(\rho)\leq\underbrace{\frac{1}{\lambda-1}\Big{[}\operatorname{\mathbf{KL}}\big{(}\mathfrak{Q}(\rho,\mathcal{Q})||\mathfrak{P}(\pi,\mathcal{P})\big{)}+\log(\frac{8mn}{\delta})\Big{]}+\frac{\lambda}{8mn}}_{=:\Gamma(\lambda)}\Big{)}\geq
1-\frac{\delta}{2}$ (45)

For any choice of $\rho,\mathcal{Q}$, let
$\lambda^{*}=\sqrt{8mn(\operatorname{\mathbf{KL}}(\mathfrak{Q}(\rho,\mathcal{Q})||\mathfrak{P}(\pi,\mathcal{P}))+\log(\frac{8mn}{\delta}))+1}$.
If $\lambda^{*}>4mn$, that implies

$\displaystyle\sqrt{\frac{\operatorname{\mathbf{KL}}(\mathfrak{Q}(\rho,\mathcal{Q})||\mathfrak{P}(\pi,\mathcal{P}))+\log(\frac{8mn}{\delta})+1}{2mn}}>1.$
(46)

Otherwise, $\lambda^{*}\in(1,4mn]$, so inequality (45) holds, and we have

$\displaystyle\Gamma(\lambda^{*})<\sqrt{\frac{\operatorname{\mathbf{KL}}(\mathfrak{Q}(\rho,\mathcal{Q})||\mathfrak{P}(\pi,\mathcal{P}))+\log(\frac{8mn}{\delta})+1}{2mn}}.$
(47)

Therefore,

$\displaystyle\mathbb{P}_{S_{1},\dots,S_{n}}\Big{(}\forall{\rho,\mathcal{Q}}:\widetilde{\mathcal{R}}(\rho)-\widehat{\mathcal{R}}(\rho)\leq\sqrt{\frac{\operatorname{\mathbf{KL}}(\mathfrak{Q}(\rho,\mathcal{Q})||\mathfrak{P}(\pi,\mathcal{P}))+\log(\frac{8mn}{\delta})+1}{2mn}}\Big{)}\geq
1-\frac{\delta}{2}.$ (48)

In combination with Lemma A.4, with probability at least $1-\frac{\delta}{2}$
it holds for all
$\rho\in\mathcal{M}(\mathcal{A}),\mathcal{Q}:\mathcal{A}\to\mathcal{M}(\mathcal{F})$:

$\displaystyle\widetilde{\mathcal{R}}(\rho)-\widehat{\mathcal{R}}(\rho)\leq\sqrt{\frac{\operatorname{\mathbf{KL}}(\rho||\pi)+\operatorname*{\mathbb{E}}_{A\sim\rho}[C_{1}(A,\mathcal{Q},\mathcal{P})]+\log(\frac{8mn}{\delta})+1}{2mn}}.$
(49)

where $C_{1}(A,\mathcal{Q},\mathcal{P})$ is defined as in (23). Combining (49)
and Lemma A.2 by a union bound concludes the proof. ∎

###  A.2 Proof of Theorem 3.2.

We now restate and prove Theorem 3.2.

######  Theorem A.5.

For any fixed meta-prior $\pi\in\mathcal{M}(\mathcal{A})$, any fixed hyper-
prior $\mathcal{P}\in\mathcal{M}(\mathcal{M}(\mathcal{F}))$ and any
$\delta>0$, it holds with probability at least $1-\delta$ over the sampling of
the datasets, that for all meta-posterior distributions
$\rho\in\mathcal{M}(\mathcal{A})$ over algorithms, and for all hyper-posterior
functions
$\mathcal{Q}:\mathcal{A}\rightarrow\mathcal{M}(\mathcal{M}(\mathcal{F}))$ we
have

$\displaystyle\mathcal{R}(\rho)$
$\displaystyle\leq\widehat{\mathcal{R}}(\rho)+\sqrt{\frac{\operatorname{\mathbf{KL}}(\rho||\pi)+\log(\frac{4\sqrt{n}}{\delta})}{2n}}+\
\operatorname*{\mathbb{E}}_{A\sim\rho}\sqrt{\frac{C_{2}(A,\mathcal{Q},\mathcal{P})+\log(\frac{8mn}{\delta})+1}{2mn}},$
(50) with $\displaystyle C_{2}(A,\mathcal{Q},\mathcal{P})$
$\displaystyle=\operatorname{\mathbf{KL}}(\mathcal{Q}(A)\|\mathcal{P})+\operatorname*{\mathbb{E}}_{P\sim\mathcal{Q}(A)}\sum_{i=1}^{n}\operatorname{\mathbf{KL}}(A(S_{i})||P).$
(51)

The three-step proof largely follows that of Theorem 3.1, except for some
differences that emerge because the constant hyper-prior allows some arguments
to hold (with high probability over the datasets) uniformly for all algorithms
at the same time.

#### Part I

We bound the different $\mathcal{R}(\rho)$ and $\widetilde{\mathcal{R}}(\rho)$
the same way as in Lemma A.2.

#### Part II

We define the following two functions that produce distributions over
$\mathcal{M}(\mathcal{F})\times\mathcal{F}^{\otimes n}$, i.e. they assign
joint probabilities to tuples, $(P,f_{1},...,f_{n})$ that contain a prior over
models and $n$ models.

  * •

_Posterior $\mathfrak{Q}(A,\mathcal{Q}(A))$:_ given as input an algorithm
$A\in\mathcal{A}$ and a hyper-posterior mapping
$\mathcal{Q}:\mathcal{A}\to\mathcal{M}(\mathcal{F})$ as input, it outputs the
distribution over $\mathcal{M}(\mathcal{F})\times\mathcal{F}^{\otimes n}$ with
the following generating process: _i)_ sample a prior $P\sim\mathcal{Q}(A)$,
_ii)_ for each task, $i=1,\dots,n$, sample a model $f_{i}\sim A(S_{i})$.

  * •

_Prior $\mathfrak{P}(\mathcal{P})$:_ given a hyper-prior
$\mathcal{P}\in\mathcal{M}(\mathcal{F})$ as input, it outputs the distribution
over $\mathcal{M}(\mathcal{F})\times\mathcal{F}^{\otimes n}$ with the
following generating process: _i)_ sample a prior $P\sim\mathcal{P}(A)$, _ii)_
for each task, $i=1,\dots,n$, sample a model $f_{i}\sim P$.

######  Lemma A.6.

For any fixed meta-prior $\pi\in\mathcal{M}(\mathcal{A})$, fixed hyper-prior
$\mathcal{P}\in\mathcal{M}(\mathcal{M}(\mathcal{F}))$, any $\delta>0$, and any
$\lambda>0$, it holds with probability $1-\frac{\delta}{2}$ over the sampling
of datasets from training tasks that for all algorithms $A\in\mathcal{A}$ and
for all hyper-posterior functions
$\mathcal{Q}:\mathcal{A}\rightarrow\mathcal{M}(\mathcal{M}(\mathcal{F}))$:

$\displaystyle\widetilde{\mathcal{R}}(A)-\widehat{\mathcal{R}}(A)$
$\displaystyle\leq\frac{1}{\lambda}\operatorname{\mathbf{KL}}\big{(}\mathfrak{Q}(A,\mathcal{Q}(A))\|\mathfrak{P}(\mathcal{P})\big{)}+\frac{1}{\lambda}\log(\frac{2}{\delta})+\frac{\lambda}{8nm},$
(52) where $\displaystyle\widetilde{\mathcal{R}}(A)$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\operatorname*{\mathbb{E}}_{z\sim
D_{i}}\ell(z,A(S_{i})),\qquad\text{and}\qquad\widehat{\mathcal{R}}(A)=\frac{1}{n}\sum_{i=1}^{n}\frac{1}{|S_{i}|}\sum_{z\in
S_{i}}\ell(z,A(S_{i})).$ (53)

###### Proof.

First for any task $i$ and any model $f_{i}$ we define:

$\displaystyle\Delta_{i}(f_{i})=\operatorname*{\mathbb{E}}_{z\sim
D_{i}}\ell(z,f_{i})-\frac{1}{|S_{i}|}\sum_{z\in S_{i}}\ell(z,f_{i})$ (54)

By this definition and the definitions of $\widetilde{\mathcal{R}}$ and
$\widehat{\mathcal{R}}$ we have:

$\displaystyle\operatorname*{\mathbb{E}}_{(P,f_{1},f_{2},...,f_{n})\sim\mathfrak{Q}(A,\mathcal{Q}(A))}\Big{[}\frac{1}{n}\sum_{i=1}^{n}\Delta_{i}(f_{i})\Big{]}$
$\displaystyle=\widetilde{\mathcal{R}}(A)-\widehat{\mathcal{R}}(A)$ (55)

Using this equation and the _change of measure inequality_ (Seldin et al.,
2012) between the two distributions $\mathfrak{Q}(A,\mathcal{Q}(A))$ and
$\mathfrak{P}(\mathcal{P})$, for any $\lambda>0$, any $A\in\mathcal{A}$ and
any $\mathcal{Q}:\mathcal{A}\to\mathcal{M}(\mathcal{M}(\mathcal{F}))$, we
have:

$\displaystyle\widetilde{\mathcal{R}}(A)-\widehat{\mathcal{R}}(A)-\frac{1}{\lambda}\operatorname{\mathbf{KL}}\big{(}\mathfrak{Q}(A,\mathcal{Q}(A))||\mathfrak{P}(\mathcal{P})\big{)}$
$\displaystyle\leq\frac{1}{\lambda}\log\operatorname*{\mathbb{E}}_{(P,f_{1},f_{2},...,f_{n})\sim\mathfrak{P}(\mathcal{P})}\prod_{i=1}^{n}e^{\frac{\lambda}{n}\Delta_{i}(f_{i})}$
(56)

Because $\mathfrak{P}(\mathcal{P})$ is independent of $S_{1},...,S_{n}$, we
have

$\displaystyle\operatorname*{\mathbb{E}}_{S_{1},\dots,S_{n}}\operatorname*{\mathbb{E}}_{(P,f_{1},f_{2},...,f_{n})\sim\mathfrak{P}(\pi,\mathcal{P})}\prod_{i=1}^{n}e^{\frac{\lambda}{n}\Delta_{i}(f_{i})}$
$\displaystyle=\operatorname*{\mathbb{E}}_{S_{1},\dots,S_{n}}\operatorname*{\mathbb{E}}_{P\sim\mathcal{P}}\operatorname*{\mathbb{E}}_{f_{1}\sim
P}\dots\operatorname*{\mathbb{E}}_{f_{n}\sim
P}\prod_{i=1}^{n}e^{\frac{\lambda}{n}\Delta_{i}(f_{i})}$ (57)
$\displaystyle=\operatorname*{\mathbb{E}}_{P\sim\mathcal{P}}\operatorname*{\mathbb{E}}_{S_{1}}\operatorname*{\mathbb{E}}_{f_{1}\sim
P}e^{\frac{\lambda}{n}\Delta_{1}(f_{1})}\dots\operatorname*{\mathbb{E}}_{S_{n}}\operatorname*{\mathbb{E}}_{f_{n}\sim
P}e^{\frac{\lambda}{n}\Delta_{n}(f_{n})}$ (58)
$\displaystyle=\operatorname*{\mathbb{E}}_{P\sim\mathcal{P}}\prod_{i=1}^{n}\operatorname*{\mathbb{E}}_{S_{i}}\operatorname*{\mathbb{E}}_{f_{i}\sim
P}e^{\frac{\lambda}{n}\Delta_{i}(f_{i})}$ (59)

Each $\Delta_{i}(f_{i})$ is a bounded random variable with support in an
interval of size $1$. By Hoeffding’s lemma we have

$\displaystyle\operatorname*{\mathbb{E}}_{S_{i}}\operatorname*{\mathbb{E}}_{f_{i}\sim
P}e^{\frac{\lambda}{n}\Delta_{i}(f_{i})}\leq e^{\frac{\lambda^{2}}{8n^{2}m}}.$
(60)

Therefore by combining (59) and (60) we have:

$\displaystyle\operatorname*{\mathbb{E}}_{S_{1},\dots,S_{n}}\operatorname*{\mathbb{E}}_{(P,f_{1},f_{2},...,f_{n})\sim\mathfrak{P}(\mathcal{P})}\prod_{i=1}^{n}e^{\frac{\lambda}{n}\Delta_{i}(f_{i})}\leq
e^{\frac{\lambda^{2}}{8nm}}.$ (61)

By Markov’s inequality, for any $\epsilon>0$ we have

$\displaystyle\mathbb{P}_{S_{1},\dots,S_{n}}\Big{(}\operatorname*{\mathbb{E}}_{(P,f_{1},f_{2},...,f_{n})\sim\mathfrak{P}(\mathcal{P})}\prod_{i=1}^{n}e^{\frac{\lambda}{n}\Delta_{i}(f_{i})}\geq
e^{\epsilon}\Big{)}\leq e^{\frac{\lambda^{2}}{8nm}-\epsilon}$ (62)

Hence by combining (56) and (62) we get

$\displaystyle\mathbb{P}_{S_{1},\dots,S_{n}}\Big{(}\exists{A,\mathcal{Q}}:\widetilde{\mathcal{R}}(A)-\widehat{\mathcal{R}}(A)-\frac{1}{\lambda}\operatorname{\mathbf{KL}}(\mathfrak{Q}(A,\mathcal{Q}(A))||\mathfrak{P}(\mathcal{P}))\geq\frac{1}{\lambda}\epsilon\Big{)}\leq
e^{\frac{\lambda^{2}}{8nm}-\epsilon},$ (63)

or, equivalently, it holds for any $\delta>0$ with probability at least
$1-\frac{\delta}{2}$:

$\displaystyle\forall{A,\mathcal{Q}}:\quad\widetilde{\mathcal{R}}(A)-\widehat{\mathcal{R}}(A)\leq\frac{1}{\lambda}\operatorname{\mathbf{KL}}(\mathfrak{Q}(A,\mathcal{Q}(A))||\mathfrak{P}(\mathcal{P}))+\frac{1}{\lambda}\log(\frac{2}{\delta})+\frac{\lambda}{8nm}$
(64)

∎

The following lemma splits the $\operatorname{\mathbf{KL}}$ term of (64) into
more interpretable quantities.

######  Lemma A.7.

For the posterior, $\mathfrak{Q}(A,\mathcal{Q}(A))$, and prior,
$\mathfrak{P}(\mathcal{P})$, defined above it holds:

$\displaystyle\begin{split}&\operatorname{\mathbf{KL}}\big{(}\mathfrak{Q}(A,\mathcal{Q}(A))||\mathfrak{P}(\mathcal{P})\big{)}=\operatorname{\mathbf{KL}}(\mathcal{Q}(A)\|\mathcal{P})+\operatorname*{\mathbb{E}}_{P\sim\mathcal{Q}(A)}\sum_{i=1}^{n}\operatorname{\mathbf{KL}}(A(S_{i})||P)\end{split}$
(65)

###### Proof.

$\displaystyle\operatorname{\mathbf{KL}}(\mathfrak{Q}(A,\mathcal{Q}(A))||\mathfrak{P}(\mathcal{P}))$
$\displaystyle=\operatorname*{\mathbb{E}}_{P\sim\mathcal{Q}(A)}\Big{[}\operatorname*{\mathbb{E}}_{f_{i}\sim
A(S_{i})}\ln\frac{\mathcal{Q}(A)(P)\prod_{i=1}^{n}A(S_{i})(f_{i})}{\mathcal{P}(P)\prod_{i=1}^{n}P(f_{i})}\Big{]}$
(66)
$\displaystyle=\operatorname*{\mathbb{E}}_{P\sim\mathcal{Q}(A)}\Big{[}\ln\frac{\mathcal{Q}(A)(P)}{\mathcal{P}(P)}\Big{]}+\operatorname*{\mathbb{E}}_{P\sim\mathcal{Q}(A)}\Big{[}\sum_{i=1}^{n}\operatorname*{\mathbb{E}}_{f_{i}\sim
A(S_{i})}\ln\frac{A(S_{i})(f_{i})}{P(f_{i})}\Big{]}\Bigg{]}$ (67)
$\displaystyle=\operatorname{\mathbf{KL}}(\mathcal{Q}(A)\|\mathcal{P})+\operatorname*{\mathbb{E}}_{P\sim\mathcal{Q}(A)}\sum_{i=1}^{n}\operatorname{\mathbf{KL}}(A(S_{i})||P)$
(68)

∎

#### Part III

We now finish the proof of Theorem 3.2 by combining the above results.

###### Proof.

By applying a union bound for all the values of $\lambda\in\Lambda$ with
$\Lambda=\\{1,\dots,4mn\\}$ we obtain that

$\displaystyle\mathbb{P}_{S_{1},\dots,S_{n}}\Big{(}\forall{A,\mathcal{Q}}:\widetilde{\mathcal{R}}(A)-\widehat{\mathcal{R}}(A)$
$\displaystyle\leq\sqrt{\frac{\operatorname{\mathbf{KL}}\big{(}\mathfrak{Q}(A,\mathcal{Q}(A))||\mathfrak{P}(\mathcal{P})\big{)}+\log(\frac{8mn}{\delta})+1}{2mn}}\Big{)}\geq
1-\frac{\delta}{2}.$ (69)

Because this inequality holds (with high probability over the datasets) for
all algorithms at the same time, it also holds in expectation over algorithms
with respect to any distribution. Therefore we have:

$\displaystyle\mathbb{P}_{S_{1},\dots,S_{n}}\Big{(}\forall{\rho,\mathcal{Q}}:\operatorname*{\mathbb{E}}_{A\sim\rho}[\widetilde{\mathcal{R}}(A)-\widehat{\mathcal{R}}(A)]\leq\operatorname*{\mathbb{E}}_{A\sim\rho}\sqrt{\frac{\operatorname{\mathbf{KL}}(\mathfrak{Q}(A,\mathcal{Q}(A))||\mathfrak{P}(\mathcal{P}))+\log(\frac{8mn}{\delta})+1}{2mn}}\Big{)}\geq
1-\frac{\delta}{2},$ (70)

or, equivalently,

$\displaystyle\mathbb{P}_{S_{1},\dots,S_{n}}\Big{(}\forall{\rho,\mathcal{Q}}:\widetilde{\mathcal{R}}(\rho)-\widehat{\mathcal{R}}(\rho)\leq\operatorname*{\mathbb{E}}_{A\sim\rho}\sqrt{\frac{\operatorname{\mathbf{KL}}(\mathfrak{Q}(A,\mathcal{Q}(A))||\mathfrak{P}(\mathcal{P}))+\log(\frac{8mn}{\delta})+1}{2mn}}\Big{)}\geq
1-\frac{\delta}{2}.$ (71)

In combination with Lemma A.7, with probability at least $1-\frac{\delta}{2}$
we have for all
$\rho\in\mathcal{M}(\mathcal{A}),\mathcal{Q}:\mathcal{A}\to\mathcal{M}(\mathcal{M}(\mathcal{F}))$:

$\displaystyle\widetilde{\mathcal{R}}(\rho)-\widehat{\mathcal{R}}(\rho)\leq\operatorname*{\mathbb{E}}_{A\sim\rho}\sqrt{\frac{C_{2}(A,\mathcal{Q},\mathcal{P})+\log(\frac{8mn}{\delta})+1}{2mn}}$
(72)

where $C_{2}(A,\mathcal{Q},\mathcal{P})$ is defined as in (51). Combining (72)
and Lemma A.2 concludes the proof. ∎

##  Appendix B Experimental details

In this section, we provide the details of our experiments.

###  B.1 Setup

We follow the experimental setup proposed in Amit & Meir (2018) for
benchmarking meta-learning methods. The experiment consists of two types of
tasks based on the MNIST dataset (LeCun & Cortes, 1998). In the first one,
each task is the MNIST classification task with a task-specific permutation in
the labels. In the second experiment, each task has the MNIST images as
samples, but a task-specific shuffle is applied to a subset of 200 pixels of
the input. In both cases, there are 10 training tasks and 20 test tasks. We
use 600 samples per training task and 100 samples per test task. This choice
corresponds to a setup in which independent learning cannot be expected to
provide good performance (the number of samples per task is small), and meta-
learning is necessary.

###  B.2 Meta-learning algorithm

As discussed in Section 2, the meta-learning mechanism introduced in Amit &
Meir (2018) is to learn a hyper-posterior over priors in the training phase.
For a future task, they minimize a PAC-Bayes bound based on this prior. As
mentioned in Section 5 they train a neural network and use the same prior as
the initialization point. This setup does not allow learning an initialization
different from the prior used for regularization.

To show the benefits of the additional freedom provided by our framework, we
use the same procedure except that we learn a separate initialization for the
network which can differ from the prior used in the objective, as discussed in
Sections 3.1 and 5. In the stochastic setting, we learn a meta-posterior
$\rho$ over the initialization prior and the regularization prior in the
training phase. For future tasks, we sample the two distributions
$(P_{0},P_{1})$ from $\rho$, initialize our stochastic neural network by
$P_{0}$, and optimize a PAC-Bayes bound with prior $P_{1}$. Note that the meta
learner is free to make use of the added flexibility by learning $P_{0}$
different from $P_{1}$, or to recover the previous setup by learning $P_{0}$
identical to $P_{1}$. We do not have to fear overfitting from the larger set
of parameters, because the objective is based on a generalization bound that
enforces appropriate regularization.

We use Gaussians for all distributions, which allows us to compute the
complexity terms in closed form. More precisely, let $d$ be the number of
weights in our neural network and we represent the prior and posteriors by
their mean $\mu_{i}$ and the log variance value $\log\sigma_{i}$ for the
weight $w_{i}$. Formally, we represent each $\rho$ as
$\rho_{0}\times\rho_{1}$, which $\rho_{i}$ is a distribution over $P_{i}$, and
has the form of $\mathcal{N}(\theta_{i},\kappa_{\rho}^{2}I_{2d\times 2d})$. We
use a fixed parameter for $\kappa_{\rho}$, and we learn the means
$\theta_{i}$. The meta-priors also have the same form, i.e.
$\pi=\pi_{0}\times\pi_{1}$ and
$\pi_{i}=\mathcal{N}(0,\kappa_{\pi}^{2}I_{2d\times 2d})$, with fixed
$\kappa_{\pi}$.

To use our generalization bounds for this mechanism, we apply Theorem 3.1
(with $\delta=0.1$) and we set we
$\mathcal{Q}(P_{0},P_{1})=\mathcal{P}(P_{0},P_{1})=\delta_{P_{1}}$. The result
is a bound

$\displaystyle\mathcal{R}(\rho)$
$\displaystyle\leq\widehat{\mathcal{R}}(\rho)+\sqrt{\frac{\operatorname{\mathbf{KL}}(\rho\|\pi)+\log(\frac{4\sqrt{n}}{\delta})}{2n}}+\sqrt{\frac{\operatorname{\mathbf{KL}}(\rho\|\pi)+\operatorname*{\mathbb{E}}_{(P_{0},P_{1})\sim\rho}\sum_{i=1}^{n}\operatorname{\mathbf{KL}}(A(S_{i})||P_{1})]+\log(\frac{8mn}{\delta})+1}{2mn}}$
(73)

in which $\operatorname{\mathbf{KL}}(\rho\|\pi)$ has the following form:

$\displaystyle\operatorname{\mathbf{KL}}(\rho\|\pi)=\frac{4d\kappa_{\rho}+\|\theta_{0}\|^{2}+\|\theta_{1}\|^{2}}{2\kappa_{\pi}}-2d+4d\log(\frac{\kappa_{\pi}}{\kappa_{\rho}})$
(74)

Training phase. In the training phase, we optimize the right-hand side of (73)
to find the meta-posterior $\rho$. As in Amit & Meir (2018) we use the Monte
Carlo method to approximate the values for calculating the expectation terms,
and use the re-parametrization trick (Kingma et al., 2015) to optimize the
expected value of the $\operatorname{\mathbf{KL}}(A(S_{i})||P_{1})$ terms.

To find $\rho$ we follow the optimization procedure defined in Amit & Meir
(2018). For each task $i$, we assign a stochastic neural network $Q_{i}$,
initiated in the following way: The mean of each weight is initiated randomly
with the Glorot method (Glorot & Bengio, 2010), and the $\log$-variance of
each weight is initiated randomly from $\mathcal{N}(-10,0.1^{2})$.

In their original optimization procedure Amit & Meir (2018) optimize their
objective for 200 epochs to find the hyper-posterior. Because our meta-
distribution has two parts: one for initialization and one for regularization,
we add the following change to this procedure: In the first 100 epochs, we
assume $\rho_{0}$ and $\rho_{1}$ are equal and we minimize the bound to find
$\rho_{0}=\rho_{1}$ and posteriors $Q_{i}$s. After 100 epochs, we fix
$\rho_{0}$, initialize the $Q_{i}$s by sampling from $\rho_{0}$ (Since
$\rho_{0}$ is supposed to be the meta-distribution over initialization prior)
and optimize the bound for $\rho_{1}$ and the $Q_{i}$s for another 100 epochs.

Future tasks. For a future task $T_{\text{new}}$ with its training dataset
$S_{\text{new}}$ we learn its posterior as follows: we sample the
initialization prior from $\rho_{0}$ to initiate a stochastic neural network
$Q_{\text{new}}$. Then, similar to previous works, we optimize the following
PAC-Bayesian bound with the prior $P_{1}$ sampled from $\rho_{1}$ for 100
epochs.

$\displaystyle\widehat{\mathcal{R}}(Q_{\text{new}})+\sqrt{\frac{\operatorname{\mathbf{KL}}(Q_{\text{new}}||P_{1})+\log(\frac{8m}{\delta})+1}{2m}}$
(75)

We use Monte Carlo sampling to approximate the expectations.

###  B.3 Implementation and Numeric Results

Our implementation is based on the code of Amit & Meir (2018), except that we
fixed a bug in their computation of the
$\operatorname{\mathbf{KL}}$-divergences, which was also present in later
works derived from it. Furthermore, we corrected an issue with how the
gradients of the objective in Rezazadeh (2022) were computed. All experiments
were done with the corrected implementation, which we will make publicly
available.

We use the same network architectures as proposed Amit & Meir (2018): a small
ConvNet with two convolutional layers and one fully-connected layer for the
_permuted labels_ task, and a three-layer fully-connected network for the
_shuffled pixels_ task. For further details on the architecture, see the
original reference. We used the Adam optimizer with a learning rate of
$10^{-3}$ and the number of Monte Carlo iterations was 1 in all experiments.
For the fixed parameters of the minimization objective, we put $\delta=0.1$,
and for the variances of meta-prior $\pi$ and meta-posterior $\rho$, we set
$\kappa_{\pi}=10^{2}$ and $\kappa_{\rho}=10^{-3}$. Moreover, the batch size is
128 and the used loss function is Cross-Entropy loss.

The experimental results are shown in the Table 2. We compare our results with
the following prior-based works: The (MLAP-M) bound of Amit & Meir (2018), The
Classic bound of Rezazadeh (2022), and the kl-bound of Guan & Lu (2022). The
results confirm that the extra flexibility of our framework can be beneficial.
Specifically, in the _permuted labels_ experiment, having a different
initialization and regularization helps a lot. In the _shuffled pixel_
setting, the flexibility does not help and we get the same performance as the
previous methods. A noteworthy feature of Table 2 is the high error of
Rezazadeh (2022) and Guan & Lu (2022) in the permuted labels task. These are a
consequence of the fact that the complexity terms in their bounds are very big
in low-data regime that we are interested in (where meta-learning is meant to
help). As a result, the optimization mainly attempt as reducing the complexity
terms, which leads to underfitting and classification performance as good as a
random guess ($\approx 90\%$ error). The same problem occurs for the Catoni-
type bound in Guan & Lu (2022) for both experimental settings, so we do not
report its results.

#### Comparison of our bounds with and without different initialization and
regularization:

We present an ablation study in Table 3. To see if the added flexibility of
our setting is indeed responsible for the improved results rather than the
different objective compared to prior work, we compare our results with the
case that the two distributions are equal when we use the distribution learned
for the regularization for the initialization as well. As one can see, using
different distributions for initialization and regularization reduce the error
in the _permuted labels_ task, but for _shuffled pixels_ they stay the same.

Bound | Shuffled Pixel | Permuted Label
---|---|---
initialization identical to prior ($\rho_{0}=\rho_{1}$) |  10.1 $\pm$ 1.3 |  15.5 $\pm$ 4.3
initialization can differ from prior |  9.9 $\pm$ 1.1 |  7.9 $\pm$ 1.7
Table 3: The ablation study to confirm that the gained performance is due to
separate initialization and regularization. We compare our method with the
case if we use the distributions in the end of our training procedure both as
the initialization and regularization. As one can see, having different
distributions leads to better performance in one of the tasks.