Distributed Sketching on Data Partitions for OLS Regression

# Distributed Sketching on Data Partitions for OLS Regression
Source: [https://arxiv.org/html/2607.07888](https://arxiv.org/html/2607.07888)
1\] organization= School of Computer Science, University of Oklahoma, country = U\.S\.

mode=titleDistributed Sketching on Data Partitions for OLS Regression

###### Abstract

This paper studies distributed sketching for ordinary least squares \(OLS\) regression, an approach that distributes small sketches of a large data set over multiple machines to separately construct OLS estimators and average them\. Unlike prior studies that consider sketching on the whole data set, we consider sketching on partitioned subsets to further reduce computational cost\. Under the fixed design setting, we characterize the exact excess loss of the averaged OLS estimator\. Results show that this loss is comparable to the established loss for sketching on the whole data set when the divergence among subset covariances is small\.

###### keywords:

Distributed Sketching\\sepOrdinary Least Squares Regression\\sepExpected Excess Loss\\sep

## 1Introduction

Distributed sketching is an effective approach to scale up ordinary least squares \(OLS\) regression for massive data\(bartan2023distributed;garg2024distributed;chen2025gpu\)\. Its basic idea is to distribute small sketches of a large data set to multiple machines, ask each machine to build an OLS estimator from the received sketch, and average the estimators built by all machines\. Anexactexcess loss of the averaged estimator is characterized in\(bartan2023distributed\), presuming each sketch is mapped from the whole data set using Gaussian projection\. This sketching mechanism has a known limitation, however, that the mapping process is often computationally expensive\.

This paper considers an alternative sketching mechanism, where each sketch is mapped from a partitioned subset of the whole data set\. In this case, the mapping cost decreases as the subset size reduces or, equivalently, as the number of distributed machines increases \(so that each machine holds a smaller subset\)\. Under the fixed design setting, we also characterize the exact excess loss of the averaged estimator\. Results show that this loss is comparable to the above established loss when the divergence among subset covariances is small\.

## 2Preliminaries

Consider the fixed design setting\. Letx1,…,xn∈ℝdx\_\{1\},\\ldots,x\_\{n\}\\in\\mathbb\{R\}^\{d\}be a fixed set ofnnpoints\. Letyi∈ℝy\_\{i\}\\in\\mathbb\{R\}be the label ofxix\_\{i\}generated byyi=xiT​α∗\+εiy\_\{i\}=x\_\{i\}^\{T\}\\alpha\_\{\*\}\+\\varepsilon\_\{i\}, whereα∗∈ℝd\\alpha\_\{\*\}\\in\\mathbb\{R\}^\{d\}is fixed andεi\\varepsilon\_\{i\}’s are i\.i\.d\. random noises with𝔼​εi=0\\mathbb\{E\}\\varepsilon\_\{i\}=0andV​a​r​\(εi\)=σ2Var\(\\varepsilon\_\{i\}\)=\\sigma^\{2\}for some fixedσ\>0\\sigma\>0\. LetX=\[x1,…,xn\]T∈ℝn×dX=\[x\_\{1\},\\ldots,x\_\{n\}\]^\{T\}\\in\\mathbb\{R\}^\{n\\times d\}be the sample matrix,Y=\[y1,…,yn\]T∈ℝnY=\[y\_\{1\},\\ldots,y\_\{n\}\]^\{T\}\\in\\mathbb\{R\}^\{n\}be the label vector andE=\[ε1,…,εn\]T∈ℝnE=\[\\varepsilon\_\{1\},\\ldots,\\varepsilon\_\{n\}\]^\{T\}\\in\\mathbb\{R\}^\{n\}be the noise vector\. Then, the above setting can be written as

Y=X​α∗\+E\.Y=X\\alpha\_\{\*\}\+E\.\(1\)
Consider any even row partition ofXXintokksubmatricesX1,…,Xk∈ℝp×dX\_\{1\},\\ldots,X\_\{k\}\\in\\mathbb\{R\}^\{p\\times d\}, and assumep​k=npk=nfor convenience\. LetY1,…,Yk∈ℝpY\_\{1\},\\ldots,Y\_\{k\}\\in\\mathbb\{R\}^\{p\}andE1,…,Ek∈ℝpE\_\{1\},\\ldots,E\_\{k\}\\in\\mathbb\{R\}^\{p\}be the corresponding row partitions ofYYandEE, respectively, which impliesYi=Xi​α∗\+EiY\_\{i\}=X\_\{i\}\\alpha\_\{\*\}\+E\_\{i\}\. LetS~=\{S~1,…,S~k∈ℝm×n\}\\tilde\{S\}=\\\{\\tilde\{S\}\_\{1\},\\ldots,\\tilde\{S\}\_\{k\}\\in\\mathbb\{R\}^\{m\\times n\}\\\}andS=\{S1,…,Sk∈ℝm×p\}S=\\\{S\_\{1\},\\ldots,S\_\{k\}\\in\\mathbb\{R\}^\{m\\times p\}\\\}be two sets of independent random matrices with i\.i\.d\. entries followingN​\(0,1/m\)N\(0,1/m\)\. Let\|\|⋅\|\|\|\|\\cdot\|\|denoteL2L\_\{2\}norm andIsI\_\{s\}be an identity matrix of sizess\.

Consider three OLS estimators\. GivenEE, the first estimator is built on the whole data set i\.e\.,

α^∗=arg⁡minα∈Rd​‖X​α−Y‖2,\\hat\{\\alpha\}\_\{\*\}=\\arg\\min\_\{\\alpha\\in R^\{d\}\}\|\|X\\alpha\-Y\|\|^\{2\},\(2\)Given\(E,S~\)\(E,\\tilde\{S\}\), the second estimator is built on sketches mapped from the whole set i\.e\.,

β¯=1k​∑i=1kβ^i,whereβ^i=arg⁡minα∈ℝd​‖S~i​X​α−S~i​Y‖2\.\\bar\{\\beta\}=\\frac\{1\}\{k\}\\sum\_\{i=1\}^\{k\}\\hat\{\\beta\}\_\{i\},\\quad\\text\{where\}\\ \\ \\hat\{\\beta\}\_\{i\}=\\arg\\min\_\{\\alpha\\in\\mathbb\{R\}^\{d\}\}\|\|\\tilde\{S\}\_\{i\}X\\alpha\-\\tilde\{S\}\_\{i\}Y\|\|^\{2\}\.\(3\)Given\(E,S\)\(E,S\), the third estimator is built on sketches mapped from partitioned subsets i\.e\.,

θ¯=1k​∑i=1kθ^i,whereθ^i=arg⁡minα∈ℝd​‖Si​Xi​α−Si​Yi‖2\.\\bar\{\\theta\}=\\frac\{1\}\{k\}\\sum\_\{i=1\}^\{k\}\\hat\{\\theta\}\_\{i\},\\quad\\text\{where\}\\ \\ \\hat\{\\theta\}\_\{i\}=\\arg\\min\_\{\\alpha\\in\\mathbb\{R\}^\{d\}\}\|\|S\_\{i\}X\_\{i\}\\alpha\-S\_\{i\}Y\_\{i\}\|\|^\{2\}\.\(4\)Finally, let the squared loss of a regression functionα\\alphaon a given\(X,Y\)\(X,Y\)be denoted as

L​\(α\)=‖X​α−Y‖2\.L\(\\alpha\)=\|\|X\\alpha\-Y\|\|^\{2\}\.\(5\)
The exact excess loss forβ¯\\bar\{\\beta\}has been studied\. We will characterize the exact loss forθ¯\\bar\{\\theta\}and make proper comparisons\. Similar to prior studies, we focus on the casep\>d\+1p\>d\+1, and assume with probability one that all data matrices are full rank andXiT​XiX\_\{i\}^\{T\}X\_\{i\}’s are invertible\. A quantity that turns out useful in the characterization is

D=1k2​∑i=1k∑j=1kDi​j,whereDi​j=tr​\[\(XiT​Xi\)​\(XjT​Xj\)−1\]\.D=\\frac\{1\}\{k^\{2\}\}\\sum\_\{i=1\}^\{k\}\\sum\_\{j=1\}^\{k\}D\_\{ij\},\\quad\\text\{where\}\\ \\ D\_\{ij\}=\\mathrm\{tr\}\[\(X\_\{i\}^\{T\}X\_\{i\}\)\(X\_\{j\}^\{T\}X\_\{j\}\)^\{\-1\}\]\.\(6\)The quantity can be viewed as a divergence measure for the subset covariances, and a smaller value generally implies smaller divergence\. It is clear thatD=dD=difk=1k=1\(soXi=XX\_\{i\}=X\)\. The following lemma presents a tight lower bound\.

###### Lemma 2\.1\.

With probability one,D≥dD\\geq dand the equality is achieved whenXiT​Xi=XjT​XjX\_\{i\}^\{T\}X\_\{i\}=X\_\{j\}^\{T\}X\_\{j\}for alli≠ji\\neq j\.

The quantity is also connected to several well\-known measures, which enriches its interpretation\. For convenience, assume all submatrices are centered so thatXiT​XiX\_\{i\}^\{T\}X\_\{i\}is the \(unscaled\) sample covariance for subsetii\.

One connection is to the classic Stein’s loss\(dey1985estimation\)or, equivalently, Burg matrix divergence\(kulis2009low\)\. Standard divergence between the sample covariances of subsetsiiandjjis defined as

B​D​\(i,j\)=Di​j−d−log​det\[\(XiT​Xi\)​\(XjT​Xj\)−1\]\.BD\(i,j\)=D\_\{ij\}\-d\-\\log\\det\[\(X\_\{i\}^\{T\}X\_\{i\}\)\(X\_\{j\}^\{T\}X\_\{j\}\)^\{\-1\}\]\.\(7\)We can define the average Burg divergence across all subsets as

