# Contaminated Multi-task Learning with Heterogeneity: Fundamental Limits and Optimal Algorithms

arXiv: https://arxiv.org/abs/2607.02681 · HTML: https://mlsanity.com/paper/2607.02681/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 104 references that are in the map.
- First posted on arXiv 2 Jul 2026.

## Builds on (most cited first, 10 of 10)

- [Robust regression with covariate filtering: Heavy tails and adversarial contamination](https://mlsanity.com/paper/2009.12976/) (2020)
- [Adaptive and Robust Multi-Task Learning](https://mlsanity.com/paper/2202.05250/) (2022)
- [Learning from Similar Linear Representations: Adaptivity, Minimaxity, and Robustness](https://mlsanity.com/paper/2303.17765/) (2023)
- [Robust Sparse Mean Estimation via Sum of Squares](https://mlsanity.com/paper/2206.03441/) (2022)
- [Federated Transfer Learning with Differential Privacy](https://mlsanity.com/paper/2403.11343/) (2024)
- [Optimal Cox regression under federated differential privacy: coefficients and cumulative hazards](https://mlsanity.com/paper/2508.19640/) (2025)
- [Robust Unsupervised Multi-task and Transfer Learning on Gaussian Mixture Models](https://mlsanity.com/paper/2209.15224/) (2022)
- [Robust Data Fusion via Subsampling](https://mlsanity.com/paper/2508.12048/) (2025)
- [High-Dimensional Robust Mean Estimation with Untrusted Batches](https://mlsanity.com/paper/2602.20698/) (2026)
- [Multi-task Linear Regression without Eigenvalue Lower Bounds: Adaptivity, Robustness, and Safety](https://mlsanity.com/paper/2605.17126/) (2026)

## Abstract (arXiv)

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 ε 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 ε√d/n, which is suboptimal compared to the lower bound ε/√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 √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.