Contaminated Multi-task Learning with Heterogeneity: Fundamental Limits and Optimal Algorithms
arXiv:2607.02681
2026
Optimization
1 ideas extracted · analyzed Aug 30, 2026
What the math gives to ML
This paper identifies a concrete failure mode in personalized and federated optimization: regularizing task parameters toward a shared center or detecting outlier tasks by scalar scores can incur contamination error proportional to \(\epsilon\sqrt{d/n}\), whereas the minimax target is only \(\epsilon/\sqrt n\). The transferable asset is its task-level filtering view: robustly aggregate vector gradients before the global update, rather than regularizing parameters or ranking tasks with a single loss score. This can be implemented as a spectral robust mean estimator over per-task gradients, with local task updates retained for personalization. The main falsifiable benefit is improved Byzantine/data-contamination robustness at dimension-independent error scaling.
Ideas from this paper
✗ Mechanism failed
2026
Replace the ordinary average of task or client gradients with an iterative spectral filter that removes tasks whose gradient vectors explain an anomalously large covariance direction. The global model uses the filtered gradient, while each task still maintains its own personalized parameters and local optimizer state. Unlike parameter-center regularization, the robustification acts directly on the vector messages and is designed to avoid an additional \(\sqrt d\) contamination penalty.
Useful8/10
Difficulty5/10
Novelty5/10