Multi-task Linear Regression without Eigenvalue Lower Bounds: Adaptivity, Robustness, and Safety

We study the multi-task linear regression problem in the presence of contaminated tasks. We address the setting where the unknown parameters of a majority of tasks are close in the $\ell_2$-norm, while a fraction of tasks are arbitrary outliers. Existing theoretical frameworks for this problem rely heavily on the assumption that the empirical second moment of each task has a minimum eigenvalue bounded away from zero (order $\Omega(1)$). Crucially, this assumption fails in many high-dimensional scenarios, rendering prior guarantees vacuous. To overcome this limitation, we propose an estimator based on matrix-weighted norm regularization. We also introduce a relative balancedness condition, quantified by a balancedness constant, that compares each task's second moment with the average inlier geometry and relaxes the need for taskwise second-moment lower bounds. In favorable regimes with moderate balancedness, our prediction MSE bounds match the rate of Duan and Wang (2023) under substantially weaker spectral assumptions; the resulting task-overall MSE is minimax optimal up to logarithmic factors. Furthermore, we demonstrate that our estimator enjoys a safety guarantee: when the relevant balancedness constant is large or infinite, or when tasks are unrelated, the method performs no worse than independent task learning.

Many real-world prediction problems come in related groups: a hospital may predict outcomes across many clinics, or a platform may forecast demand across many products. Learning these problems together can improve accuracy, especially when each one has limited data. But sharing information is not always safe. Some problems in the group may be unrelated or corrupted, and real datasets often contain uneven measurements, where some patterns are much easier to observe than others. Existing theory for robust multi-task learning often rules out this unevenness, making its guarantees less useful in high-dimensional applications. We propose a method for learning grouped prediction problems together while protecting against harmful sharing. The method can automatically benefit from related problems, tolerate a small fraction of arbitrary bad ones, and handle uneven data geometry without requiring strong uniform measurement assumptions. It also does not need to know in advance how similar the problems are. When sharing is helpful, it matches the best known guarantees under weaker assumptions; when sharing is harmful, it remains as safe as learning each problem separately.