New algorithm removes dimension barrier in contaminated multi-task learning

Multi-task learning promises to improve performance by sharing information across related tasks, but real-world data often includes corrupted tasks—contaminated samples that can derail standard approaches. A new paper from researchers Ye Tian, Mengchu Li, and Marco Avella Medina reveals that many common strategies for handling such contamination have a critical weakness. In their contaminated multi-task empirical risk minimization framework, where an ε fraction of K tasks (each with n samples) may be arbitrarily corrupted, they show that adaptive regularization, global matrix regularization, decomposition-based methods, and score-based outlier detection all suffer a worst-case contamination error of order ε√(d/n). This is dimension-dependent and suboptimal compared to the theoretical lower bound of ε/√n—a fundamental barrier that grows with the feature dimensionality d.

The authors overcome this barrier with a computationally efficient filtering-based robust multi-task gradient descent method. Under standard assumptions (local strong convexity, smoothness, sub-Gaussian gradients), their algorithm achieves high-probability upper bounds matching the minimax rates up to logarithmic factors across a broad regime. Crucially, it removes the extra √d contamination dependence that plagues prior methods, while still enabling personalization to local tasks under strong heterogeneity. The paper includes simulations and a real-data analysis demonstrating strong robustness relative to a range of benchmark methods. For practitioners in federated learning, transfer learning, or any setting where some clients or tasks may supply corrupted data, this work offers both theoretical clarity and a practical algorithm that doesn't compromise on performance.