\pdfoutput=1

\documentclass[english,11pt]{article}
\input{macros}
\usepackage{etoc}
\pgfplotsset{compat=1.18}
\etocdepthtag.toc{mtchapter}
\etocsettagdepth{mtchapter}{subsection}
\etocsettagdepth{mtappendix}{none}
\setlist[enumerate,1]{label=\arabic*., leftmargin=2em, labelsep=0.5em}
\newcommand{\BlackBox}{\rule{1.5ex}{1.5ex}} 
\usepackage{authblk}
\bibliographystyle{apalike}
\setcitestyle{authoryear}
\usepackage{tcolorbox}
\newcommand{\tr}{\operatorname{Tr}}

\usepackage[flushleft]{threeparttable} % note below tables

% \usepackage[fontsize=11pt]{scrextend}
% \renewcommand{\baselinestretch}{1.5}



\begin{document}


\title{\LARGE Multi-task Linear Regression without Eigenvalue Lower Bounds:
Adaptivity, Robustness and Safety}%\blfootnote{Author names are sorted alphabetically.}



\author[1]{Seok-Jin Kim\thanks{\texttt{seok-jin.kim@columbia.edu}}}
% The order may be wrong on these next two:
\newcommand\CoAuthorMark{\footnotemark[\arabic{footnote}]} % get the current value


\affil[1]{Columbia IEOR}



\date{This version: \today}

\maketitle

