REVIEW 2 major objections 6 minor 300 references
Filtering multi-task gradients beats regularization: contamination error drops from ε√(d/n) to near the minimax rate ε/√n while still personalizing under heterogeneity.
Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →
T0 review · grok-4.5
2026-07-12 07:44 UTC pith:CNQIKXGM
load-bearing objection Solid theory paper: clean negative results on the ε√d/n barrier plus a filtering method that matches minimax rates for both global and local parameters under joint contamination and heterogeneity. the 2 major comments →
Contaminated Multi-task Learning with Heterogeneity: Fundamental Limits and Optimal Algorithms
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
In contaminated multi-task ERM with ε-fraction adversarial tasks and heterogeneous clean tasks, regularization families and score-based detectors are fundamentally limited by a dimension-dependent contamination barrier of order ε√(d/n). A filtering-based robust multi-task gradient descent that jointly aggregates gradients and estimates their covariance removes that barrier, matching the minimax rates ε/√n + √(ε)h + √(d/(nK)) for the global parameter and the corresponding personalized rates for clean local parameters, up to logarithmic factors, under local strong convexity, smoothness and sub-Gaussian gradients.
What carries the argument
Joint robust gradient estimation (JRGE) via iterative filtering of task-level gradients, fed by a simple robust covariance estimator built from single-task empirical covariances, then plugged into multi-task gradient descent with soft-thresholded local updates.
Load-bearing premise
Each task risk must be strongly convex and smooth inside a fixed-radius ball around its own minimizer, and sample gradients must obey a high-probability Lipschitz condition so that the filtering steps stay controlled throughout the trajectory.
What would settle it
In the Gaussian mean model with large d, fix ε and n so that ε√(d/n) is several times larger than ε/√n; if the filtering estimator's worst-case error still tracks ε√(d/n) rather than the claimed near-minimax rate, the barrier-removal claim fails.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies multi-task ERM under adversarial contamination of an ε-fraction of K tasks (each of size n) together with heterogeneity among clean tasks. It first proves that several standard paradigms—adaptive/robust center regularization, global matrix penalties, decomposition (dirty) models, and score-based outlier-task detection—incur a worst-case contamination error of order ε√(d/n) in the Gaussian mean model, which is suboptimal relative to the lower bound ε/√n (Theorems 1–4). It then establishes minimax lower bounds for both the global average-risk minimizer θ* and the clean local minimizers θ^(k)* in a general heterogeneous ERM setting, capturing the interaction √(ε)h + h^(k) (Theorem 5 / 12). A filtering-based robust multi-task gradient descent method (Algorithms 1–3), using joint robust gradient estimation and a simple single-task covariance filter, is shown to attain high-probability upper bounds matching these lower bounds up to logs in a broad regime (roughly n ≳ d or ε²(1 ∨ √(n/d)) ≲ n/K), under local strong convexity, smoothness, and sub-Gaussian gradients (Corollary 1). Simulations and a HAR real-data study support robustness and personalization relative to many benchmarks.
Significance. If the matching rates hold as stated, the work cleanly separates a dimension-dependent contamination barrier that affects a wide family of regularization and score-based methods from a filtering approach that removes the extra √d factor while retaining personalization under heterogeneity. The lower bounds improve on prior work by making the √(ε)h interaction explicit and by treating both global and local parameters. The algorithmic construction (JRGE + single-task covariance filtering + soft-thresholded local gradients) is computationally practical and is supported by extensive comparisons. The appendix proofs use standard tools (stability certificates, covering arguments, Taylor expansions for regularizers) and the optimality regime is stated explicitly (Remark 5, Figure 1). These are genuine contributions to robust multi-task / federated learning under simultaneous contamination and heterogeneity.
major comments (2)
- Algorithms 2 and 3 take the contamination fraction ε as a known input (and λ_Σ, λ are tuned with knowledge of ε-scale quantities). The theoretical rates and the filtering certificate (Lemma 8, Proposition 4) depend on this. The manuscript should either (i) state clearly that ε is assumed known, as is common in strong-contamination analyses, or (ii) add a short discussion/robustness check on misspecification of ε (e.g., over-estimating ε by a constant factor). Without this, the practical claim that the method is ready for use when ε is unknown is slightly stronger than the theory supports.
- Corollary 1 / Remark 5: the upper bound still carries the residual contamination term (ε/√n)[(d/n)^{1/4} + (d/n)^{1/2}]. The abstract and introduction emphasize that the method “removes the extra √d contamination dependence” of regularization methods. That is correct relative to ε√(d/n), but when n is only moderately larger than d the residual is not fully dimension-free. A one-sentence clarification in the abstract or Remark 5 that full minimax optimality (matching ε/√n) holds in the stated regime, and that outside it a milder dimension factor remains, would prevent over-reading of the claim.
minor comments (6)
- Assumption 6 (high-probability Lipschitz of sample gradients with L' ≲ (nKd)^{C}) is used for uniform control of filtering iterates. A brief remark that this is a high-probability strengthening of population smoothness (Assumption 2), and that it holds for the mean and GLM examples under the stated sub-Gaussian conditions (Lemmas 1–2), would help readers who skip the appendix.
- Section 2.1.1 / Assumption 1: the list of regularizer conditions is long. A short pointer that Lasso, Ridge, Bridge, SCAD, MC+, and hard-thresholding all satisfy it (with verification deferred to Appendix A.6) is already present; ensuring the main-text statement of Theorem 1 explicitly says “for any regularizer satisfying Assumption 1” would make the negative result easier to cite.
- Tables 1–3 and Appendix C: bold/italic marking of best and second/third is helpful. Adding a one-line note that Single-task is omitted from global-error columns because it does not produce a pooled estimator would avoid confusion.
- Notation: the same symbol L is used for the smoothness constant (Assumption 2) and for the proximal radius of the regularizer (Assumption 1). Different letters would reduce cognitive load when both sections are read together.
- Figure 1 caption: “shaded region corresponds to the regime where the upper bound in Corollary 1 is minimax optimal up to logarithmic factors” is clear; a brief axis label or legend for the two boundaries (n ∼ d and n ∼ Kε²) would make the figure self-contained.
- Related work: the discussion of untrusted-batch / batch-contamination models (QV18, CLM20, ABLY26) is useful. A sentence contrasting task-level contamination with within-batch contamination would further situate the contribution.
Circularity Check
No significant circularity: rates derived from stated assumptions and independent minimax constructions; self-citations are background only.
full rationale
The paper's central claims (negative results Theorems 1-4 establishing the ε√(d/n) barrier for regularization/score-based methods; minimax lower bounds Theorem 5/12 via packing/Le Cam; matching upper bounds Corollary 1 via filtering Algorithms 2-3 under Assumptions 2/4/6) are derived from first-order optimality, concentration, stability certificates, and gradient-descent contraction, not by redefining the target quantities in terms of themselves or by fitting parameters that force the claimed rates. Lower bounds are constructed independently of the upper-bound algorithm. Self-citations (e.g., to DW22, TWXF22) supply motivation and comparison baselines but are not load-bearing for the new rates or the filtering analysis; the proofs in the appendix are self-contained under the listed assumptions. No fitted-input-as-prediction, uniqueness-imported-from-authors, or ansatz-smuggled-via-citation patterns appear. Residual log factors and the local-ball restriction are acknowledged rather than hidden. Score 1 only for the presence of ordinary self-citations that do not close any definitional loop.
Axiom & Free-Parameter Ledger
free parameters (4)
- contamination fraction ε (assumed known for Algorithm 2/3)
- filtering threshold λ_Σ and soft-threshold λ
- step sizes η, η^(k) and iteration count T
- heterogeneity radii h, h^(k) and local radius R0
axioms (6)
- domain assumption Local L-smoothness and 1/L-strong convexity of each task risk on a ball of radius R0 (Assumption 2).
- domain assumption Task gradient heterogeneity bounds (9)–(10) with parameters h and h^(k) (Assumption 3).
- domain assumption Sub-Gaussian sample gradients with uniform ψ2 bound (Assumption 4).
- domain assumption High-probability Lipschitz continuity of sample gradients in θ (Assumption 6).
- domain assumption Strong contamination model: adversary may replace all samples of an ε-fraction of tasks arbitrarily, possibly depending on clean data.
- standard math Standard concentration and covering arguments for sub-Gaussian vectors and empirical processes.
invented entities (2)
-
Joint robust gradient estimation (JRGE) with multi-task single-task covariance filtering (Algorithms 2–3)
no independent evidence
-
Soft-thresholded personalized local gradient g^(k) around the robust global gradient
no independent evidence
read the original abstract
Integrating information across related tasks can improve estimation and prediction in transfer, multi-task, and federated learning, but contamination and heterogeneity make robust borrowing challenging. We study a contaminated multi-task empirical risk minimization (ERM) framework in which an $\epsilon$ fraction of $K$ tasks, each with sample size $n$, may be arbitrarily contaminated while the remaining tasks are heterogeneous. Our goal is to estimate both the global minimizer of the average risk and the clean task-specific minimizers, thereby combining robustness and personalization. In the Gaussian mean model, we show that several common paradigms, including adaptive and robust regularization around a shared center, global matrix regularization, decomposition-based regularization, and score-based outlier-task detection, all suffer from a worst-case contamination error of order $\epsilon\sqrt{d/n}$, which is suboptimal compared to the lower bound $\epsilon/\sqrt{n}$. This identifies a dimension-dependent barrier for these approaches. We then establish minimax lower bounds for a general heterogeneous ERM setting and propose a computationally efficient filtering-based robust multi-task gradient descent method. Under local strong convexity, smoothness, and sub-Gaussian gradient assumptions, the proposed method attains high-probability upper bounds matching the minimax rates up to logarithmic factors over a broad regime. In particular, it removes the extra $\sqrt{d}$ contamination dependence of many regularization-based methods and score-based outlier detection, while achieving personalization to local tasks under strong heterogeneity. Simulations and a real-data analysis demonstrate strong robustness and personalization relative to a broad range of benchmark methods.
Figures
Reference graph
Works this paper leans on
-
[1]
1996 , publisher=
Weak Convergence and Empirical Processes: With Applications to Statistics , author=. 1996 , publisher=
1996
-
[2]
IEEE Transactions on Signal Processing , volume=
Robust wavelet denoising , author=. IEEE Transactions on Signal Processing , volume=. 2001 , publisher=
2001
-
[3]
Information and Inference: A Journal of the IMA , volume=
Estimating location parameters in sample-heterogeneous distributions , author=. Information and Inference: A Journal of the IMA , volume=. 2022 , publisher=
2022
-
[4]
arXiv preprint arXiv:2508.19640 , year=
Optimal Cox regression under federated differential privacy: coefficients and cumulative hazards , author=. arXiv preprint arXiv:2508.19640 , year=
-
[5]
The Annals of Statistics , volume=
On robustness and local differential privacy , author=. The Annals of Statistics , volume=. 2023 , publisher=
2023
-
[6]
International Conference on Algorithmic Learning Theory , pages=
Robust estimation of discrete distributions under local differential privacy , author=. International Conference on Algorithmic Learning Theory , pages=. 2023 , organization=
2023
-
[7]
Advances in Neural Information Processing Systems , volume=
Robust and differentially private mean estimation , author=. Advances in Neural Information Processing Systems , volume=
-
[8]
9th Innovations in Theoretical Computer Science Conference (ITCS 2018) , series =
Learning Discrete Distributions from Untrusted Batches , author =. 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) , series =. 2018 , editor =. doi:10.4230/LIPIcs.ITCS.2018.47 , url =
-
[9]
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages =
Efficiently Learning Structured Distributions from Untrusted Batches , author =. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages =. 2020 , publisher =
2020
-
[10]
Proceedings of the 37th International Conference on Machine Learning , series =
Optimal Robust Learning of Discrete Distributions from Batches , author =. Proceedings of the 37th International Conference on Machine Learning , series =. 2020 , publisher =
2020
-
[11]
Advances in Neural Information Processing Systems , volume =
A General Method for Robust Learning from Batches , author =. Advances in Neural Information Processing Systems , volume =
-
[12]
Proceedings of the 38th International Conference on Machine Learning , series =
Robust Density Estimation from Batches: The Best Things in Life are (Nearly) Free , author =. Proceedings of the 38th International Conference on Machine Learning , series =. 2021 , publisher =
2021
-
[13]
Advances in Neural Information Processing Systems , volume =
Linear Regression using Heterogeneous Data Batches , author =. Advances in Neural Information Processing Systems , volume =. 2024 , url =
2024
-
[14]
The Thirty Seventh Annual Conference on Learning Theory , series =
Robust Distribution Learning with Local and Global Adversarial Corruptions , author =. The Thirty Seventh Annual Conference on Learning Theory , series =. 2024 , publisher =
2024
-
[15]
Journal of the Royal Statistical Society Series B: Statistical Methodology , pages=
Minimax and adaptive transfer learning for nonparametric classification under distributed differential privacy constraints , author=. Journal of the Royal Statistical Society Series B: Statistical Methodology , pages=. 2025 , publisher=
2025
-
[16]
Annual Review of Statistics and Its Application , volume=
A theoretical review of modern robust statistics , author=. Annual Review of Statistics and Its Application , volume=. 2025 , publisher=
2025
-
[17]
A festschrift for Erich L
The notion of breakdown point , author=. A festschrift for Erich L. Lehmann , volume=. 1983 , publisher=
1983
-
[18]
The Annals of Statistics , volume=
Robust Machine Learning By Median-of-Means , author=. The Annals of Statistics , volume=. 2020 , publisher=
2020
-
[19]
The screening and ranking algorithm to detect
Niu, Yue S and Zhang, Heping , year = 2012, journal =. The screening and ranking algorithm to detect
2012
-
[20]
A review on minimax rates in change point detection and localisation , author =
-
[21]
Biometrika , publisher =
Continuous inspection schemes , author =. Biometrika , publisher =
-
[22]
arXiv preprint arXiv:1311.2669 , year=
Distance-based and continuum Fano inequalities with applications to statistical estimation , author=. arXiv preprint arXiv:1311.2669 , year=
-
[23]
, author=
An optimal randomized algorithm for maximum Tukey depth. , author=. SODA , volume=
-
[24]
30th USENIX Security Symposium (USENIX Security 21) , pages=
Extracting training data from large language models , author=. 30th USENIX Security Symposium (USENIX Security 21) , pages=
-
[25]
Advances in Neural Information Processing Systems 36 , year =
Youssef Allouah and Rachid Guerraoui and Nirupam Gupta and Rafael Pinot and Geovani Rizk , title =. Advances in Neural Information Processing Systems 36 , year =
-
[26]
2019 , publisher=
Robust statistics: theory and methods (with R) , author=. 2019 , publisher=
2019
-
[27]
arXiv preprint arXiv:2605.17126 , year=
Multi-task Linear Regression without Eigenvalue Lower Bounds: Adaptivity, Robustness and Safety , author=. arXiv preprint arXiv:2605.17126 , year=
-
[28]
arXiv preprint arXiv:2508.12048 , year=
Robust Data Fusion via Subsampling , author=. arXiv preprint arXiv:2508.12048 , year=
-
[29]
arXiv preprint arXiv:2602.20698 , year =
Maryam Aliakbarpour and Vladimir Braverman and Yuhan Liu and Junze Yin , title =. arXiv preprint arXiv:2602.20698 , year =. doi:10.48550/arXiv.2602.20698 , eprint =
-
[30]
Statistics and its Interface , volume=
Penalized unsupervised learning with outliers , author=. Statistics and its Interface , volume=
-
[31]
Journal of the Royal Statistical Society Series B: Statistical Methodology , pages=
Byzantine-tolerant distributed learning of finite mixture models , author=. Journal of the Royal Statistical Society Series B: Statistical Methodology , pages=. 2026 , publisher=
2026
-
[32]
1980 , publisher=
Identification of outliers , author=. 1980 , publisher=
1980
-
[33]
Advances in Neural Information Processing Systems 37 , pages =
Youssef Allouah and Abdellah El Mrini and Rachid Guerraoui and Nirupam Gupta and Rafael Pinot , title =. Advances in Neural Information Processing Systems 37 , pages =. 2024 , doi =
2024
-
[34]
The Thirty Eighth Annual Conference on Learning Theory , pages=
Optimal Robust Estimation under Local and Global Corruptions: Stronger Adversary and Smaller Error , author=. The Thirty Eighth Annual Conference on Learning Theory , pages=. 2025 , organization=
2025
-
[35]
Proceedings of the 2016 ACM SIGSAC conference on computer and communications security , pages=
Deep learning with differential privacy , author=. Proceedings of the 2016 ACM SIGSAC conference on computer and communications security , pages=
2016
-
[36]
2017 , journal =
Minimax estimation of linear and quadratic functionals on sparsity classes , author=. 2017 , journal =
2017
-
[37]
2017 IEEE Symposium on Security and Privacy (SP) , pages=
Is interaction necessary for distributed private learning? , author=. 2017 IEEE Symposium on Security and Privacy (SP) , pages=. 2017 , organization=
2017
-
[38]
arXiv preprint arXiv:2010.06562 , year=
Unified lower bounds for interactive high-dimensional estimation under information constraints , author=. arXiv preprint arXiv:2010.06562 , year=
Pith/arXiv arXiv 2010
-
[39]
Optimal change point detection and localization in sparse dynamic networks , author =
-
[40]
Statistical analysis and forecasting of economic structural change , publisher =
Nonparametric tests for shift and change in regression at an unknown time point , author =. Statistical analysis and forecasting of economic structural change , publisher =
-
[41]
arXiv preprint arXiv:1711.03908 , year=
Finite sample differentially private confidence intervals , author=. arXiv preprint arXiv:1711.03908 , year=
-
[42]
Lecture Notes for ECE598YW (UIUC) , volume=
Lecture notes on information-theoretic methods for high-dimensional statistics , author=. Lecture Notes for ECE598YW (UIUC) , volume=
-
[43]
Adversarial examples in the physical world , author =. 1607.02533 , archiveprefix =
-
[44]
Physical adversarial examples for object detectors , author =
-
[45]
Adversarial examples for evaluating reading comprehension systems , author =
-
[46]
On physical adversarial patches for object detection , author =
-
[47]
Robust statistics: the approach based on influence functions , author =
-
[48]
The Annals of Statistics , publisher =
Optimal change point detection and localization in sparse dynamic networks , author =. The Annals of Statistics , publisher =
-
[49]
Multiscale
Futschik, Andreas and Hotz, Thomas and Munk, Axel and Sieling, Hannes , year = 2014, journal =. Multiscale
2014
-
[50]
The Annals of Statistics , publisher =
Break detection in the covariance structure of multivariate time series models , author =. The Annals of Statistics , publisher =
-
[51]
A linear time method for the detection of point and collective anomalies , author =
-
[52]
Economic Structural Change , publisher =
Recursive M-tests for the change-point problem , author =. Economic Structural Change , publisher =
-
[53]
Journal of the Royal Statistical Society: Series B (Statistical Methodology) , publisher =
High dimensional change point estimation via sparse projection , author =. Journal of the Royal Statistical Society: Series B (Statistical Methodology) , publisher =
-
[54]
Fast approximation of
Do, Minh N , year = 2003, journal =. Fast approximation of
2003
-
[55]
Elements of information theory , author =
-
[56]
The total variation distance between high-dimensional Gaussians , author =
-
[57]
Discrete Applied Mathematics , publisher =
A result of Vapnik with applications , author =. Discrete Applied Mathematics , publisher =
-
[58]
Statistics & Probability Letters , publisher =
Tight lower bound on the probability of a binomial exceeding its expectation , author =. Statistics & Probability Letters , publisher =
-
[59]
International Conference on Artificial Intelligence and Statistics , pages =
A robust univariate mean estimator is all you need , author =. International Conference on Artificial Intelligence and Statistics , pages =
-
[60]
Summer School on Machine Learning , pages =
Introduction to statistical learning theory , author =. Summer School on Machine Learning , pages =
-
[61]
The Annals of Statistics , publisher =
Wild binary segmentation for multiple change-point detection , author =. The Annals of Statistics , publisher =
-
[62]
Statistica Sinica , publisher =
Multiple change-point detection via a screening and ranking algorithm , author =. Statistica Sinica , publisher =
-
[63]
A robust bootstrap change point test for high-dimensional location parameter , author =
-
[64]
Journal of the American Statistical Association , publisher =
Optimal detection of changepoints with a linear computational cost , author =. Journal of the American Statistical Association , publisher =
-
[65]
Assouad,
Yu, Bin , year = 1997, booktitle =. Assouad,
1997
-
[66]
Doubly Robust Bayesian Inference for Non-Stationary Streaming Data with -Divergences , author =
-
[67]
High-dimensional probability: An introduction with applications in data science , author =
-
[68]
A unified approach to robust mean estimation , author =
-
[69]
An evaluation of change point detection algorithms , author =
-
[70]
Breakthroughs in statistics , publisher =
Robust estimation of a location parameter , author =. Breakthroughs in statistics , publisher =
-
[71]
Robust estimates of location , author =
-
[72]
Journal of the Royal Statistical Society: Series B (Statistical Methodology) , publisher =
Robust estimation in the normal mixture model based on robust clustering , author =. Journal of the Royal Statistical Society: Series B (Statistical Methodology) , publisher =
-
[73]
Lecture notes on Robustness in Machine Learning , author =
-
[74]
The Annals of Statistics , volume=
All-in-one robust estimator of the Gaussian mean , author=. The Annals of Statistics , volume=. 2022 , publisher=
2022
-
[75]
Optimal nonparametric multivariate change point detection and localization , author =
-
[76]
International Conference on Artificial Intelligence and Statistics , pages=
High dimensional robust sparse regression , author=. International Conference on Artificial Intelligence and Statistics , pages=. 2020 , organization=
2020
-
[77]
Department of Statistics, Princeton University , year=
T6: Order Statistics, in mimeographed notes for Statistics 411 , author=. Department of Statistics, Princeton University , year=
-
[78]
Conference on Learning Theory , pages=
Computationally efficient robust sparse estimation in high dimensions , author=. Conference on Learning Theory , pages=. 2017 , organization=
2017
-
[79]
Proceedings of the International Congress of Mathematicians, Vancouver, 1975 , volume=
Mathematics and the picturing of data , author=. Proceedings of the International Congress of Mathematicians, Vancouver, 1975 , volume=
1975
-
[80]
A general decision theory for
Chen, Mengjie and Gao, Chao and Ren, Zhao , year = 2016, journal =. A general decision theory for
2016
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.