# Universality in block dependent linear models with applications to
nonparametric regression

Samriddha Lahiry  Department of Statistics, Harvard University
<EMAIL_ADDRESS>Pragya Sur  Department of Statistics, Harvard
University<EMAIL_ADDRESS>
###### Abstract

Over the past decade, characterizing the exact asymptotic risk of regularized
estimators in high-dimensional regression has emerged as a popular line of
work. This literature considers the proportional asymptotics framework, where
the number of features and samples both diverge, at a rate proportional to
each other. Substantial work in this area relies on Gaussianity assumptions on
the observed covariates. Further, these studies often assume the design
entries to be independent and identically distributed. Parallel research
investigates the universality of these findings, revealing that results based
on the i.i.d. Gaussian assumption extend to a broad class of designs, such as
i.i.d. sub-Gaussians. However, universality results examining dependent
covariates so far focused on correlation-based dependence or a highly
structured form of dependence, as permitted by right rotationally invariant
designs. In this paper, we break this barrier and study a dependence structure
that in general falls outside the purview of these established classes. We
seek to pin down the extent to which results based on i.i.d. Gaussian
assumptions persist. We identify a class of designs characterized by a block
dependence structure that ensures the universality of i.i.d. Gaussian-based
results. We establish that the optimal values of the regularized empirical
risk and the risk associated with convex regularized estimators, such as the
Lasso and ridge, converge to the same limit under block dependent designs as
they do for i.i.d. Gaussian entry designs. Our dependence structure differs
significantly from correlation-based dependence, and enables, for the first
time, asymptotically exact risk characterization in prevalent nonparametric
regression problems in high dimensions. Finally, we illustrate through
experiments that this universality becomes evident quite early, even for
relatively moderate sample sizes.

##  1 Introduction

Over the past decade, a novel regime to exploring high-dimensional asymptotics
has emerged in supervised learning. This paradigm posits that the number of
features ($p$) and the number of samples ($n$) both diverge with the ratio
$p/n$ converging to a positive constant. For natural reasons, this paradigm is
referred to as the proportional asymptotics regime. Numerous parallel
techniques have emerged to address statistical and probabilistic questions
within this framework, including random matrix theory [MP67], approximate
message passing theory [DMM09, BM11, BM12, Ran11, JM13, ZK16, DM16, SC19,
BKM+19, WWM20, MV21, FVRS22, LFW23], the leave-one-out/cavity method [MPV87,
Tal03, MM09, KBB+13, BBKY13, EK18, ZK16, SCC19, SC19, CCFM21], convex Gaussian
min-max theorem [Sto13a, Sto13b, Sto13c, OTH13, TOH15, TAH18], etc. The
widespread adoption of this paradigm in statistical research can, in part, be
attributed to its precise asymptotic results, which showcase exceptional
performance when tested on finite samples (cf. [CS20, SC19, SCC19, ZSC22,
SC18, ZK16, FVRS22, MS22b, LS22, JMSS22] and references cited therein).
Moreover, this paradigm liberates researchers from stringent sparsity
assumptions on underlying signals, accommodating structured classes of both
dense and sparse signals.

However, a limitation arises within this paradigm—conventional tools often
assume Gaussianity in the distribution of observed covariates. Extensive prior
literature [Cha06, ESY09, TV14, Erd11, BLM15, MN17, CL21, HL22, LS22, PH17,
GKL+22, DSL23, WZF22, HS23, MS22a, MRSS23, HX23] suggests that this assumption
is hardly a conceptual constraint. The results derived under this paradigm are
often insensitive to the specific form of the covariate distribution, and rely
more on the distribution’s tails or on quantities such as the spectrum of the
sample covariance matrix. In particular, prior work demonstrates the seamless
extension of results derived under i.i.d. Gaussian designs to i.i.d. sub-
Gaussian designs with suitable moments. Nevertheless, universality results
under dependent design entries are relatively scarce. This paper addresses
this challenge, revealing that under an appropriate notion of block
dependence, universality results persist.

Our universality result substantially broadens the scope of statistical models
considered within the proportional asymptotics regime. While the extension of
universality beyond the independent model is intrinsically fascinating, we
demonstrate that our results apply to widely used statistical models that had
thus far remained outside the purview of this literature. Specifically, we
leverage our universality result to provide precise risk characterization of
estimators arising in nonparametric regression in the presence of high-
dimensional covariates (Section 2). To the best of our knowledge, this class
of problems had so far remained uncharted. Our result relies on a block
dependence structure and we exhibit three popular examples where such
dependence emerges naturally. The first example pertains to the additive
model, well-studied in statistics, and applied in diverse fields such as
biomedical research [MTM22, HRM22], agronomy [MMD+21], environmental science
[RRMA19] etc. The second example, scalar- on-functional regression, arises
from the expansive field of functional data analysis, motivated by
longitudinal data, growth curves, time series, and more [Mor15]. The third and
final example is from genomics, particularly linkage-disequilibrium models
[Lew88], where block dependence structures arise naturally.

To introduce our setup formally, let $(Y_{i},X_{i})_{i=1}^{n}$ be i.i.d.
random variables with $Y_{i}\in\mathbb{R}$ and $X_{i}\in\mathbb{R}^{p}$. We
assume that $Y_{i}$ is a function of $X_{i}$ corrupted by an additive noise
i.e.

$Y_{i}=g^{*}(X_{i})+\epsilon_{i}$

with the most popular choice of $g^{*}$ being the linear model where one
assumes $g^{*}(X_{i})=X_{i}^{T}\beta^{*}$. In the next section, we will see
that many nonparametric models can be reduced to linear models by choosing a
suitable basis, and doing so induces interesting block dependent structures.
To capture such nonparametric regression models, it suffices to focus on
linear models with appropriate dependencies among covariates. This would be
the main focus of our paper.

We consider a penalized empirical risk minimization problem of the form
$\min_{\beta}\hat{R}_{n}(Y,\mathcal{X},\beta)$ where

$\hat{R}_{n}(Y,\mathcal{X},\beta)=\frac{1}{2n}\sum_{i=1}^{n}\|Y_{i}-\mathcal{X}^{T}_{i}\beta\|^{2}+\lambda
f(\beta).$ (1.1)

Here $\mathcal{X}=(\mathcal{X}_{1},\ldots,\mathcal{X}_{n})^{T}$,
$Y=(Y_{1},\ldots,Y_{n})^{T}$, $X_{i}\in\mathbb{R}^{p},\beta\in\mathbb{R}^{p}$
and $f$ is a convex penalty function.

We denote the minimum and the minimizer of the empirical risk by

$\hat{R}_{n}(Y,\mathcal{X})=\min_{\beta\in\mathbb{R}^{p}}\hat{R}_{n}(Y,\mathcal{X},\beta),\quad\text{
and
}\hat{\beta}_{\mathcal{X}}\in\operatornamewithlimits{arg\,min}_{\beta\in\mathbb{R}^{p}}\hat{R}_{n}(Y,\mathcal{X},\beta)$
(1.2)

respectively. For the rest of this paper we will assume that the covariates
are centred i.e. $E[\mathcal{X}_{i}]=0$.

Regularized estimators have been a subject of intense study over the decades.
Extensive prior work characterizes the risk of such estimators in the
proportional asymptotics regime when the covariates are drawn from a Gaussian
distribution. To extend to non-Gaussian settings, the typical strategy
involves proving universality results that answer the following question: can
rows of the data matrix $\mathcal{X}_{i}^{T}$ be replaced by Gaussian vectors
with matching moments and yield the same asymptotic results?

Among existing universality results, [KM11] established that when the design
matrix has i.i.d. entries and finite sixth moment, the optimal value of the
risk of a box constrained Lasso is the same as the optimal value when the
entries are i.i.d. Gaussian. Subsequently, [MN17] showed an analogous result
in the context of elastic net. See also [HS23] for a comprehensive set of
universality results that hold when the design entries are i.i.d. Despite this
stylized setting, results based on i.i.d. Gaussian designs capture many new
high-dimensional phenomena accurately in a qualitative sense. Further, this
assumption allows one to characterize precise limits of objects of statistical
relevance, such as risks of estimators [BM12, KBB+13, BBKY13, EK18, DM16,
SC19], behaviour of finite-dimensional marginals [SC19, SCC19], and prediction
error of machine learning algorithms [MRSY19, DKT22, LS22, LSS23], as well as
prove $\sqrt{n}$-consistency of estimators for average treatment effects
[JMSS22]. In light of the elegant theory and novel high-dimensional phenomena
this allows to capture, it is imperative to understand the limits of these
results. In this paper, we seek to understand the extent to which results
based on i.i.d. Gaussian designs continue to hold in presence of dependence
among the covariates.

In the context of dependent covariates, [MS22a] established that when rows of
the design are of the form $\mathcal{X}_{i}=\Sigma^{1/2}Z_{i}$ with entries of
$Z_{i}$ i.i.d. subGaussian, the optimal value of the risk matches that of the
design whose rows are of the form $\Sigma^{1/2}G_{i}$, where $G_{i}$ has
i.i.d. Gaussian entries. However, in a broad class of problems, the dependence
structure among covariates may not be in the precise form $\Sigma^{1/2}Z_{i}$
with $Z_{i}$ containing i.i.d. entries. On the other hand, [DLS23, DSL23,
WZF22] studied universality under curated forms of dependence, as allowed by
right rotationally invariant designs, that are critical in compressed sensing
applications [DT09, MJG+13, ABKZ20]. See [LS23] for detailed discussion and
examples on the nature of dependent problems this class can handle. These
forms of dependence studied in prior work fails to capture general sub-
Gaussian designs that may arise naturally in important statistical models—this
is the main focus of our paper.

In our conquest to understand dependent covariates, we recognize that "too
much" dependence among entries of $\mathcal{X}_{i}$ may break universality, as
demonstrated in [EK18, HS23]. In the latter, the authors show that for
isotropic designs, if each entry in a row of the design depends on every other
entry, the estimation risk is asymptotically different from the model with
i.i.d. Gaussian covariates. However, noteworthy examples of dependence exist
where each entry of the design depends on a subset of the entire row (cf.
Section 2). A natural question then arises: do universality results hold under
such dependence structures? We answer in the affirmative, identifying a class
of dependence structures that ensure universality results continue to hold. In
particular, we show the following

Let $\mathcal{X}$ be a design matrix with i.i.d. mean zero rows. Further
assume that each row $\mathcal{X}_{i}$ is “block dependent” and subGaussian.
Let $\mathcal{G}$ be a design matrix with i.i.d. rows distributed as a
multivariate Gaussian $\mathcal{N}(0,\Lambda)$ for a diagonal matrix
$\Lambda$. If $E(\mathcal{X}_{i}\mathcal{X}^{T}_{i})=\Lambda$ then we have

$\min_{\beta}\hat{R}_{n}(Y,\mathcal{X},\beta)\approx\min_{\beta}\hat{R}_{n}(Y,\mathcal{\mathcal{G}},\beta)\quad\text{and}\quad\|\hat{\beta}_{\mathcal{X}}-\beta_{0}\|^{2}\approx\|\hat{\beta}_{\mathcal{G}}-\beta_{0}\|^{2}.$

This simple mathematical result opens the avenue for exact risk
characterization of regularized estimators in high-dimensional models that had
so far evaded the literature (see Section 2 for concrete examples). We define
the notion of block dependence formally in Section 2. To the best of our
knowledge, our result is the first in the literature on universality in high-
dimensional regression that goes beyond correlation-based dependence or right
rotationally invariant designs. We provide a more detailed literature review
in Section 6. For simplicity, we focus on two of the most commonly used
penalty functions—the $\ell_{1}$ (Lasso) or the $\ell^{2}_{2}$ (ridge). These
differ drastically in the geometry they induce in high dimensions. In this
light, we believe that most other popular examples of separable penalties can
be handled by extending our current proof techniques.

###  1.1 Outline of the results

To illustrate the importance of considering block dependent designs, we
present various examples in Section 2. The initial example revolves around the
commonly used additive model, where we demonstrate that by considering block
dependent settings, one can extend results from parametric models to
nonparametric models. Additionally, we explore an example of scalar-on-
function regression where such dependence may emerge. The third example delves
into a genomics model where block dependent designs naturally come into play.
Section 3 presents preliminaries and Section 4 presents our main results. In
Section 5, we present simulations corroborating our theory while Section 6
reviews literature related to our work. Section 7 provides the proof of the
main theorems and corollaries. Finally, we conclude in Section 8 with a
discussion on possible generalizations of our results, while the proofs of the
auxiliary lemmas are given in the Appendix.

###  1.2 Notations

We use the $O(.)$ and $o(.)$ to denote asymptotically bounded and
asymptotically goes to $0$ respectively i.e we say $a_{n}=O(\gamma_{n})$ if
$\limsup|a_{n}/\gamma_{n}|\leq C$ and $a_{n}=o(\gamma_{n})$ if
$\limsup|a_{n}/\gamma_{n}|=0$. Similarly $O_{p}(.)$ and $o_{p}(.)$ are
reserved for the stochastic versions of the same quantities. We will use
$\xrightarrow{P}$ to denote convergence in probability. The $\ell_{1}$ and
$\ell_{2}$ norms of vectors are denoted by $\|.\|_{1}$ and $\|.\|$
respectively unless otherwise mentioned. For matrices the $\|A\|$ will always
denote the largest singular value of $A$ (operator norm) and hence the same
notation $\|.\|$ will be reserved for the $\ell_{2}$ norm of a vector and the
operator of norm of the matrix, the difference being understood from the
context. We will denote the set $\\{1,\ldots,p\\}$ by $[p]$. For any subset
$S\subset[p]$ and a matrix $X$ we will denote the submatrix whose column
indices are restricted to $S$ by $X_{S}$. Similarly subvector of a vector $v$,
whose coordinates are restricted to $S$, will be called $v_{S}$. Throughout
the notation $C$ will denote a generic constant unless otherwise specified.
The Kronecker delta function will be denoted as
$\delta_{ij}=\mathds{1}_{i=j}$. For $\mu$ in $\mathbb{R}^{m}$ ($m>0$) we will
also use $\delta_{\mu}$ to define the delta measure which is $1$ at $\mu$ and
$0$ otherwise. Since the same notation is used they will appear in separate
context and the one referred to will be clear from the context. For
$(\mu_{1},\ldots,\mu_{p})$ with $\mu_{i}\in\mathbb{R}^{m}$ ($m,p>0,1\leq i\leq
p$) we will define the empirical distribution by
$\frac{1}{p}\sum_{i=1}\delta_{\mu_{i}}$. For any sequences of probability
measures $\mu_{n}$ and another probability measure $\mu$, we say that
$\mu_{n}\xRightarrow{W_{2}}\mu$ if the following holds: there exists a
sequence of couplings $\Pi_{n}$ with marginals $\mu_{n}$ and $\mu$
respectively, so that if $(X_{n},X)\sim\Pi_{n}$, then
$E[(X_{n}-X)^{2}]\rightarrow 0$ as $n\rightarrow\infty$.

Next we fix some notations for the optimizers and the optimum value of the
risk that will help us state our results in a compact form. Let
$\varphi=\beta-\beta_{0}$ and
$\hat{\varphi}_{\mathcal{X}}=\hat{\beta}_{\mathcal{X}}-\beta_{0}$ where
$\hat{\beta}_{\mathcal{X}}$ is the minimizer of the empirical risk in equation
(1.1). Consider the expression of empirical risk in equation (1.1). For the
sake of brevity, we will denote $\hat{R}_{n}(Y,\mathcal{X},\beta)$ as
$R(\varphi,\mathcal{X})$, where the dependence on $\beta_{0}$ and $\xi$ (and
hence $Y$) is suppressed. Similarly, we will denote the minimum risk as
$R(\mathcal{X})$. Further we will denote the general form as
$R^{K}(\varphi,\mathcal{X})$ where $K=L$ or $K=R$ is used to distinguish
between the Lasso and ridge setups i.e whether
$f(\beta)=\|\beta\|_{1}/\sqrt{n}$ or $f(\beta)=\|\beta\|^{2}_{2}/2$
respectively. The minimum value of the empirical risk in this setup will be
denoted as $R^{K}(\mathcal{X})$ and the error by
$\hat{\varphi}^{K}_{\mathcal{X}}:=\hat{\beta}^{K}_{\mathcal{X}}-\beta_{0}$.
Finally we will abuse notation and call both $\hat{\varphi}_{\mathcal{X}}$ and
$\hat{\beta}_{\mathcal{X}}$ optimizers when there is no chance of confusion
and the quantity referred to will be understood from the context.

##  2 Examples of block dependent designs

As discussed in the preceding section, we seek to study models with block
dependencies among the design entries. To be precise, we define our formal
notion of block dependence below.

######  Definition 2.1.

A $p$-dimensional random vector $W$ is called block dependent (with dependence
parameter $d$) if there exist a partition $\\{S_{j}\\}_{j=1}^{k_{p}}$ of $[p]$
(i.e. $S_{j}$ are disjoint and $\cup_{j=1}^{k_{p}}S_{j}=[p]$) such that
$|S_{j}|\leq d\,\,\forall j$ and $W_{l}\perp W_{k}$ if $l\in S_{i},k\in
S_{j},i\neq j$.

The design matrices whose rows are i.i.d. block dependent random vectors will
be called block dependent designs. As a warm up toward our results, we present
here three concrete settings where block dependent designs arise naturally.

###  2.1 Penalized additive regression model

Let $(Y_{i},X_{i})_{i=1}^{n}$ be i.i.d. with $Y_{i}\in\mathbb{R}$ and
$X_{i}\in[0,1]^{p_{0}}$. We consider the following additive model

$Y_{i}=h^{*}(X_{i})+\epsilon_{i},$

with $h^{*}(X_{i})=\sum_{j=1}^{p_{0}}h_{j}^{*}(X^{j}_{i})$ and $X^{j}_{i}$
denoting the $j^{th}$ component of $X_{i}$. This model features in [Sto85],
where nonparametric estimation of $h^{*}$ is considered under an $L^{2}$ loss
with suitable smoothness restrictions on the function classes. A high-
dimensional version of the same problem can be found in [TZ19], where the
authors consider penalized estimators of the form
$\hat{h}=\sum_{i=1}^{p_{0}}\hat{h}_{j}$ that minimizes

$\frac{1}{2n}\sum_{i=1}^{n}(Y_{i}-h(X_{i}))^{2}+\mathcal{D}(h).$ (2.1)

Here $\mathcal{D}(h)$ penalizes the complexity of the function $h$ and the
$h_{j}$’s are the components of the additive model. In this context, [TZ19]
consider a more general model where each component $h_{j}$ is allowed to be
multivariate. For convenience, we first describe the model under a univariate
setup. In [TZ19], the authors consider an ultra-high-dimensional regime where
$\log(p_{0})=o(n)$ but with sparsity assumptions on the number of active
components $h_{j}$ (see Section 6 for a detailed discussion). We switch gears
to a different regime where ${p_{0}}/n\rightarrow\kappa$ where $\kappa$ can be
greater than 1. Further we do not assume any sparsity on the underlying model
and obtain an exact characterization of the estimation risk. In other words,
our work encompasses dense as well as sparse signals. In contrast to prior
work where the assumed sparsity is often sub-linear, we are able to allow
linear sparse models (see [TZ19] for other forms of sparsity, such as weak
sparsity, that takes a slightly different form, and we refrain from comparing
it further here).

To make the setting more concrete, we express each component $h_{j}$ in terms
of the trigonometric basis of $L^{2}[0,1]$, denoted by $\phi_{j}(t)$, and
given by

$\phi_{0}(t)=1,\quad\phi_{2k-1}(t)=\sqrt{2}cos(2\pi
kt),\quad\phi_{2k}(t)=\sqrt{2}sin(2\pi kt),\quad k=1,2,\ldots.$

In nonparametric estimation theory (see [Tsy09]) one considers estimation when
the functions are restricted to certain smoothness classes with a popular
choice being the periodic Sobolev class which is defined as follows

