Seok-Jin Kim's new regression method works without eigenvalue assumptions
No more eigenvalue lower bounds: multi-task regression with outliers made robust
Seok-Jin Kim's new paper, accepted at ICML 2026, tackles multi-task linear regression when a fraction of tasks are contaminated. Classical approaches require each task's second moment to have a minimum eigenvalue bounded away from zero — a condition that fails in high-dimensional settings. Kim introduces an estimator based on matrix-weighted norm regularization and a "balancedness" condition that compares each task's second moment to the average inlier geometry.
This relaxed assumption allows the method to match the optimal MSE rates of prior work (Duan & Wang, 2023) under much weaker spectral conditions, achieving minimax optimality up to logarithmic factors. Notably, when tasks are unrelated or the balancedness constant is large, the estimator safely defaults to independent task learning — no worse than baselines. The framework thus achieves simultaneous adaptivity to task similarity, robustness to outliers, and safety outside favorable transfer regimes.
- Drops the requirement that each task's second moment has a minimum eigenvalue of Ω(1), enabling high-dimensional settings
- Introduces balancedness constant to compare task geometry to average inlier geometry, relaxing spectral assumptions
- Achieves minimax optimal MSE (up to log factors) and guarantees safety: performance no worse than independent task learning
Why It Matters
Makes multi-task learning practical for high-dimensional data with outliers, without fragile eigenvalue assumptions.