REVIEW 2 major objections 4 minor 4 references
When More Data Doesn't Help: Limits of Adaptation in Multitask Learning
T0 review · 2 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read Even arbitrarily large per-task samples cannot make multitask learning adaptive.
desk verdict The headline result has a serious proof gap: a Θ(1) term is dropped in the KL bound, so Theorem 5.2 is unproven as written. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The argument rests on an 'Approximate Multitask' random construction: each source is fair with probability $\alpha_F=t^*/N$ and noisy otherwise, so the observed data are drawn from a mixture distribution. The impossibility is then reduced via Fano's inequality to a binary hypothesis-testing problem between the two possible labels $\sigma$ and $1-\sigma$, and the load-bearing step is bounding the KL divergence $D_{\mathrm{KL}}(P^\sigma\,\|\,P^{1-\sigma})=O(1)$ between the mixture laws. That bound (Appendix C, Eqs. (13)-(20)) is obtained by linearizing log-ratios with $\log x\le x-1$ and applying Bernoulli's inequality inside binomial expectations; together with the Bernstein class condition (parameter $\beta$) that controls the label noise of the construction, this makes the Fano lower bound hold.
What would settle it
Evaluate numerically, or by a sharper analytic bound, the quantity $D_{\mathrm{KL}}(P^\sigma\,\|\,P^{1-\sigma})$ for the mixture model of Section 5.1 at, e.g., $\beta=1/2$, $n=2$, and $N=2^{n\beta/(1-\beta)}=4$ (and larger $N$ satisfying the stated condition) and check whether it remains $O(1)$ as $N$ grows. If any permitted choice of $\beta,n,N$ yields a KL divergence that grows without bound, the Fano lower bound of Theorem 5.2 would fail, and the claimed $\Omega((n\sqrt{N})^{-1/(2-\beta)})$ rate would not follow. Equivalently, one could directly implement the optimal hypothesis test for the constructed family and see whether a mistake probability bounded below by a constant is actually forced.
Extended reading notes
Core claim
Theorem 5.2 states that, for any $n>0$, if the number of tasks satisfies $N\ge n^{n\beta/(1-\beta)}$ and there are $t^*=\sqrt{N\,n^{n\beta/(2-\beta)}}$ fair sources (each drawn from the target distribution $P$) among the $N$ independent sources while the remaining sources are noisy, then any adaptive algorithm given the union of all datasets has expected excess risk $\mathbb{E}[\mathrm{er}_D(A(Z))]=\Omega((n\sqrt{N})^{-1/(2-\beta)})$. The minimax rate over the same class when the learner is told which sources are fair is $O((n t^*)^{-1/(2-\beta)})=o((n\sqrt{N})^{-1/(2-\beta)})$, so the adaptive learner is provably suboptimal. Because this holds for arbitrarily large $n$, the paper concludes that having abundant per-task data cannot overcome the failure of adaptation in multitask learning.
Load-bearing premise
The theorem stands on the claim that the KL divergence between the two mixture distributions is bounded by a universal constant, which is proved in Appendix C by the inequalities $\log x\le x-1$ and Bernoulli's inequality; if that bound fails for some $\beta\in(0,1)$ and $n>0$ in the stated parameter regime, the Fano-based argument collapses. A second scope assumption is that the number of tasks is super-exponential in the per-task sample size, $N\ge n^{n\beta/(1-\beta)}$, so the impossibility applies only to regimes with enormously many tasks.
Editorial extensions
If this is right
- Any adaptive algorithm that pools sources must pay $\Omega((n\sqrt{N})^{-1/(2-\beta)})$ excess risk on the constructed family, so increasing per-task sample size $n$ does not close the gap to the minimax rate.
- Pooling, i.e., running ERM on the union of all datasets, achieves $O((\log(nN)/(n\sqrt{N}))^{1/(2-\beta)})$ in this construction, which is optimal up to a logarithmic factor among adaptive algorithms.
- This result removes the per-task sample-size restriction of earlier no-free-lunch theorems and shows the impossibility is intrinsic rather than a small-sample artifact.
- The paper identifies an open problem of optimal adaptivity: finding the minimax-optimal adaptive rates and algorithms for multitask learning.
- The impossibility requires a super-exponential number of tasks ($N\ge n^{n\beta/(1-\beta)}$), leaving open, and motivating, the possibility of adaptation when the number of tasks is far smaller.
Reading between the lines
- Editorial: the super-exponential task requirement puts the impossibility far outside practical multitask settings, so the practical lesson may be the opposite: with polynomially many tasks, adaptation could be feasible, and the paper's Section 6 explicitly asks for a polynomial threshold separating possible from impossible adaptation.
- Editorial: the lower-bound rate $\Omega((n\sqrt{N})^{-1/(2-\beta)})$ corresponds to an effective sample size of $n\sqrt{N}$, suggesting that source uncertainty costs a factor $\sqrt{N}$ in pooled sample size; a testable conjecture is that the optimal adaptive rate for general multitask problems is the minimax rate evaluated at $n\sqrt{N}$ samples.
- Editorial: the KL-mixture bounding technique (log-linearization plus Bernoulli's inequality) may transfer to other heterogeneous-data settings such as federated or meta-learning, where the identity or reliability of the data provider is unknown; one could try to prove analogous impossibility results there or identify regimes where the $O(1)$ KL bound can be sharpened.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the statistical limits of adaptation in multitask learning. Building on the no-free-lunch theorem of Hanneke & Kpotufe (2022), it claims a stronger impossibility result: for any per-task sample size n, no adaptive algorithm that is given only the pooled source datasets can achieve the minimax rate, provided the number of tasks N is at least n^{nβ/(1−β)}. The construction uses binary classification with two hypothesis types and Bernstein-class margin conditions with exponent β∈(0,1). The proof proceeds by a random construction in which each source is fair with probability α_F = t*/N and noisy otherwise, and then applies Fano's inequality. The paper also studies the agnostic (β=0) case, showing that pooling is suboptimal, and shows that in the new construction pooling achieves the lower bound up to logarithmic factors. All proofs are deferred to the appendix.
Significance. If the main claim were established, the paper would resolve an open question from Hanneke & Kpotufe (2022) and would convey a genuinely interesting message: more data per task cannot cure the impossibility of adaptation in multitask learning, at least when the number of tasks is super-exponential in n. The paper is transparent about its dependence on prior work, the construction is explicit, and the discussion of optimal adaptivity in Section 6 is a useful framing for future work. The agnostic-case analysis and the pooling optimality result are also valuable as partial characterizations of adaptive behavior. However, the central theorem hinges on a KL-divergence calculation in Appendix C that contains a serious algebraic gap; as written, the main impossibility result is not proven.
major comments (2)
- [Appendix C (proof of Theorem 5.2, paragraph 'In the following, we analyze each summand separately')] The bound t*·E_P[VF,σ/VN,σ] = O((t*)²/N · (1/n)^{nβ/(2−β)}) is not justified. The computation correctly gives E_P[VF,σ/VN,σ] = (α_F/α_N)·A^n with A = p_{σ,x1}²/q_{σ,x1} + p_{1−σ,x1}²/q_{1−σ,x1} + p_{1,x0}²/q_{1,x0}. With ε=(n√N)^{-1/(2−β)} and ε0=(nN)^{-1/(2−β)}, the two x1 terms are each Θ(n^{-β/(2−β)}), while the x0 term equals (1−Cβ ε^β)²/(1−Cβ ε0^β) = 1 − Θ(ε^β), which is of order 1. Hence A = 1 + Cβ n^{-β/(2−β)} + o(n^{-β/(2−β)}), and therefore A^n = exp(Θ(n^{1−β/(2−β)})), not n^{-nβ/(2−β)}. The displayed bound drops the O(1) term inside the n-th power, and the resulting product with (t*)²/N is ω(1), not O(1). Thus the claimed D_KL(Pσ||P1−σ) = O(1) does not follow from the equations as written.
- [Theorem 5.2, proof item 1⃝] The Fano-based lower bound in the proof of Theorem 5.2 requires min{D(Pσ||P1−σ), D(P1−σ||Pσ)} ≤ O(1). The Appendix C calculation is the only support for this condition, and it contains the error described above. Consequently item 1⃝ in the proof sketch — that with probability at least c1 no estimator can identify σ correctly — is unsupported, and the lower bound E[E_D(A(Z))] = Ω((n√N)^{-1/(2−β)}) is not established. The theorem may still be true, and a difference-based estimate of E_P[log((1+VF,σ/VN,σ)/(1+VF,1−σ/VN,1−σ))] might repair the argument, but the present manuscript does not provide such a proof.
minor comments (4)
- [Abstract and Section 1] The phrase 'cannot be overcame' should be 'cannot be overcome'.
- [Theorem 5.1] The final sentence of Theorem 5.1, 'as e^{-nnβ/2(2−β)} = o(n^{-nβ/2(2−β) 2})', is garbled and should be rewritten with the intended exponent.
- [Subsection 5.3] The pooling analysis is evaluated at the minimal threshold N = n^{nβ/(1−β)}; the text should state explicitly that the bound is for that choice and may not hold for larger N satisfying only the inequality in (2).
- [Section 6] The notion of 'optimal adaptive rates' would benefit from a formal definition in Section 2 rather than being introduced informally in the discussion.
Circularity Check
No significant circularity: the new impossibility proof is an independent Fano/KL argument; the cited prior work is used only as an external benchmark, not as the load-bearing reduction.
full rationale
The central claim, Theorem 5.2, is a new lower bound on the error of any adaptive algorithm. Its proof (Appendix C) is self-contained: it builds a random mixture model, computes the likelihood ratio between the two hypotheses, and applies Fano's inequality via a direct calculation of D_KL(P^sigma || P^{1-sigma}). This KL calculation does not invoke any result from Hanneke & Kpotufe (2022); it is a fresh derivation specific to the new fair/noisy construction. The prior work is cited for the minimax rate formula, the pooling bound, and technical concentration lemmas, but those are used as external benchmarks to contextualize the theorem, not as steps in the lower-bound proof. The minimax rate formula is a published, parameter-free theorem with stated assumptions that do not include the present target result, so it qualifies as independent support under the review rules. No parameter in the construction is fitted to data and then renamed a prediction; epsilon, epsilon_0, and t* are chosen analytically, and the lower bound follows from the information-theoretic calculation rather than from the definition of any quantity. There is no self-definitional step, no ansatz smuggled via citation, and no uniqueness theorem imported from the authors' prior work. The skeptic's concern about a dropped Theta(1) term in Appendix C would be a correctness issue, not a circularity issue; correctness review is outside this pass. Overall, the derivation chain does not reduce to its inputs; the only self-citation present is transparent and not load-bearing, hence the score is 2 rather than 0.
Assumptions & free parameters
free parameters (5)
- beta (Bernstein exponent) =
in (0,1)
- epsilon =
(n sqrt(N))^{-1/(2-beta)}
- epsilon_0 =
(n N)^{-1/(2-beta)}
- t_star =
sqrt(N * n^{n beta/(2-beta)})
- N (task count) =
>= n^{n beta/(1-beta)}
assumptions (6)
- domain assumption All tasks share the same optimal classifier h* (Assumption (1), Section 2).
- domain assumption Bernstein class condition with parameters (C_beta, beta) holds for all sources and target (Assumption (3), Section 2).
- domain assumption Transfer exponent condition (Assumption (2), Section 2).
- standard math Fano's inequality and Pinsker's inequality (Lemma E.6, Appendix E).
- standard math Chernoff, Slud, Berry-Esseen, log-sum inequalities (Appendix E).
- domain assumption The learner has no target data and no knowledge of which dataset corresponds to which transfer exponent.
Cite this review
Pith. "Pith review of When More Data Doesn't Help: Limits of Adaptation in Multitask Learning." pith.science (2026). https://pith.science/paper/KEYYN2FJ
@misc{pith2026260120774,
author = {Pith},
title = {Pith review of: When More Data Doesn't Help: Limits of Adaptation in Multitask Learning},
year = {2026},
howpublished = {\url{https://pith.science/paper/KEYYN2FJ}},
note = {Machine review of arXiv:2601.20774}
}
read the original abstract
Multitask learning and related frameworks have achieved tremendous success in modern applications. In multitask learning problem, we are given a set of heterogeneous datasets collected from related source tasks and hope to enhance the performance above what we could hope to achieve by solving each of them individually. The recent work of arXiv:2006.15785 has showed that, without access to distributional information, no algorithm based on aggregating samples alone can guarantee optimal risk as long as the sample size per task is bounded. In this paper, we focus on understanding the statistical limits of multitask learning. We go beyond the no-free-lunch theorem in arXiv:2006.15785 by establishing a stronger impossibility result of adaptation that holds for arbitrarily large sample size per task. This improvement conveys an important message that the hardness of multitask learning cannot be overcame by having abundant data per task. We also discuss the notion of optimal adaptivity that may be of future interests.
Reference graph
Works this paper leans on
-
[1]
= 1/2 . Let Zσ∼P σ be a random variable and ψ:Z σ7→{0,1} be a function that returns an estimate of the indexσ. Then we have inf ψ P(ψ(Zσ)̸=σ) = 1 2 (1−∥P 0−P 1∥TV ), where∥P−Q∥ TV is called the total variation distance between distributions P and Q. Furthermore, byPinsker’s inequality, we have ∥P−Q∥ TV ≤ r 1 2 min{D KL(P||Q),D KL(Q||P)}, and thus inf ψ P(...
work page 2022
-
[2008]
Invariant risk minimization.arXiv preprint arXiv:1907.02893,
Arjovsky, M., Bottou, L., Gulrajani, I., and Lopez- Paz, D. Invariant risk minimization.arXiv preprint arXiv:1907.02893,
arXiv 1907
-
[2021]
Exploiting shared representations for personalized feder- ated learning
Collins, L., Hassani, H., Mokhtari, A., and Shakkottai, S. Exploiting shared representations for personalized feder- ated learning. InInternational Conference on Machine Learning, pp. 2089–2099,
-
[2022]
Hanneke, S. and Kpotufe, S. Adaptive sample aggregation in transfer learning.arXiv preprint arXiv:2408.16189,
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.