$W(\beta,Q)=\\{f\in
L^{2}[0,1]:\theta=\\{\theta_{l}\\}\in\Theta(\beta,Q)\text{, where
}\theta_{l}=\int_{0}^{1}\phi_{l}(t)f(t)dt\\},$ (2.2)

where $\Theta(\beta,Q)$ is the Sobolev ellipsoid defined by

$\Theta(\beta,Q)=\\{\theta=\\{\theta_{l}\\}\in\ell^{2}(\mathbb{N}):\sum_{l=1}^{\infty}\alpha_{l}\theta_{l}^{2}\leq
Q\\},$ (2.3)

with $\alpha_{l}=l^{2\beta}$ or $(l-1)^{2\beta}$ for even and odd $l$
respectively.

Let $h_{j}$ be a function of the form

$h_{j}(t)=\sum_{k=1}^{\infty}\theta^{j}_{k}\phi_{k}(t).$ (2.4)

Then observing that $\theta^{j}_{k}$ are Fourier coefficients one can consider
estimation of $h_{j}$ when $h_{j}\in W(\beta,Q)$ or equivalently
$\\{\theta^{j}_{k}\\}_{k=1}^{\infty}\in\Theta(\beta,Q)$. Thus the estimation
of the coefficients $\theta^{j}_{k}$ is equivalent to the estimation of the
function $h_{j}$ and the number of non-zero coefficients is a measure of
complexity of the function.

In this paper we additionally impose the condition that $h_{j}$ is a finite
linear combination of the basis functions i.e. it is a function of the form

$h_{j}(t)=\sum_{k=1}^{d}\theta^{j}_{k}\phi_{k}(t).$ (2.5)

Indeed such finite linear combinations can be interpreted as a subclass within
the periodic Sobolev class with finitely many Fourier coefficients and has
been widely studied, most notably in [BRT09]. Using (2.1) and (2.5), we arrive
at the penalized estimation problem

$\frac{1}{2n}\sum_{i=1}^{n}(Y_{i}-\sum_{j=1}^{p_{0}}\sum_{k=1}^{d}\theta^{j}_{k}\phi_{k}(X_{i}^{j}))^{2}+\lambda
D(\theta),$

where $D(\theta)$ penalizes the complexity of the function $h$ in terms of the
parameter $\theta$.

We observe the following facts. Since one can always center $Y$, we may drop
the intercept term arising from $\phi_{0}(t)$. Further, if we assume
$X^{j}_{i}\sim\text{ Unif }(0,1)$, then using the fact that $\\{\phi_{k}\\}$
is an orthonormal basis, we have $E[\phi_{k}(X^{j}_{i})]=0$ and
$E[\phi_{k}(X^{j}_{i})\phi_{l}(X^{j}_{i})]=\delta_{kl}$. Furthermore we assume
$X^{j}_{i}$s to be independent across $j$. Thus we can reformulate the above
problem to estimation of $\beta$ in the following linear regression problem

$Y=\mathcal{X}\beta+\xi,$ (2.6)

where the rows of $\mathcal{X}$ (a $n\times p_{0}d$ matrix) are of the form

$\mathcal{X}_{i}=(\phi_{1}(X^{1}_{i}),\ldots,\phi_{d}(X^{1}_{i}),\ldots,\phi_{d}(X^{p_{0}}_{i}),\ldots,\phi_{d}(X^{p_{0}}_{i}))^{T}$

and $\beta=(\theta^{j}_{k})_{j=1,k=1}^{p_{0},d}$. Thus the rows are
independent isotropic sub-Gaussian vectors with a block dependent structure
with each block having size $d$. We note that letting $p=p_{0}d$ we may
capture properties of estimators in this model by developing theory under the
setup where $p_{0}d/n\rightarrow\kappa$ (see Section 3.1).

Further note that for any estimator $\hat{h}_{j}(x)$ of the form
$\sum_{k=1}^{d}\hat{\theta}^{j}_{k}\phi_{k}(x^{j})$, the $L_{2}$ estimation
risk translates to

$\|\hat{h}_{j}-h_{j}\|^{2}:=\int_{0}^{1}(\hat{h}_{j}(t)-h_{j}(t))^{2}dt=\sum_{k=1}^{d}|\hat{\theta}^{j}_{k}-\theta^{j}_{k}|^{2}.$

Thus we have

$\sum_{j=1}^{p}\|h_{j}-\hat{h}_{j}\|^{2}=\sum_{j=1}^{p_{0}}\sum_{k=1}^{d}|\hat{\theta}^{j}_{k}-\theta^{j}_{k}|^{2}$
(2.7)

and it suffices to analyze the estimation risk $\|\hat{\beta}-\beta\|^{2}_{2}$
in the model (2.6).

###  2.2 Penalized functional regression

Let $(Y_{i},X_{i}(t),\epsilon_{i})_{i=1}^{n}$ be i.i.d. with
$Y_{i}\in\mathbb{R}$ and $X_{i}(t)\in\mathbb{R}$ for $t\in(0,1)$. We consider
the following functional regression model

$Y_{i}=\int_{0}^{1}X_{i}(t)\bm{\gamma}(t)+\epsilon_{i},$ (2.8)

with $\gamma(t)\in\mathbb{R}$ and $\epsilon_{i}$ being subGaussian random
variables.

This model and its variants, called functional linear regression or scalar-on-
function regression, has been widely studied in functional data analysis
[RGSO17, GBC+11, KM14]. The Kosambi–Karhunen–Loève theorem states that under
standard assumptions the stochastic process $X_{i}(t)$ admits an expansion
with respect to an orthonormal basis i.e

$X_{i}(t)=\sum_{k=1}^{\infty}\zeta_{ik}\phi_{k}(t),$

where the random variables $\zeta_{ik}$s have mean $0$ and
$E[\zeta_{il}\zeta_{ik}]=\lambda_{k}\delta_{kl}$ i.e. they are uncorrelated
with variance $\lambda_{k}$. When $X_{i}(t)$ is expanded upto a finite number
of terms as is used in practice [RGSO17], the regression model can be written
as

$Y_{i}=\sum_{k=1}^{d}\zeta_{ik}\theta_{k}+\epsilon_{i},$

where we have also expanded the function $\gamma(t)$ as
$\bm{\gamma}(t)=\sum_{k=1}^{d}\theta_{k}\phi_{k}(t)$. In the multivariate
setup the data is of the form
$(Y_{i},\mathbf{X}_{i}(t),\epsilon_{i})_{i=1}^{n}$ where $Y_{i}\in\mathbb{R}$
and $\mathbf{X}_{i}(t)\in\mathbb{R}^{p}$ for $t\in(0,1).$ We denote the
coordinates of the multivariate function $\mathbf{X}_{i}(t)$ as $X^{j}_{i}(t)$
and we assume the coordinate functions to be independent. We have the
following expansion

$X_{i}^{j}(t)=\sum_{k=1}^{d}\zeta^{j}_{ik}\phi_{k}(t).$

The random variables $\zeta^{j}_{ik}$ satisfies the relations
$E[\zeta^{j}_{ik}]=0$ and
$E[\zeta^{j}_{ik}\zeta^{j}_{il}]=\lambda^{j}_{k}\delta_{kl}$. We consider the
multivariate analogue of the model (2.8)

$Y_{i}=\sum_{j=1}^{p_{0}}\int_{0}^{1}X^{j}_{i}(t)\bm{\gamma}^{j}(t)+\epsilon_{i}.$

Finally letting $\gamma^{j}(t)=\sum_{k=1}^{d}\theta^{j}_{k}\phi_{k}(t)$ we
obtain

$Y_{i}=\sum_{j=1}^{p_{0}}\sum_{k=1}^{d}\zeta^{j}_{ik}\theta^{j}_{k}+\epsilon_{i}.$
(2.9)

We note that since $X^{1}_{i}(t),\ldots X^{p_{0}}_{i}(t)$ are independent
stochastic processes, (2.9) can also be written in the form
$Y=\mathcal{X}\beta+\xi$ with $\mathcal{X}_{i}$ of the form

$\mathcal{X}_{i}=(\zeta^{1}_{i1},\ldots,\zeta^{1}_{id},\ldots,\zeta^{p_{0}}_{i1},\ldots,\zeta^{p_{0}}_{id})^{T}$

and $\beta=(\theta^{j}_{k})_{j=1,k=1}^{p_{0},d}$. The design matrix
$\mathcal{X}$ has independent rows whose entries have the block dependent
structure as given in Definition 2.1. Indeed for each $i$, $X_{i}^{j}(t)$ and
$X_{i}^{m}(t)$ being independent for $m\neq j$, $\zeta^{j}_{ik}$ and
$\zeta^{m}_{il}$ are independent as well. Further we have
$\mathcal{X}=X\Lambda^{1/2}$ where $X_{ij}$s have variance $1$. We will assume
that that the vector $(\zeta^{j}_{ik})^{d}_{k=1}$ is subGaussian random vector
(2.9) and that $E[|\zeta^{j}_{ik}|^{4}]\leq K$ for some constant $K$. In
particular if $\zeta^{j}_{ik}$ are bounded and $d$ remains constant the above
assumptions trivially holds. Also, note that the matrix $\Lambda$ is a
diagonal matrix and we will assume that the diagonal entries $\lambda_{i}$
satisfy $c\leq\lambda_{i}\leq C$ for some $c>0$ for all
$i\in\\{1,\ldots,p_{0}d\\}$.

A common approach towards estimating the vector $\beta$ is to consider the
following penalized estimation problem (see [KM14] for example)

$\hat{\beta}=\operatornamewithlimits{arg\,min}_{\beta}\frac{1}{2n}\|Y-\mathcal{X}\beta\|^{2}+f(\beta)$

and then construct
$\hat{\bm{\gamma}}^{j}(t)=\sum_{k=1}^{d}\hat{\theta}^{j}_{k}\phi_{k}(t)$. As
in the case of Example 2.1 we have

$\sum_{j=1}^{p_{0}}\|\bm{\gamma}_{j}-\hat{\bm{\gamma}}_{j}\|^{2}=\sum_{j=1}^{p_{0}}\sum_{k=1}^{d}|\hat{\theta}^{j}_{k}-\theta^{j}_{k}|^{2},$
(2.10)

and we are reduced to the familiar setup of finding an asymptotic expression
for $\|\hat{\beta}-\beta\|^{2}_{2}$ in the model (2.6).

######  Remark 2.1.

We note that while the concept that nonparametric models can be studied as
linear models via basis expansion is widely studied in the literature, the
structure of dependence arising from such models is the focus of our study.
Unless Gaussian assumptions are used (for example assuming $X(t)$ is a
Gaussian process) the design matrix contains rows with dependent entries. In
the first and second model, we may assume that $d$ is finite and
$n/(p_{0}d)\rightarrow\kappa^{-1}$. This assumption can be relaxed to the
assumption $c<n/p_{0}<C$ for some constants $c$ and $C$. In the more general
setup we can allow $d$ to vary i.e $k\in\\{1,\ldots d_{j}\\}$ and
$cn<\sum_{j=1}^{p}d_{j}<Cn$. We will assume that each $d_{i}$ is bounded but
in the most general setup they can grow polylogarithmically with $n$.

###  2.3 Block dependent covariates in GWAS

In Genome Wide Association Studies (GWAS) one often studies the association
between phenotypes ($Y_{i}$’s) and genetic markers/single nucleotide
polymorphism (SNP) $X_{ij}$ where $i$ denotes the $i^{th}$ individual and
$j\in\\{1,\ldots,p\\}$. The markers $X_{ij}$ typically follow a dependence
structure where a particular SNP is dependent on SNPs of nearby loci, a
phenomenon called linkage disequilibrium. This phenomenon is taken into
account in the detection of causal SNPs and we refer the readers to [SBC+] and
the references therein for a detailed account.

While most measures of linkage disequilibrium is based on correlation (see
[Lew88]), other measures of association has been considered as well. For
example, [GD12] describes a measure of association in terms of Kullback-
Leibler distance between distributions. The same reference also points out
that situations of dependence may arise where the associated variables may be
uncorrelated despite being dependent and that correlation is rarely useful
beyond the case of Gaussian designs. Furthermore in GWAS, the markers $X_{ij}$
typically take on three different discrete values, encoding allele
frequencies, and therefore this application rarely encounters Gaussian
designs. These observations are perfectly in tandem with the general model
that we consider in this paper. To elucidate the occurrence of uncorrelated
but dependent random variables with discrete support we consider the following
toy example:

X | A | B | C
---|---|---|---
$a_{1}$ | 1 | 0 | 0
$a_{2}$ | -1 | 0 | 0
$a_{3}$ | 0 | 1 | 0
$a_{4}$ | 0 | -1 | 0
$a_{5}$ | 0 | 0 | 1
$a_{6}$ | 0 | 0 | -1.

Let $X$ be a random variable taking six distinct values $a_{1},\ldots,a_{6}$
with equal probabilities. Further let the three random variables take values
according to the entries of the $i^{th}$ row i.e. when $X=a_{1}$ we have
$A=1,B=0,C=0$, and so forth. It can be easily verified that the marginal
distribution of $A,B,C$ are same and they have mean $0$. Further their
covariance matrix is $cI_{3}$ for some constant $c$, so that the vector
$(A,B,C)$ can be easily scaled to obtain an isotropic random vector. Further
because of the underlying generation mechanism, they are dependent. We note
that this can be easily generalized to $d$ random variables from a table with
$2d$ rows.

On the other hand, the other aspect of the dependence structure arising in
GWAS is the concept of neighborhood dependence that tells us that a particular
SNP depends only on its neighbors. Of particular importance is the block
structure considered in [PIFP08], where there is linkage disequilibrium if and
only if two SNPs belong to the same block. Our block dependence structure in
this paper thus encompasses this critical GWAS example.

After discussing our motivation and relevant examples, we now proceed to
present the preliminaries and assumptions necessary for our main results.

##  3 Preliminaries

###  3.1 Assumptions

Throughout we assume that we observe n i.i.d. samples
$\\{Y_{i},\mathcal{X}_{i},1\leq i\leq n\\}$. We will work in a high-
dimensional setup where the covariate dimension $p$ is allowed to grow with
the sample size $n$. To make this rigorous, we consider a sequence of problem
instances $\\{Y_{i,n},\mathcal{X}_{i,n},\xi_{i,n},1\leq i\leq
n,\beta_{0}(n),\beta(n)\\}_{n\geq 1}$ and work under the setting of a linear
model

$Y_{i,n}=\mathcal{X}^{T}_{i,n}\beta_{0}(n)+\xi_{i,n},$

with $Y_{i,n}\in\mathbb{R},\mathcal{X}_{i,n}\in\mathbb{R}^{p(n)}$, and
$\beta_{0}(n)\in\mathbb{R}^{p(n)}$. We allow $p(n),n\rightarrow\infty$ with
$p(n)/n\rightarrow\kappa\in(0,\infty)$ and in the sequel we will drop the
dependence on $n$ whenever it is clear from the context. Further we let
$\xi_{i}$s be independent uniformly sub-Gaussian random variables with
variance $\sigma^{2}$. Note they do not need to arise from the same
distribution. . In a more compact form the above model will be written as

$Y=\mathcal{X}\beta_{0}+\xi,$ (3.1)

where $\mathcal{X}\in\mathbb{R}^{n\times p},Y,\xi\in\mathbb{R}^{n}$.

Our assumptions on the design $\mathcal{X}$, the signal $\beta_{0}$, and the
tuning parameter $\lambda$ are as follows.

######  Assumption 1.

(Assumptions on the design) The rows of the design $\mathcal{X}$ are i.i.d.
random vectors each of which is block dependent with dependence parameter $d$.
We assume that $\mathcal{X}=X\Lambda^{1/2}$ where the rows of $X$ are centered
and isotropic i.e. if $X_{i}$ denotes the $i$-th row of $X$ then
$E[X_{i}]=0,E[X_{ij}X_{ik}]=\delta_{jk}$. Further we assume that the entries
have bounded fourth moment ($E|X_{ij}|^{4}\leq K$) and the row vector $X_{i}$
is a subGaussian random vector. Furthermore, we assume that $\Lambda$ is a
diagonal matrix with the diagonal entries $\lambda_{i}$ satisfying
$c\leq\lambda_{i}\leq C$ for some positive constants $c,C$.

As mentioned in the remark at the end of Subsection 2.2, the dependence occurs
in blocks and the block sizes should be bounded by the dependence parameter
$d$. In Section 7, we establish that our universality holds as long as
$d=o\left(\left(\frac{n}{\log n}\right)^{1/5}\right)$. Finally, the assumption
$E[X_{ij}^{4}]\leq K$ can be weakened to an assumption involving $d,n$ and the
moments, but for simplicity, we will state our theorems under this simplified
assumption.

######  Assumption 2.

The signal satisfies the bound $\beta^{T}_{0}\Lambda\beta_{0}\leq C$. Let
$v_{i}=\sqrt{n\lambda_{i}}\beta_{0,i}$ for $1\leq i\leq p$. Then we assume
that

$\frac{1}{p}\sum_{i=1}^{p}\delta_{\lambda_{i},v_{i}}\xRightarrow{W_{2}}\mu,$

for some measure $\mu$ supported on $\mathbb{R}^{\geq 0}\times\mathbb{R}$.
Further we assume that $\|v\|_{\infty}\leq C$.

######  Assumption 3.

The tuning parameter $\lambda$ satisfies $\lambda\geq\lambda_{0}$ for a
constant $\lambda_{0}$.

We remark that we require this assumption only for the case of the Lasso and
is the analog of restricted strong convexity type assumptions in the Lasso
literature (see Section 7.1 for further details).

###  3.2 Choice of penalty function

As will be shown in Section 7, universality of both the empirical risk and the
estimation risk depends on establishing apriori that the optimizers are
guaranteed to lie in “nice” sets. However establishing this property requires
a case-by-case analysis. In this paper, we consider the two most popular
choices of penalty used in the statistics literature—the Lasso and the
ridge—that can form prototypes for many other popular examples, the ridge
serving as a prototype for strong convex penalties and the Lasso serving as a
prototype in the absence of strong convexity. Since we are able to handle
these prototypes, we believe our method can be extended to handle other
separable penalties.

######  Remark 3.1.

Some comments on the scaling of the penalties are also in order. In [HS23])
the entries of $\mathcal{X}$ are $O_{p}(n^{-1/2})$ and
$f(\beta)=\|\beta\|_{1}/n$ or $f(\beta)=\|\beta\|^{2}_{2}/2n$ respectively.
However in our case, the entries of $\mathcal{X}$ are $O_{p}(1)$. Writing
$A=\mathcal{X}/\sqrt{n}$ and $\mu=\sqrt{n}\beta$, equation (1.1) can be
rewritten in the form

$\hat{R}_{n}(y,A,\mu)=\frac{1}{2n}\sum_{i=1}^{n}\|Y_{i}-A^{T}_{i}\mu\|^{2}+\lambda\bar{f}(\mu),$
(3.2)

where $\bar{f}(\mu)=\|\mu\|_{1}/n$ or $\bar{f}(\mu)=\|\mu\|^{2}_{2}/2n$ and we
recover the setup in [HS23]. We have avoided the $n^{-1/2}$ scaling in the
design matrix since it helps to state the assumptions in a concise fashion and
to borrow certain results from the random matrix literature. In our setup we
end up with the non-standard scaling of the penalty i.e.
$f(\beta)=\|\beta\|_{1}/\sqrt{n}$ or $f(\beta)=\|\beta\|^{2}_{2}/2$
respectively.

###  3.3 Fixed point equations for the estimation risk

Finally, our universality result states that the estimation risk of
regularized estimators under our setting is asymptotically the same as that in
a setting where the design has i.i.d. Gaussian entries. Extensive prior work
characterizes the risk of convex regularized estimators in the Gaussian case
[BM11, KBB+13, DM16]. In this characterization, a certain system of fixed
point equations plays a critical role. We review this system below for
convenience. Let

$\eta_{k}(x,\lambda):=\operatornamewithlimits{arg\,min}_{x\in\mathbb{R}^{p}}\Big{\\{}\frac{1}{2}\|z-x\|^{2}+\lambda\frac{\|x\|^{k}_{k}}{k}\Big{\\}}.$