B​D=1k2​∑i,j=1kB​D​\(i,j\)=D−d−1k2​log​det∏i,j=1k\(XiT​Xi\)​\(XjT​Xj\)−1\.BD=\\frac\{1\}\{k^\{2\}\}\\sum\_\{i,j=1\}^\{k\}BD\(i,j\)=D\-d\-\\frac\{1\}\{k^\{2\}\}\\log\\det\\prod\_\{i,j=1\}^\{k\}\(X\_\{i\}^\{T\}X\_\{i\}\)\(X\_\{j\}^\{T\}X\_\{j\}\)^\{\-1\}\.\(8\)This meansDDis a leading term of the average Burg divergence, and a smallerDDgenerally implies smaller divergence\. Reversely, when the average Burg divergence is zero \(if and only if eachB​D​\(i,j\)=0BD\(i,j\)=0and equivalently all subsets have identical sample covariance\),DDattains its minimum valueddaccording to Lemma[2\.1](https://arxiv.org/html/2607.07888#S2.Thmtheorem1)\.

Another connection is to the popular leverage score\(bharadwaj2023fast\)\. LetArA^\{r\}denote thert​hr\_\{th\}row of a given matrixAA\. For subsetii, the standard leverage score of itsrt​hr\_\{th\}point is

Li​r=\(Xir\)​\(XiT​Xi\)−1​\(Xir\)T,L\_\{ir\}=\(X^\{r\}\_\{i\}\)\\ \(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}\(X^\{r\}\_\{i\}\)^\{T\},\(9\)which specifies the degree to which pointrrdeviates from other points in subsetii\. In a similar way, we can write

Di​j=∑r=1pLi​r,j,whereLi​r,j=\(Xir\)​\(XjT​Xj\)−1​\(Xir\)T\.D\_\{ij\}=\\sum\_\{r=1\}^\{p\}L\_\{ir,j\},\\quad\\text\{where\}\\ \\ L\_\{ir,j\}=\(X^\{r\}\_\{i\}\)\\ \(X\_\{j\}^\{T\}X\_\{j\}\)^\{\-1\}\(X^\{r\}\_\{i\}\)^\{T\}\.\(10\)Compared toLi​rL\_\{ir\}, termLi​r,jL\_\{ir,j\}can be viewed as a relative leverage score that specifies the degree to which pointrrdeviates from the points in subsetjj\. Then,Di​jD\_\{ij\}is the total relative leverage score for subsetii\(w\.r\.t\. subsetjj\), andDDis the average relative score that describes the deviation between subsets\.

## 3Main Result

We first revisit a known result forβ¯\\bar\{\\beta\}\.

###### Theorem 3\.1\(\(bartan2023distributed\)\)\.

GivenEE, form\>d\+1m\>d\+1:

𝔼S~∣E​\[L​\(β¯\)\]−L​\(α^∗\)=1k​L​\(α^∗\)m−d−1​d\.\\mathbb\{E\}\_\{\\tilde\{S\}\\mid E\}\[L\(\\bar\{\\beta\}\)\]\-L\(\\hat\{\\alpha\}\_\{\*\}\)=\\frac\{1\}\{k\}\\frac\{L\(\\hat\{\\alpha\}\_\{\*\}\)\}\{m\-d\-1\}d\.\(11\)

Our result forθ¯\\bar\{\\theta\}is as follows\.

###### Theorem 3\.3\.

Under the fixed design setting, forp≥m\>d\+1p\\geq m\>d\+1:

𝔼S,E\[L\(θ¯\)\]−𝔼E\[L\(α^∗\)\]=σ2kn−k​dm−d−1D\+σ2\(D−d\):=Bθ\.\\mathbb\{E\}\_\{S,E\}\[L\(\\bar\{\\theta\}\)\]\-\\mathbb\{E\}\_\{E\}\[L\(\\hat\{\\alpha\}\_\{\*\}\)\]=\\frac\{\\sigma^\{2\}\}\{k\}\\frac\{n\-kd\}\{m\-d\-1\}D\+\\sigma^\{2\}\(D\-d\)\\quad:=B\_\{\\theta\}\.\(13\)

We have three observations\. First,Bθ=BβB\_\{\\theta\}=B\_\{\\beta\}ifk=1k=1, which is expected since no partition is performed byθ¯\\bar\{\\theta\}\. Second,Bθ≤BβB\_\{\\theta\}\\leq B\_\{\\beta\}ifDDis close todd, suggesting thatθ¯\\bar\{\\theta\}can outperformβ¯\\bar\{\\beta\}if subset covariances have small divergence \(which may be common if data are i\.i\.d\. sampled\)\. Third,Bθ≥BβB\_\{\\theta\}\\geq B\_\{\\beta\}ifDDis far fromdd, suggesting thatθ¯\\bar\{\\theta\}can perform worse if subset covariances have large divergence \(which may happen if data are collected from heterogeneous sources\)\.

These observations reveal that the gap betweenDDandddis an important indicator of theθ¯\\bar\{\\theta\}performance\. To have a more concrete idea on this gap, we may further incorporate the randomness ofXX\.

The remark shows that the gap can be small whenkkis small orn≫max⁡\(k,d\)n\\gg\\max\(k,d\); in particular,𝔼​\[D\]=d\\mathbb\{E\}\[D\]=difk=1k=1, which aligns with the above results\. Another interesting experiment is to plug the rate intoBθ−BβB\_\{\\theta\}\-B\_\{\\beta\}, which gives

𝔼X​\[Bβ−Bθ\]=σ2​d⋅\(F​\(k;n,d,m\)\+1\),\\mathbb\{E\}\_\{X\}\[B\_\{\\beta\}\-B\_\{\\theta\}\]=\\sigma^\{2\}d\\cdot\(F\(k;n,d,m\)\+1\),\(14\)whereF​\(k;n,d,m\)=n−dm−d−1​k−1k​n−k​dm−d−1​n−\(d\+1\)n−k​\(d\+1\)−n−\(d\+1\)n−k​\(d\+1\)F\(k;n,d,m\)=\\frac\{n\-d\}\{m\-d\-1\}k\-\\frac\{1\}\{k\}\\frac\{n\-kd\}\{m\-d\-1\}\\frac\{n\-\(d\+1\)\}\{n\-k\(d\+1\)\}\-\\frac\{n\-\(d\+1\)\}\{n\-k\(d\+1\)\}is a function ofkk\. Through standard analysis \(that inspects function derivative\), one can showFFhas an inverted U\-shape\. This implies that, askkincreases, the performance gap betweenθ¯\\bar\{\\theta\}andβ¯\\bar\{\\beta\}can first increase and then decrease\. This is confirmed by our numerical results\.

Finally, we derive a high probability bound for the excess loss ofθ¯\\bar\{\\theta\}\. Its proof is given in Appendix[B](https://arxiv.org/html/2607.07888#A2)and primarily relies on bounding\(XiT​SiT​Si​Xi\)−1\(X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}X\_\{i\}\)^\{\-1\}using a classical singular value bound for random matrices\.

Given an estimatorα^\\hat\{\\alpha\}, letLo​\(α^\)=𝔼Y​‖X​α^−Y‖L\_\{o\}\(\\hat\{\\alpha\}\)=\\mathbb\{E\}\_\{Y\}\|\|X\\hat\{\\alpha\}\-Y\|\|denote its out\-of\-sample excess loss, whereYYandα^\\hat\{\\alpha\}are built from independent label noisesEYE\_\{Y\}andEα^E\_\{\\hat\{\\alpha\}\}respectively\. Our result is stated as follows\.

ComparingBθ′B\_\{\\theta\}^\{\\prime\}withBθB\_\{\\theta\}, we see they have the same second term\. ForBθB\_\{\\theta\}, the first term isσ2​D⋅p−dm−d−1\\sigma^\{2\}D\\cdot\\frac\{p\-d\}\{m\-d\-1\}, which is dominated byσ2​D⋅pm\\sigma^\{2\}D\\cdot\\frac\{p\}\{m\}whenm≫dm\\gg d\. ForBθ′B\_\{\\theta\}^\{\\prime\}, by ignoring the logarithmic terms, the first term is approximately

σ2​D⋅\(Γ​\(p,m,k,δ\)−1\)≈σ2​D⋅\(\(m\+p\)2\(m−d\)2−1\),\\sigma^\{2\}D\\cdot\(\\Gamma\(p,m,k,\\delta\)\-1\)\\approx\\sigma^\{2\}D\\cdot\\left\(\\frac\{\(\\sqrt\{m\}\+\\sqrt\{p\}\)^\{2\}\}\{\(\\sqrt\{m\}\-\\sqrt\{d\}\)^\{2\}\}\-1\\right\),\(16\)which is also dominated byσ2​D⋅pm\\sigma^\{2\}D\\cdot\\frac\{p\}\{m\}whenp≫m≫dp\\gg m\\gg d\. This suggestsBθ′B\_\{\\theta\}^\{\\prime\}can be a high probability proxy ofBθB\_\{\\theta\}, which means the expected excess loss is representative of a typical distributed sketching performance\.

## 4Proof of Theorem[3\.3](https://arxiv.org/html/2607.07888#S3.Thmtheorem3)

GivenEE, let the squared loss of an estimatorα\\alphaon\(Xi,Yi\)\(X\_\{i\},Y\_\{i\}\)be

Li​\(α\)=‖Xi​α−Yi‖2\.L\_\{i\}\(\\alpha\)=\|\|X\_\{i\}\\alpha\-Y\_\{i\}\|\|^\{2\}\.\(17\)Letα¯\\bar\{\\alpha\}be an average estimator defined as

α¯=1k​∑i=1kα^i,whereα^i=arg⁡minα⁡Li​\(α\)\.\\bar\{\\alpha\}=\\frac\{1\}\{k\}\\sum\_\{i=1\}^\{k\}\\hat\{\\alpha\}\_\{i\},\\quad\\text\{where\}\\ \\ \\hat\{\\alpha\}\_\{i\}=\\arg\\min\_\{\\alpha\}L\_\{i\}\(\\alpha\)\.\(18\)LetE^i\\hat\{E\}\_\{i\}be the residual associated withα^i\\hat\{\\alpha\}\_\{i\}on\(Xi,Yi\)\(X\_\{i\},Y\_\{i\}\), i\.e\.,

E^i=Yi−Xi​α^i\.\\hat\{E\}\_\{i\}=Y\_\{i\}\-X\_\{i\}\\hat\{\\alpha\}\_\{i\}\.\(19\)NoteE^i\\hat\{E\}\_\{i\}is different fromEiE\_\{i\}and is fixed givenEiE\_\{i\}\. Finally, recallS=\{S1,…,Sk\}S=\\\{S\_\{1\},\\ldots,S\_\{k\}\\\}and letS​X=\{S1​X1,…,Sk​Xk\}SX=\\\{S\_\{1\}X\_\{1\},\\ldots,S\_\{k\}X\_\{k\}\\\}\. Since elements in each set are mutually independent, any variableGiG\_\{i\}that only depends onSiS\_\{i\}has𝔼S​\[Gi\]=𝔼Si​\[Gi\]\\mathbb\{E\}\_\{S\}\[G\_\{i\}\]=\\mathbb\{E\}\_\{S\_\{i\}\}\[G\_\{i\}\]and𝔼S​X​\[Gi\]=𝔼Si​Xi​\[Gi\]\\mathbb\{E\}\_\{SX\}\[G\_\{i\}\]=\\mathbb\{E\}\_\{S\_\{i\}X\_\{i\}\}\[G\_\{i\}\]\. Any expectation without subscript inherits the subscript of the preceding expectation\.

### 4\.1Roadmap

A basic observation is𝔼S∣E​\[θ^i\]=α^i\\mathbb\{E\}\_\{S\\mid E\}\[\\hat\{\\theta\}\_\{i\}\]=\\hat\{\\alpha\}\_\{i\}\(Claim[4\.1](https://arxiv.org/html/2607.07888#S4.Thmtheorem1)\)\. Based on it, we show that \(Claim[4\.2](https://arxiv.org/html/2607.07888#S4.Thmtheorem2)\):

𝔼E​\[L​\(α^∗\)\]=\(n−d\)​σ2and𝔼E​\[Li​\(α^i\)\]=\(p−d\)​σ2\.\\mathbb\{E\}\_\{E\}\[L\(\\hat\{\\alpha\}\_\{\*\}\)\]=\(n\-d\)\\sigma^\{2\}\\quad\\text\{and\}\\quad\\mathbb\{E\}\_\{E\}\[L\_\{i\}\(\\hat\{\\alpha\}\_\{i\}\)\]=\(p\-d\)\\sigma^\{2\}\.\(20\)The former establishes Remark[3\.2](https://arxiv.org/html/2607.07888#S3.Thmtheorem2)and implies another important characterization \(Claim[4\.3](https://arxiv.org/html/2607.07888#S4.Thmtheorem3)\):

𝔼S,E​\[L​\(θ¯\)\]−𝔼E​\[L​\(α^∗\)\]=𝔼S,E​‖X​\(θ¯−α^∗\)‖2\.\\mathbb\{E\}\_\{S,E\}\[L\(\\bar\{\\theta\}\)\]\-\\mathbb\{E\}\_\{E\}\[L\(\\hat\{\\alpha\}\_\{\*\}\)\]=\\mathbb\{E\}\_\{S,E\}\|\|X\(\\bar\{\\theta\}\-\\hat\{\\alpha\}\_\{\*\}\)\|\|^\{2\}\.\(21\)To evaluate the right side, we first fixEEand show that \(Claim[4\.4](https://arxiv.org/html/2607.07888#S4.Thmtheorem4)\):

𝔼S∣E​‖X​θ¯−X​α^∗‖2=𝔼​‖X​θ¯−X​α¯‖2\+‖X​α¯−X​α^∗‖2=1k2​∑i=1k𝔼​‖X​\(θ^i−α^i\)‖2\+‖X​α¯−X​α^∗‖2,\\mathbb\{E\}\_\{S\\mid E\}\|\|X\\bar\{\\theta\}\-X\\hat\{\\alpha\}\_\{\*\}\|\|^\{2\}=\\mathbb\{E\}\|\|X\\bar\{\\theta\}\-X\\bar\{\\alpha\}\|\|^\{2\}\+\|\|X\\bar\{\\alpha\}\-X\\hat\{\\alpha\}\_\{\*\}\|\|^\{2\}=\\frac\{1\}\{k^\{2\}\}\\sum\_\{i=1\}^\{k\}\\mathbb\{E\}\|\|X\(\\hat\{\\theta\}\_\{i\}\-\\hat\{\\alpha\}\_\{i\}\)\|\|^\{2\}\+\|\|X\\bar\{\\alpha\}\-X\\hat\{\\alpha\}\_\{\*\}\|\|^\{2\},\(22\)where the first equality is due to𝔼S∣E​\[θ¯\]=α¯\\mathbb\{E\}\_\{S\\mid E\}\[\\bar\{\\theta\}\]=\\bar\{\\alpha\}\(Claim[4\.1](https://arxiv.org/html/2607.07888#S4.Thmtheorem1)\) and the second is due to𝔼S∣E​\[θ^i\]=α^i\\mathbb\{E\}\_\{S\\mid E\}\[\\hat\{\\theta\}\_\{i\}\]=\\hat\{\\alpha\}\_\{i\}\. Further,

𝔼S∣E​‖X​\(θ^i−α^i\)‖2=𝔼​‖Xi​\(θ^i−α^i\)‖2\+𝔼​∑j≠i‖Xj​\(θ^i−α^i\)‖2=d\+Δim−d−1​Li​\(α^i\),\\mathbb\{E\}\_\{S\\mid E\}\|\|X\(\\hat\{\\theta\}\_\{i\}\-\\hat\{\\alpha\}\_\{i\}\)\|\|^\{2\}=\\mathbb\{E\}\|\|X\_\{i\}\(\\hat\{\\theta\}\_\{i\}\-\\hat\{\\alpha\}\_\{i\}\)\|\|^\{2\}\+\\mathbb\{E\}\{\\sum\}\_\{j\\neq i\}\|\|X\_\{j\}\(\\hat\{\\theta\}\_\{i\}\-\\hat\{\\alpha\}\_\{i\}\)\|\|^\{2\}=\\frac\{d\+\\Delta\_\{i\}\}\{m\-d\-1\}L\_\{i\}\(\\hat\{\\alpha\}\_\{i\}\),\(23\)whereΔi=∑j≠itr​\(XjT​Xj\)​\(XiT​Xi\)−1\\Delta\_\{i\}=\\sum\_\{j\\neq i\}\\mathrm\{tr\}\(X\_\{j\}^\{T\}X\_\{j\}\)\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}\.

In \([23](https://arxiv.org/html/2607.07888#S4.E23)\), the first equality follows a basic fact that‖X​z‖2=∑i=1k‖Xi​z‖2\|\|Xz\|\|^\{2\}=\\sum\_\{i=1\}^\{k\}\|\|X\_\{i\}z\|\|^\{2\}for anyz∈ℝdz\\in\\mathbb\{R\}^\{d\}, and the second equality follows two facts:𝔼​‖Xi​\(θ^i−α^i\)‖2=dm−d−1​Li​\(α^i\)\\mathbb\{E\}\|\|X\_\{i\}\(\\hat\{\\theta\}\_\{i\}\-\\hat\{\\alpha\}\_\{i\}\)\|\|^\{2\}=\\frac\{d\}\{m\-d\-1\}L\_\{i\}\(\\hat\{\\alpha\}\_\{i\}\)by Claim[4\.5](https://arxiv.org/html/2607.07888#S4.Thmtheorem5)[\(a\)](https://arxiv.org/html/2607.07888#A1.I2.i1)\(which is a direct adaptation of the prior result\(bartan2023distributed\)from\(X,Y\)\(X,Y\)to\(Xi,Yi\)\(X\_\{i\},Y\_\{i\}\)\), and𝔼​∑j≠i‖Xj​\(θ^i−α^i\)‖2=Δim−d−1​Li​\(α^i\)\\mathbb\{E\}\\sum\_\{j\\neq i\}\|\|X\_\{j\}\(\\hat\{\\theta\}\_\{i\}\-\\hat\{\\alpha\}\_\{i\}\)\|\|^\{2\}=\\frac\{\\Delta\_\{i\}\}\{m\-d\-1\}L\_\{i\}\(\\hat\{\\alpha\}\_\{i\}\)by Claim[4\.6](https://arxiv.org/html/2607.07888#S4.Thmtheorem6)\.

Plugging \([23](https://arxiv.org/html/2607.07888#S4.E23)\) back to \([22](https://arxiv.org/html/2607.07888#S4.E22)\) and taking expectation w\.r\.t\.EEon both sides, we have

𝔼S,E​‖X​θ¯−X​α^∗‖2=1k2​∑i=1kd\+Δim−d−1​𝔼E​\[Li​\(α^i\)\]\+𝔼E​‖X​α¯−X​α^∗‖2\.\\mathbb\{E\}\_\{S,E\}\|\|X\\bar\{\\theta\}\-X\\hat\{\\alpha\}\_\{\*\}\|\|^\{2\}=\\frac\{1\}\{k^\{2\}\}\\sum\_\{i=1\}^\{k\}\\frac\{d\+\\Delta\_\{i\}\}\{m\-d\-1\}\\mathbb\{E\}\_\{E\}\[L\_\{i\}\(\\hat\{\\alpha\}\_\{i\}\)\]\+\\mathbb\{E\}\_\{E\}\|\|X\\bar\{\\alpha\}\-X\\hat\{\\alpha\}\_\{\*\}\|\|^\{2\}\.\(24\)The right side can be evaluated as follows:𝔼E​\[Li​\(α^i\)\]=\(p−d\)​σ2\\mathbb\{E\}\_\{E\}\[L\_\{i\}\(\\hat\{\\alpha\}\_\{i\}\)\]=\(p\-d\)\\sigma^\{2\}by \([20](https://arxiv.org/html/2607.07888#S4.E20)\),1k2​∑i=1k\(d\+Δi\)=D\\frac\{1\}\{k^\{2\}\}\\sum\_\{i=1\}^\{k\}\(d\+\\Delta\_\{i\}\)=Dby Claim[B\.2](https://arxiv.org/html/2607.07888#A2.Thmtheorem2), and𝔼E​‖X​α¯−X​α^∗‖2=\(D−d\)​σ2\\mathbb\{E\}\_\{E\}\|\|X\\bar\{\\alpha\}\-X\\hat\{\\alpha\}\_\{\*\}\|\|^\{2\}=\(D\-d\)\\sigma^\{2\}by Claim[4\.7](https://arxiv.org/html/2607.07888#S4.Thmtheorem7)\. Plugging them back to \([24](https://arxiv.org/html/2607.07888#S4.E24)\) proves Theorem[3\.3](https://arxiv.org/html/2607.07888#S3.Thmtheorem3)\.

### 4\.2Supporting Claims

###### Claim 4\.1\.

GivenEE, the following hold:

1. \(a\)XiT​E^i=0X\_\{i\}^\{T\}\\hat\{E\}\_\{i\}=0\.
2. \(b\)Si​XiS\_\{i\}X\_\{i\}andSi​E^iS\_\{i\}\\hat\{E\}\_\{i\}are independent\.
3. \(c\)𝔼S∣S​X,E​\[θ^i\]=𝔼S∣E​\[θ^i\]=α^i\\mathbb\{E\}\_\{S\\mid SX,E\}\[\\hat\{\\theta\}\_\{i\}\]=\\mathbb\{E\}\_\{S\\mid E\}\[\\hat\{\\theta\}\_\{i\}\]=\\hat\{\\alpha\}\_\{i\}and𝔼S∣E​\[θ¯\]=α¯\\mathbb\{E\}\_\{S\\mid E\}\[\\bar\{\\theta\}\]=\\bar\{\\alpha\}\.

###### Proof Sketch\.

[\(a\)](https://arxiv.org/html/2607.07888#S4.I1.i1)holds asα^i\\hat\{\\alpha\}\_\{i\}minimizesLi​\(α\)L\_\{i\}\(\\alpha\),[\(b\)](https://arxiv.org/html/2607.07888#S4.I1.i2)follows from a well\-known property that jointly\-Gaussian variables are independent if they are uncorrelated, and[\(c\)](https://arxiv.org/html/2607.07888#S4.I1.i3)is by the estimator design and the independence property in[\(b\)](https://arxiv.org/html/2607.07888#S4.I1.i2)\. ∎

###### Claim 4\.2\.

𝔼E​\[L​\(α^∗\)\]=\(n−d\)​σ2\\mathbb\{E\}\_\{E\}\[L\(\\hat\{\\alpha\}\_\{\*\}\)\]=\(n\-d\)\\sigma^\{2\}and𝔼E​\[Li​\(α^i\)\]=\(p−d\)​σ2\\mathbb\{E\}\_\{E\}\[L\_\{i\}\(\\hat\{\\alpha\}\_\{i\}\)\]=\(p\-d\)\\sigma^\{2\}\.

###### Proof Sketch\.

LetG=X​\(XT​X\)−1​XT−InG=X\(X^\{T\}X\)^\{\-1\}X^\{T\}\-I\_\{n\}\. We can show𝔼E​\[L​\(α^∗\)\]=𝔼​‖G​E‖2=𝔼​tr​\[G​E​ET​GT\]=σ2​\(n−d\)\\mathbb\{E\}\_\{E\}\[L\(\\hat\{\\alpha\}\_\{\*\}\)\]=\\mathbb\{E\}\|\|GE\|\|^\{2\}=\\mathbb\{E\}\\mathrm\{tr\}\[GEE^\{T\}G^\{T\}\]=\\sigma^\{2\}\(n\-d\), where the first equality is by plugging in theα^∗\\hat\{\\alpha\}\_\{\*\}solution andY=X​α∗\+EY=X\\alpha\_\{\*\}\+E, and the last is by straight calculation\. Term𝔼E​\[Li​\(α^i\)\]\\mathbb\{E\}\_\{E\}\[L\_\{i\}\(\\hat\{\\alpha\}\_\{i\}\)\]is evaluated in the same way, based on\(Xi,Yi,α^i\)\(X\_\{i\},Y\_\{i\},\\hat\{\\alpha\}\_\{i\}\)instead of\(X,Y,α^∗\)\(X,Y,\\hat\{\\alpha\}\_\{\*\}\)\. ∎

###### Claim 4\.3\.

𝔼S,E​\[L​\(θ¯\)\]−𝔼E​\[L​\(α^∗\)\]=𝔼S,E​‖X​\(θ¯−α^∗\)‖2\\mathbb\{E\}\_\{S,E\}\[L\(\\bar\{\\theta\}\)\]\-\\mathbb\{E\}\_\{E\}\[L\(\\hat\{\\alpha\}\_\{\*\}\)\]=\\mathbb\{E\}\_\{S,E\}\|\|X\(\\bar\{\\theta\}\-\\hat\{\\alpha\}\_\{\*\}\)\|\|^\{2\}\.

###### Proof Sketch\.

First observe𝔼S,E​‖X​\(θ¯−α^∗\)‖2=𝔼​‖X​θ¯−Y‖2\+𝔼​‖X​α^∗−Y‖2−2​𝔼​\(X​α^∗−Y\)T​\(X​θ¯−Y\)\\mathbb\{E\}\_\{S,E\}\|\|X\(\\bar\{\\theta\}\-\\hat\{\\alpha\}\_\{\*\}\)\|\|^\{2\}=\\mathbb\{E\}\|\|X\\bar\{\\theta\}\-Y\|\|^\{2\}\+\\mathbb\{E\}\|\|X\\hat\{\\alpha\}\_\{\*\}\-Y\|\|^\{2\}\-2\\mathbb\{E\}\(X\\hat\{\\alpha\}\_\{\*\}\-Y\)^\{T\}\(X\\bar\{\\theta\}\-Y\), where the first two terms are𝔼​\[L​\(θ¯\)\]\\mathbb\{E\}\[L\(\\bar\{\\theta\}\)\]and𝔼​\[L​\(α^∗\)\]\\mathbb\{E\}\[L\(\\hat\{\\alpha\}\_\{\*\}\)\]respectively\. For the last term, by applying𝔼​\[θ¯\]=α¯\\mathbb\{E\}\[\\bar\{\\theta\}\]=\\bar\{\\alpha\}\(Claim[4\.1](https://arxiv.org/html/2607.07888#S4.Thmtheorem1)[\(c\)](https://arxiv.org/html/2607.07888#S4.I1.i3)\), we can show𝔼​\(X​α^∗−Y\)T​\(X​θ¯−Y\)=\(n−d\)​σ2=𝔼E​\[L​\(α^∗\)\]\\mathbb\{E\}\(X\\hat\{\\alpha\}\_\{\*\}\-Y\)^\{T\}\(X\\bar\{\\theta\}\-Y\)=\(n\-d\)\\sigma^\{2\}=\\mathbb\{E\}\_\{E\}\[L\(\\hat\{\\alpha\}\_\{\*\}\)\], where the second equality follows from Claim[4\.2](https://arxiv.org/html/2607.07888#S4.Thmtheorem2)\. ∎

###### Claim 4\.4\.

𝔼S∣E​‖X​θ¯−X​α^∗‖2=𝔼​‖X​θ¯−X​α¯‖2\+‖X​α¯−X​α^∗‖2=1k2​∑i=1k𝔼​‖X​\(θ^i−α^i\)‖2\+‖X​α¯−X​α^∗‖2\\mathbb\{E\}\_\{S\\mid E\}\|\|X\\bar\{\\theta\}\-X\\hat\{\\alpha\}\_\{\*\}\|\|^\{2\}=\\mathbb\{E\}\|\|X\\bar\{\\theta\}\-X\\bar\{\\alpha\}\|\|^\{2\}\+\|\|X\\bar\{\\alpha\}\-X\\hat\{\\alpha\}\_\{\*\}\|\|^\{2\}=\\frac\{1\}\{k^\{2\}\}\\sum\_\{i=1\}^\{k\}\\mathbb\{E\}\|\|X\(\\hat\{\\theta\}\_\{i\}\-\\hat\{\\alpha\}\_\{i\}\)\|\|^\{2\}\+\|\|X\\bar\{\\alpha\}\-X\\hat\{\\alpha\}\_\{\*\}\|\|^\{2\}\.

###### Proof Sketch\.

Both equalities hold because the cross terms are zero\. The first equality follows that𝔼S∣E​\[θ¯\]=α¯\\mathbb\{E\}\_\{S\\mid E\}\[\\bar\{\\theta\}\]=\\bar\{\\alpha\}\(Claim[4\.1](https://arxiv.org/html/2607.07888#S4.Thmtheorem1)[\(c\)](https://arxiv.org/html/2607.07888#S4.I1.i3)\), and the second equality follows thatθ^i,θ^j\\hat\{\\theta\}\_\{i\},\\hat\{\\theta\}\_\{j\}are independent givenEEand𝔼S∣E​\[θ^i\]=α^i\\mathbb\{E\}\_\{S\\mid E\}\[\\hat\{\\theta\}\_\{i\}\]=\\hat\{\\alpha\}\_\{i\}\(Claim[4\.1](https://arxiv.org/html/2607.07888#S4.Thmtheorem1)[\(c\)](https://arxiv.org/html/2607.07888#S4.I1.i3)\)\. ∎

###### Claim 4\.5\(Adaptation of Results in\(bartan2023distributed\)from\(X,Y\)\(X,Y\)to\(Xi,Yi\)\(X\_\{i\},Y\_\{i\}\)\)\.

GivenEE, we have

1. \(a\)𝔼S∣E​‖Xi​\(θ^i−α^i\)‖2=dm−d−1​Li​\(α^i\)\\mathbb\{E\}\_\{S\\mid E\}\|\|X\_\{i\}\(\\hat\{\\theta\}\_\{i\}\-\\hat\{\\alpha\}\_\{i\}\)\|\|^\{2\}=\\frac\{d\}\{m\-d\-1\}L\_\{i\}\(\\hat\{\\alpha\}\_\{i\}\)\.
2. \(b\)𝔼S∣S​X,E​\(θ^i−α^i\)​\(θ^i−α^i\)T=\(XiT​SiT​Si​Xi\)−1​1m​Li​\(α^i\)\\mathbb\{E\}\_\{S\\mid SX,E\}\(\\hat\{\\theta\}\_\{i\}\-\\hat\{\\alpha\}\_\{i\}\)\(\\hat\{\\theta\}\_\{i\}\-\\hat\{\\alpha\}\_\{i\}\)^\{T\}=\(X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}X\_\{i\}\)^\{\-1\}\\frac\{1\}\{m\}L\_\{i\}\(\\hat\{\\alpha\}\_\{i\}\)\.
3. \(c\)𝔼S​\(XiT​SiT​Si​Xi\)−1=\(XiT​Xi\)−1​mm−d−1\\mathbb\{E\}\_\{S\}\(X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}X\_\{i\}\)^\{\-1\}=\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}\\frac\{m\}\{m\-d\-1\}\.

###### Claim 4\.6\.

For anyii,𝔼S∣E​∑j≠i‖Xj​\(θ^i−α^i\)‖2=Δim−d−1​Li​\(α^i\)\\mathbb\{E\}\_\{S\\mid E\}\\sum\_\{j\\neq i\}\|\|X\_\{j\}\(\\hat\{\\theta\}\_\{i\}\-\\hat\{\\alpha\}\_\{i\}\)\|\|^\{2\}=\\frac\{\\Delta\_\{i\}\}\{m\-d\-1\}L\_\{i\}\(\\hat\{\\alpha\}\_\{i\}\), whereΔi=tr​\[∑j≠iXjT​Xj​\(XiT​Xi\)−1\]\\Delta\_\{i\}=\\mathrm\{tr\}\[\\sum\_\{j\\neq i\}X\_\{j\}^\{T\}X\_\{j\}\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}\]and all sums are overj=1,…,kj=1,\\ldots,kwithj=ij=iskipped\.

###### Proof\.

Observe that𝔼S∣S​X,E​‖Xj​\(θ^i−α^i\)‖2=tr​\[XjT​Xj​𝔼​\(θ^i−α^i\)​\(θ^i−α^i\)T\]=tr​\[XjT​Xj​Li​\(α^i\)m​\(XiT​SiT​Si​Xi\)−1\]\\mathbb\{E\}\_\{S\\mid SX,E\}\|\|X\_\{j\}\(\\hat\{\\theta\}\_\{i\}\-\\hat\{\\alpha\}\_\{i\}\)\|\|^\{2\}=\\mathrm\{tr\}\[X\_\{j\}^\{T\}X\_\{j\}\\mathbb\{E\}\(\\hat\{\\theta\}\_\{i\}\-\\hat\{\\alpha\}\_\{i\}\)\(\\hat\{\\theta\}\_\{i\}\-\\hat\{\\alpha\}\_\{i\}\)^\{T\}\]=\\mathrm\{tr\}\[X\_\{j\}^\{T\}X\_\{j\}\\frac\{L\_\{i\}\(\\hat\{\\alpha\}\_\{i\}\)\}\{m\}\(X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}X\_\{i\}\)^\{\-1\}\], where the last equality follows Claim[4\.5](https://arxiv.org/html/2607.07888#S4.Thmtheorem5)[\(b\)](https://arxiv.org/html/2607.07888#A1.I2.i2)\. Conditioned onEE, taking expectation of the right side w\.r\.t\.S​XSX,

tr​\[XjT​Xj​Li​\(α^i\)m⋅𝔼S​X∣E​\(XiT​SiT​Si​Xi\)−1\]=tr​\[XjT​Xj​Li​\(α^i\)m⋅m​\(XiT​Xi\)−1m−d−1\]=tr​\[\(XjT​Xj\)​\(XiT​Xi\)−1\]​Li​\(α^i\)m−d−1,\\mathrm\{tr\}\[X\_\{j\}^\{T\}X\_\{j\}\\frac\{L\_\{i\}\(\\hat\{\\alpha\}\_\{i\}\)\}\{m\}\\cdot\\mathbb\{E\}\_\{SX\\mid E\}\(X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}X\_\{i\}\)^\{\-1\}\]=\\mathrm\{tr\}\[X\_\{j\}^\{T\}X\_\{j\}\\frac\{L\_\{i\}\(\\hat\{\\alpha\}\_\{i\}\)\}\{m\}\\cdot\\frac\{m\\,\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}\}\{m\-d\-1\}\]=\\mathrm\{tr\}\[\(X\_\{j\}^\{T\}X\_\{j\}\)\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}\]\\frac\{L\_\{i\}\(\\hat\{\\alpha\}\_\{i\}\)\}\{m\-d\-1\},\(25\)where the first equality is by Claim[4\.5](https://arxiv.org/html/2607.07888#S4.Thmtheorem5)[\(c\)](https://arxiv.org/html/2607.07888#A1.I2.i3)\. Summing both sides overj=1,…​kj=1,\\ldots kwithj≠ij\\neq iproves the claim\. ∎

###### Claim 4\.7\.

𝔼E​‖X​α¯−X​α^∗‖2=\(D−d\)​σ2\\mathbb\{E\}\_\{E\}\|\|X\\bar\{\\alpha\}\-X\\hat\{\\alpha\}\_\{\*\}\|\|^\{2\}=\(D\-d\)\\sigma^\{2\}\.

###### Proof Sketch\.

The proof is based on straight calculations\. ∎

## 5Numerical Results

In this section, we report the empirical performance ofθ¯\\bar\{\\theta\}on three real\-world data sets loaded from the Python scikit\-learn datasets library, includingDigit,California Housing \(House\)andCovertype \(Cover\)\. On each set, features that have identical values across all data points are removed; the Cover data set was downsampled to 100k points for efficiency\. Statistics of the preprocessed data sets are shown in the following table\. All reported results were averaged over 100 random choices of the sketching matrices on Digit and House, and over 10 random choices on Cover\.

Dataset\#Instance\#FeatureDigit179761House206408Cover10000053We focus on evaluating the impact ofkkon the expected excess loss \(which is estimated using the given data\)\. Other hyper\-parameters were set as follows:m=d\+2m=d\+2, all sketching matrices have entries i\.i\.d\. sampled fromN​\(0,1/m\)N\(0,1/m\); to buildθ¯\\bar\{\\theta\}, each data set was evenly partitioned based on the default data order, and the few extran−p​kn\-pkpoints were abandoned\. The loss versuskkis shown in Figure[1](https://arxiv.org/html/2607.07888#S5.F1)\. Results show thatθ¯\\bar\{\\theta\}outperformsβ¯\\bar\{\\beta\}, which confirms the theoretical implication thatBθ≤BβB\_\{\\theta\}\\leq B\_\{\\beta\}if data are sampled i\.i\.d\. \(which is often satisfied in practice\)\. In addition, their performance gap first increases and then decreases, which is consistent with the theoretical implication of \([14](https://arxiv.org/html/2607.07888#S3.E14)\)\.

![Refer to caption](https://arxiv.org/html/2607.07888v1/Figure/error_digit.png)

![Refer to caption](https://arxiv.org/html/2607.07888v1/Figure/error_house.png)

![Refer to caption](https://arxiv.org/html/2607.07888v1/Figure/error_covtype.png)

Figure 1:Excess Loss versuskkon Digit \(left\), House \(mid\) and Cover \(right\)Figure[2](https://arxiv.org/html/2607.07888#S5.F2)shows the average time for building an estimator from a sketch, including the generation and application of sketching matrices\. As expected,β^i\\hat\{\\beta\}\_\{i\}consumes more time than simply performing OLS on\(X,Y\)\(X,Y\), whileθ^i\\hat\{\\theta\}\_\{i\}effectively reduces training time askkincreases\. These observations align with the time complexity analysis: \(i\) standard OLS takesO​\(n​d2\)O\(nd^\{2\}\)time, \(ii\)β^i\\hat\{\\beta\}\_\{i\}applies Gaussian sketching on the whole data set which takesO​\(m​d​n\)O\(mdn\)time, \(iii\)θ^i\\hat\{\\theta\}\_\{i\}applies Gaussian sketching on a subset which takesO​\(m​d​n/k\)O\(mdn/k\)time\. For largennand smalldd,β^i\\hat\{\\beta\}\_\{i\}would indeed take more time than OLS, whileθ^i\\hat\{\\theta\}\_\{i\}can remain more efficient with largekk\. In addition, the analysis suggestsθ^i\\hat\{\\theta\}\_\{i\}time decreases polynomially fast, as supported by Figure[2](https://arxiv.org/html/2607.07888#S5.F2)\(i\.e\.,θ^i\\hat\{\\theta\}\_\{i\}curve is almost straight under log\-scale y\-axis\)\.

![Refer to caption](https://arxiv.org/html/2607.07888v1/Figure/time_digit.png)

![Refer to caption](https://arxiv.org/html/2607.07888v1/Figure/time_house.png)

![Refer to caption](https://arxiv.org/html/2607.07888v1/Figure/time_covtype.png)

Figure 2:Training Time per estimator versuskkon Digit \(left\), House \(mid\) and Cover \(right\)
## References

## Appendix AAppendix: Proofs of Supporting Claims in Section[4\.2](https://arxiv.org/html/2607.07888#S4.SS2)

###### Claim\([4\.1](https://arxiv.org/html/2607.07888#S4.Thmtheorem1)\)\.

GivenEE, the following hold:

1. \(a\)XiT​E^i=0X\_\{i\}^\{T\}\\hat\{E\}\_\{i\}=0\.
2. \(b\)Si​XiS\_\{i\}X\_\{i\}andSi​E^iS\_\{i\}\\hat\{E\}\_\{i\}are independent\.
3. \(c\)𝔼S∣S​X,E​\[θ^i\]=𝔼S∣E​\[θ^i\]=α^i\\mathbb\{E\}\_\{S\\mid SX,E\}\[\\hat\{\\theta\}\_\{i\}\]=\\mathbb\{E\}\_\{S\\mid E\}\[\\hat\{\\theta\}\_\{i\}\]=\\hat\{\\alpha\}\_\{i\}and𝔼S∣E​\[θ¯\]=α¯\\mathbb\{E\}\_\{S\\mid E\}\[\\bar\{\\theta\}\]=\\bar\{\\alpha\}\.

###### Proof\.

To prove[\(a\)](https://arxiv.org/html/2607.07888#S4.I1.i1), recallα^i\\hat\{\\alpha\}\_\{i\}is a minimizer ofLi​\(α\)=‖Xi​α−Yi‖2L\_\{i\}\(\\alpha\)=\|\|X\_\{i\}\\alpha\-Y\_\{i\}\|\|^\{2\}\. Therefore

∂Li∂α\|α=α^i=2​XiT​Xi​α^i−2​XiT​Yi=2​XiT​Xi​α^i−2​XiT​\(Xi​α^i\+E^i\)=−2​XiT​E^i=0\.\\left\.\\frac\{\\partial L\_\{i\}\}\{\\partial\\alpha\}\\right\|\_\{\\alpha=\\hat\{\\alpha\}\_\{i\}\}=2X\_\{i\}^\{T\}X\_\{i\}\\hat\{\\alpha\}\_\{i\}\-2X\_\{i\}^\{T\}Y\_\{i\}=2X\_\{i\}^\{T\}X\_\{i\}\\hat\{\\alpha\}\_\{i\}\-2X\_\{i\}^\{T\}\(X\_\{i\}\\hat\{\\alpha\}\_\{i\}\+\\hat\{E\}\_\{i\}\)=\-2X\_\{i\}^\{T\}\\hat\{E\}\_\{i\}=0\.\(26\)
Claim[\(b\)](https://arxiv.org/html/2607.07888#S4.I1.i2)is due to a well\-known property that jointly\-Gaussian variables are independent if they are uncorrelated\. Specifically, givenEE, bothSi​XiS\_\{i\}X\_\{i\}andSi​E^iS\_\{i\}\\hat\{E\}\_\{i\}are jointly Gaussian because each of them is a linear combination of independent Gaussian entries inSiS\_\{i\}\. In addition, with Claim[\(a\)](https://arxiv.org/html/2607.07888#S4.I1.i1), it is not hard to see their correlation satisfies

c​o​r​r​\(Si​Xi,Si​E^i∣E,X\)∝𝔼S∣E​\[XiT​SiT​Si​E^i\]=XiT​E^i=0\.corr\(S\_\{i\}X\_\{i\},S\_\{i\}\\hat\{E\}\_\{i\}\\mid E,X\)\\propto\\mathbb\{E\}\_\{S\\mid E\}\[X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}\\hat\{E\}\_\{i\}\]=X\_\{i\}^\{T\}\\hat\{E\}\_\{i\}=0\.\(27\)
To prove[\(c\)](https://arxiv.org/html/2607.07888#S4.I1.i3), recallθ^i=arg⁡minα​‖Si​Xi​α−Si​Yi‖2\\hat\{\\theta\}\_\{i\}=\\arg\\min\_\{\\alpha\}\|\|S\_\{i\}X\_\{i\}\\alpha\-S\_\{i\}Y\_\{i\}\|\|^\{2\}andYi=Xi​α^i\+E^iY\_\{i\}=X\_\{i\}\\hat\{\\alpha\}\_\{i\}\+\\hat\{E\}\_\{i\}\. Then,

θ^i=\(XiT​SiT​Si​Xi\)−1​XiT​SiT​Si​\(Yi\)=\(XiT​SiT​Si​Xi\)−1​XiT​SiT​Si​\(Xi​α^i\+E^i\)=α^i\+\(XiT​SiT​Si​Xi\)−1​XiT​SiT​Si​E^i\.\\begin\{split\}\\hat\{\\theta\}\_\{i\}&=\(X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}X\_\{i\}\)^\{\-1\}X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}\(Y\_\{i\}\)\\\\\[1\.00006pt\] &=\(X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}X\_\{i\}\)^\{\-1\}X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}\(X\_\{i\}\\hat\{\\alpha\}\_\{i\}\+\\hat\{E\}\_\{i\}\)\\\\\[1\.00006pt\] &=\\hat\{\\alpha\}\_\{i\}\+\(X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}X\_\{i\}\)^\{\-1\}X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}\\hat\{E\}\_\{i\}\.\\end\{split\}\(28\)Taking expectation on both sides w\.r\.t\.SS, conditioned on\(S​X,E\)\(SX,E\), we have

𝔼S∣S​X,E​\[θ^i\]=α^i\+\(XiT​SiT​Si​Xi\)−1​XiT​SiT​𝔼S∣S​X,E​\[Si​E^i\]\.\\mathbb\{E\}\_\{S\\mid SX,E\}\[\\hat\{\\theta\}\_\{i\}\]=\\hat\{\\alpha\}\_\{i\}\+\(X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}X\_\{i\}\)^\{\-1\}X\_\{i\}^\{T\}S\_\{i\}^\{T\}\\,\\mathbb\{E\}\_\{S\\mid SX,E\}\[S\_\{i\}\\hat\{E\}\_\{i\}\]\.\(29\)On the right side, the second term is zero based on the following argument

𝔼S∣S​X,E​\[Si​E^i\]=𝔼S∣E​\[Si​E^i\]=𝔼S∣E​\[Si\]​E^i=0→,\\mathbb\{E\}\_\{S\\mid SX,E\}\[S\_\{i\}\\hat\{E\}\_\{i\}\]=\\mathbb\{E\}\_\{S\\mid E\}\[S\_\{i\}\\hat\{E\}\_\{i\}\]=\\mathbb\{E\}\_\{S\\mid E\}\[S\_\{i\}\]\\,\\hat\{E\}\_\{i\}=\\vec\{0\},\(30\)where the first equality holds becauseSi​E^iS\_\{i\}\\hat\{E\}\_\{i\}andSi​XiS\_\{i\}X\_\{i\}are independent \(due to Claim[\(b\)](https://arxiv.org/html/2607.07888#S4.I1.i2)\), and the second equality holds becauseE^i\\hat\{E\}\_\{i\}is fixed givenEE\. Based on the above, we have

𝔼S∣E​\[θ^i\]=ES​X∣E​\(𝔼S∣S​X,E​\[θ^i\]\)=ES​X∣E​\[α^i\]=α^i\.\\mathbb\{E\}\_\{S\\mid E\}\[\\hat\{\\theta\}\_\{i\}\]=E\_\{SX\\mid E\}\(\\mathbb\{E\}\_\{S\\mid SX,E\}\[\\hat\{\\theta\}\_\{i\}\]\)=E\_\{SX\\mid E\}\[\\hat\{\\alpha\}\_\{i\}\]=\\hat\{\\alpha\}\_\{i\}\.\(31\)This proves the first part of[\(c\)](https://arxiv.org/html/2607.07888#S4.I1.i3)\. The second part𝔼S∣E​\[θ¯\]=α¯\\mathbb\{E\}\_\{S\\mid E\}\[\\bar\{\\theta\}\]=\\bar\{\\alpha\}follows trivially\. ∎

###### Claim\([4\.2](https://arxiv.org/html/2607.07888#S4.Thmtheorem2)\)\.

𝔼E​\[L​\(α^∗\)\]=\(n−d\)​σ2\\mathbb\{E\}\_\{E\}\[L\(\\hat\{\\alpha\}\_\{\*\}\)\]=\(n\-d\)\\sigma^\{2\}and𝔼E​\[Li​\(α^i\)\]=\(p−d\)​σ2\\mathbb\{E\}\_\{E\}\[L\_\{i\}\(\\hat\{\\alpha\}\_\{i\}\)\]=\(p\-d\)\\sigma^\{2\}\.

###### Proof\.

LetG=X​\(XT​X\)−1​XT−InG=X\(X^\{T\}X\)^\{\-1\}X^\{T\}\-I\_\{n\}\. The first part of the claim can be verified as follows

𝔼E​\[L​\(α^∗\)\]=𝔼​‖X​α^∗−Y‖2=𝔼​‖G​E‖2=𝔼​tr​\[G​E​ET​GT\]=σ2​tr​\[G​GT\]=σ2​\(n−d\)\.\\mathbb\{E\}\_\{E\}\[L\(\\hat\{\\alpha\}\_\{\*\}\)\]=\\mathbb\{E\}\|\|X\\hat\{\\alpha\}\_\{\*\}\-Y\|\|^\{2\}=\\mathbb\{E\}\|\|GE\|\|^\{2\}=\\mathbb\{E\}\\mathrm\{tr\}\[GEE^\{T\}G^\{T\}\]=\\sigma^\{2\}\\mathrm\{tr\}\[GG^\{T\}\]=\\sigma^\{2\}\(n\-d\)\.\(32\)In \([32](https://arxiv.org/html/2607.07888#A1.E32)\), the second equality is based on the following arguments

‖X​α^∗−Y‖2=‖X​\(XT​X\)−1​XT​Y−Y‖2=‖X​\(XT​X\)−1​XT​\(X​α∗\+E\)−\(X​α∗\+E\)‖2=‖X​α∗\+X​\(XT​X\)−1​XT​E−X​α∗−E‖2=‖G​E‖2,\\begin\{split\}\|\|X\\hat\{\\alpha\}\_\{\*\}\-Y\|\|^\{2\}&=\|\|X\(X^\{T\}X\)^\{\-1\}X^\{T\}Y\-Y\|\|^\{2\}\\\\\[1\.00006pt\] &=\|\|X\(X^\{T\}X\)^\{\-1\}X^\{T\}\(X\\alpha\_\{\*\}\+E\)\-\(X\\alpha\_\{\*\}\+E\)\|\|^\{2\}\\\\\[1\.00006pt\] &=\|\|X\\alpha\_\{\*\}\+X\(X^\{T\}X\)^\{\-1\}X^\{T\}E\-X\\alpha\_\{\*\}\-E\|\|^\{2\}\\\\\[1\.00006pt\] &=\|\|GE\|\|^\{2\},\\end\{split\}\(33\)where the first equality is by the fact thatα^∗\\hat\{\\alpha\}\_\{\*\}minimizes‖X​α−Y‖2\|\|X\\alpha\-Y\|\|^\{2\}, and the second is by the fact thatY=X​α∗\+EY=X\\alpha\_\{\*\}\+E\. In \([32](https://arxiv.org/html/2607.07888#A1.E32)\), the last equality is by straight calculation i\.e\.,

tr​\[G​GT\]=tr​\[X​\(XT​X\)−1​XT​X​\(XT​X\)−1​XT\]−2​t​r​\[X​\(XT​X\)−1​XT\]\+tr​\[In\]=tr​\[Id\]−2​t​r​\[Id\]\+tr​\[In\]=n−d\.\\begin\{split\}\\mathrm\{tr\}\[GG^\{T\}\]&=\\mathrm\{tr\}\[X\(X^\{T\}X\)^\{\-1\}X^\{T\}X\(X^\{T\}X\)^\{\-1\}X^\{T\}\]\-2\\mathrm\{tr\}\[X\(X^\{T\}X\)^\{\-1\}X^\{T\}\]\+\\mathrm\{tr\}\[I\_\{n\}\]\\\\\[1\.00006pt\] &=\\mathrm\{tr\}\[I\_\{d\}\]\-2\\mathrm\{tr\}\[I\_\{d\}\]\+\\mathrm\{tr\}\[I\_\{n\}\]\\\\\[1\.00006pt\] &=n\-d\.\\end\{split\}\(34\)The second part of the claim can be verified in the same way, with\(X,Y,α^∗\)\(X,Y,\\hat\{\\alpha\}\_\{\*\}\)replaced by\(Xi,Yi,α^i\)\(X\_\{i\},Y\_\{i\},\\hat\{\\alpha\}\_\{i\}\)\. ∎

###### Claim\([4\.3](https://arxiv.org/html/2607.07888#S4.Thmtheorem3)\)\.

𝔼S,E​\[L​\(θ¯\)\]−𝔼E​\[L​\(α^∗\)\]=𝔼S,E​‖X​\(θ¯−α^∗\)‖2\\mathbb\{E\}\_\{S,E\}\[L\(\\bar\{\\theta\}\)\]\-\\mathbb\{E\}\_\{E\}\[L\(\\hat\{\\alpha\}\_\{\*\}\)\]=\\mathbb\{E\}\_\{S,E\}\|\|X\(\\bar\{\\theta\}\-\\hat\{\\alpha\}\_\{\*\}\)\|\|^\{2\}\.

###### Proof\.

First observe

𝔼S,E​‖X​\(θ¯−α^∗\)‖2=𝔼​‖X​θ¯−Y‖2\+𝔼​‖X​α^∗−Y‖2−2​𝔼​\(X​α^∗−Y\)T​\(X​θ¯−Y\)\.\\mathbb\{E\}\_\{S,E\}\|\|X\(\\bar\{\\theta\}\-\\hat\{\\alpha\}\_\{\*\}\)\|\|^\{2\}=\\mathbb\{E\}\|\|X\\bar\{\\theta\}\-Y\|\|^\{2\}\+\\mathbb\{E\}\|\|X\\hat\{\\alpha\}\_\{\*\}\-Y\|\|^\{2\}\-2\\mathbb\{E\}\(X\\hat\{\\alpha\}\_\{\*\}\-Y\)^\{T\}\(X\\bar\{\\theta\}\-Y\)\.\(35\)The first two terms are𝔼​\[L​\(θ¯\)\]\\mathbb\{E\}\[L\(\\bar\{\\theta\}\)\]and𝔼​\[L​\(α^∗\)\]\\mathbb\{E\}\[L\(\\hat\{\\alpha\}\_\{\*\}\)\]respectively\. It remains to show the last expectation is𝔼​\[L​\(α^∗\)\]\\mathbb\{E\}\[L\(\\hat\{\\alpha\}\_\{\*\}\)\]\. First,

𝔼S,E​\(X​α^∗−Y\)T​\(X​θ¯−Y\)=𝔼E​\[𝔼S∣E​\(X​α^∗−Y\)T​\(X​θ¯−Y\)\]=𝔼E​\(X​α^∗−Y\)T​\(X​𝔼S∣E​\[θ¯\]−Y\)=𝔼E​\(X​α^∗−Y\)T​\(X​α¯−Y\)=𝔼​α^∗T​XT​X​α¯\+𝔼​YT​Y−𝔼​YT​X​α¯−𝔼​α^∗T​XT​Y=𝔼​YT​Y−𝔼​α^∗T​XT​Y\.\\begin\{split\}\\mathbb\{E\}\_\{S,E\}\(X\\hat\{\\alpha\}\_\{\*\}\-Y\)^\{T\}\(X\\bar\{\\theta\}\-Y\)&=\\mathbb\{E\}\_\{E\}\\left\[\\mathbb\{E\}\_\{S\\mid E\}\(X\\hat\{\\alpha\}\_\{\*\}\-Y\)^\{T\}\(X\\bar\{\\theta\}\-Y\)\\right\]\\\\\[1\.00006pt\] &=\\mathbb\{E\}\_\{E\}\(X\\hat\{\\alpha\}\_\{\*\}\-Y\)^\{T\}\(X\\mathbb\{E\}\_\{S\\mid E\}\[\\bar\{\\theta\}\]\-Y\)\\\\\[1\.00006pt\] &=\\mathbb\{E\}\_\{E\}\(X\\hat\{\\alpha\}\_\{\*\}\-Y\)^\{T\}\(X\\bar\{\\alpha\}\-Y\)\\\\\[1\.00006pt\] &=\\mathbb\{E\}\\hat\{\\alpha\}\_\{\*\}^\{T\}X^\{T\}X\\bar\{\\alpha\}\+\\mathbb\{E\}Y^\{T\}Y\-\\mathbb\{E\}Y^\{T\}X\\bar\{\\alpha\}\-\\mathbb\{E\}\\hat\{\\alpha\}\_\{\*\}^\{T\}X^\{T\}Y\\\\\[1\.00006pt\] &=\\mathbb\{E\}Y^\{T\}Y\-\\mathbb\{E\}\\hat\{\\alpha\}\_\{\*\}^\{T\}X^\{T\}Y\.\\end\{split\}\(36\)Above, the second equality is by the fact that onlyθ¯\\bar\{\\theta\}depends onSS; the third equality follows𝔼S∣E​\[θ¯\]=α¯\\mathbb\{E\}\_\{S\\mid E\}\[\\bar\{\\theta\}\]=\\bar\{\\alpha\}in Claim[4\.1](https://arxiv.org/html/2607.07888#S4.Thmtheorem1)[\(c\)](https://arxiv.org/html/2607.07888#S4.I1.i3); the last equality holds because \(in its above line\) the first and third terms cancel each other i\.e\.,

α^∗T​XT​X​α¯=YT​X​\(XT​X\)−1​XT​X​α¯=YT​X​α¯\.\\hat\{\\alpha\}\_\{\*\}^\{T\}X^\{T\}X\\bar\{\\alpha\}=Y^\{T\}X\(X^\{T\}X\)^\{\-1\}X^\{T\}X\\bar\{\\alpha\}=Y^\{T\}X\\bar\{\\alpha\}\.\(37\)It remains to show the right side of \([36](https://arxiv.org/html/2607.07888#A1.E36)\) equals𝔼​\[L​\(α^∗\)\]\\mathbb\{E\}\[L\(\\hat\{\\alpha\}\_\{\*\}\)\]\. We will evaluate the two terms separately\.

To evaluate the first term𝔼​YT​Y\\mathbb\{E\}Y^\{T\}Y, recallY=X​α∗\+EY=X\\alpha\_\{\*\}\+E\. Then,

𝔼E​\[Y​YT\]=𝔼​\(X​α∗\+E\)​\(X​α∗\+E\)T=𝔼​\[X​α∗​α∗T​XT\+E​ET\+X​α∗​ET\+E​α∗T​XT\]=X​α∗​α∗T​XT\+𝔼​\[E​ET\]=X​α∗​α∗T​XT\+σ2​In\.\\begin\{split\}\\mathbb\{E\}\_\{E\}\[YY^\{T\}\]&=\\mathbb\{E\}\(X\\alpha\_\{\*\}\+E\)\(X\\alpha\_\{\*\}\+E\)^\{T\}\\\\\[1\.00006pt\] &=\\mathbb\{E\}\[X\\alpha\_\{\*\}\\alpha\_\{\*\}^\{T\}X^\{T\}\+EE^\{T\}\+X\\alpha\_\{\*\}E^\{T\}\+E\\alpha\_\{\*\}^\{T\}X^\{T\}\]\\\\\[1\.00006pt\] &=X\\alpha\_\{\*\}\\alpha\_\{\*\}^\{T\}X^\{T\}\+\\mathbb\{E\}\[EE^\{T\}\]\\\\\[1\.00006pt\] &=X\\alpha\_\{\*\}\\alpha\_\{\*\}^\{T\}X^\{T\}\+\\sigma^\{2\}I\_\{n\}\.\\end\{split\}\(38\)Above, the third equality holds because onlyEEis random and has zero mean; the last equality holds becauseEEhas i\.i\.d\. entries followingN​\(0,σ2\)N\(0,\\sigma^\{2\}\)\. Based on above, we have

𝔼E​\[YT​Y\]=𝔼​tr​\[Y​YT\]=tr​\[𝔼​\(Y​YT\)\]=tr​\[X​α∗​α∗T​XT\+σ2​In\]=α∗T​XT​X​α∗\+n​σ2\.\\mathbb\{E\}\_\{E\}\[Y^\{T\}Y\]=\\mathbb\{E\}\\mathrm\{tr\}\[YY^\{T\}\]=\\mathrm\{tr\}\[\\mathbb\{E\}\(YY^\{T\}\)\]=\\mathrm\{tr\}\[X\\alpha\_\{\*\}\\alpha\_\{\*\}^\{T\}X^\{T\}\+\\sigma^\{2\}I\_\{n\}\]=\\alpha\_\{\*\}^\{T\}X^\{T\}X\\alpha\_\{\*\}\+n\\sigma^\{2\}\.\(39\)To evaluate the second term𝔼​α^∗T​XT​Y\\mathbb\{E\}\\hat\{\\alpha\}\_\{\*\}^\{T\}X^\{T\}Y, recallα^∗\\hat\{\\alpha\}\_\{\*\}minimizes‖X​α−Y‖2\|\|X\\alpha\-Y\|\|^\{2\}\. Then,

𝔼E​\[α^∗T​XT​Y\]=𝔼​YT​X​\(XT​X\)−1​XT​Y=𝔼​tr​\[X​\(XT​X\)−1​XT​Y​YT\]=tr​\[X​\(XT​X\)−1​XT​𝔼​\(Y​YT\)\]=tr​\[X​\(XT​X\)−1​XT​\(X​α∗​α∗T​XT\+σ2​In\)\]=tr\[Xα∗α∗TXT\+σ2X\(XTX\)−1XT\)\]=α∗T​XT​X​α∗\+σ2​tr​\[Id\]=α∗T​XT​X​α∗\+d​σ2,\\begin\{split\}\\mathbb\{E\}\_\{E\}\[\\hat\{\\alpha\}\_\{\*\}^\{T\}X^\{T\}Y\]=\\mathbb\{E\}Y^\{T\}X\(X^\{T\}X\)^\{\-1\}X^\{T\}Y&=\\mathbb\{E\}\\mathrm\{tr\}\[X\(X^\{T\}X\)^\{\-1\}X^\{T\}YY^\{T\}\]\\\\\[1\.00006pt\] &=\\mathrm\{tr\}\[X\(X^\{T\}X\)^\{\-1\}X^\{T\}\\mathbb\{E\}\(YY^\{T\}\)\]\\\\\[1\.00006pt\] &=\\mathrm\{tr\}\[X\(X^\{T\}X\)^\{\-1\}X^\{T\}\(X\\alpha\_\{\*\}\\alpha\_\{\*\}^\{T\}X^\{T\}\+\\sigma^\{2\}I\_\{n\}\)\]\\\\\[1\.00006pt\] &=\\mathrm\{tr\}\[X\\alpha\_\{\*\}\\alpha\_\{\*\}^\{T\}X^\{T\}\+\\sigma^\{2\}X\(X^\{T\}X\)^\{\-1\}X^\{T\}\)\]\\\\\[1\.00006pt\] &=\\alpha\_\{\*\}^\{T\}X^\{T\}X\\alpha\_\{\*\}\+\\sigma^\{2\}\\mathrm\{tr\}\[I\_\{d\}\]\\\\\[1\.00006pt\] &=\\alpha\_\{\*\}^\{T\}X^\{T\}X\\alpha\_\{\*\}\+d\\sigma^\{2\},\\end\{split\}\(40\)where the 5th equality follows the above evaluation of𝔼​\[Y​YT\]\\mathbb\{E\}\[YY^\{T\}\]\. Plugging \([38](https://arxiv.org/html/2607.07888#A1.E38),[40](https://arxiv.org/html/2607.07888#A1.E40)\) back to \([36](https://arxiv.org/html/2607.07888#A1.E36)\), we have

𝔼S,E​\(X​α^∗−Y\)T​\(X​θ¯−Y\)=𝔼​YT​Y−𝔼​α^∗T​XT​Y=\(n−d\)​σ2=𝔼E∣X​\[L​\(α^∗\)\],\\mathbb\{E\}\_\{S,E\}\(X\\hat\{\\alpha\}\_\{\*\}\-Y\)^\{T\}\(X\\bar\{\\theta\}\-Y\)=\\mathbb\{E\}Y^\{T\}Y\-\\mathbb\{E\}\\hat\{\\alpha\}\_\{\*\}^\{T\}X^\{T\}Y=\(n\-d\)\\sigma^\{2\}=\\mathbb\{E\}\_\{E\\mid X\}\[L\(\\hat\{\\alpha\}\_\{\*\}\)\],\(41\)where the last equality is due to Claim[4\.2](https://arxiv.org/html/2607.07888#S4.Thmtheorem2)\. Putting it back to \([35](https://arxiv.org/html/2607.07888#A1.E35)\), we have

𝔼S,E∣X​‖X​\(θ¯−α^∗\)‖2=𝔼​‖X​θ¯−Y‖2\+𝔼​‖X​α^∗−Y‖2−2​𝔼​\(X​α^∗−Y\)T​\(X​θ¯−Y\)=L​\(θ¯\)\+L​\(α^∗\)−2​L​\(α^∗\)=L​\(θ¯\)−L​\(α^∗\)\.\\begin\{split\}\\mathbb\{E\}\_\{S,E\\mid X\}\|\|X\(\\bar\{\\theta\}\-\\hat\{\\alpha\}\_\{\*\}\)\|\|^\{2\}&=\\mathbb\{E\}\|\|X\\bar\{\\theta\}\-Y\|\|^\{2\}\+\\mathbb\{E\}\|\|X\\hat\{\\alpha\}\_\{\*\}\-Y\|\|^\{2\}\-2\\mathbb\{E\}\(X\\hat\{\\alpha\}\_\{\*\}\-Y\)^\{T\}\(X\\bar\{\\theta\}\-Y\)\\\\\[1\.00006pt\] &=L\(\\bar\{\\theta\}\)\+L\(\\hat\{\\alpha\}\_\{\*\}\)\-2L\(\\hat\{\\alpha\}\_\{\*\}\)\\\\\[1\.00006pt\] &=L\(\\bar\{\\theta\}\)\-L\(\\hat\{\\alpha\}\_\{\*\}\)\.\\end\{split\}\(42\)This proves the lemma\. ∎

###### Claim\([4\.4](https://arxiv.org/html/2607.07888#S4.Thmtheorem4)\)\.

𝔼S∣E​‖X​θ¯−X​α^∗‖2=1k2​∑i=1k𝔼​‖X​\(θ^i−α^i\)‖2\+‖X​α¯−X​α^∗‖2\\mathbb\{E\}\_\{S\\mid E\}\|\|X\\bar\{\\theta\}\-X\\hat\{\\alpha\}\_\{\*\}\|\|^\{2\}=\\frac\{1\}\{k^\{2\}\}\\sum\_\{i=1\}^\{k\}\\mathbb\{E\}\|\|X\(\\hat\{\\theta\}\_\{i\}\-\\hat\{\\alpha\}\_\{i\}\)\|\|^\{2\}\+\|\|X\\bar\{\\alpha\}\-X\\hat\{\\alpha\}\_\{\*\}\|\|^\{2\}\.

###### Proof\.

Since neitherα¯\\bar\{\\alpha\}orα^∗\\hat\{\\alpha\}\_\{\*\}depends onSS, we have

𝔼S∣E​‖X​θ¯−X​α^∗‖2=𝔼​‖X​θ¯−X​α¯\+X​α¯−X​α^∗‖2=𝔼​‖X​θ¯−X​α¯‖2\+‖X​α¯−X​α^∗‖2\+2​𝔼​\(θ¯−α¯\)T​XT​X​\(α¯−α^∗\)=𝔼​‖X​θ¯−X​α¯‖2\+‖X​α¯−X​α^∗‖2\+2​\(𝔼​\[θ¯\]−α¯\)T​XT​X​\(α¯−α^∗\)=𝔼​‖X​θ¯−X​α¯‖2\+‖X​α¯−X​α^∗‖2\.\\begin\{split\}\\mathbb\{E\}\_\{S\\mid E\}\|\|X\\bar\{\\theta\}\-X\\hat\{\\alpha\}\_\{\*\}\|\|^\{2\}&=\\mathbb\{E\}\|\|X\\bar\{\\theta\}\-X\\bar\{\\alpha\}\+X\\bar\{\\alpha\}\-X\\hat\{\\alpha\}\_\{\*\}\|\|^\{2\}\\\\\[1\.00006pt\] &=\\mathbb\{E\}\|\|X\\bar\{\\theta\}\-X\\bar\{\\alpha\}\|\|^\{2\}\+\|\|X\\bar\{\\alpha\}\-X\\hat\{\\alpha\}\_\{\*\}\|\|^\{2\}\+2\\mathbb\{E\}\(\\bar\{\\theta\}\-\\bar\{\\alpha\}\)^\{T\}X^\{T\}X\(\\bar\{\\alpha\}\-\\hat\{\\alpha\}\_\{\*\}\)\\\\\[1\.00006pt\] &=\\mathbb\{E\}\|\|X\\bar\{\\theta\}\-X\\bar\{\\alpha\}\|\|^\{2\}\+\|\|X\\bar\{\\alpha\}\-X\\hat\{\\alpha\}\_\{\*\}\|\|^\{2\}\+2\(\\mathbb\{E\}\[\\bar\{\\theta\}\]\-\\bar\{\\alpha\}\)^\{T\}X^\{T\}X\(\\bar\{\\alpha\}\-\\hat\{\\alpha\}\_\{\*\}\)\\\\\[1\.00006pt\] &=\\mathbb\{E\}\|\|X\\bar\{\\theta\}\-X\\bar\{\\alpha\}\|\|^\{2\}\+\|\|X\\bar\{\\alpha\}\-X\\hat\{\\alpha\}\_\{\*\}\|\|^\{2\}\.\\end\{split\}\(43\)Above, the third equality holds because onlyθ¯\\bar\{\\theta\}depends onSS, and the last equality holds because𝔼S∣E​\[θ¯\]=α¯\\mathbb\{E\}\_\{S\\mid E\}\[\\bar\{\\theta\}\]=\\bar\{\\alpha\}by Claim[4\.1](https://arxiv.org/html/2607.07888#S4.Thmtheorem1)[\(c\)](https://arxiv.org/html/2607.07888#S4.I1.i3)\. For the first term, by the designs of averaged estimators,

𝔼S∣E​‖X​θ¯−X​α¯‖2=𝔼​‖1k​∑i=1kX​\(θ^i−α^i\)‖2=𝔼​1k2​∑i=1k‖X​\(θ^i−α^i\)‖2\+𝔼​1k2​∑i=1k∑j≠i\(θ^i−α^i\)T​XT​X​\(θ^j−α^j\)=𝔼​1k2​∑i=1k‖X​\(θ^i−α^i\)‖2\.\\begin\{split\}\\mathbb\{E\}\_\{S\\mid E\}\|\|X\\bar\{\\theta\}\-X\\bar\{\\alpha\}\|\|^\{2\}&=\\mathbb\{E\}\|\|\\frac\{1\}\{k\}\\sum\_\{i=1\}^\{k\}X\(\\hat\{\\theta\}\_\{i\}\-\\hat\{\\alpha\}\_\{i\}\)\|\|^\{2\}\\\\ &=\\mathbb\{E\}\\frac\{1\}\{k^\{2\}\}\\sum\_\{i=1\}^\{k\}\|\|X\(\\hat\{\\theta\}\_\{i\}\-\\hat\{\\alpha\}\_\{i\}\)\|\|^\{2\}\+\\mathbb\{E\}\\frac\{1\}\{k^\{2\}\}\\sum\_\{i=1\}^\{k\}\\sum\_\{j\\neq i\}\(\\hat\{\\theta\}\_\{i\}\-\\hat\{\\alpha\}\_\{i\}\)^\{T\}X^\{T\}X\(\\hat\{\\theta\}\_\{j\}\-\\hat\{\\alpha\}\_\{j\}\)\\\\ &=\\mathbb\{E\}\\frac\{1\}\{k^\{2\}\}\\sum\_\{i=1\}^\{k\}\|\|X\(\\hat\{\\theta\}\_\{i\}\-\\hat\{\\alpha\}\_\{i\}\)\|\|^\{2\}\.\\end\{split\}\(44\)Above, the double sum is zero for two reasons: \(i\)θ^i,θ^j\\hat\{\\theta\}\_\{i\},\\hat\{\\theta\}\_\{j\}are independent because they are respectively built onSi,SjS\_\{i\},S\_\{j\}which are independent; \(ii\) Claim[4\.1](https://arxiv.org/html/2607.07888#S4.Thmtheorem1)[\(c\)](https://arxiv.org/html/2607.07888#S4.I1.i3)says𝔼S∣E​\[θ^i\]=α^i\\mathbb\{E\}\_\{S\\mid E\}\[\\hat\{\\theta\}\_\{i\}\]=\\hat\{\\alpha\}\_\{i\}for anyii; hence, every term in the double sum satisfies

𝔼S∣E​\(θ^i−α^i\)T​XT​X​\(θ^j−α^j\)=\(𝔼​\[θ^i\]−α^i\)T​XT​X​\(𝔼​\[θ^j\]−α^j\)=0\.\\mathbb\{E\}\_\{S\\mid E\}\(\\hat\{\\theta\}\_\{i\}\-\\hat\{\\alpha\}\_\{i\}\)^\{T\}X^\{T\}X\(\\hat\{\\theta\}\_\{j\}\-\\hat\{\\alpha\}\_\{j\}\)=\(\\mathbb\{E\}\[\\hat\{\\theta\}\_\{i\}\]\-\\hat\{\\alpha\}\_\{i\}\)^\{T\}X^\{T\}X\(\\mathbb\{E\}\[\\hat\{\\theta\}\_\{j\}\]\-\\hat\{\\alpha\}\_\{j\}\)=0\.\(45\)Plugging \([44](https://arxiv.org/html/2607.07888#A1.E44)\) back to \([43](https://arxiv.org/html/2607.07888#A1.E43)\) proves the claim\. ∎

###### Claim\([4\.5](https://arxiv.org/html/2607.07888#S4.Thmtheorem5)\)\.

GivenEE, we have

1. \(a\)𝔼S∣E​‖Xi​\(θ^i−α^i\)‖2=dm−d−1​Li​\(α^i\)\\mathbb\{E\}\_\{S\\mid E\}\|\|X\_\{i\}\(\\hat\{\\theta\}\_\{i\}\-\\hat\{\\alpha\}\_\{i\}\)\|\|^\{2\}=\\frac\{d\}\{m\-d\-1\}L\_\{i\}\(\\hat\{\\alpha\}\_\{i\}\)\.
2. \(b\)𝔼S∣S​X,E​\(θ^i−α^i\)​\(θ^i−α^i\)T=\(XiT​SiT​Si​Xi\)−1​1m​Li​\(α^i\)\\mathbb\{E\}\_\{S\\mid SX,E\}\(\\hat\{\\theta\}\_\{i\}\-\\hat\{\\alpha\}\_\{i\}\)\(\\hat\{\\theta\}\_\{i\}\-\\hat\{\\alpha\}\_\{i\}\)^\{T\}=\(X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}X\_\{i\}\)^\{\-1\}\\frac\{1\}\{m\}L\_\{i\}\(\\hat\{\\alpha\}\_\{i\}\)\.
3. \(c\)𝔼S​\(XiT​SiT​Si​Xi\)−1=\(XiT​Xi\)−1​mm−d−1\\mathbb\{E\}\_\{S\}\(X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}X\_\{i\}\)^\{\-1\}=\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}\\frac\{m\}\{m\-d\-1\}\.

###### Proof\.

All results are directly adapted from\(bartan2023distributed, Lemma 1\)\. This lemma says given any\(X,Y\)\(X,Y\)and Gaussian sketchingQ∈ℝm×nQ\\in\\mathbb\{R\}^\{m\\times n\}satisfying𝔼​QT​Q=In\\mathbb\{E\}Q^\{T\}Q=I\_\{n\}, we have𝔼Q​‖X​\(γ^Q−γ^\)‖2=dm−d−1​L​\(γ^\)\\mathbb\{E\}\_\{Q\}\|\|X\(\\hat\{\\gamma\}\_\{Q\}\-\\hat\{\\gamma\}\)\|\|^\{2\}=\\frac\{d\}\{m\-d\-1\}L\(\\hat\{\\gamma\}\), whereγ^\\hat\{\\gamma\}is a minimizer ofL​\(α\)=‖X​α−Y‖2L\(\\alpha\)=\|\|X\\alpha\-Y\|\|^\{2\}andγ^Q\\hat\{\\gamma\}\_\{Q\}is a minimizer of‖Q​X​α−Q​Y‖2\|\|QX\\alpha\-QY\|\|^\{2\}\. The original proof invokes two results\. First,𝔼Q∣Q​X​\(γ^Q−γ^\)​\(γ^Q−γ^\)T=\(XT​QT​Q​X\)−1​1m​L​\(γ^\)\\mathbb\{E\}\_\{Q\\mid QX\}\(\\hat\{\\gamma\}\_\{Q\}\-\\hat\{\\gamma\}\)\(\\hat\{\\gamma\}\_\{Q\}\-\\hat\{\\gamma\}\)^\{T\}=\(X^\{T\}Q^\{T\}QX\)^\{\-1\}\\frac\{1\}\{m\}L\(\\hat\{\\gamma\}\)based on straight calculations and the fact that𝔼Q∣Q​X​\[γ^Q\]=γ^\\mathbb\{E\}\_\{Q\\mid QX\}\[\\hat\{\\gamma\}\_\{Q\}\]=\\hat\{\\gamma\}\. Second,𝔼Q​\(XT​QT​Q​X\)−1=\(XT​X\)−1​mm−d−1\\mathbb\{E\}\_\{Q\}\(X^\{T\}Q^\{T\}QX\)^\{\-1\}=\(X^\{T\}X\)^\{\-1\}\\frac\{m\}\{m\-d\-1\}sinceQ​XQXis a Wishart matrix whose expected inverse is well\-known\.

We simply adapt the above results from\(Q​X,Q​Y\)\(QX,QY\)to\(Q​Xi,Q​Yi\)\(QX\_\{i\},QY\_\{i\}\)\. This is done by replacing the above quantities\(X,Y,Q,γ^,γ^Q,L\)\(X,Y,Q,\\hat\{\\gamma\},\\hat\{\\gamma\}\_\{Q\},L\)with\(Xi,Yi,Si,α^i,θ^i,Li\)\(X\_\{i\},Y\_\{i\},S\_\{i\},\\hat\{\\alpha\}\_\{i\},\\hat\{\\theta\}\_\{i\},L\_\{i\}\), plus a new property that𝔼​\[θ^i\]=α^i\\mathbb\{E\}\[\\hat\{\\theta\}\_\{i\}\]=\\hat\{\\alpha\}\_\{i\}in Claim[4\.1](https://arxiv.org/html/2607.07888#S4.Thmtheorem1)[\(c\)](https://arxiv.org/html/2607.07888#S4.I1.i3)\. ∎

###### Claim\([4\.7](https://arxiv.org/html/2607.07888#S4.Thmtheorem7)\)\.

𝔼E​‖X​α¯−X​α^∗‖2=\(D−d\)​σ2\\mathbb\{E\}\_\{E\}\|\|X\\bar\{\\alpha\}\-X\\hat\{\\alpha\}\_\{\*\}\|\|^\{2\}=\(D\-d\)\\sigma^\{2\}\.

###### Proof\.

SinceY=X​α∗\+EY=X\\alpha\_\{\*\}\+Eandα^∗\\hat\{\\alpha\}\_\{\*\}is a minimizer of‖X​α−Y‖2\|\|X\\alpha\-Y\|\|^\{2\},

α^∗=\(XT​X\)−1​XT​Y=\(XT​X\)−1​XT​\(X​α∗\+E\)=α∗\+\(XT​X\)−1​XT​E\.\\hat\{\\alpha\}\_\{\*\}=\(X^\{T\}X\)^\{\-1\}X^\{T\}Y=\(X^\{T\}X\)^\{\-1\}X^\{T\}\(X\\alpha\_\{\*\}\+E\)=\\alpha\_\{\*\}\+\(X^\{T\}X\)^\{\-1\}X^\{T\}E\.\(46\)Similarly, sinceYi=Xi​α∗\+EiY\_\{i\}=X\_\{i\}\\alpha\_\{\*\}\+E\_\{i\}andα^i\\hat\{\\alpha\}\_\{i\}is a minimizer of‖Xi​α−Yi‖2\|\|X\_\{i\}\\alpha\-Y\_\{i\}\|\|^\{2\},

α^i=\(XiT​Xi\)−1​XiT​Yi=\(XiT​Xi\)−1​XiT​\(Xi​α∗\+Ei\)=α∗\+\(XiT​Xi\)−1​XiT​Ei\.\\hat\{\\alpha\}\_\{i\}=\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}X\_\{i\}^\{T\}Y\_\{i\}=\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}X\_\{i\}^\{T\}\(X\_\{i\}\\alpha\_\{\*\}\+E\_\{i\}\)=\\alpha\_\{\*\}\+\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}X\_\{i\}^\{T\}E\_\{i\}\.\(47\)LetHi=1k​\(XiT​Xi\)−1​XiT​EiH\_\{i\}=\\frac\{1\}\{k\}\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}X\_\{i\}^\{T\}E\_\{i\}\. The above implies

α¯=1k​∑i=1kα^i=1k​∑i=1kα∗\+1k​∑i=1k\(XiT​Xi\)−1​XiT​Ei=α∗\+∑i=1kHi\.\\bar\{\\alpha\}=\\frac\{1\}\{k\}\\sum\_\{i=1\}^\{k\}\\hat\{\\alpha\}\_\{i\}=\\frac\{1\}\{k\}\\sum\_\{i=1\}^\{k\}\\alpha\_\{\*\}\+\\frac\{1\}\{k\}\\sum\_\{i=1\}^\{k\}\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}X\_\{i\}^\{T\}E\_\{i\}=\\alpha\_\{\*\}\+\\sum\_\{i=1\}^\{k\}H\_\{i\}\.\(48\)This further impliesα¯−α^∗=∑i=1kHi−\(XT​X\)−1​XT​E\\bar\{\\alpha\}\-\\hat\{\\alpha\}\_\{\*\}=\\sum\_\{i=1\}^\{k\}H\_\{i\}\-\(X^\{T\}X\)^\{\-1\}X^\{T\}Eand hence

𝔼E​‖X​\(α¯−α^∗\)‖2=𝔼​‖X​∑i=1kHi−X​\(XT​X\)−1​XT​E‖2=𝔼​‖X​∑i=1kHi‖2\+𝔼​‖X​\(XT​X\)−1​XT​E‖2−2​𝔼​\(X​∑i=1kHi\)T​X​\(XT​X\)−1​XT​E\.\\begin\{split\}\\mathbb\{E\}\_\{E\}\|\|X\(\\bar\{\\alpha\}\-\\hat\{\\alpha\}\_\{\*\}\)\|\|^\{2\}&=\\mathbb\{E\}\|\|X\\sum\_\{i=1\}^\{k\}H\_\{i\}\-X\(X^\{T\}X\)^\{\-1\}X^\{T\}E\|\|^\{2\}\\\\ &=\\mathbb\{E\}\|\|X\\sum\_\{i=1\}^\{k\}H\_\{i\}\|\|^\{2\}\+\\mathbb\{E\}\|\|X\(X^\{T\}X\)^\{\-1\}X^\{T\}E\|\|^\{2\}\-2\\mathbb\{E\}\(X\\sum\_\{i=1\}^\{k\}H\_\{i\}\)^\{T\}X\(X^\{T\}X\)^\{\-1\}X^\{T\}E\.\\end\{split\}\(49\)On the right side, we will evaluate the three expectations separately\.

1st Term: To evaluate𝔼E​‖X​∑i=1kHi‖2\\mathbb\{E\}\_\{E\}\|\|X\\sum\_\{i=1\}^\{k\}H\_\{i\}\|\|^\{2\}, observe that

𝔼E​‖X​∑i=1kHi‖2=𝔼​tr​\[X​∑i,j=1kHi​HjT​XT\]=𝔼​tr​\[X​∑i=1kHi​HiT​XT\+X​∑i=1k∑j≠iHi​HjT​XT\]=𝔼​tr​\[X​∑i=1kHi​HiT​XT\]\+𝔼​tr​\[X​∑i=1k∑j≠iHi​HjT​XT\]=tr​\[X​∑i=1k𝔼​\(Hi​HiT\)​XT\]\+tr​\[X​∑i=1k∑j≠i𝔼​\(Hi​HjT\)​XT\]=tr​\[X​∑i=1k𝔼​\(Hi​HiT\)​XT\],\\begin\{split\}\\mathbb\{E\}\_\{E\}\|\|X\\sum\_\{i=1\}^\{k\}H\_\{i\}\|\|^\{2\}=\\mathbb\{E\}\\mathrm\{tr\}\[X\\sum\_\{i,j=1\}^\{k\}H\_\{i\}H\_\{j\}^\{T\}X^\{T\}\]&=\\mathbb\{E\}\\mathrm\{tr\}\[X\\sum\_\{i=1\}^\{k\}H\_\{i\}H\_\{i\}^\{T\}X^\{T\}\+X\\sum\_\{i=1\}^\{k\}\\sum\_\{j\\neq i\}H\_\{i\}H\_\{j\}^\{T\}X^\{T\}\]\\\\ &=\\mathbb\{E\}\\mathrm\{tr\}\[X\\sum\_\{i=1\}^\{k\}H\_\{i\}H\_\{i\}^\{T\}X^\{T\}\]\+\\mathbb\{E\}\\mathrm\{tr\}\[X\\sum\_\{i=1\}^\{k\}\\sum\_\{j\\neq i\}H\_\{i\}H\_\{j\}^\{T\}X^\{T\}\]\\\\ &=\\mathrm\{tr\}\[X\\sum\_\{i=1\}^\{k\}\\mathbb\{E\}\(H\_\{i\}H\_\{i\}^\{T\}\)X^\{T\}\]\+\\mathrm\{tr\}\[X\\sum\_\{i=1\}^\{k\}\\sum\_\{j\\neq i\}\\mathbb\{E\}\(H\_\{i\}H\_\{j\}^\{T\}\)X^\{T\}\]\\\\ &=\\mathrm\{tr\}\[X\\sum\_\{i=1\}^\{k\}\\mathbb\{E\}\(H\_\{i\}H\_\{i\}^\{T\}\)X^\{T\}\],\\end\{split\}\(50\)where the last equality holds becauseEEhas i\.i\.d\. zero\-mean entries so that𝔼E​Ei​EjT=0​Ip\\mathbb\{E\}\_\{E\}E\_\{i\}E\_\{j\}^\{T\}=0I\_\{p\}, which implies

𝔼E​Hi​HjT=𝔼​1k2​\(XiT​Xi\)−1​XiT​Ei​EjT​Xj​\(XjT​Xj\)−1=1k2​\(XiT​Xi\)−1​XiT​𝔼​\(Ei​EjT\)​Xj​\(XjT​Xj\)−1=0​Id\.\\mathbb\{E\}\_\{E\}H\_\{i\}H\_\{j\}^\{T\}=\\mathbb\{E\}\\frac\{1\}\{k^\{2\}\}\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}X\_\{i\}^\{T\}E\_\{i\}E\_\{j\}^\{T\}X\_\{j\}\(X\_\{j\}^\{T\}X\_\{j\}\)^\{\-1\}=\\frac\{1\}\{k^\{2\}\}\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}X\_\{i\}^\{T\}\\mathbb\{E\}\(E\_\{i\}E\_\{j\}^\{T\}\)X\_\{j\}\(X\_\{j\}^\{T\}X\_\{j\}\)^\{\-1\}=0I\_\{d\}\.\(51\)It remains to evaluate the right side of \([50](https://arxiv.org/html/2607.07888#A1.E50)\)\. Since𝔼E​Ei​EiT=σ2​Ip\\mathbb\{E\}\_\{E\}E\_\{i\}E\_\{i\}^\{T\}=\\sigma^\{2\}I\_\{p\},

𝔼E​Hi​HiT=𝔼​1k2​\(XiT​Xi\)−1​XiT​Ei​EiT​Xi​\(XiT​Xi\)−1=1k2​\(XiT​Xi\)−1​XiT​𝔼​\(Ei​EiT\)​Xi​\(XiT​Xi\)−1=σ2k2​\(XiT​Xi\)−1\.\\begin\{split\}\\mathbb\{E\}\_\{E\}H\_\{i\}H\_\{i\}^\{T\}=\\mathbb\{E\}\\frac\{1\}\{k^\{2\}\}\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}X\_\{i\}^\{T\}E\_\{i\}E\_\{i\}^\{T\}X\_\{i\}\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}&=\\frac\{1\}\{k^\{2\}\}\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}X\_\{i\}^\{T\}\\mathbb\{E\}\(E\_\{i\}E\_\{i\}^\{T\}\)X\_\{i\}\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}\\\\ &=\\frac\{\\sigma^\{2\}\}\{k^\{2\}\}\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}\.\\end\{split\}\(52\)Plugging \([52](https://arxiv.org/html/2607.07888#A1.E52)\) back to \([50](https://arxiv.org/html/2607.07888#A1.E50)\), plus the fact thatXT​X=∑j=1k\(XjT​Xj\)X^\{T\}X=\\sum\_\{j=1\}^\{k\}\(X\_\{j\}^\{T\}X\_\{j\}\), we have

𝔼E​‖X​∑i=1kHi‖2=tr​\[X​∑i=1k𝔼​\(Hi​HiT\)​XT\]=tr​\[∑i=1k𝔼​\(Hi​HiT\)​XT​X\]=tr​\[σ2k2​∑i=1k\(XiT​Xi\)−1​∑j=1k\(XjT​Xj\)\]=tr​\[σ2​D\]=D​σ2\.\\begin\{split\}\\mathbb\{E\}\_\{E\}\|\|X\\sum\_\{i=1\}^\{k\}H\_\{i\}\|\|^\{2\}=\\mathrm\{tr\}\\left\[X\\sum\_\{i=1\}^\{k\}\\mathbb\{E\}\(H\_\{i\}H\_\{i\}^\{T\}\)X^\{T\}\\right\]&=\\mathrm\{tr\}\\left\[\\sum\_\{i=1\}^\{k\}\\mathbb\{E\}\(H\_\{i\}H\_\{i\}^\{T\}\)X^\{T\}X\\right\]\\\\ &=\\mathrm\{tr\}\\left\[\\frac\{\\sigma^\{2\}\}\{k^\{2\}\}\\sum\_\{i=1\}^\{k\}\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}\\sum\_\{j=1\}^\{k\}\(X\_\{j\}^\{T\}X\_\{j\}\)\\right\]\\\\ &=\\mathrm\{tr\}\[\\sigma^\{2\}D\]=D\\sigma^\{2\}\.\\end\{split\}\(53\)2nd Term: To evaluate𝔼​‖X​\(XT​X\)−1​XT​E‖2\\mathbb\{E\}\|\|X\(X^\{T\}X\)^\{\-1\}X^\{T\}E\|\|^\{2\}, recall𝔼E​E​ET=σ2​In\\mathbb\{E\}\_\{E\}EE^\{T\}=\\sigma^\{2\}I\_\{n\}\. Then

𝔼E​‖X​\(XT​X\)−1​XT​E‖2=𝔼​tr​\[X​\(XT​X\)−1​XT​E​ET​X​\(XT​X\)−1​XT\]=tr​\[X​\(XT​X\)−1​XT​𝔼​\(E​ET\)​X​\(XT​X\)−1​XT\]=σ2​tr​\[X​\(XT​X\)−1​XT​X​\(XT​X\)−1​XT\]=σ2​tr​\[Id\]=d​σ2\.\\begin\{split\}\\mathbb\{E\}\_\{E\}\|\|X\(X^\{T\}X\)^\{\-1\}X^\{T\}E\|\|^\{2\}&=\\mathbb\{E\}\\mathrm\{tr\}\[X\(X^\{T\}X\)^\{\-1\}X^\{T\}EE^\{T\}X\(X^\{T\}X\)^\{\-1\}X^\{T\}\]\\\\\[1\.00006pt\] &=\\mathrm\{tr\}\[X\(X^\{T\}X\)^\{\-1\}X^\{T\}\\mathbb\{E\}\(EE^\{T\}\)X\(X^\{T\}X\)^\{\-1\}X^\{T\}\]\\\\\[1\.00006pt\] &=\\sigma^\{2\}\\mathrm\{tr\}\[X\(X^\{T\}X\)^\{\-1\}X^\{T\}X\(X^\{T\}X\)^\{\-1\}X^\{T\}\]\\\\\[1\.00006pt\] &=\\sigma^\{2\}\\mathrm\{tr\}\[I\_\{d\}\]=d\\sigma^\{2\}\.\\end\{split\}\(54\)3rd Term: To evaluate𝔼E​\(X​∑i=1kHi\)T​X​\(XT​X\)−1​XT​E\\mathbb\{E\}\_\{E\}\(X\\sum\_\{i=1\}^\{k\}H\_\{i\}\)^\{T\}X\(X^\{T\}X\)^\{\-1\}X^\{T\}E, recallXT​E=∑j=1kXjT​EjX^\{T\}E=\\sum\_\{j=1\}^\{k\}X\_\{j\}^\{T\}E\_\{j\}\. Then

𝔼E​\(X​∑i=1kHi\)T​X​\(XT​X\)−1​XT​E=𝔼​∑i=1kHiT​XT​E=𝔼​∑i=1k∑j=1kHiT​XjT​Ej=𝔼​∑i=1kHiT​XiT​Ei\+𝔼​∑i=1k∑j≠iHiT​XjT​Ej=𝔼​∑i=1kHiT​XiT​Ei\.\\begin\{split\}\\mathbb\{E\}\_\{E\}\(X\\sum\_\{i=1\}^\{k\}H\_\{i\}\)^\{T\}X\(X^\{T\}X\)^\{\-1\}X^\{T\}E=\\mathbb\{E\}\\sum\_\{i=1\}^\{k\}H\_\{i\}^\{T\}X^\{T\}E&=\\mathbb\{E\}\\sum\_\{i=1\}^\{k\}\\sum\_\{j=1\}^\{k\}H\_\{i\}^\{T\}X\_\{j\}^\{T\}E\_\{j\}\\\\ &=\\mathbb\{E\}\\sum\_\{i=1\}^\{k\}H\_\{i\}^\{T\}X\_\{i\}^\{T\}E\_\{i\}\+\\mathbb\{E\}\\sum\_\{i=1\}^\{k\}\\sum\_\{j\\neq i\}H\_\{i\}^\{T\}X\_\{j\}^\{T\}E\_\{j\}\\\\ &=\\mathbb\{E\}\\sum\_\{i=1\}^\{k\}H\_\{i\}^\{T\}X\_\{i\}^\{T\}E\_\{i\}\.\\end\{split\}\(55\)Above, the last equality holds because forj≠ij\\neq i,EjE\_\{j\}andHiH\_\{i\}\(depending onEiE\_\{i\}\) are independent so that

𝔼E​∑i=1k∑j≠iHiT​XjT​Ej=∑i=1k∑j≠i𝔼​\[Hi\]T​XjT​𝔼​\[Ej\]=0→\.\\mathbb\{E\}\_\{E\}\\sum\_\{i=1\}^\{k\}\\sum\_\{j\\neq i\}H\_\{i\}^\{T\}X\_\{j\}^\{T\}E\_\{j\}=\\sum\_\{i=1\}^\{k\}\\sum\_\{j\\neq i\}\\mathbb\{E\}\[H\_\{i\}\]^\{T\}X\_\{j\}^\{T\}\\mathbb\{E\}\[E\_\{j\}\]=\\vec\{0\}\.\(56\)It remains to evaluate the right side of \([55](https://arxiv.org/html/2607.07888#A1.E55)\)\. By plugging inHi=1k​\(XiT​Xi\)−1​XiT​EiH\_\{i\}=\\frac\{1\}\{k\}\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}X\_\{i\}^\{T\}E\_\{i\}, we have

𝔼E​∑i=1kHiT​XiT​Ei=𝔼​1k​∑i=1kEiT​Xi​\(XiT​Xi\)−1​XiT​Ei=𝔼​1k​∑i=1ktr​\[Xi​\(XiT​Xi\)−1​XiT​Ei​EiT\]=1k​∑i=1ktr​\[Xi​\(XiT​Xi\)−1​XiT​𝔼​\(Ei​EiT\)\]=σ2k​∑i=1ktr​\[Xi​\(XiT​Xi\)−1​XiT\]=σ2k​∑i=1ktr​\[Id\]=d​σ2\.\\begin\{split\}\\mathbb\{E\}\_\{E\}\\sum\_\{i=1\}^\{k\}H\_\{i\}^\{T\}X\_\{i\}^\{T\}E\_\{i\}&=\\mathbb\{E\}\\frac\{1\}\{k\}\\sum\_\{i=1\}^\{k\}E\_\{i\}^\{T\}X\_\{i\}\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}X\_\{i\}^\{T\}E\_\{i\}\\\\ &=\\mathbb\{E\}\\frac\{1\}\{k\}\\sum\_\{i=1\}^\{k\}\\mathrm\{tr\}\[X\_\{i\}\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}X\_\{i\}^\{T\}E\_\{i\}E\_\{i\}^\{T\}\]\\\\ &=\\frac\{1\}\{k\}\\sum\_\{i=1\}^\{k\}\\mathrm\{tr\}\[X\_\{i\}\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}X\_\{i\}^\{T\}\\mathbb\{E\}\(E\_\{i\}E\_\{i\}^\{T\}\)\]\\\\ &=\\frac\{\\sigma^\{2\}\}\{k\}\\sum\_\{i=1\}^\{k\}\\mathrm\{tr\}\[X\_\{i\}\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}X\_\{i\}^\{T\}\]\\\\ &=\\frac\{\\sigma^\{2\}\}\{k\}\\sum\_\{i=1\}^\{k\}\\mathrm\{tr\}\[I\_\{d\}\]=d\\sigma^\{2\}\.\\end\{split\}\(57\)Plugging this back to \([55](https://arxiv.org/html/2607.07888#A1.E55)\), the 3rd term is

𝔼E​\(X​∑i=1kHi\)T​X​\(XT​X\)−1​XT​E=d​σ2\.\\mathbb\{E\}\_\{E\}\(X\\sum\_\{i=1\}^\{k\}H\_\{i\}\)^\{T\}X\(X^\{T\}X\)^\{\-1\}X^\{T\}E=d\\sigma^\{2\}\.\(58\)Wrap Up\. Finally, plugging the evaluations of all terms back to \([49](https://arxiv.org/html/2607.07888#A1.E49)\), we have

𝔼E​‖X​\(α¯−α^∗\)‖2=𝔼​‖X​∑i=1kHi‖2\+𝔼​‖X​\(XT​X\)−1​XT​E‖2−2​𝔼​\(X​∑i=1kHi\)T​X​\(XT​X\)−1​XT​E=D​σ2\+d​σ2−2​d​σ2=\(D−d\)​σ2\.\\begin\{split\}\\mathbb\{E\}\_\{E\}\|\|X\(\\bar\{\\alpha\}\-\\hat\{\\alpha\}\_\{\*\}\)\|\|^\{2\}&=\\mathbb\{E\}\|\|X\\sum\_\{i=1\}^\{k\}H\_\{i\}\|\|^\{2\}\+\\mathbb\{E\}\|\|X\(X^\{T\}X\)^\{\-1\}X^\{T\}E\|\|^\{2\}\-2\\mathbb\{E\}\(X\\sum\_\{i=1\}^\{k\}H\_\{i\}\)^\{T\}X\(X^\{T\}X\)^\{\-1\}X^\{T\}E\\\\ &=D\\sigma^\{2\}\+d\\sigma^\{2\}\-2d\\sigma^\{2\}\\\\ &=\(D\-d\)\\sigma^\{2\}\.\\end\{split\}\(59\)This proves the claim\. ∎

## Appendix BAppendix: Proofs of other Claims

###### Lemma\([2\.1](https://arxiv.org/html/2607.07888#S2.Thmtheorem1)\)\.

With probability one,D≥dD\\geq dand the equality is achieved whenXiT​Xi=XjT​XjX\_\{i\}^\{T\}X\_\{i\}=X\_\{j\}^\{T\}X\_\{j\}for alli≠ji\\neq j\.

###### Proof\.

By presumption allXiT​XiX\_\{i\}^\{T\}X\_\{i\}’s are invertible with probability one\. Consider two cases\. Whenj=ij=i, it is clear thatDi​j=tr​\[Id\]=dD\_\{ij\}=\\mathrm\{tr\}\[I\_\{d\}\]=d\. Whenj≠ij\\neq i, we will analyzeDi​j\+Dj​iD\_\{ij\}\+D\_\{ji\}for each pair of\(i,j\)\(i,j\)\. Let

Gi​j=\(XiT​Xi\)​\(XjT​Xj\)−1G\_\{ij\}=\(X\_\{i\}^\{T\}X\_\{i\}\)\(X\_\{j\}^\{T\}X\_\{j\}\)^\{\-1\}\(60\)andλt​\(⋅\)\\lambda\_\{t\}\(\\cdot\)be thett​ht\_\{th\}singular value of a matrix\. Then

Di​j\+Dj​i=tr​\[Gi​j\]\+tr​\[Gj​i\]=∑t=1dλt​\(Gi​j\)\+∑t=1dλt​\(Gj​i\)=∑t=1dλt​\(Gi​j\)\+∑t=1d1λt​\(Gi​j\)\.D\_\{ij\}\+D\_\{ji\}=\\mathrm\{tr\}\[G\_\{ij\}\]\+\\mathrm\{tr\}\[G\_\{ji\}\]=\\sum\_\{t=1\}^\{d\}\\lambda\_\{t\}\(G\_\{ij\}\)\+\\sum\_\{t=1\}^\{d\}\\lambda\_\{t\}\(G\_\{ji\}\)=\\sum\_\{t=1\}^\{d\}\\lambda\_\{t\}\(G\_\{ij\}\)\+\\sum\_\{t=1\}^\{d\}\\frac\{1\}\{\\lambda\_\{t\}\(G\_\{ij\}\)\}\.\(61\)where the last equality follows a simple fact thatGi​j=Gj​i−1G\_\{ij\}=G\_\{ji\}^\{\-1\}\. Further, since all singular values are positive,

λt​\(Gi​j\)\+1λt​\(Gi​j\)≥2​λt​\(Gi​j\)​1λt​\(Gi​j\)=2\.\\lambda\_\{t\}\(G\_\{ij\}\)\+\\frac\{1\}\{\\lambda\_\{t\}\(G\_\{ij\}\)\}\\geq 2\\sqrt\{\\lambda\_\{t\}\(G\_\{ij\}\)\\frac\{1\}\{\\lambda\_\{t\}\(G\_\{ij\}\)\}\}=2\.\(62\)This lower bound holds for everytt\. Plugging all lower bounds back to \([61](https://arxiv.org/html/2607.07888#A2.E61)\), we have

Di​j\+Dj​i=∑t=1dλt​\(Gi​j\)\+1λt​\(Gi​j\)≥∑t=1d2=2​d\.D\_\{ij\}\+D\_\{ji\}=\\sum\_\{t=1\}^\{d\}\\lambda\_\{t\}\(G\_\{ij\}\)\+\\frac\{1\}\{\\lambda\_\{t\}\(G\_\{ij\}\)\}\\geq\\sum\_\{t=1\}^\{d\}2=2d\.\(63\)Combining this with the casei=ji=j, we have

D=1k2​∑i,j=1kDi​j=1k2​∑i=1kDi​i\+1k2​∑i=1k∑j≠iDi​j≥1k2​k​d\+1k2​k​\(k−1\)2​2​d=dk\+dk​\(k−1\)=d\.\\begin\{split\}D=\\frac\{1\}\{k^\{2\}\}\\sum\_\{i,j=1\}^\{k\}D\_\{ij\}=\\frac\{1\}\{k^\{2\}\}\\sum\_\{i=1\}^\{k\}D\_\{ii\}\+\\frac\{1\}\{k^\{2\}\}\\sum\_\{i=1\}^\{k\}\\sum\_\{j\\neq i\}D\_\{ij\}\\geq\\frac\{1\}\{k^\{2\}\}kd\+\\frac\{1\}\{k^\{2\}\}\\frac\{k\(k\-1\)\}\{2\}2d=\\frac\{d\}\{k\}\+\\frac\{d\}\{k\}\(k\-1\)=d\.\\end\{split\}\(64\)To identify conditions for the equality, note the equality in \([62](https://arxiv.org/html/2607.07888#A2.E62)\) holds ifλt​\(Gi​j\)=1λt​\(Gi​j\)\\lambda\_\{t\}\(G\_\{ij\}\)=\\frac\{1\}\{\\lambda\_\{t\}\(G\_\{ij\}\)\}or, equivalently,λt​\(Gi​j\)=1\\lambda\_\{t\}\(G\_\{ij\}\)=1\. Then, it is not hard to see the equality in \([64](https://arxiv.org/html/2607.07888#A2.E64)\) holds whenλt​\(Gi​j\)=1\\lambda\_\{t\}\(G\_\{ij\}\)=1for allt,i,jt,i,j– a condition that is satisfied whenXiT​Xi=XjT​XjX\_\{i\}^\{T\}X\_\{i\}=X\_\{j\}^\{T\}X\_\{j\}for alli≠ji\\neq j\. This proves the lemma\. ∎

###### Claim B\.1\.

Ifxix\_\{i\}’s are sampled i\.i\.d\. fromN​\(0→,𝒱\)N\(\\vec\{0\},\\mathcal\{V\}\)with an invertible𝒱∈ℝd×d\\mathcal\{V\}\\in\\mathbb\{R\}^\{d\\times d\}, then𝔼X​\[D\]=n−\(d\+1\)n−k​\(d\+1\)​d\\mathbb\{E\}\_\{X\}\[D\]=\\frac\{n\-\(d\+1\)\}\{n\-k\(d\+1\)\}d\.

###### Proof\.

By assumptionXjT​XjX\_\{j\}^\{T\}X\_\{j\}is a Wishart matrix withppdegrees of freedom\. It is well\-known that𝔼X​\[XjT​Xj\]=p​𝒱\\mathbb\{E\}\_\{X\}\[X\_\{j\}^\{T\}X\_\{j\}\]=p\\mathcal\{V\}and𝔼X​\[\(XjT​Xj\)−1\]=𝒱−1p−d−1\\mathbb\{E\}\_\{X\}\[\(X\_\{j\}^\{T\}X\_\{j\}\)^\{\-1\}\]=\\frac\{\\mathcal\{V\}^\{\-1\}\}\{p\-d\-1\}\(petersen2008matrix, Theorems 7\.8\.1 and 7\.9\.1\)\. Then

𝔼X​\[D\]=𝔼​1k2​∑i,j=1ktr​\(XiT​Xi\)​\(XjT​Xj\)−1=𝔼​1k2​∑i=1ktr​\(XiT​Xi\)​\(XiT​Xi\)−1\+𝔼​1k2​∑i=1k∑j≠itr​\(XiT​Xi\)​\(XjT​Xj\)−1=𝔼​1k2​∑i=1ktr​\[Id\]\+1k2​∑i=1k∑j≠itr​\[𝔼Xi​\(XiT​Xi\)​𝔼Xj​\(XjT​Xj\)−1\]=dk\+1k2​∑i=1k∑j≠ipp−d−1​tr​\[Id\]=dk\+k−1k​p​dp−d−1=dk​\(1\+p​\(k−1\)p−d−1\)=n−d−1n−k​d−k​d\.\\begin\{split\}\\mathbb\{E\}\_\{X\}\[D\]&=\\mathbb\{E\}\\frac\{1\}\{k^\{2\}\}\\sum\_\{i,j=1\}^\{k\}\\mathrm\{tr\}\(X\_\{i\}^\{T\}X\_\{i\}\)\(X\_\{j\}^\{T\}X\_\{j\}\)^\{\-1\}\\\\ &=\\mathbb\{E\}\\frac\{1\}\{k^\{2\}\}\\sum\_\{i=1\}^\{k\}\\mathrm\{tr\}\(X\_\{i\}^\{T\}X\_\{i\}\)\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}\+\\mathbb\{E\}\\frac\{1\}\{k^\{2\}\}\\sum\_\{i=1\}^\{k\}\\sum\_\{j\\neq i\}\\mathrm\{tr\}\(X\_\{i\}^\{T\}X\_\{i\}\)\(X\_\{j\}^\{T\}X\_\{j\}\)^\{\-1\}\\\\ &=\\mathbb\{E\}\\frac\{1\}\{k^\{2\}\}\\sum\_\{i=1\}^\{k\}\\mathrm\{tr\}\[I\_\{d\}\]\+\\frac\{1\}\{k^\{2\}\}\\sum\_\{i=1\}^\{k\}\\sum\_\{j\\neq i\}\\mathrm\{tr\}\\left\[\\mathbb\{E\}\_\{X\_\{i\}\}\(X\_\{i\}^\{T\}X\_\{i\}\)\\ \\mathbb\{E\}\_\{X\_\{j\}\}\(X\_\{j\}^\{T\}X\_\{j\}\)^\{\-1\}\\right\]\\\\ &=\\frac\{d\}\{k\}\+\\frac\{1\}\{k^\{2\}\}\\sum\_\{i=1\}^\{k\}\\sum\_\{j\\neq i\}\\frac\{p\}\{p\-d\-1\}\\mathrm\{tr\}\[I\_\{d\}\]\\\\ &=\\frac\{d\}\{k\}\+\\frac\{k\-1\}\{k\}\\frac\{pd\}\{p\-d\-1\}\\\\ &=\\frac\{d\}\{k\}\\left\(1\+\\frac\{p\(k\-1\)\}\{p\-d\-1\}\\right\)\\\\ &=\\frac\{n\-d\-1\}\{n\-kd\-k\}d\.\\end\{split\}\(65\)Above, the third equality holds becauseXiX\_\{i\}andXjX\_\{j\}are independent wheneveri≠ji\\neq j, and the last followsp​k=npk=n\. ∎

###### Claim B\.2\.

∑i=1k\(d\+Δi\)=k2​D\\sum\_\{i=1\}^\{k\}\(d\+\\Delta\_\{i\}\)=k^\{2\}D\.

###### Proof\.

The key observation is that

d=tr​\[Id\]=tr​\[XiT​Xi​\(XiT​Xi\)−1\]\.d=\\mathrm\{tr\}\[I\_\{d\}\]=\\mathrm\{tr\}\[X\_\{i\}^\{T\}X\_\{i\}\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}\]\.\(66\)Thus,

d\+Δi=tr​\[XiT​Xi​\(XiT​Xi\)−1\]\+tr​\[∑j≠iXjT​Xj​\(XiT​Xi\)−1\]=tr​\[∑j=1kXjT​Xj​\(XiT​Xi\)−1\]\.d\+\\Delta\_\{i\}=\\mathrm\{tr\}\[X\_\{i\}^\{T\}X\_\{i\}\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}\]\+\\mathrm\{tr\}\[\{\\sum\}\_\{j\\neq i\}X\_\{j\}^\{T\}X\_\{j\}\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}\]=\\mathrm\{tr\}\[\{\\sum\}\_\{j=1\}^\{k\}X\_\{j\}^\{T\}X\_\{j\}\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}\]\.\(67\)Thus, by the design ofDD,

∑i=1k\(d\+Δi\)=∑i=1ktr​\[∑j=1kXjT​Xj​\(XiT​Xi\)−1\]=tr​\[∑i=1k∑j=1kXjT​Xj​\(XiT​Xi\)−1\]=k2​D\.\\sum\_\{i=1\}^\{k\}\(d\+\\Delta\_\{i\}\)=\\sum\_\{i=1\}^\{k\}\\mathrm\{tr\}\[\\sum\_\{j=1\}^\{k\}X\_\{j\}^\{T\}X\_\{j\}\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}\]=\\mathrm\{tr\}\[\\sum\_\{i=1\}^\{k\}\\sum\_\{j=1\}^\{k\}X\_\{j\}^\{T\}X\_\{j\}\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}\]=k^\{2\}D\.\(68\)∎

At last, we prove Remark[3\.5](https://arxiv.org/html/2607.07888#S3.Thmtheorem5)\. The proof invokes the following classical singular value bounds for random matrix\.

###### Theorem B\.3\(\(vershynin2012introduction\), Corollary 5\.35\)\.

LetZZbe anm×pm\\times pmatrix whose entries are independent standard normal random variables\. Then for everyt≥0t\\geq 0, with probability at least1−2​exp⁡\(−t2/2\)1\-2\\exp\(\-t^\{2\}/2\)one has

m−p−t≤σmin​\(Z\)≤σmax​\(Z\)≤m\+p\+t,\\sqrt\{m\}\-\\sqrt\{p\}\-t\\leq\\sigma\_\{\\min\}\(Z\)\\leq\\sigma\_\{\\max\}\(Z\)\\leq\\sqrt\{m\}\+\\sqrt\{p\}\+t,\(69\)whereσmax\\sigma\_\{\\max\}andσmin\\sigma\_\{\\min\}denote the maximum and minimum singular values, respectively\.

The following claim will be used to prove Remark\.

###### Proof\.

To prove the first claim, let

Xi=Ui​RiX\_\{i\}=U\_\{i\}R\_\{i\}\(70\)be a QR decomposition ofXiX\_\{i\}, whereUi∈ℝp×dU\_\{i\}\\in\\mathbb\{R\}^\{p\\times d\}has orthonormal columns andRi∈ℝd×dR\_\{i\}\\in\\mathbb\{R\}^\{d\\times d\}\.

Our main argument is thatSi​UiS\_\{i\}U\_\{i\}has i\.i\.d\. entries fromN​\(0,1/m\)N\(0,1/m\)\. To verify this, lets∈ℝ1×ps\\in\\mathbb\{R\}^\{1\\times p\}denote an arbitrary row ofSiS\_\{i\}\. First,s​UisU\_\{i\}is a vector whose entries are jointly Gaussian, because any linear combination of these entries can be expressed ass​Ui​csU\_\{i\}cfor some constantc∈ℝdc\\in\\mathbb\{R\}^\{d\}– this expression is a sum of \(scaled\) independent Gaussian entries ofssand thus itself a Gaussian\. Second, entries ofs​UisU\_\{i\}are uncorrelated because the mean is

𝔼​\[s​Ui\]=𝔼​\[s\]​Ui=0,\\mathbb\{E\}\[sU\_\{i\}\]=\\mathbb\{E\}\[s\]U\_\{i\}=0,\(71\)and thus the covariance matrix is

cov​\(s​Ui\)=𝔼​\(s​Ui−𝔼​\[s​Ui\]\)T​\(s​Ui−𝔼​\[s​Ui\]\)=𝔼​\(s​Ui\)T​\(s​Ui\)=UiT​𝔼​\[sT​s\]​Ui=1m​UiT​Ui=1m​Id,\\text\{cov\}\(sU\_\{i\}\)=\\mathbb\{E\}\(sU\_\{i\}\-\\mathbb\{E\}\[sU\_\{i\}\]\)^\{T\}\(sU\_\{i\}\-\\mathbb\{E\}\[sU\_\{i\}\]\)=\\mathbb\{E\}\(sU\_\{i\}\)^\{T\}\(sU\_\{i\}\)=U\_\{i\}^\{T\}\\mathbb\{E\}\[s^\{T\}s\]U\_\{i\}=\\frac\{1\}\{m\}U\_\{i\}^\{T\}U\_\{i\}=\\frac\{1\}\{m\}I\_\{d\},\(72\)where the last equality holds becauseUiU\_\{i\}has orthonormal columns\. In summary, the entries ofs​UisU\_\{i\}are jointly Gaussian and uncorrelated, which implies they are independent\.

For entries ofSi​UiS\_\{i\}U\_\{i\}that are generated by different rows ofSiS\_\{i\}, they are independent because the rows are independent\. In addition, it can be shown they separately followN​\(0,1/m\)N\(0,1/m\)by the same argument fors​UisU\_\{i\}\.

Now we knowSi​UiS\_\{i\}U\_\{i\}has i\.i\.d\. entries fromN​\(0,1/m\)N\(0,1/m\)\. The next step is to apply Theorem[B\.3](https://arxiv.org/html/2607.07888#A2.Thmtheorem3)to bound its singular value\. To be specific, with probability at least1−exp⁡\(−t2/2\)1\-\\exp\(\-t^\{2\}/2\)\(no factor 2 for only one side of the inequality\),

σmin​\(m​Si​Ui\)≥m−d−t\.\\sigma\_\{\\min\}\(\\sqrt\{m\}S\_\{i\}U\_\{i\}\)\\geq\\sqrt\{m\}\-\\sqrt\{d\}\-t\.\(73\)Dividing both sides bym\\sqrt\{m\}and settingexp⁡\(−t2/2\)=δ/\(2​k\)\\exp\(\-t^\{2\}/2\)=\\delta/\(2k\), we have with probability at least1−δ/\(2​k\)1\-\\delta/\(2k\),

σmin​\(Si​Ui\)≥1−dm−2​ln⁡\(2​k/δ\)m\.\\sigma\_\{\\min\}\(S\_\{i\}U\_\{i\}\)\\geq 1\-\\sqrt\{\\frac\{d\}\{m\}\}\-\\sqrt\{\\frac\{2\\ln\(2k/\\delta\)\}\{m\}\}\.\(74\)If the right side is positive i\.e\.,1−dm−2​ln⁡\(2​k/δ\)m\>01\-\\sqrt\{\\frac\{d\}\{m\}\}\-\\sqrt\{\\frac\{2\\ln\(2k/\\delta\)\}\{m\}\}\>0, then the above implies

\(Si​Ui\)T​\(Si​Ui\)⪰\(1−dm−2​ln⁡\(2​k/δ\)m\)2​Id,\(S\_\{i\}U\_\{i\}\)^\{T\}\(S\_\{i\}U\_\{i\}\)\\succeq\\left\(1\-\\sqrt\{\\frac\{d\}\{m\}\}\-\\sqrt\{\\frac\{2\\ln\(2k/\\delta\)\}\{m\}\}\\right\)^\{2\}I\_\{d\},\(75\)and thus

XiT​SiT​Si​Xi=RiT​UiT​SiT​Si​Ui​Ri⪰\(1−dm−2​ln⁡\(2​k/δ\)m\)2​RiT​Ri,X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}X\_\{i\}=R\_\{i\}^\{T\}U\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}U\_\{i\}R\_\{i\}\\succeq\\left\(1\-\\sqrt\{\\frac\{d\}\{m\}\}\-\\sqrt\{\\frac\{2\\ln\(2k/\\delta\)\}\{m\}\}\\right\)^\{2\}R\_\{i\}^\{T\}R\_\{i\},\(76\)and further

\(XiT​SiT​Si​Xi\)−1⪯\(1−dm−2​ln⁡\(2​k/δ\)m\)−2​\(RiT​Ri\)−1\.\(X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}X\_\{i\}\)^\{\-1\}\\preceq\\left\(1\-\\sqrt\{\\frac\{d\}\{m\}\}\-\\sqrt\{\\frac\{2\\ln\(2k/\\delta\)\}\{m\}\}\\right\)^\{\-2\}\(R\_\{i\}^\{T\}R\_\{i\}\)^\{\-1\}\.\(77\)Finally, plugging in the following equivalence proves the first claim:

XiT​Xi=RiT​UiT​Ui​Ri=RiT​Ri,X\_\{i\}^\{T\}X\_\{i\}=R\_\{i\}^\{T\}U\_\{i\}^\{T\}U\_\{i\}R\_\{i\}=R\_\{i\}^\{T\}R\_\{i\},\(78\)where the last equality holds becauseUiU\_\{i\}has orthonormal columns\. The condition of the first claim follows the above presumption that1−dm−2​ln⁡\(2​k/δ\)m\>01\-\\sqrt\{\\frac\{d\}\{m\}\}\-\\sqrt\{\\frac\{2\\ln\(2k/\\delta\)\}\{m\}\}\>0\.

The second claim directly follows Theorem[B\.3](https://arxiv.org/html/2607.07888#A2.Thmtheorem3), which states that with probability at least1−exp⁡\(−t2/2\)1\-\\exp\(\-t^\{2\}/2\),

σmax​\(m​Si\)≤m\+p\+t\.\\sigma\_\{\\max\}\(\\sqrt\{m\}S\_\{i\}\)\\leq\\sqrt\{m\}\+\\sqrt\{p\}\+t\.\(79\)Dividing both sides bym\\sqrt\{m\}and settingexp⁡\(−t2/2\)=δ/\(2​k\)\\exp\(\-t^\{2\}/2\)=\\delta/\(2k\), we have with probability at least1−δ/\(2​k\)1\-\\delta/\(2k\),

σmax​\(Si\)≤1\+pm\+2​ln⁡\(2​k/δ\)m\.\\sigma\_\{\\max\}\(S\_\{i\}\)\\leq 1\+\\sqrt\{\\frac\{p\}\{m\}\}\+\\sqrt\{\\frac\{2\\ln\(2k/\\delta\)\}\{m\}\}\.\(80\)Taking square on both sides and applying the fact that‖SiT​Si‖o​p=σmax2​\(Si\)\|\|S\_\{i\}^\{T\}S\_\{i\}\|\|\_\{op\}=\\sigma\_\{\\max\}^\{2\}\(S\_\{i\}\)proves the second claim\. ∎

###### Proof\.

Recall thatLo​\(α^\)=𝔼Y​‖X​α^−Y‖L\_\{o\}\(\\hat\{\\alpha\}\)=\\mathbb\{E\}\_\{Y\}\|\|X\\hat\{\\alpha\}\-Y\|\|is a measure of out\-of\-sample loss, whereYYandα^\\hat\{\\alpha\}are built from independent label noisesEYE\_\{Y\}andEα^E\_\{\\hat\{\\alpha\}\}respectively\. The proof is divided into two parts\. The first part evaluatesLo​\(θ¯\)L\_\{o\}\(\\bar\{\\theta\}\)and the second part evaluatesLo​\(α^∗\)L\_\{o\}\(\\hat\{\\alpha\}\_\{\*\}\)\.

Part I\. Evaluation ofLo​\(θ¯\)L\_\{o\}\(\\bar\{\\theta\}\)

LetEYE\_\{Y\}be the data noise ofYY, i\.e\.,Y=X​α\+EYY=X\\alpha\+E\_\{Y\}\. Then,

Lo​\(θ¯\)=𝔼Y​‖X​θ¯−Y‖2=𝔼EY​‖X​θ¯−X​α−EY‖2=‖X​θ¯−X​α‖2\+𝔼​‖EY‖2−2​𝔼​EYT​\(X​θ¯−X​α\)=‖X​θ¯−X​α‖2\+σ2​n\.\\begin\{split\}L\_\{o\}\(\\bar\{\\theta\}\)&=\\mathbb\{E\}\_\{Y\}\|\|X\\bar\{\\theta\}\-Y\|\|^\{2\}\\\\\[1\.00006pt\] &=\\mathbb\{E\}\_\{E\_\{Y\}\}\|\|X\\bar\{\\theta\}\-X\\alpha\-E\_\{Y\}\|\|^\{2\}\\\\\[1\.00006pt\] &=\|\|X\\bar\{\\theta\}\-X\\alpha\|\|^\{2\}\+\\mathbb\{E\}\|\|E\_\{Y\}\|\|^\{2\}\-2\\mathbb\{E\}E\_\{Y\}^\{T\}\(X\\bar\{\\theta\}\-X\\alpha\)\\\\\[1\.00006pt\] &=\|\|X\\bar\{\\theta\}\-X\\alpha\|\|^\{2\}\+\\sigma^\{2\}n\.\\end\{split\}\(82\)Further, letEθ¯:=\{E1,…,Ek\}E\_\{\\bar\{\\theta\}\}:=\\\{E\_\{1\},\\ldots,E\_\{k\}\\\}be the collection of data noises learned byθ¯\\bar\{\\theta\}, whereYi=Xi​α\+EiY\_\{i\}=X\_\{i\}\\alpha\+E\_\{i\}\. Then,

𝔼Eθ¯​‖X​θ¯−X​α‖2=𝔼​‖X​1k​∑i=1kθ^i−X​α‖2=1k2​𝔼​‖∑i=1kX​\(θ^i−α\)‖2=1k2​∑i=1k𝔼​‖X​\(θ^i−α\)‖2,\\mathbb\{E\}\_\{E\_\{\\bar\{\\theta\}\}\}\|\|X\\bar\{\\theta\}\-X\\alpha\|\|^\{2\}=\\mathbb\{E\}\|\|X\\frac\{1\}\{k\}\\sum\_\{i=1\}^\{k\}\\hat\{\\theta\}\_\{i\}\-X\\alpha\|\|^\{2\}=\\frac\{1\}\{k^\{2\}\}\\mathbb\{E\}\|\|\\sum\_\{i=1\}^\{k\}X\(\\hat\{\\theta\}\_\{i\}\-\\alpha\)\|\|^\{2\}=\\frac\{1\}\{k^\{2\}\}\\sum\_\{i=1\}^\{k\}\\mathbb\{E\}\|\|X\(\\hat\{\\theta\}\_\{i\}\-\\alpha\)\|\|^\{2\},\(83\)where the last equality holds because the expected sum of cross terms is zero; to be specific, since

θ^i=\(XiT​SiT​Si​Xi\)−1​XiT​SiT​Si​Yi=\(XiT​SiT​Si​Xi\)−1​XiT​SiT​Si​\(Xi​α\+Ei\)=α\+\(XiT​SiT​Si​Xi\)−1​XiT​SiT​Si​Ei,\\hat\{\\theta\}\_\{i\}=\(X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}X\_\{i\}\)^\{\-1\}X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}Y\_\{i\}=\(X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}X\_\{i\}\)^\{\-1\}X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}\(X\_\{i\}\\alpha\+E\_\{i\}\)=\\alpha\+\(X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}X\_\{i\}\)^\{\-1\}X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}E\_\{i\},\(84\)we have

𝔼Eθ¯​\[θ^i\]=𝔼Ei​\[θ^i\]=α,\\mathbb\{E\}\_\{E\_\{\\bar\{\\theta\}\}\}\[\\hat\{\\theta\}\_\{i\}\]=\\mathbb\{E\}\_\{E\_\{i\}\}\[\\hat\{\\theta\}\_\{i\}\]=\\alpha,\(85\)and thus

𝔼Eθ¯​∑i=1k∑j≠i\(θ^i−α\)T​XT​X​\(θ^j−α\)=∑i=1k∑j≠i𝔼Ei​\(θ^i−α\)T​XT​X​𝔼Ej​\(θ^j−α\)=0\.\\mathbb\{E\}\_\{E\_\{\\bar\{\\theta\}\}\}\\sum\_\{i=1\}^\{k\}\\sum\_\{j\\neq i\}\(\\hat\{\\theta\}\_\{i\}\-\\alpha\)^\{T\}X^\{T\}X\(\\hat\{\\theta\}\_\{j\}\-\\alpha\)=\\sum\_\{i=1\}^\{k\}\\sum\_\{j\\neq i\}\\mathbb\{E\}\_\{E\_\{i\}\}\(\\hat\{\\theta\}\_\{i\}\-\\alpha\)^\{T\}X^\{T\}X\\mathbb\{E\}\_\{E\_\{j\}\}\(\\hat\{\\theta\}\_\{j\}\-\\alpha\)=0\.\(86\)Next, formula \([84](https://arxiv.org/html/2607.07888#A2.E84)\) also implies

θ^i−α=\(XiT​SiT​Si​Xi\)−1​XiT​SiT​Si​Ei\.\\hat\{\\theta\}\_\{i\}\-\\alpha=\(X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}X\_\{i\}\)^\{\-1\}X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}E\_\{i\}\.\(87\)Plugging it into the right side of \([83](https://arxiv.org/html/2607.07888#A2.E83)\), we have

1k2​∑i=1k𝔼Eθ¯​‖X​\(θ^i−α\)‖2=1k2​∑i=1k𝔼​tr​\[XT​X​\(θ^i−α\)​\(θ^i−α\)T\]=1k2​∑i=1ktr​\[XT​X​𝔼​\(θ^i−α\)​\(θ^i−α\)T\]=1k2​∑i=1ktr​\[XT​X​𝔼​\(XiT​SiT​Si​Xi\)−1​XiT​SiT​Si​Ei​EiT​SiT​Si​Xi​\(XiT​SiT​Si​Xi\)−1\]=1k2​∑i=1ktr​\[XT​X​\(XiT​SiT​Si​Xi\)−1​XiT​SiT​Si​𝔼​\(Ei​EiT\)​SiT​Si​Xi​\(XiT​SiT​Si​Xi\)−1\]=σ2k2​∑i=1ktr​\[XT​X​\(XiT​SiT​Si​Xi\)−1​XiT​SiT​Si​SiT​Si​Xi​\(XiT​SiT​Si​Xi\)−1\]≤σ2k2​∑i=1k‖Si​SiT‖o​p⋅tr​\[XT​X​\(XiT​SiT​Si​Xi\)−1​XiT​SiT​Si​Xi​\(XiT​SiT​Si​Xi\)−1\]=σ2k2​∑i=1k‖Si​SiT‖o​p⋅tr​\[XT​X​\(XiT​SiT​Si​Xi\)−1\]\.\\begin\{split\}\\frac\{1\}\{k^\{2\}\}\\sum\_\{i=1\}^\{k\}\\mathbb\{E\}\_\{E\_\{\\bar\{\\theta\}\}\}\|\|X\(\\hat\{\\theta\}\_\{i\}\-\\alpha\)\|\|^\{2\}&=\\frac\{1\}\{k^\{2\}\}\\sum\_\{i=1\}^\{k\}\\mathbb\{E\}\\ \\text\{tr\}\[X^\{T\}X\(\\hat\{\\theta\}\_\{i\}\-\\alpha\)\(\\hat\{\\theta\}\_\{i\}\-\\alpha\)^\{T\}\]\\\\ &=\\frac\{1\}\{k^\{2\}\}\\sum\_\{i=1\}^\{k\}\\text\{tr\}\[X^\{T\}X\\mathbb\{E\}\(\\hat\{\\theta\}\_\{i\}\-\\alpha\)\(\\hat\{\\theta\}\_\{i\}\-\\alpha\)^\{T\}\]\\\\ &=\\frac\{1\}\{k^\{2\}\}\\sum\_\{i=1\}^\{k\}\\text\{tr\}\[X^\{T\}X\\mathbb\{E\}\(X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}X\_\{i\}\)^\{\-1\}X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}E\_\{i\}E\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}X\_\{i\}\(X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}X\_\{i\}\)^\{\-1\}\]\\\\ &=\\frac\{1\}\{k^\{2\}\}\\sum\_\{i=1\}^\{k\}\\text\{tr\}\[X^\{T\}X\(X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}X\_\{i\}\)^\{\-1\}X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}\\mathbb\{E\}\(E\_\{i\}E\_\{i\}^\{T\}\)S\_\{i\}^\{T\}S\_\{i\}X\_\{i\}\(X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}X\_\{i\}\)^\{\-1\}\]\\\\ &=\\frac\{\\sigma^\{2\}\}\{k^\{2\}\}\\sum\_\{i=1\}^\{k\}\\text\{tr\}\[X^\{T\}X\(X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}X\_\{i\}\)^\{\-1\}X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}S\_\{i\}^\{T\}S\_\{i\}X\_\{i\}\(X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}X\_\{i\}\)^\{\-1\}\]\\\\ &\\leq\\frac\{\\sigma^\{2\}\}\{k^\{2\}\}\\sum\_\{i=1\}^\{k\}\|\|S\_\{i\}S\_\{i\}^\{T\}\|\|\_\{op\}\\cdot\\text\{tr\}\[X^\{T\}X\(X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}X\_\{i\}\)^\{\-1\}X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}X\_\{i\}\(X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}X\_\{i\}\)^\{\-1\}\]\\\\ &=\\frac\{\\sigma^\{2\}\}\{k^\{2\}\}\\sum\_\{i=1\}^\{k\}\|\|S\_\{i\}S\_\{i\}^\{T\}\|\|\_\{op\}\\cdot\\text\{tr\}\[X^\{T\}X\(X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}X\_\{i\}\)^\{\-1\}\]\.\\end\{split\}\(88\)Above, the inequality follows the fact thatAT​M​A⪯‖M‖o​p​AT​AA^\{T\}MA\\preceq\|\|M\|\|\_\{op\}A^\{T\}Afor any symmetric positive semidefinite matrixMMand properly sized matrixAA\.

