Fast Rate Bounds for Multi-Task and Meta-Learning with Different Sample Sizes

Thank you for your helpful review. We hope our response answers your questions and addresses your concerns.

Question 1: What would you say is the core technical novelty behind [...] the proof of Theorem 3.2

As 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. For 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.

Question 2: what bound you are using when you write "Fast rate with “m_min" in the experimental results in the main text?

We 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).)

We would also like to comment on some other parts of the review, hoping that this will address some of your other concerns.

Computational issue of going from the implicit to explicit bounds:

Thank 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. Of 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.

relation of Theorem 2.1 to previous work

As 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.

nature of technical contribution

We 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. The conceptual lies observing that two MTL scenarios make sense in the unbalanced setting, both should be treated by different bounds.

description of Lotfi et al. (2024)

Thanks 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.

connection of proof in the Appendix to theorem

Thank you for the helpful feedback. We will make the connections between main text and the Appendix clearer, including explicit statements about the proofs.

Additional comments

Thanks, we'll fix these.

Thank you for the insightful review. I hope our reply will address your questions.

key technical challenges of the proofs:

Indeed, 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. For 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.

What is the authors' intuition for why task-centric multi-task learning is more affected by imbalanced sample sizes than the sample-centric analog?

The 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.

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.

If 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.

We 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.

Dear AC,

Given that there are just a few minutes left, we only provide a very short answer.

We can not find any work on MTL that does not have information sharing, and our claims and analysis are also about real MTL bounds.

About the rate, we wanted to improve dependency over $min_i m_i$ to achieve a bound with a better sample complexity than $n m_{min}$. The bound you provide has the sample complexity of $n$.

As I said, my question was prompted by the comment from reviewer cSyd, and I did read your response to the reviewer carefully. Here is how you could use empirical Bernstein:

Apply a per-task empirical Bernstein (Audibert--Munoz--Szepesv'ari--style) bound: for each $i$, with probability $\ge 1-\delta_i$,

$R_i - \hat R_i \le \sqrt{\frac{2 \hat V_i \log(2/\delta_i)}{m_i}} + \frac{7 \log(2/\delta_i)}{3(m_i-1)},$

where $\hat V_i$ is the empirical variance of losses in task $i$.

Pick $\delta_i = \delta/n$ and take a union-bound over $i$. Averaging over tasks yields, with probability $\ge 1-\delta$,

$R_T - \hat R_T \le \frac{1}{n}\sum_{i=1}^n \sqrt{\frac{2\hat V_i \log(2n/\delta)}{m_i}}+ \frac{7 \log(2n/\delta)}{3n}\sum_{i=1}^n \frac{1}{m_i-1}.$

If you want a single compact rate, use $\hat V_i\le 1/4$ to get

$R_T - \hat R_T \lesssim \sqrt{\frac{\log(n/\delta)}{2n}\sum_i\frac{1}{m_i}} + O\left(\frac{\log(n/\delta)}{n}\sum_i\frac{1}{m_i}\right),$

again driven by $\sum_i 1/m_i$ (or $m_h$).

Equal $\delta_i$ is clean, but one can sometimes reduce constants by giving larger $\delta_i$ (looser confidence) to tasks whose bound is already tight (large $m_i$) and {smaller} $\delta_i$ (tighter confidence) to tasks with few samples. For example, $\delta_i = \delta \frac{m_i^{-1}}{\sum_{k=1}^n m_k^{-1}}$ or $\delta_i = \delta \frac{m_i}{\sum_{k=1}^n m_k}.$

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.

the technical innovation

As 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. For 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.

remark about the meta-learning proofs

Indeed, 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.

what if μ is bounded from below?

Thank 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$.

intuition about the use of Lemma A.1

We 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$.

geometry of the solution space

Given 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.

Is there anything technically contrasting between task-centric versus sample-centric versions of the proofs?

The 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.

it seems that sample-centric is the nicer version of MTL versus task-centric

We 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.

in line 527 shouldn't it be $B(m_i, \mathcal{R}_i(f_i)/m_i)$?

We 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.

Task-centric rates for the risks are hard to bound due to the numerical complexity.

We 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.

Paper Formatting Concerns:

Thanks for spotting these, we will fix them.