We will focus on two particular values of $k$ in the above expression of
$\eta_{k}(,)$; $k$ be taken as $2$ when $K=R$ and $1$ when $K=L$ (i.e. ridge
and Lasso respectively).

Now let $\mu_{0,i}=\sqrt{n\lambda_{i}}\beta_{0,i}$ and
$\omega_{i}=\lambda_{i}^{-1/2}$. Also define $Q_{n}$ as the law of the
$3$-tuple of random variables
$(M,\Omega,Z)\sim(\frac{1}{p}\sum_{i=1}^{p}\delta_{\mu_{0,i},\omega_{i}})\otimes
N(0,1)$. We have the following system of equations

$\displaystyle(\gamma^{K}_{*})^{2}$
$\displaystyle=1+\frac{p}{n}E_{Q_{n}}\left[\eta_{k}\left(M+\gamma^{K}_{*}Z,\frac{\gamma^{K}_{*}\lambda\Omega^{k}}{\beta^{K}_{*}}\right)-M\right]^{2},$
(3.3) $\displaystyle\beta^{K}_{*}$
$\displaystyle=\gamma^{K}_{*}\left[1-\frac{p}{n}E_{Q_{n}}\left[\eta^{\prime}_{k}\left(M+\gamma^{K}_{*}Z,\frac{\gamma^{K}_{*}\lambda\Omega^{k}}{\beta^{R}_{*}}\right]\right)\right].$

Consistent with our notation, $(\beta_{*}^{R},\gamma_{*}^{R})$ will be the
solution of the fixed point equations (3.3) for ridge and
$(\beta_{*}^{L},\gamma_{*}^{L})$ will the corresponding solution for the
Lasso. Next we define “error" terms which are functions of the solutions of
the above equation system. Let $g\sim N(0,I_{p})$. Define the vectors
$\varphi^{R}_{*}$ and $\varphi^{L}_{*}$ for the ridge and Lasso problems in
terms of their $i^{th}$ entries as follows

$\displaystyle\varphi^{R}_{*,i}$
$\displaystyle=\eta_{2}\left(\beta_{0,i}+\frac{\gamma^{R}_{*}\omega_{i}g_{i}}{\sqrt{n}},\frac{\gamma^{R}_{*}\lambda\omega_{i}^{2}}{\beta^{R}_{*}}\right)-\beta_{0,i},$
(3.4) $\displaystyle\varphi^{L}_{*,i}$
$\displaystyle=\eta_{1}\left(\beta_{0,i}+\frac{\gamma^{L}_{*}\omega_{i}g_{i}}{\sqrt{n}},\frac{\gamma^{L}_{*}\lambda\omega_{i}^{2}}{\sqrt{n}\beta^{L}_{*}}\right)-\beta_{0,i},$
(3.5)

for $i\in\\{1,\ldots,p\\}$. The above term will play a crucial role in the
asymptotic characterization of the estimation risk. We are now ready to state
the main results of our paper.

##  4 Main result

In this section we state the main results of our paper. We consider the linear
model (3.1) and seek to study universality properties of the optimum value of
the empirical risk and the estimation risk of the optimizer. In particular, we
aim to establish that

$\displaystyle\min_{\beta}\hat{R}_{n}(Y,\mathcal{X},\beta)\approx\min_{\beta}\hat{R}_{n}(Y,\mathcal{\mathcal{G}},\beta)\quad\text{and}\quad\|\hat{\beta}_{\mathcal{X}}-\beta_{0}\|^{2}\approx\|\hat{\beta}_{\mathcal{G}}-\beta_{0}\|^{2},$
(4.1)

where $\mathcal{G}=G\Lambda^{1/2}$, $G$ a matrix with i.i.d. standard Gaussian
entries.

Recall that we have defined the shifted versions of the optimizers as
$\hat{\varphi}^{K}_{\mathcal{X}}:=\hat{\beta}^{K}_{\mathcal{X}}-\beta_{0}$.
Before we state our main theorems, we describe a set restricted to which our
universality result holds.

$\mathcal{T}_{n}:=\\{\varphi:\|\varphi\|_{\infty}\leq C\sqrt{\frac{d\log
n}{n}},\|\varphi\|\leq C\\}.$

######  Theorem 4.1.

Suppose the design matrix $\mathcal{X}=X\Lambda^{1/2}$ satisfies Assumption 1
and $\beta_{0}$ satisfies Assumption 2. Further $\mathcal{G}=G\Lambda^{1/2}$,
where $G\in\mathbb{R}^{n\times p}$ contains i.i.d. Gaussian entries, and that
$\psi$ is a bounded differentiable function with bounded Lipschitz derivative.
Then $\exists\gamma_{n}=o(1)$ such that for any subset
$S_{n}\subset\mathbb{R}^{p}$, we have

$|E(\psi(\min_{\varphi\in\mathcal{S}_{n}\cap\mathcal{T}_{n}}R^{R}(\varphi,\mathcal{X})))-E(\psi(\min_{\varphi\in\mathcal{S}_{n}\cap\mathcal{T}_{n}}R^{R}(\varphi,\mathcal{G})))|\leq\gamma_{n}.$

Further if we assume Assumption 3 in addition to Assumptions 1-2, then we have

$|E(\psi(\min_{\varphi\in\mathcal{S}_{n}\cap\mathcal{T}_{n}}R^{L}(\varphi,\mathcal{X})))-E(\psi(\min_{\varphi\in\mathcal{S}_{n}\cap\mathcal{T}_{n}}R^{L}(\varphi,\mathcal{G})))|\leq\gamma_{n}.$

In the next step we show that the Lasso and ridge optimizers denoted by
$\hat{\varphi}^{L}_{\mathcal{X}}$ and $\hat{\varphi}^{R}_{\mathcal{X}}$ lie in
the subset $\mathcal{T}_{n}$ with high probability. Thus the restriction over
$\mathcal{T}_{n}$ can be easily lifted and we have the following result.

######  Corollary 4.1.

Assume the conditions of Theorem 4.1. Then we have

$|E(\psi(\min_{\varphi}R^{K}(\varphi,\mathcal{X})))-E(\psi(\min_{\varphi}R^{K}(\varphi,\mathcal{G})))|\leq\gamma_{n},$

for some $\gamma_{n}=o(1)$. In particular if
$R^{K}(\mathcal{G})\rightarrow\rho$, then $R^{K}(\mathcal{X})\rightarrow\rho$
as well.

Next we turn to characterizing the estimation risk of the optimizers. The
difficulty and the methods used to prove this result is thoroughly discussed
in Section 7. Finally, we have our main result.

######  Theorem 4.2.

Assume the conditions in Theorem 4.1. For all Lipshitz functions
$\varrho:\mathbb{R}^{p}\rightarrow\mathbb{R}$ and $\epsilon>0$ we have

$P(|\varrho(\hat{\varphi}^{K}_{X})-\varrho(\hat{\varphi}^{K}_{G})|\geq\epsilon)\leq\varepsilon_{n},$
(4.2)

for some $\varepsilon_{n}\rightarrow 0$.

We will establish in the proof of Theorem 4.2 that both
$\varrho(\hat{\varphi}^{K}_{X})$ and $\varrho(\hat{\varphi}^{K}_{G})$
concentrate around the common value $E[\varrho(\varphi^{K}_{*})]$ where
$\varphi^{R}_{*}$ and $\varphi^{L}_{*}$ are defined in equations (3.4) and
(3.5) respectively. Thus by choosing a suitable $\varrho$, the above theorem
can naturally be specialized to yield the estimation risk of the ridge and the
Lasso in our dependent covariates setup. We obtain the following corollary for
dependent subGaussian designs.

######  Corollary 4.2.

Let $\gamma_{*}^{K}$ and $\beta_{*}^{K}$ be fixed points of the equation
system (3.3). In the setup of Theorem 4.1, we have

$\displaystyle\|\hat{\beta}^{R}_{\mathcal{X}}-\beta_{0}\|^{2}-E_{\bar{Q}_{n}}\left[\eta_{2}\left(M+\frac{\gamma^{R}_{*}\Omega
Z}{\sqrt{n}},\frac{\gamma^{R}_{*}\lambda\Omega^{2}}{\beta^{R}_{*}}\right)-M\right]^{2}$
$\displaystyle\xrightarrow{P}0,$
$\displaystyle\|\hat{\beta}^{L}_{\mathcal{X}}-\beta_{0}\|^{2}-E_{\bar{Q}_{n}}\left[\eta_{1}\left(M+\frac{\gamma^{L}_{*}\Omega
Z}{\sqrt{n}},\frac{\gamma^{L}_{*}\lambda\Omega^{2}}{\sqrt{n}\beta^{L}_{*}}\right)-M\right]^{2}$
$\displaystyle\xrightarrow{P}0.$

Here the expectations are taken with respect to the measure $\bar{Q}_{n}$
which is the law of the $3$-tuple of random variables
$(M,\Omega,Z)\sim(\frac{1}{p}\sum_{i=1}^{p}\delta_{\beta_{0,i},\omega_{i}})\otimes
N(0,1)$ where $\omega_{i}=\lambda^{-1/2}_{i}$.

Note that the equivalent results for estimation risk in the independent
Gaussian design have been obtained in [EK18] and [BM11] for ridge and Lasso
respectively and thus our result generalizes the exact risk characterization
to the dependent subGaussian case. We are now in position to compute the
estimation risks of the Lasso and the ridge in the penalized regression models
described in Section 2. In the following corollaries, we demonstrate these for
the two nonparametric regression models we described.

######  Corollary 4.3.

Let

$Y_{i}=\sum_{j=1}^{p_{0}}h^{*}_{j}(X^{j}_{i})+\epsilon_{i},\quad
i\in\\{1,\ldots,n\\},$

where $X^{j}_{i}$ are i.i.d. Unif(0,1), and
$h^{*}_{j}(t)=\sum_{k=1}^{d}\theta^{j}_{0k}\phi_{k}(t)$. Define
$\theta=\\{\theta_{k}^{j}\\}_{j=1,k=1}^{p_{0},d}$ and
$\beta_{0}=\\{\theta_{0,k}^{j}\\}_{j=1,k=1}^{p_{0},d}$ and let $\beta_{0}$
satisfy Assumption 1 with $\Lambda=I_{p_{0}d}$. Further define the optimizers
as follows

$\displaystyle\hat{\theta}^{L}$
$\displaystyle=\operatornamewithlimits{arg\,min}_{\theta}\frac{1}{2n}\sum_{i=1}^{n}(Y_{i}-\sum_{j=1}^{p_{0}}\sum_{k=1}^{d}\theta^{j}_{k}\phi_{k}(X_{i}^{j}))^{2}+\frac{\lambda}{\sqrt{n}}\sum_{j=1}^{p_{0}}\sum_{k=1}^{d}|\theta^{j}_{k}|,$
$\displaystyle\hat{\theta}^{R}$
$\displaystyle=\operatornamewithlimits{arg\,min}_{\theta}\frac{1}{2n}\sum_{i=1}^{n}(Y_{i}-\sum_{j=1}^{p_{0}}\sum_{k=1}^{d}\theta^{j}_{k}\phi_{k}(X_{i}^{j}))^{2}+\frac{\lambda}{2}\sum_{j=1}^{p_{0}}\sum_{k=1}^{d}|\theta^{j}_{k}|^{2}.$

Then denoting
$\hat{h}^{L}_{j}(t)=\sum_{k=1}^{d}\hat{\theta}_{k}^{j,L}\phi_{k}(t)$ and
$\hat{h}^{R}_{j}(t)=\sum_{k=1}^{d}\hat{\theta}_{k}^{j,R}\phi_{k}(t)$ we have,

$\sum_{j=1}^{p_{0}}\|\hat{h}^{R}_{j}-h^{*}_{j}\|^{2}-E_{\tilde{Q}_{n}}\left[\eta_{1}\left(M+\frac{\gamma^{L}_{*}Z}{\sqrt{n}},\frac{\gamma^{L}_{*}\lambda}{\sqrt{n}\beta^{L}_{*}}\right)-M\right]^{2}\xrightarrow{P}0.$
(4.3)

Further if Assumption 3 is satisfied we have

$\sum_{j=1}^{p_{0}}\|\hat{h}^{L}_{j}-h^{*}_{j}\|^{2}-E_{\tilde{Q}_{n}}\left[\eta_{2}\left(M+\frac{\gamma^{R}_{*}Z}{\sqrt{n}},\frac{\gamma^{R}_{*}\lambda}{\beta^{R}_{*}}\right)-M\right]^{2}\xrightarrow{P}0.$
(4.4)

In the above two statements the expectations are taken with respect to the
measure $\tilde{Q}_{n}$ which is the law of the $2$-tuple of random variables
$(M,Z)\sim(\frac{1}{p}\sum_{i=1}^{p}\delta_{\beta_{0,i}})\otimes N(0,1)$.

######  Corollary 4.4.

Let

$Y_{i}=\sum_{j=1}^{p_{0}}\int_{0}^{1}X^{j}_{i}(t)\bm{\gamma}^{j}_{0}(t)+\epsilon_{i},\quad
i\in\\{1,\ldots,n\\},$

where $X_{i}^{j}(t)$s are independent,
$X_{i}^{j}(t)=\sum_{k=1}^{d}\zeta^{j}_{ik}\phi_{k}(t)$, and
$\bm{\gamma}^{j}_{0}(t)=\sum_{i=1}^{d}\theta^{j}_{0k}\phi_{k}(t)$. Define
$\theta=\\{\theta_{k}^{j}\\}_{j=1,k=1}^{p_{0},d}$,
$\beta_{0}=\\{\theta_{0,k}^{j}\\}_{j=1,k=1}^{p_{0},d}$,
$Var(\zeta^{j}_{ik})=\lambda_{(j-1)d+k}$, and
$\Lambda=diag(\lambda_{1},\ldots,\lambda_{p_{0}d})$. Let the vectors
$\zeta_{i}=(\zeta^{j}_{ik})_{j=1,k=1}^{p_{0},d}$ satisfy Assumption 1. Further
let $\beta_{0}$ satisfy Assumption 2. Define the optimizers as follows

$\displaystyle\hat{\theta}^{L}$
$\displaystyle=\operatornamewithlimits{arg\,min}_{\theta}\frac{1}{2n}\sum_{i=1}^{n}(Y_{i}-\sum_{j=1}^{p_{0}}\sum_{k=1}^{d}\theta^{j}_{k}\zeta^{j}_{ik})^{2}+\frac{\lambda}{\sqrt{n}}\sum_{j=1}^{p}\sum_{k=1}^{d}|\theta^{j}_{k}|,$
$\displaystyle\hat{\theta}^{R}$
$\displaystyle=\operatornamewithlimits{arg\,min}_{\theta}\frac{1}{2n}\sum_{i=1}^{n}(Y_{i}-\sum_{j=1}^{p_{0}}\sum_{k=1}^{d}\theta^{j}_{k}\zeta^{j}_{ik})^{2}+\frac{\lambda}{2}\sum_{j=1}^{p_{0}}\sum_{k=1}^{d}|\theta^{j}_{k}|^{2}.$

Then denoting
$\hat{\bm{\gamma}}^{L}_{j}(t)=\sum_{k=1}^{d}\hat{\theta}_{k}^{j,L}\phi_{k}(t)$
and
$\hat{\bm{\gamma}}^{R}_{j}(t)=\sum_{k=1}^{d}\hat{\theta}_{k}^{j,R}\phi_{k}(t)$
we have

$\sum_{j=1}^{p_{0}}\|\hat{\bm{\gamma}}^{R}_{j}-\bm{\gamma}^{*}_{j}\|^{2}-E_{\bar{Q}_{n}}\left[\eta_{2}\left(M+\frac{\gamma^{R}_{*}\Omega
Z}{\sqrt{n}},\frac{\gamma^{R}_{*}\lambda\Omega^{2}}{\beta^{R}_{*}}\right)-M\right]^{2}\xrightarrow{P}0.$
(4.5)

Further if Assumption 3 is satisfied we have

$\sum_{j=1}^{p_{0}}\|\hat{\bm{\gamma}}^{L}_{j}-\bm{\gamma}^{*}_{j}\|^{2}-E_{\bar{Q}_{n}}\left[\eta_{1}\left(M+\frac{\gamma^{L}_{*}\Omega
Z}{\sqrt{n}},\frac{\gamma^{L}_{*}\lambda\Omega^{2}}{\sqrt{n}\beta^{L}_{*}}\right)-M\right]^{2}\xrightarrow{P}0.$
(4.6)

Here the expectations are taken with respect to the measure $\bar{Q}_{n}$
which is the law of the $3$-tuple of random variables
$(M,\Omega,Z)\sim(\frac{1}{p}\sum_{i=1}^{p}\delta_{\beta_{0,i},\omega_{i}})\otimes
N(0,1)$ where $\omega_{i}=\lambda^{-1/2}_{i}$.

######  Remark 4.1.

Corollaries 4.3 and 4.4 follows directly by applying Corollary 4.2 to the
additive and functional regression models respectively. The simpler form of
the risks in (4.3) and (4.4) in comparison to (4.5) and (4.6) is due to the
fact the the rows in the former setup are isotropic random vectors and hence
$\Lambda=\tilde{\Omega}=I_{p_{0}d}$. Similarly, in this simplified setup the
measure $\bar{Q}_{n}$ appearing Corollary 4.2 simplifies to $\tilde{Q}_{n}$ in
(4.3) and (4.4).

##  5 Illustration

In this section, we demonstrate the efficacy of our result via experiments. In
particular, we consider the first two settings in Section 2 and compare the
risk of regularized estimators in each model with that under i.i.d. Gaussian
designs. Across our simulations, we observe that universality kicks in for
quite moderate sample sizes, a reassuring observation that suggests our
current asymptotic abstraction captures reality reasonably well. As in Section
2 we will denote $p=p_{0}d$, i.e. there will be $p_{0}$ blocks each having
size $d$.

###  5.1 Penalized additive regression model

Recall the setup given in Example 2.1,

$Y_{i}=\sum_{i=1}^{p_{0}}h_{j}^{*}(X^{j}_{i})+\epsilon_{i},\quad
h_{j}(t)=\sum_{k=1}^{d}\theta^{j}_{k}\phi_{k}(t),\quad\phi_{2l-1}(t)=\sqrt{2}cos(2\pi
lt),\quad\phi_{2l}(t)=\sqrt{2}sin(2\pi lt)\text{ for }l=1,\ldots,d/2.$

We set $n=200,p_{0}=30,d=10$ so that $(p_{0}d)/n=1.5$. For the $i^{th}$ row of
the design matrix, we use the following strategy: Generate i.i.d.
$\\{X^{j}_{i}\\}_{j=1}^{30}$ such that $X^{j}_{i}\sim Unif(0,1)$ and construct
the following

$\mathcal{X}_{i}=(\phi_{1}(X^{1}_{i}),\ldots,\phi_{10}(X^{1}_{i}),\ldots,\phi_{1}(X^{30}_{i}),\ldots,\phi_{10}(X^{30}_{i}))^{T}.$

We repeat this construction for $n=200$ rows to create the design matrix
$\mathcal{X}$ and for the Gaussian problem, we construct the $200\times 300$
matrix $\mathcal{G}$ with i.i.d. Gaussian entries. We generate the error
entries $\epsilon_{i}$, $\bar{\epsilon}_{i}$ so that they are i.i.d. standard
normal. Finally, we generate the signal
$\beta_{0}=\\{\theta^{j}_{0,k}\\}^{p_{0},d}_{j=1,k=1}$ as
$\beta_{0,j}=n^{-1/2}\mathfrak{b}_{j}$, where the $\mathfrak{b}_{j}^{\prime}s$
are i.i.d. Bernoulli random variables, and subsequently, keep $\beta_{0}$
fixed across multiple runs/iterations of the simulation. For each iteration
$m$ (we will average over 50 iterations later), we generate data corresponding
to our two models under consideration as follows

$Y_{i}=\mathcal{X}^{T}_{i}\beta_{0}+\epsilon_{i},\quad
Y_{i}^{\mathcal{G}}=\mathcal{G}^{T}_{i}\beta_{0}+\bar{\epsilon}_{i}.$ (5.1)