To proceed, apply Remark[B\.4](https://arxiv.org/html/2607.07888#A2.Thmtheorem4)to bound every‖Si​SiT‖o​p\|\|S\_\{i\}S\_\{i\}^\{T\}\|\|\_\{op\}and\(XiT​SiT​Si​Xi\)−1\(X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}X\_\{i\}\)^\{\-1\}in the above sum\. Recall the original theorem bounds each term with probability at least1−δ/2​k1\-\\delta/2k\. Then, by a union bound, form≥\(d\+2​ln⁡\(2​k/δ\)\)2m\\geq\(\\sqrt\{d\}\+\\sqrt\{2\\ln\(2k/\\delta\)\}\)^\{2\}, with probability at least1−δ1\-\\delta,

σ2k2​∑i=1k‖Si​SiT‖o​p⋅tr​\[XT​X​\(XiT​SiT​Si​Xi\)−1\]≤σ2k2​∑i=1k\(1\+p/m\+2​log⁡\(2​k/δ\)/m\)2\(1−d/m−2​log⁡\(2​k/δ\)/m\)2​tr​\[\(XT​X\)​\(XiT​Xi\)−1\]=Γ​\(p,m,k,δ\)⋅σ2k2​∑i=1ktr​\[\(XT​X\)​\(XiT​Xi\)−1\]=Γ​\(p,m,k,δ\)⋅σ2​D\.\\begin\{split\}\\frac\{\\sigma^\{2\}\}\{k^\{2\}\}\\sum\_\{i=1\}^\{k\}\|\|S\_\{i\}S\_\{i\}^\{T\}\|\|\_\{op\}\\cdot\\text\{tr\}\[X^\{T\}X\(X\_\{i\}^\{T\}S\_\{i\}^\{T\}S\_\{i\}X\_\{i\}\)^\{\-1\}\]&\\leq\\frac\{\\sigma^\{2\}\}\{k^\{2\}\}\\sum\_\{i=1\}^\{k\}\\frac\{\\left\(1\+\\sqrt\{p/m\}\+\\sqrt\{2\\log\(2k/\\delta\)/m\}\\right\)^\{2\}\}\{\\left\(1\-\\sqrt\{d/m\}\-\\sqrt\{2\\log\(2k/\\delta\)/m\}\\right\)^\{2\}\}\\text\{tr\}\[\(X^\{T\}X\)\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}\]\\\\ &=\\Gamma\(p,m,k,\\delta\)\\cdot\\frac\{\\sigma^\{2\}\}\{k^\{2\}\}\\sum\_\{i=1\}^\{k\}\\text\{tr\}\[\(X^\{T\}X\)\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}\]\\\\ &=\\Gamma\(p,m,k,\\delta\)\\cdot\\sigma^\{2\}D\.\\end\{split\}\(89\)Above,Γ​\(p,m,k,δ\)=\(1\+p/m\+2​log⁡\(2​k/δ\)/m\)2\(1−d/m−2​log⁡\(2​k/δ\)/m\)2\\Gamma\(p,m,k,\\delta\)=\\frac\{\\left\(1\+\\sqrt\{p/m\}\+\\sqrt\{2\\log\(2k/\\delta\)/m\}\\right\)^\{2\}\}\{\\left\(1\-\\sqrt\{d/m\}\-\\sqrt\{2\\log\(2k/\\delta\)/m\}\\right\)^\{2\}\}and the last equality holds because

