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

• URL: http://arxiv.org/abs/2605.17126v1
• Date: Sat, 16 May 2026 19:06:54 GMT
• Title: Multi-task Linear Regression without Eigenvalue Lower Bounds: Adaptivity, Robustness and Safety
• Abstract summary: We study the multi-task linear regression problem in the presence of contaminated tasks.<n>We introduce a relative balancedness condition, quantified by a balancedness constant, that compares each task's second moment with the average inlier geometry.<n>Our method achieves simultaneous adaptivity to task similarity, robustness to outliers, and safety outside favorable transfer regimes.
• Score: 2.538209532048867
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 $Ω(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. Consequently, our methodology achieves simultaneous adaptivity to task similarity, robustness to outliers, and safety outside favorable transfer regimes.

Related papers

• Contaminated Multi-task Learning with Heterogeneity: Fundamental Limits and Optimal Algorithms [5.54992643082602]
  We study a contaminated multi-task empirical risk minimization framework.<n>Our goal is to estimate both the global minimizer of the average risk and the clean task-specific minimizers.<n>We propose a computationally efficient filtering-based robust multi-task gradient descent method.
  arXiv  Detail & Related papers  (2026-07-02T18:23:41Z)
• Low Rank for Rank: Uncertainty-Aware Task-Specific LLM Ranking under Sparse Pairwise Comparisons [16.73008463123115]
  Low-rank sharing improves sample efficiency over independent task-wise Bradley-Terry estimation.<n>Experiments on synthetic data and Arena show that low-rank sharing improves sample efficiency over independent task-wise Bradley-Terry estimation.
  arXiv  Detail & Related papers  (2026-05-28T05:44:43Z)
• Active Bipartite Ranking with Smooth Posterior Distributions [1.9838140219494644]
  Bipartite ranking is a statistical learning problem involved in many applications and widely studied in the passive context.<n>We propose a novel algorithm, referred to as smooth-rank and designed for the continuous setting, which aims to minimise the distance between the ROC curve of the estimated ranking rule and the optimal one w.r.t. the $sup$ norm.<n>We provide a problem dependent upper bound on the expected sampling time of smooth-rank and establish a problem dependent lower bound on the expected sampling time of any PAC$(,)$ algorithm.
  arXiv  Detail & Related papers  (2026-02-27T18:32:08Z)
• In-Context Learning Is Provably Bayesian Inference: A Generalization Theory for Meta-Learning [51.56484100374058]
  We introduce a principled risk decomposition that separates the total ICL risk into two components: Bayes Gap and Posterior Variance.<n>For a uniform-attention Transformer, we derive a non-asymptotic upper bound on this gap, which explicitly clarifies the dependence on the number of pretraining prompts.<n>The Posterior Variance is a model-independent risk representing the intrinsic task uncertainty.
  arXiv  Detail & Related papers  (2025-10-13T03:42:31Z)
• Fast Rate Bounds for Multi-Task and Meta-Learning with Different Sample Sizes [21.925083923451595]
  We present new fast-rate PAC-Bayesian generalization bounds for multi-task and meta-learning in the unbalanced setting.<n>Our new bounds are numerically computable as well as interpretable.<n>We shed light on the fact that the unbalanced situation allows two meaningful definitions of multi-task risk.
  arXiv  Detail & Related papers  (2025-05-21T13:22:07Z)
• Relaxed Quantile Regression: Prediction Intervals for Asymmetric Noise [51.87307904567702]
  Quantile regression is a leading approach for obtaining such intervals via the empirical estimation of quantiles in the distribution of outputs.<n>We propose Relaxed Quantile Regression (RQR), a direct alternative to quantile regression based interval construction that removes this arbitrary constraint.<n>We demonstrate that this added flexibility results in intervals with an improvement in desirable qualities.
  arXiv  Detail & Related papers  (2024-06-05T13:36:38Z)
• Robust Multi-Task Learning with Excess Risks [24.695243608197835]
  Multi-task learning (MTL) considers learning a joint model for multiple tasks by optimizing a convex combination of all task losses. Existing methods use an adaptive weight updating scheme, where task weights are dynamically adjusted based on their respective losses to prioritize difficult tasks. We propose Multi-Task Learning with Excess Risks (ExcessMTL), an excess risk-based task balancing method that updates the task weights by their distances to convergence.
  arXiv  Detail & Related papers  (2024-02-03T03:46:14Z)
• Noise Covariance Estimation in Multi-Task High-dimensional Linear Models [8.807375890824977]
  This paper studies the multi-task high-dimensional linear regression models where the noise among different tasks is correlated. Treating the regression coefficients as a nuisance parameter, we leverage the multi-task elastic-net and multi-task lasso estimators to estimate the nuisance. Under suitable conditions, the proposed estimator attains the same rate of convergence as the "oracle" estimator.
  arXiv  Detail & Related papers  (2022-06-15T02:37:37Z)
• Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
  We study the problem of estimating the fixed point of a contractive operator defined on a separable Banach space. We establish non-asymptotic bounds for both the operator defect and the estimation error.
  arXiv  Detail & Related papers  (2022-01-21T02:46:57Z)
• New Tight Relaxations of Rank Minimization for Multi-Task Learning [161.23314844751556]
  We propose two novel multi-task learning formulations based on two regularization terms. We show that our methods can correctly recover the low-rank structure shared across tasks, and outperform related multi-task learning methods.
  arXiv  Detail & Related papers  (2021-12-09T07:29:57Z)
• Risk-Sensitive Deep RL: Variance-Constrained Actor-Critic Provably Finds Globally Optimal Policy [95.98698822755227]
  We make the first attempt to study risk-sensitive deep reinforcement learning under the average reward setting with the variance risk criteria. We propose an actor-critic algorithm that iteratively and efficiently updates the policy, the Lagrange multiplier, and the Fenchel dual variable.
  arXiv  Detail & Related papers  (2020-12-28T05:02:26Z)
• Precise High-Dimensional Asymptotics for Quantifying Heterogeneous Transfers [66.66228496844191]
  We show when does combining the samples from two related tasks perform better than learning with one target task alone?<n>This question is motivated by an empirical phenomenon known as negative transfer, which has been observed in practice.<n>We illustrate these results in a random-effects model to mathematically prove a phase transition from positive to negative transfer as the number of source task samples increases.
  arXiv  Detail & Related papers  (2020-10-22T14:14:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.