We recall from (2.7) that in this model

$\sum_{j=1}^{p}\|h_{j}-\hat{h}_{j}\|^{2}=\|\hat{\beta}^{L}_{\mathcal{X}}-\beta_{0}\|^{2},$

if the Lasso is used and $\|\hat{\beta}^{R}_{\mathcal{X}}-\beta_{0}\|^{2}$ in
the case of ridge regression. In Figures (1(a)) and (1(b)), we plot the
estimation risks $\|\hat{\beta}^{L}_{\mathcal{X}}-\beta_{0}\|^{2}$ and
$\|\hat{\beta}^{R}_{\mathcal{X}}-\beta_{0}\|^{2}$ averaged over $50$
iterations with red curves. We overlay the corresponding risks for the
Gaussian problem, $\|\hat{\beta}^{L}_{\mathcal{G}}-\beta_{0}\|^{2}$ and
$\|\hat{\beta}^{R}_{\mathcal{G}}-\beta_{0}\|^{2}$, as black dots. Observe the
impeccable agreement of the risks under both settings that clearly validates
our universality results and demonstrates its impressive efficacy in sample
sizes as low as a couple of hundred.

(a) Lasso

(b) Ridge

Figure 1: Estimation risk in the penalized additive model (see Section 2.1)
averaged over 50 iterations with $n=200,p_{0}=30$, and $d=10$. The red curves
correspond to the risk $\|\beta^{L}_{\mathcal{X}}-\beta_{0}\|^{2}$ and
$\|\beta^{R}_{\mathcal{X}}-\beta_{0}\|^{2}$ for the Lasso and the ridge
respectively, while the corresponding risks for the Gaussian problem
$\|\beta^{L}_{\mathcal{G}}-\beta_{0}\|^{2}$ and
$\|\beta^{R}_{\mathcal{G}}-\beta_{0}\|^{2}$ are overlaid as black dots.

###  5.2 Penalized functional regression

Recall that in the setup given in Example 2.2 we have,

$Y_{i}=\sum_{j=1}^{p_{0}}\sum_{k=1}^{d}\zeta^{j}_{ik}\beta^{j}_{k}+\epsilon_{i},$

where $E[\zeta^{j}_{ik}]=0$
$E[\zeta^{j}_{ik}\zeta^{j}_{il}]=\delta_{kl}\lambda_{k}$. Further
$\zeta^{j}_{ik}$ and $\zeta^{m}_{il}$ are independent if $j\neq m$. We
consider the case when $n=500$ and $p_{0}=30$, and $d=10$ i.e. we construct a
setup where each row has $30$ blocks of size $10$ so that so that
$(p_{0}d)/n=0.6$. The random variables across the block are independent while
the random variables within the blocks are dependent. To construct dependent
random variables within a block, we generate $10$ independent Rademacher
random variables and multiply them by a common random variable, as defined
below. We repeat this procedure for every block. Let $V$ be a random variable
distributed as follows

$P(V=0)=\frac{1}{2},\quad P(V=-\sqrt{2})=\frac{1}{4},\quad
P(V=\sqrt{2})=\frac{1}{4}.$

We generate i.i.d. rows $X_{i}$ with $j$-th entry $X_{ij}$ distributed as
follows. Let $\\{U_{j}\\}_{j=1}^{300}$ and $\\{V_{j}\\}_{j=1}^{30}$ be two
sets of independent random variables with $U_{j}$’s distributed as i.i.d.
Rademacher and $V_{j}$s as i.i.d. random variables with the distribution same
as that of $V$. Now define $W_{j}=U_{j}V_{\lceil\frac{j}{10}\rceil}$ for
$j\in\\{1,\ldots,300\\}$. Next we generate the diagonal matrix $\Lambda$ with
$30$ identical blocks: the diagonal elements of the first block
$\lambda^{1/2}_{i},i\in 1\ldots 10$ are generated independently from
$Unif(1,2)$ and all other blocks are identical copies of the first block. It
can be easily verified that the random variables are pairwise uncorrelated and
the random variables within the blocks are not independent. We generate the
design matrix $\mathcal{X}$ as $\mathcal{X}=X\Lambda^{1/2}$. For the Gaussian
case, we generate a $500\times 300$ matrix $G$ with i.i.d. Gaussian entries
and then define $\mathcal{G}=G\Lambda^{1/2}$. As in the previous subsection,
we generate the signal $\beta_{0}=\\{\theta^{j}_{0,k}\\}^{p_{0},d}_{j=1,k=1}$
as $\beta_{0,j}=n^{-1/2}\mathfrak{b}_{j}$, where the
$\mathfrak{b}_{j}^{\prime}s$ are i.i.d. Bernoulli random variables, and
subsequently, keep $\beta_{0}$ fixed across multiple runs/iterations of the
simulation. Finally, we generate the random variables $Y$ and
$Y^{\mathcal{G}}$ following the linear models in (5.1) (after adjusting for
the dimension).

In the aforementioned setting, we plot the estimation risk of the Lasso and
the ridge as a function of $\lambda$. Figure (2(a)) shows Lasso with the red
curve being the case of the dependent sub-Gaussian design and the black dots
being the independent Gaussian design. Figure (2(b)) shows the corresponding
plot for the ridge. In both cases, the risk curves match, demonstrating the
validity of our universality result and the fact that the asymptotics kicks in
for quite moderate sample size and dimensions.

(a) Lasso

(b) Ridge

Figure 2: Estimation risk in the penalized functional regression model (see
Section 2.2) averaged over 50 iterations with $n=500,p_{0}=30$, and $d=10$.
The red curves corresponds to the risk
$\|\beta^{L}_{\mathcal{X}}-\beta_{0}\|^{2}$ and
$\|\beta^{R}_{\mathcal{X}}-\beta_{0}\|^{2}$ for Lasso and risk respectively,
while the corresponding risks for the Gaussian
$\|\beta^{L}_{\mathcal{G}}-\beta_{0}\|^{2}$ and
$\|\beta^{R}_{\mathcal{G}}-\beta_{0}\|^{2}$ are overlaid as black dots.

##  6 Related Literature

In this section, we provide a detailed discussion of existing universality
results in the literature, and situate our work in this broader context.
Universality results are pervasive in the literature on random matrix theory.
Over the past decade, the exploration of universality concerning the choice of
the design matrix distribution has gained traction in the context of high-
dimensional linear models. In the context of the Lasso, [KM11] established
universality of the cost optimum, while for the elastic net, [MN17]
established universality of the estimation risk. Similar results exist for
random linear inverse problems ([ASH19, OT17]). Recently, [HS23] studied a
broad spectrum of penalized regression problems and established universality
of the optimum value of the empirical risk and the risk of regularized
estimators under i.i.d. designs. [DSL23] established universality of the
optimizer as well as their risk under a broader class of structured and/or
semi-random covariate distributions.

Parallel universality results exist for approximate message passing algorithms
(cf. [BLM15, CL21, DLS23, WZF22]). Further, [HL22] demonstrated equivalence
between regression problems where the rows of the design matrix arise from
nonlinear transforms of Gaussian features and design matrices with linearized
Gaussian features. Subsequently, [MS22a] developed an extension of this result
to the neural tangent model and a linear transformation of the i.i.d. model.

We note that in terms of dependent covariates under the linear model
framework, [MS22a] is the most relevant to our setting. Although the two-layer
neural tangent model and the random feature model presented there are
intriguing examples of dependence from a machine learning standpoint, for this
discussion, we focus on the setup outlined in [MS22a, Section 3.3], i.e.,
linear functions of independent entries. Notably, this example involves rows
of the form $\Sigma^{1/2}Z_{i}$, where the entries of $Z_{i}$ are independent
sub-Gaussian. In this article, we broaden this understanding to encompass a
different form of dependence with block structure (see Section 2) that prior
work fails to capture. As noted earlier, this block dependence arises in
various widely used statistical models, as we demonstrate in Section 2. We
also note another limitation of [MS22a] in the context of estimation risk. The
paper proves the universality of the training error, which is the same as our
optimum but instead of estimation risk, discusses the universality of test
error. Although estimation risk can be obtained in their setting by a similar
argument, it requires some strong convexity conditions for the penalty
function. In our work, we overcome this barrier. Leveraging methods from
[HS23] in conjunction with new proof ideas, we are able to address the case of
the Lasso where strong convexity does not hold.

Our paper also builds a bridge between the proportional asymptotics literature
and the nonparametric regression literature, which has a long history. In
particular, we study additive models (see Section 2) that were previously
analyzed in the high-dimensional setting with $\log(p)=o(n)$ (where $p$
quantifies the the number of component functions in the additive model) along
with sparsity assumptions (see [TZ19]) on the number of active component
functions. [TZ19] (see [MvdGB09, KY10, YZ16, RJWY12] for similar models)
considers both smoothness and sparsity based penalties and also allows for
weak sparsity. We explore the additive models but under a high-dimensional
setting where $p/n\rightarrow\kappa$ ($\kappa$ can be greater than $1$),
without imposing sparsity assumptions. Furthermore, while the prior literature
was concerned with the rates of the estimation risk, we characterize the exact
behavior of the risk or rather the exact constant that it converges to in our
setting. A similar setup arises while dealing with the functional regression
model, where we obtain results without any sparsity assumption whatsoever on
the underlying function class. Finally, our paper considers a model from
genomics where the covariates may be dependent but uncorrelated (see [GD12]).
We have described a toy model (see [SSC18, SBC+] for other models) in Section
2.3, which showcases how such structures might arise and then showed that the
model is amenable to our universality analysis.

##  7 Proofs

Our universality proof relies on the following key observation: for showing
(i) universality of the optimum value of the empirical risk (Theorem 4.1) as
well as ii) universality of the estimation risk of regularized estimators
(Corollary 4.2), one requires to first establish that the estimators lie in
some "nice" set with high probability. After this is established, points (i)
and (ii) can be proved using separate techniques. For the subsequent
discussion, we will use the term universality of the optimizer to mean (4.2)
in the statement of Theorem 4.2. Before we delve into our proof, we provide a
brief description of our proof path below.

As a first step for points (i) and (ii), we require to prove that the
optimizer lies in a compact set whose $\ell_{2}$ norm is bounded by a constant
and $\ell_{\infty}$ norm approaches $0$ in the large $n$ limit. We prove these
key results in Lemmas 7.1 and 7.2 respectively. Subsequently for part (i), we
establish a version of normal approximation for linear combinations of
dependent random variables. For part (ii), we draw inspiration from the
techniques in [HS23]. That said, we emphasize that the techniques used in
[HS23] are heavily dependent on independence of the entries of the design, a
property that does not hold in our setting. This raises additional technical
challenges in our setting that we handle as we proceed. For part (ii), it
suffices to prove Theorem 4.2, once we have established the aforementioned
compactness property. For Theorem 4.2 in turn, we require the compactness
property, part (i), and a notion of separation in the Gaussian model, which we
name the Gordon gap.

As will be explained in the next section, the compactness property is non-
trivial to establish in the dependent subGaussian setup, and we use a novel
leave-d-out argument to solve the problem. In addition, while Stein’s method
has been used to show universality in several contexts, to the best of our
knowledge, the dependency neighbourhood technique that we employ in this paper
to show our normal approximation as part of point (i) has never seen prior
usage in the context of regression models with dependent designs. Finally, the
Gordon gap is a technical tool that is only relevant to the independent
Gaussian design problem (see Section 7.3) and has been used before in [HS23,
MM21]. Nonetheless, the scaling factor $\Lambda$, which is critical for
covering our example in Section 2.2, poses significant additional challenges
involving convergence of fixed points of certain equations that we overcome
via an equicontinuity argument.

###  7.1 Compactness property

As a first step, we prove that the optimizers
$\hat{\varphi}^{K}_{\mathcal{X}}:=\hat{\beta}^{K}_{\mathcal{X}}-\beta_{0}$
belong to the following set with probability at least $1-n^{-c}$

$\mathcal{T}_{n}:=\\{\varphi\in\mathbb{R}^{p}:\|\varphi\|_{\infty}\leq
C\sqrt{\frac{d\log n}{n}},\|\varphi\|\leq C\\}.$ (7.1)

Since the ridge regression objective is strongly convex, the $\ell_{2}$ bound
$\|\hat{\varphi}_{\mathcal{X}}^{R}\|\leq C$ follows trivially. For the Lasso
the analogous condition follows due to a restricted strong convexity type
property that we discuss next. In the traditional theory for Lasso, in the
setting of ultra-high dimensions ($p>>n$), it is customary to assume sparsity
on the underlying signal. This allows one to define the familiar and famous
restricted strong convexity condition (see [NRWY12] and references cited
therein). Using this, one can subsequently control the $\ell_{2}$ norm of the
Lasso solution. Since we refrain from explicitly assuming sparsity assumptions
on the signal, this strategy does not directly translate to our setting.
However, in our high-dimensional regime, even when $p>n$, when the tuning
parameter is sufficiently large (Assumption 3, see also [HS23, Lemma 6.3]),
one can establish that the Lasso solution is sparse (with sparsity
proportional to the sample size) with high probability. This implies that
having control on the smallest singular value of $\mathcal{X}_{S}$ (matrix
formed by restricting $\mathcal{X}$ to a sparse subset) is sufficient for
ensuring a restricted strong convexity type property of the Lasso solution.
This allows one to bound the $\ell_{2}$ norm of the Lasso solution.

Establishing the $\ell_{\infty}$ bound poses challenges since the leave-one-
method as outlined in [HS23] fails in the presence of dependence in the data.
Instead we use a novel leave-d-out method which essentially considers the
following optimization problem

$\hat{\varphi}^{(S)}=\operatornamewithlimits{arg\,min}_{\varphi\in\mathbb{R}^{p},\varphi_{S}=0}\frac{1}{2n}\|X\varphi-\xi\|^{2}+f(\varphi),$

where $S$ is a subset of $1,\ldots,p$ of cardinality $d$. A detailed analysis
together with our block dependence assumption then yields a suitable upper
bound on $\|\hat{\varphi}^{K}_{\mathcal{X},S}\|$, which in turn provides the
desired upper bound on $\|\hat{\varphi}^{K}_{\mathcal{X}}\|_{\infty}$. Such
leave-d-out arguments have been used in prior literature in [EK18, SC19,
SCC19] in other contexts, however, these works do not use this for
universality arguments. For convenience we will show a scaled version of
$\hat{\varphi}^{K}_{\mathcal{X}}$ (which we call
$\hat{\theta}^{K}_{\mathcal{X}}$ and is defined below) belongs to
$\mathcal{T}_{n}$ (see (7.1)), from which it easily follows that
$\hat{\varphi}^{K}_{\mathcal{X}}\in\mathcal{T}_{n}$. First we introduce some
notations.

Recall the empirical risk minimization problem

$\hat{R}_{n}(Y,\mathcal{X},\beta)=\frac{1}{2n}\sum_{i=1}^{n}\|Y_{i}-\mathcal{X}^{T}_{i}\beta\|^{2}+\lambda
f(\beta).$

Since $\mathcal{X}$ is of the form $X\Lambda^{1/2}$, we let
$\vartheta=\Lambda^{1/2}\beta$. Then the risk minimization problem can be
rewritten as

$\hat{R}_{n}(Y,X,\vartheta)=\frac{1}{2n}\sum_{i=1}^{n}\|Y_{i}-X^{T}_{i}\vartheta\|^{2}+\lambda
f(\Lambda^{-1/2}\vartheta).$

Since $\varphi=\beta-\beta_{0}$, we define $\theta=\vartheta-\vartheta_{0}$ so
that $\theta=\Lambda^{1/2}\varphi$. The new parametrization is concisely
presented in the following display

$\vartheta=\Lambda^{1/2}\beta,\quad,\vartheta_{0}=\Lambda^{1/2}\beta_{0},\quad\theta=\vartheta-\vartheta_{0},\quad\Lambda^{-1/2}=\tilde{\Omega}.$
(7.2)

For brevity, we will also denote the value of $\hat{R}_{n}(Y,X,\vartheta)$ on
using the variable $\theta$ as $R^{K}(X,\theta)$ (with K=L or R depending on
whether $\ell_{1}$ or $\ell_{2}$ penalty is used), where we have suppressed
the dependence on $\vartheta_{0}$ (and hence $Y$) and $n$. Finally, we define
the following optimizers

$\displaystyle\hat{\theta}^{R}_{X}$
$\displaystyle=\operatornamewithlimits{arg\,min}_{\theta\in\mathbb{R}^{p}}\frac{1}{2n}\|X\theta-\xi\|^{2}+\frac{\lambda}{2}\|\tilde{\Omega}(\theta+\vartheta_{0})\|^{2},$
$\displaystyle\hat{\theta}^{L}_{X}$
$\displaystyle=\operatornamewithlimits{arg\,min}_{\theta\in\mathbb{R}^{p}}\frac{1}{2n}\|X\theta-\xi\|^{2}+\frac{\lambda}{\sqrt{n}}\|\tilde{\Omega}(\theta+\vartheta_{0})\|_{1}.$

The following lemmas proved in the appendix show that the optimizers lie in
the set $\mathcal{T}_{n}$ with high probability.

######  Lemma 7.1.

Under Assumptions 1-3 we have

$\|\hat{\theta}^{K}_{X}\|_{2}\leq C$

with probability at least $1-n^{-c}$ for positive constants $c$ and $C$.

######  Lemma 7.2.

Under Assumptions 1-3 we have

$\|\hat{\theta}^{K}_{X}\|_{\infty}\leq C\sqrt{\frac{d\log n}{n}}$

with probability at least $1-n^{-c}$ for positive constants $c$ and $C$.

###  7.2 Universality of the optimum

We next describe our proof for the universality of the optimum that
corresponds to point (i) discussed in the beginning of Section 7. We may
divide this proof into three steps. The first step replaces the minimum over
the compact set with a minimum over a discrete set, and shows that the
approximation error goes to zero. The second step involves approximating the
minimization over the discrete set by a smoothed minimum, and showing once
again that the approximation error is negligible. The final step proves that
this smoothed minimum is universal, that is, its value is asymptotically the
same if the dependent design is replaced by an i.i.d. Gaussian design with
matching moments.

This proof strategy has been used in prior work (see [HS23, Theorem 2.3] or
[MS22a, Theorem 1]). The universality of the smoothed minimum is the crucial
step and depends heavily on the dependence/independence structure in the
underlying design matrix. It involves showing for any given set $S_{n}$ we
have

$\sup_{\theta\in\mathcal{T}_{n}\cap
S_{n}}|\mathop{\mathbf{E}}\left[\phi(X_{i}^{\top}\theta)\right]-\mathop{\mathbf{E}}\left[\phi(G_{i}^{\top}\theta)\right]|\rightarrow
0$ (7.3)

for a suitable choice of test function $\phi$, where $X_{i}$ is a row vector
from the block dependent design and $G_{i}$ is a row vector from the
independent Gaussian design. The arguments showing this step differs in our
case compared to prior work. To establish such a pointwise normality
condition, we use a version of Stein’s method that involves dependency graphs
together with the fact that the optimizer lies in the compact set
$\mathcal{T}_{n}$.

Heuristically the universality result holds because $X^{T}_{i}\hat{\beta}^{K}$
is a weighted sum of dependent sub-Gaussian random variables that converges to
a Gaussian random variable if the dependence is “low" in a suitable sense. It
can be easily observed that the weighted sum may fail to converge if the
weights are chosen arbitrarily, for example if
$\hat{\beta}^{K}=(1,0,\ldots,0)$, convergence to a Gaussian cannot be
expected. For this reason we require the coordinates of $\hat{\beta}^{K}$ to
be small enough, which justifies the $\ell_{\infty}$ bound proved in Lemma
7.2.

###### Proof of Theorem 4.1.

For this proof, we will assume that $\mathcal{S}_{n}$ is a subset of
$\mathcal{T}_{n}$, which we can assume without loss of generality.

Step 1: Discretization

