{"id":"9a491b7c-57d0-448b-b699-dbfb4b21c296","arxiv_id":"2601.20774","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A new impossibility theorem shows that adaptive multitask learning fails even with arbitrarily large per-task sample sizes, provided the number of tasks is at least n^{nβ/(1−β)}.","lead":"This paper proves a stronger version of a no-free-lunch theorem for multitask learning: even when every source task has an arbitrarily large dataset, no algorithm can automatically find the useful sources and match the best possible performance, so long as the number of sources is super-exponentially large in the per-source sample size. The result settles an open question about whether more data per task can overcome the fundamental difficulty of adaptation.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Appendix C's KL proof drops a Θ(1) term before raising to the nth power: the P-conditional contribution is not O(1), so Theorem 5.2's lower bound is unproven as written.","rationale":"The reader correctly identified the KL bound in Appendix C as the load-bearing step of Theorem 5.2. The stress-test finds a concrete algebraic error in that bound: the P-conditional expectation E_P[VFσ/VNσ] is not O((ε^{2β}/ε0^β)^n); the O(1) term from p_{1,x0}^2/q_{1,x0} cannot be dropped before the nth power. Since that term is what makes the intended cancellation with (t*)^2/N work, the proof of D_KL = O(1) collapses. The theorem may be salvageable with a different argument, but as written the lower bound is unproven. This is more than a typo or a loose constant: the displayed inequality in Appendix C is false for the stated parameter regime. The verdict should move from CONDITIONAL to UNVERDICTED because the central claim is not established by the submitted proof, though the result itself has not been disproved.","tokens_in":33754,"tokens_out":29567,"duration_ms":225350,"concrete_test":"For β=1/2, n=10, Cβ=2, N=10^{10} (satisfying (2)), compute A = p_{σ,x1}^2/q_{σ,x1}+p_{1−σ,x1}^2/q_{1−σ,x1}+p_{1,x0}^2/q_{1,x0} from the definitions in §5.1 and evaluate t*·(αF/αN)·A^n. If this exceeds O(1) (it is ≈10^6), the Appendix C bound fails. Analytically, show A−1 = Θ(n^{−β/(2−β)}) as N→∞, so A^n = exp(Θ(n^{1−β/(2−β)})), contradicting the O((1/n)^{nβ/(2−β)}) claimed in the proof.","verdict_should_be":"UNVERDICTED","load_bearing_attack":"Appendix C, Eqs. (18)-(20), bounds the P-conditional part of D_KL(P^σ||P^{1−σ}) by t*·E_P[VFσ/VNσ] and computes E_P[VFσ/VNσ] = (αF/αN)·A^n with A = p_{σ,x1}^2/q_{σ,x1} + p_{1−σ,x1}^2/q_{1−σ,x1} + p_{1,x0}^2/q_{1,x0}. The paper then drops the last term, treating A = O(ε^{2β}/ε0^β), and concludes t*·E_P[VFσ/VNσ] = O((t*)^2/N·(1/n)^{nβ/(2−β)}) = O(1). But p_{1,x0}^2/q_{1,x0} = 1 − Θ(ε^β) ≈ 1, while ε^{2β}/ε0^β = n^{−β/(2−β)}; hence A = 1 + Θ(n^{−β/(2−β)}) (the ε^β correction is negligible under (2)). Therefore A^n = exp(Θ(n^{1−β/(2−β)})), not n^{−nβ/(2−β)}. Since t*·αF/αN = (t*)^2/N = n^{nβ/(2−β)}, the term is Ω(n^{nβ/(2−β)} exp(c n^{(2−2β)/(2−β)})), which is not O(1). The displayed inequality leading to Eq. (20) is thus false; the claimed O(1) KL bound, and with it the Fano-based proof of Theorem 5.2, is unsupported.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":34172,"tokens_out":27832,"duration_ms":211936,"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":[{"comment":"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.","section":"Appendix C (proof of Theorem 5.2, paragraph 'In the following, we analyze each summand separately')"},{"comment":"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.","section":"Theorem 5.2, proof item 1⃝"}],"minor_comments":[{"comment":"The phrase 'cannot be overcame' should be 'cannot be overcome'.","section":"Abstract and Section 1"},{"comment":"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.","section":"Theorem 5.1"},{"comment":"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":"Subsection 5.3"},{"comment":"The notion of 'optimal adaptive rates' would benefit from a formal definition in Section 2 rather than being introduced informally in the discussion.","section":"Section 6"}],"recommendation":"major_revision","confidential_remarks":"The paper is from the same research group as the main prior work it builds on, but the dependence is transparent and the construction is genuinely new. My main concern is the KL-divergence bound in Appendix C, which I believe may be repairable with a sharper argument that exploits cancellations between VF,σ and VF,1−σ; however, as submitted the central impossibility theorem is not proven. I recommend major revision rather than rejection because the high-level approach appears promising and the flaw is localized to one load-bearing calculation."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main theorem is not proven as written. The KL-divergence bound in Appendix C drops the dominant term in the sum before raising it to the nth power, and that term ruins the O(1) conclusion. This is a load-bearing flaw, not a typo.\n\nWhat is genuinely new: the paper asks the right question—whether the no-free-lunch result from Hanneke & Kpotufe (2022) persists when each task has many samples. The construction with two noisy source types and the attempt to bound a mixture KL divergence is real technical work. The agnostic-case results (Theorems 4.2–4.4) appear novel and the proofs there are more standard; the pooling-suboptimality counterexample is a nice addition.\n\nThe specific break: after computing E_P[V_Fσ/V_Nσ] = (α_F/α_N)·a^n with a = p_{σ,x1}²/q_{σ,x1} + p_{1-σ,x1}²/q_{1-σ,x1} + p_{1,x0}²/q_{1,x0}, the authors call p_{1,x0}²/q_{1,x0} = O(1) and then effectively drop it, leaving only the O(ε^{2β}/ε0^β) terms. But p_{1,x0}²/q_{1,x0} = (1 − Cβ ε^β)²/(1 − Cβ ε0^β) = 1 − Θ(ε^β), so a = 1 + Θ(n^{−β/(2−β)}), not n^{−β/(2−β)}. Then a^n = exp(c n^{(2−2β)/(2−β)}), and together with the (t*)²/N prefactor this is enormous, not O(1). The Fano argument collapses. I checked the surrounding text; the displayed inequality is simply false.\n\nAlso, the abstract overstates the scope: the construction requires N ≥ n^{nβ/(1−β)}, which is super-exponential in n, and that condition should be in the abstract. The minimax rate for the construction is asserted rather than proved, and there is a typo in the pooling-bound algebra—minor compared to the KL issue.\n\nThis paper is for the theory community working on multitask learning and adaptivity. If the main proof can be repaired, the result is significant. As it stands, the agnostic section may be salvageable, but the central claim is unsupported.\n\nI would send this out for peer review rather than desk reject: the question is important and the authors are working on it honestly. But the current version should not be accepted; a referee should push for a correct KL bound or a narrowed claim.","headline":"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.","tokens_in":34682,"tokens_out":5781,"would_cite":false,"duration_ms":47403,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T05","62C20","62B10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Even arbitrarily large per-task samples cannot make multitask learning adaptive.","keywords":["multitask learning","adaptivity","no-free-lunch theorem","minimax rates","Fano's inequality","Kullback-Leibler divergence","transfer exponent","Bernstein class condition"],"falsifier":"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.","tokens_in":33458,"feed_emoji":"🧠","tokens_out":9870,"duration_ms":73765,"temperature":0.7,"pith_summary":"This paper establishes an impossibility result for adaptivity in multitask learning: an algorithm that is given only the pooled datasets from many source tasks, with no information distinguishing 'good' sources from 'noisy' ones, cannot match the optimal error rate no matter how large the per-task sample size is. The construction uses $N$ sources, of which $t^*$ are drawn from the target distribution and the rest are noisier, with per-task sample size $n$; in this family every adaptive algorithm suffers excess risk $\\Omega((n\\sqrt{N})^{-1/(2-\\beta)})$ while an oracle knowing the sources achieves $o((n\\sqrt{N})^{-1/(2-\\beta)})$. This strengthens a prior no-free-lunch theorem that held only for bounded $n$, and it shows the obstacle is identifying which datasets to trust, not the amount of data per task. The proof combines a random mixture model, Fano's inequality, and a tight bound on the KL divergence between mixtures.","feed_headline":"Even unlimited samples per task can't make multitask learning adaptive","feed_subtitle":"No learner can pick the right sources from pooled data without extra information, however many samples each task has.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the prior no-free-lunch theorem for bounded per-task sample size that this paper strengthens, and the minimax rate and pooling bounds (its Theorem 9 and Corollary 2) used throughout.","marker":"Hanneke & Kpotufe (2022)"},{"why":"Defines the Bernstein class condition that controls the label-noise regime $\\beta$ and that the constructed fair and noisy sources must satisfy.","marker":"Bartlett et al. (2004)"},{"why":"Introduces the noise condition of which the Bernstein class condition is a relaxation; the interpolation between $n^{-1}$ and $n^{-1/2}$ rates is parameterized by $\\beta$.","marker":"Tsybakov (2004)"},{"why":"Motivates the technical difficulty by noting that bounding KL divergence between mixture distributions is generally hard, the obstacle overcome in Appendix C.","marker":"Hershey & Olsen (2007)"}],"fun_headline_variants":["More data per task can't fix multitask adaptation failure","Adaptive multitask learning fails even with unbounded samples","Unlimited per-task data won't make multitask learning adaptive","Even infinite samples per task can't overcome multitask adaptation limits","Abundant data per task doesn't rescue multitask adaptation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["More data per task can't fix multitask adaptation failure","Adaptive multitask learning fails even with unbounded samples","Unlimited per-task data won't make multitask learning adaptive","Even infinite samples per task can't overcome multitask adaptation limits","Abundant data per task doesn't rescue multitask adaptation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000182,"raw_usage":{"total_tokens":1295,"prompt_tokens":914,"completion_tokens":381,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":530,"completion_tokens_details":{"reasoning_tokens":298}},"tokens_in":530,"tokens_out":381,"duration_ms":3404,"temperature":1.0,"reasoning_tokens":298,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T15:40:22.902342+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":2}