∑i=1ktr​\[\(XT​X\)​\(XiT​Xi\)−1\]=tr​\[\(XT​X\)​∑i=1k\(XiT​Xi\)−1\]=tr​\[∑j=1k\(XjT​Xj\)​∑i=1k\(XiT​Xi\)−1\]=tr​\[∑i,j=1k\(XjT​Xj\)​\(XiT​Xi\)−1\]=k2​D\.\\begin\{split\}\\sum\_\{i=1\}^\{k\}\\text\{tr\}\[\(X^\{T\}X\)\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}\]=\\text\{tr\}\[\(X^\{T\}X\)\\sum\_\{i=1\}^\{k\}\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}\]&=\\text\{tr\}\[\\sum\_\{j=1\}^\{k\}\(X\_\{j\}^\{T\}X\_\{j\}\)\\sum\_\{i=1\}^\{k\}\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}\]\\\\ &=\\text\{tr\}\[\\sum\_\{i,j=1\}^\{k\}\(X\_\{j\}^\{T\}X\_\{j\}\)\(X\_\{i\}^\{T\}X\_\{i\}\)^\{\-1\}\]\\\\ &=k^\{2\}D\.\\end\{split\}\(90\)
Plugging \([89](https://arxiv.org/html/2607.07888#A2.E89)\) back to \([88](https://arxiv.org/html/2607.07888#A2.E88)\) then \([83](https://arxiv.org/html/2607.07888#A2.E83)\), we have

𝔼Eθ¯​‖X​θ¯−X​α‖2≤Γ​\(p,m,k,δ\)⋅σ2​D\.\\mathbb\{E\}\_\{E\_\{\\bar\{\\theta\}\}\}\|\|X\\bar\{\\theta\}\-X\\alpha\|\|^\{2\}\\leq\\Gamma\(p,m,k,\\delta\)\\cdot\\sigma^\{2\}D\.\(91\)Combining this with \([82](https://arxiv.org/html/2607.07888#A2.E82)\) yields

𝔼θ¯​\[Lo​\(θ¯\)\]≤Γ​\(p,m,k,δ\)⋅σ2​D\+σ2​n\.\\mathbb\{E\}\_\{\\bar\{\\theta\}\}\[L\_\{o\}\(\\bar\{\\theta\}\)\]\\leq\\Gamma\(p,m,k,\\delta\)\\cdot\\sigma^\{2\}D\+\\sigma^\{2\}n\.\(92\)
Part II\. Evaluation ofLo​\(α^∗\)L\_\{o\}\(\\hat\{\\alpha\}\_\{\*\}\)

Evaluation ofLo​\(α^∗\)L\_\{o\}\(\\hat\{\\alpha\}\_\{\*\}\)is similar to that ofLo​\(θ¯\)L\_\{o\}\(\\bar\{\\theta\}\)\. First,

Lo​\(α^∗\)=𝔼Y​‖X​α^∗−Y‖2=‖X​α^∗−X​α‖2\+σ2​n\.L\_\{o\}\(\\hat\{\\alpha\}\_\{\*\}\)=\\mathbb\{E\}\_\{Y\}\|\|X\\hat\{\\alpha\}\_\{\*\}\-Y\|\|^\{2\}=\|\|X\\hat\{\\alpha\}\_\{\*\}\-X\\alpha\|\|^\{2\}\+\\sigma^\{2\}n\.\(93\)Then, letEα^∗E\_\{\\hat\{\\alpha\}\_\{\*\}\}be the data noise learned byα^∗\\hat\{\\alpha\}\_\{\*\}\. We have

𝔼Eα^∗​\[Lo​\(α^∗\)\]=𝔼Eα^∗​‖X​α^∗−X​α‖2\+σ2​n\.\\mathbb\{E\}\_\{E\_\{\\hat\{\\alpha\}\_\{\*\}\}\}\[L\_\{o\}\(\\hat\{\\alpha\}\_\{\*\}\)\]=\\mathbb\{E\}\_\{E\_\{\\hat\{\\alpha\}\_\{\*\}\}\}\|\|X\\hat\{\\alpha\}\_\{\*\}\-X\\alpha\|\|^\{2\}\+\\sigma^\{2\}n\.\(94\)Further, since

α^∗=\(XT​X\)−1​XT​Y=\(XT​X\)−1​XT​\(X​α\+Eα^∗\)=α\+\(XT​X\)−1​XT​Eα^∗\\hat\{\\alpha\}\_\{\*\}=\(X^\{T\}X\)^\{\-1\}X^\{T\}Y=\(X^\{T\}X\)^\{\-1\}X^\{T\}\(X\\alpha\+E\_\{\\hat\{\\alpha\}\_\{\*\}\}\)=\\alpha\+\(X^\{T\}X\)^\{\-1\}X^\{T\}E\_\{\\hat\{\\alpha\}\_\{\*\}\}\(95\)we have

𝔼Eα^∗​‖X​α^∗−X​α‖2=𝔼​tr​\[X​\(XT​X\)−1​XT​Eα^∗​Eα^∗T​X​\(XT​X\)−1​XT\]=tr​\[X​\(XT​X\)−1​XT​𝔼​\(Eα^∗​Eα^∗T\)​X​\(XT​X\)−1​XT\]=σ2​tr​\[X​\(XT​X\)−1​XT​X​\(XT​X\)−1​XT\]=σ2​tr​\[Id\]=σ2​d\.\\begin\{split\}\\mathbb\{E\}\_\{E\_\{\\hat\{\\alpha\}\_\{\*\}\}\}\|\|X\\hat\{\\alpha\}\_\{\*\}\-X\\alpha\|\|^\{2\}&=\\mathbb\{E\}\\text\{tr\}\[X\(X^\{T\}X\)^\{\-1\}X^\{T\}E\_\{\\hat\{\\alpha\}\_\{\*\}\}E\_\{\\hat\{\\alpha\}\_\{\*\}\}^\{T\}X\(X^\{T\}X\)^\{\-1\}X^\{T\}\]\\\\\[1\.00006pt\] &=\\text\{tr\}\[X\(X^\{T\}X\)^\{\-1\}X^\{T\}\\mathbb\{E\}\(E\_\{\\hat\{\\alpha\}\_\{\*\}\}E\_\{\\hat\{\\alpha\}\_\{\*\}\}^\{T\}\)X\(X^\{T\}X\)^\{\-1\}X^\{T\}\]\\\\\[1\.00006pt\] &=\\sigma^\{2\}\\text\{tr\}\[X\(X^\{T\}X\)^\{\-1\}X^\{T\}X\(X^\{T\}X\)^\{\-1\}X^\{T\}\]\\\\\[1\.00006pt\] &=\\sigma^\{2\}\\text\{tr\}\[I\_\{d\}\]\\\\\[1\.00006pt\] &=\\sigma^\{2\}d\.\\end\{split\}\(96\)Plugging this back to \([94](https://arxiv.org/html/2607.07888#A2.E94)\), we have

𝔼Eα^∗​\[Lo​\(α^∗\)\]=σ2​d\+σ2​n\.\\mathbb\{E\}\_\{E\_\{\\hat\{\\alpha\}\_\{\*\}\}\}\[L\_\{o\}\(\\hat\{\\alpha\}\_\{\*\}\)\]=\\sigma^\{2\}d\+\\sigma^\{2\}n\.\(97\)
Part III\. Summary

Combining \([92](https://arxiv.org/html/2607.07888#A2.E92)\) and \([97](https://arxiv.org/html/2607.07888#A2.E97)\) yields that, form≥\(d\+2​ln⁡\(2​k/δ\)\)2m\\geq\(\\sqrt\{d\}\+\\sqrt\{2\\ln\(2k/\\delta\)\}\)^\{2\}, with probability at least1−δ1\-\\delta,

𝔼θ¯​\[Lo​\(θ¯\)\]−𝔼Eα^∗​\[Lo​\(α^∗\)\]≤Γ​\(p,m,k,δ\)⋅D​σ2−d​σ2,\\mathbb\{E\}\_\{\\bar\{\\theta\}\}\[L\_\{o\}\(\\bar\{\\theta\}\)\]\-\\mathbb\{E\}\_\{E\_\{\\hat\{\\alpha\}\_\{\*\}\}\}\[L\_\{o\}\(\\hat\{\\alpha\}\_\{\*\}\)\]\\leq\\Gamma\(p,m,k,\\delta\)\\cdot D\\sigma^\{2\}\-d\\sigma^\{2\},\(98\)whereΓ​\(p,m,k,δ\)=\(m\+p\+2​log⁡\(2​k/δ\)\)2​\(m−d−2​log⁡\(2​k/δ\)\)−2\\Gamma\(p,m,k,\\delta\)=\\left\(\\sqrt\{m\}\+\\sqrt\{p\}\+\\sqrt\{2\\log\(2k/\\delta\)\}\\right\)^\{2\}\\left\(\\sqrt\{m\}\-\\sqrt\{d\}\-\\sqrt\{2\\log\(2k/\\delta\)\}\\right\)^\{\-2\}\. This proves the remark\. ∎

## Appendix C: Additional Numerical Results

We report two additional observations here\. First, a popular way to speed up Gaussian sketching is to apply faster sketching methods like Subsampled Randomized Hadamard Transform \(SRHT\)\. However, SRHT is not always faster, for its time complexity isO​\(n​d​log⁡n\)O\(nd\\log n\)which is more efficient only whenm≪nm\\ll n\. This is confirmed by the results in Figure[3](https://arxiv.org/html/2607.07888#Ax1.F3), wherennis reduced by random downsampling\. The time of SRHT is obtained by using it to replace Gaussian when buildingβ^i\\hat\{\\beta\}\_\{i\}, and we see SRHT is only faster whennnis small\. In all cases,θ^i\\hat\{\\theta\}\_\{i\}remains the most efficient method askkincreases\. Another observation from the experiment is that someXiT​XiX\_\{i\}^\{T\}X\_\{i\}matrices are not invertible \(e\.g\., due to sparsity\), which is a limitation of the present characterization\. How to overcome this limitation, such as through regularization, is an interesting direction for future research\.

![Refer to caption](https://arxiv.org/html/2607.07888v1/Figure/time_SRHT_1.png)

![Refer to caption](https://arxiv.org/html/2607.07888v1/Figure/time_SRHT_3.png)

![Refer to caption](https://arxiv.org/html/2607.07888v1/Figure/time_SRHT_4.png)

Figure 3:Training Time per estimator versuskkon Digit, withn=1024n=1024\(left\),n=256n=256\(mid\) andn=128n=128\(right\)\.