Pick a $\delta$ net of the set $\mathcal{S}_{n}$ and call it $S_{n,\delta}$.
Let $\hat{\theta}=\operatornamewithlimits{arg\,min}_{\theta\in
S_{n}}R(\theta,X)$ and
$\tilde{\theta}=\operatornamewithlimits{arg\,min}_{\theta\in
S_{n,\delta}}R(\theta,X)$. For the purposes of this proof, we write
$\hat{\theta}^{K}_{X}$ as $\hat{\theta}$ and $R^{K}(\theta,X)$ as
$R(\theta,X)$ since the same proof works for both Lasso and ridge regression.
We observe the following chain of inequalities

$\displaystyle|\min_{\theta\in S_{n,\delta}}R(\theta,X)-\min_{\theta\in
S_{n}}R(\theta,X)|$ $\displaystyle\leq\min_{\theta\in
S_{n,\delta}}R(\theta,X)-\min_{\theta\in S_{n}}R(\theta,X)$ $\displaystyle\leq
R(\tilde{\theta},X)-R(\hat{\theta},X)$
$\displaystyle\leq|R(\tilde{\theta},X)-R(\hat{\theta},X)|$
$\displaystyle\leq|\frac{1}{2n}(\|X\tilde{\theta}-\xi\|^{2}-\|X\theta-\xi\|^{2}|+|f(\tilde{\theta})-f(\theta)|$
$\displaystyle\leq\frac{1}{2n}\|X(\bar{\theta}-\tilde{\theta})\|^{2}+\frac{1}{n}\left|(X\bar{\theta}-\xi)^{T}X(\tilde{\theta}-\hat{\theta})\right|+C_{1}\|\tilde{\Omega}(\tilde{\theta}-\hat{\theta})\|$
$\displaystyle\leq\frac{1}{2n}\|X(\bar{\theta}-\tilde{\theta})\|^{2}+\frac{1}{n}|(\|X\|\|\bar{\theta}\|+\|\xi\|)\|X\|\|\tilde{\theta}-\hat{\theta})\|+C\|\tilde{\theta}-\hat{\theta}\|.$

Noting that $\|X\|\leq C\sqrt{n}$ and $\|\xi\|\leq C\sqrt{n}$ with probability
at least $1-n^{-c}$ and $\max\\{\|\theta\|,\|\tilde{\theta}\|\\}\leq C$ (since
$\mathcal{S}_{n}$ and $S_{n,\delta}$ are subsets of $\mathcal{T}_{n}$) we
conclude that

$|\min_{\theta\in S_{n,\delta}}R(\theta,X)-\min_{\theta\in
S_{n}}R(\theta,X)|\leq C\delta$

with probability at least $1-n^{-c}$. For a bounded differentiable function
with bounded Lipschitz derivative we have

$|E[\psi(\min_{\theta\in S_{n,\delta}}R(\theta,X))]-E[\psi(\min_{\theta\in
S_{n}}R(\theta,X))]|\leq C\|\psi^{\prime}\|_{\infty}\delta.$ (7.4)

Step 2: Approximation by smoothed minimum

The smoothed minimum is defined as follows

$f_{\delta}(\alpha,X)=-\frac{1}{n\alpha}\log\sum_{\theta\in\mathcal{S}_{n,\delta}}\exp{(-n\alpha
R(\theta,X))}$

with the following approximation error (cf. [MS22a])

$|f_{\delta}(\alpha,X)-\min_{\theta\in S_{n,\delta}}R(\theta,X)|\leq
C(\delta)\alpha^{-1}.$

Again using a Lipschitz function as in (7.4), we obtain

$|E[\psi(f_{\delta}(\alpha,X))]-E[\psi(\min_{\theta\in
S_{n,\delta}}R(\theta,X)))]|\leq C\|\psi^{\prime}\|_{\infty}\alpha^{-1}.$
(7.5)

Step 3: Universality of the smoothed minimum

The universality of the smoothed minimum follows via the interpolation path as
shown in [MS22a]. In particular one defines matrices $U_{t}$ where the rows
are given by

$U_{t,i}=sin(t)X_{i}+cos(t)G_{i}$

and uses the relation

$|E(\psi(f_{\delta}(\alpha,X))-\psi(f_{\delta}(\alpha,G)))|=\left|E\int_{0}^{\pi/2}\frac{\partial}{\partial
t}(\psi(f_{\delta}(\alpha,U_{t}))\right|.$ (7.6)

It can be shown that $|E\frac{\partial}{\partial
t}(\psi(f_{\delta}(\alpha,U_{t}))|\rightarrow 0$ once the pointwise normality
condition (see (7.3)) is satisfied (see [MS22a, Lemma 4]), which we prove via
Stein’s method. Thus from (7.4), (7.5), and (7.6), we conclude that

$\lim_{n\rightarrow\infty}|E[\psi(\min_{\theta\in
S_{n}}R(\theta,X))]-E[\psi(\min_{\theta\in S_{n}}R(\theta,G))]|\rightarrow 0$

by suitably choosing $\delta\rightarrow 0$, $\alpha\rightarrow\infty$, and
$n\rightarrow\infty$, once we verify (7.3). To show the latter, recall that
$S_{n}$ can be assumed to a subset of $\mathcal{T}_{n}$ without loss of
generality and hence we aim to show

$\sup_{\theta\in
S_{n}}|\mathop{\mathbf{E}}\left[\phi(X_{i}^{\top}\theta)\right]-\mathop{\mathbf{E}}\left[\phi(G_{i}^{\top}\theta)\right]|\rightarrow
0.$

We use the following relation

$|\mathop{\mathbf{E}}\left[\phi(X_{i}^{\top}\theta)\right]-\mathop{\mathbf{E}}\left[\phi(G_{i}^{\top}\theta)\right]|=|\mathop{\mathbf{E}}\left[\phi(\nu
X_{i}^{\top}\theta/\nu)\right]-\mathop{\mathbf{E}}\left[\phi(\nu Z)\right]|,$

where $\nu^{2}=\|\theta\|^{2}$ and $Z\sim N(0,1)$. Define

$\psi(x)=e^{x^{2}/2}\int_{\infty}^{x}e^{-y^{2}/2}(\phi(\nu
y)-\mathop{\mathbf{E}}((\phi(\nu Z)))dy,$

which satisfies the Stein’s identity

$\psi^{\prime}(x)-x\psi(x)=\phi(\nu x)-\mathop{\mathbf{E}}(\nu Z),$

and if $\|\phi^{\prime}(x)\|_{\infty}\leq B,$ then

$\max\\{\psi(x),\psi^{\prime}(x),\psi^{\prime\prime}(x)\\}\leq 2\nu B\leq C,$
(7.7)

since $||\theta||\leq C_{1}$ (for some constant $C_{1}$) in our setting. Thus
it suffices to upper bound

$\mathop{\mathbf{E}}\left[\psi^{\prime}\left(\frac{X_{i}^{\top}\theta}{\nu}\right)-\frac{X_{i}^{\top}\theta}{\nu}\psi\left(\frac{X_{i}^{\top}\theta}{\nu}\right)\right].$

By using (7.7), the block dependent structure (Definition 2.1), and [Ros11,
Theorem 3.6] we have

$\mathop{\mathbf{E}}\left[\psi^{\prime}\left(\frac{X_{i}^{\top}\theta}{\nu}\right)-\frac{X_{i}^{\top}\theta}{\nu}\psi\left(\frac{X_{i}^{\top}\theta}{\nu}\right)\right]\leq\frac{Cd^{2}\varsigma_{3}}{\sigma^{3}}+\frac{Cd^{3/2}\sqrt{\varsigma_{4}}}{\sigma^{2}},$

with

$\varsigma_{3}=\frac{\max_{j}E|X_{ij}|^{3}\sum_{j=1}^{p}|\theta|_{j}^{3}}{\|\theta\|^{3}},\quad\text{
and
}\varsigma_{4}=\frac{\max_{j}E|X_{ij}|^{4}\sum_{j=1}^{p}|\theta|_{j}^{4}}{\|\theta\|^{4}}.$

Now suppose $\max_{j}|\theta_{j}|\leq\alpha_{n}$ and $\|\theta\|>\epsilon$,
then with $\varsigma=\max\\{\max_{j}E|x_{ij}|^{3},\max_{j}E|x_{ij}|^{4}\\}$ we
have

$\mathop{\mathbf{E}}\left[\psi^{\prime}\left(\frac{X_{i}^{\top}\theta}{\nu}\right)-\frac{X_{i}^{\top}\theta}{\nu}\psi\left(\frac{X_{i}^{\top}\theta}{\nu}\right)\right]\leq\frac{d^{2}\varsigma\alpha_{n}}{\epsilon}+\frac{d^{3/2}\sqrt{\varsigma}\alpha_{n}}{\epsilon}.$
(7.8)

Since $\theta\in S_{n}\subset\mathcal{T}_{n}$, $\alpha_{n}\rightarrow 0$ and
hence the RHS of (7.8) goes to $0$ as $n\rightarrow\infty$. On the other hand,
when $\|\theta\|<\epsilon$, we have

$|\mathop{\mathbf{E}}\left[\phi(X_{i}^{\top}\theta)\right]-\mathop{\mathbf{E}}\left[\phi(G_{i}^{\top}\theta)\right]|\leq\|\phi^{{}^{\prime}}\|_{\infty}(E(X_{i}^{\top}\theta)^{2})^{1/2}+(E(G_{i}^{\top}\theta)^{2})^{1/2}\leq
C_{1}\epsilon,$

for some $C_{1}$ since $\|\theta\|\leq C$ for $\theta\in\mathcal{T}_{n}$.
Letting $\epsilon$ go to $0$, we have

$\displaystyle\sup_{\theta\in
S_{n}}|\mathop{\mathbf{E}}\left[\phi(X_{i}^{\top}\theta)\right]-\mathop{\mathbf{E}}\left[\phi(G_{i}^{\top}\theta)\right]|$
$\displaystyle\leq$ $\displaystyle\sup_{\theta\in
S_{n}\cap\\{\|\theta\|\geq\epsilon}\\}|\mathop{\mathbf{E}}\left[\phi(X_{i}^{\top}\theta)\right]-\mathop{\mathbf{E}}\left[\phi(G_{i}^{\top}\theta)\right]|+\sup_{\theta\in
S_{n}\cap\\{\|\theta\|\leq\epsilon}\\}|\mathop{\mathbf{E}}\left[\phi(X_{i}^{\top}\theta)\right]-\mathop{\mathbf{E}}\left[\phi(G_{i}^{\top}\theta)\right]|\rightarrow
0$

as desired. ∎

Remark: Note that in the proof we only require $d^{2}\alpha_{n}$ converges to
$0$. So the result holds for growing $d$. In particular, $\alpha_{n}$ can be
chosen as $(d\log n/n)^{1/2}$ and the proof works as long as $d^{5}\log
n/n\rightarrow 0$.

###  7.3 Universality of the optimizer

We use the terms universality of the optimizer and universality of the
estimation risk interchangeably. This is because the proof of Theorem 4.2
shows the universality of the optimizer and an application of Theorem 4.2
gives Corollary 4.2, which deals with the universality of the estimation risk.

Our proof of this step builds upon [HS23]. The universality of the optimizer
is established in [HS23, Theorem 2.4] under two conditions (called (O1) and
(O2) in [HS23]) with the regression setup considered in [HS23, Theorem 3.1].
We note that condition (O1) mentioned in there is the same as the bound on the
$\ell_{\infty}$ norm of the optimizer, which we prove in Lemma 7.2 by our
leave-$d$-out method. Condition (O2) is the Gordon gap that states the
following: if there is a difference in the unrestricted optimum and the
optimum restricted to a particular set with high probability, then the
optimizer does not belong to that set with high probability. In other words,
for any pair of positive constants $\psi^{K}$ and $z$, the following holds

$\\{\inf_{\theta\in
R^{p}}R^{K}(\theta,G)\leq\psi^{K}+z\\}\cap\\{\inf_{\theta\in
S_{n}}R^{K}(\theta,G)\geq\psi^{K}+2z)\\}\subset\\{\hat{\theta}^{K}_{G}\in
S^{c}_{n}\\}.$ (7.9)

We observe that the statement above concerns independent Gaussian design only
i.e. we do not need to establish such a condition for the dependent sub-
Gaussian design matrix. Although it may seem nontrivial that the universality
of the optimizer follows from checking this condition for the Gaussian case,
we show that (see proof of Theorem 4.2) the Gordon gap coupled with Theorem
4.1 (which shows universality of the optimum value of the empirical risk for
all subsets of the nice compact set) readily yields the desired universality
of the optimizer. This proof strategy was also utilized in [HS23, MS22a].
Although our proof for the Gordon gap builds upon [HS23, Theorems 3.4, 3.8],
the scaling matrix $\Lambda$ calls for a far more nuanced analysis. In
particular, Lemma 7.3 below plays a critical role in the proof of Theorem 4.2.
The scaling factor introduces considerable challenges in establishing this
lemma. We overcome this by employing a nontrivial equicontinuity argument (see
Appendix A.3), a step not necessitated in the case of [HS23].

Let $\omega_{i}=\tilde{\Omega}_{ii}$ and $\mu_{0}=\sqrt{n}\vartheta_{0}$ where
$\tilde{\Omega}$ and $\vartheta$ are defined in (7.2). Recall the fixed point
solution $\beta^{K}_{*},\gamma^{K}_{*}$ of the equation (3.3) and define
$\theta_{*}^{K}=w_{*}^{K}/\sqrt{n}$ where

$w_{*,i}^{K}=\eta_{k}\left(\mu_{0,i}+\gamma^{K}_{*}g_{i},\frac{\gamma^{K}_{*}\lambda\omega_{i}^{k}}{\beta^{K}_{*}}\right)-\mu_{0,i}$

with $k=1$ for $K=R$ and $k=2$ for $K=L$. Let us define the set
$S_{n,\epsilon}$ as follows

$\mathcal{S}_{n,\epsilon}:=\\{\theta:|\varrho(\theta)-E(\varrho(\theta^{K}_{*}))|\geq\epsilon\\}.$

Henceforth we will omit the $\epsilon$ and call it $S_{n}$ since Theorem 4.2
is proved for a fixed $\epsilon$). We have the following lemma.

######  Lemma 7.3.

There exists positive constants $\psi^{R}$ and $\psi^{L}$ (denoted by
$\psi^{K}$ with $K=R$ for ridge and $K=L$ for Lasso) and $z$ such that the
following holds

$P\left(\inf_{\theta\in
R^{p}}R^{K}(\hat{\theta},G)\geq\psi^{K}+z\right)\leq\delta_{n}\quad
P\left(\inf_{\theta\in
S_{n}}R^{K}(\hat{\theta},G)\leq\psi^{K}+2z)\right)\leq\delta_{n}$

for some $\delta_{n}\rightarrow 0$.

Now we are ready to prove Theorem 4.2.

###### Proof of Theorem 4.2.

We start with formalizing the statement in (7.9). We have the following set of
inequalities for suitable choices of $\gamma_{n}$, $\delta_{n}$,
$\epsilon_{n}\rightarrow 0$.

$\displaystyle P(\hat{\theta}^{K}_{X}\in\mathcal{S}_{n})$ $\displaystyle\leq
P(\hat{\theta}^{K}_{X}\in\mathcal{S}_{n}\cap\mathcal{T}_{n})+\epsilon_{n}$
$\displaystyle\leq
P\left(\inf_{\theta\in\mathcal{T}_{n}}R^{K}(\theta,X)\geq\psi^{K}+3z\right)+P\left(\inf_{\theta\in\mathcal{S}_{n}\cap\mathcal{T}_{n}}R^{K}(\theta,X)\leq\psi^{K}+6z\right)+\epsilon_{n}$
$\displaystyle\leq
P\left(\inf_{\theta\in\mathcal{T}_{n}}R^{K}(\theta,G)\geq\psi^{K}+z\right)+P\left(\inf_{\theta\in\mathcal{S}_{n}\cap\mathcal{T}_{n}}R^{K}(\theta,G)\leq\psi^{K}+2z\right)+\epsilon_{n}+2\gamma_{n}$
$\displaystyle\leq
P\left(\inf_{\theta}R^{K}(\theta,G)\geq\psi^{K}+z\right)+P\left(\inf_{\theta\in\mathcal{S}_{n}}R^{K}(\theta,G)\leq\psi^{K}+2z\right)+3\epsilon_{n}+2\gamma_{n}$
$\displaystyle\leq 2\delta_{n}+3\epsilon_{n}+2\gamma_{n}.$

We note that the first and fourth inequality follows from Lemmas 7.1 and 7.2.
The second inequality follows from the following inclusion

$\\{\inf_{\theta\in\mathcal{T}_{n}}R^{K}(\theta,X)\leq\psi^{K}+3z\\}\cap\\{\inf_{\theta\in\mathcal{S}_{n}\cap\mathcal{T}_{n}}R^{K}(\theta,X)\geq\psi^{K}+6z\\}\subset\\{\hat{\theta}^{K}_{X}\in(\mathcal{S}_{n}\cap\mathcal{T}_{n})^{c}\\}.$

The third inequality follows from Theorem 4.1 with a suitable choice of test
function, while the last inequality follows from Lemma 7.3. Next we use (7.2)
to obtain our statements with the old parameters. For $\varphi$, we use the
fact that $\varphi=\tilde{\Omega}\theta$ and $\theta=w/\sqrt{n}$ to obtain

$\varphi^{K}_{*}=\tilde{\Omega}\frac{w_{*}^{K}}{\sqrt{n}}$

so that

$\displaystyle\varphi^{R}_{*,i}$
$\displaystyle=\eta_{2}\left(\beta_{0,i}+\frac{\gamma^{R}_{*}\omega_{i}g_{i}}{\sqrt{n}},\frac{\gamma^{R}_{*}\lambda\omega_{i}^{2}}{\beta^{R}_{*}}\right)-\beta_{0,i}$
(7.10) $\displaystyle\varphi^{L}_{*,i}$
$\displaystyle=\eta_{1}\left(\beta_{0,i}+\frac{\gamma^{L}_{*}\omega_{i}g_{i}}{\sqrt{n}},\frac{\gamma^{L}_{*}\lambda\omega_{i}^{2}}{\sqrt{n}\beta^{L}_{*}}\right)-\beta_{0,i},$
(7.11)

where we have used the fact that

$\eta_{1}(\alpha
x,\alpha\lambda)=\alpha\eta_{1}(x,\lambda),\quad\eta_{2}(\alpha
x,\lambda)=\alpha\eta_{2}(x,\lambda).$

Since $\hat{\varphi}^{K}_{X}=\tilde{\Omega}\hat{\theta}^{K}_{X}$, where the
entries of $\tilde{\Omega}$ are bounded, we can easily redefine $\varrho$ so
that

$P(|\varrho(\hat{\varphi}^{K}_{X})-E(\varrho(\varphi^{K}_{*}))|\geq\epsilon)\leq
2\delta_{n}+2\epsilon_{n}+3\gamma_{n}.$ (7.12)

Now we observe that although the above result is proved for dependent
subGaussian designs, the latter subsumes the case of independent Gaussian
design and hence it trivially follows that

$P(|\varrho(\hat{\varphi}^{K}_{G})-E(\varrho(\varphi^{K}_{*}))|\geq\epsilon)\leq
2\delta_{n}+3\epsilon_{n}+2\gamma_{n}.$ (7.13)

Combining (7.12) and (7.13), we obtain that

$P(|\varrho(\hat{\varphi}^{K}_{X})-\varrho(\hat{\varphi}^{K}_{G})|\geq
2\epsilon)\leq 4\delta_{n}+6\epsilon_{n}+4\gamma_{n}.$

Defining $4\delta_{n}+6\epsilon_{n}+4\gamma_{n}$ as $\varepsilon_{n}$ and
replacing $2\epsilon$ by $\epsilon$ we observe that the desired claim is
proved. ∎

We now have all ingredients in place for the proof of Corollary 4.2.

###### Proof of Corollary 4.2.

