Fast Rate Bounds for Multi-Task and Meta-Learning with Different Sample Sizes
Authors: Hossein Zakerinia
Christoph H. Lampert
Venue: NeurIPS 2025 poster ()
Keywords: Multitask learning
generalization bounds
PAC-Bayes
fast-rate
unbalanced
Primary area: theory
TL;DR: We study fast-rate generalization bounds for multi-task and meta-learning with unbalanced task sizes, showing key differences with the balanced setting and provide new results for the unbalanced setting.

Abstract: We present new fast-rate PAC-Bayesian generalization bounds for multi-task and meta-learning in the unbalanced setting, i.e. when the tasks have training sets of different sizes, as is typically the case in real-world scenarios. Previously, only standard-rate bounds were known for this situation, while fast-rate bounds were limited to the setting where all training sets are of equal size. Our new bounds are numerically computable as well as interpretable, and we demonstrate their flexibility in handling a number of cases where they give stronger guarantees than previous bounds. Besides the bounds themselves, we also make conceptual contributions: we demonstrate that the unbalanced multi-task setting has different statistical properties than the balanced situation, specifically that proofs from the balanced situation do not carry over to the unbalanced setting. Additionally, we shed light on the fact that the unbalanced situation allows two meaningful definitions of multi-task risk, depending on whether all tasks should be considered equally important or if sample-rich tasks should receive more weight than sample-poor ones.

Fast Rate Bounds for Multi-Task and Meta-Learning with Different Sample Sizes
Hossein Zakerinia Institute of Science and Technology Austria (ISTA)
hossein wakerinia@ista..aa.
Christoph H. Lampert
Institute of Science and Technology Austria (ISTA)
chl@ista. ac.at
Abstract
We present new fast-rate PAC-Bayesian generalization bounds for multi-task and meta-learning in the unbalanced setting, i.e. when the tasks have training sets of different sizes, as is typically the case in real-world scenarios. Previously, only standard-rate bounds were known for this situation, while fast-rate bounds were limited to the setting where all training sets are of equal size. Our new bounds numerically computable well as interpretable, and demonstrate their flexibility in handling a number of cases where they give stronger guarantees than previous bounds. Besides the bounds themselves, we also make conceptual contributions: we demonstrate that the unbalanced multi-task setting has different statistical properties than the balanced situation, specifically that proofs from the balanced situation do not carry over to the unbalanced setting. Additionally,
we shed light on the fact that the unbalanced situation allows two meaningful definitions of multi task risk, depending on whether all tasks should be considered equally important or if sample-rich tasks should receive more weight than sample- poor ones.
Introduction
In multi-task learning (MTL) multiple related tasks are Iearned jointly, with the goal of improving generalization performance compared learning each task separately. As a result, MTL is particu- larly promising in settings where tasks are individually data-scarce but collectively rich in shared information, such as personalized Internet services, healthcare applications, or autonomous driving. Due to its fundamental nature, aspects of MTL also influence many other recent developments in the field of machine learning, such distributed learning /Verbraeken al., 2020), federated learning (Zhao al. 2018 Kairouz et al. 2021), multi-agent learning (Gronauer & Diepold (2022) or meta-learning (Hospedales al. 2021). l). Besides numerous algorithmic contributions, there also rich collection of results on the theoretical properties of MTL, in particular the improved generalization guarantees it provides compared to single-task learning.
Recent works on the generalization properties of machine learning models are often stated in the framework of PAC-Bayesian generalization bounds (McAllester 1998). In contrast to classical approaches, such as VC-theory (Vapnik & Chervonenkis] 1971) or Rademacher complexity (Bartlett
Mendelson] 2002), these tend to provide tighter results with the potential to only provide structural insight but even be numerically informative (i.e. non-vacuous) (Lotfi et al. 2022 2024).
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

For MTL, number of PAC-Bayesian generalization guarantees have been derived, often in combina- tion with related results for meta-learning. Initially. these were in the standard-rate setting (Pentina & Lampert 2014 2015 Amit & Meir 2018; Rothfuss et al. (023). with convergence rates at best O(vI/M), ). where M is the total number of training data points.
Quite recently, also some fast-rate bounds for MTL were developed with convergence rates up to O(I/M) (Guan & Lu 2022 Zakerinia et al., 2025). However, there is a fundamental limitation: existing f'as--rate bounds for MTL hold only if all tasks have the same number of samples. This an unrealistic restriction for practical settings, such as federated learning or healthcare.
In this work, we close this surprising gap in the literature: we prove fast-rate bounds for multi-task learning, for which tasks can have different numbers of samples (called unbalanced), for both of the so-called kl-style (Seeger 2002 Maurer 2004) as well as "Catoni-style" (Catoni, (007) bounds. However, our contribution not only technical, but also conceptual: first, we demonstrate that the unbalanced setting is not simply a minor variant of the balanced one, but has its own statistical properties. Specifically, the results and proot's of the existing fast rate bound do not carry over to the unbalanced setting, but f'ast-rate bounds for unbalanced multi-task learning are possible. Consequently, for our results, we establish new path for proving fast-rate bounds that we expect to be of independent interest also for other situations. Second, we identify the previously overlooked fact that the unbalanced setting allows for not just one but two meaningful definitions for the multi talti-task risk: dask-centric or sample-centrie. The task-centric risk assigns equal importance to each task. This makes sense, for example, if tasks are individual customers, and one wants to give each of them the best possible experience. The sample-centric risk assigns weights to tasks proportionally to how many training data points they have. This makes sense when the core aim to make as many correct predictions as possible, e.g. when tasks are products and samples are individual sales. Finally, we also extend our results to the meta-learning setting (Schmidhuber) 1987, Baxter 2000).
In summary, our main contributions are the first fast-rate generalization bounds for unbalanced multi-task learning, both in the task-centric and the sample-centric setting. As an additional contribution, we provide new insights into the statistical properties of these learning settings, and a numeric analysis of their potential, in particular in comparison to existing standard-rat bounds.
2 Background
Multi-task and Meta-learning. Machine learning tasks can be described triples, t (D, E). where D is a data distribution, S is a dataset of m i.i.d. samples from D, and E is a loss function in [0, 1]. Learning a task means finding model, f. from family of models, F, that has a small risk (expected loss), R())= = EE-D {(ʃ, =), with respect to the distribution D. In standard (single-task) learning, the learning algorithm can only use the dataset S to determine f. Typically does so by minimizing the training risk R(()) = regularization terms.
{(f, 21), potentially in combination with some m =
1
In multi-task learning (MTL) (Caruana 1997). D. multiple tasks, (1,-.., ln. are given. The goal is to learn individual models f1,...,Ju for the given tasks, but the learning algorithm can do so jointly, using the data from all tasks simultaneouslly The implicit assumption is that the different tasks are related and that sharing information across them could improve performance. This reflects how humans often learn: by leveraging shared structures and knowledge across tasks learn more efficiently. In this work, we refer to the number of tasks as n and the number of training samples for task i as m,.
Meta-learning (Schmidhuber) 1987). or learning to learn TThrun & Pratt 1998), extends multi-task learning the setting where, in addition to the observed tasks, there will also be future tasks that are not observed yet. The goal is to use the observed tasks' data to find a learning algorithm A from set of possible algorithms A that will learn good models future tasks. To theoretically study meta-learning meta-learning, one formalizes the relationship between tasks by assuming the existence of an environment of tasks T and an (unknown) environment distribution 7, from which both the observed training tasks and future tasks are i.i.d. samples (Baxter 2000).
PAC-Bayesian bounds. PAC-Bayesian generalization bounds MMAAllester 1998). i.e. guarantees for the generalization gap of stochastic models, have gained significant interest in recent years,

---