\begin{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 $\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 \citet{duan2023adaptive} 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.
\end{abstract}




\section{Introduction}\label{section; introduction}

Multi-task learning (MTL) aims to improve performance across multiple tasks simultaneously by exploiting their underlying relatedness \citep{zhang2018overview,zhang2021survey}.
This paradigm has achieved significant empirical success \citep{caruana1997multitask,evgeniou2004regularized,evgeniou2005learning}
and has recently attracted growing theoretical interest \citep{asiaee2019data,wu2020understanding,tian2026robust,tian2025learning,huang2025optimal}.
In this paper, we investigate MTL for linear and generalized linear models (GLMs) in a regime where the majority of tasks are similar, but a minority are arbitrary outliers.
Crucially, neither the degree of similarity nor the fraction of outliers is known \emph{a priori}, necessitating an adaptive learning approach.
While outliers pose substantial theoretical challenges, robust estimators have recently been developed to address them \citep{tian2026robust,duan2023adaptive,tian2025learning}.

\paragraph{Problem Setup.}
We consider a system of $m$ tasks. For the $j$-th task, we observe a dataset $\cD_j := \{(x_{ji}, y_{ji})\}_{i=1}^{n_j}$, with covariates $x_{ji}\in\RR^d$ and responses $y_{ji}\in\RR$, generated by a linear model $\EE[y_{ji} \mid x_{ji}] = x_{ji}^\top \theta_j^\star$, where $\theta_j^\star \in \RR^d$ is the unknown parameter for task $j \in [m]$.
Our analysis naturally extends to generalized linear models (GLMs).
The objective is to estimate each $\theta_j^\star$ with small prediction mean squared error (MSE), also referred to as prediction risk.
For each task $j$, let $\bSigma_j := \frac{1}{n_j}\sum_{i=1}^{n_j} x_{ji} x_{ji}^\top$ denote the \textit{empirical second moment matrix}.
We primarily focus on the balanced sample size case where $n_j = n$ for all $j$, deferring the heterogeneous setting to the appendix.

\paragraph{Task Relatedness with Outliers.}
We adopt the contamination model introduced by \citet{duan2023adaptive}.
We assume there exists a subset of ``inlier'' tasks $\Sb \subseteq [m]$ whose parameters $\{\theta_j^\star\}_{j \in \Sb}$ lie within an $\ell_2$-ball of radius $\delta$.
The remaining tasks in $\Sb^c$ are outliers with no assumed structure, comprising a fraction $\frac{|\Sb^c|}{m} < \varepsilon$ of the total tasks.
The parameters $\varepsilon$ and $\delta$ are unknown to the learner.
This contaminated relatedness model has also been developed in subsequent work on semiparametric multi-task inference \citep{bhattacharya2025late}.
This formulation generalizes standard $\ell_2$-closeness assumptions studied in the outlier-free regime \citep{soare2014multi,wang2021multitask,sessa2023multitask}.
Alternative notions of relatedness, such as shared low-rank representations, have been explored elsewhere \citep{tian2025learning}; see Section~\ref{section; background} for a detailed review.

\paragraph{Relaxing Lower Boundedness of Second Moments.}
A significant limitation of existing outlier-robust analyses \citep[e.g.,][]{duan2023adaptive,tian2025learning} is the reliance on well-conditioned covariates.
Specifically, these works typically assume the existence of constants $\rho = \Omega(1)$ and $L = \cO(1)$ such that $\rho \Ib_d \preceq \bSigma_j \preceq L \Ib_d$ for all $j \in [m]$.
Under this \emph{Lower Boundedness of Second Moments} (LBSM) condition, the analysis of \citet{duan2023adaptive} yields the following bounds for their estimator \(\{\hat{\theta}_j\}_{j=1}^m\):
\begin{equation}\label{equation; ARMUL bound}
\begin{aligned}
&\|\hat{\theta}_j-\theta_j^\star\|^2_2 
\lesssim \frac{1}{\rho^2}
\left(\frac{d}{mn}+\min\left(\frac{L^4}{\rho^2}\delta^2, \frac{d}{n}\right)+ \varepsilon^2 \frac{d}{n}\right),
\quad j \in \Sb, \\
&\|\hat{\theta}_j-\theta_j^\star\|^2_2
\lesssim \frac{1}{\rho^2}\frac{d}{n},
\quad j \in \Sb^c. 
\end{aligned}
\end{equation}
While the upper bound $L = \cO(1)$ is mild \citep{vershynin2018high,wainwright2019high}, the lower bound requirement $\rho = \Omega(1)$ is restrictive and often unrealistic in high-dimensional settings or for distributions with decaying spectra.
For instance, covariates drawn uniformly from a sphere satisfy $\rho \asymp 1/d$, causing the bound in \eqref{equation; ARMUL bound} to degrade significantly.
This concern is not limited to passive data collection: in online learning settings such as linear bandits, the covariates or actions are selected adaptively by an algorithm, and the resulting taskwise empirical second moments need not satisfy uniform spectral regularity.
From the standpoint of prediction MSE, it remains an open question whether this dependence on $\rho$ is fundamental or an artifact of the Euclidean-parameter analysis.

Single-task linear regression suggests that the LBSM requirement should not be necessary for prediction.
Indeed, a fundamental baseline is \emph{Independent-Task Learning} (ITL), which estimates $\theta_j^\star$ using only $\cD_j$ and attains in-sample prediction MSE $\tilde{\cO}(d/n)$ regardless of the condition number of $\bSigma_j$ \citep{wainwright2019high,bach2024learning}.
This raises the central question of this work: \emph{can multi-task linear regression exploit relatedness even under rapidly decaying spectra, while still preserving the ITL rate whenever transfer is unhelpful?}
We answer this question affirmatively by replacing the standard $\ell_2$ regularization used in \citet{duan2023adaptive} (see Eq.~\eqref{equation; armul loss}) with a \emph{matrix-weighted regularization} induced by the norms $\|\cdot\|_{\bSigma_j}$.
As detailed in Section~\ref{section; methodologies}, this geometry relaxes LBSM: under the balancedness assumption introduced in Section~\ref{section; data assumption}, it enables beneficial transfer, while preserving the $\tilde{\cO}(d/n)$ independent-task rate when transfer is unhelpful.

\subsection{Overview of Results}
Our approach replaces LBSM with a \emph{balancedness assumption}, quantified by a balancedness constant $B$ that measures the similarity of second moment matrices across tasks rather than enforcing a uniform lower bound.
Under LBSM, $B \lesssim 1$, but our condition accommodates significantly broader scenarios, including rapidly decaying spectra.
Under this relaxed assumption, we derive adaptive in-sample MSE guarantees and, once $n$ exceeds a mild threshold, corresponding population MSE bounds.
Our results are summarized informally as follows:

\begin{theorem}[Informal]
Consider the multi-task linear regression problem with outliers (Definition~\ref{definition; task relatedness}).
In favorable regimes with a moderate balancedness constant \(B\), our estimator attains the same \(m,n,\delta,\varepsilon\) MSE dependence as the robust MTL guarantee of \citet{duan2023adaptive}, under {substantially relaxed assumptions} on the covariate eigenspectrum; moreover, the task-overall MSE is minimax optimal in these parameters, up to logarithmic and balancedness-dependent factors.
Furthermore, the estimator exhibits:
\begin{enumerate}\setlength\itemsep{0em}
\item \textbf{Robustness:} Efficient estimation in the presence of an unknown fraction $\varepsilon$ of outliers.
\item \textbf{Adaptivity:} Automatic utilization of task similarity under balancedness, without prior knowledge of $\delta$ or $\varepsilon$.
\item \textbf{Safety:} An MSE bound of $\tilde{\cO}(d/n)$ holds even when no useful moderate balancedness constant exists or tasks are unrelated, matching the independent-task baseline.
\end{enumerate}
\end{theorem}

Thus, when \(B\) is moderate, the estimator exploits task relatedness and recovers the robust MTL rate of \citet{duan2023adaptive} under weaker spectral assumptions.
When \(B\) is large or the relatedness structure is unfavorable, the same procedure falls back to the safe \(\tilde{\cO}(d/n)\) rate.



\subsection{Background}\label{section; background}
Multi-task learning has been surveyed comprehensively in \citet{zhang2021survey}.
Within the context of linear models, MTL is a mature field \citep{evgeniou2004regularized,evgeniou2005learning,asiaee2019data,cai2022individual,li2022transfer}.
Classical approaches range from shared covariate representations \citep{breiman1997predicting,evgeniou2004regularized,evgeniou2005learning} to Stein-type shrinkage estimation \citep{chen2015data}.
Theoretical characterizations have been established in simplified settings, such as two-task linear systems or single-hidden-layer networks \citep{mousavi2020minimax, wu2020understanding}.

Regarding task relatedness structures, sparsity-based methods (without outliers) are discussed in \citet{cai2022individual,li2022transfer,huang2025optimal,xu2025multitask}, while low-rank shared representations are examined in \citet{hu2021near,du2023multi,tian2025learning}.
Robust MTL has also been studied with irrelevant or outlier tasks in both linear and latent-variable settings \citep{chen2011integrating,tian2026robust}.
Our work focuses on $\ell_2$-closeness (Definition~\ref{definition; task relatedness}). The outlier-free variant was investigated by \citet{soare2014multi,wang2021multitask,sessa2023multitask}, while the contaminated setting was formalized by \citet{duan2023adaptive} and later pursued in related semiparametric multi-task work \citep{bhattacharya2025late}.

Naive baselines include ITL and Data Pooling (DP).
Both are suboptimal in our regime: ITL ignores task relatedness, while DP is sensitive to negative transfer from outliers \citep{duan2023adaptive}.
To address this, \citet{duan2023adaptive} proposed an adaptive robust method (ARMUL) minimizing the objective:
\begin{align}\label{equation; armul loss}
\cL(\theta_1, \dots, \theta_m, \beta) = \sum_{j \in [m]} \left( f_j(\theta_j) + \lambda \|\theta_j - \beta \|_2 \right),
\end{align}
where $f_j$ is the task-specific loss.
However, their theoretical guarantees (e.g., Eq.~\ref{equation; ARMUL bound}) depend inversely on taskwise curvature parameters; in linear regression, this amounts to dependence on the minimum eigenvalue of \(\bSigma_j\).
Our work relaxes these requirements by replacing the Euclidean regularization $\|\cdot\|_2$ with a matrix-weighted penalty $\|\theta_j - \beta \|_{\bSigma_j}$, while avoiding the strong-convexity requirement used in prior analyses.

\subsection{Notation}
The constants $c_1, c_2, C_1, C_2, \dots$ may differ from line to line. We use the symbol $[n]$ as a shorthand for $\{ 1, 2, \dots, n \}$. For nonnegative sequences $\{ a_n \}_{n=1}^{\infty}$ and $\{ b_n \}_{n=1}^{\infty}$, we write $a_n \lesssim b_n$ or $a_n = \cO(b_n)$ if there exists a positive constant $C$ such that $a_n \leq C b_n$ for all $n$. We use $\widetilde{\cO}$ to hide polylogarithmic factors. In addition, we write $a_n \asymp b_n$ if $a_n \lesssim b_n$ and $b_n \lesssim a_n$. For a vector $x \in \RR^d$, $\|x\|_p$ denotes its $\ell_p$-norm. For any positive semidefinite matrix $A \in \RR^{d \times d}$, we define the induced norm $\|x\|_A := \sqrt{x^\top A x}$.
For extended-real-valued functions \(f,g:\RR^d\to\RR\cup\{+\infty\}\), their infimal convolution is
\[
(f\star g)(\beta):=\inf_{\theta\in\RR^d}\{f(\theta)+g(\beta-\theta)\}.
\]
When the parameter space is restricted to a convex set \(\Cb\), the infimum is taken over \(\theta\in\Cb\).

\section{Problem Setup}\label{section; setup}

We consider a multi-task learning setting with $m$ tasks.
For each task $j \in [m]$, we observe a dataset $\cD_j := \{(x_{ji}, y_{ji})\}_{i=1}^{n_j}$ consisting of $d$-dimensional covariates and scalar responses.
We assume the data generation process follows a linear model:
\begin{align}
y_{ji} = x_{ji}^\top \theta^\star_j + \varepsilon_{ji}, \quad i \in [n_j],
\end{align}
where $\theta^\star_j \in \RR^d$ is the unknown parameter for task $j$.
Conditional on the design $\Xb := \{x_{ji}\}_{j,i}$, the noise terms $\varepsilon_{ji}$ are assumed to be independent and $\sigma$-sub-Gaussian.
Without loss of generality, we set the sub-Gaussian parameter $\sigma = 1$.
While our framework extends to Generalized Linear Models (GLMs) as discussed in Section~\ref{section; GLM}, we focus on the linear model for the primary analysis.

For each task $j$, let $\Xb_j := (x_{j1}, \dots, x_{jn_j})^\top \in \RR^{n_j \times d}$ denote the design matrix and $\Yb_j := (y_{j1}, \dots, y_{jn_j})^\top \in \RR^{n_j}$ the response vector.
We define the empirical Gram matrix as $\Vb_j := \Xb_j^\top \Xb_j = \sum_{i=1}^{n_j} x_{ji} x_{ji}^\top$ and the \emph{empirical second moment matrix} as $\bSigma_j := \frac{1}{n_j}\Vb_j$.
To simplify the theoretical exposition, we assume a balanced sample size $n_j = n$ for all $j \in [m]$ in the main text; extensions to heterogeneous sample sizes are provided in Appendix~\ref{section; general sample size}.

\paragraph{Regularity Assumptions.}
Following standard high-dimensional statistics literature \citep{vershynin2018high,wainwright2019high}, we assume that the covariate norms are bounded.
Specifically, we assume $\|\bSigma_j\|_{\operatorname{op}} \le c$ for a universal constant $c$, which we normalize to $c=1$ for simplicity.
For instance, in the task-wise i.i.d. setting, this empirical bound holds with high probability when $\|x_{ji}\|_2$ is almost surely bounded or sub-exponential.
\emph{Crucially, we do \emph{not} assume that the minimum eigenvalue of $\bSigma_j$ is bounded away from zero.}
% Our goal is to estimate $\{\theta_j^\star\}_{j=1}^m$ efficiently even when $\bSigma_j$ is ill-conditioned or singular, a regime where classical methods often fail.

\paragraph{Task Relatedness with Outliers.}
We adopt the contamination framework introduced by \citet{duan2023adaptive} to model task relatedness in the presence of outliers.

\begin{definition}[Task Relatedness]\label{definition; task relatedness}
A set of tasks is said to be $(\varepsilon, \delta)$-related if there exist a subset of indices $\Sb \subseteq [m]$ and a shared centroid parameter $\theta^\star \in \RR^d$ such that:
\begin{align*}
\max_{j \in \Sb} \|\theta_j^{\star} - \theta^\star\|_{2} \le \delta
\quad \text{and} \quad
\frac{|\Sb^c|}{m} \le \varepsilon.
\end{align*}
\end{definition}
Here, $\Sb$ represents the set of ``inlier'' tasks similar to $\theta^\star$, while $\Sb^c$ contains outlier tasks with arbitrary parameters.
Our algorithm is fully adaptive and requires no prior knowledge of the radius $\delta$, the outlier fraction $\varepsilon$, or the index set $\Sb$.

\paragraph{Performance Measures.}
We evaluate the performance of our estimators using the MSE.
Given the fixed design nature of our analysis, we primarily focus on the \emph{in-sample MSE}.
For an estimator $\hat{\theta}_j$, the in-sample MSE for task $j$ is defined as:
\begin{align}\label{equation; in-sample MSE}
\cE^{\operatorname{in}}_j (\hat{\theta}_j) := \|\hat{\theta}_j - \theta_j^\star\|_{\bSigma_j}^2 = \frac{1}{n_j}\sum_{i=1}^{n_j} \bigl| x_{ji}^\top(\hat{\theta}_j - \theta_j^\star) \bigr|^2.
\end{align}
In the specific setting where covariates are \emph{task-wise i.i.d.} (i.e., $x_{ji} \sim \cP_j$ independently), we also consider the \emph{population MSE}:
\begin{align}\label{equation; MSE}
\cE_j(\hat{\theta}_j) := \EE_{x \sim \cP_j} \bigl[ \bigl| x^\top(\hat{\theta}_j - \theta_j^\star) \bigr|^2 \bigr] = \|\hat{\theta}_j - \theta_j^\star\|_{\bar\bSigma_j}^2,
\end{align}
where $\bar \bSigma_j := \EE[\bSigma_j]$ is the population covariance matrix.
This measure is standard in random design settings \citep{van2008high,buhlmann2011statistics}.
This metric differs from the squared Euclidean parameter error used in \citet{duan2023adaptive}.
Under LBSM, the two metrics are equivalent up to constants.
Under general spectra without LBSM, however, Euclidean parameter error may fail to concentrate even when \(\delta=\varepsilon=0\), because weakly observed or unobserved directions are not statistically identifiable from prediction data.
For this reason, prediction MSE, or risk, is widely used as a standard performance metric in regression with ill-conditioned or singular designs.


\section{Methodologies}\label{section; methodologies}

In this section, we present our proposed estimator.
Although the main theoretical results are stated for the balanced case \(n_j=n\), we present the estimator in a form that also covers heterogeneous sample sizes.
We specialize to \(n_j=n\) in the main analysis from Section~\ref{section; data assumption} onward, and defer the full heterogeneous-sample-size guarantee to Appendix~\ref{section; general sample size}.
We define the collective parameter vector as $\Theta = (\theta_1, \dots, \theta_m, \beta) \in (\RR^d)^{m+1}$, where $\beta$ serves as a shared centroid parameter.
For each task $j \in [m]$, let $f_j: \RR^d \to \RR$ be the task-specific convex loss function.
For standard linear regression, we adopt the quadratic loss $f_j(\theta) = \frac{1}{2n_j}\|\Yb_j - \Xb_j \theta \|_2^2$.

\paragraph{Proposed Objective.}
We propose to minimize a novel multi-task objective function that incorporates a \emph{matrix-weighted regularization}.
Given nonnegative weights $\{w_j\}_{j=1}^m$ and regularization parameters $\{\lambda_j\}_{j=1}^m$, our loss function is defined as:
\begin{equation}\label{equation; loss}
\cL(\Theta) := \sum_{j=1}^m w_j \left( f_j(\theta_j) + \lambda_j \|\theta_j - \beta\|_{\bSigma_j} \right).
\end{equation}
Here, the penalty term $\|\theta_j - \beta\|_{\bSigma_j} := \sqrt{(\theta_j - \beta)^\top \bSigma_j (\theta_j - \beta)}$ adapts the regularization geometry to the empirical second moment of each task.
This is the primary distinction from prior work \citep{duan2023adaptive}, which employs isotropic regularization (see Eq.~\eqref{equation; armul loss}).
Equivalently,$
\|\theta_j-\beta\|_{\bSigma_j} = \frac{1}{\sqrt{n_j}}\|\Xb_j(\theta_j-\beta)\|_2,
$
so the penalty measures disagreement in \emph{prediction space} rather than raw parameter space.
For Gaussian regression with common noise variance, this quantity is proportional to the Kullback--Leibler divergence between the task-wise predictive distributions induced by \(\theta_j\) and \(\beta\) on task \(j\)'s design.
Equivalently, the analysis can be viewed as whitening by \(\bSigma_j^{1/2}\): the penalty becomes Euclidean in prediction-normalized coordinates, which is why weakly observed directions are not over-penalized.
Under pairwise comparability of the task covariances, this whitening perspective would largely reduce to a common-geometry argument; the main technical challenge here is to make it work under the weaker one-sided, average-based balancedness condition of Assumption~\ref{assumption; comparability}.
By contrast, an isotropic Euclidean penalty treats weak and well-observed directions equally and reintroduces the lower-eigenvalue dependence that we seek to avoid.
Thus, by exploiting the curvature information in $\bSigma_j$, our formulation remains effective even when the Gram matrices are ill-conditioned or singular.

Let $\Cb \subseteq \RR^d$ denote the feasible set for the parameters $\theta_j^\star$ and $\theta^\star$.
If a norm bound is known (e.g., $\|\theta^\star\|_2 \le \xi$), we set $\Cb = \mathbf{B}(0, \xi)$; otherwise, we set $\Cb = \RR^d$.
Our estimator is obtained by solving the following joint convex optimization problem:
\begin{equation}\label{equation; minimizer}
(\hat{\theta}_1, \dots, \hat{\theta}_m, \hat{\beta}) \in \mathop{\arg \min}_{\Theta \in \Cb^{m+1}} \cL(\theta_1, \dots, \theta_m, \beta).
\end{equation}
The complete procedure is outlined in Algorithm~\ref{algorithm; MTLR}.

\begin{algorithm}[H]
\caption{\texttt{MTLR}: Matrix-Weighted Multi-task Linear Regression}
\label{algorithm; MTLR}
\begin{algorithmic}[1]
\STATE \textbf{Input:} Datasets $\{\cD_j\}_{j=1}^m$, task weights $\{w_j\}_{j=1}^m$, regularization parameters $\{\lambda_j\}_{j=1}^m$.
\STATE \textbf{Step 1:} Compute the empirical second moment matrices $  \bSigma_j \leftarrow \frac{1}{n_j}\Xb_j^\top \Xb_j$, for all $j \in [m]$.

\STATE \textbf{Step 2:} Solve the joint convex minimization problem:
\begin{align*}
    &(\hat{\theta}_1, \dots, \hat{\theta}_m, \hat{\beta})  \\
    &\leftarrow \mathop{\arg \min}_{\Theta \in \Cb^{m+1}} \sum_{j=1}^m w_j \left( f_j(\theta_j) + \lambda_j \|\theta_j - \beta\|_{\bSigma_j} \right).
\end{align*}
\STATE \textbf{Return:} The estimated task parameters $\{\hat{\theta}_j\}_{j=1}^m$.
\end{algorithmic}
\end{algorithm}

\paragraph{Parameter Selection.}
As justified by our theoretical analysis (Section~\ref{section; results-linear}), we recommend scaling the regularization parameter as $\lambda_j \asymp \sqrt{d/n_j}$.
This prescription uses only the observed dimension \(d\) and sample sizes \(n_j\); the remaining scalar multiplier can be fixed for a target confidence level or tuned by cross-validation, without knowing \(\varepsilon\), \(\delta\), or \(\Sb\).
Further guidance on hyperparameter tuning is provided in the experimental section.

\paragraph{Specific Instantiations.}
We detail the configuration of our loss function for different settings:

\begin{itemize}
\item \textbf{Linear Model (Equal Sample Size):}
In the standard setting where $n_j = n$, we set $w_j = 1$ and $\lambda_j = \lambda$ for all $j$.
The objective simplifies to:
\[
\cL(\Theta) = \sum_{j=1}^m \big( \frac{1}{2n} \|\Yb_j - \Xb_j \theta_j\|_2^2 + \lambda \|\theta_j - \beta\|_{\bSigma_j} \big).
\]

\item \textbf{GLM (Equal Sample Size):}
For GLMs with equal sample sizes, we again set $w_j=1$ and $\lambda_j=\lambda$ for all $j$, and define the task loss as the negative log-likelihood:
\[
f_j(\theta) := \frac{1}{n} \sum_{i=1}^{n} \bigl( \psi(x_{ji}^\top \theta) - y_{ji} x_{ji}^\top \theta \bigr),
\]
where $\psi$ is the cumulant generating function (e.g., $\psi(t) = \log(1+e^t)$ for logistic regression).
See Section~\ref{section; GLM} for details.

\item \textbf{General Sample Size:}
For heterogeneous sample sizes, we balance the terms by setting $w_j = n_j$ and scaling $\lambda_j = \lambda / \sqrt{n_j}$.
The resulting weighted loss for linear model is:
\[
\cL(\Theta) = \sum_{j=1}^m n_j \big( \frac{1}{2n_j} \|\Yb_j - \Xb_j \theta_j\|_2^2 + \lambda_j \|\theta_j - \beta\|_{\bSigma_j} \big).
\]
A detailed derivation is provided in Appendix~\ref{section; general sample size}.
\end{itemize}

\paragraph{Implementation via Reparameterization.}
Since the objective \eqref{equation; loss} is jointly convex whenever the task losses \(f_j\) and the feasible set \(\Cb\) are convex, it can be solved efficiently.
For practical implementation, it is often convenient to reparameterize the problem using deviations $v_j := \theta_j - \beta$.
We optimize over $(\beta, v_1, \dots, v_m)$ by solving:
\[
\min_{\beta, \{v_j\}} \sum_{j=1}^m w_j \left( f_j(\beta + v_j) + \lambda_j \|v_j\|_{\bSigma_j} \right).
\]
The exact objective is nonsmooth only at zero-seminorm deviations, and is amenable to standard convex optimization algorithms such as proximal gradient descent or block coordinate descent.
In our numerical experiments, we use L-BFGS-B on this reparameterized objective with a tiny numerical floor in the norm-gradient computation.
For the problem sizes considered in our experiments, this implementation converged reliably and added only modest optimization overhead relative to the baseline methods.


\section{Our Relaxed Assumption: Balancedness}\label{section; data assumption}

We now introduce our core assumption regarding the spectral properties of the tasks.
Unlike prior works that impose absolute bounds on eigenvalues, we propose a relative condition measuring the \emph{balancedness} of information across tasks.
From this section through the main linear and GLM results, we maintain the balanced-sample-size convention \(n_j=n\); the heterogeneous-sample-size extension is given in Appendix~\ref{section; general sample size}.

For any subset of tasks $\Ib \subseteq [m]$, let $\Vb_\Ib := \sum_{j \in \Ib} \Vb_j$ denote the aggregate Gram matrix, and define the average empirical second moment matrix as:
\[
\bm{\bSigma}_\Ib := \frac{1}{n|\Ib|} \Vb_\Ib = \frac{1}{|\Ib|} \sum_{j \in \Ib} \bSigma_j.
\]
$\bm{\bSigma}_\Ib$ captures the aggregate covariate geometry within the task cluster $\Ib$.
Our assumption posits that the second moment of any individual task is not excessively disparate compared to the aggregate geometry of the similar tasks $\Sb$.

\begin{assumption}[Balancedness]\label{assumption; comparability}
There exists a constant $B > 0$ such that the following spectral inequality holds for all $j \in [m]$:
\begin{align}
\bSigma_j \preceq B \cdot \bm{\bSigma}_\Sb.
\end{align}
We refer to $B$ as the \textit{balancedness constant}.
\end{assumption}

Strictly speaking, if extended values are allowed, the smallest such scalar always exists in \([1,\infty]\): when no finite scalar satisfies the Loewner inequality, we write \(B=\infty\).
Thus, throughout the paper, statements such as ``favorable balancedness'' mean that this extended balancedness constant is finite and moderate, not merely that a formal value of \(B\) can be assigned.
This distinction matters because there are examples with essentially disjoint informative directions where shared estimation offers little or no improvement over ITL; see Remark~\ref{remark: finite B matters}.

The role of $B$ is one-sided.
It does not measure eigendecay itself, and it does not exclude zero eigenvalues: fast eigendecay and exact rank deficiency are both compatible with finite $B$.
Nor is the point of the theory to claim optimal dependence on arbitrary $B$.
Instead, $B$ quantifies how favorable the transfer geometry is once LBSM has been removed.
The main theorem remains informative even when $B$ is large: the transfer terms weaken, but the safety statement still matches ITL.

Crucially, Assumption~\ref{assumption; comparability} is strictly weaker than the LBSM condition ($\bSigma_j \succeq \rho \Ib$) assumed in \citet{duan2023adaptive}.
We highlight several key properties:
\begin{enumerate}
\item \textbf{Upper Bound Only:} We only impose an \textit{upper bound} on $\bSigma_j$. This allows $\bSigma_j$ to be rank-deficient or have a rapidly decaying spectrum (i.e., zero or near-zero eigenvalues are permitted).
\item \textbf{Safety First:} The algorithm does not need to know $B$. Even if $B$ is large or infinite, Theorem~\ref{theorem; MSE bound} still yields the independent-task rate $\tilde{\cO}(d/n)$ through its universal safety part.
\item \textbf{Favorable-Regime Refinement:} When $B$ is moderate, transfer becomes provably beneficial and the sharper multi-task terms appear.
\item \textbf{Relaxed Comparability:} It is weaker than pairwise comparability ($\bSigma_j \preceq B \bSigma_k$), as it compares an individual task to the \emph{average} of many tasks. Pairwise comparability is implied by LBSM with an upper covariance bound and often appears in transfer-learning analyses through bounded density-ratio assumptions; our condition is one-sided and average-based.
\end{enumerate}

\begin{remark}[Why finite $B$ matters]\label{remark: finite B matters}
A finite balancedness constant is not merely a technical artifact. If the inlier tasks are concentrated on essentially disjoint subspaces, then one can have \(B \asymp |\Sb|\) while the average covariance \(\bSigma_\Sb\) contains no direction that is uniformly informative across tasks. In such a regime, shared estimation offers little or no gain over ITL. Thus, some form of balancedness is genuinely necessary for nontrivial transfer, even though the safety part of our guarantee continues to hold without it.
\end{remark}

\paragraph{Connection to Covariate Shift in Linear Models.}
The balancedness assumption has a similar one-sided flavor to coverage assumptions in linear-model transfer under covariate shift.
There, source-to-target transfer is typically controlled by a Loewner comparison between the second moment matrices of the training and evaluation distributions: the directions that matter for the target risk must be sufficiently covered by the source design, while no uniform lower bound on every target covariance direction is required \citep{wang2026pseudo}.
Our condition plays the same role in the multi-task contaminated setting.
The aggregate inlier covariance \(\bSigma_\Sb\) acts as the shared source of information, and the requirement \(\bSigma_j \preceq B\bSigma_\Sb\) says that each task's prediction geometry is covered by that aggregate inlier geometry up to the balancedness constant \(B\).
Thus the assumption is not a disguised eigenvalue lower bound; it is a one-sided coverage condition that identifies when information can be transferred safely from the good tasks while still permitting singular or highly anisotropic designs.

\paragraph{Empirical Diagnostic.}
Because Assumption~\ref{assumption; comparability} is stated in terms of empirical second moments, it also suggests a simple diagnostic:
\begin{align*}
   & B_{\mathrm{emp}}
:=
\max_{j\in[m]}
\lambda_{\max}\!\left(\bSigma_{[m]}^{\dagger/2}\bSigma_j\bSigma_{[m]}^{\dagger/2}\right),
\\
&\bSigma_{[m]}:=\frac{1}{m}\sum_{k=1}^m\bSigma_k.
\end{align*}
When the outlier fraction is moderate, \(\bSigma_{[m]}\) is a practical proxy for the unknown inlier average \(\bSigma_\Sb\), so \(B_{\mathrm{emp}}\) provides a rough estimate of how favorable the transfer geometry is.
Large values of \(B_{\mathrm{emp}}\) indicate that one or a few tasks have covariate directions poorly represented by the task average.
This diagnostic is not used by the estimator, but it can help interpret a dataset or screen a small number of tasks that make transfer geometry unfavorable.


\subsection{Examples of Assumption~\ref{assumption; comparability}}\label{subsection; balancedness example}
We illustrate the generality of Assumption~\ref{assumption; comparability} through the following examples, covering both well-conditioned and degenerate regimes.

\paragraph{Example 1 (LBSM Regime).}
Suppose the standard eigenvalue bounds hold: $\rho \Ib_d \preceq \bSigma_j \preceq L\Ib_d$ for all $j$.
Then $\bSigma_j \preceq L \Ib_d = \frac{L}{\rho} (\rho \Ib_d) \preceq \frac{L}{\rho} \bm{\bSigma}_\Sb$.
Thus, Assumption~\ref{assumption; comparability} holds with $B = L/\rho$.
Our analysis therefore replaces direct lower-eigenvalue dependence by the relative constant \(B\), which equals \(L/\rho\) under this classical well-conditioned regime but remains meaningful far beyond it.

\paragraph{Example 2 (Pairwise Comparable).}
If $\bSigma_j \preceq B' \bSigma_k$ for all pairs $j, k$, then summing over $k \in \Sb$ and normalizing implies $\bSigma_j \preceq B' \bm{\bSigma}_\Sb$. Thus, the assumption holds with $B=B'$.

\paragraph{Example 3 (Degenerate/Low-Rank Covariates).}
Consider a degenerate setting where $\bSigma_j = \Ib_d$ for a subset $\Ib \subset [m]$ and $\bSigma_j = \mathbf{0}$ otherwise.
Provided that the inliers overlap with the informative tasks (i.e., $\Sb \cap \Ib \neq \emptyset$), a direct calculation shows that Assumption~\ref{assumption; comparability} holds with the finite constant $B = \frac{|\Sb|}{|\Sb \cap \Ib|}$.

\subsection{Balancedness for Task-wise i.i.d. Covariates}
\label{subsection; assumption example expected second moment}
While our analysis primarily relies on the empirical quantities $\bSigma_j$, it is instructive to relate Assumption~\ref{assumption; comparability} to population properties when covariates are stochastic.
Consider the setting where $x_{ji} \overset{\text{i.i.d.}}{\sim} \cP_j$ for each task $j$, and let $\bar{\bSigma}_j := \EE_{x\sim\cP_j}[xx^\top]$.

We define the \textit{comparability measure} $\nu_j \ge 1$ as the smallest constant satisfying:
\begin{align}\label{definition; comparability measure}
\nu_j^{-1} \bSigma_j \preceq \bar{\bSigma}_j \preceq \nu_j \bSigma_j.
\end{align}
This constant captures the concentration of the empirical covariance around its mean.
Standard matrix concentration theory guarantees that $\nu_j \approx 1$ with high probability once the sample size $n$ satisfies mild conditions.

\paragraph{Sample Complexity for Sub-Exponential Covariates.}
If \(x_{ji}\) follows a strongly sub-Gaussian or sub-exponential distribution with parameter \(K = \cO(1)\), then by Theorem 4.7.1 in \citet{vershynin2018high,ding2024sub}, we typically have 
\(
\nu_j \lesssim 1
\)
once \(n = \tilde\Omega(d)\).
Standard distributions such as Gaussian and Uniform satisfy this condition.
Specifically, if the coordinates of \(\bar\bSigma_j^{-1/2}x_{ji}\) have \(\cO(1)\) ninth moments, or if \(\bar\bSigma_j^{-1/2}x_{ji}\) itself satisfies a \(\tilde{\cO}(1)\) high-probability \(\ell_2\)-norm bound, then a sample complexity of \(\tilde{\cO}(d)\) suffices \citep{oliveira2016lower}.
We provide a more detailed discussion regarding general sub-exponential covariates in Section~\ref{section; detail sample complexity} and Lemma~\ref{lemma; sample complexity}.
Even for general sub-exponential covariates, \(\nu_j = \tilde{\cO}(1)\) holds provided that \(n\) satisfies a mild sample complexity requirement.
Furthermore, if $\bar{\bSigma}_j$ satisfies the LBSM condition, standard matrix concentration results imply \(\nu_j = \mathcal{O}(1)\) as long as $n = \tilde{\Omega}(d)$ \citep{vershynin2018high}.

Using this measure, we can reformulate the balancedness assumption in terms of population quantities:
\begin{remark}[Population Balancedness]\label{example; bounded second moments}
Define the average population covariance \(\bar \bSigma_{\Sb}:= \frac{1}{|\Sb|} \sum_{j \in \Sb} \bar{\bSigma}_j\).
If the population covariances satisfy $\bar{\bSigma}_j \preceq \bar{B}\bar{\bSigma}_\Sb$, then the empirical Assumption~\ref{assumption; comparability} holds with $B \lesssim (\max_j \nu_j)^2 \bar{B}$.
\end{remark}

\section{Results for Linear Model}\label{section; results-linear}

In this section, we derive theoretical guarantees for the linear model.
Unlike prior analyses, our guarantees depend on the relaxed balancedness constant $B$ rather than the minimum eigenvalue of $\bSigma_j$.
They should be read in two layers: a universal safety bound, and a sharper transfer bound when the geometry is favorable.

We fix a failure probability $\kappa \in (0,1)$ and define $\zeta := \log(16m/\kappa)$.
Throughout this section, we maintain the balanced-sample-size convention \(n_j=n\); the general case is treated in Appendix~\ref{section; general sample size}.

\subsection{In-sample MSE Bound}
We analyze Algorithm~\ref{algorithm; MTLR} with the regularization parameter scaled as $\lambda_j = q\sqrt{d\zeta/n}$ for a sufficiently large universal constant $q \gtrsim 1$.
The following theorem establishes the in-sample performance.

\begin{theorem}[In-sample MSE]\label{theorem; MSE bound}
Suppose the task relatedness condition (Definition~\ref{definition; task relatedness}) holds.
With probability at least $1-\kappa$, the estimator $\hat{\theta}_j$ obtained by Algorithm~\ref{algorithm; MTLR} with \(\Cb= \RR^{d}\) satisfies the following bounds simultaneously for all $j \in [m]$:

\begin{itemize}
\item \textbf{Safety Guarantee:} Regardless of the balancedness constant $B$ or the parameters $\varepsilon$ and $\delta$,
\[
\cE_j^{\operatorname{in}}(\hat{\theta}_j) \;\lesssim\; q^2 \frac{d}{n} \zeta.
\]
This matches the minimax rate for independent-task linear regression.

\item \textbf{Adaptivity and Robustness:} If Assumption~\ref{assumption; comparability} holds with $B \lesssim \min(1/\varepsilon, m)$, then for all inlier tasks $j \in \Sb$:
\[
\begin{aligned}
\cE_j^{\operatorname{in}}(\hat{\theta}_j)
&\;\lesssim\; \biggl( \frac{B d}{m n}
    + \min\left( B\delta^2, \, q^2 \frac{d}{n} \right) 
    + q^2 B^2 \varepsilon^2 \frac{d}{n} \biggr) \zeta.
\end{aligned}
\]
\end{itemize}
\end{theorem}
\paragraph{Discussion.}
Compared to \citet{duan2023adaptive}, our result avoids dependence on the minimum eigenvalue of the second moments.
Part (a) is a universal safety statement: regardless of $B$, $\varepsilon$, or $\delta$, the estimator never pays more than the independent-task rate up to logarithmic factors.
Part (b) becomes active only when $B$ is moderate and tasks are related.
In this favorable regime, the inlier guarantee, together with the safety bound for outlier tasks, recovers the same \(m,n,\delta,\varepsilon\) rate structure as the robust MTL guarantee of \citet{duan2023adaptive}, but without imposing LBSM; the covariate-geometry dependence enters through the relative balancedness constant \(B\) rather than through a taskwise lower eigenvalue.
Under classical LBSM with \(B=L/\rho\), this replaces the lower-eigenvalue-driven factors in the prior Euclidean-parameter analysis by the relative balancedness factor \(B\), which can remain finite even when no uniform lower eigenvalue exists.
Specializing back to the LBSM regime, our prediction-MSE bound has a milder \(\rho\)-dependence than the MSE bound obtained from the analysis of \citet{duan2023adaptive}.

\paragraph{Discussion of Optimality.}
Indeed, averaging the theorem bounds over all tasks gives
\begin{align*}
    &\frac{1}{m}\sum_{j=1}^m \cE_j^{\operatorname{in}}(\hat{\theta}_j)
\lesssim
\left(\frac{B d}{mn}+\min\left(B\delta^2,\, q^2\frac{d}{n}\right)+q^2B^2\varepsilon^2\frac{d}{n}+\varepsilon q^2\frac{d}{n}\right)\zeta,
\end{align*}
which, in favorable regimes with moderate \(B\), has the same \(m,n,\delta,\varepsilon\) dependence as the robust MTL benchmark of \citet{duan2023adaptive} when viewed through prediction risk.
The matching lower-bound comparison is most naturally stated in the fixed-design setting and is already witnessed by an orthogonal-design submodel: when \(\Xb_j^\top \Xb_j=n\Ib_d\) and the noise is Gaussian, the observations reduce to independent Gaussian sequence observations \(n^{-1}\Xb_j^\top \Yb_j=\theta_j^\star+N(0,\Ib_d/n)\), with \(B=1\).
Specializing the minimax lower-bound construction of \citet{duan2023adaptive} to this submodel yields the additive lower bound
\[
\frac{d}{mn}+\min\left\{\delta^2,\frac{d}{n}\right\}+\varepsilon\frac{d}{n}.
\]
Since in-sample prediction MSE coincides with squared Euclidean parameter error in this orthogonal submodel, the task-overall in-sample MSE above is minimax optimal with respect to \(m,n,\delta,\varepsilon\) in the favorable balanced regime, up to logarithmic and balancedness-dependent factors.

\subsection{Population MSE Bound}
We now extend our guarantees to the population MSE $\cE_j(\hat{\theta}_j)$ (defined in \eqref{equation; MSE}) under the assumption that covariates are task-wise i.i.d.
Recall the definition of the comparability constant $\nu_j$ from \eqref{definition; comparability measure}, which relates empirical and population covariances ($\bar{\bSigma}_j \preceq \nu_j \bSigma_j$).

\begin{theorem}[Population MSE]\label{theorem; population MSE}
In the task-wise i.i.d. setting, under the conditions of Theorem~\ref{theorem; MSE bound}, the following population bounds hold with probability at least \(1-\kappa\):
\begin{enumerate}
\item \textbf{Via Comparability:} For all tasks,
\[
\cE_j(\hat{\theta}_j) \;\le\; \nu_j \cdot \cE_j^{\operatorname{in}}(\hat{\theta}_j).
\]
\item \textbf{Via Intrinsic Dimension (Safety):} Let $U_j$ be a high-probability upper bound on $\|x_{ji}\|_2$ in the sense formalized in Definition~\ref{definition; hp norm bound} of Appendix~\ref{section; detail sample complexity}. If the parameter domain is known to be bounded, \(\Cb = \mathbf{B}(0,\xi)\), and \(\theta_j^\star\in\Cb\), then:
\[
\cE_j(\hat{\theta}_j^\xi) \;\lesssim\; \cE_j^{\operatorname{in}}(\hat{\theta}_j) + \tilde{\cO}\big(\frac{\xi^2 U_j^2}{n}\big),
\]
where \(\hat{\theta}_j^\xi\) is the \(\|\cdot\|_{\bSigma_j}\)-norm projection of \(\hat{\theta}_j\) onto \(\mathbf B(0,\xi)\).
\end{enumerate}
\end{theorem}

\paragraph{Discussion.}
The population bound introduces an additional empirical-to-population comparability factor, \(\nu_j\).
When \(\nu_j \lesssim 1\), which holds for many sub-Gaussian or sub-exponential designs once \(n \gtrsim d\), the favorable in-sample transfer guarantee carries over directly to population MSE.
Even when \(\nu_j\) is large, the intrinsic-dimension bound still provides a second safety layer through \(\cE_j(\hat\theta_j^\xi) \lesssim \cE_j^{\mathrm{in}}(\hat\theta_j)+\xi^2U_j^2/n\).
The high-probability norm parameter \(U_j\) is defined precisely in Appendix~\ref{section; detail sample complexity}: it is a tail scale for \(\|x_{ji}\|_2\).
The bounded-domain condition is extra prior information on the parameter scale; it is not needed for the in-sample theorem, but it gives a population fallback when empirical-to-population comparability is unfavorable.
For the linear model, the projection post-processing is only used for this fallback: since it is taken in the same \(\|\cdot\|_{\bSigma_j}\)-norm as the in-sample risk and \(\theta_j^\star\in\mathbf B(0,\xi)\), it does not increase the in-sample prediction error, i.e., \(\cE_j^{\operatorname{in}}(\hat{\theta}_j^\xi)\le \cE_j^{\operatorname{in}}(\hat{\theta}_j)\).
Thus, when prior knowledge of the bounded parameter set \(\Cb\) is available, the projected estimator is automatically no worse for in-sample MSE, while Theorem~\ref{theorem; population MSE} provides an additional safety guarantee for population MSE.
For sub-Gaussian covariates and constant \(\xi\), standard norm concentration gives \(U_j=\tilde{\cO}(\sqrt{d})\), so this term still matches the ITL rate up to logarithmic factors.
Moreover, whenever \(\nu_j\) is moderate, or more generally whenever \(U_j^2 \ll d\) because the design is effectively low-dimensional, the resulting population bound is strictly sharper than ITL.
In this sense, \(\nu_j\) determines when the transfer improvement lifts to population risk, while the \(U_j\)-based bound preserves safety even outside that regime.

% \paragraph{Task-Overall Population MSE.}
% In the task-wise i.i.d. setting, a natural task-overall population prediction metric is
% \[
% \cE(\hat{\theta}_1,\dots,\hat{\theta}_m)
% :=
% \frac{1}{m}\sum_{j=1}^m \cE_j(\hat{\theta}_j).
% \]
% Combining Theorem~\ref{theorem; MSE bound} with Theorem~\ref{theorem; population MSE} shows that, whenever \(\nu_j \lesssim 1\) for the inlier tasks, the same task-overall rate transfers to population risk:
% \[
% \cE(\hat{\theta}_1,\dots,\hat{\theta}_m)
% \lesssim
% \left(\frac{B d}{mn}+\min\left(B\delta^2,\, q^2\frac{d}{n}\right)+q^2B^2\varepsilon^2\frac{d}{n}+\varepsilon q^2\frac{d}{n}\right)\zeta
% \]
% up to logarithmic factors.
% Thus, in favorable regimes with moderate \(B\), the population metric inherits the same \(m,n,\delta,\varepsilon\) dependence as the robust MTL task-overall benchmark of \citet{duan2023adaptive}.
% We do not claim optimal dependence on arbitrary large \(B\); large \(B\) is instead handled by the separate safety guarantee.



\section{Results for Generalized Linear Model}\label{section; GLM}
We now extend the analysis to generalized linear models (GLMs) \citep{van2008high}.
Throughout this section, we keep the balanced-sample-size convention \(n_j = n\).

For each task \(j \in [m]\) and sample \(i \in [n]\), the conditional distribution is given by:
\[
\PP\bigl[y_{ji} \,\bigm|\, x_{ji}\bigr]
= \rho(y_{ji})\exp\bigl(y_{ji} \cdot x_{ji}^\top \theta_j^\star -\psi(x_{ji}^\top \theta_j^\star)\bigr),
\]
where \(\psi\) is a convex function, and we define the link function as \(\psi'(z) = m(z)\).
This implies \(\EE[y_{ji}\mid x_{ji}] = m(x_{ji}^\top \theta_j^\star)\).
We define the stochastic noise as \(\varepsilon_{ji} := y_{ji}- m(x_{ji}^\top \theta_j^\star)\).
We assume that the pairs \((x_{ji},y_{ji})\) for \(i,j \ge 1\) are sampled independently.
We adopt standard GLM assumptions \citep{pmlr-v139-oh21a,tian2025learning} and, for simplicity, take \(\varepsilon_{ji}\) to be $1$-sub-Gaussian.

\begin{assumption}\label{assumption; GLM domain}
We assume that \(\theta_j^\star, \theta^\star \in \mathbf{B}(0, \xi)\) for some constant \(\xi > 0\) known to the learner.
Furthermore, we assume there exists an interval \(\mathcal{I}\subset\RR\) such that for all tasks \(j\), samples \(i\), and parameters \(\theta \in \Cb=\mathbf{B}(0,\xi)\), the linear predictor satisfies \(x_{ji}^\top\theta \in \mathcal{I}\).
On this interval, the link curvature is uniformly bounded:
\[
\alpha_\ell \le m'(z)=\psi''(z)\le \alpha_u,\qquad \forall z\in\mathcal{I},
\]
for universal constants \(\alpha_\ell,\alpha_u>0\).
\end{assumption}

\paragraph{In-Sample and Population MSE.}
Define the GLM in-sample prediction error by
\(\cR_j^{\operatorname{in}}(\theta):=\frac{1}{n} \sum_{i=1}^{n} |m(x_{ji}^\top \theta_j^\star) -m(x_{ji}^\top \theta)|^2\).
As in the linear case, when covariates are task-wise i.i.d.\ (i.e., \(x_{ji}\sim \cP_j\) independently within each task), we also define the population prediction error by
\(\cR_j(\theta):=\EE_{x_{ji} \sim \cP_j} |m(x_{ji}^\top \theta_j^\star) -m(x_{ji}^\top \theta)|^2\).
Under Assumption~\ref{assumption; GLM domain}, the mean value theorem gives
\begin{align*}
\cR^{\operatorname{in}}_j (\hat{\theta}_j)  \lesssim \cE^{\operatorname{in}}_j (\hat{\theta}_j), \quad      \cR^{\operatorname{}}_j (\hat{\theta}_j)  \lesssim \cE^{\operatorname{}}_j (\hat{\theta}_j).
\end{align*}
Thus it suffices to control \( \cE^{\operatorname{in}}_j (\hat{\theta}_j) \) and \(\cE^{\operatorname{}}_j (\hat{\theta}_j)\).

\paragraph{Loss Function and Algorithm for GLM.}
In Algorithm~\ref{algorithm; MTLR}, for the GLM setup, we construct the loss function \(\cL\) using:
\[
f_j(\theta) := \frac{1}{n}\sum_{i=1}^n \Bigl(\psi(x_{ji}^\top \theta) - y_{ji} x_{ji}^\top \theta\Bigr).
\]
We set the domain of the parameter to \( \Cb = \mathbf{B}(0,\xi)\). Apart from these changes, the procedure follows the methodology outlined in Section~\ref{section; methodologies}.


\paragraph{In-Sample MSE Bounds.}\;
The GLM analogue of Theorem~\ref{theorem; MSE bound} is as follows.
Recall that \(\zeta := \log(16m/\kappa)\).

\begin{theorem}[In-sample MSE: GLM]\label{theorem; MSE bound GLM}
Suppose the task relatedness condition (Definition~\ref{definition; task relatedness}) and GLM regularity assumptions (Assumption~\ref{assumption; GLM domain}) hold.
With probability at least $1-\kappa$, the estimator $\hat{\theta}_j$ obtained by Algorithm~\ref{algorithm; MTLR} with $\Cb = \mathbf{B}(0, \xi)$ and $\lambda_j = q\sqrt{d\zeta/n}$ ($q \gtrsim 1$) satisfies the following bounds simultaneously for all $j \in [m]$:

\begin{itemize}
\item \textbf{Safety Guarantee (Universal):} Regardless of the balancedness constant $B$ or the parameters $\varepsilon$ and $\delta$,
\[
\cE_j^{\operatorname{in}}(\hat{\theta}_j) \;\lesssim\; q^2 \frac{d}{n} \zeta.
\]
This matches the known independent-task GLM rate.

\item \textbf{Adaptivity to Relatedness (Inliers):} If Assumption~\ref{assumption; comparability} holds with $B \lesssim \min(1/\varepsilon, m)$, then for all inlier tasks $j \in \Sb$:
\[
\begin{aligned}
\cE_j^{\operatorname{in}}(\hat{\theta}_j)
&\;\lesssim\; \biggl( \frac{B d}{m n}
    + \min\left( B^2\delta^2, \, q^2 \frac{d}{n} \right) 
    + q^2B^2 \varepsilon^2 \frac{d}{n} \biggr) \zeta.
\end{aligned}
\]
\end{itemize}
\end{theorem}
This mirrors the linear-model message: part (a) gives universal safety, while part (b) yields sharper transfer only in the favorable regime.

\paragraph{Population MSE Bounds.}\;
Combining Theorem~\ref{theorem; MSE bound GLM} with Theorem~\ref{theorem; population MSE} yields the corresponding GLM population guarantee: safety when \(B\) is large or infinite, or when \(\nu_j\) is large, and sharper transfer when both are moderate.
For GLMs, the algorithm is already run over the bounded domain \(\Cb=\mathbf B(0,\xi)\), so the intrinsic-dimension comparison in Theorem~\ref{theorem; population MSE} applies directly without any additional post-processing.



\section{Numerical Experiments}\label{section; appendix experiments}

The experiments below are theory-aligned diagnostics for contaminated linear and generalized linear multi-task learning.
Accordingly, we compare against data pooling (DP), independent-task learning (ITL), and ARMUL \citep{duan2023adaptive}.
Code for reproducing the numerical experiments is available at \url{https://github.com/seokjinkim0428/Multi-task-Linear-Regression}.
The synthetic studies vary the quantities appearing in our theory: task relatedness, contamination, eigendecay, and balancedness.
We also include a real-data experiment on the UCI Human Activity Recognition (HAR) dataset to illustrate the same matrix-weighted approach in a multi-task logistic regression setting.

\subsection{Synthetic Data}
We benchmark our method against DP, ITL, and ARMUL. Unless otherwise stated, the synthetic experiments use \(n=100\), \(m=30\), and \(d=30\), and we evaluate population MSE for each task. The covariates \(x_{ji}\) are sampled from the unit sphere and then scaled coordinatewise by \(k^{-\alpha}\), where \(\alpha\) controls eigendecay. For related tasks \(j \in \Sb\), we set \(\theta_j^\star = \theta^\star + \delta \Delta_j\), where \(\Delta_j\) is sampled uniformly from the upper unit sphere; for outlier tasks \(j \in \Sb^c\), we sample \(\theta_j^\star\) from the same upper-hemisphere geometry with Euclidean radius \(r_{\mathrm{out}}=10\). Responses are generated as \(y_{ji} = x_{ji}^\top \theta_j^\star + \varepsilon_{ji}\), with \(\varepsilon_{ji} \sim \cN(0,1)\).

We report MSE separately on all, related, and outlier tasks. For our method and ARMUL, we tune the multiplicative regularization parameter using 5-fold cross-validation over
\[
\mathcal{Q}_{\mathrm{synth}}=\{0.1,0.4,0.7,1.0,2.0,4.0,8.0,16.0\},
\]
and every point averages over 30 Monte Carlo repetitions. DP and ITL do not require hyperparameter tuning.
Throughout this subsection, we use \(\bar{B}\) to denote the population balancedness constant from Remark~\ref{example; bounded second moments}, namely the smallest scalar such that \(\bar\bSigma_j \preceq \bar{B} \bar\bSigma_{\Sb}\) for all inlier tasks \(j \in \Sb\). Our large-balancedness DGP is calibrated directly at this population-covariance level. In Gaussian random-design settings, standard covariance concentration implies that the empirical balancedness constant \(B\) closely tracks \(\bar{B}\) up to small fluctuations, so sweeping \(\bar{B}\) is a natural proxy for sweeping \(B\).

\paragraph{Sweep of Task Relatedness \(\delta\).}
We vary \(\delta \in \{0.2,0.4,0.8,1.6,3.2\}\) while keeping \(\varepsilon=0.1\), \(\alpha=1\), and the covariance geometry shared across tasks, so \(\bar{B}=1\). Across this favorable-transfer regime, our estimator consistently attains the smallest all-task MSE and the clearest gains on related tasks. Its all-task MSE ranges from \(0.0138\) to \(0.0259\), while the best competing baseline remains above \(0.041\). On related tasks, our method remains well below the transfer baselines, with errors between \(0.0022\) and \(0.0136\). As expected, the outlier-only split is not where transfer helps most, and ITL remains competitive there.

\begin{figure}[H]
\centering
\includegraphics[width=\textwidth]{Images/synthetic_delta_panels.png}
\caption{Synthetic sweep over the inlier radius \(\delta\). Rows show all-task, related-task, and outlier-task MSE.}
\label{figure; synthetic delta sweep}
\end{figure}

\paragraph{Sweep of Outlier Fraction \(\varepsilon\).}
We next vary \(\varepsilon \in \{0.05,0.1,0.2,0.3,0.4\}\), again under \(\bar{B}=1\). This directly isolates contamination while preserving favorable covariance alignment. Our method remains best on all-task MSE throughout the sweep and preserves a large advantage on related tasks even as the fraction of arbitrary outliers increases. The all-task error increases smoothly from \(0.0062\) to \(0.0460\), rather than showing an abrupt failure mode. On the outlier-only split, ITL is typically the strongest baseline, which is natural because those tasks are deliberately unrelated.

\begin{figure}[H]
\centering
\includegraphics[width=\textwidth]{Images/synthetic_epsilon_panels.png}
\caption{Synthetic sweep over the outlier fraction \(\varepsilon\). Rows show all-task, related-task, and outlier-task MSE.}
\label{figure; synthetic epsilon sweep}
\end{figure}

\paragraph{Sweep of Eigendecay \(\alpha\).}
To stress the spectral assumptions directly, we keep \(\bar{B}=1\) and vary the eigendecay exponent over
\[
\alpha\in\{0,0.5,1.0,1.5,2.0\}.
\]
This experiment is the cleanest demonstration that our method does not require a uniform eigenvalue lower bound. Even when the spectrum decays sharply, our estimator continues to dominate on all-task and related-task error. In particular, the gap is already substantial at \(\alpha=0\), and it remains visible through the rapidly decaying cases \(\alpha=1.5\) and \(2.0\).

\begin{figure}[H]
\centering
\includegraphics[width=\textwidth]{Images/synthetic_decay_alpha_panels.png}
\caption{Synthetic sweep over the eigendecay exponent \(\alpha\). Rows show all-task, related-task, and outlier-task MSE.}
\label{figure; synthetic decay sweep}
\end{figure}

\paragraph{Sweep of Population Balancedness \(\bar{B}\).}
Our large-\(\bar{B}\) stress test uses a different DGP. For this section only, we set \(m=50\), \(\varepsilon=0.5\), and \(\delta=0.5\). We first sample the outlier set uniformly at random. The remaining tasks are inliers, and their covariances are assigned from a two-group spiked family:
\[
\bSigma_j = \eta \Ib + (1-\eta)e_{g(j)}e_{g(j)}^\top.
\]
Here \(e_1,e_2\) are two coordinate directions and \(g(j)\in\{1,2\}\) records the spike group assigned to task \(j\). We sweep target values \(W\in\{5,10,15,20\}\), where \(W\) is the desired population balancedness level \(\bar B\). Given \(W\), let \(r=\lfloor |\Sb|/W\rfloor\) and \(p=r/|\Sb|\). Conditional on the random inlier set, we select \(r\) inlier tasks uniformly without replacement and set \(g(j)=2\) for these minority-spike tasks; all remaining inlier tasks have \(g(j)=1\).
Outlier tasks also use the majority-spike covariance \(g(j)=1\), but their regression parameters are sampled independently from the same outlier construction as above, with Euclidean radius \(r_{\mathrm{out}}=10\).
We choose
\[
\eta=\frac{1/W-p}{1-p},
\]
clipped to \([0,1]\). This choice calibrates the inlier average covariance along the minority spike direction. Indeed, along direction \(e_2\), a minority task has variance \(1\), while the inlier average has variance \(p+(1-p)\eta\). Therefore the one-sided comparison ratio for a minority-spike task is
\[
\frac{1}{p+(1-p)\eta}=W,
\]
up to the integer rounding in \(r\). Thus the population balancedness constant is calibrated to \(\bar B\approx W\). Since the design is Gaussian, standard covariance concentration implies that the empirical balancedness constant \(B\) is close to this population value \(\bar B\) once \(n\gtrsim d\), up to logarithmic factors.

The resulting pattern is especially informative. When \(\bar{B}=5\), our estimator is the best overall, with all-task MSE \(0.0074\). As \(\bar{B}\) increases, ITL becomes the best method on all-task error, which is precisely the regime where aggressive transfer should lose its advantage. In this large-\(\bar{B}\), high-contamination regime, our method tracks the ITL baseline closely and does not exhibit catastrophic negative transfer. Because this experiment uses the severe contamination level \(\varepsilon=0.5\), we view the all-task curve as the primary diagnostic; the related-task split is less informative here than in the earlier sweeps.
We do not expect the errors to vary monotonically with \(\bar B\), since changing \(\bar B\) changes the underlying spiked-covariance mixture rather than merely increasing a single scalar difficulty parameter.

\begin{figure}[H]
\centering
\includegraphics[width=\textwidth]{Images/synthetic_bar_b_target_panels.png}
\caption{Large-\(\bar{B}\) synthetic stress test based on common-operator-norm spiked covariances. Rows show all-task, related-task, and outlier-task MSE.}
\label{figure; synthetic bar b sweep}
\end{figure}

\paragraph{Rank-Deficient Stress.}
This same sweep also probes the rank-deficient regime.
The calibrated floor \(\eta\) is zero at the \(\bar{B}=5\) endpoint, so the inlier covariance matrices are singular rank-one spiked covariances; at the remaining sweep values the floor is small, giving near-singular designs.
Thus the experiment tests both large-balancedness behavior and the singular/near-singular covariance regime that violates a uniform eigenvalue lower bound.


\subsection{Real-World Data}
We evaluated the performance of our proposed algorithm against various baselines using the HAR dataset \citep{anguita2013public}. This dataset comprises motion data collected from 30 participants wearing waist-mounted smartphones equipped with inertial sensors. The dataset covers six distinct daily activities: walking, walking upstairs, walking downstairs, sitting, standing, and laying. The subject-level sample sizes range from 281 to 409 observations, with an average of about 343 observations per volunteer. Each data point is represented by a 561-dimensional feature vector, capturing characteristics in both the time and frequency domains.

Following \citet{duan2023adaptive}, we formulated the problem as a multi-task logistic regression with \(m=30\) tasks (one task per volunteer). Unlike their HAR experiment, which distinguished \texttt{sitting} from the other activities, we instead used the label \(y=1\) for \texttt{standing} and \(y=0\) for all other activities. We randomly selected \(20\%\) of the data from each task for testing and trained logistic models on the remaining data.
We intentionally do not apply PCA.
The purpose of our method is precisely to remain stable when some covariate directions have small empirical variance, so discarding low-variance directions is not necessary for numerical stability and may remove useful information.
This means that the HAR numbers below should be read as a theory-aligned real-data illustration, not as a direct reproduction of the HAR table in \citet{duan2023adaptive}, whose label construction and PCA preprocessing differ from ours.

We compared our method with ARMUL, DP, and ITL, utilizing the logistic regression loss for all methods. For our method and ARMUL, we tuned the regularization parameter \(q\)—the multiplicative factor in \(\lambda_j = q \frac{\sqrt{d}}{\sqrt{n_j}}\)—using 5-fold cross-validation over the grid \(q \in \{0.05, 0.10, 0.15, \dots, 0.50\}\). We repeated the experiment over \(30\) independent random splits. As shown in Table~\ref{table; real-world results}, our method strictly outperformed DP, ITL, and ARMUL.

\begin{table}[H]
\centering
\caption{Results for the real-world data experiment. Comparison of classification error rates (percentage). Standard deviations are reported in parentheses.}
\label{table; real-world results}
\vspace{0.2cm}
\begin{tabular}{lc}
\toprule
Method & Mean Error (SD) \\
\midrule
\textbf{Ours} & 1.25 (0.32) \\
DP & 7.61 (0.46)\\
ITL & 4.67 (0.51) \\
ARMUL \citep{duan2023adaptive} & 5.24 (0.43) \\
\bottomrule
\end{tabular}
\end{table}
As a diagnostic, the empirical balancedness constant on the raw HAR subject tasks is about \(B_{\text{emp}} \approx 30\): not a trivial \({B}\approx 1\) regime, but also far from a completely degenerate transfer geometry.
Thus, the HAR experiment is not in a \(B=\mathcal{O}(1)\) regime; rather, it illustrates that the proposed matrix-weighted procedure can remain empirically effective even when both the ambient dimension and the balancedness diagnostic are large.
One plausible interpretation is that DP is vulnerable to subject heterogeneity because it forces all participants to share a single parameter, while ARMUL is disadvantaged by the failure of LBSM in this high-dimensional setting.
The improvement over ITL suggests that balancedness is mainly a sufficient condition for our sharp theory: even when \(B_{\text{emp}}\) is large, matrix-weighted regularization can still exploit useful shared structure while remaining stable.


\section{Conclusion}


In this paper, we have established an efficient multi-task linear regression framework that operates under strictly relaxed assumptions on the covariate spectrum.
By introducing a matrix-weighted regularization scheme, we recover the \(m,n,\delta,\varepsilon\) prediction-MSE rates of \citet{duan2023adaptive} under substantially weaker spectral assumptions.
In the favorable balanced regime, the resulting task-overall MSE is minimax optimal up to logarithmic and balancedness-dependent factors.
Crucially, our estimator provides a \emph{safety guarantee}: it performs robustly when tasks are related and the balancedness constant \(B\) is moderate, yet gracefully degrades to the independent-task rate when \(B\) is large or infinite.

Promising directions for future research include investigating the tightness of the dependence on the balancedness constant \(B\) and extending this geometric framework to infinite-dimensional settings such as reproducing kernel Hilbert spaces (RKHS) and overparameterized neural-network regimes, including neural tangent kernel limits.

\section*{Acknowledgments}
We thank the reviewers for their thoughtful and constructive feedback, which helped improve the presentation of this work. We are also grateful to Kaizheng Wang for helpful discussions.


\newpage
\bibliography{ref}

\newpage
\appendix


\clearpage
\newpage
\begin{center}
\textbf{{\Huge Supplementary Materials}}
\end{center}
\vspace{0.5cm}
\etocdepthtag.toc{mtappendix}
\etocsettagdepth{mtchapter}{none}
\etocsettagdepth{mtappendix}{subsection}
\tableofcontents


\crefalias{section}{appendix} % uncomment if you are using cleveref

\newpage



\section{Loss Geometry}\label{section; loss geometry}

The next results isolate the single-task \(n\)-sample geometry that underlies our multi-task analysis.
Unlike the main contaminated multi-task setup, every statement in this section concerns a single regression problem with empirical second moment \(\bSigma\) and the matrix-weighted infimal convolution \(f \star \lambda \|\cdot\|_{\bSigma}\).
We separate the linear and GLM cases because the domain and curvature assumptions differ. 
For a loss \(f\), feasible set \(\Cb\), and seminorm \(\|\cdot\|_{\bSigma}\), we use the convention
\[
(f \star \lambda\|\cdot\|_{\bSigma})(\beta)
:=
\inf_{\theta\in\Cb}\left\{f(\theta)+\lambda\|\theta-\beta\|_{\bSigma}\right\}.
\]
This definition is used in both the linear and GLM arguments below.
In the linear case we take \(\Cb=\RR^d\), so the constraint is omitted; in the GLM case we take \(\Cb=\mathbf B(0,\xi)\).

\subsection{Linear Regression}

We first consider a single fixed-design linear regression problem with \(n\) samples \(\{(x_i,y_i)\}_{i=1}^n\), model
\[
y_i = x_i^\top \theta^\star + \varepsilon_i,
\]
design matrix \(\Xb \in \RR^{n\times d}\), response vector \(\Yb \in \RR^n\), empirical second moment \(\bSigma := \frac{1}{n}\Xb^\top \Xb\), and squared loss
\[
f(\theta) := \frac{1}{2n}\|\Yb - \Xb\theta\|_2^2,
\qquad
g(\beta) := (f \star \lambda\|\cdot\|_{\bSigma})(\beta).
\]
The first ingredient identifies a regime where the regularized task objective agrees with the original loss and a complementary safety bound showing that regularization cannot hurt by more than the single-task rate.

\paragraph{Whitened Notation.}
When \(\bSigma\) is full-rank, we define the whitened design matrix by
\[
\tilde{\Xb}:=\Xb\bSigma^{-1/2},
\]
and, for any vector \(v\in\RR^d\), we define its whitened image by
\[
\bar v := \bSigma^{1/2}v.
\]
For any function \(h:\RR^d\to\RR\), we define its whitened version by
\[
\bar h(\bar v) := h(\bSigma^{-1/2}\bar v).
\]
Thus \(\bar\theta\), \(\bar\beta\), \(\bar\theta^\star\), \(\bar{\hat\theta}\), and \(\bar{\tilde\theta}\) are all instances of the same map \(v\mapsto \bar v\). In particular, the transformed loss is
\[
\bar{f}(\bar v) := f(\bSigma^{-1/2}\bar v)
= \frac{1}{2n}\|\Yb-\tilde{\Xb}\bar v\|_2^2.
\]
When \(\bSigma\) is rank-deficient, the barred notation is interpreted in the projected row space in the rank-deficient case below.

\begin{proposition}[Infimal Convolution Invariant Region: Linear]\label{proposition; invariant region linear}
If the regularization parameter satisfies
\[
\lambda > \|\theta^\star - \beta \|_{\bSigma} + c_0 \frac{\sqrt{d\log (1/\kappa)}}{\sqrt{n}},
\]
then with probability at least $1-\kappa$, we have $f(\beta) = g(\beta)$.
Furthermore, any minimizer $\beta'$ of the objective $f(\theta) + \lambda \|\theta - \beta\|_{\bSigma}$ satisfies $\|\beta' - \beta \|_{\bSigma} = 0$.
\end{proposition}

\begin{proof}
We first prove the result for the case where $\bSigma$ is full-rank, and then extend it to the general case.

\paragraph{Case 1: Full-Rank $\bSigma$.}
Note that $\frac{1}{n}\tilde{\Xb}^\top \tilde{\Xb} = \Ib_d$.
The optimization problem can be rewritten in the transformed space as:
\begin{align*}
\min_{\theta} \left( \frac{1}{2n} \|\Yb -\Xb \theta \|_2^2 + \lambda \|\theta -\beta \|_{\bSigma} \right)
&= \min_{\bar{\theta}} \left( \frac{1}{2n} \|\Yb -\tilde{\Xb}\bar{\theta} \|_2^2 + \lambda \| \bar{\theta} - \bar{\beta} \|_2 \right).
\end{align*}
By the first-order optimality condition for the $\ell_2$-regularized problem (or Lemma~\ref{lemma; ARMUL invariant region}), the minimizer is exactly $\bar{\beta}$ if $\lambda > \|\nabla \bar{f}(\bar{\beta}) \|_2$.

We calculate the gradient norm at $\bar{\beta}$:
\begin{align*}
\|\nabla \bar{f}(\bar{\beta}) \|_2
&= \left\| \frac{1}{n}\tilde{\Xb}^\top (\tilde{\Xb} \bar{\beta} - \Yb) \right\|_2 \\
&= \left\| \frac{1}{n}\tilde{\Xb}^\top (\tilde{\Xb} \bar{\beta} - \tilde{\Xb} \bar{\theta}^\star - \bm{\varepsilon}) \right\|_2 \\
&\leq \left\| \frac{1}{n}\tilde{\Xb}^\top \tilde{\Xb} (\bar{\beta} - \bar{\theta}^\star) \right\|_2 + \left\| \frac{1}{n}\tilde{\Xb}^\top \bm{\varepsilon} \right\|_2 \\
&= \|\bar{\beta} - \bar{\theta}^\star\|_2 + \left\| \frac{1}{n}\tilde{\Xb}^\top \bm{\varepsilon} \right\|_2.
\end{align*}
The first term equals $\|\beta - \theta^\star\|_{\bSigma}$.
For the second term, since the rows of $\tilde{\Xb}$ are isotropic, the Hanson-Wright inequality (Lemma~\ref{lemma; hanson wright inequality}) implies that with probability at least $1-\kappa$:
\[
\left\| \frac{1}{n}\tilde{\Xb}^\top \bm{\varepsilon} \right\|_2 \le c_0 \frac{\sqrt{d \log(1/\kappa)}}{\sqrt{n}}.
\]
Thus, the condition on $\lambda$ ensures $\bar{\beta}$ is the minimizer, implying $\beta$ minimizes the original objective.

\paragraph{Case 2: Rank-Deficient $\bSigma$.}
Let \(\mathcal R:=\mathrm{Range}(\bSigma)=\mathrm{row}(\Xb)\), and let \(\Pb\) be the orthogonal projection onto \(\mathcal R\).
Since \(\mathrm{Null}(\bSigma)=\mathrm{Null}(\Xb)\), for every \(v\in\RR^d\),
\[
\Xb v=\Xb\Pb v,
\qquad
\|v\|_{\bSigma}=\|\Pb v\|_{\bSigma}.
\]
Hence both the loss and the penalty in the linear objective depend on \(\theta\) only through \(\Pb\theta\), with \(\beta\) entering only through \(\Pb\beta\):
\[
f(\theta)=f(\Pb\theta),
\qquad
\|\theta-\beta\|_{\bSigma}=\|\Pb\theta-\Pb\beta\|_{\bSigma}.
\]
Because the linear case is unconstrained, the original problem is exactly equivalent to the reduced problem over \(u\in\mathcal R\),
\[
\min_{u\in\mathcal R}\left\{f(u)+\lambda\|u-\Pb\beta\|_{\bSigma}\right\}.
\]
On \(\mathcal R\), the restricted operator \(\bSigma|_{\mathcal R}\) is positive definite, so Case 1 applies to the reduced \(r=\rank(\bSigma)\)-dimensional problem with projected parameters \(\Pb\theta^\star\) and \(\Pb\beta\).
The stochastic term is of order \(\sqrt{r/n}\), which is bounded by the displayed \(\sqrt{d/n}\) term.
Since \(\|\Pb\beta-\Pb\theta^\star\|_{\bSigma}=\|\beta-\theta^\star\|_{\bSigma}\), the assumed lower bound on \(\lambda\) implies that \(\Pb\beta\) is a minimizer of the reduced problem.
Therefore \(g(\beta)=f(\beta)\).
Moreover, if \(\beta'\) is any minimizer of the original objective, then \(\Pb\beta'\) is a minimizer of the reduced problem, so \(\|\Pb\beta'-\Pb\beta\|_{\bSigma}=0\).
Equivalently, \(\|\beta'-\beta\|_{\bSigma}=0\).
\end{proof}

\begin{proposition}[Personalization: Linear]\label{proposition; personalization}
With probability at least $1-\kappa$, the following holds uniformly over all \(\beta\in\RR^d\): for every minimizer \(\hat{\theta}(\beta)\) of \(f(\theta) + \lambda \|\theta-\beta \|_{\bSigma}\),
\begin{align*}
\|\hat{\theta}(\beta) - \theta^\star \|_{\bSigma} \leq \lambda + c_0 \sqrt{\frac{d}{n}\log\left(\frac{1}{\kappa}\right)}.
\end{align*}
\end{proposition}

\begin{proof}
If \(\bSigma\) is rank-deficient, let \(\mathcal R:=\mathrm{Range}(\bSigma)=\mathrm{row}(\Xb)\) and let \(\Pb\) be the orthogonal projection onto \(\mathcal R\).
As in the previous proposition, \(f(\theta)=f(\Pb\theta)\) and \(\|\theta-\beta\|_{\bSigma}=\|\Pb\theta-\Pb\beta\|_{\bSigma}\).
Thus the unconstrained problem reduces exactly to \(\mathcal R\), where \(\bSigma|_{\mathcal R}\) is positive definite; the stochastic bound on this \(r=\rank(\bSigma)\)-dimensional space is no larger than the displayed \(\sqrt d\) bound.
It therefore suffices to prove the result on the working subspace, and we write the proof as if \(\bSigma\) were full-rank.

Fix an arbitrary \(\beta\in\RR^d\), and let \(\hat{\theta}=\hat{\theta}(\beta)\).
Let \(\tilde{\theta}\) be the minimizer of \(f(\theta)\) (OLS).
The estimators in the transformed space, $\bar{\hat{\theta}} := \bSigma^{1/2}\hat{\theta}$ and $\bar{\tilde{\theta}} := \bSigma^{1/2}\tilde{\theta}$, are the minimizers of
\begin{align*}
\min_{\bar{\theta}} \left( \bar{f}(\bar{\theta}) + \lambda \|\bar{\theta} - \bar{\beta}\|_2 \right) \quad \text{and} \quad \min_{\bar{\theta}} \bar{f}(\bar{\theta}),
\end{align*}
respectively.

\paragraph{Step 1: Perturbation via Regularization.}
Since $\nabla^2 \bar{f}(\bar{\theta}) = \Ib_d$, the function $\bar{f}$ is 1-strongly convex.
The regularization term $h(\bar{\theta}) := \lambda \|\bar{\theta} - \bar{\beta}\|_2$ is convex and $\lambda$-Lipschitz with respect to $\|\cdot\|_2$.
By Lemma~\ref{lemma; ARMUL effect outlier},
\[
\|\bar{\hat{\theta}} - \bar{\tilde{\theta}}\|_2 \leq \lambda,
\]
which is equivalent to $\|\hat{\theta} - \tilde{\theta}\|_{\bSigma} \leq \lambda$.

\paragraph{Step 2: OLS Estimation Error.}
The unregularized estimator $\tilde{\theta}$ is the OLS solution, and
\begin{align*}
\|\bar{\tilde{\theta}} - \bar{\theta}^\star\|_2
&\le \|\nabla \bar{f}(\bar{\theta}^\star)\|_2
= \left\| \frac{1}{n} \sum_{i=1}^n \varepsilon_i \tilde{x}_i \right\|_2,
\end{align*}
where $\tilde{x}_i = \bSigma^{-1/2}x_i$ are isotropic.
Applying the Hanson-Wright inequality (Lemma~\ref{lemma; hanson wright inequality}), with probability at least $1-\kappa$:
\[
\|\bar{\tilde{\theta}} - \bar{\theta}^\star\|_2 \leq c_0 \sqrt{\frac{d}{n}\log\left(\frac{1}{\kappa}\right)}.
\]
This is equivalent to $\|\tilde{\theta} - \theta^\star\|_{\bSigma} \le c_0 \sqrt{\frac{d}{n}\log(\frac{1}{\kappa})}$.

\paragraph{Conclusion.}
Combining the two bounds yields
\begin{align*}
\|\hat{\theta} - \theta^\star\|_{\bSigma}
&\le \|\hat{\theta} - \tilde{\theta}\|_{\bSigma} + \|\tilde{\theta} - \theta^\star\|_{\bSigma} \\
&\le \lambda + c_0 \sqrt{\frac{d}{n}\log\left(\frac{1}{\kappa}\right)}.
\end{align*}
The only random event used above is the OLS noise event in Step 2, which does not depend on \(\beta\). Hence the bound holds simultaneously for every \(\beta\) and every corresponding minimizer \(\hat{\theta}(\beta)\).
\end{proof}

\subsection{Generalized Linear Models}\label{section; loss properties}

We next consider a single fixed-design GLM with \(n\) samples \(\{(x_i,y_i)\}_{i=1}^n\), empirical second moment
\[
\bSigma := \frac{1}{n}\sum_{i=1}^n x_i x_i^\top,
\]
parameter domain \(\Cb = \mathbf{B}(0,\xi)\) from Assumption~\ref{assumption; GLM domain}, negative log-likelihood
\[
f(\theta) := \frac{1}{n}\sum_{i=1}^n \bigl(-y_{i}x_{i}^\top \theta + \psi(x_{i}^\top \theta)\bigr),
\qquad
g(\beta) := (f \star \lambda\|\cdot\|_{\bSigma})(\beta),
\]
and again study the corresponding matrix-weighted infimal convolution on this single-task \(n\)-sample problem.

\paragraph{Whitened Notation.}
When \(\bSigma\) is full-rank, define the whitened covariates by
\begin{align*}
\tilde{x}_i &:= \bSigma^{-1/2}x_i,
\end{align*}
for any vector \(v\in\RR^d\), define its whitened image by
\[
\bar v := \bSigma^{1/2}v,
\]
and define the transformed domain by
\[
\bar{\Cb} := \{\bar v : v\in\Cb\}.
\]
For any function \(h:\RR^d\to\RR\), define its whitened version by
\[
\bar h(\bar v) := h(\bSigma^{-1/2}\bar v).
\]
Thus \(\bar\theta\), \(\bar\beta\), \(\bar\theta^\star\), \(\bar{\hat\theta}\), and \(\bar{\tilde\theta}\) are all instances of the same map \(v\mapsto \bar v\). In particular, the transformed loss is
\[
\bar{f}(\bar v)
:=
f(\bSigma^{-1/2}\bar v)
=
\frac{1}{n}\sum_{i=1}^n \left( -y_{i}\tilde{x}_{i}^\top \bar v + \psi(\tilde{x}_{i}^\top \bar v) \right).
\]
When \(\bSigma\) is rank-deficient, the barred notation is interpreted on the projected row space, with the projected feasible set described in the proof below.

\begin{proposition}[Infimal Convolution Invariant Region: GLM]\label{proposition; invariant region GLM}
If \(\beta\in\Cb\) and $\lambda > \alpha_u \|\beta-\theta^\star \|_{\bSigma} + c_0 \frac{\sqrt{d \log(1/\kappa)}}{\sqrt{n}}$, then with probability at least $1-\kappa$,
\[
\beta \in \mathop{\arg \min}_{\theta \in \Cb} \left( f(\theta) + \lambda \|\theta -\beta \|_{\bSigma} \right).
\]
Consequently, $f(\beta) = (f \star \lambda\|\cdot\|_{\bSigma})(\beta)$.
Furthermore, any minimizer $\beta'$ satisfies $\|\beta' - \beta\|_{\bSigma} = 0$.
\end{proposition}

\begin{proof}
We first consider the case where $\bSigma$ is full-rank.
The original optimization problem is equivalent to the transformed problem:
\begin{align*}
\beta \in \mathop{\arg \min}_{\theta \in \Cb} \left( f(\theta) + \lambda \|\theta -\beta \|_{\bSigma} \right)
\iff
\bar{\beta} \in \mathop{\arg \min}_{\bar{\theta} \in \bar{\Cb}} \left( \bar{f}(\bar{\theta}) + \lambda \|\bar{\theta} -\bar{\beta} \|_{2} \right).
\end{align*}
Since $\bar{f}$ is convex on $\bar{\Cb}$ and \(\bar\beta\in\bar{\Cb}\), by Lemma~\ref{lemma; ARMUL invariant region constrained}, it suffices to show that $\|\nabla \bar{f}(\bar{\beta})\|_2 < \lambda$.

We compute the gradient $\nabla \bar{f}(\bar{\beta})$:
\begin{align*}
\nabla \bar{f}(\bar{\beta})
&= \frac{1}{n}\sum_{i=1}^n \left( -y_i \tilde{x}_i + \psi'(\tilde{x}_i^\top \bar{\beta})\tilde{x}_i \right).
\end{align*}
Substituting the model equation $y_i = \psi'(\tilde{x}_i^\top \bar{\theta}^\star) + \varepsilon_i$, we decompose the gradient into a noise term and a bias term:
\begin{align*}
\nabla \bar{f}(\bar{\beta})
&= -\frac{1}{n}\sum_{i=1}^n \varepsilon_i \tilde{x}_i + \frac{1}{n}\sum_{i=1}^n \left( \psi'(\tilde{x}_i^\top \bar{\beta}) - \psi'(\tilde{x}_i^\top \bar{\theta}^\star) \right) \tilde{x}_i.
\end{align*}
By the Mean Value Theorem, there exists $\xi_i$ between $\tilde{x}_i^\top \bar{\beta}$ and $\tilde{x}_i^\top \bar{\theta}^\star$ such that:
\[
\psi'(\tilde{x}_i^\top \bar{\beta}) - \psi'(\tilde{x}_i^\top \bar{\theta}^\star) = \psi''(\xi_i) \tilde{x}_i^\top (\bar{\beta} - \bar{\theta}^\star).
\]
Substituting this back, we obtain:
\begin{align*}
\nabla \bar{f}(\bar{\beta})
&= -\frac{1}{n}\sum_{i=1}^n \varepsilon_i \tilde{x}_i + \left( \frac{1}{n}\sum_{i=1}^n \psi''(\xi_i) \tilde{x}_i \tilde{x}_i^\top \right) (\bar{\beta} - \bar{\theta}^\star).
\end{align*}
Let $\tilde{\Qb} := \frac{1}{n}\sum_{i=1}^n \psi''(\xi_i) \tilde{x}_i \tilde{x}_i^\top$.
Under Assumption~\ref{assumption; GLM domain}, we have $\psi''(\cdot) \in [\alpha_\ell, \alpha_u]$.
Since $\frac{1}{n}\sum_{i=1}^n \tilde{x}_i \tilde{x}_i^\top = \Ib_d$, the matrix $\tilde{\Qb}$ satisfies:
\[
\alpha_\ell \Ib_d \preceq \tilde{\Qb} \preceq \alpha_u \Ib_d \implies \|\tilde{\Qb}\|_{\operatorname{op}} \le \alpha_u.
\]

We now bound the norm of the gradient. Using the triangle inequality:
\begin{align*}
\|\nabla \bar{f}(\bar{\beta})\|_2
&\leq \left\| \frac{1}{n}\sum_{i=1}^n \varepsilon_i \tilde{x}_i \right\|_2 + \|\tilde{\Qb}\|_{\operatorname{op}} \|\bar{\beta} - \bar{\theta}^\star\|_2 \\
&\leq \left\| \frac{1}{n}\sum_{i=1}^n \varepsilon_i \tilde{x}_i \right\|_2 + \alpha_u \|\beta - \theta^\star\|_{\bSigma}.
\end{align*}
Since the whitened covariates $\tilde{x}_i$ are isotropic, we apply the Hanson-Wright inequality (Lemma~\ref{lemma; hanson wright inequality}).
With probability at least $1-\kappa$:
\[
\left\| \frac{1}{n}\sum_{i=1}^n \varepsilon_i \tilde{x}_i \right\|_2 \leq c_0 \frac{\sqrt{d \log(1/\kappa)}}{\sqrt{n}}.
\]
Thus, provided that $\lambda > \alpha_u \|\beta - \theta^\star\|_{\bSigma} + c_0 \frac{\sqrt{d \log(1/\kappa)}}{\sqrt{n}}$, the condition $\|\nabla \bar{f}(\bar{\beta})\|_2 < \lambda$ holds, implying $\beta$ is a minimizer over \(\Cb\).

For the case where $\bSigma$ is rank-deficient, let \(\mathcal R:=\mathrm{Range}(\bSigma)=\mathrm{row}(\Xb)\), and let \(\Pb\) be the orthogonal projection onto \(\mathcal R\).
As above, \(\mathrm{Null}(\bSigma)=\mathrm{Null}(\Xb)\), so the GLM linear predictors and the seminorm are unchanged by projection:
\[
x_i^\top\theta=x_i^\top\Pb\theta,
\qquad
\|\theta-\beta\|_{\bSigma}
=
\|\Pb\theta-\Pb\beta\|_{\bSigma}.
\]
The constrained domain causes no further difficulty.
Here \(\Cb=\mathbf B(0,\xi)\), and orthogonal projections are contractions; hence
\[
\Pb\Cb=\Cb\cap\mathcal R\subseteq\Cb.
\]
Thus replacing any feasible \(\theta\) by \(\Pb\theta\) preserves all GLM linear predictors and the \(\bSigma\)-seminorm penalty while keeping the parameter feasible.
The original constrained problem is therefore equivalent, in objective value and minimizer projections, to the reduced problem over \(u\in\Pb\Cb=\Cb\cap\mathcal R\), with \(\beta\) and \(\theta^\star\) replaced by \(\Pb\beta\) and \(\Pb\theta^\star\).
Because the reduced feasible set remains inside \(\Cb\), the curvature condition in Assumption~\ref{assumption; GLM domain} is valid throughout the reduced problem.
On \(\mathcal R\), the restricted operator \(\bSigma|_{\mathcal R}\) is positive definite, so the full-rank argument applies in dimension \(r=\rank(\bSigma)\), with the stochastic \(\sqrt r\) term bounded by the displayed \(\sqrt d\) term.
Since \(\|\Pb\beta-\Pb\theta^\star\|_{\bSigma}=\|\beta-\theta^\star\|_{\bSigma}\), the same lower bound on \(\lambda\) implies that \(\Pb\beta\) minimizes the reduced problem.
Equivalently, \(\beta\) is a minimizer of the original constrained problem, and any minimizer \(\beta'\) satisfies \(\|\Pb\beta'-\Pb\beta\|_{\bSigma}=0\), i.e., \(\|\beta'-\beta\|_{\bSigma}=0\).
\end{proof}

\begin{lemma}[Strong Convexity and Growth Condition: GLM]\label{lemma; PL GLM}
Suppose \(\bSigma\) is full-rank, and let $\bar{f}$ be the transformed loss defined in Proposition~\ref{proposition; invariant region GLM} on the domain $\bar{\Cb}$.
The function $\bar{f}$ is $\alpha_\ell$-strongly convex.
Consequently, let $\bar{\tilde{\theta}}$ be the minimizer of $\bar{f}$ over the convex set $\bar{\Cb}$. Then for any $\bar{\theta} \in \bar{\Cb}$:
\[
\bar{f}(\bar{\theta}) \ge \bar{f}(\bar{\tilde{\theta}}) + \frac{\alpha_\ell}{2} \|\bar{\theta} - \bar{\tilde{\theta}}\|_2^2.
\]
\end{lemma}

\begin{proof}
First, we establish the uniform lower bound on the Hessian.
The Hessian of the transformed loss is given by:
\[
\nabla^2 \bar{f}(\bar{\theta}) = \frac{1}{n}\sum_{i=1}^n \psi''(\tilde{x}_i^\top \bar{\theta}) \tilde{x}_i \tilde{x}_i^\top.
\]
Under Assumption~\ref{assumption; GLM domain}, the second derivative of the cumulant generating function satisfies $\psi''(z) \ge \alpha_\ell$ for all $z$ in the domain.
Additionally, by the construction of the whitened covariates $\tilde{x}_i = \bSigma^{-1/2}x_i$, the empirical covariance is isotropic:
\[
\frac{1}{n}\sum_{i=1}^n \tilde{x}_i \tilde{x}_i^\top = \bSigma^{-1/2} \left( \frac{1}{n}\sum_{i=1}^n x_i x_i^\top \right) \bSigma^{-1/2} = \bSigma^{-1/2} \bSigma \bSigma^{-1/2} = \Ib_d.
\]
This implies $\nabla^2 \bar{f}(\bar{\theta}) \succeq \alpha_\ell \Ib_d$ for all $\bar{\theta} \in \bar{\Cb}$, establishing $\alpha_\ell$-strong convexity.

Now, applying the definition of strong convexity at the minimizer $\bar{\tilde{\theta}}$:
\[
\bar{f}(\bar{\theta}) \ge \bar{f}(\bar{\tilde{\theta}}) + \nabla \bar{f}(\bar{\tilde{\theta}})^\top (\bar{\theta} - \bar{\tilde{\theta}}) + \frac{\alpha_\ell}{2}\|\bar{\theta} - \bar{\tilde{\theta}}\|_2^2.
\]
Since $\bar{\Cb}$ is a convex set and $\bar{\tilde{\theta}}$ is the minimizer over $\bar{\Cb}$, the first-order optimality condition states that $\langle \nabla \bar{f}(\bar{\tilde{\theta}}), \bar{\theta} - \bar{\tilde{\theta}} \rangle \ge 0$ for all $\bar{\theta} \in \bar{\Cb}$.
Dropping the non-negative linear term yields the desired result:
\[
\bar{f}(\bar{\theta}) \ge \bar{f}(\bar{\tilde{\theta}}) + \frac{\alpha_\ell}{2}\|\bar{\theta} - \bar{\tilde{\theta}}\|_2^2.
\]
\end{proof}

\begin{proposition}[Personalization: GLM] \label{proposition: personalization glm}
Let $\hat{\theta}$ be a minimizer of
\[
\min_{\theta \in \Cb} \left\{ f(\theta) + \lambda \|\theta-\beta \|_{\bSigma} \right\},
\]
and let $\tilde{\theta}$ be the minimizer of the unregularized loss $f(\theta)$.
Then for any $\lambda > 0$, we have:
\[
\|\hat{\theta} - \tilde{\theta} \|_{\bSigma} \leq \frac{2\lambda}{\alpha_\ell}.
\]
Consequently, with probability at least $1-\kappa$:
\[
\|\hat{\theta} - \theta^\star \|_{\bSigma} \leq \frac{2\lambda}{\alpha_\ell} + \frac{c_0}{\alpha_\ell} \sqrt{\frac{d \log(2/\kappa)}{n}}.
\]
\end{proposition}

\begin{proof}
If \(\bSigma\) is rank-deficient, let \(\mathcal R:=\mathrm{Range}(\bSigma)=\mathrm{row}(\Xb)\), and let \(\Pb\) be the orthogonal projection onto \(\mathcal R\).
For any \(\theta\in\Cb\), the GLM loss and the matrix seminorm depend only on \(\Pb\theta\), and the projected feasible set is
\[
\Pb\Cb=\Cb\cap\mathcal R\subseteq\Cb,
\]
because \(\Cb=\mathbf B(0,\xi)\).
Therefore the regularized and unregularized constrained problems reduce exactly to \(\Pb\Cb\) on \(\mathcal R\), with \(\beta\) replaced by \(\Pb\beta\).
The curvature bounds remain valid on this reduced feasible set, and \(\bSigma|_{\mathcal R}\) is positive definite.
The proof below applies on \(\mathcal R\); converting back gives the same \(\bSigma\)-seminorm bounds, and the stochastic term is controlled by \(\sqrt{\rank(\bSigma)}\le\sqrt d\).
We therefore write the argument in full-rank notation.

We proceed by analyzing the problem in the whitened domain.
Let $\bar{\theta} := \bSigma^{1/2}\theta$ and define the transformed domain $\bar{\Cb} := \{ \bSigma^{1/2}\theta \mid \theta \in \Cb \}$.
The transformed loss function is given by $\bar{f}(\bar{\theta}) := f(\bSigma^{-1/2}\bar{\theta})$.

Let $\bar{\hat{\theta}} = \bSigma^{1/2}\hat{\theta}$ and $\bar{\tilde{\theta}} = \bSigma^{1/2}\tilde{\theta}$ be the minimizers in $\bar{\Cb}$ for the regularized and unregularized problems, respectively.

\paragraph{Step 1: Lower Bound via Strong Convexity.}
By Lemma~\ref{lemma; PL GLM}, $\bar{f}$ is $\alpha_\ell$-strongly convex on $\bar{\Cb}$.
Using the property of strongly convex functions and the first-order optimality condition for $\bar{\tilde{\theta}}$ (i.e., $\langle \nabla \bar{f}(\bar{\tilde{\theta}}), \bar{\theta} - \bar{\tilde{\theta}} \rangle \ge 0$ for all $\bar{\theta} \in \bar{\Cb}$), we have:
\begin{align*}
\bar{f}(\bar{\hat{\theta}}) - \bar{f}(\bar{\tilde{\theta}})
&\ge \langle \nabla \bar{f}(\bar{\tilde{\theta}}), \bar{\hat{\theta}} - \bar{\tilde{\theta}} \rangle + \frac{\alpha_\ell}{2} \|\bar{\hat{\theta}} - \bar{\tilde{\theta}}\|_2^2 \\
&\ge \frac{\alpha_\ell}{2} \|\bar{\hat{\theta}} - \bar{\tilde{\theta}}\|_2^2.
\end{align*}

\paragraph{Step 2: Upper Bound via Regularization.}
From the optimality of $\bar{\hat{\theta}}$ for the regularized objective:
\[
\bar{f}(\bar{\hat{\theta}}) + \lambda \|\bar{\hat{\theta}} - \bar{\beta}\|_2 \le \bar{f}(\bar{\tilde{\theta}}) + \lambda \|\bar{\tilde{\theta}} - \bar{\beta}\|_2.
\]
Rearranging terms and applying the reverse triangle inequality:
\begin{align*}
\bar{f}(\bar{\hat{\theta}}) - \bar{f}(\bar{\tilde{\theta}})
&\le \lambda \left( \|\bar{\tilde{\theta}} - \bar{\beta}\|_2 - \|\bar{\hat{\theta}} - \bar{\beta}\|_2 \right) \\
&\le \lambda \|\bar{\hat{\theta}} - \bar{\tilde{\theta}}\|_2.
\end{align*}

\paragraph{Step 3: Combining Bounds.}
Combining the inequalities from Steps 1 and 2:
\[
\frac{\alpha_\ell}{2} \|\bar{\hat{\theta}} - \bar{\tilde{\theta}}\|_2^2 \le \lambda \|\bar{\hat{\theta}} - \bar{\tilde{\theta}}\|_2.
\]
Assuming $\|\bar{\hat{\theta}} - \bar{\tilde{\theta}}\|_2 > 0$ (otherwise the bound holds trivially), we divide by the norm to obtain:
\[
\|\bar{\hat{\theta}} - \bar{\tilde{\theta}}\|_2 \le \frac{2\lambda}{\alpha_\ell}.
\]
Converting back to the original space using $\|\bar{v}\|_2 = \|v\|_{\bSigma}$, we get $\|\hat{\theta} - \tilde{\theta}\|_{\bSigma} \le \frac{2\lambda}{\alpha_\ell}$.

\paragraph{Step 4: Final Error Bound.}
The unregularized GLM estimator $\tilde{\theta}$ satisfies the standard concentration bound (derived from the $\alpha_\ell$-strong convexity and Hanson-Wright inequality on the gradient):
\[
\|\tilde{\theta} - \theta^\star\|_{\bSigma} \le \frac{1}{\alpha_\ell} \|\nabla \bar{f}(\bar{\theta}^\star)\|_2 \le \frac{c_0}{\alpha_\ell} \sqrt{\frac{d \log(2/\kappa)}{n}}.
\]
Applying the triangle inequality $\|\hat{\theta} - \theta^\star\|_{\bSigma} \le \|\hat{\theta} - \tilde{\theta}\|_{\bSigma} + \|\tilde{\theta} - \theta^\star\|_{\bSigma}$ yields the final result.
\end{proof}

\section{Proofs for the Linear Model}\label{section; linear proofs}\label{section; apdx groundwork}

We now turn to the genuinely multi-task part of the linear-model proof.
The single-task \(n\)-sample loss geometry was isolated in Section~\ref{section; loss geometry}; here we set up the pooled objectives, analyze the inlier pooling estimator, control the outlier perturbation step, and conclude the proof of Theorem~\ref{theorem; MSE bound}.

\subsection{Multi-Task Setup and Notation}

Throughout the transfer proof, all quantities involving the inlier average \(\bSigma_\Sb\) are interpreted after projecting onto \(\mathrm{Range}(\bSigma_\Sb)\).
On this projected subspace, the displayed inverses are ordinary inverses.
This entails no loss for in-sample risk, because Assumption~\ref{assumption; comparability} implies that any direction in \(\mathrm{Null}(\bSigma_\Sb)\) is also in \(\mathrm{Null}(\bSigma_j)\) for every inlier task \(j\in\Sb\).
Thus, in the proof below, we work on this projected subspace and treat \(\bSigma_\Sb\) as full-rank.
For the linear model, we work on the unconstrained domain $\Cb=\RR^d$.


For any subset of tasks $\Ib \subseteq [m]$, let
\[
N_\Ib := \sum_{j \in \Ib} n_j,
\qquad
\Vb_\Ib := \sum_{j \in \Ib} \Vb_j,
\qquad
\bSigma_\Ib := \frac{1}{N_\Ib}\Vb_\Ib.
\]
In the balanced case analyzed in the main theorem, $n_j=n$ and hence $N_\Sb = n|\Sb|$.
We define the task loss
\[
f_j(\beta) := \frac{1}{2n}\sum_{i=1}^{n} (y_{ji}-x_{ji}^\top \beta)^2
\]
and its matrix-weighted infimal convolution
\[
g_j(\beta) := \left(f_j \star \lambda \|\cdot\|_{\bSigma_j}\right)(\beta)
= \inf_{u \in \RR^d} \left\{ f_j(u) + \lambda \|u-\beta\|_{\bSigma_j} \right\}.
\]
We further write
\begin{align*}
F(\beta) &:= \sum_{j \in [m]} f_j(\beta), & G(\beta) &:= \sum_{j \in [m]} g_j(\beta), \\
F_{\Sb}(\beta) &:= \sum_{j \in \Sb} f_j(\beta), & G_{\Sb}(\beta) &:= \sum_{j \in \Sb} g_j(\beta).
\end{align*}
We also denote the aggregate outlier contribution by
\[
L(\beta) := \sum_{j \in \Sb^c} g_j(\beta),
\qquad\text{so that}\qquad
G(\beta)=G_\Sb(\beta)+L(\beta).
\]
Let $\hat{\beta}_{F}$, $\hat{\beta}_{F_\Sb}$, $\hat{\beta}_{G}$, and $\hat{\beta}_{G_\Sb}$ denote minimizers of these objectives.
We also define the invariant region
\[
R_j := \left\{ \beta \in \Cb \mid f_j(\beta) = g_j(\beta) \right\}, \qquad j \in [m],
\]
and, for each inlier task, $\eta_j^\star := \theta_j^\star - \theta^\star$.

\paragraph{Pooled Whitening Notation.}
On \(\mathrm{Range}(\bSigma_\Sb)\), we define the pooled whitening map by
\[
\bar v := \bSigma_\Sb^{1/2}v,
\qquad v\in\RR^d.
\]
For any function \(h:\RR^d\to\RR\), we define its pooled-whitened version by
\[
\bar{h}(\bar v) := h(\bSigma_\Sb^{-1/2}\bar v),
\]
where \(\bSigma_\Sb^{-1/2}\) denotes the inverse on \(\mathrm{Range}(\bSigma_\Sb)\).
Thus \(\bar\theta\), \(\bar\beta\), \(\bar\theta^\star\), \(\bar\theta_j^\star\), \(\bar{\hat\beta}_F\), \(\bar{\hat\beta}_{F_\Sb}\), \(\bar{\hat\beta}_G\), and \(\bar{\hat\beta}_{G_\Sb}\) are all instances of the same pooled whitening map. In particular, we write \(\bar F\), \(\bar G\), \(\bar F_\Sb\), \(\bar G_\Sb\), and \(\bar L\) for the transformed pooled objectives.

\subsection{The Inlier Pooling Estimator}

The second ingredient is a high-probability description of the inlier pooling estimator. This identifies the statistical rate of the ideal inlier-only procedure and characterizes a regime in which the regularized inlier objective collapses to the same minimizer.

\begin{lemma}[Error Bound of Pooling Estimator: Linear]\label{lemma; error bound F_S linear model}
Let $\hat{\beta}_{F_{\Sb}}$ be the minimizer of $F_\Sb$.
Under Assumption~\ref{assumption; comparability}, with probability at least $1-\frac{\kappa}{4}$, simultaneously for all $j\in\Sb$,
\begin{align*}
\|\hat{\beta}_{F_{\Sb}} - \theta^\star\|_{\bSigma_j} &\leq \sqrt{B}\delta + c_0 \sqrt{\frac{B d\zeta}{N_\Sb}}.
\end{align*}
\end{lemma}

\begin{proof}
Recall the closed-form solution for the pooling estimator:
\[
\hat{\beta}_{F_{\Sb}} = \Vb_{\Sb}^{-1} \sum_{k \in \Sb} \Xb_k^\top \Yb_k = \theta^\star + \Vb_{\Sb}^{-1} \sum_{k \in \Sb} \Xb_k^\top (\Xb_k \eta_k^\star + \bm{\varepsilon}_k).
\]
We analyze the error in the $\bSigma_j$-norm, decomposing it into a bias term and a variance term:
\begin{align*}
\|\hat{\beta}_{F_{\Sb}} - \theta^\star\|_{\bSigma_j}
&\le \underbrace{\left\| \Vb_{\Sb}^{-1} \sum_{k \in \Sb} \Vb_k \eta_k^\star \right\|_{\bSigma_j}}_{\text{Bias}}
+ \underbrace{\left\| \Vb_{\Sb}^{-1} \sum_{k \in \Sb} \Xb_{k}^\top \bm{\varepsilon}_k \right\|_{\bSigma_j}}_{\text{Variance}}.
\end{align*}

\paragraph{Bias Term.}
Using the balancedness assumption $\bSigma_j \preceq B \bSigma_{\Sb} = \frac{B}{N_\Sb} \Vb_{\Sb}$, we have $\bSigma_j^{1/2} \Vb_\Sb^{-1} \bSigma_j^{1/2} \preceq \frac{B}{N_\Sb} \Ib$.
Let $\eb$ be the stacked vector of $\{ \Xb_k \eta_k^\star \}_{k \in \Sb} \in \RR^{N_\Sb}$.
Then
\[
(\text{Bias})^2 \le \frac{B}{N_\Sb} \eb^\top \Xb_\Sb (\Xb_\Sb^\top \Xb_\Sb)^{-1} \Xb_\Sb^\top \eb \le \frac{B}{N_\Sb} \|\eb\|_2^2.
\]
Since $\|\eb\|_2^2 \le N_\Sb \delta^2$, we obtain $\text{Bias} \le \sqrt{B} \delta$.

\paragraph{Variance Term.}
Let \(\Xb_\Sb\) be the stacked inlier design and let \(\bm\varepsilon_\Sb\) be the stacked inlier noise vector.
The squared variance term is the quadratic form
\[
\bm\varepsilon_\Sb^\top
\Xb_\Sb\Vb_\Sb^{-1}\bSigma_j\Vb_\Sb^{-1}\Xb_\Sb^\top
\bm\varepsilon_\Sb.
\]
Since \(\Vb_\Sb=N_\Sb\bSigma_\Sb\), Assumption~\ref{assumption; comparability} gives
\[
\Vb_\Sb^{-1/2}\bSigma_j\Vb_\Sb^{-1/2}\preceq \frac{B}{N_\Sb}\Ib.
\]
Thus the quadratic-form matrix has trace at most \(Bd/N_\Sb\) and operator norm at most \(B/N_\Sb\).
Applying the Hanson-Wright inequality (Lemma~\ref{lemma; hanson wright inequality}) with failure level \(\kappa/(4m)\) for each task \(j\) gives, on a union-bound event of probability at least \(1-\kappa/4\),
\[
\text{Variance}
\le c_0 \sqrt{\frac{B d\zeta}{N_\Sb}}.
\]
Combining both terms yields the result.
\end{proof}

\begin{proposition}[Equivalence of Pooling Estimators: Linear]\label{proposition; pooling range linear}
If the regularization parameter satisfies
\[
\lambda > (\sqrt{B}+1)\delta + c_0 \sqrt{\frac{d \zeta}{n}} + c_0 \sqrt{\frac{B d \zeta}{N_\Sb}},
\]
then with probability at least $1-\frac{\kappa}{2}$, we have $\hat{\beta}_{G_{\Sb}} = \hat{\beta}_{F_{\Sb}}$ and $\hat{\beta}_{F_{\Sb}} \in R_j$ for all $j \in \Sb$.
\end{proposition}

\begin{proof}
Let \(\mathcal{E}_{\mathrm{pool}}\) be the pooling-estimator event from Lemma~\ref{lemma; error bound F_S linear model}; it has probability at least \(1-\kappa/4\).
Let \(\mathcal{E}_{\mathrm{inv}}\) be the event that the taskwise noise bound used in Proposition~\ref{proposition; invariant region linear} holds for every \(j\in\Sb\), each invoked with failure level \(\kappa/(4m)\).
By a union bound, \(\PP(\mathcal{E}_{\mathrm{inv}})\ge 1-\kappa/4\), and hence \(\PP(\mathcal{E}_{\mathrm{pool}}\cap\mathcal{E}_{\mathrm{inv}})\ge1-\kappa/2\).
On this intersection, a sufficient condition for $\beta \in R_j$ is $\lambda > \|\theta_j^\star - \beta\|_{\bSigma_j} + c_0 \sqrt{\frac{d \zeta}{n}}$.
Substituting $\beta = \hat{\beta}_{F_{\Sb}}$:
\begin{align*}
\|\theta_j^\star - \hat{\beta}_{F_{\Sb}}\|_{\bSigma_j}
&\leq \|\theta_j^\star - \theta^\star\|_{\bSigma_j} + \|\theta^\star - \hat{\beta}_{F_{\Sb}}\|_{\bSigma_j} \\
&\leq \delta + \left( \sqrt{B}\delta + c_0 \sqrt{\frac{B d\zeta}{N_\Sb}} \right),
\end{align*}
where we used Lemma~\ref{lemma; error bound F_S linear model}.
The assumed lower bound on $\lambda$ ensures this condition holds strictly for all $j \in \Sb$.
Thus, $\hat{\beta}_{F_{\Sb}}$ lies in the invariant region of every task $j \in \Sb$.
For each \(j\in\Sb\), define the positive slack
\[
\Delta_j
:=
\lambda-\left(\|\theta_j^\star-\hat{\beta}_{F_{\Sb}}\|_{\bSigma_j}
+ c_0\sqrt{\frac{d\zeta}{n}}\right)
>0.
\]
Since \(\beta\mapsto \|\theta_j^\star-\beta\|_{\bSigma_j}\) is continuous and the stochastic term in Proposition~\ref{proposition; invariant region linear} does not depend on \(\beta\), there exists \(r_j>0\) such that
\[
\|\beta-\hat{\beta}_{F_{\Sb}}\|_2<r_j
\quad\Longrightarrow\quad
\|\theta_j^\star-\beta\|_{\bSigma_j}+c_0\sqrt{\frac{d\zeta}{n}}<\lambda.
\]
Hence Proposition~\ref{proposition; invariant region linear} implies \(f_j(\beta)=g_j(\beta)\) throughout the Euclidean ball \(B_{r_j}(\hat{\beta}_{F_{\Sb}})\).
Let \(r:=\min_{j\in\Sb} r_j>0\). Then
\[
F_\Sb(\beta)=G_\Sb(\beta)
\qquad\text{for all }\beta\in B_r(\hat{\beta}_{F_{\Sb}}).
\]
On \(\mathrm{Range}(\bSigma_\Sb)\), \(F_\Sb\) is strictly convex, so \(\hat{\beta}_{F_{\Sb}}\) is its unique minimizer in the prediction-relevant subspace and therefore a local minimizer of \(G_\Sb\) as well.
Finally, $G_\Sb$ is convex as a sum of infimal convolutions of convex functions, so any local minimizer is global. Hence $\hat{\beta}_{F_{\Sb}}$ minimizes $G_\Sb$.
\end{proof}

\subsection{A Perturbation Bound for Outliers}

The third ingredient controls the shift from the inlier-only objective $G_\Sb$ to the full objective $G = G_\Sb + L$, where $L$ denotes the aggregate outlier contribution introduced above, by treating this outlier term as a Lipschitz perturbation in the whitened geometry.



\begin{claim}[Local Inlier Curvature: Linear]\label{claim; outlier linear}
Suppose Assumption~\ref{assumption; comparability} holds and
\[
\lambda > 2(\sqrt{B}+1)\delta + 2c_0 \sqrt{\frac{d \zeta }{n}} + 2c_0 \sqrt{\frac{d \zeta B}{N_\Sb}}.
\]
Conditioned on the event where Lemma~\ref{lemma; error bound F_S linear model}, Proposition~\ref{proposition; pooling range linear}, and the taskwise noise bounds used in Proposition~\ref{proposition; invariant region linear} hold for all \(j\in\Sb\), every $\beta$ satisfying
\[
\|\bar{\beta}-\bar{\hat{\beta}}_{G_\Sb}\|_2 \le \frac{\lambda}{2\sqrt{B}},
\]
belongs to the invariant region $R_j$ for all $j\in\Sb$.
Consequently, in this neighborhood,
\[
\nabla^2 \bar{G}_\Sb(\bar{\beta}) = |\Sb|\Ib_d.
\]
\end{claim}

\begin{proof}
Under the stated event, $\hat{\beta}_{G_\Sb}=\hat{\beta}_{F_\Sb}$.
Moreover, by Lemma~\ref{lemma; error bound F_S linear model} and the assumed lower bound on $\lambda$, for every $j\in\Sb$,
\[
\|\theta_j^\star-\hat{\beta}_{G_\Sb}\|_{\bSigma_j}
+ c_0\sqrt{\frac{d\zeta}{n}}
\le
(\sqrt{B}+1)\delta
+ c_0\sqrt{\frac{Bd\zeta}{N_\Sb}}
+ c_0\sqrt{\frac{d\zeta}{n}}
< \frac{\lambda}{2}.
\]
If $\|\bar{\beta}-\bar{\hat{\beta}}_{G_\Sb}\|_2 \le \lambda/(2\sqrt{B})$, then Assumption~\ref{assumption; comparability} gives
\[
\|\beta-\hat{\beta}_{G_\Sb}\|_{\bSigma_j}
\le \sqrt{B}\|\beta-\hat{\beta}_{G_\Sb}\|_{\bSigma_\Sb}
= \sqrt{B}\|\bar{\beta}-\bar{\hat{\beta}}_{G_\Sb}\|_2
\le \frac{\lambda}{2}.
\]
Hence
\[
\|\theta_j^\star-\beta\|_{\bSigma_j}
+ c_0\sqrt{\frac{d\zeta}{n}}
< \lambda,
\]
so Proposition~\ref{proposition; invariant region linear} implies $\beta\in R_j$ for all $j\in\Sb$.
Since the stochastic term in Proposition~\ref{proposition; invariant region linear} is precisely the taskwise noise bound included in the conditioning event and does not depend on $\beta$, this implication holds simultaneously throughout the displayed neighborhood.

Therefore $G_\Sb$ and $F_\Sb$ agree throughout this neighborhood. For the linear loss,
\[
\nabla^2 \bar{f}_j(\bar{\beta})
=
\bSigma_\Sb^{-1/2}\bSigma_j\bSigma_\Sb^{-1/2},
\]
which is independent of $\bar{\beta}$.
Summing over $j\in\Sb$ and using $\bSigma_\Sb=|\Sb|^{-1}\sum_{j\in\Sb}\bSigma_j$ yields
\[
\nabla^2 \bar{G}_\Sb(\bar{\beta})
=
\nabla^2 \bar{F}_\Sb(\bar{\beta})
=
\sum_{j\in\Sb}\bSigma_\Sb^{-1/2}\bSigma_j\bSigma_\Sb^{-1/2}
=
|\Sb|\Ib_d.
\]
\end{proof}

\begin{proposition}[Key Proposition: Linear Model]\label{proposition; outlier bound}
Suppose Assumption~\ref{assumption; comparability} holds with $B < \frac{1}{3\varepsilon}$ and the regularization parameter satisfies:
\[
\lambda > 2(\sqrt{B}+1)\delta + 2c_0 \sqrt{\frac{d \zeta }{n}} + 2c_0 \sqrt{\frac{d \zeta B}{N_\Sb}}.
\]
Then, with probability at least $1-\kappa$, the following holds simultaneously for all inlier tasks $j \in \Sb$:
\begin{align*}
\|\hat{\beta}_{G}- \theta_j^\star \|_{\bSigma_{j}} \leq (\sqrt{B}+1) \delta + c_0 \sqrt{\frac{Bd \zeta}{N_\Sb}} + \frac{\varepsilon}{1-\varepsilon}B \lambda.
\end{align*}
Furthermore, under the same event, we have
\[
\|\hat{\theta}_j-\hat{\beta}_{G}\|_{\bSigma_j}=0,
\qquad
\|\hat{\theta}_j-\theta_j^\star\|_{\bSigma_j}
=\|\hat{\beta}_{G}-\theta_j^\star\|_{\bSigma_j}
\]
for all $j \in \Sb$.
\end{proposition}

\begin{proof}
Using the pooled whitening notation introduced above, let $\bar{\hat{\beta}}_{G} := \bSigma_{\Sb}^{1/2}\hat{\beta}_{G}$ and $\bar{\hat{\beta}}_{G_\Sb} := \bSigma_{\Sb}^{1/2}\hat{\beta}_{G_{\Sb}}$.
Minimizing $G$ is equivalent to minimizing $\bar{G} = \bar{G}_\Sb + \bar{L}$.

\paragraph{Step 1: Pooling Range and Strong Convexity.}
Let $\mathcal{E}_{\text{pool}}$ denote the event where Lemma~\ref{lemma; error bound F_S linear model}, Proposition~\ref{proposition; pooling range linear}, and the taskwise invariant-region noise bounds hold.
By the failure-budget convention above, the pooling-estimator event is allocated failure \(\kappa/4\) and the taskwise noise events are allocated total failure \(\kappa/4\), so \(\PP(\mathcal{E}_{\text{pool}})\ge 1-\kappa/2\ge 1-\kappa\).
By Proposition~\ref{proposition; pooling range linear}, $\hat{\beta}_{F_\Sb} = \hat{\beta}_{G_\Sb}$ on this event.
Moreover, Claim~\ref{claim; outlier linear} shows that for all $\beta$ in the neighborhood
\[
\|\bar{\beta} - \bar{\hat{\beta}}_{G_\Sb}\|_2 \leq \frac{\lambda}{2\sqrt{B}},
\]
the transformed inlier objective has exact quadratic curvature:
\[
\nabla^2 \bar{G}_\Sb(\bar{\beta}) = \nabla^2 \bar{F}_\Sb(\bar{\beta}) = |\Sb| \Ib_d.
\]

\paragraph{Step 2: Lipschitz Continuity of Outliers.}
Since $\varepsilon < \frac{1}{3B} \le \frac{1}{2B+1}$, Lemma~\ref{lemma; transformed loss Lipschitz upper bound} ensures that
\[
\operatorname{Lip}(\bar{L}) \leq \sum_{j \in \Sb^c} \operatorname{Lip}(\bar{g}_j) \le m\varepsilon \sqrt{B} \lambda.
\]
We apply Lemma~\ref{lemma; ARMUL effect outlier} with parameters $r = \frac{\lambda}{2\sqrt{B}}$, $\rho = |\Sb|$, and $\lambda' = m\varepsilon \sqrt{B}\lambda$.
Since $m\varepsilon \sqrt{B} \lambda < (1-\varepsilon)m \frac{\lambda}{2\sqrt{B}} \le \rho r$, this yields
\[
\|\bar{\hat{\beta}}_{G} - \bar{\hat{\beta}}_{G_\Sb} \|_2 \leq \frac{m\varepsilon \sqrt{B}\lambda}{|\Sb|} \leq \frac{\varepsilon}{1-\varepsilon} \sqrt{B} \lambda.
\]
Translating back to the original domain, for any $j \in \Sb$,
\[
\|\hat{\beta}_{G} - \hat{\beta}_{G_\Sb} \|_{\bSigma_j} \leq \frac{\varepsilon}{1-\varepsilon} B \lambda.
\]

\paragraph{Step 3: Total Error Bound.}
Combining this perturbation bound with Lemma~\ref{lemma; error bound F_S linear model}, on $\mathcal{E}_{\text{pool}}$ we obtain
\begin{align}\label{equation; error bound linear}
\|\hat{\beta}_{G} - \theta_{j}^\star \|_{\bSigma_j}
&\leq \|\hat{\beta}_{G_{\Sb}} - \theta_{j}^\star \|_{\bSigma_j} + \|\hat{\beta}_{G} - \hat{\beta}_{G_{\Sb}} \|_{\bSigma_j} \nonumber \\
&\leq (\sqrt{B}+1)\delta + c_0 \sqrt{\frac{Bd \zeta}{N_\Sb}} + \frac{\varepsilon}{1-\varepsilon} B \lambda \nonumber \\
&\leq (\sqrt{B}+1)\delta + c_0 \sqrt{\frac{Bd \zeta}{N_\Sb}} + \frac{1}{2}\lambda.
\end{align}

\paragraph{Step 4: Invariant Region Check.}
To verify that $\hat{\beta}_G \in R_j$, Proposition~\ref{proposition; invariant region linear} requires
\[
\|\hat{\beta}_{G} - \theta_{j}^\star \|_{\bSigma_j} + c_0 \sqrt{\frac{d \zeta}{n}} < \lambda.
\]
Substituting \eqref{equation; error bound linear}, the left-hand side is bounded by
\[
(\sqrt{B}+1)\delta + c_0 \sqrt{\frac{Bd \zeta}{N_\Sb}} + \frac{1}{2}\lambda + c_0 \sqrt{\frac{d \zeta}{n}},
\]
which is strictly smaller than $\lambda$ by the assumed lower bound on $\lambda$.
Hence $\hat{\beta}_G \in R_j$ for all $j \in \Sb$.
By Proposition~\ref{proposition; invariant region linear}, every corresponding taskwise minimizer satisfies \(\|\hat{\theta}_j-\hat{\beta}_G\|_{\bSigma_j}=0\), and therefore \(\|\hat{\theta}_j-\theta_j^\star\|_{\bSigma_j}=\|\hat{\beta}_G-\theta_j^\star\|_{\bSigma_j}\).
\end{proof}

\begin{lemma}\label{lemma; transformed loss Lipschitz upper bound}
The transformed regularized loss function $\bar{g}_j(\cdot)$ is $\sqrt{B}\lambda_j$-Lipschitz.
\end{lemma}

\begin{proof}
Let
\[
M_j:=\bSigma_{\Sb}^{-1/2}\bSigma_j\bSigma_{\Sb}^{-1/2}.
\]
In pooled-whitened coordinates,
\[
\bar g_j(w)
=
\inf_z\left\{\bar f_j(z)+\lambda_j\|z-w\|_{M_j}\right\},
\]
where the infimum is over the pooled-whitened subspace.
By Assumption~\ref{assumption; comparability}, \(M_j\preceq B\Ib_d\).
Fix \(w,w'\) and \(\eta>0\), and choose \(z_\eta\) such that
\[
\bar g_j(w')+\eta
>
\bar f_j(z_\eta)+\lambda_j\|z_\eta-w'\|_{M_j}.
\]
Then
\begin{align*}
\bar g_j(w)-\bar g_j(w')
&\le
\lambda_j\bigl(\|z_\eta-w\|_{M_j}-\|z_\eta-w'\|_{M_j}\bigr)+\eta \\
&\le
\lambda_j\|w-w'\|_{M_j}+\eta
\le
\sqrt{B}\lambda_j\|w-w'\|_2+\eta.
\end{align*}
Letting \(\eta\downarrow0\) and exchanging \(w,w'\) proves the claim.
\end{proof}

\subsection{Proof of Theorem~\ref{theorem; MSE bound}}

\begin{proof}
Let \(\mathcal{E}_{\mathrm{safe}}\) be the event obtained by applying the uniform form of Proposition~\ref{proposition; personalization} to each task with failure probability \(\kappa/(2m)\) and taking a union bound.
Then \(\PP(\mathcal{E}_{\mathrm{safe}})\ge1-\kappa/2\), and on this event, with \(\lambda=q\sqrt{d\zeta/n}\) and \(q\gtrsim1\), for every task \(j\in[m]\),
\[
\|\hat{\theta}_j-\theta_j^\star\|_{\bSigma_j}^2
\lesssim \frac{d\zeta}{n}+\lambda^2
\lesssim q^2\frac{d\zeta}{n}.
\]
This proves part~(a), including all outlier tasks, without any balancedness or relatedness assumption.

It remains to prove the sharper inlier bound in part~(b). We analyze the estimator in two regimes depending on the magnitude of the task heterogeneity $\delta$ relative to the regularization parameter $\lambda = q\sqrt{\frac{d \zeta}{n}}$.
Throughout this part, \(B\lesssim \min(1/\varepsilon,m)\); choosing the hidden universal constant small enough gives the numerical conditions needed in Proposition~\ref{proposition; outlier bound}, and also \(N_\Sb=|\Sb|n\asymp mn\).

\paragraph{Case 1: Proposition~\ref{proposition; outlier bound} Applies.}
Suppose
\[
\lambda
>
2(\sqrt{B}+1)\delta
+2c_0\sqrt{\frac{d\zeta}{n}}
+2c_0\sqrt{\frac{Bd\zeta}{N_\Sb}}.
\]
Then Proposition~\ref{proposition; outlier bound} applies.
Its proof constructs a transfer event \(\mathcal{E}_{\mathrm{transfer}}\) with \(\PP(\mathcal{E}_{\mathrm{transfer}})\ge1-\kappa/2\) under the present good-event budget.
On \(\mathcal{E}_{\mathrm{safe}}\cap\mathcal{E}_{\mathrm{transfer}}\), which has probability at least \(1-\kappa\), for all inlier tasks $j \in \Sb$:
\begin{align*}
\|\hat{\theta}_{j} - {\theta}_{j}^\star \|_{\bSigma_j}
&= \|\hat{\beta}_{G} - {\theta}_{j}^\star \|_{\bSigma_j} \\
&\leq (\sqrt{B}+1)\delta + c_0 \sqrt{\frac{Bd \zeta}{N_\Sb}} + \frac{\varepsilon}{1-\varepsilon}B \lambda.
\end{align*}
Squaring and using $(a+b+c)^2 \lesssim a^2+b^2+c^2$, we obtain
\begin{align*}
\|\hat{\theta}_{j} - {\theta}_{j}^\star \|^2_{\bSigma_j}
&\lesssim B \delta^2 + \frac{B d \zeta}{mn} + \left(\frac{\varepsilon}{1-\varepsilon}B\right)^2 \lambda^2 \\
&\lesssim \min\left(B \delta^2, \, q^2 \frac{d \zeta}{n}\right) + \frac{B d \zeta}{mn} + q^2B^2\varepsilon^2 \frac{d \zeta}{n}.
\end{align*}
The last inequality uses the displayed condition, which implies \(B\delta^2\lesssim \lambda^2=q^2d\zeta/n\).

\paragraph{Case 2: Proposition~\ref{proposition; outlier bound} Does Not Apply.}
If the displayed condition fails, then
\[
\lambda
\le
2(\sqrt{B}+1)\delta
+2c_0\sqrt{\frac{d\zeta}{n}}
+2c_0\sqrt{\frac{Bd\zeta}{N_\Sb}}.
\]
Since \(q\gtrsim1\) is chosen large enough that \(q\ge 8c_0\), we can absorb the middle term into the left-hand side and obtain
\[
\frac{\lambda}{2}
\lesssim
\sqrt{B}\delta
+\sqrt{\frac{Bd\zeta}{N_\Sb}},
\]
where we used \(B\ge1\).
Hence at least one of the following alternatives must hold:
\[
\lambda\lesssim \sqrt{B}\delta
\qquad\text{or}\qquad
\lambda\lesssim \sqrt{\frac{Bd\zeta}{N_\Sb}}.
\]
Equivalently,
\[
q^2\frac{d\zeta}{n}\lesssim B\delta^2
\qquad\text{or}\qquad
q^2\frac{d\zeta}{n}\lesssim \frac{Bd\zeta}{N_\Sb}.
\]
On the already-defined event \(\mathcal{E}_{\mathrm{safe}}\),
\begin{align*}
\|\hat{\theta}_{j} - {\theta}_{j}^\star \|^2_{\bSigma_j}
&\lesssim \frac{d \zeta}{n} + \lambda^2
\lesssim q^2 \frac{d \zeta}{n}.
\end{align*}
The preceding alternatives show that this safety bound is controlled by either the heterogeneity term or the pooling term, and therefore by the right-hand side claimed in part~(b).

\paragraph{Conclusion.}
Combining the two cases, we conclude that with probability at least $1-\kappa$, for all $j \in \Sb$,
\[
\|\hat{\theta}_{j} - {\theta}_{j}^\star \|^2_{\bSigma_j}
\lesssim \frac{B d \zeta}{mn} + \min\left(B \delta^2, \, q^2 \frac{d \zeta}{n}\right) + q^2B^2 \varepsilon^2 \frac{d \zeta}{n}.
\]
The outlier tasks are already covered by the universal safety bound proved at the beginning.
\end{proof}



\section{Proofs for the GLM}\label{section; glm proofs}\label{section; key propositions}

We now turn to the genuinely multi-task part of the GLM proof.
The single-task \(n\)-sample GLM loss geometry was isolated in Section~\ref{section; loss geometry}; this section focuses on the inlier pooling estimator, the outlier perturbation step, and the theorem and population-risk proofs.

\subsection{Multi-Task Setup and Notation}

Throughout the GLM transfer proof, all quantities involving the inlier average \(\bSigma_\Sb\) are interpreted after projecting onto \(\mathrm{Range}(\bSigma_\Sb)\).
On this projected subspace, the displayed inverses are ordinary inverses.
This entails no loss for prediction risk: Assumption~\ref{assumption; comparability} implies that any direction in \(\mathrm{Null}(\bSigma_\Sb)\) is also in \(\mathrm{Null}(\bSigma_j)\) for every inlier task \(j\in\Sb\).
Moreover, since the GLM feasible set is \(\Cb=\mathbf B(0,\xi)\), orthogonal projection onto \(\mathrm{Range}(\bSigma_\Sb)\) keeps feasible parameters inside \(\Cb\).
Thus, in the proof below, we work on this projected subspace and treat \(\bSigma_\Sb\) as full-rank.

For any subset of tasks \(\Ib\subseteq[m]\), let
\[
N_\Ib := \sum_{j\in\Ib} n_j,
\qquad
\Vb_\Ib := \sum_{j\in\Ib}\Vb_j,
\qquad
\bSigma_\Ib := \frac{1}{N_\Ib}\Vb_\Ib.
\]
In the balanced case analyzed in the GLM theorem, \(n_j=n\) and hence \(N_\Sb=n|\Sb|\) and \(\bSigma_\Sb=|\Sb|^{-1}\sum_{j\in\Sb}\bSigma_j\).
Define \(\tau:=\alpha_u/\alpha_\ell\) and write \(m=\psi'\) for the GLM mean function.
For each task, define
\[
f_j(\beta)
:=
\frac{1}{n}\sum_{i=1}^n
\left(-y_{ji}x_{ji}^\top\beta+\psi(x_{ji}^\top\beta)\right)
\]
and its matrix-weighted infimal convolution over \(\Cb\),
\[
g_j(\beta)
:=
\left(f_j\star\lambda\|\cdot\|_{\bSigma_j}\right)(\beta)
=
\inf_{u\in\Cb}
\left\{f_j(u)+\lambda\|u-\beta\|_{\bSigma_j}\right\}.
\]
We further write
\[
F_\Sb(\beta):=\sum_{j\in\Sb}f_j(\beta),
\qquad
G_\Sb(\beta):=\sum_{j\in\Sb}g_j(\beta),
\qquad
L(\beta):=\sum_{j\in\Sb^c}g_j(\beta),
\qquad
G(\beta):=G_\Sb(\beta)+L(\beta).
\]
Let \(\hat\beta_{F_\Sb}\), \(\hat\beta_{G_\Sb}\), and \(\hat\beta_G\) denote minimizers of these objectives over \(\Cb\).
As before, define the invariant region
\[
R_j:=\{\beta\in\Cb: f_j(\beta)=g_j(\beta)\},
\qquad j\in[m].
\]

\paragraph{Pooled Whitening Notation.}
On \(\mathrm{Range}(\bSigma_\Sb)\), we define the pooled whitening map by
\[
\bar v:=\bSigma_\Sb^{1/2}v,
\qquad
v\in\RR^d,
\]
and the pooled-whitened covariates by
\[
\tilde x_{ji}:=\bSigma_\Sb^{-1/2}x_{ji}.
\]
The transformed feasible set is
\[
\bar\Cb:=\{\bSigma_\Sb^{1/2}v:v\in\Cb\}.
\]
For any objective \(h\) above, we define its pooled-whitened version by
\[
\bar h(\bar v):=h(\bSigma_\Sb^{-1/2}\bar v),
\]
where \(\bSigma_\Sb^{-1/2}\) denotes the inverse on \(\mathrm{Range}(\bSigma_\Sb)\).
Thus \(\bar\theta\), \(\bar\beta\), \(\bar\theta^\star\), \(\bar\theta_j^\star\), \(\bar{\hat\beta}_{F_\Sb}\), \(\bar{\hat\beta}_{G_\Sb}\), and \(\bar{\hat\beta}_G\) are all instances of the same pooled whitening map.
In particular, we write \(\bar F_\Sb\), \(\bar G_\Sb\), \(\bar L\), and \(\bar G\) for the transformed objectives.

\subsection{The Inlier Pooling Estimator}\label{section; pooling analysis}

We now derive concentration bounds for the pooling estimator in Generalized Linear Models.

\begin{lemma}[Error Bound of Pooling Estimator: GLM]\label{lemma; pooling GLM}
With probability at least $1-\frac{\kappa}{4}$, the minimizer $\hat{\beta}_{F_{\Sb}}$ of the inlier loss $F_\Sb$ satisfies:
\begin{align*}
\|\hat{\beta}_{F_{\Sb}} -\theta^\star \|_{\bSigma_{\Sb}} \leq \frac{c_0}{\alpha_\ell}\sqrt{\frac{d\zeta}{N_\Sb}} + \tau \sqrt{B}\delta.
\end{align*}
Consequently, for any $j \in \Sb$, we have the task-specific bound:
\begin{align*}
\|\hat{\beta}_{F_{\Sb}} -\theta^\star \|_{\bSigma_{j}} \leq \frac{c_0}{\alpha_\ell}\sqrt{\frac{B d\zeta}{N_\Sb}} + B \tau \delta.
\end{align*}
\end{lemma}

\begin{proof}
Using the pooled whitening notation introduced above, let $\bar{\hat{\beta}}_{F_\Sb} := \bSigma_\Sb^{1/2} \hat{\beta}_{F_\Sb}$.

\paragraph{Step 1: Gradient Bound via Strong Convexity.}
The Hessian of the transformed loss satisfies $\nabla^2 \bar{F}_\Sb(\bar{\beta}) \succeq \alpha_\ell |\Sb| \Ib_d$, so $\bar{F}_\Sb$ is $\mu$-strongly convex with $\mu=\alpha_\ell |\Sb|$.
Let $\bar{\hat{\beta}}_{F_\Sb}$ be the minimizer of $\bar{F}_\Sb$. Strong convexity implies
\[
\bigl\langle \nabla \bar{F}_\Sb(\bar{\theta}^\star) - \nabla \bar{F}_\Sb(\bar{\hat{\beta}}_{F_\Sb}),\, \bar{\theta}^\star - \bar{\hat{\beta}}_{F_\Sb} \bigr\rangle
\ge \mu \|\bar{\theta}^\star - \bar{\hat{\beta}}_{F_\Sb}\|_2^2.
\]
Since \(\bar{\hat{\beta}}_{F_\Sb}\) minimizes \(\bar F_\Sb\) over the convex set \(\bar\Cb\) and \(\bar\theta^\star\in\bar\Cb\), the constrained first-order condition gives
\[
\left\langle \nabla \bar F_\Sb(\bar{\hat{\beta}}_{F_\Sb}),\,
\bar\theta^\star-\bar{\hat{\beta}}_{F_\Sb}\right\rangle\ge0.
\]
Therefore Cauchy--Schwarz yields
\[
\|\bar{\hat{\beta}}_{F_\Sb} - \bar{\theta}^\star\|_2 \le \frac{1}{\alpha_\ell |\Sb|}\|\nabla \bar{F}_\Sb(\bar{\theta}^\star)\|_2.
\]

\paragraph{Step 2: Gradient Decomposition.}
We calculate the gradient at the centroid $\bar{\theta}^\star$:
\begin{align*}
\nabla \bar{F}_\Sb(\bar{\theta}^\star)
&= \frac{1}{n} \sum_{j \in \Sb} \sum_{i=1}^n \left( m(\tilde{x}_{ji}^\top \bar{\theta}^\star)-y_{ji} \right) \tilde{x}_{ji} \\
&= -\underbrace{\frac{1}{n} \sum_{j \in \Sb} \sum_{i=1}^n \varepsilon_{ji} \tilde{x}_{ji}}_{\text{Noise}} + \underbrace{\frac{1}{n} \sum_{j \in \Sb} \sum_{i=1}^n \left( m(x_{ji}^\top \theta^\star)-m(x_{ji}^\top \theta_j^\star) \right) \tilde{x}_{ji}}_{\text{Bias}},
\end{align*}
where $\tilde{x}_{ji} = \bSigma_\Sb^{-1/2} x_{ji}$ and $m=\psi'$ is the mean function.

\paragraph{Step 3: Bounding the Noise Term.}
The noise term is a sum of independent sub-Gaussian random vectors. Since
\[
\sum_{j \in \Sb} \sum_{i=1}^n \tilde{x}_{ji} \tilde{x}_{ji}^\top
= \bSigma_\Sb^{-1/2} \Bigl(\sum_{j \in \Sb} \Xb_j^\top \Xb_j\Bigr) \bSigma_\Sb^{-1/2}
= N_\Sb \Ib_d,
\]
the covariance of the sum is isotropic.
Applying the Hanson-Wright inequality with failure level \(\kappa/4\):
\[
\|\text{Noise}\|_2 \le c_0 \frac{\sqrt{N_\Sb d\zeta}}{n} = c_0 \sqrt{\frac{|\Sb| d\zeta}{n}}.
\]

\paragraph{Step 4: Bounding the Bias Term.}
By the Mean Value Theorem, $m(x_{ji}^\top \theta^\star) - m(x_{ji}^\top \theta_j^\star) = u_{ji} x_{ji}^\top (\theta^\star - \theta_j^\star)$, where $u_{ji} \in [\alpha_\ell, \alpha_u]$.
Let $\Qb_j := \frac{1}{n} \sum_{i=1}^n u_{ji} x_{ji} x_{ji}^\top$. Note that $\alpha_\ell \bSigma_j \preceq \Qb_j \preceq \alpha_u \bSigma_j$.
The bias term can be written as:
\[
\text{Bias} = \sum_{j \in \Sb} \bSigma_\Sb^{-1/2} \Qb_j (\theta^\star - \theta_j^\star) = \sum_{j \in \Sb} \bSigma_\Sb^{-1/2} \Qb_j \bSigma_\Sb^{-1/2} \bSigma_\Sb^{1/2} (\theta^\star - \theta_j^\star).
\]
We bound the norm of each term in the sum:
\begin{align*}
\|\bSigma_\Sb^{-1/2} \Qb_j (\theta^\star - \theta_j^\star)\|_2
&\le \|\bSigma_\Sb^{-1/2} \Qb_j^{1/2}\|_{\operatorname{op}} \|\Qb_j^{1/2} (\theta^\star - \theta_j^\star)\|_2 \\
&\le \|\bSigma_\Sb^{-1/2} \Qb_j^{1/2}\|_{\operatorname{op}} \sqrt{\alpha_u} \|\theta^\star - \theta_j^\star\|_{\bSigma_j}.
\end{align*}
Using $\Qb_j \preceq \alpha_u \bSigma_j$ and Assumption~\ref{assumption; comparability} ($\bSigma_j \preceq B \bSigma_\Sb$), we have:
\[
\|\bSigma_\Sb^{-1/2} \Qb_j^{1/2}\|_{\operatorname{op}}^2 = \|\bSigma_\Sb^{-1/2} \Qb_j \bSigma_\Sb^{-1/2}\|_{\operatorname{op}} \le \alpha_u \|\bSigma_\Sb^{-1/2} \bSigma_j \bSigma_\Sb^{-1/2}\|_{\operatorname{op}} \le \alpha_u B.
\]
Moreover, by the global covariate normalization \(\|\bSigma_j\|_{\op}\le 1\) from the Regularity Assumptions and the task-relatedness condition \(\|\theta_j^\star-\theta^\star\|_2\le\delta\), we have
\[
\|\theta^\star-\theta_j^\star\|_{\bSigma_j}\le \|\theta^\star-\theta_j^\star\|_2\le \delta.
\]
Thus, $\|\text{Bias term}_j\|_2 \le \sqrt{\alpha_u B} \sqrt{\alpha_u} \delta = \alpha_u \sqrt{B} \delta$.
Summing over $j \in \Sb$:
\[
\|\text{Bias}\|_2 \le \sum_{j \in \Sb} \alpha_u \sqrt{B} \delta = |\Sb| \alpha_u \sqrt{B} \delta.
\]

\paragraph{Step 5: Final Bound.}
Combining the bounds:
\begin{align*}
\|\hat{\beta}_{F_{\Sb}} - \theta^\star\|_{\bSigma_\Sb}
&\le \frac{1}{\alpha_\ell |\Sb|} \left( c_0 \sqrt{\frac{|\Sb| d\zeta}{n}} + |\Sb| \alpha_u \sqrt{B} \delta \right) \\
&= \frac{c_0}{\alpha_\ell} \sqrt{\frac{d\zeta}{n |\Sb|}} + \frac{\alpha_u}{\alpha_\ell} \sqrt{B} \delta \\
&= \frac{c_0}{\alpha_\ell} \sqrt{\frac{d\zeta}{N_\Sb}} + \tau \sqrt{B} \delta.
\end{align*}
The task-specific bound follows from $\|\cdot\|_{\bSigma_j} \le \sqrt{B} \|\cdot\|_{\bSigma_\Sb}$.
\end{proof}

\begin{proposition}[Equivalence of Pooling Estimators: GLM]\label{proposition; pooling range GLM}
Suppose the regularization parameter satisfies the following lower bound:
\[
\lambda > \alpha_u (B\tau+1)\delta + \frac{c_0 \alpha_u}{\alpha_\ell}\sqrt{\frac{B d\zeta}{N_\Sb}} + c_0 \sqrt{\frac{d \zeta}{n}}.
\]
Then, with probability at least $1-\frac{\kappa}{2}$, we have $\hat{\beta}_{G_{\Sb}} = \hat{\beta}_{F_{\Sb}}$.
Furthermore, $\hat{\beta}_{F_{\Sb}} \in R_j$ holds simultaneously for all $j \in \Sb$.
\end{proposition}

\begin{proof}
Let \(\mathcal{E}_{\mathrm{pool}}^{\mathrm{glm}}\) be the event from Lemma~\ref{lemma; pooling GLM}; it has probability at least \(1-\kappa/4\).
Let \(\mathcal{E}_{\mathrm{inv}}^{\mathrm{glm}}\) be the event that the taskwise GLM invariant-region noise bound from Proposition~\ref{proposition; invariant region GLM} holds for every \(j\in\Sb\), each invoked with failure level \(\kappa/(4m)\).
Then \(\PP(\mathcal{E}_{\mathrm{pool}}^{\mathrm{glm}}\cap\mathcal{E}_{\mathrm{inv}}^{\mathrm{glm}})\ge1-\kappa/2\).

The goal is to show that the unregularized pooling estimator $\hat{\beta}_{F_{\Sb}}$ minimizes the regularized objective $G_\Sb(\beta) = \sum_{j \in \Sb} g_j(\beta)$.
For GLMs, \(\nabla^2 f_j(\beta)=\frac{1}{n}\Xb_j^\top \Db_j(\beta)\Xb_j \succeq \alpha_\ell \bSigma_j\), where \(\Db_j(\beta)\) is the diagonal matrix of \(\psi''\)-values. Hence
\[
\nabla^2 F_\Sb(\beta)
=
\sum_{j\in\Sb}\nabla^2 f_j(\beta)
\succeq
\alpha_\ell\sum_{j\in\Sb}\bSigma_j
=
\alpha_\ell |\Sb| \bSigma_\Sb
\succ 0,
\]
so \(F_\Sb\) is strictly convex and \(\hat{\beta}_{F_{\Sb}}\) is its unique minimizer.

By Proposition~\ref{proposition; invariant region GLM}, the condition $\hat{\beta}_{F_{\Sb}} \in R_j$ is satisfied if:
\begin{equation}\label{eq: invariant condition check}
\lambda > \alpha_u \|\theta_j^\star - \hat{\beta}_{F_{\Sb}}\|_{\bSigma_j} + c_0 \sqrt{\frac{d \zeta}{n}}.
\end{equation}
We bound the error term $\|\theta_j^\star - \hat{\beta}_{F_{\Sb}}\|_{\bSigma_j}$ using the triangle inequality:
\begin{align*}
\|\theta_j^\star - \hat{\beta}_{F_{\Sb}}\|_{\bSigma_j}
&\leq \|\theta_j^\star - \theta^\star\|_{\bSigma_j} + \|\theta^\star - \hat{\beta}_{F_{\Sb}}\|_{\bSigma_j}.
\end{align*}
For the first term, using the bounded covariate assumption implies $\|\theta_j^\star - \theta^\star\|_{\bSigma_j} \le \delta$.
For the second term, we apply Lemma~\ref{lemma; pooling GLM}:
\[
\|\hat{\beta}_{F_{\Sb}} - \theta^\star\|_{\bSigma_j} \leq B \tau \delta + \frac{c_0}{\alpha_\ell}\sqrt{\frac{B d\zeta}{N_\Sb}}.
\]
Combining these, the condition \eqref{eq: invariant condition check} becomes:
\begin{align*}
\lambda > \alpha_u \left( \delta + B\tau\delta + \frac{c_0}{\alpha_\ell}\sqrt{\frac{B d\zeta}{N_\Sb}} \right) + c_0 \sqrt{\frac{d \zeta}{n}}.
\end{align*}
This is exactly the assumed lower bound on $\lambda$.
Thus, on \(\mathcal{E}_{\mathrm{pool}}^{\mathrm{glm}}\cap\mathcal{E}_{\mathrm{inv}}^{\mathrm{glm}}\), $\hat{\beta}_{F_{\Sb}}$ lies in the invariant region $R_j$ for all $j \in \Sb$.
For each \(j\in\Sb\), define the positive slack
\[
\Delta_j^{\mathrm{glm}}
:=
\lambda-\left(\alpha_u\|\theta_j^\star-\hat{\beta}_{F_{\Sb}}\|_{\bSigma_j}
+ c_0\sqrt{\frac{d\zeta}{n}}\right)
>0.
\]
Since \(\beta\mapsto \|\theta_j^\star-\beta\|_{\bSigma_j}\) is continuous and the stochastic term in Proposition~\ref{proposition; invariant region GLM} does not depend on \(\beta\), there exists \(r_j>0\) such that
\[
\|\beta-\hat{\beta}_{F_{\Sb}}\|_2<r_j
\quad\Longrightarrow\quad
\alpha_u\|\theta_j^\star-\beta\|_{\bSigma_j}+c_0\sqrt{\frac{d\zeta}{n}}<\lambda.
\]
Hence Proposition~\ref{proposition; invariant region GLM} implies \(f_j(\beta)=g_j(\beta)\) throughout the Euclidean ball \(B_{r_j}(\hat{\beta}_{F_{\Sb}})\).
Let \(r:=\min_{j\in\Sb}r_j>0\). Then
\[
F_\Sb(\beta)=G_\Sb(\beta)
\qquad\text{for all }\beta\in B_r(\hat{\beta}_{F_{\Sb}}).
\]
Since \(\hat{\beta}_{F_{\Sb}}\) is the unique minimizer of \(F_\Sb\), it is a local minimizer of \(G_\Sb\) as well.
Finally, \(G_\Sb\) is convex as a sum of infimal convolutions of convex functions, so any local minimizer is global. Hence \(\hat{\beta}_{G_\Sb}=\hat{\beta}_{F_{\Sb}}\).
\end{proof}

\subsection{A Perturbation Bound for Outliers}


\begin{proposition}[Key Proposition: GLM]\label{proposition; outlier bound GLM}
Suppose Assumption~\ref{assumption; comparability} holds with $B < \frac{1}{4\tau \varepsilon}$ and the regularization parameter satisfies:
\[
\lambda > 2\alpha_u (\tau B +1) \delta + 2 c_0 \sqrt{\frac{d \zeta}{n}} + 2 \tau c_0 \sqrt{\frac{B d \zeta}{N_\Sb}}.
\]
Then, with probability at least $1-\kappa$, the following holds simultaneously for all $j \in \Sb$:
\begin{align*}
\|\hat{\beta}_{G} - \theta_{j}^\star \|_{\bSigma_j}
&\leq (\tau B +1)\delta + \frac{c_0}{\alpha_\ell} \sqrt{\frac{Bd \zeta}{N_\Sb}} + \frac{2\varepsilon B\lambda}{\alpha_\ell}.
\end{align*}
Furthermore, under the same event, we have
\[
\|\hat{\theta}_j-\hat{\beta}_{G}\|_{\bSigma_j}=0,
\qquad
\|\hat{\theta}_j-\theta_j^\star\|_{\bSigma_j}
=\|\hat{\beta}_{G}-\theta_j^\star\|_{\bSigma_j}
\]
for all $j \in \Sb$.
\end{proposition}

\begin{proof}
Using the pooled whitening notation introduced above, let $\bar{\hat{\beta}}_{G} := \bSigma_{\Sb}^{1/2}\hat{\beta}_{G}$ and $\bar{\hat{\beta}}_{G_\Sb} := \bSigma_{\Sb}^{1/2}\hat{\beta}_{G_{\Sb}}$ denote the minimizers of the transformed global objective $\bar{G} = \bar{G}_\Sb + \bar{L}$ and the inlier objective $\bar{G}_\Sb$, respectively.
Let $\mathcal{E}_{\mathrm{glm}}$ be the good event constructed in Proposition~\ref{proposition; pooling range GLM}: the GLM pooling error holds and the taskwise GLM invariant-region noise bounds hold for all \(j\in\Sb\).
The pooling part is allocated failure \(\kappa/4\), and the taskwise invariant-region noise bounds are allocated failure \(\kappa/(4m)\) per task, so
\[
\PP(\mathcal{E}_{\mathrm{glm}})\ge 1-\frac{\kappa}{2}\ge 1-\kappa.
\]

\paragraph{Step 1: Pooling Estimator and Strong Convexity.}
By Proposition~\ref{proposition; pooling range GLM}, the pooling estimator coincides with the regularized inlier estimator, i.e., $\hat{\beta}_{F_\Sb} = \hat{\beta}_{G_\Sb}$.
Furthermore, invoking Claim~\ref{claim; outlier GLM}, for all $\beta$ in the neighborhood $\|\bar{\beta} - \bar{\hat{\beta}}_{G_\Sb} \|_2 \leq \frac{\lambda}{2 \alpha_u\sqrt{ B}}$, the transformed inlier loss is strongly convex:
\begin{align*}
\nabla^2 \bar{G}_\Sb(\bar{\beta}) \succeq \alpha_\ell |\Sb| \Ib_d.
\end{align*}

\paragraph{Step 2: Perturbation via Outliers.}
We bound the Lipschitz constant of the transformed outlier term $\bar{L}$. Using the assumption $B < \frac{1}{4\tau \varepsilon}$ and Lemma~\ref{lemma; outlier lipschitz GLM}:
\begin{align*}
\operatorname{Lip}(\bar{L}) \leq m\varepsilon \sqrt{B} \lambda.
\end{align*}
We apply the constrained perturbation lemma (Lemma~\ref{lemma; ARMUL effect outlier constrained}) over the convex set \(\bar\Cb\), with \(f=\bar G_\Sb\), \(g=\bar L\), \(x_0=\bar{\hat\beta}_{G_\Sb}\), \(\rho = \alpha_\ell |\Sb|\), and \(r = \frac{\lambda}{2\alpha_u \sqrt{B}}\).
Since $|\Sb| \ge (1-\varepsilon)m$, and we may assume $B \ge 1$ without loss of generality, the condition $B < \frac{1}{4\tau \varepsilon}$ implies $\varepsilon \le \frac{1}{4}$ and hence $\frac{\varepsilon}{1-\varepsilon} \le \frac{1}{3}$. Moreover,
\[
\frac{\operatorname{Lip}(\bar{L})}{\rho r}
= \frac{2\alpha_u \varepsilon B}{\alpha_\ell} \cdot \frac{m}{|\Sb|}
\le \frac{2\tau \varepsilon B}{1-\varepsilon} < 1,
\]
so the condition $\operatorname{Lip}(\bar{L}) < \rho r$ holds.
Applying the lemma yields:
\begin{align*}
\|\bar{\hat{\beta}}_G - \bar{\hat{\beta}}_{G_{\Sb}} \|_2
&\leq \frac{m\varepsilon \sqrt{B} \lambda}{\alpha_\ell |\Sb|}
\leq \frac{\varepsilon}{1-\varepsilon} \frac{\sqrt{B} \lambda}{\alpha_\ell}
\le \frac{2\varepsilon \sqrt{B}\lambda}{\alpha_\ell},
\end{align*}
where we used $|\Sb| \ge (1-\varepsilon)m$ and $\varepsilon \le 1/4$.
Converting back to the $\bSigma_j$-norm using $\bSigma_j \preceq B \bSigma_\Sb$, we obtain:
\begin{align*}
\|\hat{\beta}_{G} - \hat{\beta}_{G_{\Sb}} \|_{\bSigma_j}
\leq \sqrt{B} \|\bar{\hat{\beta}}_G - \bar{\hat{\beta}}_{G_{\Sb}} \|_2
\leq \frac{2\varepsilon B \lambda}{\alpha_\ell}.
\end{align*}

\paragraph{Step 3: Total Error and Invariant Region.}
Combining the perturbation bound with the pooling error (Lemma~\ref{lemma; pooling GLM}):
\begin{align}\label{equation; bound GLM detail}
\|\hat{\beta}_{G} - \theta_{j}^\star \|_{\bSigma_j}
&\leq \|\hat{\beta}_{G_{\Sb}} - \theta_{j}^\star \|_{\bSigma_j} + \|\hat{\beta}_{G} - \hat{\beta}_{G_{\Sb}} \|_{\bSigma_j} \nonumber \\
&\leq (\tau B +1)\delta + \frac{c_0}{\alpha_\ell} \sqrt{\frac{Bd \zeta}{N_\Sb}} + \frac{2\varepsilon B \lambda}{\alpha_\ell}.
\end{align}
To prove the zero-seminorm personalization statement, we check the condition for the invariant region (Proposition~\ref{proposition; invariant region GLM}).
We need $\lambda > \alpha_u \|\hat{\beta}_{G} - \theta_{j}^\star \|_{\bSigma_j} + c_0 \sqrt{\frac{d \zeta}{n}}$.
Substituting the error bound from \eqref{equation; bound GLM detail} into the right-hand side:
\begin{align*}
\text{RHS}
&\leq \alpha_u \left[ (\tau B +1)\delta + \frac{c_0}{\alpha_\ell} \sqrt{\frac{Bd \zeta}{N_\Sb}} + \frac{2\varepsilon B \lambda}{\alpha_\ell} \right] + c_0 \sqrt{\frac{d \zeta}{n}} \\
&= \alpha_u (\tau B +1)\delta + \tau c_0 \sqrt{\frac{Bd \zeta}{N_\Sb}} + c_0 \sqrt{\frac{d \zeta}{n}} + 2 \tau \varepsilon B \lambda.
\end{align*}
By the assumption $B < \frac{1}{4\tau \varepsilon}$, we have $2 \tau \varepsilon B \le \frac{1}{2}$. Thus, the $\lambda$ term on the right-hand side is at most $\frac{1}{2}\lambda$.
The assumed lower bound on $\lambda$ then ensures that the remaining deterministic and stochastic terms are also bounded by $\frac{1}{2}\lambda$.

Therefore, on the event $\mathcal{E}_{\mathrm{glm}}$, the condition holds. Proposition~\ref{proposition; invariant region GLM} then implies that every task-specific minimizer at center \(\hat{\beta}_G\) satisfies \(\|\hat{\theta}_j-\hat{\beta}_G\|_{\bSigma_j}=0\) for all \(j\in\Sb\). Hence the corresponding prediction-seminorm errors coincide, and the bound follows directly from \eqref{equation; bound GLM detail}.
\end{proof}

\begin{lemma}\label{lemma; outlier lipschitz GLM}
The transformed regularized loss function $\bar{g}_j$ is $\sqrt{B}\lambda_j$-Lipschitz on the domain $\bar{\Cb} := \{ \bSigma_{\Sb}^{1/2} \beta \mid \beta \in \Cb \}$.
\end{lemma}

\begin{proof}
Let
\[
M_j:=\bSigma_{\Sb}^{-1/2}\bSigma_j\bSigma_{\Sb}^{-1/2}.
\]
For \(w\in\bar\Cb\), the constrained infimal convolution becomes
\[
\bar g_j(w)
=
\inf_{z\in\bar\Cb}
\left\{\bar f_j(z)+\lambda_j\|z-w\|_{M_j}\right\}.
\]
By Assumption~\ref{assumption; comparability}, \(M_j\preceq B\Ib_d\).
Fix \(w,w'\in\bar\Cb\) and \(\eta>0\), and choose \(z_\eta\in\bar\Cb\) such that
\[
\bar g_j(w')+\eta
>
\bar f_j(z_\eta)+\lambda_j\|z_\eta-w'\|_{M_j}.
\]
Then
\begin{align*}
\bar g_j(w)-\bar g_j(w')
&\le
\lambda_j\bigl(\|z_\eta-w\|_{M_j}-\|z_\eta-w'\|_{M_j}\bigr)+\eta \\
&\le
\lambda_j\|w-w'\|_{M_j}+\eta
\le
\sqrt{B}\lambda_j\|w-w'\|_2+\eta.
\end{align*}
Letting \(\eta\downarrow0\) and exchanging \(w,w'\) proves the claim on \(\bar\Cb\).
\end{proof}

\begin{claim}\label{claim; outlier GLM}
Suppose Assumption~\ref{assumption; comparability} holds with $B < \frac{1}{4\tau \varepsilon}$ and
\[
\lambda > 2\alpha_u (\tau B +1) \delta + 2 c_0 \sqrt{\frac{d \zeta}{n}} + 2 \tau c_0 \sqrt{\frac{B d \zeta}{N_\Sb}}.
\]
Conditioned on the event where Lemma~\ref{lemma; pooling GLM}, Proposition~\ref{proposition; pooling range GLM}, and the taskwise GLM invariant-region noise bounds hold for all \(j\in\Sb\), for any $\beta \in \Cb$ such that $\|\bar{\beta} - \bar{\hat{\beta}}_{G_{\Sb}} \|_2 \leq \frac{\lambda}{2\alpha_u \sqrt{B}}$, we have:
\[
\nabla^2 \bar{G}_\Sb(\bar{\beta}) \succeq \alpha_\ell |\Sb|\Ib_d.
\]
\end{claim}

\begin{proof}
Let $\eta := \frac{\lambda}{2\alpha_u \sqrt{B}}$. Consider any $\beta$ such that $\|\bar{\beta} - \bar{\hat{\beta}}_{G_{\Sb}} \|_2 \leq \eta$.
First, we bound the distance in the task-specific norm $\|\cdot\|_{\bSigma_j}$. Using the assumption $\bSigma_j \preceq B \bSigma_\Sb$:
\begin{align*}
\|\beta - \hat{\beta}_{G_{\Sb}} \|_{\bSigma_j}
&\leq \sqrt{B} \|\beta - \hat{\beta}_{G_{\Sb}} \|_{\bSigma_{\Sb}} \\
&= \sqrt{B} \|\bar{\beta} - \bar{\hat{\beta}}_{G_{\Sb}} \|_2 \\
&\leq \sqrt{B} \eta = \frac{\lambda}{2\alpha_u}.
\end{align*}

Next, we apply the triangle inequality and the error bound for the pooling estimator (Lemma~\ref{lemma; pooling GLM}). Recall that under the favorable event, $\hat{\beta}_{G_\Sb} = \hat{\beta}_{F_\Sb}$.
Thus:
\begin{align*}
\|\beta - \theta_j^\star \|_{\bSigma_j}
&\leq \|\beta - \hat{\beta}_{G_{\Sb}} \|_{\bSigma_j} + \|\hat{\beta}_{G_{\Sb}} - \theta_j^\star \|_{\bSigma_j} \\
&\leq \frac{\lambda}{2\alpha_u} + \left( (\tau B + 1)\delta + \frac{c_0}{\alpha_\ell} \sqrt{\frac{B d \zeta}{N_\Sb}} \right).
\end{align*}

To ensure $\beta$ lies in the invariant region $R_j$, Proposition~\ref{proposition; invariant region GLM} requires $\lambda > \alpha_u \|\beta - \theta_j^\star \|_{\bSigma_j} + c_0 \sqrt{\frac{d \zeta}{n}}$.
Substituting the bound above, it suffices to show:
\begin{align*}
\lambda > \alpha_u \left( \frac{\lambda}{2\alpha_u} + (\tau B + 1)\delta + \frac{c_0}{\alpha_\ell} \sqrt{\frac{B d \zeta}{N_\Sb}} \right) + c_0 \sqrt{\frac{d \zeta}{n}}.
\end{align*}
Simplifying the right-hand side:
\begin{align*}
\lambda > \frac{\lambda}{2} + \alpha_u (\tau B + 1)\delta + \tau c_0 \sqrt{\frac{B d \zeta}{N_\Sb}} + c_0 \sqrt{\frac{d \zeta}{n}}.
\end{align*}
Rearranging terms, this condition is equivalent to
\begin{align*}
\frac{\lambda}{2} > \alpha_u (\tau B + 1)\delta + \tau c_0 \sqrt{\frac{B d \zeta}{N_\Sb}} + c_0 \sqrt{\frac{d \zeta}{n}},
\end{align*}
which is exactly the assumed lower bound on $\lambda$.

Consequently, for all $\beta$ in the neighborhood, $\beta \in R_j$ holds for all $j \in \Sb$. This implies $G_\Sb(\beta) = F_\Sb(\beta)$ locally.
Finally, we compute the Hessian lower bound. The Hessian of the transformed inlier loss is:
\begin{align*}
\nabla^2 \bar{G}_\Sb(\bar{\beta})
&= \nabla^2 \bar{F}_\Sb(\bar{\beta}) \\
&= \bSigma_\Sb^{-1/2} \left( \sum_{j \in \Sb} \nabla^2 f_j(\beta) \right) \bSigma_\Sb^{-1/2}.
\end{align*}
For GLM, $\nabla^2 f_j(\beta) = \frac{1}{n} \Xb_j^\top \mathbf{D}_j \Xb_j$, where $\mathbf{D}_j$ is a diagonal matrix with entries $\psi''(\cdot) \ge \alpha_\ell$. Thus, $\nabla^2 f_j(\beta) \succeq \alpha_\ell \bSigma_j$.
Summing over inliers:
\begin{align*}
\nabla^2 \bar{G}_\Sb(\bar{\beta})
&\succeq \bSigma_\Sb^{-1/2} \left( \sum_{j \in \Sb} \alpha_\ell \bSigma_j \right) \bSigma_\Sb^{-1/2} \\
&= \alpha_\ell \bSigma_\Sb^{-1/2} (|\Sb| \bSigma_\Sb) \bSigma_\Sb^{-1/2} \\
&= \alpha_\ell |\Sb| \Ib_d.
\end{align*}
This completes the proof.
\end{proof}

\subsection{Proof of Theorem~\ref{theorem; MSE bound GLM} (In-sample MSE of GLM)}

\begin{proof}
Let \(\mathcal{E}_{\mathrm{safe}}^{\mathrm{glm}}\) be the event obtained by applying Proposition~\ref{proposition: personalization glm} taskwise with failure probability \(\kappa/(2m)\).
By a union bound, \(\PP(\mathcal{E}_{\mathrm{safe}}^{\mathrm{glm}})\ge1-\kappa/2\), and on this event, for all \(j\in[m]\),
\[
\|\hat{\theta}_{j}-\theta_j^\star\|_{\bSigma_j}^2
\lesssim \frac{d\zeta}{n}+\lambda^2
\lesssim q^2\frac{d\zeta}{n}.
\]
This proves part~(a), so the remainder proves the sharper inlier guarantee in part~(b).
Recall that \(q \gtrsim 1\), so we may choose the implicit constant large enough that \(q \ge 8c_0\).
Also, since part~(b) assumes \(B \lesssim \min(1/\varepsilon,m)\), the favorable regime of Proposition~\ref{proposition; outlier bound GLM} is available and \(N_\Sb = |\Sb|n \asymp mn\).

\paragraph{Case 1: Proposition~\ref{proposition; outlier bound GLM} Applies.}
Suppose
\[
\lambda > 2\alpha_u (\tau B +1) \delta + 2 c_0 \sqrt{\frac{d \zeta}{n}} + 2 \tau c_0 \sqrt{\frac{B d \zeta}{N_\Sb}}.
\]
Then Proposition~\ref{proposition; outlier bound GLM} applies.
Its proof constructs a transfer event \(\mathcal{E}_{\mathrm{transfer}}^{\mathrm{glm}}\) with \(\PP(\mathcal{E}_{\mathrm{transfer}}^{\mathrm{glm}})\ge1-\kappa/2\) under the present good-event budget.
On \(\mathcal{E}_{\mathrm{safe}}^{\mathrm{glm}}\cap\mathcal{E}_{\mathrm{transfer}}^{\mathrm{glm}}\), which has probability at least \(1-\kappa\), for all inlier tasks \(j \in \Sb\),
\[
\|\hat{\theta}_{j} - {\theta}_{j}^\star \|_{\bSigma_j}
\leq (\tau B +1)\delta + \frac{c_0}{\alpha_\ell} \sqrt{\frac{Bd \zeta}{N_\Sb}} + \frac{2\varepsilon B\lambda}{\alpha_\ell}.
\]
Squaring and using \((a+b+c)^2 \lesssim a^2+b^2+c^2\),
\[
\|\hat{\theta}_{j} - {\theta}_{j}^\star \|^2_{\bSigma_j}
\lesssim B^2\delta^2 + \frac{B d \zeta}{N_\Sb} + q^2B^2 \varepsilon^2 \frac{d \zeta}{n}.
\]
Moreover, the displayed condition implies \(\lambda \gtrsim B\delta\), hence
\[
B^2\delta^2 \lesssim q^2\frac{d\zeta}{n}.
\]
Therefore,
\[
\|\hat{\theta}_{j} - {\theta}_{j}^\star \|^2_{\bSigma_j}
\lesssim \frac{B d \zeta}{mn} + \min\left(B^2\delta^2,\, q^2\frac{d\zeta}{n}\right) + q^2B^2 \varepsilon^2 \frac{d \zeta}{n}.
\]

\paragraph{Case 2: Proposition~\ref{proposition; outlier bound GLM} Does Not Apply.}
If the displayed condition fails, then
\[
\lambda \le 2\alpha_u (\tau B +1) \delta + 2 c_0 \sqrt{\frac{d \zeta}{n}} + 2 \tau c_0 \sqrt{\frac{B d \zeta}{N_\Sb}}.
\]
Since \(q \ge 8c_0\), we can absorb the middle term into the left-hand side and obtain
\[
\frac{\lambda}{2}
\le 2\alpha_u (\tau B +1) \delta + 2 \tau c_0 \sqrt{\frac{B d \zeta}{N_\Sb}}.
\]
Hence at least one of the following two alternatives must hold:
\[
\lambda \lesssim B\delta
\qquad\text{or}\qquad
\lambda \lesssim \sqrt{\frac{B d \zeta}{N_\Sb}}.
\]
Equivalently,
\[
q^2\frac{d\zeta}{n} \lesssim B^2\delta^2
\qquad\text{or}\qquad
q^2\frac{d\zeta}{n} \lesssim \frac{B d\zeta}{N_\Sb}.
\]
In either subcase,
\[
q^2\frac{d\zeta}{n}
\lesssim
\frac{B d\zeta}{mn} + \min\left(B^2\delta^2,\, q^2\frac{d\zeta}{n}\right).
\]
On the already-defined event \(\mathcal{E}_{\mathrm{safe}}^{\mathrm{glm}}\), the GLM personalization bound gives
\[
\|\hat{\theta}_{j} - {\theta}_{j}^\star \|^2_{\bSigma_j}
\lesssim \frac{d \zeta}{n} + \lambda^2
\lesssim q^2\frac{d\zeta}{n}.
\]
Combining the last two displays yields the same theorem-level bound in this regime.

This completes the proof.
\end{proof}

\section{Proof of Theorem~\ref{theorem; population MSE} (Population MSE)}\label{section; apdx proof population}

\begin{proof}
The theorem relates the in-sample MSE to the population MSE.

\paragraph{Part 1: Via Comparability.}
The first inequality $\cE_j(\hat{\theta}_j) \le \nu_j \cE_j^{\operatorname{in}}(\hat{\theta}_j)$ follows directly from the definition of the comparability constant $\nu_j$ (Definition~\ref{definition; comparability measure}) and the definition of the MSEs.
Specifically, $\|\cdot\|_{\bar{\bSigma}_j}^2 \le \nu_j \|\cdot\|_{\bSigma_j}^2$.

\paragraph{Part 2: Via Intrinsic Dimension (Safety).}
For the second inequality, we consider the case where \(\nu_j\) might be large.
Assume that the parameter domain is known to be bounded,
\(\Cb=\mathbf{B}(0,\xi)\), and that \(\theta_j^\star\in\Cb\).
Let
\[
\hat{\theta}_j^\xi
\in
\argmin_{\theta\in \mathbf{B}(0,\xi)}
\|\theta-\hat{\theta}_j\|_{\bSigma_j}^2
\]
be the \(\|\cdot\|_{\bSigma_j}\)-norm projection of \(\hat{\theta}_j\) onto
\(\mathbf{B}(0,\xi)\).

Since \(\theta_j^\star\in\mathbf{B}(0,\xi)\), the projection property gives
\[
\|\hat{\theta}_j^\xi-\theta_j^\star\|_{\bSigma_j}^2
\le
\|\hat{\theta}_j-\theta_j^\star\|_{\bSigma_j}^2
=
\cE_j^{\operatorname{in}}(\hat{\theta}_j).
\]
Moreover, both \(\hat{\theta}_j^\xi\) and \(\theta_j^\star\) belong to
\(\mathbf{B}(0,\xi)\), so
\[
\|\hat{\theta}_j^\xi-\theta_j^\star\|_2 \le 2\xi .
\]
Let \(U_j\) be the high-probability upper bound on \(\|x_{ji}\|_2\).
Applying Lemma~\ref{lemma; U/n} to the bounded estimator
\(\hat{\theta}_j^\xi\), we obtain
\[
\cE_j(\hat{\theta}_j^\xi)
\lesssim
\|\hat{\theta}_j^\xi-\theta_j^\star\|_{\bSigma_j}^2
+
\frac{U_j^2}{n}
\|\hat{\theta}_j^\xi-\theta_j^\star\|_2^2 .
\]
Combining the previous two displays yields
\[
\cE_j(\hat{\theta}_j^\xi)
\lesssim
\cE_j^{\operatorname{in}}(\hat{\theta}_j)
+
\frac{\xi^2 U_j^2}{n}.
\]
This confirms that even if the spectral ratio \(\nu_j\) diverges, the
projected estimator has population risk controlled by the in-sample risk
plus a \(1/n\)-order safety term.
\end{proof}

\section{Results for Linear Model with General Sample Size}\label{section; general sample size}

This section generalizes our main results to the setting where sample sizes $n_j$ vary across tasks.
We demonstrate that our matrix-weighted approach naturally adapts to heterogeneous information levels by scaling the regularization parameter inversely with the square root of the sample size.

Because the heterogeneous-sample-size objective aggregates the Gram matrices \(\Vb_j\), the relevant inlier geometry is their sample-size-weighted average. Accordingly, throughout this section we slightly abuse notation and write
\[
\bSigma_\Sb := \frac{1}{N_\Sb}\sum_{j \in \Sb} \Vb_j
= \sum_{j \in \Sb} \frac{n_j}{N_\Sb}\bSigma_j.
\]
The balancedness assumption in this section is interpreted with respect to this weighted inlier average, namely
\[
\bSigma_j \preceq B \bSigma_\Sb,
\qquad j \in [m].
\]
When \(n_j=n\) for all \(j\), this coincides with the original definition \(\bSigma_\Sb = |\Sb|^{-1}\sum_{j \in \Sb}\bSigma_j\).

\paragraph{Task Relatedness.}
We adopt the generalized task relatedness definition from \citet{duan2023adaptive}, which scales the closeness condition by the sample sizes.

\begin{definition}[Task Relatedness for General Sample Size]\label{assumption; general sample task relatedness}
There exist $\varepsilon, \delta_0 \geq 0$ and a subset of inliers $\Sb \subseteq [m]$ such that:
\begin{align*}
\min_{\theta \in \mathbb{R}^d} \max_{j \in \Sb} \left\{ \sqrt{n_j} \|\theta_j^{\star} - \theta\|_2 \right\} \leq \delta_0
\quad \text{and} \quad
\sum_{j \in \Sb^c} \sqrt{n_j} \leq \varepsilon \frac{N_\Sb}{\sqrt{n^\star}},
\end{align*}
where $N_\Sb := \sum_{j \in \Sb} n_j$ is the total sample size of inliers, and $n^\star := \max_{j \in \Sb} n_j$.
\end{definition}
To simplify the bounds, we define the structural constant $\alpha$ as:
\[
\alpha := \frac{\sqrt{n^\star} \sum_{j \in \Sb} \sqrt{n_j}}{N_\Sb}.
\]
Note that in the equal sample size case ($n_j = n$), we have $n^\star=n, N_\Sb = |\Sb|n$, and $\alpha = 1$, recovering the standard definition.

\subsection{Algorithm Adaptation}
Recall the task-specific loss $f_j(\theta) := \frac{1}{2n_j} \|\Yb_j - \Xb_j \theta\|_2^2$.
For heterogeneous sample sizes, we weigh the loss by the sample size $w_j = n_j$ and scale the regularization parameter as $\lambda_j = \frac{\lambda}{\sqrt{n_j}}$, where $\lambda$ is a global tuning parameter.
The resulting objective function is:
\begin{align}\label{equation; general sample loss}
\cL(\Theta) = \sum_{j=1}^m \left( \frac{1}{2} \|\Yb_j - \Xb_j \theta_j\|_2^2 + \lambda \sqrt{n_j} \|\theta_j - \beta\|_{\bSigma_j} \right).
\end{align}
We set $\Cb = \RR^d$.

\subsection{MSE Bound}
We present the main guarantee. Let $\zeta = \log(16m/\kappa)$.
We select $\lambda = q \sqrt{d \zeta}$ for a sufficiently large universal constant $q \gtrsim 1$.

\begin{theorem}[MSE Bound: General Sample Size]\label{theorem; general sample MSE}
If we run Algorithm~\ref{algorithm; MTLR} with $q \gtrsim 1$, then with probability at least $1-\kappa$:

\begin{enumerate}
\item[(a)] \textbf{Safety:} For all tasks $j \in [m]$, regardless of relatedness:
\[
\cE_j^{\operatorname{in}}(\hat{\theta}_j) \;\lesssim\; q^2 \frac{d \zeta}{n_j}.
\]
\item[(b)] \textbf{Adaptivity:} If the $(\varepsilon, \delta_0)$-task relatedness holds and the weighted balancedness assumption above is satisfied with $B \lesssim \min(1/\varepsilon, m)$, then for all inlier tasks $j \in \Sb$:
\[
\cE_j^{\operatorname{in}}(\hat{\theta}_j) \;\lesssim\; \frac{n^\star}{n_j}\frac{B d \zeta}{N_\Sb} + \frac{1}{n_j} \min\left( \alpha^2 B^2 \delta_0^2, \, q^2 d \zeta \right) + \frac{\varepsilon^2 B^2 \lambda^2}{n^\star}.
\]
\end{enumerate}
\end{theorem}

\paragraph{Discussion.}
Theorem~\ref{theorem; general sample MSE} confirms that our method's properties—Safety, Adaptivity, and Robustness—are preserved under sample size heterogeneity.
The safety statement in part (a) does not require task relatedness or weighted balancedness; when \(B\) is large or infinite, only the sharper transfer claim in part (b) becomes inactive.
The bound interpolates between the independent rate \((d/n_j)\) and a pooled variance term governed by \((n^\star/n_j)\cdot d/N_\Sb\).
This extra factor reflects the use of a single global tuning constant \(q\) across tasks with different information levels, and it disappears in the equal-sample-size regime.
Importantly, strictly weaker spectral assumptions are required compared to \citet{duan2023adaptive}, as we do not rely on minimum eigenvalue bounds.

\paragraph{Population MSE.}
In the task-wise i.i.d.\ random-design setting, the in-sample-to-population conversion in Theorem~\ref{theorem; population MSE} is taskwise and applies verbatim to Theorem~\ref{theorem; general sample MSE}, after the same standard rescaling of \(\kappa\) in \(\zeta\).
Thus, if \(\bar{\bSigma}_j \preceq \nu_j \bSigma_j\), then \(\cE_j(\hat{\theta}_j) \le \nu_j \cE_j^{\operatorname{in}}(\hat{\theta}_j)\); with a bounded parameter domain, the intrinsic-dimension safety alternative gives \(\cE_j(\hat{\theta}_j^\xi) \lesssim \cE_j^{\operatorname{in}}(\hat{\theta}_j)+\xi^2U_j^2/n_j\).

\section{Proofs for the Linear Model with General Sample Size}\label{section; proof general sample size}

We organize the heterogeneous-sample-size analysis in the same proof order as the equal-sample-size linear model: setup and notation, the inlier pooling estimator, the outlier perturbation step, and the final theorem proof.

\subsection{Setup and Notation}

Recall the task-specific loss
\[
    f_j(\theta) = \frac{1}{2n_j}\|\Yb_j - \Xb_j \theta\|_2^2,
\]
the task-wise regularization level $\lambda_j = \lambda/\sqrt{n_j}$, and the weighted objective
\[
    \cL(\Theta) = \sum_{j=1}^m \left( \frac{1}{2} \|\Yb_j - \Xb_j \theta_j\|_2^2 + \lambda \sqrt{n_j} \|\theta_j - \beta\|_{\bSigma_j} \right).
\]
We work on the unconstrained domain $\Cb = \RR^d$ and define
\begin{align*}
    g_j(\beta) &:= (f_j \star \lambda_j \|\cdot\|_{\bSigma_j})(\beta), \\
    F_\Sb(\beta) &:= \sum_{j \in \Sb} n_j f_j(\beta), \\
    G_\Sb(\beta) &:= \sum_{j \in \Sb} n_j g_j(\beta), \\
    L(\beta) &:= \sum_{j \in \Sb^c} n_j g_j(\beta), \\
    G(\beta) &:= G_\Sb(\beta) + L(\beta).
\end{align*}
Let
\[
    \bSigma_\Sb := \frac{1}{N_\Sb} \sum_{j \in \Sb} \Vb_j,
\]
Throughout this appendix, the balancedness assumption is interpreted with this weighted inlier covariance, namely \(\bSigma_j \preceq B \bSigma_\Sb\) for all \(j \in [m]\).
As before, the invariant region is
\[
    R_j := \left\{ \beta \in \Cb \mid f_j(\beta) = g_j(\beta) \right\}, \qquad j \in [m].
\]
As in the equal-sample-size appendix, we work after restricting to \(\mathrm{Range}(\bSigma_\Sb)\), so without loss of generality \(\bSigma_\Sb \succ 0\).

\paragraph{Pooled Whitening Notation.}
We use the pooled whitening map
\[
    \bar v := \bSigma_\Sb^{1/2}v,
    \qquad v\in\RR^d.
\]
For any function \(h:\RR^d \to \RR\), we define its pooled-whitened version by
\[
    \bar{h}(\bar v) := h(\bSigma_\Sb^{-1/2}\bar v).
\]
Thus \(\bar\theta\), \(\bar\beta\), \(\bar\theta^\star\), \(\bar\theta_j^\star\), \(\bar{\hat\beta}_{F_\Sb}\), \(\bar{\hat\beta}_{G_\Sb}\), and \(\bar{\hat\beta}_G\) are all instances of the same pooled whitening map. In particular, we write \(\bar{F}_\Sb\), \(\bar{G}_\Sb\), \(\bar{L}\), and \(\bar{G}\) for the transformed objectives.



\subsection{The Inlier Pooling Estimator}

We first characterize the inlier-only estimator and identify a regime where the regularized inlier objective collapses to the same minimizer.

\begin{lemma}[Error Bound of Pooling Estimator]\label{lemma; pooling general sample}
    With probability at least $1-\frac{\kappa}{4}$, the pooling estimator $\hat{\beta}_{F_\Sb}$ satisfies simultaneously for all \(j\in\Sb\):
    \[
        \|\hat{\beta}_{F_{\Sb}} - \theta^\star\|_{\bSigma_j} \leq \alpha\frac{B \delta_0 }{\sqrt{n^\star}} + c_0 \sqrt{\frac{B d \zeta}{N_\Sb}}.
    \]
    Consequently, for each $j\in \Sb$,
    \[
        \|\hat{\beta}_{F_{\Sb}} - \theta_j^\star\|_{\bSigma_j}
        \lesssim \alpha\frac{B \delta_0 }{\sqrt{n_j}} + \sqrt{\frac{B d \zeta}{N_\Sb}}.
    \]
\end{lemma}

\begin{proof}
    Recall $\hat{\beta}_{F_\Sb} = \Vb_\Sb^{-1} \sum_{k \in \Sb} \Xb_k^\top \Yb_k$ and write
    \[
        \|\hat{\beta}_{F_{\Sb}} - \theta^\star\|_{\bSigma_j} \le \text{Bias}_j + \text{Variance}_j.
    \]

    \paragraph{Bias Term.}
    Let $\eta_k^\star := \theta_k^\star - \theta^\star$ and
    \(
        a := \sum_{k \in \Sb} \Vb_k \eta_k^\star.
    \)
    Then $\text{Bias}_j = \| \Vb_\Sb^{-1} a \|_{\bSigma_j}$.
    Using $\bSigma_j \preceq B \bSigma_\Sb = \frac{B}{N_\Sb}\Vb_\Sb$, we have
    \[
        \text{Bias}_j^2
        \le \frac{B}{N_\Sb} \bigl\| \Vb_\Sb^{-1/2} a \bigr\|_2^2.
    \]
    Next, by $\bSigma_k \preceq B \bSigma_\Sb$ we have $\Vb_k \preceq \frac{n_k B}{N_\Sb} \Vb_\Sb$, hence
    \[
        \bigl\| \Vb_\Sb^{-1/2} \Vb_k \eta_k^\star \bigr\|_2
        \le \sqrt{\frac{n_k B}{N_\Sb}} \, \|\eta_k^\star\|_{\Vb_k}.
    \]
    Therefore,
    \[
        \bigl\| \Vb_\Sb^{-1/2} a \bigr\|_2
        \le \sum_{k \in \Sb} \bigl\| \Vb_\Sb^{-1/2} \Vb_k \eta_k^\star \bigr\|_2
        \le \sqrt{\frac{B}{N_\Sb}} \sum_{k \in \Sb} n_k \|\eta_k^\star\|_{\bSigma_k}.
    \]
    Under the bounded covariate assumption, $\|\eta_k^\star\|_{\bSigma_k} \le \|\eta_k^\star\|_2$, and the task-relatedness condition gives
    $\sqrt{n_k}\|\eta_k^\star\|_2 \le \delta_0$. Hence
    \[
        \text{Bias}_j
        \le \frac{B}{N_\Sb} \sum_{k \in \Sb} \sqrt{n_k}\,\delta_0
        = \alpha \frac{B\delta_0}{\sqrt{n^\star}}.
    \]

    \paragraph{Variance Term.}
    Using Hanson--Wright with failure level \(\kappa/(4m)\) for each \(j\in\Sb\), a union bound, and $\bSigma_j \preceq \frac{B}{N_\Sb} \Vb_\Sb$,
    \[
        \text{Variance}_j \le c_0 \sqrt{\tr(\bSigma_j \Vb_\Sb^{-1}) \zeta} \le c_0 \sqrt{\frac{B d \zeta}{N_\Sb}}.
    \]

    For the task-specific error, apply triangle inequality:
    \[
        \|\hat{\beta}_{F_{\Sb}} - \theta_j^\star\|_{\bSigma_j}
        \le \|\hat{\beta}_{F_{\Sb}} - \theta^\star\|_{\bSigma_j} + \|\theta^\star-\theta_j^\star\|_{\bSigma_j}.
    \]
    The first term is bounded above. For the second, $\|\theta^\star-\theta_j^\star\|_{\bSigma_j}\le \|\theta^\star-\theta_j^\star\|_2 \le \delta_0/\sqrt{n_j}$ by definition of task relatedness.
    Since $\alpha B\ge 1$, this yields
    \[
        \|\hat{\beta}_{F_{\Sb}} - \theta_j^\star\|_{\bSigma_j}
        \lesssim \alpha\frac{B \delta_0 }{\sqrt{n_j}} + \sqrt{\frac{B d \zeta}{N_\Sb}}.
    \]
\end{proof}

\begin{proposition}[Equivalence of Pooling Estimators: General Sample Size]\label{proposition; pooling range general sample}
    There is a universal constant \(C_{\mathrm{gs}}\) such that the following holds. Suppose for all $j \in \Sb$,
    \[
        \frac{\lambda}{\sqrt{n_j}} > C_{\mathrm{gs}}\left(
        \alpha B \frac{\delta_0}{\sqrt{n_j}} + c_0\sqrt{\frac{Bd\zeta}{N_\Sb}} + c_0\sqrt{\frac{d \zeta}{n_j}}
        \right).
    \]
    Then, with probability at least $1-\frac{\kappa}{2}$, $\hat{\beta}_{F_\Sb} \in R_j$ for all $j\in \Sb$, and $\hat{\beta}_{F_\Sb}$ minimizes $G_\Sb$.
    In particular, we may choose $\hat{\beta}_{G_\Sb}=\hat{\beta}_{F_\Sb}$.
\end{proposition}

\begin{proof}
    Let \(\mathcal{E}_{\mathrm{pool}}^{\mathrm{gs}}\) be the event from Lemma~\ref{lemma; pooling general sample}, which has probability at least \(1-\kappa/4\).
    Let \(\mathcal{E}_{\mathrm{inv}}^{\mathrm{gs}}\) be the event that the taskwise invariant-region noise bound from Proposition~\ref{proposition; invariant region linear} holds for all \(j\in\Sb\), each invoked with failure level \(\kappa/(4m)\).
    Then \(\PP(\mathcal{E}_{\mathrm{pool}}^{\mathrm{gs}}\cap\mathcal{E}_{\mathrm{inv}}^{\mathrm{gs}})\ge1-\kappa/2\).
    On this intersection, it suffices to verify for each $j\in \Sb$:
    \[
        \frac{\lambda}{\sqrt{n_j}} > \|\theta_j^\star-\hat{\beta}_{F_\Sb}\|_{\bSigma_j} + c_0\sqrt{\frac{d\zeta}{n_j}}.
    \]
    We bound the first term by triangle inequality:
    \[
        \|\theta_j^\star-\hat{\beta}_{F_\Sb}\|_{\bSigma_j}
        \le \|\theta_j^\star-\theta^\star\|_{\bSigma_j} + \|\theta^\star-\hat{\beta}_{F_\Sb}\|_{\bSigma_j}.
    \]
    Since $\|\bSigma_j\|_{\op}\le 1$ and $\sqrt{n_j}\|\theta_j^\star-\theta^\star\|_2\le \delta_0$, we have
    \[
        \|\theta_j^\star-\theta^\star\|_{\bSigma_j}\le \frac{\delta_0}{\sqrt{n_j}}.
    \]
    By Lemma~\ref{lemma; pooling general sample},
    \[
        \|\theta^\star-\hat{\beta}_{F_\Sb}\|_{\bSigma_j}
        \le \alpha\frac{B\delta_0}{\sqrt{n^\star}} + c_0\sqrt{\frac{Bd\zeta}{N_\Sb}}
        \le \alpha\frac{B\delta_0}{\sqrt{n_j}} + c_0\sqrt{\frac{Bd\zeta}{N_\Sb}}.
    \]
    Combining the last three displays and using \(\alpha B\ge 1\) (we may assume \(B\ge1\)), the assumed lower bound on \(\lambda/\sqrt{n_j}\) implies \(\hat{\beta}_{F_\Sb}\in R_j\) for all \(j\in \Sb\).
    For each \(j\in\Sb\), define the positive slack
    \[
        \Delta_j^{\mathrm{gs}}
        :=
        \frac{\lambda}{\sqrt{n_j}}
        -
        \left(
        \|\theta_j^\star-\hat{\beta}_{F_\Sb}\|_{\bSigma_j}
        + c_0\sqrt{\frac{d\zeta}{n_j}}
        \right)
        >0.
    \]
    Since \(\beta\mapsto \|\theta_j^\star-\beta\|_{\bSigma_j}\) is continuous and the stochastic term in Proposition~\ref{proposition; invariant region linear} does not depend on \(\beta\), there exists \(r_j>0\) such that
    \[
        \|\beta-\hat{\beta}_{F_\Sb}\|_2<r_j
        \quad\Longrightarrow\quad
        \frac{\lambda}{\sqrt{n_j}}
        >
        \|\theta_j^\star-\beta\|_{\bSigma_j}
        + c_0\sqrt{\frac{d\zeta}{n_j}}.
    \]
    Hence Proposition~\ref{proposition; invariant region linear} implies \(f_j(\beta)=g_j(\beta)\) throughout the Euclidean ball \(B_{r_j}(\hat{\beta}_{F_\Sb})\).
    Let \(r:=\min_{j\in\Sb} r_j>0\). Then
    \[
        F_\Sb(\beta)=G_\Sb(\beta)
        \qquad\text{for all }\beta\in B_r(\hat{\beta}_{F_\Sb}).
    \]
    Since \(F_\Sb\) is strictly convex with Hessian \(N_\Sb \bSigma_\Sb \succ 0\), \(\hat{\beta}_{F_\Sb}\) is its unique minimizer, and therefore a local minimizer of \(G_\Sb\) as well.
    By convexity, this local minimizer is global, so \(\hat{\beta}_{F_\Sb}\) minimizes \(G_\Sb\).
    This proves the claimed statement on \(\mathcal{E}_{\mathrm{pool}}^{\mathrm{gs}}\cap\mathcal{E}_{\mathrm{inv}}^{\mathrm{gs}}\), whose probability is at least \(1-\kappa/2\).
\end{proof}

\subsection{A Perturbation Bound for Outliers}

We next control the passage from the inlier objective $G_\Sb$ to the full objective $G = G_\Sb + L$, where \(L\) denotes the aggregate outlier contribution introduced in the setup.

\begin{claim}\label{claim; general sample case}
    Assume $\varepsilon < \frac{1}{3B}$.
    With the same constant \(C_{\mathrm{gs}}\) as in Proposition~\ref{proposition; pooling range general sample}, suppose
    \[
        \frac{\lambda}{\sqrt{n_j}} > C_{\mathrm{gs}}\left(
        \alpha B \frac{\delta_0}{\sqrt{n_j}} + c_0\sqrt{\frac{Bd\zeta}{N_\Sb}} + c_0\sqrt{\frac{d \zeta}{n_j}}
        \right)
    \]
    for all $j \in \Sb$.
    On the event where Proposition~\ref{proposition; pooling range general sample}, Lemma~\ref{lemma; pooling general sample}, and the taskwise invariant-region noise bounds hold,
    for all $\beta$ such that $\|\bar{\beta} - \bar{\hat{\beta}}_{G_\Sb}\|_2 \leq \frac{\lambda}{2\sqrt{B n^\star}}$, we have
    \[
        \nabla^2 \bar{G}_\Sb(\bar{\beta}) \succeq N_\Sb \Ib_d.
    \]
\end{claim}

\begin{proof}
    The proof follows the same logic as the equal-sample-size case, but we verify the weighted scaling explicitly.
    Fix $\beta$ such that $\|\bar{\beta} - \bar{\hat{\beta}}_{G_\Sb}\|_2 \le \frac{\lambda}{2\sqrt{B n^\star}}$.
    For any $j \in \Sb$, using $\bSigma_j \preceq B\bSigma_\Sb$:
    \begin{align*}
        \|\beta - \hat{\beta}_{G_\Sb}\|_{\bSigma_j}
        &\le \sqrt{B}\|\beta - \hat{\beta}_{G_\Sb}\|_{\bSigma_\Sb}
        = \sqrt{B}\|\bar{\beta} - \bar{\hat{\beta}}_{G_\Sb}\|_2 \\
        &\le \frac{\lambda}{2\sqrt{n^\star}}
        \le \frac{\lambda}{2\sqrt{n_j}}.
    \end{align*}
    By Proposition~\ref{proposition; pooling range general sample}, we have $\hat{\beta}_{G_\Sb}=\hat{\beta}_{F_\Sb}$.
    Hence, by Lemma~\ref{lemma; pooling general sample},
    \[
        \|\hat{\beta}_{G_\Sb} - \theta_j^\star\|_{\bSigma_j}
        \lesssim \alpha \frac{B\delta_0}{\sqrt{n_j}} + \sqrt{\frac{Bd\zeta}{N_\Sb}}.
    \]
    Hence
    \begin{align*}
        \|\beta - \theta_j^\star\|_{\bSigma_j}
        &\lesssim \frac{\lambda}{2\sqrt{n_j}}
        + \alpha \frac{B\delta_0}{\sqrt{n_j}}
        + \sqrt{\frac{Bd\zeta}{N_\Sb}}.
    \end{align*}
    Proposition~\ref{proposition; invariant region linear} (applied with task-wise $\lambda_j=\lambda/\sqrt{n_j}$) requires
    \[
        \frac{\lambda}{\sqrt{n_j}} > \|\beta-\theta_j^\star\|_{\bSigma_j} + c_0\sqrt{\frac{d\zeta}{n_j}}.
    \]
    The displayed assumption, with \(C_{\mathrm{gs}}\) chosen sufficiently large, leaves enough slack after the \(\lambda/(2\sqrt{n_j})\) term to verify this condition.
    Therefore $\beta \in R_j$ for all $j \in \Sb$, so $G_\Sb(\beta)=F_\Sb(\beta)$ locally.
    Consequently, $\nabla^2 \bar{G}_\Sb(\bar{\beta})=\nabla^2 \bar{F}_\Sb(\bar{\beta})=N_\Sb \Ib_d$.
\end{proof}

\begin{proposition}[Key Proposition: General Sample Size]\label{proposition; general sample outlier}
    Assume $\varepsilon < \frac{1}{3B}$.
    With the same universal constant \(C_{\mathrm{gs}}\), suppose the regularization parameter satisfies
    \[
        \frac{\lambda}{\sqrt{n_j}} > C_{\mathrm{gs}}\left(
        \alpha B \frac{\delta_0}{\sqrt{n_j}} + c_0\sqrt{\frac{Bd\zeta}{N_\Sb}} + c_0\sqrt{\frac{d \zeta}{n_j}}
        \right)
    \]
    for all $j \in \Sb$, then with probability at least $1-\kappa$:
    \begin{enumerate}
        \item The pooled center satisfies
        \[
            \|\hat{\beta}_G - \theta_j^\star \|_{\bSigma_j} \lesssim \alpha\frac{B\delta_0}{\sqrt{n_j}} + \sqrt{\frac{Bd \zeta}{N_\Sb}} + \frac{\varepsilon B \lambda}{\sqrt{n^\star}}.
        \]
        \item Furthermore,
        \[
            \|\hat{\theta}_j-\hat{\beta}_{G}\|_{\bSigma_j}=0,
            \qquad
            \|\hat{\theta}_j-\theta_j^\star\|_{\bSigma_j}
            =
            \|\hat{\beta}_{G}-\theta_j^\star\|_{\bSigma_j}
        \]
        for all $j \in \Sb$.
    \end{enumerate}
\end{proposition}

\begin{proof}
    The proof strategy mirrors Proposition~\ref{proposition; outlier bound}, adapted for weighted sums.
    Let \(\mathcal{E}_{\mathrm{gs}}\) be the good event from Proposition~\ref{proposition; pooling range general sample}: the pooling estimator bound and all taskwise invariant-region noise bounds hold.
    The pooled event is allocated failure \(\kappa/4\), and the taskwise events are allocated failure \(\kappa/(4m)\) each, so \(\PP(\mathcal{E}_{\mathrm{gs}})\ge1-\kappa/2\ge1-\kappa\).
    Using the pooled whitening notation introduced above, let
    \[
        \bar{\hat{\beta}}_G := \bSigma_\Sb^{1/2}\hat{\beta}_G,
        \qquad
        \bar{\hat{\beta}}_{G_\Sb} := \bSigma_\Sb^{1/2}\hat{\beta}_{G_\Sb}.
    \]

    \paragraph{Step 1: Strong Convexity.}
    The aggregate inlier loss is $F_\Sb(\beta) = \sum_{j \in \Sb} \frac{1}{2} \|\Yb_j - \Xb_j \beta\|_2^2$.
    By Proposition~\ref{proposition; pooling range general sample}, we may set $\hat{\beta}_{G_\Sb}=\hat{\beta}_{F_\Sb}$ on the high-probability event.
    The Hessian of the transformed inlier loss is
    \[
        \nabla^2 \bar{F}_\Sb(\bar{\beta}) = \bSigma_\Sb^{-1/2} \left( \sum_{j \in \Sb} \Xb_j^\top \Xb_j \right) \bSigma_\Sb^{-1/2} = \bSigma_\Sb^{-1/2} (N_\Sb \bSigma_\Sb) \bSigma_\Sb^{-1/2} = N_\Sb \Ib_d.
    \]
    Thus, $\bar{F}_\Sb$ is $N_\Sb$-strongly convex. By Claim~\ref{claim; general sample case}, this strong convexity holds for $\bar{G}_\Sb$ in the relevant neighborhood.

    \paragraph{Step 2: Lipschitz Constant of Outliers.}
    We bound the Lipschitz constant of the transformed outlier term $\bar{L}(\cdot) = \sum_{j \in \Sb^c} n_j \bar{g}_j(\cdot)$.
    From Lemma~\ref{lemma; transformed loss Lipschitz upper bound}, $\bar{g}_j$ is $\sqrt{B}\lambda_j$-Lipschitz.
    Thus, $n_j \bar{g}_j$ is $n_j \sqrt{B} (\lambda/\sqrt{n_j}) = \sqrt{n_j} \sqrt{B} \lambda$-Lipschitz.
    Summing over outliers:
    \[
        \operatorname{Lip}(\bar{L}) \le \sum_{j \in \Sb^c} \sqrt{B} \lambda \sqrt{n_j} = \sqrt{B} \lambda \sum_{j \in \Sb^c} \sqrt{n_j}.
    \]
    Using the task-relatedness definition ($\sum_{\Sb^c} \sqrt{n_j} \le \varepsilon \frac{N_\Sb}{\sqrt{n^\star}}$):
    \[
        \operatorname{Lip}(\bar{L}) \le \frac{\varepsilon \sqrt{B} \lambda N_\Sb}{\sqrt{n^\star}}.
    \]

    \paragraph{Step 3: Perturbation Bound.}
    We apply Lemma~\ref{lemma; ARMUL effect outlier} with $\rho = N_\Sb$ and radius
    \[
        r = \frac{\lambda}{2\sqrt{B n^\star}},
    \]
    for which Claim~\ref{claim; general sample case} guarantees local strong convexity of $\bar{G}_\Sb$.
    The perturbation condition requires $\operatorname{Lip}(\bar{L}) < \rho r$. Using the bound above,
    \[
        \operatorname{Lip}(\bar{L})
        \le \frac{\varepsilon \sqrt{B} \lambda N_\Sb}{\sqrt{n^\star}}
        = 2\varepsilon B \, \rho r.
    \]
    Since $\varepsilon < \frac{1}{3B}$, the condition holds. The lemma yields
    \[
        \|\bar{\hat{\beta}}_G - \bar{\hat{\beta}}_{G_\Sb}\|_2 \le \frac{\operatorname{Lip}(\bar{L})}{\rho} \le \frac{\varepsilon \sqrt{B} \lambda}{\sqrt{n^\star}}.
    \]
    Converting to the $\bSigma_j$-norm,
    \[
        \|\hat{\beta}_G - \hat{\beta}_{G_\Sb}\|_{\bSigma_j} \le \sqrt{B} \|\hat{\beta}_G - \hat{\beta}_{G_\Sb}\|_{\bSigma_\Sb} \le \frac{\varepsilon B \lambda}{\sqrt{n^\star}}.
    \]

    \paragraph{Step 4: Combining Errors.}
    Combining this with the pooling estimator error (Lemma~\ref{lemma; pooling general sample}):
    \begin{align*}
        \|\hat{\beta}_G - \theta_j^\star\|_{\bSigma_j}
        &\le \|\hat{\beta}_G - \hat{\beta}_{G_\Sb}\|_{\bSigma_j} + \|\hat{\beta}_{G_\Sb} - \theta_j^\star\|_{\bSigma_j} \\
        &= \|\hat{\beta}_G - \hat{\beta}_{G_\Sb}\|_{\bSigma_j} + \|\hat{\beta}_{F_\Sb} - \theta_j^\star\|_{\bSigma_j} \\
        &\lesssim \frac{\varepsilon B \lambda}{\sqrt{n^\star}} + \alpha \frac{B\delta_0}{\sqrt{n_j}} + \sqrt{\frac{B d \zeta}{N_\Sb}}.
    \end{align*}

    \paragraph{Step 5: Invariant Region for the Full Estimator.}
    It remains to justify the zero-seminorm personalization statement for inlier tasks.
    Proposition~\ref{proposition; invariant region linear}, with taskwise regularization \(\lambda_j=\lambda/\sqrt{n_j}\), requires
    \[
        \frac{\lambda}{\sqrt{n_j}}
        >
        \|\hat{\beta}_G-\theta_j^\star\|_{\bSigma_j}
        + c_0\sqrt{\frac{d\zeta}{n_j}}.
    \]
    The deterministic part of the displayed assumption, with \(C_{\mathrm{gs}}\) sufficiently large, controls the terms
    \(\alpha B\delta_0/\sqrt{n_j}\), \(\sqrt{Bd\zeta/N_\Sb}\), and \(c_0\sqrt{d\zeta/n_j}\).
    The perturbation term is absorbed by the small-contamination condition:
    since \(n_j\le n^\star\),
    \[
        \frac{\varepsilon B\lambda}{\sqrt{n^\star}}
        \le
        \varepsilon B \frac{\lambda}{\sqrt{n_j}}
        \le
        \frac{1}{3}\frac{\lambda}{\sqrt{n_j}}.
    \]
    Thus \(\hat{\beta}_G\in R_j\) for every \(j\in\Sb\), which implies that every task-specific minimizer at center \(\hat{\beta}_G\) satisfies \(\|\hat{\theta}_j-\hat{\beta}_G\|_{\bSigma_j}=0\).
    Hence the corresponding prediction-seminorm errors coincide, so the pooled-center error bound above also gives the stated bound for \(\hat{\theta}_j\).
\end{proof}

\subsection{Proof of Theorem~\ref{theorem; general sample MSE}}

\begin{proof}
    Recall \(\lambda = q\sqrt{d \zeta}\).
    Since \(q \gtrsim 1\), we may choose the implicit constant so that \(q \ge 8c_0\).
    Let \(\mathcal{E}_{\mathrm{safe}}^{\mathrm{gs}}\) be the event obtained by applying the personalization bound taskwise with failure probability \(\kappa/(2m)\).
    Then \(\PP(\mathcal{E}_{\mathrm{safe}}^{\mathrm{gs}})\ge1-\kappa/2\), and on this event, for every task \(j\in[m]\),
    \[
        \|\hat{\theta}_j-\theta_j^\star\|_{\bSigma_j}^2
        \lesssim \frac{d\zeta}{n_j}+\frac{\lambda^2}{n_j}
        \lesssim q^2\frac{d\zeta}{n_j}.
    \]
    This proves part~(a).

    \paragraph{Case 1: Proposition~\ref{proposition; general sample outlier} Applies.}
    Because the inequality in Proposition~\ref{proposition; general sample outlier} is hardest when \(n_j=n^\star\), it suffices to assume
    \[
        \frac{\lambda}{\sqrt{n^\star}} > C_{\mathrm{gs}}\left(
        \alpha B \frac{\delta_0}{\sqrt{n^\star}} + c_0\sqrt{\frac{Bd\zeta}{N_\Sb}} + c_0\sqrt{\frac{d \zeta}{n^\star}}
        \right).
    \]
    Indeed, after multiplying both sides by \(\sqrt{n_j}\), the only \(n_j\)-dependent term is the pooling-variance contribution \(c_0\sqrt{n_jBd\zeta/N_\Sb}\), which is largest at \(n_j=n^\star\).
    Then Proposition~\ref{proposition; general sample outlier} applies.
    Its proof constructs a transfer event \(\mathcal{E}_{\mathrm{transfer}}^{\mathrm{gs}}\) with \(\PP(\mathcal{E}_{\mathrm{transfer}}^{\mathrm{gs}})\ge1-\kappa/2\) under the present good-event budget.
    On \(\mathcal{E}_{\mathrm{safe}}^{\mathrm{gs}}\cap\mathcal{E}_{\mathrm{transfer}}^{\mathrm{gs}}\), which has probability at least \(1-\kappa\), for every \(j\in \Sb\),
    \[
        \|\hat{\theta}_j - \theta_j^\star\|_{\bSigma_j}
        \lesssim \alpha\frac{B\delta_0}{\sqrt{n_j}} + \sqrt{\frac{Bd \zeta}{N_\Sb}} + \frac{\varepsilon B \lambda}{\sqrt{n^\star}}.
    \]
    Squaring yields
    \[
        \|\hat{\theta}_j - \theta_j^\star\|_{\bSigma_j}^2
        \lesssim
        \alpha^2B^2\frac{\delta_0^2}{n_j}
        +\frac{Bd\zeta}{N_\Sb}
        +\frac{\varepsilon^2B^2\lambda^2}{n^\star}.
    \]
    Moreover, the displayed condition implies \(\alpha B\delta_0 \lesssim \lambda=q\sqrt{d\zeta}\), so the heterogeneity term may be replaced, up to constants, by
    \[
        \frac{1}{n_j}\min\left(\alpha^2B^2\delta_0^2,\ q^2d\zeta\right).
    \]
    Since \(n_j\le n^\star\), the pooling term satisfies
    \[
        \frac{Bd\zeta}{N_\Sb}
        \le
        \frac{n^\star}{n_j}\frac{Bd\zeta}{N_\Sb}.
    \]
    Therefore, on \(\mathcal{E}_{\mathrm{safe}}^{\mathrm{gs}}\cap\mathcal{E}_{\mathrm{transfer}}^{\mathrm{gs}}\),
    \[
        \|\hat{\theta}_j - \theta_j^\star\|_{\bSigma_j}^2
        \lesssim
        \frac{n^\star}{n_j}\frac{Bd\zeta}{N_\Sb}
        +
        \frac{1}{n_j}\min\left(\alpha^2B^2\delta_0^2,\ q^2d\zeta\right)
        +
        \frac{\varepsilon^2B^2\lambda^2}{n^\star}.
    \]

    \paragraph{Case 2: Proposition~\ref{proposition; general sample outlier} Does Not Apply.}
    If the displayed condition fails, then
    \[
        \frac{\lambda}{\sqrt{n^\star}}
        \le C_{\mathrm{gs}}\left(
        \alpha B \frac{\delta_0}{\sqrt{n^\star}} + c_0\sqrt{\frac{Bd\zeta}{N_\Sb}} + c_0\sqrt{\frac{d \zeta}{n^\star}}
        \right).
    \]
    Since \(q \gtrsim 1\) is chosen large enough relative to \(C_{\mathrm{gs}}c_0\), we absorb the last term into the left-hand side and obtain
    \[
        \frac{\lambda}{2\sqrt{n^\star}}
        \lesssim \alpha B \frac{\delta_0}{\sqrt{n^\star}} + \sqrt{\frac{Bd\zeta}{N_\Sb}}.
    \]
    Therefore at least one of the following alternatives must hold:
    \[
        \frac{\lambda}{\sqrt{n^\star}} \lesssim \alpha B \frac{\delta_0}{\sqrt{n^\star}}
        \qquad\text{or}\qquad
        \frac{\lambda}{\sqrt{n^\star}} \lesssim \sqrt{\frac{Bd\zeta}{N_\Sb}}.
    \]
    The first alternative implies, for every \(j\in\Sb\),
    \[
        q^2\frac{d\zeta}{n_j}
        =
        \frac{\lambda^2}{n_j}
        \lesssim
        \alpha^2B^2\frac{\delta_0^2}{n_j}.
    \]
    The second alternative implies
    \[
        q^2 \frac{d \zeta}{n^\star} \lesssim \frac{B d \zeta}{N_\Sb}
        \qquad\Longrightarrow\qquad
        q^2\frac{d\zeta}{n_j}
        =
        \frac{n^\star}{n_j}q^2\frac{d\zeta}{n^\star}
        \lesssim
        \frac{n^\star}{n_j}\frac{Bd\zeta}{N_\Sb}.
    \]
    Hence, in either subcase, the safety rate obeys
    \[
        q^2\frac{d\zeta}{n_j}
        \lesssim
        \frac{n^\star}{n_j}\frac{Bd\zeta}{N_\Sb}
        +
        \frac{1}{n_j}\min\left(\alpha^2B^2\delta_0^2,\ q^2d\zeta\right).
    \]

    On the already-defined event \(\mathcal{E}_{\mathrm{safe}}^{\mathrm{gs}}\), the personalization bound with \(\lambda_j=\lambda/\sqrt{n_j}\) gives
    \[
        \|\hat{\theta}_j - \theta_j^\star\|_{\bSigma_j}
        \lesssim \lambda_j + \sqrt{\frac{d\zeta}{n_j}}
        \lesssim q\sqrt{\frac{d\zeta}{n_j}},
    \]
    so
    \[
        \|\hat{\theta}_j - \theta_j^\star\|_{\bSigma_j}^2
        \lesssim
        q^2\frac{d\zeta}{n_j}.
    \]
    Combining the last two displays yields
    \[
        \|\hat{\theta}_j - \theta_j^\star\|_{\bSigma_j}^2
        \lesssim
        \frac{n^\star}{n_j}\frac{Bd\zeta}{N_\Sb}
        +
        \frac{1}{n_j}\min\left(\alpha^2B^2\delta_0^2,\ q^2d\zeta\right).
    \]
    Adding the nonnegative outlier-robustness term
    \(\varepsilon^2B^2\lambda^2/n^\star\) gives the claimed bound in part~(b).
\end{proof}

\section{Details for Sample Complexity of Second Moment Concentration}\label{section; detail sample complexity}

We discuss in more detail the sample complexity of covariance comparability, initially covered in Section~\ref{section; data assumption}.
We generically investigate the sample complexity required for the empirical second moment and the expected second moment to become comparable for a distribution \(x \sim \cP\).

Let \(x_1, \dots, x_n\) be \(n\) i.i.d.\ samples drawn from \(\cP\). We define the empirical second moment matrix \(\bSigma\) and the population second moment matrix \(\bar{\bSigma}\) as:
\begin{align*}
\bSigma := \frac{1}{n}\sum_{i=1}^n x_ix_i^\top, \quad \text{and} \quad \bar{\bSigma}:= \EE_{x \sim \cP}[xx^\top].
\end{align*}
Our goal is to find a constant \(\nu > 0\) such that, with high probability over the \(n\) samples, the following spectral ordering holds:
\begin{align*}
\nu^{-1} \bSigma \preceq \bar \bSigma \preceq \nu \bSigma.
\end{align*}
Furthermore, we aim to determine the sample complexity \(n\) required to achieve \(\nu = \tilde\cO(1)\).

In Section~\ref{subsection; assumption example expected second moment}, we demonstrated that for many standard distributions (which we categorize as \textbf{Type 1}), the sample complexity is $n = \tilde{\Omega}(d)$.
We briefly summarize these before discussing the more general \textbf{Type 2} distributions.

\paragraph{Type 1 Distributions.}
For this class, if \(n = \tilde\Omega(d)\), comparability holds with \(\nu = \cO(1)\). This class is characterized by properties discussed in \citep{oliveira2016lower}:
\begin{enumerate}[]
\item Every coordinate of \(\bar{\bSigma}^{-\frac{1}{2}}x\) has 9th moments bounded by \(\cO(1)\).
\item A notable subset includes strongly sub-Gaussian vectors, where \(v^\top x\) is sub-Gaussian with proxy variance \(c v^\top \bar{\bSigma} v\) for some \(c = \cO(1)\).
\end{enumerate}
This encompasses Gaussian, uniform distributions, and cases with independently sub-Gaussian coordinates.

\paragraph{Type 2 Distributions.}
We now present the sample complexity for a more general sub-exponential class.
We proceed under the assumption that the norm \(\|x\|_2\) concentrates.

\begin{definition}[High-probability bound of \(\|x\|_2\)]\label{definition; hp norm bound}
We assume there exists a parameter \(U>0\) such that for some absolute constant \(c>0\):
\begin{align*}
\PP\left[ \frac{\|x\|_2}{U} > t \right] \le \exp(-ct).
\end{align*}
\end{definition}
Note that if \(\|x\|_{\psi_1} \le C_{\psi_1}\), we typically have \(U = \tilde{\cO}(\sqrt{d} C_{\psi_1})\). However, \(U\) can be significantly smaller than \(d\), depending on the \textit{intrinsic dimension} (often related to $\tr(\bar{\bSigma})$).

\begin{definition}[Minimum non-zero eigenvalue]
Let \(\gamma\) be the minimum non-zero eigenvalue of the population covariance \(\bar{\bSigma}\).
\end{definition}

Our main result for Type 2 distributions states that we achieve comparability with a constant factor $\nu = 6$ provided $n = \tilde{\Omega}(U^2/\gamma)$.

\begin{lemma}[Sample complexity of comparability]\label{lemma; sample complexity}
Assume the high-probability bound on $\|x\|_2$ holds. If
\begin{align*}
n \gtrsim \frac{U^2}{\gamma}\log^3\!\left(\frac{nU}{\gamma \kappa}\right),
\end{align*}
then with probability at least \(1-\kappa\),
\begin{align*}
\frac{1}{6} \bar{\bSigma}\preceq  {\bSigma} \preceq 6 \bar{\bSigma}.
\end{align*}
\end{lemma}
This indicates that the minimum eigenvalue \(\gamma\) affects the sample complexity requirement but does not degrade the constant factor in the spectral bound once the sample size is sufficient.

\paragraph{Proof of Lemma~\ref{lemma; sample complexity}}
Without loss of generality, we assume \(\bar{\bSigma}\) is full-rank. If not, the analysis restricts to the subspace spanned by the support of $\cP$.
We define a truncation radius
\begin{align*}
K := A U \log \left(\frac{nU}{\gamma \kappa}\right)
\end{align*}
for a sufficiently large constant \(A\).
We define the truncated distribution \(\check{\cP}\) as the distribution of \(x\) conditioned on the event \(\cE_{\text{trunc}} := \{ \|x\|_2 \le K \}\).
Let \(\check{\bSigma} := \EE_{x \sim \check{\cP}}[xx^\top]\).

Consider the event \(\cE_{\text{samples}} := \{ \forall i \in [n], \|x_i\|_2 \le K \}\).
By the union bound and the definition of $U$:
\begin{align*}
\PP(\cE_{\text{samples}}^c) \le \sum_{i=1}^n \PP(\|x_i\|_2 > K) \le n \exp\left( -c \frac{K}{U} \right) \le \kappa,
\end{align*}
provided $A$ is chosen large enough.
Conditioned on \(\cE_{\text{samples}}\), the samples \(x_1, \dots, x_n\) can be treated as i.i.d.\ draws from the truncated distribution \(\check{\cP}\).

We apply the Matrix Bernstein inequality to the whitened truncated variables. Let \(z_i := \check{\bSigma}^{-1/2} x_i\). Under truncation, we verify the operator norm bound:
\begin{align*}
\| \check{\bSigma}^{-1/2} x_i x_i^\top \check{\bSigma}^{-1/2} \|_2 = \| \check{\bSigma}^{-1/2} x_i \|_2^2 \le \frac{1}{\lambda_{\min}(\check{\bSigma})} \|x_i\|_2^2 \le \frac{2}{\gamma} K^2,
\end{align*}
where we used the fact that \(\check{\bSigma} \succeq \frac{1}{2}\bar{\bSigma} \succeq \frac{\gamma}{2}\Ib\) (proven in Lemma~\ref{lemma; tail_bound} below).
The Matrix Bernstein inequality implies that with high probability:
\begin{align*}
\|{\check \bSigma}^{-\frac{1}{2}} (\bSigma - \check \bSigma)  { \check \bSigma}^{-\frac{1}{2}} \| \le C \sqrt{\frac{K^2 \log n}{n\gamma}} + C \frac{K^2 \log n}{n\gamma}.
\end{align*}
Given the sample complexity condition \(n \gtrsim \frac{K^2}{\gamma} \log n\), we can ensure the RHS is bounded by \(1/2\).
This implies:
\begin{align}\label{equation; truncated moment comparability}
\frac{1}{2} \check{\bSigma} \preceq \bSigma \preceq \frac{3}{2} \check{\bSigma}.
\end{align}
Using Lemma~\ref{lemma; tail_bound}, we know that \(\bar{\bSigma}\) and \(\check{\bSigma}\) are close:
\begin{align*}
\bar{\bSigma} - \frac{\gamma}{2}\Ib \preceq \check{\bSigma} \preceq 2 \bar{\bSigma}.
\end{align*}
Specifically, since \(\bar{\bSigma} \succeq \gamma \Ib\), the additive error implies multiplicative comparability (e.g., \(\frac{1}{2}\bar{\bSigma} \preceq \check{\bSigma}\)).
Combining this with \cref{equation; truncated moment comparability}, we obtain the desired result:
\begin{align*}
\frac{1}{6} \bar{\bSigma} \preceq \frac{1}{2} \check{\bSigma} \preceq \bSigma \preceq \frac{3}{2} \check{\bSigma} \preceq 3 \bar{\bSigma}.
\end{align*}
\hfill \BlackBox

We now present a lemma useful for establishing MSE bounds (Theorem~\ref{theorem; population MSE}).

\begin{lemma}\label{lemma; U/n}
Let \(K\) be defined as in the proof of Lemma~\ref{lemma; sample complexity}. With probability at least \(1-2\kappa\),
\begin{align*}
\bar{\bSigma} \preceq c\left(\bSigma + \frac{K^2}{n}\Ib\right)
\end{align*}
for some absolute constant \(c>1\).
\end{lemma}
\begin{proof}
We again consider the high-probability event \(\cE_{\text{samples}}\) where all samples satisfy \(\|x_i\|_2 \le K\).
Conditioned on this event, we essentially sample from \(\check{\cP}\).
By applying a one-sided Matrix Bernstein inequality (or similar concentration bounds for bounded random vectors as in Lemma~\ref{lemma; sample complexity}), we obtain:
\begin{align*}
\check{\bSigma } \preceq c'\left(\bSigma + \frac{K^2}{n}\Ib\right)
\end{align*}
for some constant \(c' > 1\).
From Lemma~\ref{lemma; tail_bound}, we have \(\bar{\bSigma} \preceq 2\check{\bSigma}\). Combining these yields the result.
\end{proof}

Finally, we provide the rigorous "peeling" argument that bounds the difference between the full and truncated population covariances.

\begin{lemma}[Truncation tail bound]\label{lemma; tail_bound}
Let \(\check{\bSigma} = \EE[xx^\top \mid \|x\|_2 \le K]\), where \(K\) is defined as in the proof of Lemma~\ref{lemma; sample complexity} (i.e., \(K = A U \log\!\left(\frac{nU}{\gamma \kappa}\right)\)). For a sufficiently large constant \(A\),
\begin{align*}
\| \bar{\bSigma} - \PP(\|x\|_2 \le K) \check{\bSigma} \|_2 \le \frac{\gamma}{2}.
\end{align*}
Consequently, \(\check{\bSigma} \succeq \frac{1}{2} \bar{\bSigma} \succeq \frac{\gamma}{2} \Ib\).
\end{lemma}
\begin{proof}
Let \(E\) be the indicator event \(\{\|x\|_2 \le K\}\). We can decompose the expectation:
\begin{align*}
\bar{\bSigma} = \EE[xx^\top] = \PP(E)\EE[xx^\top \mid E] + \EE[xx^\top \mathbb{I}(E^c)] = \PP(E)\check{\bSigma} + \Delta.
\end{align*}
We bound the residual matrix \(\Delta = \EE[xx^\top \mathbb{I}(\|x\|_2 > K)]\) using a peeling argument.
Define shells \(S_j := \{ x : K + (j-1)U < \|x\|_2 \le K + jU \}\) for \(j \ge 1\).
\begin{align*}
\Delta &\preceq \EE[ \|x\|_2^2 \mathbb{I}(\|x\|_2 > K) ] \Ib \\
&= \sum_{j=1}^\infty \EE[ \|x\|_2^2 \mathbb{I}(x \in S_j) ] \Ib \\
&\preceq \sum_{j=1}^\infty (K + jU)^2 \PP(\|x\|_2 > K + (j-1)U) \Ib.
\end{align*}
Using the tail assumption \(\PP(\|x\|_2 > tU) \le e^{-ct}\), we have:
\begin{align*}
\PP(\|x\|_2 > K + (j-1)U) \le \exp\left(-c \frac{K + (j-1)U}{U}\right) = e^{-cK/U} e^{-c(j-1)}.
\end{align*}
Substituting this back:
\begin{align*}
\|\Delta\|_2 &\le e^{-cK/U} \sum_{j=1}^\infty (K+jU)^2 e^{-c(j-1)}.
\end{align*}
Since \(K \gg U\), the term dominates for small \(j\).
Recall \(K = A U \log(nU/\gamma)\), so \(e^{-cK/U} = (\frac{\gamma}{nU})^{cA}\).
For sufficiently large \(A\), the pre-factor \((\frac{\gamma}{nU})^{cA}\) suppresses the polynomial terms in the sum, ensuring:
\begin{align*}
\|\Delta\|_2 \le \frac{\gamma}{2}.
\end{align*}
Thus, \(\PP(E)\check{\bSigma} \succeq \bar{\bSigma} - \frac{\gamma}{2}\Ib \succeq \frac{\gamma}{2}\Ib\).
Since \(\PP(E) \le 1\), this implies \(\check{\bSigma} \succeq \frac{\gamma}{2}\Ib\).
\end{proof}




\section{Technical Lemmas}



\begin{lemma}\label{lemma; ARMUL infimal convolution lipschitz}
If $f: \mathbb{R}^d \rightarrow \mathbb{R}$ is convex, $\inf _{\boldsymbol{x} \in \mathbb{R}^d} f(\boldsymbol{x})>-\infty$, and $R: \mathbb{R}^d \rightarrow \mathbb{R}$ is convex and $L$-Lipschitz with respect to a norm $\|\cdot\|$ for some $L \geq 0$, then
\[
g(\theta):= \inf_{x \in \Cb} \bigl\{ f(x) + R(\theta-x) \bigr\}
\]
is convex and $L$-Lipschitz with respect to $\|\cdot\|$.
\end{lemma}

\begin{proof}
For any \(\theta, \theta' \in \Cb\) and any \(\varepsilon>0\), there exists $x_0 \in \Cb$ such that 
\begin{align*}
g(\theta') +\varepsilon > f(x_0) + R(\theta'-x_0).
\end{align*}
Then we have
\begin{align*}
&g(\theta) - g(\theta') \le f(x_0)  + R(\theta -x_0) -(f(x_0) + R(\theta' -x_0) - \varepsilon) \\
&\le R(\theta -x_0) -R(\theta' -x_0) +\varepsilon \\ 
&\le L\|\theta -\theta' \| +\varepsilon.
\end{align*}
Since \(\varepsilon \) is arbitrary, we get the wanted result.

\end{proof}
\begin{lemma}[Lemma F.2 from \citealt{duan2023adaptive}]\label{lemma; ARMUL effect outlier}
Let $f: \mathbb{R}^d \rightarrow \mathbb{R}$ be a convex function and $\boldsymbol{x}_0=\operatorname{argmin}_{\boldsymbol{x}} f(\boldsymbol{x})$. Suppose there exist $\rho>0$ and $r>0$ such that $\nabla^2 f(\boldsymbol{x}) \succeq \rho \boldsymbol{I}, \forall \boldsymbol{x} \in B\left(\boldsymbol{x}_0, r\right)$. We have
\begin{align*}
\|\boldsymbol{f}\|_2 \geq \rho \min \left\{\left\|\boldsymbol{x}-\boldsymbol{x}_0\right\|_2, r\right\}, \quad \forall \boldsymbol{f} \in \partial f(\boldsymbol{x}), \quad \boldsymbol{x} \in \mathbb{R}^d .
\end{align*}

If $g: \mathbb{R}^d \rightarrow \mathbb{R}$ is convex and $\lambda'$-Lipschitz for some $\lambda'<\rho r$, then $f(\boldsymbol{x})+g(\boldsymbol{x})$ has a unique minimizer and it belongs to $B\left(\boldsymbol{x}_0, \lambda' / \rho\right)$.
\end{lemma}

\begin{lemma}[Constrained Perturbation Bound]\label{lemma; ARMUL effect outlier constrained}
Let \(\Cb\subseteq\RR^d\) be closed and convex.
Let \(f:\RR^d\to\RR\) be convex and differentiable, and let \(x_0\in\arg\min_{x\in\Cb} f(x)\).
Suppose there exist \(\rho>0\) and \(r>0\) such that
\[
\nabla^2 f(x)\succeq \rho I_d,\qquad \forall x\in \Cb\cap B(x_0,r).
\]
Let \(g:\RR^d\to\RR\) be convex and \(\lambda'\)-Lipschitz with respect to \(\|\cdot\|_2\).
If \(\lambda'<\rho r\), then every minimizer
\[
\hat x\in \arg\min_{x\in\Cb}\{f(x)+g(x)\}
\]
satisfies
\[
\|\hat x-x_0\|_2\le \frac{\lambda'}{\rho}.
\]
\end{lemma}

\begin{proof}
Fix any minimizer \(\hat x\in\arg\min_{x\in\Cb}\{f(x)+g(x)\}\), and set \(t:=\|\hat x-x_0\|_2\).
If \(t=0\), the claim is immediate.
Let \(u:=(\hat x-x_0)/t\) and \(s:=\min\{t,r\}\).
Since \(\Cb\) is convex, the segment \(x_0+a u\), \(0\le a\le t\), lies in \(\Cb\).
The one-dimensional function \(\phi(a):=f(x_0+a u)\) is convex on \([0,t]\), and satisfies \(\phi''(a)\ge \rho\) for \(0\le a\le s\).
Therefore \(\phi'(t)-\phi'(0)\ge \rho s\), which gives
\[
\bigl\langle \nabla f(\hat x)-\nabla f(x_0),\,\hat x-x_0\bigr\rangle
\ge
\rho\min\{t,r\}\,t.
\]
By the constrained first-order optimality condition for \(\hat x\), there exist \(v\in\partial g(\hat x)\) and \(n\in N_{\Cb}(\hat x)\) such that
\[
\nabla f(\hat x)+v+n=0.
\]
Since \(x_0\in\Cb\), \(\langle n,x_0-\hat x\rangle\le0\).
Since \(x_0\) minimizes the convex differentiable function \(f\) over \(\Cb\), we also have
\(\langle\nabla f(x_0),\hat x-x_0\rangle\ge0\).
Thus
\[
\bigl\langle \nabla f(\hat x)-\nabla f(x_0),\,\hat x-x_0\bigr\rangle
\le
\langle -v,\hat x-x_0\rangle
\le
\|v\|_2\,t
\le
\lambda' t,
\]
where the last inequality uses the \(\lambda'\)-Lipschitz property of \(g\).
Combining the two displays and dividing by \(t>0\), we obtain
\[
\rho\min\{t,r\}\le \lambda'.
\]
Because \(\lambda'<\rho r\), the minimum cannot be \(r\), and hence \(t<r\).
Therefore \(\rho t\le \lambda'\), proving \(t\le \lambda'/\rho\).
\end{proof}

\begin{lemma}[Lemma F.3. from \citealt{duan2023adaptive}]\label{lemma; ARMUL invariant region}
Let $f$ be convex and differentiable. 
If $\lambda>\left\|\nabla f\left({x}\right)\right\|_2$, then
\begin{align*}
f(x)=f \star \left(\lambda\|\cdot\|_2\right)(x) \quad \text { and } \quad \underset{y \in \mathbb{R}^d}{\operatorname{argmin}}\left\{f(y)+\lambda\|x-y\|_2\right\}=x.
\end{align*}
\end{lemma}

\begin{proof}
Observe that
\begin{align*}
f(y) + \lambda \|x - y\|_2
&\ge f(x) + \bigl\langle \nabla f(x),\,y - x \bigr\rangle + \lambda \|x - y\|_2\\
&\ge f(x) + \bigl(\lambda - \|\nabla f(x)\|_2\bigr)\|x - y\|_2
\;>\;f(x).
\end{align*}

\end{proof}

\begin{lemma}[Constrained Invariant Region]\label{lemma; ARMUL invariant region constrained}
Let \(f:\RR^d\to\RR\) be convex and differentiable, let \(\Cb\subseteq\RR^d\) be a convex set, and let \(x\in\Cb\).
If \(\lambda>\|\nabla f(x)\|_2\), then
\[
f(x)
=
\inf_{y\in\Cb}\left\{f(y)+\lambda\|x-y\|_2\right\},
\qquad
\arg\min_{y\in\Cb}\left\{f(y)+\lambda\|x-y\|_2\right\}
=
\{x\}.
\]
\end{lemma}

\begin{proof}
Fix any \(y\in\Cb\).
By convexity and differentiability of \(f\),
\[
f(y)\ge f(x)+\langle\nabla f(x),y-x\rangle.
\]
Therefore
\[
f(y)+\lambda\|x-y\|_2
\ge
f(x)+\langle\nabla f(x),y-x\rangle+\lambda\|x-y\|_2
\ge
f(x)+\bigl(\lambda-\|\nabla f(x)\|_2\bigr)\|x-y\|_2.
\]
If \(y\ne x\), the last term is strictly larger than \(f(x)\) because \(\lambda>\|\nabla f(x)\|_2\).
For \(y=x\), the objective value is exactly \(f(x)\).
Hence \(x\) is the unique minimizer over \(\Cb\), and the constrained infimal convolution value at \(x\) equals \(f(x)\).
\end{proof}


\subsection{Concentration Inequalities}
\begin{lemma}[Corollary E.1 from \citealt{wang2026pseudo}]\label{lemma; trace class concentration bounded}
Let $\left\{\boldsymbol{x}_i\right\}_{i=1}^n$ be i.i.d. random elements in a separable Hilbert space $\mathbb{H}$ with $\boldsymbol{\bSigma}=$ $\mathbb{E}\left(\boldsymbol{x}_i \otimes \boldsymbol{x}_i\right)$ being trace class. Define $\hat{\boldsymbol{\bSigma}}=\frac{1}{n} \sum_{i=1}^n \boldsymbol{x}_i \otimes \boldsymbol{x}_i$. Choose any constant $\gamma \in(0,1)$ and define an event $\mathcal{A}=\{(1-\gamma)(\boldsymbol{\bSigma}+\lambda \boldsymbol{I}) \preceq \hat{\boldsymbol{\bSigma}}+\lambda \boldsymbol{I} \preceq(1+\gamma)(\boldsymbol{\bSigma}+\lambda \boldsymbol{I})\}$.

1. If $\left\|\boldsymbol{x}_i\right\|_{\mathbb{H}} \leq M$ holds almost surely for some constant $M$, then there exists a constant $C \geq 1$ determined by $\gamma$ such that $\mathbb{P}(\mathcal{A}) \geq 1-\delta$ holds so long as $\delta \in(0,1 / 14]$ and $\lambda \geq \frac{C M^2 \log (n / \delta)}{n}$.    

2. If $\left\|\left\langle\boldsymbol{x}_i, \boldsymbol{v}\right\rangle\right\|_{\psi_2}^2 \leq \kappa \mathbb{E}\left|\left\langle\boldsymbol{x}_i, \boldsymbol{v}\right\rangle\right|^2$ holds for all $\boldsymbol{v} \in \mathbb{H}$ and some constant $\kappa$, then there exists a constant $C$ determined by $\kappa$ such that $\mathbb{P}(\mathcal{A}) \geq 1-\delta$ holds so long as $\delta \in(0,1 / e]$ and $\lambda \geq \frac{C \operatorname{Tr}(\boldsymbol{\Sigma}) \log (1 / \delta)}{\gamma^2 n}$.
\end{lemma}



\begin{lemma}[Lemma E.1 from \citealt{wang2026pseudo}]\label{lemma; hanson wright inequality}
Suppose that $\boldsymbol{x} \in \mathbb{R}^d$ is a zero-mean random vector with $\|\boldsymbol{x}\|_{\psi_2} \leq 1$. There exists a universal constant $c_0>0$ such that for any symmetric and positive semi-definite matrix $\boldsymbol{\bSigma} \in \mathbb{R}^{d \times d}$,

\begin{align*}
\mathbb{P}\left(\boldsymbol{x}^{\top} \boldsymbol{\bSigma} \boldsymbol{x} \leq c_0 \operatorname{Tr}(\boldsymbol{\bSigma}) t\right) \geq 1-e^{-r(\boldsymbol{\bSigma}) t}, \quad \forall t \geq 1
\end{align*}


Here $r(\boldsymbol{\bSigma})=\operatorname{Tr}(\boldsymbol{\bSigma}) /\|\boldsymbol{\bSigma}\|_2$ is the effective rank of $\boldsymbol{\bSigma}$.
\end{lemma}



\end{document}