Choose $\varrho$ as the function $\|.\|^{2}$. Although this function is not
Lipshitz in the entire domain $\mathbb{R}^{p}$ it is Lipshitz in the bounded
domain $\\{\varphi:\|\varphi\|\leq C\\}$. Since our optimizers have bounded
$\ell_{2}$ norm with probability at least $1-n^{-c}$, we work in the domain
$\\{\varphi:\|\varphi\|\leq C\\}$ for our purposes and use Theorem 4.2 to
conclude

$\displaystyle\|\hat{\varphi}^{R}_{X}\|^{2}-E_{\bar{Q}_{n}}\left[\eta_{2}\left(M+\frac{\gamma^{R}_{*}\Omega
Z}{\sqrt{n}},\frac{\gamma^{R}_{*}\lambda\Omega^{2}}{\beta^{R}_{*}}\right)-M\right]^{2}$
$\displaystyle\xrightarrow{P}0,$
$\displaystyle\|\hat{\varphi}^{L}_{X}\|^{2}-E_{\bar{Q}_{n}}\left[\eta_{1}\left(M+\frac{\gamma^{L}_{*}\Omega
Z}{\sqrt{n}},\frac{\gamma^{L}_{*}\lambda\Omega^{2}}{\sqrt{n}\beta^{L}_{*}}\right)-M\right]^{2}$
$\displaystyle\xrightarrow{P}0.$

Substituting $\hat{\varphi}^{K}_{X}=\hat{\beta}^{K}_{X}-\beta_{0}$, we
conclude our proof. ∎

##  8 Discussion

In this paper, we established universality results within the framework of
empirical risk minimization, demonstrating that the optimal value of the
regularized empirical risk and estimation risk of regularized estimators
converge to the same value for block dependent sub-Gaussian designs, as in the
case of i.i.d. Gaussian designs. In sum, to the best of the authors’
knowledge, our paper is the first in the literature that handles dependence
structures beyond correlation-based dependence or those allowed by right
rotationally invariant designs. Our examples from Section 2 demonstrate the
importance of studying such general dependencies, providing the first segue
into nonparametric problems. Notably, this allows us to characterize the
(asymptotically) exact risk of estimators for popular non-parametric
regression models under high-dimensional covariates. We conclude our
manuscript with a couple of directions for future work.

First, our results do not account for dependence captured by an explicit
covariance matrix. A logical extension of our work would involve proving
dependence when feature vectors take the form $\Sigma^{1/2}Z_{i}$. Here,
instead of $Z_{i}$ being a random vector with independent sub-Gaussian
entries, as considered in [MS22a], $Z_{i}$ is isotropic, and block dependent
sub-Gaussian vectors. We conjecture that under some regularity assumptions on
the covariance matrix $\Sigma$, the optimal value of the risk and the risk of
regularized estimators should be asymptotically the same as that of the design
with rows of the form $\Sigma^{1/2}G_{i}$ where the entries of $G_{i}$ are
i.i.d. Gaussian. While proving universality of the optimum in this scenario
aligns with the approach in [MS22a], generalizing our leave-d-out method in
presence of a general $\Sigma$ and subsequently proving universality of the
optimizer presents nontrivial challenges, which we defer to future work.

Second, an intriguing avenue involves considering a more general dependence
pattern, where each entry of the feature vector depends on only a small number
of other entries, without a block structure. Currently, the block structure is
pivotal in our proofs of $\ell_{\infty}$ bounds via our leave-d-out method. We
view our current contribution as a stepping stone towards investigating these
other notions of dependence. The absence of the block structure implies a
stronger form of dependence, necessitating new tools. We defer this to future
investigation.

##  9 Acknowledgements

The authors would like to thank Nabarun Deb, Rounak Dey, and Subhabrata Sen
for helpful discussions at various stages of the manuscript. P.S. would like
to acknowledge partial funding from NSF DMS-2113426.

## References

  * [ABKZ20] Alia Abbara, Antoine Baker, Florent Krzakala, and Lenka Zdeborová.  On the universality of noiseless linear estimation with respect to the measurement matrix.  Journal of Physics A: Mathematical and Theoretical, 53(16):164001, 2020.
  * [ASH19] Ehsan Abbasi, Fariborz Salehi, and Babak Hassibi.  Universality in learning from linear measurements.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
  * [BBKY13] Derek Bean, Peter J. Bickel, Noureddine El Karoui, and Bin Yu.  Optimal m-estimation in high-dimensional regression.  Proceedings of the National Academy of Sciences, 110(36):14563–14568, 2013.
  * [BKM+19] Jean Barbier, Florent Krzakala, Nicolas Macris, Léo Miolane, and Lenka Zdeborová.  Optimal errors and phase transitions in high-dimensional generalized linear models.  Proceedings of the National Academy of Sciences, 116(12):5451–5460, 2019.
  * [BLM15] Mohsen Bayati, Marc Lelarge, and Andrea Montanari.  Universality in polytope phase transitions and message passing algorithms.  The Annals of Applied Probability, 25(2):753 – 822, 2015.
  * [BM11] Mohsen Bayati and Andrea Montanari.  The dynamics of message passing on dense graphs, with applications to compressed sensing.  IEEE Transactions on Information Theory, 57(2):764–785, 2011.
  * [BM12] Mohsen Bayati and Andrea Montanari.  The lasso risk for gaussian matrices.  IEEE Transactions on Information Theory, 58(4):1997–2017, 2012\.
  * [BRT09] Peter J. Bickel, Ya’acov Ritov, and Alexandre B. Tsybakov.  Simultaneous analysis of Lasso and Dantzig selector.  The Annals of Statistics, 37(4):1705 – 1732, 2009.
  * [CCFM21] Yuxin Chen, Yuejie Chi, Jianqing Fan, and Cong Ma.  Spectral methods for data science: A statistical perspective.  Foundations and Trends® in Machine Learning, 14(5):566–806, 2021.
  * [Cha06] Sourav Chatterjee.  A generalization of the Lindeberg principle.  The Annals of Probability, 34(6):2061 – 2076, 2006.
  * [CL21] Wei-Kuo Chen and Wai-Kit Lam.  Universality of approximate message passing algorithms.  Electronic Journal of Probability, 26(none):1 – 44, 2021.
  * [CS20] Emmanuel J. Candès and Pragya Sur.  The phase transition for the existence of the maximum likelihood estimate in high-dimensional logistic regression.  The Annals of Statistics, 48(1):27 – 42, 2020.
  * [DKT22] Zeyu Deng, Abla Kammoun, and Christos Thrampoulidis.  A model of double descent for high-dimensional binary linear classification.  Information and Inference: A Journal of the IMA, 11(2):435–495, 2022.
  * [DLS23] Rishabh Dudeja, Yue M. Lu, and Subhabrata Sen.  Universality of approximate message passing with semi-random matrices, 2023.
  * [DM16] David Donoho and Andrea Montanari.  High dimensional robust m-estimation: Asymptotic variance via approximate message passing.  Probability Theory and Related Fields, 166:935–969, 2016.
  * [DMM09] David L. Donoho, Arian Maleki, and Andrea Montanari.  Message-passing algorithms for compressed sensing.  Proceedings of the National Academy of Sciences, 106(45):18914–18919, 2009.
  * [DSL23] Rishabh Dudeja, Subhabrata Sen, and Yue M. Lu.  Spectral universality of regularized linear regression with nearly deterministic sensing matrices, 2023.
  * [DT09] David Donoho and Jared Tanner.  Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing.  Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 367(1906):4273–4293, 2009.
  * [EK18] Noureddine El Karoui.  On the impact of predictor geometry on the performance on high-dimensional ridge-regularized generalized robust regression estimators.  Probability Theory and Related Fields, 70:95–175, 2018.
  * [Erd11] Laszlo Erdős.  Universality of wigner random matrices: a survey of recent results.  Russian Mathematical Surveys, 66(3):507, jun 2011.
  * [ESY09] László Erdős, Benjamin Schlein, and Horng-Tzer Yau.  Local semicircle law and complete delocalization for wigner random matrices.  Communications in Mathematical Physics, 287(2):641–655, 2009.
  * [FVRS22] Oliver Y. Feng, Ramji Venkataramanan, Cynthia Rush, and Richard J. Samworth.  A unifying tutorial on approximate message passing.  Foundations and Trends in Machine Learning, 2022.
  * [GBC+11] Jeff Goldsmith, Jennifer Bobb, Ciprian M. Crainiceanu, Brian Caffo, and Daniel Reich.  Penalized functional regression.  Journal of Computational and Graphical Statistics, 20(4):830–851, 2011.  PMID: 22368438.
  * [GD12] Simianer H. Gianola D, Manfredi E.  On measures of association among genetic variables.  Anim Genet., 43, 2012.
  * [GKL+22] Federica Gerace, Florent Krzakala, Bruno Loureiro, Ludovic Stephan, and Lenka Zdeborová.  Gaussian universality of linear classifiers with random labels in high-dimension.  arXiv preprint arXiv:2205.13303, 2022.
  * [HL22] Hong Hu and Yue M Lu.  Universality laws for high-dimensional learning with random features.  IEEE Transactions on Information Theory, 69(3):1932–1964, 2022\.
  * [HRM22] Gillian Z. Heller, Kristy P. Robledo, and Ian C. Marschner.  Distributional regression in clinical trials: treatment effects on parameters other than the mean.  BMC Medical Research Methodology, 2022.
  * [HS23] Qiyang Han and Yandi Shen.  Universality of regularized regression estimators in high dimensions.  The Annals of Statistics, 51(4):1799–1823, 2023.
  * [HX23] Qiyang Han and Xiaocong Xu.  The distribution of ridgeless least squares interpolators.  arXiv preprint arXiv:2307.02044, 2023.
  * [JM13] Adel Javanmard and Andrea Montanari.  State evolution for general approximate message passing algorithms, with applications to spatial coupling.  Information and Inference: A Journal of the IMA, 2(2):115–144, 2013\.
  * [JMSS22] Kuanhao Jiang, Rajarshi Mukherjee, Subhabrata Sen, and Pragya Sur.  A new central limit theorem for the augmented ipw estimator: Variance inflation, cross-fit covariance and beyond.  arXiv preprint arXiv:2205.10198, 2022.
  * [KBB+13] Noureddine El Karoui, Derek Bean, Peter J. Bickel, Chinghway Lim, and Bin Yu.  On robust regression with high-dimensional predictors.  Proceedings of the National Academy of Sciences, 110(36):14557–14562, 2013.
  * [KM11] Satish Babu Korada and Andrea Montanari.  Applications of the lindeberg principle in communications and statistical learning.  IEEE Transactions on Information Theory, 57(4):2440–2450, 2011\.
  * [KM14] Vladimir Koltchinskii and Stanislav Minsker.  $l_{1}$-penalization in functional linear regression with subgaussian design.  Journal de l’École polytechnique — Mathématiques, 1:269–330, 2014.
  * [KY10] Vladimir Koltchinskii and Ming Yuan.  Sparsity in multiple kernel learning.  The Annals of Statistics, 38(6):3660 – 3695, 2010.
  * [Lew88] Richard Lewontin.  On measures of gametic disequilibrium.  Genetics, 120(3), 1988.
  * [LFW23] Gen Li, Wei Fan, and Yuting Wei.  Approximate message passing from random initialization with applications to $\mathbb{Z}_{2}$ synchronization.  Proceedings of the National Academy of Sciences, 120(31):e2302930120, 2023.
  * [LS22] Tengyuan Liang and Pragya Sur.  A precise high-dimensional asymptotic theory for boosting and minimum-$\ell_{1}$-norm interpolated classifiers.  The Annals of Statistics, 50(3):1669–1695, 2022.
  * [LS23] Yufan Li and Pragya Sur.  Spectrum-aware adjustment: A new debiasing framework with applications to principal components regression.  arXiv preprint arXiv:2309.07810, 2023.
  * [LSS23] Tengyuan Liang, Subhabrata Sen, and Pragya Sur.  High-dimensional asymptotics of Langevin dynamics in spiked matrix models.  Information and Inference: A Journal of the IMA, 12(4):2720–2752, 10 2023.
  * [MJG+13] Hatef Monajemi, Sina Jafarpour, Matan Gavish, Stat 330/CME 362 Collaboration, David L Donoho, Sivaram Ambikasaran, Sergio Bacallado, Dinesh Bharadia, Yuxin Chen, Young Choi, et al.  Deterministic matrices matching the compressed sensing phase transitions of gaussian random matrices.  Proceedings of the National Academy of Sciences, 110(4):1181–1186, 2013.
  * [MM09] Marc Mezard and Andrea Montanari.  Information, physics, and computation.  Oxford University Press, 2009.
  * [MM21] Léo Miolane and Andrea Montanari.  The distribution of the Lasso: Uniform control over sparse balls and adaptive parameter tuning.  The Annals of Statistics, 49(4):2313 – 2335, 2021.
  * [MMD+21] Guillermo S. Marcillo, Nicolas F. Martin, Brian W. Diers, Michelle Da Fonseca Santos, Erica Pontes Leles, Godfree Chigeza, and Josy H. Francischini.  Implementation of a generalized additive model (gam) for soybean maturity prediction in african environments.  Agronomy, 11(6), 2021.
  * [MN17] Andrea Montanari and Phan-Minh Nguyen.  Universality of the elastic net error.  In 2017 IEEE International Symposium on Information Theory (ISIT), pages 2338–2342, 2017.
  * [Mor15] Jeffrey S. Morris.  Functional regression.  Annual Review of Statistics and Its Application, 2(1):321–359, 2015\.
  * [MP67] Vladimir Alexandrovich Marchenko and Leonid Andreevich Pastur.  Distribution of eigenvalues for some sets of random matrices.  Matematicheskii Sbornik, 114(4):507–536, 1967.
  * [MPV87] Marc Mézard, Giorgio Parisi, and Miguel Angel Virasoro.  Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications, volume 9.  World Scientific Publishing Company, 1987.
  * [MRSS23] Andrea Montanari, Feng Ruan, Basil Saeed, and Youngtak Sohn.  Universality of max-margin classifiers.  arXiv preprint arXiv:2310.00176, 2023.
  * [MRSY19] Andrea Montanari, Feng Ruan, Youngtak Sohn, and Jun Yan.  The generalization error of max-margin linear classifiers: High-dimensional asymptotics in the overparametrized regime.  arXiv preprint arXiv:1911.01544, 2019.
  * [MS22a] Andrea Montanari and Basil N. Saeed.  Universality of empirical risk minimization.  In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 4310–4312. PMLR, 02–05 Jul 2022.
  * [MS22b] Andrea Montanari and Subhabrata Sen.  A short tutorial on mean-field spin glass techniques for non-physicists.  arXiv preprint arXiv:2204.02909, 2022.
  * [MTM22] Ariel I. Mundo, John R. Tipton, and Timothy J. Muldoon.  Generalized additive models to analyze nonlinear trends in biomedical longitudinal data using r: Beyond repeated measures anova and linear mixed models.  Statistics in Medicine, 41(21):4266–4283, 2022.
  * [MV21] Marco Mondelli and Ramji Venkataramanan.  Approximate message passing with spectral initialization for generalized linear models.  In International Conference on Artificial Intelligence and Statistics, pages 397–405. PMLR, 2021.
  * [MvdGB09] Lukas Meier, Sara van de Geer, and Peter Bühlmann.  High-dimensional additive modeling.  The Annals of Statistics, 37(6B):3779 – 3821, 2009.
  * [NRWY12] Sahand N Negahban, Pradeep Ravikumar, Martin J Wainwright, and Bin Yu.  A unified framework for high-dimensional analysis of m-estimators with decomposable regularizers.  2012\.
  * [OT17] Samet Oymak and Joel A Tropp.  Universality laws for randomized dimension reduction, with applications.  Information and Inference: A Journal of the IMA, 7(3):337–446, 11 2017.
  * [OTH13] Samet Oymak, Christos Thrampoulidis, and Babak Hassibi.  The squared-error of generalized lasso: A precise analysis.  In 2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1002–1009, 2013.
  * [PH17] Ashkan Panahi and Babak Hassibi.  A universal analysis of large-scale regularized least squares solutions.  Advances in Neural Information Processing Systems, 30, 2017.
  * [PIFP08] Cristian Pattaro, Ruczinski Ingo, Daniele Fallin, and Giovanni Parmigiani.  Haplotype block partitioning as a tool for dimensionality reduction in SNP association studies.  BMC Genomics, 9(1), 2008.
  * [Ran11] Sundeep Rangan.  Generalized approximate message passing for estimation with random linear mixing.  In 2011 IEEE International Symposium on Information Theory Proceedings, pages 2168–2172. IEEE, 2011.
  * [RGSO17] Philip T. Reiss, Jeff Goldsmith, Han Lin Shang, and R. Todd Ogden.  Methods for scalar-on-function regression.  Int Stat Rev., 2017.
  * [RJWY12] Garvesh Raskutti, Martin J Wainwright, and Bin Yu.  Minimax-optimal rates for sparse additive models over kernel classes via convex programming.  Journal of machine learning research, 13(2), 2012.
  * [Ros11] Nathan Ross.  Fundamentals of Stein’s method.  Probability Surveys, 8(none):210 – 293, 2011.
  * [RRMA19] Khaiwal Ravindra, Preety Rattan, Suman Mor, and Ashutosh Nath Aggarwal.  Generalized additive models: Building evidence of air pollution, climate change and human health.  Environment International, 132:104987, 2019.
  * [SBC+] Matteo Sesia, Stephen Bates, Emmanuel Candès, Jonathan Marchini, and Chiara Sabatti.  False discovery rate control in genome-wide association studies with population structure.  Proceedings of the National Academy of Sciences of the United States of America.
  * [SC18] Pragya Sur and Emmanuel J. Candès.  Supporting information to: a modern maximum-likelihood theory for high-dimensional logistic regression.  Proceedings of the National Academy of Sciences, 2018.
  * [SC19] Pragya Sur and Emmanuel J. Candès.  A modern maximum-likelihood theory for high-dimensional logistic regression.  Proceedings of the National Academy of Sciences, 116(29):14516–14525, 2019.
  * [SCC19] Pragya Sur, Yuxin Chen, and Emmanuel J Candes.  The likelihood ratio test in high-dimensional logistic regression is asymptotically a rescaled chi-square.  Probability Theory and Related Fields, 175:487–558, 2019.
  * [SSC18] M Sesia, C Sabatti, and E J Candès.  Gene hunting with hidden Markov model knockoffs.  Biometrika, 106(1):1–18, 08 2018.
  * [Sto85] Charles J. Stone.  Additive Regression and Other Nonparametric Models.  The Annals of Statistics, 13(2):689 – 705, 1985.
  * [Sto13a] Mihailo Stojnic.  A framework to characterize performance of lasso algorithms.  arXiv preprint arXiv:1303.7291, 2013.
  * [Sto13b] Mihailo Stojnic.  Meshes that trap random subspaces.  arXiv preprint arXiv:1304.0003, 2013.
  * [Sto13c] Mihailo Stojnic.  Upper-bounding $\ell_{1}$-optimization weak thresholds.  arXiv preprint arXiv:1303.7289, 2013.
  * [TAH18] Christos Thrampoulidis, Ehsan Abbasi, and Babak Hassibi.  Precise error analysis of regularized $m$ -estimators in high dimensions.  IEEE Transactions on Information Theory, 64(8):5592–5628, 2018\.
  * [Tal03] Michel Talagrand.  Spin glasses: a challenge for mathematicians: cavity and mean field models, volume 46.  Springer Science & Business Media, 2003.
  * [TOH15] Christos Thrampoulidis, Samet Oymak, and Babak Hassibi.  Regularized linear regression: A precise analysis of the estimation error.  In Peter Grünwald, Elad Hazan, and Satyen Kale, editors, Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pages 1683–1709, Paris, France, 03–06 Jul 2015. PMLR.
  * [Tsy09] Alexandre B. Tsybakov.  Introduction to Nonparametric Estimation.  Springer Series in Statistics. Springer, New York, 2009.  Revised and extended from the 2004 French original, Translated by Vladimir Zaiats.
  * [TV14] Terence Tao and Van Vu.  Random matrices: the universality phenomenon for wigner ensembles.  Modern aspects of random matrix theory, 72:121–172, 2014.
  * [TZ19] Zhiqiang Tan and Cun-Hui Zhang.  Doubly penalized estimation in additive regression with high-dimensional data.  The Annals of Statistics, 47(5):2567 – 2600, 2019.
  * [Ver12] Roman Vershynin.  Introduction to the non-asymptotic analysis of random matrices, page 210–268.  Cambridge University Press, 2012.
  * [WWM20] Shuaiwen Wang, Haolei Weng, and Arian Maleki.  Which bridge estimator is the best for variable selection?  The Annals of Statistics, 48(5):2791 – 2823, 2020.
  * [WZF22] Tianhao Wang, Xinyi Zhong, and Zhou Fan.  Universality of approximate message passing algorithms and tensor networks.  arXiv preprint arXiv:2206.13037, 2022.
  * [YZ16] Ming Yuan and Ding-Xuan Zhou.  Minimax optimal rates of estimation in high dimensional additive models.  The Annals of Statistics, 44(6):2564 – 2593, 2016.
  * [ZK16] Lenka Zdeborová and Florent Krzakala.  Statistical physics of inference: thresholds and algorithms.  Advances in Physics, 65(5):453–552, 2016.
  * [ZSC22] Qian Zhao, Pragya Sur, and Emmanuel J. Candès.  The asymptotic distribution of the MLE in high-dimensional logistic models: Arbitrary covariance.  Bernoulli, 28(3):1835 – 1861, 2022.