particularly for their ability to provide non-vacuous generalization bounds for neural networks (Dziugaite Roy, 2017 Loth et al., 2022), unlike traditional approaches such as VC dimension (Vapnik & Chervonenkis, 1971) or Rademacher complexity (Bartlett & Mendelson 2002).
Stochastic models are parametrized
distribution (also called posterior) over the hypothesis set. For any distribution, Q M(F), its loss is the expected loss of models drawn according to Q. i.c. ({Q)2) = E {(f: 2). PAC-Bayes bounds provide upper-bound for R(Q) En~D {(2, z) using the training risk R(Q)=
E== {(Q, zi), and a complexity term which usually is based on the Kullback-Leibler divergence between the posterior and data-independent prior.
Standard PAC-Bayesian bounds provide high-probabilin guarantees that the true risk does not exceed the training risk by more than term that decreases with rate of (m)) Here is an example of PAC-Bayes bound:
Theorem 2.1 (McAllestrr 1998)). For any fixed ö O, and data-independent prior P, with probability at least 8 over sampling of a dataset S we have
R(Q)= = R(Q)) + KL(QIIP) log( + 3 log(m) +
(I)
2m
To prove this result, and many other PAC-Bayesian results, one follows common blueprint: 1) apply a change of measure inequality (Seldin et al. 2012) to bound the expectation of a function with respect the posterior Q by the complexity term KL[Q]] P), and the expectation of corresponding moment generating function (MGF) with respect to the prior P. which is independent of training samples. 2) one shows that the MGF for the independent samples is bounded by a sufficiently small term. Often, this involves upper-bounding it by the expectation of an MGF with respect to i.i.d. Bernoulli random variables, and upper-bounding this upper bound by more-or-less explicit calculation.
Besides standard (also called slow-rate) bounds, such I it is also possible to construct bounds that can give tighter guarantees, even a O(1/m) convergence rate when the training error is small, The following theorem is an example of such a fast-rate bound:
Theorem 2.2 (Maurer, 2004)). For any fixed 5 >> O, and data-indepee data-independent prior P, with probability
least 8 over sampling of a dataset we have
(L(Q||) + log 2/m
kl(R((Q) R(Q))
(2)
2m
where
kl(glp) = q log 2 + (1 - q) log 1 p
(3)
1-
In fast-rate bounds, the dependence between training risk and true risk is typically implicit, such as characterized by their Kullback-Leibler divergence in (2.. However, for any observed R(Q), one can derive an explicit upper bound on R(Q) by numerically inverting the kl expression with respect to its second argument.
The main advantage of fast-rate bounds is that they provide much tighter guarantees in the regime where the training risk is small, as is commonly the case when working with rich model classes such as neural networks. As a consequence, fast-rate PAC-Bayesian bounds are among the most promising tools for studying the generalization properties of deep neural networks (Dziugaite & Roy 2011
Pérez-Ortiz et al. 2021
Lotfi et al. 2022), even including large language models (Lothi et al.
2024)
PAC-Bayesian multi-task learning and meta-learning. Following Pentina & Lampert 201 (0144) 4). PAC-Bayes is important framework to study multi-task learning and meta- meta-learning, naturally formalizes information sharing through the concept of a prior.
In PAC-Bayesian multi-task learning, we wish to learn posterior distributions for the n given tasks jointly. However, instead of tata-independent priors, we can learn a (distribution over) data-dependent prior be shared for all tasks. Formally, we learn shared hyper-posterior Q over priors, and different
3

---

posteriors, Qn. for different tasks. We define two distributions over (MF) x F i.e. they assign joint probabilities to tuples, fI.... which contain a prior over models, and n models. A standard PAC-Bayesian multi-task bound then has form
Theorem 2.3. For any fixed hyper-prior P, any ó > O, it holds with probability at least 1 - â over the sampling of the training datasets, , Sn, that for all hyper-posteriee Q and all posteriors Q1..... On
1
n R.(
1 R Σ +(Q0++ V1
KL
+ log 5
+
S
71
where RS and Ri are the expected risk and training risk of task i, my Σ is the harmonic mean
of the training set sizes, my [St). Q is a distribution over M(F) x F given by the product Q x Qi x .... x Qu. and & is a distribution given by the generating process: i) sample a prior P P, for each lask, i b...., n, sample model fa P.
(L(l (Lemma B.4 the appendix) one can see the importance of the hyper-posterior Compared to a naive bound with n complexity terms based on the individual posteriors and fixed prior P, in (4) the prior be chosen in data-dependent way (by means of choosing Q), at the expense of only one additional complexity term ( P). When the tasks are related in a way that allows for common prior, the multi-task bound can be much tighter than single-task bounds could. See Appendix
From the fact that ( ki(
[ for more discussion.
PAC-Bayes meta-learning was first formalized in Pentina & Lampert (2014) as transferring the prior learned using the training tasks to future tasks to be used for minimizing a PPACBBayes bound. This was followed by a rich line of works (Amit & Mcir 20188] 3018;Lo. [iu et al. 2202 Guan & Lu, 2022; Riou
ct al.
2023 Friedman & Meir 2023 Rezazadeh, 2022] / Rothluss et al. [ et al. 2021 Tran
& Yu 2023 Farid & Majumdar| [202]] (Scott et al. (2024) in different setups. In this work, we follow
the general form introduced in Zakerinia et al. (2024), which formulates meta-learning as learning a
general stochastic learning algorithm for future tasks. Formally, the goal is to learn meta-posterion p over a set of algorithms A, generating training posteriors A(SI),... A(S,), and using a multi-task hyper-posterior ((A) as described above.
3 Unbalanced multi-task learning
In this section, we describe our main technical and conceptual contributions. First, we briefly demonstrate in what sense the existing proofs for fast-rate bounds do not carry over from the balanced to the unbalanced multi-task situation. Then, we discuss the requirements that fast-rate bounds should possess in the unbalanced situation, in particular we draw attention to the fact that one has to make a choice whether to bound the task-centric or the sample-centric risk (which we will introduce there). And finally, for both of these, we prove series of generalization bounds, first for the multi-task learning and then extending them to the meta-learning setting.
3.1 Existing proofs do not carry over to the unbalanced setting
Existing fast-rate multi-task bounds (Guan & Lu 2022 Zakerinia et al. 2025) are proved following essentially the same steps as their single-task analogues. First, one applies a change of measure inequality. Second, one bounds the empirical multi-task risk 1
2²) by an average m ΣØ= Xt.j- where the X1, for i = 1,.... n. and j = 1,..., m are Bernoulli random variables with a common mean μr. Third, one uses Theorem (1) from Maurer (2004) to establish a bound on the resulting MGF M₁,(A) E k)(ālu)] < 2 2em for any À < m. Finally, one uses Markov's 's inequality and rearranges terms to obtain the final form of the bound, where the multiplier An in front of the kl-term in the MGF becomes the denominators of the complexity term, i.e. here the rate of convergence is up to (1/nm).
n _ m Σm {f.,
;= π. ΣT
- 1
In the following Lemma we show that this otherwise ubiquitous proof technique fails in the case of unbalanced MTI., because the corresponding MGF does not have a finite bound for sufficiently large multipliers.

---

mi. Lemma 3.1. Let X1. Lid. Bernoulli(p) for = I....,n and L...., M, Define f "E= mi Ej=1 Nij; as their average, weighted by inverse dataset sizes. Let mymin min; mi Then, the MGF M₂(A) = E [eenAk((Bl)] has the property that supocusi M₂(X) = +00, whenever À >> Mmmin In particular, there is no finite bound on My(A) that depends only on n. and the m, but not p.
Discussion. A consequence of Lemma 3.1 is that the best multi-task rate achievable by the proof technique above is O(1/nmmiin). However, the resulting bound would not improve when the number of samples for some tasks increases while mimin remains the same. This is unintuitive and inconsistent with the standard-rate bound in Theorem 2.3 whose convergence depends on the harmonic average of dataset sizes, mhh rather than their minimum. Also, a known property of implicit bounds in the form of Theorem 2.2 that one derive corresponding explicit standard-rate bounds from them by means of Pinsker's incquality, kl(gpp)= 2 2(q - p)². Doing so in this situation, however, would result in standard-rate bound with the suboptimal rate O / I/remmmin) instead of O( II/mmm)) Overall, our analysis suggests that a different approach should be considered to achieve fast-rate bound for the unbalanced multi-tast task learning, and we do so in the following sections |
Note that in this paper, focus the fast-rate bounds for unbalanced multi-task learning in the PAC- BaC-Bayesian framework, however, a similar problem also exists in the PAC setting, i.c., the current fast-rate bounds in the PAC literature would also have dependency the minimum number of samples (Yousefi et al. 2018).
3.2 Task-centric vs sample-centric guarantees for unbalanced multi-task learning
Unarguably, the goal of multi-task learning is to learn multiple models that perform well for their respective tasks. such, one might argue that MTL. actually a multi-objectivv learning prob- lem (Sener & Koltun 2018). In practice, however, one needs to define a scalar objective to quantify the success of learning in general, and generalization particular (Hu al.) (023). Most exist- ing work in multi-task learning
uniform average across tasks for this purpose, resulting in multi-task risk, , and its empirical counterpart
1 Σ R((O.)) = Σ
a
RI........ Qn)
E ((Qu.)), DnD
(5)
71 1=1
= n R(((.))
1 Σ
12
-- -1
Σ -
mi
4(Q ziy).
(6)
We call this setting task-centric MTL, because each task is treated as equally important, regardless of how much data it contributes to the learning. An alternative scalarization is sample-centric MTL, in which tasks get weighted proportionally to their amount of training data. The corresponding risk and empirical risk are
"
n
RQ Qn) Σ
mi (Q()))
Σ
m ((Qu.))
(7)
M
M 2-D,
1=1
1=1
n
a
m4
R3(Q....,, Qn)
my
R,
4(Q
(8)
M
M
respectively, where M = Σ; my is the total number of data points.
In balanced MTI., both notions coincide, so no decision between them is necessary. In unbalanced MTL, however, they are distinct, and we argue that the choice of preferable objective depends on the problem setting. For example, consider a common scenario, in which a service provider trains client-specifie models. the goal appropriate. If, however, the goal is make as few mistakes as possible on future data, data-rich clients should get more attention, because they will likely contribute also a larger fraction of the future data points. Consequently, the sample-centric setting is preferable.
maximize client satisfaction, the task-centric setting
Note that none of the discussed problems occur for the balanced setting with My. m, because
there Mmmin m mhh
5

---

Consequently, in this work we provide new results for both settings. All proofs are provided in the supplemental material.
3.3 Fast-rate generalization bounds for task-centric multi-task learning
Our main results are the following generalization bounds, which establish the first fast-rate general- ization guarantees for unbalanced multi-task learning.
Theorem 3.2. For any fixed hyper-prior' P, any > 0, holds with probability at least Ô over the sampling of the training datasets that for all hepper-posterior functions Q and all posteriors Q1..... ...
a Σ my (. KL(2)13) + log 5
1
+ Σ log mm,(2/m;)
For any fixed hyper-prios P, any 8 > 0, and any . An > O, holds with probability at least functions Q and all
1 - 8 over the sampling of the training datasets that for all posteriors Qı QI...., On:
m, log(1 R((Q.) + R.
+ log( (10)
n
Discussion. For proving these results (unlike the balanced setting), we consider independent terms capturing the derivations related to each task (which depends on its own sample size). By jointly bounding the combination of these terms to gain the shared complexity term based on hyper-posterior.
The kl-type bound (9) relates the individual per-tasks risk with their empirical estimates. For the balanced setting with m. ... my m, it recovers previous fast-rate results (up to log terms), because nm (I(RTRR) < E, m (K,,, due to Jensen's 's inequality. The form we provide also handles the unbalanced case, for which in light of discussion in Section 3.1 we avoid having to bound kI R directly, instead finding the weighted linear combination of per-task kl-terms to be more suitable target.
To better understand the behavior of p9) in the unbalanced setting, assume a setting in which all tasks have fixed training set sizes, except for one, say task k. for which we consider larger and larger training set sizes, i.e. ml + oo. Then, for identical (Ω, Q.,..., Qn). and therefore constant {), the left hand side of the bound grows with my kl Rx). while the right hand side grows as log( /mx), which implies fast-rate convergence kl R₂) - O. In particular, tasks with few samples do not slow down generalization of tasks with many samples.
As second indication that (9) provides the right characterization, observe that it readily implies an explicit standard-rate bound of the correct rate O( ((VI] /L/r/Innn I/Rmp,) using the relation
2 mi > (R. -R.
2
m: (R, -R,)² R.)²
Σ my kl(R, RR),
(11)
1=1
where the left inequality follows from the Muuchy-Sehwarz. and the right one from Pinsker's inequality.
The Catoni-type bound (10) offers a more explicit characterization of the generalization behavior, because the empirical risk appears explicitly on the right hand side of the inequality. Like the kl-bound, it guarantees fast-rate convergence for any task, even if the training set sizes of all other tasks remain fixed.
A natural question is which of the two bounds yields better guarantees. As it turns out, this depends on the choice of A .....,,,,, An. It is known (Germain et al. 2009 Proposition 2. that supx log(1 + > >ql = kl(p)), i.e., an optimal choice of the A would recover (.. except without the log terms on the right hand side. Unfortunately, (TO) does not hold uniformly with respect to the A--vuuus, so one cannot simply optimize the expressions to obtain the best values. However, if one has a candidate set of potential values, the bound can be made uniform for this set by union bound, and select the tightest one. This is also the strategy we follow in our empirical evaluation, see Section 5 Note, however, there is no guarantee that the resulting bound will improve over O so promising strategy is to also include that one into the union bound.

---

3.4 Numerical computation of the bounds
Single-task kl-bounds are straightforward to compute numerically: because only single quantity is unknown (the true risk R), one can make use of the fact that kl(glp) is strictly monotonically increasing and therefore invertible in p [g, 1] to identify the largest values of R such that kl (R) fulfillss the bound. Similarly, single-task Catoni-style bounds can readily be used to derive a numeric
bound on the risk by observing that -m log(1 R + Re m is strictly monotonically increasing function of RR.
In the MTL setting, the bounds in Theorem 3.2 have unknowns, Ri...., Rr but the corresponding bounds provide only a single joint constraint. As such, the set of feasible solutions is much richer than in the single-task setting. In the task-centric setting, we are interested in guarantees on the largest possible value for RT
-1 -, R2 i.e. we have to numerically solve the optimization problem
L +ERA R.
RT.
max R1 R.,
subject to generalization bound constraint.
(12)
We illustrate this process in Figure setting, the potentially complex geometry the constraint set allows obtaining tighter guarantees by combining multiple bounds. For example, a union bound. Optimizing over the resulting constraint set can provide an even better guarantee on RJ than the minimum of using each bound individually. Figure 3 also illustrates this effeet, which is impossible the single-task setting due to the one-dimensional nature of the problem there.
Interestingly, and to our knowledge unique to the MTL
instantiate both (9) and (10) and combine them by
For our experiments, we use Sequential Least Squares Programming (SLSQP) (Kraft) 1988). gradient-based optimization algorithm that solves constrained nonlinear problems by iteratively approximating them with quadratic programming subproblems. Note that this procedure is computa- tionally inexpensive compared to model training.
3.5 Generalization bounds for sample-centric multi-task learning
sample-centric MTL has a different goal than task-centric MTL.: its objectives are weighted by the training set sizes, to reflect that tasks with many samples can also be expected to occur more often in the future. In this section, we provide the fast-rate generalization bounds for the corresponding risk 77)
As discussed in Section 3.2
Theorem 3.3. For any fixed hyper-prior P, any ô > holds with probability least 1- ô over the sampling of the training datasets that for all hyper-posterior functions Q and all posteriors QI,...:.... Qni
(I(R*(R*) < KL(2) + log
2 8
sample-centric kl-bound
(13)
M
For any fixed hyper-prior P. any 8 O, and any X > O, it holds with probability least 1 6 over the sampling of the training datasets that for all hyper-posterior functions Q and all posteriors Q.....:
Qu
M log(1
KL + log(?))
RD + RRE
S R
sample-centric Catoni-bound (14)
A
A
The provided bounds are more similar to balanced multi-task learning, and have the following properties: 1) The focus is on the sample level, and separating terms based on the tasks is not necessary. 2) All samples contribute the same amount to the training risk, and issue such as in Lemma does not happen. 3) The sample complexity is based on the total number of samples, and the minimum sample size harmonic mean not bottleneck.
Discussion.
Corollary 3.4. Applying Pinsker's 's inequality to the kl-bound of Theorem 3.3 results in the following explicit standard-rat bound for sample-centric multi-task learming:
KL (1) + log 2
R$. < Rs +
(15)
2M

---

Meta-learning with unbalanced tasks
In this section, we extend our results to meta-lcarning. Following the framework of Zakerinia et al. (2024), the goal is leam learning algorithm, A, from a candidate set, A, to be used for future tasks. At meta-training time, a set of training tasks are available that were sampled i.i.d. from a task environment that allows for tasks to have different training set sizes in [1, m As in multi-ta learning, previous works studied this problem only in a task-centric view. However, it is also possible and relevant study sample-centric meta-learning for the setting in which tasks with more training samples should get more weight in the analysis. Consequently, we define two meta-learning risks:
(P)=
E E(2, A(S)), Amop (D.. anD
E
E
(P)
m Amp (D.m. 2 Mana
E
E
E
f(2, A(S)), (16)
where p meta- meta-posterior over the set of algorithms A. Each algorithm in A A is function that given a dataset would generate a posterior distribution A(S). Additionally, each algorithm can learn hyper-posterion ((A) similar to multi-task learning. Therefore, for each algorithm
would use
the two distributions. 1) (A):: hyper-posteriin ((A) specific to algorithm A (data-dependent) and task posteriors A(S,). and 2) P(A): hyper-prior ((A) specific algorithm A (data-independent)
and priors P ~ ((A).
In this section, we provide fast-rate bounds for unbalanced meta-learning. Here, we state the kl- style bounds, while the analogous Catoni-style bounds and the proofs for both types are provided in Appendix B.4 To provide our results, first introduce the following notation, which is the upper-bound given numerical optimization the kl-bound explained in Section3.4
k1 17: m. ma (q......gn) = sup {
Σ
m. kl(gppp)) S b, E [0, [0.11]
Pi
(17)
With this notation we provide our main meta-learning bounds.
Theorem 4.1. For any fixed meta-prior n, and fixed set of A), any 5 >> O, it holds with probability least 1 6 over the sampling of the training datasets that for all pest-posssrrios, and hyper- posteriors Q(A);
Task-centric mela-learning: with 61 = =E log(2//m)
4V + a)) KL(plT)) + log 8
(P) < kl
kl klm.........
(18)
Sample-centric metallarnng: with 02 log(2vM)
Ris S kl,
M
kl (R((0) + tz)) KL(P)| log
4
(19)
nMmmax
where C(p) = (L(ppl))+++ + E (L(Z)()))IP((A) + log
Amp
Discussion. The meta-learning generalization bounds are based on two parts: 1) multi-task bound which noper-bounds the generalization error within the training tasks 2) generalization bound the environment level, to upper- bound the expected performance for the environment based on the true risk of the training tasks.
Numerically computing the bounds consists of first numerically computing the upper-bound for the true risk of the training risks, and then numerically computing the final bound. Similar multi-task learning, the bounds have a better sample complexity over the sample size of training task when the risks are small, and additionally, a better complexity over the number of tasks, for example for task-centric bounds, when the risks are small, the rate of the bounds would be O(1/m 1/n) instead of ((v1/m/ + /1/n). Additionally, applying Pinsker's inequality to the task-centric bound, would result in the standard-rate meta- learning bounds of Zakerinia et al. (2024). Similarly, by using Pinsker's 's inequality, get standard-rate bounds for sample-centric meta-learning.

---

0.7
Fast rate with Mmiin
0.00
risk (difforence to standard-
0.6
Standard rate
-0.01
Fast-rate kl-style
0.5
Fast-rate: Catoni-style
-0.02
nikk
0.4
empirical risk
-0.03
0.3
Standard rate
-0.04
0.2
Fast-rate: ki-style
-0.05
Fast-rate: Catoni-style
0.1
Fast-rate: Oracle
0.0
0.06
0.0
0.02
0.04
0.06
0.08
0.1
0.0
0.02
0.04
0.06
0.08
0.1
simplicity
simplicity
Figure 1: Task-centric MTL: graphical results for linear models on the MDPR dataset
0.30
Standard rate
risk (difference standard-dnee rate)
0,00
Standard rate
0.25
Fast-rate ki-style
-0.01
Fast-rate: ki-style
Fast-rate: Catoni-style
Fast-rate: Catoni-style
0.20
empirical risk
-0.02
Fast-rate: Oracle
nikk
0.15
-0.03
-0,04
0.10
-0.05
0.05
-0.06
0.00
0.0
0.02
0.04
0,06
0.08
0.1
0.0
0.02
0.04
0.06
0.08
0.1
simplicity
simplicity
Figure 2: Sample-centric MTL: graphical results for linear models on the MDPR dataset
Experiments
While contribution in this work is theoretical, also provide results from numeric experiments to illustrate the numeric behavior the bounds we establish. Specifically, we report on experiments in prototypical multi-task settings: linear classification with learned regularizer, and neural network learning random subspace representation. We also provide a visual illustration of the bounds" geometry for = 2 in Appendix C
MTL bound for linear models. In our first experiments, we provide generalization guarantees in the setup of linear multi-task learning with biased regularization (Kienzle Chellapilla 2006): for each task, we learn a (stochastic) linear classifier, parametrized by a (Gaussian) distribution over each task's 's classifier weights. Additionally, we learn regularization term, which is also parametrized by Gaussian and shared among all tasks. As dataset, we use the MDPR dataset (Pentina & Lampert 2017), which consists of 953 tasks. Their training set sizes range between 102 and 22530 samples, making the setting clearly unbalanced. Besides the original data, we also create variants of higher simplicity, by adding a mulltiipe of the label value to each input features for E [0, 0.1). For details on the setup, Appendix C
Figures and show the results (more details and numeric values can be found in the appendix). In the cesk-centric setting, fast-rate and standard bounds provide similar guarantees for = 0, but with larger values of 77, the fast-rate bounds benefit more from the decrease of the empirical risk and provide tighter guarantees than the standard-ran bound. This only holds for the new unbalanced bounds we present in this work, though. The naive fast-rate bound with convergence rate determined by Mimin is always far looser than even the standard-rate bound. In the sample-centric setting, the benefit our fast-rate bounds apparent already at r) = O, and the gap standard-rate bound increases with growing ?).

---

Table Generalization bounds for low-rank parametrized deep networks on split-CIFAA
Task-centric
Dataset
CIFARIO
CIFARI00
Standard rate
0.307
0.595
Fast-rate with min
0.347
0,616
Fast-rate: kl-style
0.272
0.591
Fast-rate: Catoni-style
0.271
0.591
Joint constraint
0.270
0.591
Sample-centric
Dataset
CIFARIO
CIFARI00
Standard rate
0.300
0.595
Fast-rate: ki-style
0.265
0.593
Fast-rate: Catoni-style
0.262
0.590
MTL bound for neural networks. Our second experiment provides generalization guarantees for unbalanced multi-task learning of low-rank parametrized neural networks (Zakerinia et al. (025). As dataset we use Molii-CIFARRO and split-CIFAR (Krizhevsky 2009). in which popular CIFAR datasets are split in an unbalanced way into tasks, each of which possesses only of 10 (for CIFARTO) or 10 out of 100 (for CIFARI0O) classes. As model, we use a Vision Transformer
model with approximately 5.5 million parameters, pretrained on ImageNet (Dosovitskiy et al. 2020). Further details are provided in Appendix
Table I shows the results. For the task-centric as well as the sample-centric views using our fast-rate bounds instead of the standard-rater ones leads to noticeable improvements, while the bound with dependence Mmmin would be much looser. In line with the theory, the improvements are larger for split-C CIFAR1O, 10, where the empirical error small, than for aplit-CIFARION where the empirical error is too large for the fast-rate property to be effective.
6 Conclusion
The literature on generalization behavior of multi-task learning has been heavily focused on the setting where all tasks have the same number of training samples, despite fact that this balanced setting is not realistic for real-world tasks. In this work, we explicitly study the unbalanced multi-task learning, showing that it has different statistical properties than the balanced setting, and that the results and proof techniques from the balanced setting do not simply carry over to the unbalanced setting. We argued that for evaluating multi-task methods, there are two different views, which matter in different applications: task-centric and sample-centric. As our main contribution, we provided fast-rate generalization bounds in the PAC-Bayes framework for both settings, and we demonstrated through empirical evaluations that these bounds not only theoretically superior but also can provide tighter guarantees than standard bounds.
A limitation of our work is that the resulting bounds are less interpretable than explicit standard-rate bounds, and that numeric optimization required to obtain numerical guarantees. We believe will be interesting future work to explore if more explicit fast-rate bounds are possible for the unbalanced setup at all.
Acknowledgements
This research was supported by the Scientific Service Units (SSU) of ISTA through resources provided by Scientific Computing (SciComp).
10

---

References
Amit, R. and Meir, R. Meta-learning by adjusting priors based on extended PAC-Bayes theory. In International Conference Machine Learning (ICML), 2018.
Bartlett, L. and Mendelson, S. Rademacher and Gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research (JMLR), 2002.
Baxter, A model of inductive bias learning. Journal of Artificial Intelligence Research (JAIR), 12: 149-198, 2000.
Berend, D. and Tassa, T. Efficient bounds on Bell numbers and on moments of sums of random variables. Probability and Mathematical Statistics, 2010.
Caruana, R. Multitask learning. Machine Learning, 28:41-75, 1997.
Catoni, O. PAC-Bayesian supervised classification: The thermodynamics of statistical learning, volume 56 of Lecture notes. Institute of Mathematical Statistics, 2007.
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 Neurul Information Processing Systems (NeurIPS), 2021.
Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., Uszkoreit, J., and Houlsby, N. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations (ICLR), 2020.
Dziugaite, G. K. and Roy, D. M. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In Uncertainty in Artificial Intelligence (UAI), 2017.
Farid, A. and Majumdar, A. Generalization bounds for meta-learning via PAC-Bayes and uniform stability. Conference on Neural Information Processing Systems (NeurIPS), 2021.
Friedman, L. and Meir, R. Adaptive meta-learning via data-dependent PAC-Bayes bounds. In Conference on Lifelong Learning Agents (CoLLAs), 2023.
Germain, P., Lacasse, A., Laviolette, F., and Marchand, M. PAC-Bayesiee learning of linear classifiers. In International Conference on Machine Learning (ICML), 2009.
Gronauer, S. and Diepold, K. Multi-agent deep reinforcement learning: a survey, Artificial Intelligence Review, 55(2), 2022.
Guan, J. and Lu, Z. Fast-rate PAC-Bayesian generalization bounds for meta-leamning In International Conference Machine Learning (ICML), 2022.
Hospedales, T., Antoniou, A., Micaelli, P., and Storkey, A. Meta-learning in neural networks: survey, IEEE Transactions Pattern Analysis and Machine Intelligence (TPAMI), 44(9), 2021.
Hu, Y., Xian, R., Wu, Q., Fan, Q. Yin, L., and Zhao, H. Revisiting scalarization in multi-task learning: A theoretical perspective. In Conference on Neural Information Processing Systems (NeurIPS), 2023.
Kairouz, P.. McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A. N., Bonawitz, K. A.,
Charles, Z., Cormode, G., Cummings, R., D' D'Olivirra, R. G. L., Eichner, H., Rouayheb, S. E.. Evans, D., Gardner, J., Garrett, Z., Gascón, A., Ghazi, B., Gibbons, P. B., Gruteser, M., Harchaoui, Z., He, C., He, L.,, Huo, Z., Hutchinson, B., Hsu, J., Jaggi, M., Javidi, T., Joshi, G., Khodak, M.. Konečný, J., Korolova, A., Koushanfar, F., Koyejo, S., Lepoint, T., Liu, Y. Mittal, P., Mohri, M., Nock, R., Özgür, A., Pagh, R., Qi, H., Ramage, D., Raskar, R., Raykova, M., Song, D., Song, W., Stich, S. U., Sun, Z., Suresh, A. T., Tramèr, F., Vepakomma, P., Wang, J., Xiong, L., Xu, Z., Yang, Q. Yu, X., Yu, H., and Zhao, S. Advances and open problems in federated learning. Foundations and Trends in Machine Learning, 14, 2021.

---

Kienzle, W. and Chellapilla, K. Personalized handwriting recognition via biased regularization. In International Conference on Machine Learning (ICML), 2006.
Kraft, D. software package for sequential quadratic programming. Forschungsbericht Deutsche Forschungs- und Versuchsanstalt fur Luft- und Raumfahrt, 1988.
Krizhevsky, A. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
Liu. T., Lu, J., Yan. Z., and Zhang, G. PAC-Bayes bounds for meta-learning with data-dependent prior. arXiv preprint arXiv:2102.03744 2021.
Lotfi, S., Finzi, M., Kapoor, S., Potapezynski, A., Goldblum, M., and Wilson, A. G. PAC-Bayes compression bounds so tight that they can explain generalization. In Conference on Neural Information Processing Systems (NeurIPS). 2022.
Lotfi, S., Finzi, M. A., Kuang, Y., Rudner, T. G. J., Goldblum, M., and Wilson, A. G. Unlocking tokens data points for generalization bounds on larger language models. In Conference on Neural Information Processing Systems (NeurIPS), 2024.
Maurer, A. A note on the PAC Bayesian theorem. arXiv preprint arXivics. 2004.
McAllester, D. A. Some PAC-Bayesian theorems. In Conference on Computational Learning Theory (COLT), 1998.
Pentina, A. and Lampert, C. H. A PAC-Bayesian bound for lifelong learning. In International Conference on Machine Learning (ICML), 2014.
Pentina, A. and Lampert, C. H. Lifelong learning with non-iid tasks. In Conference on Neural Information Processing Systems (NeurlPS), 2015.
Pentina, A. and Lampert, C. H. Multi-task learning with labeled and unlabeled tasks. In International Conference on Machine Learning (ICML), 2017.
Pérez-Ortiz, M., Rivasplata, O., Shawe-Taylor, J., and Szepesvári, C. Tighter risk certificates for neural networks. Journal of Machine Learning Research (JMLR), 22(227):1-40, 2021.
Rezazadeh, A. A unified view PAC-Bayes bounds for meta-learning In International Conference on Machine Learning (ICML), 2022.
Riou, C., Alquier, P., and Chérief-Abdellatie 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, 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, J. Evolutionary principles in self-referential learning. Diploma thesis, Technical University of Munich, Germany, 1987.
Scott, J., Zakerinia, H., and Lampert, C. H. PeFLL: Personalized Federated Learning by Learning to Learn. In International Conference Learning Representations (ICLR), 2024.
Sceger, M. PAC-Bayesian generalisation error bounds for gaussian process classification. Journal of Machine Learning Research (JMLR), 2002.
Seldin, Y., Laviolette, F., for martingales. IEEE Transactions on Information Theory, 58(12):0866-002; 2012.
N., Shawe-Taylor, J., and Auer, PAC- BaC-Bayesian inequalities
Sener, O. and Koltun, V. Multi-task learning as multi-objective optimization. In Conference Neural Information Processing Systems (NeurIPS), 2018
Thrun, S. and Pratt, L. (eds.). Learning to Learn. Kluwer Academic Press, 1998.
Tian, and Yu, H. Can we improve meta-learning model few-shot learning by aligning data distributions? Knowledge-Baad Based Systems, 277:110800, 2023.
12

---

Vapnik, V. N. and Chervonenkis, A. Y. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability Its Applications, 16(2):264-280, 1971.
Verbracken, J., Wolting, M., Katzy, J., Kloppenburg, J., Verbelen, T., and Rellermeyer, A survey on distributed machine learning. ACM Computing Surveys, 53(2), 2020.
Yousefi, N., Lei, Y., Kloft, M., Mollaghasemi, M., and Anagnostopoulos, G. C. Local Rademacher complexity based learning guarantees for multi-task learning. Journal of Machine Learning Research (JMLR), 19(38):1-47, 2018.
Zakerinia, H., Behjati, A., and Lampert, C. More flexible PAC-Bayesian meta-learning by learning learning algorithms. In International Conference on Machine Learning (ICML), 2024.
Zakerinia, H., Ghobadi, D., and Lampert, C. H. From low intrinsic dimensionality to non- non-vacuous generalization bounds in deep multi-task learning. arXiv preprint arXiv:2501. /9067, 2025.
Zhao, Y., Li, M., Lai, L., Suda, N., Civin, D., and Chandra, Federated learning with non-iid data. arXiv preprint arXiv: arXi:: 00t::11800000082,,00000 2018.
13

---

A PAC-Bayesian multi-task learning
very simple solution achieve bounds for several tasks with different sample sizes is to compute single-task bounds for all tasks separately, and combine them by averaging and union bound. However, this simple solution does not achieve the goal of multi-task learning, i.e., benefiting from shared information between tasks and task similarity. Importantly, this method does not share complexity terms and does not benefit from an increasing number of tasks, resulting in a sub-optimal bound, see e.g. Zakerinia et al. (2025) for numeric experiments.
PAC-Bayes multi-task learning shares information by learning (distribution over) data-dependent prior to be shared for all tasks. Formally, we define two distributions over M(F) x F i... they assign joint probabilities to tuples, (P. fi..... .......... fr., which contain prior over models, and n models: 1) Q is a distribution given by the product Q x Q1 x... x Qn. and Q is distribution given by the generating process: i) sample prior P P. ii) for each task, I..... n, sample model fi P.
Additionally, we can also define the distribution Q slightly differently by the following generating process: i) sample a prior P ~ Q, ii) for each task, i = .....,,3 Ri, sample model f, QP which is a data-dependent function that adapts the posterior for each prior P. This approach might help reducing the complexity terms, i.e. for each P. the term (L(Q::I would become ( PP). However, it causes an additional complexity in adapting the posterior to each prior. The results stated in this paper are mentioned in the form of the first approach, however, all results would hold by simply inserting the different Q in the results and proof's (Pentina & Lampert 2014 Zakerinia et al. 2024..
B Proofs
B.1 Auxiliary Lemmas
Lemma B.1 ((Brrnd Tassa 2010) Proposition 3.2). Let X,, 1 S i S t, be sequence of
independent random variables for which P(O S X; 1) 1, X Σ -i=1 X,, and μt == E(X). Let
Y be the binomial random variable with distribution Y B (1, t) Then for any convex function f
we have:
Ef(X) S ES())
(20)
Lemma B.2 (Maurer 2004) Theorem 1). Let Y be the binomial random variable with distribution
Y B (t, +) then we have:
Ele kI (
(21)
where kl(gp)) q log (1 q) log 1-g is the Kullback-Leible divergence between Bernoulli distributions with mean q and p.
Lemma B.3 (Generalization of (Catoni 2007
Lemma 1.1.1.). Let X iid. Bernoulli(s)) for
i .1....,.. n and j 1, 1...., my. Define i.
m. Σ/T X, then we have:
Dr 10 कोक
(cx) p.)
log
<1
(22)
where Pp(p) - log(1 p + aa
Proof.
log E En =t ps
D. A Dyz my X
log E
(23)
log I. e nmm X
my log E
e mm Xe,
(24)
- Σ Φ (1ts)
Σ my log(1 - 14 + pGen nome
(25)
14

---

Therefore,
E
Di= #
Σi-1 A (pr)
(26)
A Eis
4 nm;
((x)
Multiplying both sides by
completes the proof.
The following lemma splits the KL term of 41
into more interpretable quantities.
Lemma B.4. For the posterior. D. and prior, P. defined above it holds:
(L(())))- (L(2))P) + E P~
Σ KI(A(S))IP))
(27)
Proof.
log ((P) II= Qi(fi)
KL(2|17) E
E pNo (a (n. Qn)
(28)
P(P)
IT P(f.)
((P)
E log Qi()i)
= E
log
+ E
(29)
PaQ
P(P).
P
finQ
P(fi)
1=1
PL( + KL(QiiP)
(30)
P
1m
B.2 Task-centric bounds
Theorem 2.3. For any fixed hyper-prior P, any 5 > O, it holds with probability at least 1 - å over the sampling of the truining datasets, Sy...., ; Syu that for all hyper-posterior Q and all posteriors
Q1..... Qni
1
R((1)) S Σ R((2.))
KL(D) [B) + log
4m 5
(4)
2mm
1=1
i=1
where R; and R, are the expected risk and training risk of task i, mh of the training Q x Qi x ... x Qu, and H is a distribution given by the generating process: i) sample a prior P P, ii) for each lask, .,..-, n, sample model fa P.
Σ is the harmonic mean sizes, my [Sa). Q is distribution over M(F) x F given by the product
Proof. First for any task and any model Si we define:
A.(fi) = E f(2,f1)
Σ f(2,f)).
(31)
InD;
mi sES.
By defining (2) = Ei Ri(Qi) and R2) = En R2,2),, we have:
E
EA. = (1) - R12
(32)
(P.
Applying the change of measure inequality (Seldin et al. 2012 between the two distributions Q and Q. for any À 0, and any Q, ......, Qn we have:
R2) - R. KL(2)13) < log (P.) (P..
E
II e AA(A))
(33)
15

---

By the construction of Q, we have
E S SI.... S. (P-f1.Ja.... and, because is independent of St..... Sn we can rewrite this
E
II A.(())
E Sp.... PaP
E
E
E
en
A.()))
(34)
SIOP
1=1
E E
E
E JamP
en Aall).)
(35)
P-P
S1
Sn
E (A.0
E PaP ==1
(36)
SimP
Each A.(A) is a bounded random variable with support in an interval of size 1. By Hoeffding's lemma we have
E E (
I e @8n
(37)
Therefore, by combining (36) and 37
we have:
E S S. (P.
E
II e A.(i))
S 6ea (ii=
12
8nimp
(38)
Which my Em
is the harmonic mean of m,s. By Markov's inequality, for any we have
P Ps Sn (P.. g
E
Il
e AA(D)
20t) S aamm
22
(39)
i=1
Hence by combining 33 and
39 we get for any E:
22
Ps...... S. or, equivalently, holds for any 8 > 0 with probability at least
30 (1)) R. 22)
(L
2 x
S
e
Smimg
(40)
6,
2'
1
2
A
AQ (12 - R., (12)
KL x
log(
(41)
X
8nm,
By applying a union bound for X E (1,2.... ).m,), and optimizing for in this set we get:
KL + log( 4mmmn +1
(1) - (12) <
(42)
2nmA
In the following theorem, we prove that standard fast-rate kl-bounds scale at best with nmmin-
Lemma 3.1. Let Xi.j iid. Bernoulli(u) for i = I,...,n and ,,.. Define ğú mi E)= Xijz their average, weighted by inverse dataset sizes. Let mymin = min, my
E I
Then, the MGF Mn(A) = E [enAal has the property that supo<ue1 My(A) = toG, whenever > Mmin- In particular, there no finite bound on My(A) that depends only on n and the my but not p.
Proof. Assume > Mimin Then
M(A) = E mdd k((p)p)
(43)
172
mi
=h (1 - (1- mk] mikll 1 In
As my (c)
(44)
K;
k 0
R
Σ
E, Rs (1 - 11) Em (m)=
I.
m
be
>E:
Σ.
me-ki my
>E
my-ki
m3
k;
kI.... Am
1=1
(45)
Σ E (1- (1)
Emm
mi-k,
f(n, X, k1, Mi,. Mi...., knn mn),
k
(46)
16

---

where
>E;
[n, X, mi,,,,---.. -- Ray mn)
&: m2
my
(47)
m;
h;s
Assume I is the index for the minimum my such that my Mymins pick the single term with ki my and h; O for + (. Since all terms are positive,
(A) 2 m--> mL
(1 (1) Eng (n-1)A f(n, X, O, my..... my m..... ,0, m.)
(48)
(49)
which for < 0.1, there is constant C' such that (() > Cp T4 fn, X, my...... m,, m...... 0, mn).
(50)
Since > my the exponent my - À < O, so as + O, p pm + +oc. Hence M is unbounded for À >> minu and no finite bound depending only on and the m, can hold.
Theorem B.5 (Theorem 3.2 Equation ()). For any fixed hyper-prior P, any 8 0, it holds with probability at least functions and all posteriors Q1...., Qn
over the sampling of the training datasets that for all hyper-posterior
1 6
m, ((( S KL(2 + log
log(2 (mg()mm))) mi)
(51)
Proof. Based on Jensen's inequality we have:
Σ m, ((((((Q))))))))))))))))
E
Σ m, (((
(52)
And by change of measures we get
E
m, ((IR - KL(2)1133
P-
t=1
DE m. (.R.U.AAR.RR
< log
E P P.
log P.P
(53)
fomP
Where the equality comes from priors being data data-indeepndent. Additionally, based on Lemma for binomial random variable Y B(m,, (f.))
B.I
we have:
E
E Th SOmP
E fam S.
m, ((R
(54)
S.nD
kl Y [R,(
E
22mm,
(55)
!~PYL
Where the last inequality comes from Lemma B.2 Therefore
E PNP
E foPP
m. kI (((R
II 2 m,
(56)
And by Markov's 's inequality, with probability at least 1 over sampling of . Sn, we have:
log E
m. (I).( fiPP
log 2 + log
(57)
PaP
By combining
and
57
we get
Σ m. (.P & KL (3) + log 8
+
log(2
m2)mm))) mi)
(58)
17

---

Theorem B.6 (Theorem 3.2
Equation (T)). For any fixed hyper-prior P. any 5 > 0, and any
Ay...., An O, it holds with probability at least ô over the sampling of the training datasets that for all hyper-posterne function Q and all posteriors Q1...., Qn:
functions
(.(-RR(Q0))) m, -,)) +
x KL()) + (ogg))
(59)
Proof. Note that the function Pa is convex for 0, therefore Jensen's inequality have:
2Φ
is also convex. Based on mmng
X - E 1 (R.(f.) -R.f)))RR((ff)) R.(f.) fi~Q; n
(60)
mmm;
And by change of measures, and independence of priors, we get
E
Φ - RR (R.(f)))
KL(2)12)
Pi
Ei
1 wing
(R.(A))-RR(AA)
log E
E SimPl
(61)
P-P
Now we apply Lemma (B.I times for each task separately, keeping the others fixed. if we define B(m;, R2 (ri))), we have
binomial random variable y;
Eisr
4 ming
(R.
(R.( R.(
E
E
E
(62)
S.ND PaP fimPl
1
(R.( R
E
e
(63)
P>P fir
S.nD.
14
Y (R.(f.)
E
(64)
Where the last inequality comes from Lemma (.3) Therefore by Markov's inequality, with proba- bility at least
5 over sampling of S ..,,,,,,. Sn. we have:
Di=1 A10 (R.(F)) (R.(ff))RR.(FA)))
log
E
E frrP
log 3
(65)
PrP
By combining 66
61 and
(65)
we get that with probability at least 1-8: 6:
(R((2)) -R(())) S (L + log 5
(66)
π
Or equivalently,
KL(Q + +og(())
m, log(1 RR mmm
S R.
(67)
+ log 1 )
m. lolllg(11 - R((Q,)+ + R2(Q))
<
(68)
B.3 Sample-centric bounds
Theorem B.7 (Theorem 3.3, Equation 13 For any fixed hyper-prior P, any 5 > 0, it holds with probability at least over the sampling of the training datasets that for all hyper-posterior functions Q and all posteriors QI....,Q. Qni
KL ( + log 2
kI(R)1R>) <
sample-centric kl-bound
(69)
18

---

Proof. Based on Jensen's 's inequality we have:
M kl
m
(
Σ
(iRR((i))
E [iNQUiE(x)]
Mkl
m, (i))
Σ
mi Rs (i))((i))
M
M
M
M
(70)
And by definition of R; and R2 get
12
m,Ri(1i))
1 m2
Mkl
E
Mkl
ΣΣ
e 23,5)
Rwy
Ji
M
M
S S,
M
i=1
(71)
And by change of measures we get
n my
Mkl
ESss zi.s)
Ru
-L(()))))
M 1=1 =1
M Ei Egss ((ries)) Rw).
log
E PruP.fiePl
Additionally, we have
m2
Ufisz)) -Rw
(72)
Therefore, Based Lemma B.1 if define binomial random variable Y B(M, Rw:), replace the loss samples of all tasks as in
E
E f
M kl EE
En
(( < E c ki( (R.)) (R
(73)
And by Lemma (B.2
we have
E
M MK
< 2V
(74)
Therefore,
kl Ei Ey (f E. < 22
E
E PoP
E f
(75)
St......
And by Markov's inequality, with probability at least 1 - over sampling of S Sn, we have:
2/M M
log
E
M KK Eis Ensh (R < log
(76)
PAP fimp
5
By combining 77
and 76
we get
2 S (KL(2/)))) + log
M kl
Ru Rw
(77)
5
Theorem B.8 (Theorem 3.3
Equation 14 ). For any fixed hyper-prior P. any 5 > 0, and any
O, it holds with probability at least hyper-posterior functions Q and all posteriors Qi,..., Qn
ö over the sampling of the training datasets that for all
-M
KL(2)(3) + log(?))
log(1 Rd + R < R
sample-centric Catoni-bound (78)
A
À
19

---

Proof. Based on Jensen's 's inequality we have:
m, m,,,(
"
m (aR)(Q.)))
n
m, m2
Σ
m (fi)
M
M
Sin
M
M
(79)
And by change of measures, and independence of priors, we get
m,R,(
E
KL
P~
M
M
M
A/
(Ei
R.
m. R.(5
log
E SiMP
P-P
(80)
Therefore, Based Lemma (B.1) if define binomial random variable Y B(M, Rw:), replace the loss samples of all tasks as in
R.00
E
E
E
13
(81)
forP
s(n (R
Epap Byinpl
37
E
21
(82)
Where the last inequality comes from applying Lemma probability least 1 over sampling of S1,..., Sn, have:
B.3).
Therefore by Markov's inequality, with
Al
m. m,,,(1)) m. R.CA))) EE
log
e
S log
(83)
P-P fiePL
By combining
79
80 and
83
we get that with probability at least 8:
A
(Rw)
Rul S KL(2) + log 5
(84)
Or equivalently,
M
log(1 Rw Ry e Rw
KL(D|I + log(!))
(85)
A
À
B.4 Meta-Learning
In this section, we extend our results to meta-learning, i.e. learning an algorithm to use for future tasks based on unbalanced training tasks where task environments have different sample sizes in [1, m.maar,, using the framework introduced in (Zakerinia et al. (0224). Similar to multi-task learning, the previous works only focused task-centrie view, however, is also possible to study sample- centric meta-learning: when we care more about the performance of the tasks with more sample sizes, and can define the two following meta-learning objectives:
Rh)()) = E
A(S))
(86)
Amp (D.
END END
(p) = (D 2ND M.aa
m
f(2, A(S)
(87)
where p a meta-posteen reta-pposterio over the set of algorithms A. Each algorithm in A is function that given a dataset would generate posterior distribution A(S). Additionally, each algorithm can learn a hyper-posterior ((A) similar to multi-task learning. Therefore, for each algorithm we would use the two distributions. 1) 12( ()): hyper-posterior Q (A)) specific algorithm A (data-dependent) and task posteriors A(S)), and 2) ((A):: hyper-prior P(A) specific to algorithm A ddata-independent and priors P P P(A).
20

---

For the proofs, we define the following intermediate objectives, which are multi-task risks for A(Si)...... ................ Rr((p)
E [(2,. A(S:))
(88)
Amp n
Rs(p)
E Amp
E DrD;
8( A(S)))
(89)
M
We restate the notation introduced in the main body of the paper:
am(() sup
m. kl(ll)))))) S b, E [0. [0.11}
kl mi
Pe
(90)
==1
and the Catoni counterpart
①
(q.....
In
A1...., Am
(91)
mi Mirm00
n
sup
Ps
m, looll1111
Ps + D&e nm
xg + b, E 10.11]
(92)
B.4.1 Task-centric meta-learning
Theorem B.9 (Theorem 4.1 Equation (8)
For any fixed meta-prior and fixed set (()). any > O, and any X > O, it holds with probability at least å over the sampling of the training datasets that for all mela-posteriors, and hyper-posteriors Q(A):
4/nn
Rho (p) < kl
kl klml.... (e(l))...,,R((Ip)))
a) KL(P|(T) log
(93)
where C(p) = (L(pl]T) + EA
log = Σ log(2
Proof. Proof of this theorem consists of two steps. 1) upper-bounding (p),)) (p). (p(
and upper-bounding (p) based (p)... For the first step, define the following distributions:
Sample an algorithm A ~ p. sample (P, from 2(A).
Sample an algorithm A R, sample (P, fi..... fn) from P(A).
By the same proof steps Theorem B.5 by replacing Q and z with these two distributions, we
E
m. (((R,(((()))))(((((.)) s C(p) + log log(2
(94)
Arip
Therefore, by Jensen's inequality
m, kl((R(()) & C(p) + log
+
log(2 (2g(2.m)) m:)
(95)
g
1=1
Hence, with probability at least
RT(P) < kl .i,
(.. - -ai)
(96)
For the second part, note that by an application of the single-task learning bound, where each sample task from 7, we get that with probability least 1 :
A/n (R'(P) KL(p|TT log
Rh < kl,,'
(97)
8
By combining Equations 96 and 97 with union bound, complete the proof.
21

---

By the same reasoning, applied to Catoni-style task-centric multi-task and single-task bounds we get the following theorem:
Theorem B.10 (task-centric meta-learning, Catoni-style bound), For any fixed mela-prior n, and fixed set of (A), any > O, any AM > O, and any Xi >> 0, E [n) it holds with probability at least 1 å over the sampling of the training datasets that for all meta-posteed meta-posteriors, and hyper-posterioon (()):
Φ-1 (1- mi.....,
(P) S 1,
KL(o|(=) + log 8: AM
(98)
where C(p) (L)pT + Amp (L( log
B.4.2 Sample-centric meta-learning
Theorem B.11 (Theorem 4.1 Equation 19
For any fixed meta-prior n, and fixed set of (A)) any 5 > O, holds with probability at least 5 over the sampling of the training datasets that for all meta- pesta-osseriios, and kyper-posterion ((4):
(p) S kl,,'
M nimmaz
kl
(R(()) +
to)) KL(p|TT) + log 8
4yn
(99)
where C(p) (L(p]]T) + EA~ (L(2A))) log f. and c2 log(2v M).
Proof. Proof of this theorem consists of two steps. 1) upper-bounding (p).). based on (p).
and upper-boundigg bounding Rh based on (p).. Consider the same distributions as the proof of
Theorem B.11 With the same steps as the proof of Theorem B.7 Juuiing these distributions we get:
C(p) + log 2
(p)
S
(100)
M
Therefore,
M
(p)
M
kl (R)
(101)
Mmmax
M.maaa
and from Equations 2 we get
M
4yn (P) + log 8
R5) < kl,
(102)
nimmax
Combination these inequality with a union bound proves the theorem.
Analogously to above, using Catoni-style sample-centric multi-task and single-task bounds get the following theorem:
Theorem B.12 (sample-centric meta-learning, Catoni-style bound). For any fixed meta-prior x, and
fixed set of ((A), any 6 > O, any À O, and any AMr it holds with probability at least 1
over the sampling of the training datasets that for all meta-posteriors, and hyper-posteriors ((A):
M mimmax
2 (R()))(())))) (L(()))) + log j.AM AM
(p) S Φ--1
(103)
where C(p) = (L(p)) + Amp (L()(())))(())) - log 2 8"
22

---

C Experiments
C.1 Simulation
In this section, we provide more information and intuition on the (geometric) behavior of the bounds in Theorem 3.2 In Figure we illustrate the values of the bounds for toy example for
my m, 250, m2 150, R, 0.2, R2 0.2, 0.05, and KL 10. The shaded areas indicators of the areas that each constraint holds, and the goal is to maximize (RR, + R2), i.e. find feasible point as far as possible in the diagonal direction with slope 45 degrees.
Similar to single-task learning, the kl- kl-bound is a two-sided bound, which limits the deviation between R to R and can also give a lower-bound to the true risk. is parameter-free and can therefore be evaluated is. In contrast, Catoni bounds only provide an upper-bounds the risk, which emerge as convex curves in the [R,, R2) planes, parametrized by n parameters (here: Åι A2), which have chosen a priori (in inta-inddeendent way) for the bound to hold. The purple, orange and yellow regions in the figure illustrate different choices. For example, with x X = 700 (purple line), the guarantees from the Catoni-bount are worse than the ones provided by the kl-bound. With A1 = >2 200 (red curve), the resulting guarantees are better, though. Since a priori good values for the Äs are not clear, this observation suggests that in practice, beneficial combine the constraints from both bounds by a union bound, such that the resulting guarantees are always at least as good the better one of them.
An interesting phenomenon emerges when doing so for A 300, A2 = 400. The resulting bound value (yellow square) is in fact smaller than the minimum of the kl-bound the corresponding Catoni-bound individually, because the different geometric shapes of the constraint sets. While in this example the difference quite small, we find this an interesting observation that cannot occur in single-task learning (where the optimization problem is one-dimensional) and might be of independent interest.
Constraints and Maximizers for (R; R2)/2
kl-bound
Catoni bound, à; = =
Both constraint, A; 200., Az =00
Catoni bound. à; = 700, A 700
700
0.8
Both constraint, À; 700, à2 700
Catoni bound. A; =300, A 400
Both constraint, À: 300. à2 = 400
0.6
0.4
0.2
0.2
0.4
0.6
0.8
Figure 3: Illustration of the constraint and optimal value of bounds
23

---

Table Task-centric MTL: numeric results (in %, lower is better) for linear models on MDPR
simplicity
empirical risk
standard rate
fast-rate bounds Catoni-style
7
R.
bound
kl-style
with Mmin
oracle
0.00
21.4+0.1
38.
38.0+0.1
38.640.1
71.0+0.1
37.4+0.1
0.02
19.9+0.2
37.6+0.2
36.940.2
37. 37.340.2
70.5+0.1
36.2+0.2
0.04
13.7+0.1
32.5+0.1
31.0+0.1
30.7+0.1
67.3+0.2
30.4+0.1
0.06
6.440.2
25.9
22.7+00.1
22.640.1
60.510.3
22.2
0.08
2.3+0.1
21.0+0.3
16.440.3
16.740.3
51.540.7
15.8+0.3
0.10
1.1
18.7+0.3
13.640.3
13.640.3
45.540.6
13.0
C.2
MTL bound for linear models
In this section we provide the details for our numeric experiments on linear multi-task classification.
We use the MDPR dataset (Pentina & Lampert 2017). which consists of 953 tasks. Each task's data is a binary classification task of 25-dimensional feature vectors, which we augment with an additional constant feature simulate bias term. We aside random subset of 500 examples from each task as the test set and use the rest for training. The resulting training set sizes range between 102 and 22530 samples (average 2450, harmonic average 859.7), making the setting clearly unbalanced. In order to influence the simplicity of the task, we create variants of the dataset in which for each task, i, an offset Y) r) E [0, 1]] is added features X,, where Y; is the vector of labels. Larger values of result in an easier classification task and consequently smaller empirical risk (and ultimately also expected risk).
As model class, we use (stochastic) linear classifiers, fi(x) - sign( (i, ws) + b) with Gaussian distribution of fixed variance over the weight vectors: w; Q: =- N(u, olaxd) with = 0.1. For training we perform logistic regression with biased Frobenius regularization (Kienzle & Chellapilla 2006
min
Σ
E wl..o.
log(1 + exp(-yy' Ty)) + Alll - +/1
(104)
S
(2.y)ES,
We implement this problem in jax. We determine the mean vectors P1..... Pn by 25 steps of L-BFGS optimization with À = 0.001 using the optax package. To evaluate the stochastic classifiers we always sample weight vector from the corresponding distribution. After each step, we update the regularization bias to closed-form optimum, 1/ < Ei=14.
To evaluate the bounds, we use hyper-prior P = NO, Iaxa) and hyper Q = (WW, such that the KL-terms become
d KL(QIIP)
|/
(105)
E d 10² -1 11 -lloooo "'~N(vllexa)) 1114 1 E (L(Q))P) P~Q
(106)
1 (0² - -log 0²) +
2 -11 2
(107)
To numerically compute the non-explicit bounds, we fix = 0.05 and first compute the empirical In the task-centric setting, we then treat the unknown risks R.....,R. R,, as free
risks, R2 ........A R., optimization variables and numerically maximize R. Σ, R, subject to the inequality constraint specified to the bound of interest. In the sample-centric setting, we compute the empirical sample risk, Rs Σ, R, and solve for the scalar quantity R, again constrained by the respective bound.
For the Catoni-style bounds, the optimal value(s) are not clear a prior. Therefore, we instantiate these bounds with 11 values for À (where ê1 = ... = X, = À in the task-centric case), exponentially spaced [10-2.. rema, 102 rrmaa]] and with confidence values ă 0.05 We then combine resulting inequalities by union bound and solve the optimization problem subject to all of the constraints. We found the SLSQP optimizer, which is available in scipy optimize ze 's minimize's routine to work reliably and efficiently for all of these setups.
II

---

Table 3: Sample-centric MTL: numeric results (in %,, lower is better) for linear models on MDPR
simplicity
empirical risk
standard rate bound
fast-rate bounds
7
R
kl-style
Catoni-style
oracle
0.00
15.2+0.1
25.5+0.1
23.5
23.9=0.1
23.5
0.02
14.640.1
25.1+0.1
23.0+0.1
23.4_0.1
23.0+0.1
0.04
11.1+0.1
22.3+0.1
19.4
20. 20.1
19.4
0.06
6.310.3
17.940.2
13.5.0.3
13.6_0.4
13.5.0.3
0.08
2.8+0.1
13.840.2
8.0+0.2
8.0
8.020.3
0.10
1.740.6
12.2+0.7
5.941.1
6.1+1.0
5.9
and the numerical results, and Figures aaddeess[[nhhhooo the results graphically, which also include plot of the differences between the new fast-rate bounds and the original standard-rate ones. Additionally included is the value of the fast-rate oracle bound, i.e. the Catoni-bound if the optimal X-value(s) were known. In the task-centric case, can see that kl-style and Catoni-style bounds yield comparable values, slightly (for S 0.2) to clearly (for 1) 2 0.4) better than the standard-rate bounds. A small difference to the oracle bound remains, indicating that more involved procedure for choosing the X-values might be beneficial. In the sample-centric case, the kl-style bound achieves almost identical results the oracle one. The Catoni-style bound is slightly looser for 17 S 0.4, but then catches up to the other ones. Here, there is a clear improvement over the standard rate bound for all values of 17-
C.3
MTL bound for neural networks
In this section, we provide the details of the numerical experiments on multi-task learning with low-rank parametrized neural networks. We use the multi-task framework of (Zaerinnia et 2025). but generalize it to the unbalanced case, For learning n models fi...., fa E IR they use k random expansion matrices Gi...., , GR [Rdx! to form matrix = [ G2u2, ... [G E R to represent a subspace, and individual models are learned in the subspace ʃj fo Ga 0g R They follow by quantizing the model and encoding all trainable parameters using arithmetic coding.
For computing the bounds, for subspace G, we would define a prior P for a discrete set of models in G as P(f,) 2 2g-en(as), and the hyper-prior over priors (or equivalently sub- spaces) is P(G) 2 (c)) For the choice of Q; 8({i) and Q 5(G), we get bounds. For experiments,
KL (P) len fi f1...... fw) log 2, and we compute we use two multi-tast benchmarks: Cilit-CIFRROO and split- Selit-CIFA//OO (Krizhevsyy) 2009), which samples are distributed between tasks such that each task has data for out of 10 and 10 out of 100, respectively. We use Vision Transformer model (Dosovitskiy et al. (020) (~~ 5.5 million parame- ters) pretrained on ImageNet. For computing the numerical upper-bound Squares Programming (SLSQP), a gradient-based optimization algorithm that solves constrained nonlinear problems by iteratively approximating them with quadratic programming subproblems. For computing the Catoni bound, we choose equal A = À for all tasks. For task-centric bound we choose À cnm,, and for sample-centric we choose bound for values of The results are given in Table D For both views, the improvements from slow-rates to our fast-rates are visible. Specifically, the Fast-rate bounds of previous works (Guan Lu 2022 Zakerinia et al., (025) for balanced MTL would give at best the rate with mmmin which translates to even a worse result compared to slow-rate bounds. Additionally, the fast-rate behavior of more improvement when training error is small is visible between the easier task (split-CIFAR10) compared to the more challenging task (split-CIFAR 100).
use Sequential Least
cM for (0.5, 0.6,, ... 1.5) by a union
?Code: http://///gicbbb..cmm//aeaeeiiis
25

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Our claims accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how be expected to generalize other settings.
much the results
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss limitations in the Conclusion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
26

---

Justification:
We provide this information in the main body and appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We provide this information in the main body and appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
27

---

Answer:
[Yes]
Justification:
The code is available at
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nnps.cr
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ //iipe.cc/pullic/guuii wwwticccguie//eeeeeeeeeii CoodeSubeiiie ssi ssionnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provide this information in the main body and the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Where available, we report error bars over repeated experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
28

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification:
The computational requirements for our experiments are minor.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
Our research conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work is theoretical and conceptual, we do not expect societal impact besides the general consequences of advancing the field of machine learning.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
29

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not release model or data.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We provide references for the assets used.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
30

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our work does introduce new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our work does not involve crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our work does not involve crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
31

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: Our research does not rely on LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy for what should or should not be described.
32


Reviews:
[{"review_id": "V10XQnYOIb", "reviewer": "Reviewer_4gzb", "summary": "The work derives PAC-Bayes fast rates for multi-task learning (MTL) with unbalanced datasets.\nThere is prior work on PAC-Bayes for _balanced_ datasets, yet the authors provide a lemma that shows that the usual line of argument fails to go through in the unbalanced setting. \nThus, the authors provide an alternative argument that provides both kl-style and Catoni-style bounds. \nThe prior bounds are both provided in a task-centric (each task is given equal weight) and sample-centric (weight per task is proportional to number of samples for that task) form.\nPrevious fast-rates in the balanced MTL setting are able to be \"numerically inverted\" to provide bounds on the risk. \nThis work studies the non-trivial solution space of such numerical procedures for task-centric MTL.  Finally they conduct experiments to on linear and neural networks that demonstrate the benefit of their approach versus the rate that doesn't scale in aggregate (but with the size of the minimum sample) and the standard rate.", "questions": "* Is my remark about the meta-learning proofs above representative? \n\n* Reviewing the proof of Lemma 3.1 we see that the issue is that $\\mu$ is unbounded from below. We note that $\\mu$ small is exactly the situation in which we would expect a fact rate to be possible (small empirical error). What if $\\mu$ is small and bounded from below? (i.e., in a non-interpolation setting.) It seems that this removes this weakness of the prior analysis.\n\n* It seems to me that the bound with binomial upper bound (Lemma A.1) facilitates some information sharing between tasks. On one hand, your analysis recovers the balanced MTL setting so it seems your proof is the correct one. On the other hand, it seems that we're losing the information sharing via Lemma A.1 which seems like a bad idea. Is my intuition about the use of Lemma A.1 incorrect? \n\n* Do the authors have a sense of the geometry of the solution space for the numerical computation in Section 3.4? \n\n* Is there anything technically contrasting between task-centric versus sample-centric versions of the proofs? \n\n* Given Corollary 3.4, in comparison to the numerical numerical details in Section 3.4,  it seems that sample-centric is the nicer version of MTL  versus task-centric. Is that the sense of the authors? \n\n* On line 527 shouldn't it be $B(m_i, \\mathcal{R}_i(f_i)/m_i)? As it is doesn't seem to match with  Lemmas A.1-2. This same confusion similarly resides in the application of Lemma A.2 in the final inequality of Equation (53). (Both these also hold for the other proof too. )", "limitations": "* Task-centric rates for the risks are hard to bound due to the numerical complexity.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n* A study of unbalanced datasets in the PAC-Bayes setting is interesting particularly since it appears to differ from the PAC setting, in which it appears to me that everything goes through with standard arguments in the unbalanced setting. \n* Their study of task-centric and ample centric is natural and valuable. \n* The authors have identified a weakness in the previous arguments for deriving MTL bounds in unbalanced datasets. \n* The authors work recovers prior standard bounds in two senses. First, when all the tasks have the same number of samples we recover the balanced fast-rate. Second, the naive approach that would be dependent on the smallest sample size is unable to recover the standard rate (via the Pinsker's inequality trick).  Given these recoveries of prior work it seems that this is the more correct analysis of MTL learning in general and therefore clarifies the literature to the nuance between balanced and imbalanced datasets. \n* I appreciated the experiments. In particular Figure 1 that shows the benefits of their method as the task becomes easier which shows the benefit of their approach.  \n* The discovery that kl-bounds have difficult numerical inversion in the task-centric version.\n\n**Weakness**\n* In comparison to prior work, the technical innovation appears to be applying Lemma A.1 to each task independently. Then, after applying Lemma A.2 the harmonic mean is intimidate. \n* The difficulty of numerical inversion the task-version appears to limit the applicability of that particular rate (although this may be natural).\n* I appreciate the detailed treatment of meta-learning, yet it appears that once the MTL rates are derived the remaining meta-learning analysis is standard.", "was_revised": true, "final_justification": "I had a productive conversation with the authors wherein my major theoretical concerns were addressed. I didn't trace through every technical detail of the discussion between the AC and the authors. Yet, I see the technical challenges in extending fast rates, at least in the Bayes setting, to unbalanced datasets. As unbalanced datasets are ubiquitous, a dedicated study of these rates is appreciated. As pointed out by the AC, the experiments are at best hard to interpret. In all, I keep my rating. While the contribution of the work towards our understanding in MTL is moderate, illuminating the differences between imbalanced and standard datasets, along with their associated fast rates, is acknowledged.", "rebuttal": "Thank you for your expert review. In the following we hope to answer your questions. We hope it addresses your concern and that you will support our work in the following process. \n\n\n\n\n>  the technical innovation\n\n\nAs common in PAC-Bayesian theory, it is not that one specific step of the proof is of high technical depth, but our contribution lies in the choice which individual objects to define and how to combine them in order to achieve optimal rates.\nFor Theorem 3.2, we take insight from our lower bound in Lemma 3.1 (which is another technical contribution) and define separate terms for different tasks; however, we then use a shared change of measure step to keep as much information as possible shared among tasks and establish the optimal dependency on the sample sizes. We also bound the moment generating functions of each task separately, because the proof of Lemma 3.1 suggests that a joint bound would lead to a suboptimal rate. \n\n\n> remark about the meta-learning proofs  \n\nIndeed, on the technical level, the main challenge of meta-learning bounds is usually to establish the multi-task part. However, we believe the meta-learning bounds are also of interest to the community, and we are not aware of prior work on sample-centric meta-learning at all so far. So, we do not consider including them a weakness. \n\n\n> what if μ is bounded from below?\n\n\nThank you for the remark. A lower bound on $\\mu$ would indeed solve the unboundedness of the MGF. However, as seen in the proof of Lemma 3.1, many terms with inverse dependence on $\\mu$ would remain. Therefore, this approach would yield a trade-off between a high lower bound on $\\mu$ (which is the object for which we hope to have a small upper bound) or a high upper bound on the MGF. The nice property of the MGF bound we apply is that the dependency of $\\mu$ vanishes and we get a term independent of it solely based on $n$ and $m_i$. \n\n\n> intuition about the use of Lemma A.1\n\n\nWe would argue that the main source of information sharing is the joint change of measure for all tasks at the same time, which we preserve in our proof (although with the sum of independent terms). The information loss due to the independent use of Lemma A1 and A2 per task can be seen in the additional log terms. It would be interesting to explore if these can be avoided. However, the dominant indicator of information sharing (the KL term) has the correct dependency on $n$ and $m_i$.\n\n\n> geometry of the solution space\n\n\nGiven their functional forms, we vaguely think of the Catoni bound as a “linear-ish” upper bound (in particular single-sided), whereas the kl-bound is a “ball-ish” and double-sided. A deeper geometric understanding of the bounds and their interaction could indeed be fruitful. \n\n\n> Is there anything technically contrasting between task-centric versus sample-centric versions of the proofs?\n\n\nThe proof of the sample-centric bound is more “standard”: we can bound all tasks with a single term, and we do not face the mentioned limitation on MGF, so it is more straightforward to get the results, and it has a better log dependency. In contrast, in the task-centric setting one has to be more careful in proof steps to avoid the setting of Lemma 3.1, and the fact that split expressions earlier comes at the cost of the additional log terms. \n\n\n> it seems that sample-centric is the nicer version of MTL versus task-centric\n\n\nWe believe that the question of sample-centric versus task-centric depends on the application, i.e. which risk reflects the actual object of interest more appropriately. That said, the sample-centric view behaves more similarly to the balanced case, and the analysis is indeed mathematically nicer. \n\n\n> in line 527 shouldn't it be $B(m_i, \\mathcal{R}_i(f_i)/m_i)$? \n\n\nWe use the notation $B(n,p)$ for a binomial distribution where n is the number of “trials” and p is the “success” probability of each trial. Here we insert the number of samples $m_i$ and their mean $\\mathcal{R}_i(f_i)$. The confusion might come from the statement of Lemma A.1. in which there is a term $\\mu/t$. Note, however, that in that statement, $\\mu$ is the expectation of the sum of $t$ terms, which makes  $\\mu/t$ the mean. We will clarify this in the manuscript.\n\n\n> Task-centric rates for the risks are hard to bound due to the numerical complexity.\n\n\nWe agree that having this additional optimization step is a bit of a nuisance. However, the actual optimization is possible using standard toolboxes and not actually numerically expensive compared to the model training itself. \n\n\n> Paper Formatting Concerns:\n\n\nThanks for spotting these, we will fix them."}, {"review_id": "pSCSq8Bp0w", "reviewer": "Reviewer_cSyd", "summary": "This paper provides fast risk bounds for multi-task learning and meta-learning, where different tasks could have different sample sizes. It argues that previous bounds cannot be easily generalized to varying sample cases, and argues for a different proof technique required for handling different sample sizes. It also evaluates the bounds numerically on various tasks and show that it improves over the previous bounds.", "questions": "1. Why can't the proof of Guan & Lu 2022 be generalized to different sample sizes? As stated before, I think in Proposition 6, the error can be split over various tasks separately.", "limitations": "I think the comparison to previous works and why those cannot be extended to different sample sizes needs to be properly addressed.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 1, "strengths_and_weaknesses": "The main strength of the paper is the generalization of prior bounds on multi-task and meta-learning. It argues that previous bounds cannot be easily extended to the case of different sample sizes. However, in my opinion, this does not seem true. Looking at bounds of Guan & Lu 2022, the fast bounds for meta learning can be easily generalized to different sample sizes. Using their notation, $\\tilde{err}(Q) - \\hat{err}(Q)$ in the paper is currently bounded in Proposition 6 in the Appendix. It gives a rate of $1/mn$, assuming n tasks and m samples per task. Instead simply splitting $\\tilde{err}(Q) - \\hat{err}(Q)$ over different tasks (as in Proposition 3) would give the error rate dependent on each $m_i$ separately.", "was_revised": true, "final_justification": "The rebuttal response clarified the concern I had. I have updated my score accordingly.", "rebuttal": "Thank you for your review. Your critique seems to be based on the impression that our result lacks relevance, as you suggest an alternative technique for bounding the multi-task risk. However, we believe this to be a misunderstanding that we would like to clarify in the following. \n\n\nIf we read your description right, you suggest a two-stage strategy: first, bound the risks for each task separately, and then combine the resulting bounds. The first step would indeed result in $n$ individual bounds with rates $1/m_i$. The problem emerges in the second step of how to combine the bounds into an overall multi-task risk. Specifically, the average $1/n \\sum_i 1/{m_i}$ does not improve with increasing $n$. Furthermore, combining high probability bounds will typically require a union bound across tasks, which results in an additional $log(n)$ term. For example, in the balanced case, the resulting bound would have a rate $O(log(n)/m)$, which increases with the number of tasks instead of decreasing. In comparison, our bounds scale like $O(log(n)/nm)$ in this case. \n\n\nWe hope that in light of these clarifications you reassess your assessment of our contribution. If you have further questions or concerns, we would be happy to answer them during the discussion phase."}, {"review_id": "cjsmyXaW37", "reviewer": "Reviewer_7kbH", "summary": "This paper derives new, fast rates for the multi-task and meta learning problems under imbalanced sample sizes per task. The authors provide results in a PAC-Bayes framework, which situates their contributions within both the MTL/ML and PAC-Bayes literatures. Their results bring to light new phenomena in the behavior of multi-task and meta-learning with imbalances sample sizes.", "questions": "1. What are the key technical challenges of the proofs of Theorems 3.2, 3.3, and 4.1? What differentiates the proof techniques used in this paper from existing techniques that are, seemingly, provably suboptimal?\n\n2. My understanding is that the novel behavior that the authors uncover in imbalanced multi-task learning is most prevalent in the task-centric setting. What is the authors' intuition for why task-centric multi-task learning is more affected by imbalanced sample sizes than the sample-centric analog?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths: The paper is exceptionally well-written and clearly motivated. The authors provide an excellent background for the problem under consideration. In particular, Lemma 3.1 demonstrates formally the necessity of the contribution of this work. The main theoretical results are clearly written and genuinely novel. The simulations support the bounds numerically.\n\nWeaknesses: It is not clear that proofs of the theorems are significantly different from existing results on a technical level. I am not an expert in PAC-Bayes, but my reading of the proofs is that they broadly follow the same structure as existing proof techniques. Upon my current reading of the paper, this slightly detracts from the work's novelty, but I look forward to discussing the nuances of the proof with the authors in the discussion section.", "was_revised": true, "final_justification": "The paper is well written, and the authors have answered by questions in the rebuttal regarding the technical difficulty of the paper.", "rebuttal": "Thank you for the insightful review. I hope our reply will address your questions. \n\n\n> key technical challenges of the proofs: \n\n\nIndeed, the proofs of PAC-Bayesian results often consist of similar steps, but the details matter in order to obtain tight guarantees. For Theorem 3.2, **the technical novelty lies in the choice which individual objects we define and how we combine them**: inspired by our lower bound in Lemma 3.1, we define separate terms for different tasks; however, we then use a shared change of measure step to keep as much information as possible shared among tasks and establish the optimal dependency on $n$. We also bound the moment generating functions of each task separately, because the proof of Lemma 3.1 suggests that a joint bound would lead to a suboptimal rate. \nFor Theorems 3.3 and 4.1, our contribution is mostly conceptual as we introduce a new (sample-centric) objective that better matches the requirements of some multi-task applications; however, the community did not look at it before. The proof of the results only required standard existing proof techniques. \n\n\n>  What is the authors' intuition for why task-centric multi-task learning is more affected by imbalanced sample sizes than the sample-centric analog?\n\n\nThe main point is that in the task-centric setting, samples from different tasks have different importance/weights, i.e. the “rare” samples from low-budget tasks influence the loss more than samples from the tasks with more samples. Controlling this difference introduces more challenges compared to the sample-centric in which all samples have the same importance."}, {"review_id": "bZiJQt5AzC", "reviewer": "Reviewer_Co3j", "summary": "The authors develop PAC-Bayesian risk bounds for the multi-task and meta-learning settings, in both cases taking care to give bounds for the unbalanced regime (where each task can have a different number of samples) that can give fast rates, even in situations where there exists a task with only a small number of samples. The focus is both on the simple average of tasks and a sample-size-weighted average (task-centric and sample-centric respectively) .The multi-task risk bounds are both of kl-type and Catoni-type, while the meta-learning risk bounds are of kl-type. Along the way, the authors show that the downside of existing (\"standard\") multi-task learning bounds in the unbalanced regime, while also showing how the perhaps-most-straightforward PAC-Bayesian analysis method cannot be useful when there exists a task whose number of samples is very small. The authors lightly touch upon computational issues related to getting the best possible bound from their (implicit) risk bounds. Finally, the authors demonstrate how their bounds fare in practice compared to some standard bounds and a more naive fast rate bound.", "questions": "1. What would you say is the core technical novelty behind your results? Having looked over some of the proofs, I think it would suffice if you restrict your attention (when answering this question) to the proof of Theorem 3.2\n\n2. Can you point out what bound you are using when you write \"Fast rate with $m\\_{\\\\min}$\" in the experimental results in the main text?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "## Strengths\n\nTo my knowledge, prior works haven't shown fast rate PAC-Bayesian risk bounds for settings where tasks have variable sample size (the unbalanced setting). I can see that there is some value in filling in this gap, whether in the multi-task setting or the meta-learning setting. Related to the lack of prior coverage of the unbalanced setting, I don't believe the issue of bounds plagued by $m\\_{\\\\min}$ has previously been raised, and the authors did well in highlighting how a naive approach and some existing bounds can suffer when the minimum sample size (among the training tasks) is very small.\n\nAnother interesting aspect of this work, which unfortunately was severely under-discussed in the main text, is the computational issue of going from the authors' bounds (which are implicit, involving, e.g., Bernoulli kl-divergence terms in the case of the kl-type bounds) to the best possible bound on the multi-task risk (say, the simple average). This issue strikes me as extremely interesting, and the authors apparently have thought about this a lot due to the extra material in the appendix (which, out of respect of the page limit and since it was new content not supporting results appearing in the main text, I regret to say I could not review out of fairness to the other papers in submission to NeurIPS this year). Going forward, I encourage the authors to devote significant attention to this computational aspect in the main text, including at least one figure. This might be where the key technical contribution actually lies for your work. You might even have new theorems as part of this (like, extracting the best possible explicit bound given your existing implicit bounds). In truth, the under-coverage of the computational aspect in the main text is a weakness that can be turned into a major strength.\n\nI think it is nice that the authors made explicit the task-centric and sample-centric objectives. I can't say that this is terribly novel, as task-centric is standard and (without even checking) I feel that sample-centric should have appeared in some works before. Even so, formalizing all of this, along with presenting bounds for each case, is nice.\n\nThe experimental results are encouraging. I have a question about precisely what bound was used for \"Fast rate with $m\\_{\\\\min}$\".\n\n\n## Weaknesses\n\nI felt the paper is quite lacking when it comes to describing how the technical ideas in the present paper relate to previous works. For example, Theorem 2.1 (which I understand the authors do not claim to be a novel result but simply present as a way to provide context for their upcoming, new results) seems to essentially be due to Pentina and Lampert (2014). Yet, the proof in the appendix is written from scratch, without giving credit to previous, related results. \n\nI found to be underwhelming the technical novelty behind the authors' new risk bounds (e.g., Theorem 3.2). Inspection of the proof reveals that the authors follow a standard PAC-Bayesian analysis modulo the application of Lemma A.1; the application of that lemma is similar to how the lemma is used in the work of Zakerinia et al. (2025). I found the lack of a majorly new technical idea to be surprising because the authors say — both in their Introduction and their Section 3 — that their contribution is technical. For a venue like NeurIPS and a paper that positions it as theory paper (as the authors do), please take care to explain what the technical hurdles were.\n\nLess major 1: From the writing, I felt the authors were suggesting that Lotfi et al. (2024) considered PAC-Bayesian bounds. I believe this work only considered compression bounds. It would be better to adjust the writing to avoid sending an incorrect message (please correct me if I'm wrong; I could not find PAC-Bayes bounds in the work of Lotfi et al.).\n\nLess major 2: A somewhat minor presentational aspect is this the authors do not make clear where the proofs of various results happen. For example, a search for \"Theorem 3.2\" in the appendix does not turn up any results. Instead, I eventually found two theorems in the appendix which together provide the two statements of Theorem 3.2.\n\n\n## Additional comments\n\n\nA few comments on the appendix:\n\nLine 495: $\\\\mathcal{R}\\_u$ and $\\\\hat{\\\\mathcal{R}}\\_u$ were never defined, although I could infer their meaning.\n\nLine 506: for completeness you should mention that you're using a geometric grid rather than using a union bound over the infinite set $(1, 4 n m\\_h]$.\n\nEquation (51): Here and in some places below here, the summation should be pulled to the outside; as written, $f\\_i$ is out of scope (since $i$ is \"out of scope\" in the computer-science sense).\n\nLines 527–528: It would help to provide more explanation on precisely which function $f$ you consider (when applying Lemma A.1), what choice of $X\\_i$ you use, etc. I figured this out myself but it took a bit of time as I had to write everything out. Also, note that you are missing an expectation with respect to $f\\_i$ just after the inequality in equation (53).", "was_revised": true, "final_justification": "In my initial review, I indicated that the technical novelty behind the authors' new risk bounds is low. The author response did not provide evidence that there are new technical ideas here. I reiterate that for the proof of Theorem 3.2, the analysis is standard up until the application of Lemma A.1, and that lemma's application is similar to what happened in Zakerinia et al. (2025).\n\nOn the other hand, I agree with the authors that their results cannot be obtained in the ways suggested by one reviewer and the AC. Instead, my criticism is that what the authors actually do is a technically minor contribution compared to the proofs in previous results.\n\nI am borderline on this paper but am not opposed to the paper being accepted.", "rebuttal": "Thank you for your helpful review. We hope our response answers your questions and addresses your concerns.\n\n> Question 1: What would you say is the core technical novelty behind [...] the proof of Theorem 3.2 \n\nAs common in PAC-Bayesian theory, it is not that one specific step of the proof is of high technical depth, but our contribution lies in the choice which individual objects to define and how to combine them in order to achieve optimal rates.\nFor Theorem 3.2, we take insight from our lower bound in Lemma 3.1 (which is another technical contribution) and define separate terms for different tasks; however, we then use a shared change of measure step to keep as much information as possible shared among tasks and establish the optimal dependency on the sample sizes. We also bound the moment generating functions of each task separately, because the proof of Lemma 3.1 suggests that a joint bound would lead to a suboptimal rate. \n\n> Question 2: what bound you are using when you write \"Fast rate with “m_min\" in the experimental results in the main text?\n\nWe will make this more explicit in the manuscript. It is the bound that we get by following the standard MGF bound steps of Lemma 3.1 with choice $\\lambda = m_{min}$ (i.e. similar to the bounds of  Guan & Lu (2022) and Zakerinia et al. (2025).)\n\nWe would also like to comment on some other parts of the review, hoping that this will address some of your other concerns. \n\n> Computational issue of going from the implicit to explicit bounds: \n\n\nThank you for this encouraging discussion and suggestion. Indeed, we are aware of this aspect and its importance for connecting MTL theory to real applications. However, we found it orthogonal to the main results in the manuscript, which is why we included the material only in the appendix. Given your encouragement, we will try to make the aspect more prominent. \nOf course, we respect your choice not to review it. However, we would like to emphasize that the appendix was submitted at the same time as the main body of the paper, so its content is not the result of additional time, and we do refer to the appendix in the main body. \n\n\n> relation of Theorem 2.1 to previous work\n\nAs you mention, Theorem 2.1 is part of the background section, not an actually new theorem. It is indeed similar to the classical results of Pentina and Lampert (2014), but the complexity term has a different (simpler and more modern) shape. We are not aware that this bound with square root dependence and different sample sizes was ever presented in prior works, so we provide its proof for completeness.  We will be happy to clarify this in the manuscript and expand the discussion. \n\n> nature of technical contribution\n\n\nWe consider our contribution technical as well as conceptual (lines 42 and 148). The technical aspect lies in formally deriving the roadblock in why prior approaches were not able to derive fast rates in the unbalanced setting and in deriving a construction that overcomes them. Please also see our response above. Our fast-rate bounds could not have been derived by just following the steps of Guan&Lu (2022) or Zakerinia et al. (2025). At best a result with $\\lambda= m_{min}$ like Lemma 3.1 would have emerged. \nThe conceptual lies observing that two MTL scenarios make sense in the unbalanced setting, both should be treated by different bounds. \n\n> description of Lotfi et al. (2024)\n\nThanks for noticing this, we will clarify this in the manuscript. Lotfi et al. (2022) is indeed formulated as PAC-Bayesian, and it introduces the case of a finite hypothesis set as a special case. Lotfi et al. (2024) adopts the same finite-hypothesis setup, but does not phrase it as PAC-Bayesian anymore. \n\n> connection of proof in the Appendix to theorem \n\nThank you for the helpful feedback. We will make the connections between main text and the Appendix clearer, including explicit statements about the proofs.\n\n>Additional comments\n\nThanks, we'll fix these."}]

Author rebuttal:

Meta-review: The paper studies fast-rate generalization bounds for multi-task learning (MTL) and meta-learning in the unbalanced setting where tasks have unequal sample sizes. The authors argue that unbalancedness changes the statistical picture relative to the balanced case and that prior proof strategies do not carry over directly. They formalize two distinct settings, task-centric (equal weight per task) and sample-centric (weight by task size), and derive PAC-Bayes KL-style and Catoni-style fast-rate bounds for MTL (and KL-style bounds for meta-learning). Experiments on linear models (MDPR) and low-rank neural networks (split-CIFAR10/100 with ViT features) demonstrate cases where the proposed fast-rate bounds are numerically tighter than standard-rate baselines. The contribution is primarily theoretical; the experiments are illustrative of the bounds’ numerical behavior.

Remaining concerns

1. Related work on fast PAC (non-PAC-Bayes) rates for MTL. The paper completely omits prior fast-rate PAC results for multi-task learning. Because a central question here is what does and does not carry over to the unbalanced setting, a concise survey and a direct comparison would help. In particular, it would be useful to spell out which fast-rate PAC arguments fail (or continue to hold) under task imbalance and why (as also surfaced in the OpenReview discussion).

2. What do the bounds tell us; when is the KL small? The main bounds hinge on the hyper-level divergence KL(Q‖P) between a hyper-posterior and hyper-prior. While the resulting bounds are data-dependent, the paper provides little guidance on when this KL is small in realistic pipelines (e.g., sublinear in the number of tasks n), or how prior/posterior design choices (representations, sharing mechanisms) influence it. At the two extremes, if tasks are independent, the effective complexity decomposes per task, and pooling brings no benefit; if tasks are identical, the favorable KL is unsurprising. What would be an “interesting middle”, a structural characterization of relatedness under which MTL provably helps? In PAC (non-PAC-Bayes) treatments, one often sees explicit notions of task diversity/relatedness leading to rates on the order of 1/(m n) in the balanced case (m samples per task, n tasks). I would even argue that this is what makes the prior work on PAC rates for MTL so helpful and impactful. An analogous insight is not yet articulated here.

3. Purpose and informativeness of the experiments. The bounds require numerical inversion/optimization and do not presently translate into obvious algorithmic choices (e.g., task reweighting, prior design). In the experiments, the hyper-prior is taken to be standard normal, and the resulting comparisons largely mirror how different effective sample sizes behave (e.g., 1/(n·min m_i), 1/(n·m_h), 1/√(n·m_h), where m_h is the harmonic mean of {m_i}). This renders the section largely pointless, merely serving as a check of “bound geometry” rather than an investigation into when the theory is informative for realistic training decisions. The added notion of “simplicity” also appears orthogonal to task-relatedness, so it doesn’t bridge that gap.
Decision: Accept (poster)