.

##  Appendix A Proof of the Lemmas

First we state a concentration result which will be used in proving the
theorems.

###  A.1 Concentration result

######  Lemma A.1.

Let $X$ be an $n\times p$ matrix whose rows $X_{i}$ are independent sub-
Gaussian isotropic random vectors in $\mathbb{R}^{n}$. Then for every $t\geq
0$, with probability at least $1-2\exp(-c_{K}t^{2})$ one has

$\sqrt{n}-C_{K}\sqrt{p}-t\leq s_{\min}(X)\leq
s_{\max}(X)\leq\sqrt{n}+C_{K}\sqrt{p}+t,$ (A.1)

where $s_{\min}(X)$ and $s_{\max}(X)$ are the smallest and largest singular
values of the matrix $X$. The constant s $C_{K},c_{K}$ depend only on the sub-
Gaussian norm $K=\max_{i}\|X_{i}\|_{\psi_{2}}$ of the rows.

###### Proof.

See [Ver12]. ∎

###  A.2 Bounds on the optimizers

Throughout this section we will work with Assumptions 1 and 3. Further we use
the following modified assumption instead of 2 to account for change in scale
(see (7.2))

######  Assumption 4.

The signal satisfies the bound $\|\vartheta_{0}\|\leq C$. Let
$v_{i}=\sqrt{n}\vartheta_{0,i}$ for $1\leq i\leq p$. Then we assume that

$\frac{1}{p}\sum_{i=1}^{p}\delta_{\lambda_{i},v_{i}}\xRightarrow{W_{2}}\mu.$

Further we assume that $\|v\|_{\infty}\leq C$.

###### Proof of lemma 7.1.

Recall that we work under the proportional asymptotic setup i.e.
$\lim_{n\rightarrow\infty}p/n=\kappa$. For the sake of clarity we will first
deal with the setup with $\kappa^{-1}>C_{0}>C_{K}$ for some $C_{0}$ where
$C_{K}$ is the constant appearing in Lemma A.1. We will later show that in the
general setup similar bounds can be achieved by suitably modifying the tuning
parameter $\lambda$.

Case 1: $n/p\rightarrow\kappa^{-1}>C_{0}>C_{K}^{2}$

Ridge regression

Recall that $\tilde{\Omega}=\Lambda^{-1/2}$. By the optimality of
$\hat{\theta}_{X}^{R}$, it easily follows that

$\frac{1}{2}\|X\hat{\theta}_{X}^{R}-\xi\|^{2}+\frac{n\lambda}{2}\|\tilde{\Omega}(\hat{\theta}_{X}^{R}+\vartheta_{0})\|^{2}\leq\frac{1}{2}\|\xi\|^{2}+\frac{n\lambda}{2}\|\tilde{\Omega}\vartheta_{0}\|^{2},$

whence $\|X\hat{\theta}^{R}_{X}\|^{2}\leq
C(\frac{1}{2}\|\xi\|^{2}+\frac{n\lambda}{2}\|\tilde{\Omega}\vartheta_{0}\|^{2})$.

Using a lower bound on the singular value of $X$ from Lemma A.1 we observe
that the left-hand side of the last inequality is lower bounded by
$cn\|\hat{\theta}^{R}_{X}\|^{2}$ with probability at least $1-n^{-c}$ by
choosing $t=c_{1}\sqrt{\log n}$ (for suitable choice of $c_{1}$). Similarly
using $E[\|\xi\|^{2}]\leq Cn$ and sub-Gaussian concentration inequality for
the random vector $\xi$ we easily conclude that $\|\hat{\theta}^{R}_{X}\|\leq
C$ with probability at least $1-n^{-c}$. Note that we have used
$\|\vartheta_{0}\|^{2}\leq C$ and that $\tilde{\Omega}$ is a diagonal matrix
with bounded entries.

Lasso

We have an analogous bound for Lasso penalty. Indeed, similar to the above
argument we obtain

$\|X\hat{\theta}^{L}_{X}\|^{2}\leq
C\left(\frac{1}{2}\|\xi\|^{2}+\frac{n\lambda}{\sqrt{n}}\|\tilde{\Omega}\vartheta_{0}\|_{1}\right).$

Since entries of $\tilde{\Omega}$ are bounded by some constant $C$ and
$\|\vartheta_{0}\|\leq C$, we get $\|\tilde{\Omega}\vartheta\|_{1}\leq
C\sqrt{p}\|\vartheta_{0}\|\leq C\sqrt{p}$. Using the fact that $\|\xi\|\leq
C\sqrt{n}$ with probability at least $1-n^{-c}$ we obtain
$\|X\hat{\theta}^{L}_{X}\|^{2}\leq Cn$ (we have used that $(p/n)^{1/2}\leq C$)
with probability at least $1-n^{-c}$. A lower bound on the singular value of
$X$ from Lemma A.1 then yields $\|\hat{\theta}^{L}_{X}\|\leq C.$

Case 2: $n/p\rightarrow\kappa^{-1}\leq C^{2}_{K}$

Ridge regression

This is a relatively simpler case since we can directly analyze the closed
form expression of the ridge estimator and use strong convexity. Indeed for
the ridge estimator $\hat{\vartheta}_{X}^{R}$, we have

$\|\hat{\vartheta}_{X}^{R}\|=\|(X^{T}X+n\lambda\tilde{\Omega}^{2})^{-1}(X^{T}X\vartheta_{0}+X^{T}\xi)\|\leq(n\lambda
c)^{-1}(\|X^{T}X\|\|\vartheta_{0}\|+\|X^{T}\|\|\xi\|).$

By lemma A.1 we can upper bound $\|X^{T}X\|$ and $\|X\|$ by $n$ and $\sqrt{n}$
respectively. Since $\|\vartheta_{0}\|$ is bounded by a constant and
$\|\xi\|\leq C\sqrt{n}$ with probability at least $1-n^{-c}$ we obtain
$\|\hat{\vartheta}_{X}^{R}\|\leq C$ with probability at least $1-n^{-c}$ which
in turn implies $\|\hat{\theta}_{X}^{R}\|\leq C$ with probability at least
$1-n^{-c}$.

Lasso

This case is more difficult because when the condition
$n/p\rightarrow\kappa^{-1}>C^{2}_{K}$ is not satisfied, the bound on the
smallest singular value (see Lemma A.1) does not work. In fact, for $p>n$ the
smallest singular value is zero. However, we can follow the idea outlined in
[HS23] \- ensuring that $\lambda$ is larger than a certain value one can
ensure that the optimizer is sparse with the number of nonzero components a
small fraction of $n$. Restricting ourselves to such a set $S$, it is then
enough to give a lower bound for the smallest singular value of $X_{S}$.

The following lemma shows that for large enough $\lambda$ the optimizer is
sparse.

######  Lemma A.2.

For any $c_{0}<1$ There exist a $\lambda_{0}$ which depends on $c_{0}$, such
that for $\lambda\geq\lambda_{0}$,the solution $\hat{\theta}^{L}_{X}$ is
$(c_{0}n)$ sparse with probability at least $1-n^{c(\lambda,c_{0})}$ where
$c(\lambda,c_{0})$ is a constant depending on $c_{0}$ and the tuning parameter
$\lambda$.

We defer the proof of this lemma for the moment. Now we can easily derive the
$\ell_{2}$ bound for the Lasso case. By the optimality of
$\hat{\theta}^{L}_{X}$, it easily follows that

$\frac{1}{2}\|X\hat{\theta}_{X}^{L}-\xi\|^{2}+\frac{\sqrt{n}\lambda}{2}\|\tilde{\Omega}(\hat{\theta}_{X}^{L}+\vartheta_{0})\|_{1}\leq\frac{1}{2}\|\xi\|^{2}+\frac{\sqrt{n}\lambda}{2}\|\tilde{\Omega}\vartheta_{0}\|_{1}.$

We can rewrite the inequality using $\vartheta$ instead of $\theta$ as
follows:

$\frac{1}{2}\|X\hat{\vartheta}^{L}_{X}-Y\|^{2}+\frac{\sqrt{n}\lambda}{2}\|\tilde{\Omega}\hat{\vartheta}^{L}_{X}\|_{1}\leq\frac{1}{2}\|\xi\|^{2}+\frac{\sqrt{n}\lambda}{2}\|\tilde{\Omega}\vartheta_{0}\|_{1}.$

Rearranging the terms it is not difficult to observe that

$\frac{1}{2}\|X\hat{\vartheta}^{L}_{X}\|^{2}\leq
C\left(\frac{1}{2}\|\xi\|^{2}+\frac{\sqrt{n}\lambda}{2}\|\tilde{\Omega}\vartheta_{0}\|_{1}+\|Y\|^{2}\right).$

The right hand side is less than equal to $n$ due to sub-Gaussianity
assumptions. Indeed $\|\xi\|^{2}\leq n$ with high probability and the same
holds for the term $\|X\vartheta_{0}\|^{2}$ using Lemma A.1 and boundedness of
$\|\vartheta_{0}\|$. These two bounds can be used to show that $\|Y\|^{2}\leq
Cn$ with high probability. Also, using the boundedness of the entries of
$\tilde{\Omega}$ and Cauchy-Schwarz inequality we have
$\frac{\sqrt{n}\lambda}{2}\|\tilde{\Omega}\vartheta_{0}\|_{1}\leq
C\sqrt{np}\|\vartheta_{0}\|\leq Cn$. From these bounds the claimed bound on
the RHS follows. On the other hand the LHS is greater than
$cn\|\hat{\vartheta}^{L}_{X}\|^{2}$ with high probability by Lemma A.2. Thus
we obtain $\|\hat{\vartheta}^{L}_{X}\|\leq C$ for some constant $c$ with high
probability. Since $\|\vartheta_{0}\|\leq C$, we obtain that
$\|\hat{\theta}^{L}_{X}\|\leq C$ with high probability.

∎

###### Proof of Lemma 7.2.

Case 1: $n/p\rightarrow\psi^{-1}>C_{0}>C_{K}^{2}$

Ridge Regression

Let $A=X/\sqrt{n}$, $w=\sqrt{n}\theta$,
$\hat{w}^{R}_{A}=\sqrt{n}\hat{\theta}^{R}_{X}$. We also denote
$\mu_{0}=\sqrt{n}\vartheta_{0}$ and write $\hat{w}^{R}_{A}$ as $\hat{w}$ for
the sake of brevity. Thus it is enough to show that
$\|\hat{w}\|_{\infty}\leq\sqrt{d\log n}$ with high probability. We consider
the column-leave-$d$-out version of the problem. Let $S$ be a given subset of
$\\{1,\ldots,p\\}$.

$\hat{w}^{(S)}=\operatornamewithlimits{arg\,min}_{w\in\mathbb{R}^{p},w_{S}=0}\frac{1}{2}\|Aw-\xi\|^{2}+\frac{\lambda}{2}\|\tilde{\Omega}(\mu_{0}+w)\|^{2}.$

Since $\hat{w}$ is the optimal solution we obtain the following set of
inequalities

$\displaystyle 0$
$\displaystyle\leq\frac{1}{2}\|A\hat{w}^{(S)}-\xi\|^{2}+\frac{\lambda}{2}\|\tilde{\Omega}(\mu_{0}+\hat{w}^{(S)})\|^{2}-\frac{1}{2}\|A\hat{w}-\xi\|^{2}-\frac{\lambda}{2}\|\tilde{\Omega}(\mu_{0}+\hat{w})\|^{2}$
$\displaystyle=-\frac{1}{2}\|A(\hat{w}^{(S)}-\hat{w})\|^{2}+\langle
A(\hat{w}^{(S)}-\hat{w}),A\hat{w}^{(S)}-\xi)\rangle+\frac{\lambda}{2}\|\tilde{\Omega}(\mu_{0}+\hat{w}^{(S)})\|^{2}-\frac{\lambda}{2}\|\tilde{\Omega}(\mu_{0}+\hat{w})\|^{2}.$

We have the following decomposition

$\displaystyle\langle A(\hat{w}^{(S)}-\hat{w}),A\hat{w}^{(S)}-\xi)\rangle$
$\displaystyle=-\langle
A_{S}\hat{w}_{S},(A_{-S}\hat{w}^{(S)}_{-S}-\xi)\rangle+\langle
A_{-S}(\hat{w}^{(S)}_{-S}-\hat{w}_{-S}),(A_{-S}\hat{w}^{(S)}_{-S}-\xi)\rangle$
$\displaystyle=-\langle
A_{S}\hat{w}_{S},(A_{-S}\hat{w}^{(S)}_{-S}-\xi)\rangle-\lambda\langle\hat{w}^{(S)}_{-S}-\hat{w}_{-S},\tilde{\Omega}^{2}_{-S}(\mu_{0,-S}+\hat{w}^{(S)}_{-S})\rangle,$

where the last equality uses the KKT condition
$A_{-S}^{T}(A_{-S}\hat{w}^{(S)}-\xi)=-\lambda\tilde{\Omega}^{2}_{-S}(\mu_{0,-S}+\hat{w}^{(S)}_{-S})$.
Thus we have

$\displaystyle 0\leq$
$\displaystyle-\frac{1}{2}\|A(\hat{w}^{(S)}-\hat{w})\|^{2}-\langle
A_{S}\hat{w}_{S},(A_{-S}\hat{w}^{(S)}_{-S}-\xi)\rangle$
$\displaystyle-\lambda\langle\hat{w}^{(S)}_{-S}-\hat{w}_{-S},\tilde{\Omega}^{2}_{-S}(\mu_{0,-S}+\hat{w}^{(S)}_{-S})\rangle+\frac{\lambda}{2}\|\tilde{\Omega}(\mu_{0}+\hat{w}^{(S)})\|^{2}-\frac{\lambda}{2}\|\tilde{\Omega}(\mu_{0}+\hat{w})\|^{2}$
$\displaystyle\leq-\frac{1}{2}\|A(\hat{w}^{(S)}-\hat{w})\|^{2}-\langle
A_{S}\hat{w}_{S},(A_{-S}\hat{w}^{(S)}_{-S}-\xi)\rangle+\frac{\lambda}{2}\|\tilde{\Omega}_{S}\mu_{0,S}\|^{2}-\frac{\lambda}{2}\|\tilde{\Omega}_{S}(\mu_{0,S}+\hat{w}_{S})\|^{2},$

where the last inequality follows from the convexity of the function
$\|.\|^{2}$. Thus we obtain

$\frac{1}{2}\|A(\hat{w}^{(S)}-\hat{w})\|^{2}+\frac{\lambda}{2}\|\tilde{\Omega}_{S}\hat{w}_{S}\|^{2}\leq\|\hat{w}_{S}\|(\|A^{T}_{S}(A_{-S}\hat{w}^{(S)}_{-S}-\xi)\|+\lambda\|\tilde{\Omega}^{2}_{S}\mu_{0,S}\|).$

From this relation, it easily follows that for some constant $c$

$c\|\hat{w}_{S}\|\leq
2\lambda^{-1}(\|A^{T}_{S}(A_{-S}\hat{w}^{(S)}_{-S}-\xi)\|+\lambda\|\tilde{\Omega}^{2}_{S}\mu_{0,S}\|)\leq
2\lambda^{-1}(\|A^{T}_{S}A_{-S}\hat{w}^{(S)}_{-S}\|+\|A^{T}_{S}\xi\|+\lambda\|\tilde{\Omega}^{2}_{S}\mu_{0,S}\|).$
(A.2)

By the optimality of $\hat{w}^{(S)}$, we have

$\frac{1}{2}\|A_{-S}\hat{w}_{-S}^{(S)}-\xi\|^{2}+\frac{\lambda}{2}\|\tilde{\Omega}(\mu_{0}+\hat{w}_{-S}^{(S)})\|^{2}\leq\frac{1}{2}\|\xi\|^{2}+\frac{\lambda}{2}\|\tilde{\Omega}\mu_{0}\|^{2},$

whence $\|A_{-S}\hat{w}_{-S}^{(S)}\|^{2}\leq
C\left(\frac{1}{2}\|\xi\|^{2}+\frac{\lambda}{2}\|\tilde{\Omega}\mu_{0}\|^{2}\right)$.
Since $\|\xi\|^{2}\leq Cn$ with probability at least $1-n^{-c}$ and
$\|\tilde{\Omega}\mu_{0}\|^{2}\leq Cn$, we obtain
$\|A_{-S}\hat{w}_{-S}^{(S)}\|^{2}\leq Cn$ with probability at least
$1-n^{-c}$.

Now for a single coordinate $s$ there exist a set $S$ (with $|S|\leq d$) such
that $s\in S$ and the columns of $A_{S}$ and the columns of $A_{-S}$ are
independent. Let $i\in S$. Using the facts that the elements of $A_{i}$ are
independent subGaussian and that $A_{i}$ and $A_{-S}\hat{w}^{(S)}_{-S}$ are
independent, we have

$\|A^{T}_{S}A_{-S}\hat{w}^{(S)}_{-S}\|\leq\sqrt{d}\max_{i\in
S}|A^{T}_{i}A_{-S}\hat{w}^{(S)}_{-S}|\leq\sqrt{d\log n}$ (A.3)

holds with probability at least $1-n^{-c}$ conditioned on the event
$\|A_{-S}\hat{w}_{-S}^{(S)}\|^{2}\leq Cn$ which itself holds with probability
$1-n^{-c}$.

Since the elements of $A_{i}$ are i.i.d. and $A_{i}$ and $\xi$ are
independent,$|A^{T}_{i}\xi|\leq\sqrt{\log n}$ holds with probability at least
$1-n^{-c}$. Indeed conditioning on the event $\|\xi\|\leq C\sqrt{n}$ the
result follows from the sub-Gaussian concentration and the event itself holds
with probability at least $1-n^{-c}$. Similar to the bounds obtained for
$\|A^{T}_{S}A_{-S}\hat{w}^{(S)}_{-S}\|$ we obtain
$\|A^{T}_{S}\xi\|\leq\sqrt{d\log n}$ with probability at least $1-n^{-c}$.
Finally since the entries of the signal $\mu_{0}$ are bounded (recall that the
entries of $\vartheta_{0}$ are of the order $O(p^{-1/2})$ by Assumption 4),
using (A.2) we have the following inequality

$|\hat{w}_{s}|\leq\|\hat{w}_{S}\|\leq\sqrt{d\log n},$

with probability at least $1-n^{-c}$.

Also this event holds uniformly in $s$ since we can choose $c>1$ and use the
union bound. Hence

$\|\hat{w}^{R}\|_{\infty}\leq\sqrt{d\log n},$

with probability at least $1-n^{-c}$.

Lasso

Once again we start with the leave-d-out estimator. Let $S$ be a given subset
of $\\{1,\ldots,p\\}$ and define:

$\hat{w}^{(S)}=\operatornamewithlimits{arg\,min}_{w\in\mathbb{R}^{p},w_{S}=0}\frac{1}{2}\|Aw-\xi\|^{2}+\lambda\|\tilde{\Omega}(\mu_{0}+w)\|_{1}.$

The KKT condition is given by

$A_{-S}^{T}(A_{-S}\hat{w}^{(S)}_{-S}-\xi)+\lambda\tilde{\Omega}_{-S}v_{-S}=0,$

where $v_{-S}$ is the subgradient of $\|.\|_{1}$ at
$\tilde{\Omega}(\mu_{0}+\hat{w}^{(S)})$. We write the risk $R(Y,A,\vartheta)$
as a function of $w$ i.e. $R(w)$ suppressing the other variables. Denoting
$\hat{w}$ as the Lasso optimizer we have

$\displaystyle R(0,\hat{w}_{-S})=$
$\displaystyle\frac{1}{2}\|A_{-S}\hat{w}_{-S}-\xi\|^{2}+\lambda\|\tilde{\Omega}(\hat{w}_{-S}+\mu_{0})\|_{1}$
$\displaystyle=$
$\displaystyle\frac{1}{2}\|A_{-S}(\hat{w}_{-S}-\hat{w}^{(S)}_{-S})\|^{2}+\frac{1}{2}\|A_{-S}\hat{w}^{(S)}_{-S}-\xi\|^{2}+\langle
A_{-S}(\hat{w}_{-S}-\hat{w}^{(S)}_{-S}),A_{-S}\hat{w}^{(S)}_{-S}-\xi\rangle$
$\displaystyle+\lambda\|\tilde{\Omega}(\hat{w}^{(S)}_{-S}+\mu_{0})\|_{1}+\lambda\|\tilde{\Omega}(\hat{w}_{-S}+\mu_{0})\|_{1}-\lambda\|\tilde{\Omega}(\hat{w}^{(S)}_{-S}+\mu_{0})\|_{1}$
$\displaystyle=$ $\displaystyle
R(0,\hat{w}^{(S)}_{-S})+\frac{1}{2}\|A_{-S}(\hat{w}_{-S}-\hat{w}^{(S)}_{-S})\|^{2}+\langle
A_{-S}(\hat{w}_{-S}-\hat{w}^{(S)}_{-S}),A_{-S}\hat{w}^{(S)}_{-S}-\xi\rangle$
$\displaystyle+\lambda\|\tilde{\Omega}(\hat{w}_{-S}+\mu_{0})\|_{1}-\lambda\|\tilde{\Omega}(\hat{w}^{(S)}_{-S}+\mu_{0})\|_{1}$
$\displaystyle=$ $\displaystyle
R(0,\hat{w}^{(S)}_{-S})+\frac{1}{2}\|A_{-S}(\hat{w}_{-S}-\hat{w}^{(S)}_{-S})\|^{2}-\langle\hat{w}_{-S}-\hat{w}^{(S)}_{-S},\lambda\tilde{\Omega}_{-S}v_{-S}\rangle$
$\displaystyle+\lambda\|\tilde{\Omega}(\hat{w}_{-S}+\mu_{0})\|_{1}-\lambda\|\tilde{\Omega}(\hat{w}^{(S)}_{-S}+\mu_{0})\|_{1}$
$\displaystyle\geq$ $\displaystyle
R(0,\hat{w}^{(S)}_{-S})+\frac{1}{2}\|A_{-S}(\hat{w}_{-S}-\hat{w}^{(S)}_{-S})\|^{2}.$

The fourth equality follows from the KKT condition and the last inequality
from the convexity of the function $\|.\|_{1}$. Define
$f_{1}(x):=R((x,\hat{w}_{-S}))$ and $f_{2}(x):=R((x,\hat{w}^{(S)}_{-S}))$.
Then we have shown

$\frac{1}{2}\|A_{-S}(\hat{w}_{-S}-\hat{w}^{(S)}_{-S})\|^{2}\leq
f_{1}(0)-f_{2}(0)\leq(f_{1}(0)-\min_{x}f_{1}(x))-(f_{2}(0)-\min_{x}f_{2}(x)).$
(A.4)

The last inequality follows from the fact

$\min_{x}f_{1}(x)=R(\hat{w})\leq\min_{x}R((x,\hat{w}^{(S)}_{-S}))=\min_{x}f_{2}(x).$

We expand $f_{1}(x)$ as follows:

$\displaystyle f_{1}(x)=$
$\displaystyle\frac{1}{2}\|A_{S}x+A_{-S}\hat{w}_{-S}-\xi\|^{2}+\lambda\|\tilde{\Omega}_{S}(x+\mu_{0,S})\|_{1}+\lambda\|\tilde{\Omega}_{-S}(\hat{w}_{-S}+\mu_{0,-S})\|_{1}$
$\displaystyle=$
$\displaystyle\frac{1}{2}\|A_{-S}\hat{w}_{-S}-\xi\|^{2}+\frac{1}{2}\|A_{S}x\|^{2}+\langle
A_{S}x,A_{-S}\hat{w}_{-S}-\xi\rangle$
$\displaystyle+\lambda\|\tilde{\Omega}_{S}(x+\mu_{0,S})\|_{1}+\lambda\|\tilde{\Omega}_{-S}(\hat{w}_{-S}+\mu_{0,-S})\|_{1}+\lambda\|\tilde{\Omega}_{S}\mu_{0,S}\|_{1}-\lambda\|\tilde{\Omega}_{S}\mu_{0,S}\|_{1}$
$\displaystyle=$ $\displaystyle f_{1}(0)+\frac{1}{2}\|A_{S}x\|^{2}+\langle
A_{S}x,A_{-S}\hat{w}_{-S}-\xi\rangle+\lambda\|\tilde{\Omega}_{S}(x+\mu_{0,S})\|_{1}-\lambda\|\tilde{\Omega}_{S}\mu_{0,S}\|_{1}.$

Let $y_{1}=A_{-S}\hat{w}_{-S}-\xi$ and $y_{2}=A_{-S}\hat{w}^{(S)}_{-S}-\xi$.
Also define

$g(y)=\min_{x}\frac{1}{2}\|A_{S}x\|^{2}+\langle
A_{S}x,y\rangle++\lambda\|\tilde{\Omega}_{S}(x+\mu_{0,S})\|_{1}.$

Then we observe that

$f_{1}(0)-f_{2}(0)\leq(f_{1}(0)-\min_{x}f_{1}(x))-(f_{2}(0)-\min_{x}f_{2}(x))=g(y_{2})-g(y_{1}).$

Further we define the following functions:

$\displaystyle h(x)$ $\displaystyle=\frac{1}{2}\|A_{S}x\|^{2}+\langle
A_{S}x,y\rangle$ $\displaystyle b(x)$
$\displaystyle=\lambda\|\tilde{\Omega}_{S}(x+\mu_{0,S})\|_{1}.$

Thus we have,

$\displaystyle g(y)$ $\displaystyle=\min_{x}h(x)+b(x)$
$\displaystyle=\sup_{x}-h^{*}(x)-b^{*}(-x),$

where $h^{*}(x)$ and $g^{*}(x)$ are Fenchel duals of $h(x)$ and $g(x)$
respectively and the last equality is obtained using Fenchel duality theorem.
We note that with probability at least $1-n^{-c}$ $s_{\min}(A_{S})\geq c$ and
hence $A^{T}_{S}A_{S}$ is invertible and we have the following lemma:

######  Lemma A.3.

For the functions $h(x)$ and $b(x)$ defined above, we have the following
Fenchel duals:

$h^{*}(x)=\frac{1}{2}(x-A^{T}_{S}y)^{T}(A^{T}_{S}A_{S})^{-1}(x-A^{T}_{S}y),$
$b^{*}(x)=\begin{cases}-\langle\mu_{0,S},x\rangle\quad\text{ if
}\|\tilde{\Omega}^{-1}_{S}x\|_{\infty}\leq\lambda\\\ \infty\text{ otherwise
}.\end{cases}$ (A.5)

It follows that

$g(y)=\sup_{\|\tilde{\Omega}_{S}^{-1}x\|_{\infty}\leq\lambda}-\frac{1}{2}(x-A^{T}_{S}y)^{T}(A^{T}_{S}A_{S})^{-1}(x-A^{T}_{S}y)-\langle\mu_{0,S},x\rangle,$

and consequently defining $P_{S}=A_{S}(A^{T}_{S}A_{S})^{-1}A^{T}_{S}$ and
using (A.4) we obtain the following set of inequalities,

$\displaystyle\frac{1}{2}\|A_{-S}(\hat{w}_{-S}-\hat{w}^{(S)}_{-S})\|^{2}$
$\displaystyle\leq$ $\displaystyle|g(y_{2})-g(y_{1})|$ $\displaystyle\leq$
$\displaystyle\sup_{\|\tilde{\Omega}_{S}^{-1}x\|_{\infty}\leq\lambda}|x^{T}(A^{T}_{S}A_{S})^{-1}A^{T}_{S}(y_{1}-y_{2})|+\frac{1}{2}|y_{1}^{T}P_{S}y_{1}-y_{2}^{T}P_{S}y_{2}|$
$\displaystyle\leq$
$\displaystyle\sup_{\|\tilde{\Omega}_{S}^{-1}x\|_{\infty}\leq\lambda}\|x\|\|(A^{T}_{S}A_{S})^{-1}A^{T}_{S}(y_{1}-y_{2})\|+\frac{1}{2}(y_{1}-y_{2})^{T}P_{S}(y_{1}-y_{2})+|y_{2}^{T}P_{S}(y_{1}-y_{2})|.$

Recall that $y_{1}-y_{2}=A_{-S}(\hat{w}_{-S}-\hat{w}^{(S)}_{-S})$; hence we
obtain
$(y_{1}-y_{2})^{T}P_{S}(y_{1}-y_{2})=\|P_{S}A_{-S}(\hat{w}_{-S}-\hat{w}^{(S)}_{-S})\|^{2}$.
For $\|\tilde{\Omega}^{-1}_{S}x\|_{\infty}\leq\lambda$ we have the following
inequality

$\|x\|\leq\|x\|_{\infty}\sqrt{d}\leq
C\|\tilde{\Omega}^{-1}_{S}x\|_{\infty}\sqrt{d}\leq C\lambda\sqrt{d}$

and consequently we obtain,

$\displaystyle\frac{1}{2}\|P^{\perp}_{S}A_{-S}(\hat{w}_{-S}-\hat{w}^{(S)}_{-S})\|^{2}$
$\displaystyle\leq$ $\displaystyle
C\lambda\sqrt{d}\|(A^{T}_{S}A_{S})^{-1}A^{T}_{S}A_{-S}(\hat{w}_{-S}-\hat{w}^{(S)}_{-S})\|+\|(A_{-S}\hat{w}^{(S)}_{-S}-\xi)^{T}P_{S}A_{-S}(\hat{w}_{-S}-\hat{w}^{(S)}_{-S})\|$
$\displaystyle\leq$ $\displaystyle
C\lambda\sqrt{d}\|(A^{T}_{S}A_{S})^{-1}A^{T}_{S}A_{-S}(\hat{w}_{-S}-\hat{w}^{(S)}_{-S})\|+\|(A_{-S}\hat{w}^{(S)}_{-S}-\xi)^{T}A_{S}(A^{T}_{S}A_{S})^{-1}A^{T}_{S}A_{-S}(\hat{w}_{-S}-\hat{w}^{(S)}_{-S})\|$
$\displaystyle\leq$
$\displaystyle(C\lambda\sqrt{d}\|(A^{T}_{S}A_{S})^{-1}\|\|A^{T}_{S}\|\|A_{-S}\|+\|A^{T}_{-S}\|\|A_{S}\|\|(A^{T}_{S}A_{S})^{-1}\|\|A^{T}_{S}(A_{-S}\hat{w}^{(S)}_{-S}-\xi)\|)\|\hat{w}_{-S}-\hat{w}^{(S)}_{-S}\|.$

By the same argument as equation (A.3) we have
$\|A^{T}_{S}A_{-S}\hat{w}^{(S)}_{-S}\|\leq C\sqrt{d\log n}$ with probability
at least $1-n^{-c}$ and by independence of $A_{S}$ and $\xi$,
$\|A^{T}_{S}\xi\|\leq C\sqrt{d\log n}$ with probability at least $1-n^{-c}$.
Hence $\|A^{T}_{S}(A_{-S}\hat{w}^{(S)}_{-S}-\xi)\|\leq C\sqrt{d\log n}$ with
probability at least $1-n^{-c}$. By Lemma A.1 the terms
$\|A_{S}\|,\|A_{-S}\|,\|(A^{T}_{S}A_{S})^{-1}\|$ are bounded by some constant
$C$ with probability at least $1-n^{-c}$. Hence the following holds

$\frac{1}{2}\|P^{\perp}_{S}A_{-S}(\hat{w}_{-S}-\hat{w}^{(S)}_{-S})\|^{2}\leq
C\sqrt{d\log n}\|\hat{w}_{-S}-\hat{w}^{(S)}_{-S})\|,$ (A.6)

with probability at least $1-n^{-c}$. Now

$P_{S}^{\perp}(A_{-S}(\hat{w}_{-S}-\hat{w}_{-S}^{(S)}))=A_{S}(-(A^{T}_{S}A_{S})^{-1}A^{T}_{S}A_{-S}(\hat{w}_{-S}-\hat{w}_{-S}^{(S)}))+A_{-S}(\hat{w}_{-S}-\hat{w}_{-S}^{(S)})=A\bar{w},$

where

$\bar{w}^{T}=((-(A^{T}_{S}A_{S})^{-1}A^{T}_{S}A_{-S}(\hat{w}_{-S}-\hat{w}_{-S}^{(S)}))^{T},(\hat{w}_{-S}-\hat{w}_{-S}^{(S)})^{T}).$

By Lemma A.1 and the condition $n/p>C^{2}_{K}$ we have $\|A\bar{w}\|^{2}\geq
c\|\bar{w}\|^{2}$ (for some $c>0$). We also note that
$\|\bar{w}\|^{2}\geq\|\hat{w}_{-S}-\hat{w}_{-S}^{(S)}\|^{2}$ and hence,

$\displaystyle c\|\hat{w}_{-S}-\hat{w}_{-S}^{(S)}\|^{2}$ $\displaystyle\leq
C\sqrt{d\log n}\|\hat{w}_{-S}-\hat{w}^{(S)}_{-S})\|,$
$\displaystyle\|\hat{w}_{-S}-\hat{w}_{-S}^{(S)}\|$ $\displaystyle\leq
c^{-1}C\sqrt{d\log n}.$ (A.7)

By the KKT condition

$A^{T}Aw=A^{T}\xi-\lambda\tilde{\Omega}v,$

for subgradient $v$. Arguing that $\|A^{T}\xi\|_{\infty}$ and
$\lambda\|\tilde{\Omega}v\|_{\infty}$ are bounded by $C\sqrt{\log n}$ with
probability at least $1-n^{-c}$ we obtain

$\|(A^{T}A\hat{w})_{S}\|=\|A^{T}_{S}A_{S}\hat{w}_{S}+A_{S}^{T}A_{-S}\hat{w}_{-S}\|\leq
C\sqrt{d\log n}.$

Rearranging terms and using triangle inequality then yields,

$\|A^{T}_{S}A_{S}\hat{w}_{S}\|\leq C(\sqrt{d\log
p}+\|A_{S}^{T}A_{-S}\hat{w}_{-S}\|).$

Noting that $\|A^{T}_{S}A_{S}\|\geq c$ holds with probability at least
$1-n^{-c}$ we have the following decomposition:

$\|\hat{w}_{S}\|\leq C(\|A_{S}^{T}A_{-S}\hat{w}_{-S}\|+\sqrt{d\log n})\leq
C(\|A_{S}^{T}A_{-S}\hat{w}^{(S)}_{-S}\|+\|A_{S}\|\|A_{-S}\|\|\hat{w}_{-S}-\hat{w}_{-S}^{(S)}\|+\sqrt{d\log
n}).$

The term $\|A_{S}^{T}A_{-S}\hat{w}_{-S}^{(S)}\|$ can be bounded by
$\sqrt{d\log n}$ by the same argument as equation A.3. Also
$\|A_{S}\|,\|A_{-S}\|$ are bounded by some constant $C$ with probability at
least $1-n^{-c}$ by applying Lemma A.1. These facts together with (A.7) yields

$|\hat{w}|_{s}\leq\|\hat{w}_{S}\|\leq\sqrt{d\log n},$

with probability at least $1-n^{-c}$ and using a union bound we obtain

$\|\hat{w}^{L}\|_{\infty}\leq\sqrt{d\log n},$

with probability at least $1-n^{-c}$.

Case 2: $n/p\rightarrow\kappa^{-1}\leq C^{2}_{K}$

We note that for the $\ell_{\infty}$ bound in the ridge regression the lower
bound of the singular value from Lemma A.1 was not used, hence in this case
the $\ell_{\infty}$ bound proof is identical to the one used in Case 1.

For the $\ell_{\infty}$ in Lasso we note the lower bound on the singular from
Lemma A.1 was only used to give lower bound to $A\bar{w}$ (see the equation
after A.6). However in this case one can use easily show that for
$\lambda\geq\lambda_{0}$ $\hat{w}_{-S}-\hat{w}^{(S)}_{S}$ and hence $\bar{w}$
is $2c_{0}n$ sparse (see Lemma A.2). The rest of the proof is same as the
Lasso case of Lemma 7.2.

∎

###### Proof of Lemma A.2.

This follows from the proof of Lemma 6.3 of [HS23] with certain modification
due to the dependence. For the sake of completeness we give the entire proof.

From the KKT condition we can write

$A_{i}^{T}(A\hat{w}-\xi)+\lambda(\tilde{\Omega}v)_{i}=0,$ (A.8)

with $v$ be the subgradient of $\|.\|_{1}$ at
$\tilde{\Omega}(\hat{w}+\mu_{0})$. Let $S_{+}$ be the set such that for $i\in
S_{+}$, $\hat{\mu}_{i}=(\hat{w}+\mu_{0})_{i}>0$ (and similarly define
$S_{-}$). We will show that both $S_{+}$ and $S_{-}$ are bounded by $c_{0}n$
with probability at least $1-n^{-c}$ which ensures that the Lasso solution is
$2c_{0}n$ sparse with probability at least $1-n^{-c}$.

Note that the KKT condition (A.8) can be used to show

$\displaystyle\sum_{i\in S_{+}}z^{2}_{i}+\lambda^{2}\sum_{i\in
S_{+}}\omega^{2}_{i}-2\lambda\sum_{i\in S_{+}}z_{i}\omega_{i}$
$\displaystyle\leq\|A\hat{w}\|^{2}\|A_{S_{+}}A^{T}_{S_{+}}\|$ $\displaystyle
c^{2}\lambda^{2}|S_{+}|-2\lambda\sum_{i\in S_{+}}z_{i}\omega_{i}$
$\displaystyle\leq\|A\hat{w}\|^{2}\|A_{S_{+}}A^{T}_{S_{+}}\|,$

where $z=A^{T}\xi$ and we have used the lower bound on $\omega_{i}$. Thus with
probability at least $1-n^{-c}$ the following event holds

$E:=\\{c^{2}\lambda^{2}|S_{+}|\leq 2\lambda|\sum_{i\in
S_{+}}z_{i}\omega_{i}|+Cn\\}.$

We have used the fact that $\|A\hat{w}\|\leq\sqrt{n}$ with probability at
least $1-n^{-c}$ and $\|A_{S_{+}}A^{T}_{S_{+}}\|\leq C$ with the same
probability. If $|S_{+}|\geq c_{0}n$, we have $c^{2}\lambda^{2}|S_{+}|\leq
2\lambda|\sum_{i\in S_{+}}z_{i}\omega_{i}|+(C/c_{0})|S_{+}|$ so that if
$\lambda$ is chosen greater than $\lambda_{0}=(2C/c^{2}c_{0})^{1/2}$, we have

$c^{2}\lambda^{2}|S_{+}|/2\leq 2\lambda|\sum_{i\in S_{+}}z_{i}\omega_{i}|.$