# Precise analysis of ridge interpolators under heavy correlations – a Random
Duality Theory view

Mihailo Stojnic 111e-mail<EMAIL_ADDRESS>
Abstract

We consider fully row/column-correlated linear regression models and study
several classical estimators (including minimum norm interpolators (GLS),
ordinary least squares (LS), and ridge regressors). We show that _Random
Duality Theory_ (RDT) can be utilized to obtain precise closed form
characterizations of all estimators related optimizing quantities of interest,
including the _prediction risk_ (testing or generalization error). On a
qualitative level out results recover the risk’s well known non-monotonic (so-
called double-descent) behavior as the number of features/sample size ratio
increases. On a quantitative level, our closed form results show how the risk
explicitly depends on all key model parameters, including the problem
dimensions and covariance matrices. Moreover, a special case of our results,
obtained when intra-sample (or time-series) correlations are not present,
precisely match the corresponding ones obtained via spectral methods in [24,
16, 17, 6].

Index Terms: Random linear regression; Interpolators. Ridge estimators;
Correlations.

##  1 Introduction

While _non-monotonic_ behavior in parametric characterizations of various
random structures has been known for a long time, it has received an enormous
amount of attention in recent years. By a no surprise, a larger than ever
popularity of machine learning (ML) and neural networks (NN) substantially
contributed to this. Two lines of work, the neural network one (see, e.g.,
[61, 60, 8, 7, 41, 5]) and the statistical one (see, e.g., [24, 16, 6, 17]),
together with their interconnections, are among those that, in our view, led
the way in bringing such a strong interest to these phenomena.

The first line, (in a way (re)initiated in [61, 60, 8, 7, 41, 5] (and further
theoretically substantiated in e.g., [36, 6])), relates to the empirical
observation of the so-called _double-descent_ phenomenon in neural networks
generalization abilities. In particular, it was emphasized in [5] that the
generalization error has a U-shape dependence on the size of the network
before and a (potentially surprising) second descent after the interpolating
limit (see, also [1, 36, 37, 61, 60] and particularly [56] for early double-
decent displays). This basically somewhat contradictorily [23, 25] indicated
that over-parameterizing networks and ensuring zero training error might not
necessarily lead to a problem of poor generalization. Such a seeming
contradiction was positioned within a bias-variance tradeoff discussion in [5]
and later on re-discussed in a variety of contexts and via a variety of
techniques throughout the vast literature (for an early view within a
statistical learning context see also, e.g., [9]).

The second line of work is probably best represented through a particularly
attractive setup of [24]. Namely, [24] seemingly circumvents a direct
association with the zero-training of neural networks and instead focuses on
potentially simpler models that might exhibit same or similar phenomena
(concurrently, a similar “considerations of simpler models” approach was also
undertaken in [4, 6]). Moreover, it chooses particularly attractive, famous
linear regression model and study its classical associated linear estimators.
While some of the results presented in [24] were already known (see, e.g.,
[16, 17]), their further connection to the nonlinear models and neural
networks (NN) enabled a broader view of the underlying phenomena and, in a
way, reconnected back to the NN considerations of [41, 5, 36, 6]. That then
brought on a strong attention from a variety of scientific communities
substantially raising the awareness of their overall contemporary relevance
and ultimately resulting in a remarkable popularity.

The key strength of [24] (and earlier [16, 17]) actually lies in their
technical contribution. Relying on spectral random matrix (free probability)
theory, they conduct very _precise_ mathematical analyses which allow for a
substantial superseding of mere qualitative confirmation of the existence of
non-monotonicity (ascents, descents, double-descents, spikes, peaks and other
irregularities). As is usually the case with such analyses, the analytical
results of [24, 16, 17] completely corroborate the numerical observations
thereby providing a strong upgrade from substantially simpler, _qualitative_ ,
to way more challenging, _quantitative_ , non-monotonicity confirmations.
Within the scenarios where they can be applied, the spectral methods are
indeed super powerful. On the other hand, outside of them, they remain a bit
limited, thereby rendering a need for potential alternatives.

In this paper we discuss such an alternative and highlight the utilization of
an entirely different mathematical machinery, called Random Duality Theory
(RDT) that we developed in a long line of work [52, 46, 47, 48, 42, 49, 50,
51, 45]. To enable a complementary view, we study similar, though _fully
correlated_ , regression models and associated classical estimators as in [24,
16, 17, 4]. We showcase the RDT’s ability to produce very _precise_ and
generic analyses as well. Moreover, for a special case of intra-sample
uncorrelatedness, we obtain the very same results as in [24, 16, 17] (given
that we are dealing with precise analyses, such a concurrence must indeed be
present if the axioms of mathematics are properly set).

##  2 Mathematical model and definitions

We start with the standard linear model

$\displaystyle{\bf y}=X\bar{\beta}+{\bf e},$ (1)

where $X\in{\mathbb{R}}^{m\times n}$ is a matrix of covariates or feature
vectors, ${\bf y}\in{\mathbb{R}}^{m}$ is a vector of responses, and ${\bf
e}\in{\mathbb{R}}^{m}$ is a noise vector (unless stated otherwise, throughout
the paper all vectors are assumed to be _column vectors_). The model is beyond
well known and needs no further or extensively elaborate motivation. As such
it has been utilized in a variety of scientific and engineering fields over
the last at least a couple of centuries. For the easiness of exposition and
the concreteness of presentation, we will connect it to the process of
traning/testing data relations. Within such a context, we will view the rows
of $X$ ($X_{i,:},i=1,\dots,m$) as vectors of features that are presumed to
create the responses ${\bf y}_{i}$ through a (potentially imperfect or noisy)
linear combination

$\displaystyle{\bf y}_{i}=X_{i,:}\bar{\beta}+{\bf e}_{i},$ (2)

where $\bar{\beta}\in{\mathbb{R}}^{n}$ contains coefficients of the desired
linearity. Given the access to $m$ data pairs $(X_{i,:},{\bf y}_{i})$. one
would want to recover $\bar{\beta}$ as accurately as possible. As hinted in
say [42, 43, 44], various measures of accuracy are of interest. We here
consider the so-called _prediction risk_ or as it is often called
(particularly within the machine learning and neural networks communities),
the _genratlization/testing error_. It will be formally defined in the
following way. Assuming a statistical context, where $X$ and ${\bf e}$ are
random, for an estimator of $\bar{\beta}$, say $\hat{\beta}$, we have the
prediction risk

$\displaystyle R(\bar{\beta},\hat{\beta})\triangleq{\mathbb{E}}_{{\bf
x}^{(t)}}\left(\left(\left({\bf x}^{(t)}\right)^{T}\hat{\beta}-\left({\bf
x}^{(t)}\right)^{T}\bar{\beta}\right)^{2}|X,{\bf y}\right),$ (3)

where, ${\bf x}^{(t)}\in{\mathbb{R}}^{n}$ is the so-called _testing_ vector of
features completely independent of the given _training_ data pairs
$(X_{i,:},{\bf y}_{i})$. While $R(\bar{\beta},\hat{\beta})$ is clearly
deterministic when viewed through the prism of ${\bf x}^{(t)}$, it remains
random when viewed through the prism of randomness od $X$ and ${\bf y}$. Along
the same lines, throughout the paper, we adopt the convention that the
subscripts next to ${\mathbb{E}}$ and ${\mathbb{P}}$ denote the randomness
with respect to which the evaluation is taken (when it is clear from the
context, the subscript(s) will be omitted). It should also be noted that the
above prediction risk can alternatively be viewed as the so-called _excess
risk_. In such a context the prediction risk itself (given in (3)) could be
redefined slightly differently with one option, for example, being replacement
of $\left({\bf x}^{(t)}\right)^{T}\bar{\beta}$ by ${\bf y}^{(t)}$, where ${\bf
y}^{(t)}$ would be the testing response. Switching between these alternative
definitions is analytically relatively easy and, as it brings no conceptual
novelty, we, throughout the paper, utilize the definition given in (3). One
should also note that the prediction risk is defined as a function of both the
“true” ($\bar{\beta}$) and the estimated ($\hat{\beta}$) linear coefficients.
Mathematically speaking, its studying, therefore, falls into the category of –
what is in [44] termed as – the problem dependent analysis.

The prediction risk defined in (3) will be the central focus of our study
below. Before we start the presentation of the technical analysis, we will
need to introduce the types of scenarios that we consider. Three things are of
critical importance to properly set the analytical infrastructure: _(i)_ The
problem dimensions; _(ii)_ The problem statistics; and _(iii)_ The relevant
estimators. We briefly discuss each of them in the following three
subsections.

###  2.1 Dimensions

We consider large dimensional scenario, which will mean that _all_ key
underlying dimensions go to infinity. Under such a context, we are interested
in mathematically the hardest, so-called large $n$ _linear_ (proportional)
regime, where

$\displaystyle\alpha=\lim_{n\rightarrow\infty}\frac{m}{n},$ (4)

and $\alpha$ clearly remains constant as $n$ grows. It is not that difficult
to see that $\alpha$ is the under-parametrization ratio (or the inverse of the
over-parametrization ratio). We generically assume that all underlying
matrices are of full rank. On occasion however, the context may allow
considerations of lower ranks. While the appearance of any such instance will
be followed by a specifically tailored discussion, we here emphasize that
throughout the paper all matrix ranks always remain _linearly_ proportional to
$n$. Also, to simplify the writing and to make the overall presentation look
neater, we often avoid repeatedly using the $\lim_{n\rightarrow\infty}$
notation throughout derivations. It will be clear from the context that any
expression involving $n$ is assumed to be taken in the
$\lim_{n\rightarrow\infty}$ sense.

###  2.2 Statistics

To further emphasize the overall presentation neatness, we assume a Gaussian
(albeit a very general one) statistical scenario. We assume that $\bar{\beta}$
in (1) is deterministic and fixed and that the only source of randomness are
$X$ and ${\bf e}$. In particular, we take both $X$ and ${\bf e}$ to be
comprised of Gaussian entries and, for two full rank (non-necessarily
symmetric) matrices $A\in{\mathbb{R}}^{n\times n}$ and
$\overline{A}\in{\mathbb{R}}^{m\times m}$, given in the following way

$\displaystyle X=ZA,\quad\quad{\bf e}=\sigma\overline{A}{\bf v},$ (5)

where $Z\in{\mathbb{R}}^{m\times n}$ and ${\bf v}\in{\mathbb{R}}^{m}$ have iid
standard normal entries and $\sigma$ is a fixed constant. One can then rewrite
(1) as

$\displaystyle{\bf y}=X\bar{\beta}+{\bf
e}=ZA\bar{\beta}+\sigma\overline{A}{\bf v}.$ (6)

It is then not that difficult to see that the rows of feature matrix $X$,
$X_{i:,}$, are independent of each other but the elements within each row are
correlated among themselves with the correlation matrix given as

$\displaystyle{\mathbb{E}}X_{i,:}^{T}X_{i,:}=A^{T}A.$ (7)

Analogously one also has for the noise correlations

$\displaystyle{\mathbb{E}}{\bf e}{\bf e}^{T}=\overline{A}\overline{A}^{T}.$
(8)

Writing the SVDs of both $A$ and $\overline{A}$, we also have

$\displaystyle A=U\Sigma
V^{T},\quad\overline{A}=\overline{U}\overline{\Sigma}\overline{V}^{T}.$ (9)

Combining (6) and (9), we easily find

$\displaystyle{\bf y}=ZA\bar{\beta}+\overline{A}{\bf v}=ZU\Sigma
V^{T}\bar{\beta}+\sigma\overline{U}\overline{\Sigma}\overline{V}^{T}{\bf v}.$
(10)

Due to rotational symmetry of the standard normal entries of $Z$ and ${\bf
v}$, (10) is statistically equivalent to the following

$\displaystyle{\bf y}=Z\Sigma
V^{T}\bar{\beta}+\sigma\overline{U}\overline{\Sigma}{\bf v}.$ (11)

In other words, one can basically view $X$ and ${\bf e}$ as

$\displaystyle X=Z\Sigma V^{T},\quad{\bf e}=\overline{U}\overline{\Sigma}{\bf
v}.$ (12)

The above assumed statistics will be sufficient to present the key ideas. It
essentially allows for the existence of the cross-sectional (or inter-
features) correlations and intra-sample (or time-series) noise correlations.
Later on (see, Section 4), we will complete the model by allowing for intra-
sample (time-series) type of correlations among the rows of $X$.

Unless otherwise stated, we will also assume that the testing features vector
${\bf x}^{(t)}$ has the same statistics as any of the rows of the training
features matrix $X$. That basically means that we will assume that

$\displaystyle\left({\bf x}^{(t)}\right)^{T}=\left({\bf
z}^{(t)}\right)^{T}\Sigma V^{T},$ (13)

where ${\bf z}^{(t)}\in{\mathbb{R}}^{n}$ is comprised of iid standard normals
independent of $X$ and ${\bf y}$ (basically, $X$ and ${\bf e}$, or $Z$ and
${\bf v}$). It is useful to note that

$\displaystyle{\mathbb{E}}{\bf x}^{(t)}\left({\bf
x}^{(t)}\right)^{T}={\mathbb{E}}V\Sigma{\bf z}^{(t)}\left({\bf
z}^{(t)}\right)^{T}\Sigma V^{T}=V\Sigma\Sigma V^{T}.$ (14)

Also, as there will typically be not much of a point in having both $\sigma$
and magnitude of $\bar{\beta}$ vary, we will (unless otherwise stated) scale
one of them to pone. In other words, we will take $\|\bar{\beta}\|_{2}=1$.

###  2.3 Estimators

Depending on the system dimensions (regimes of operation), we will consider
three different estimators: 1) Minimum $\ell_{2}$ norm interpolator (also,
often called the generalized least squares (GLS) estimator); 2) Ridge
estimator; and 3) Plain least squares. As is well known, they are all directly
related to each other. We will recall on some of these relations throughout
the presentation as well. Here we formally introduce the estimators.

_1) Minimum $\ell_{2}$ norm interpolator (over-parameterized regime, $n>m$):_

$\displaystyle\beta_{gls}\triangleq\mbox{arg}\min_{\beta}$
$\displaystyle\|\beta\|_{2}^{2}$ subject to $\displaystyle X\beta={\bf y}.$
(15)

It is not that difficult to see that the above optimization admits a closed
form solution

$\displaystyle\beta_{gls}=X^{T}(XX^{T})^{-1}{\bf y},$ (16)

or, if written in an alternative form,

$\displaystyle\beta_{gls}=(X^{T}X)^{-1}X^{T}{\bf y},$ (17)

where $(X^{T}X)^{-1}$ is the pseudo-inverse of $X^{T}X$ (only the positive
eigenvalues are inverted).

_2) Ridge estimator (any $n$ and $m$):_ For a given fixed $\lambda>0$, we
define the so-called ridge regression estimator as

$\displaystyle\beta_{rr}(\lambda)\triangleq\mbox{arg}\min_{\beta}\lambda\|\beta\|_{2}^{2}+\frac{1}{m}\|{\bf
y}-X\beta\|_{2}^{2}.$ (18)

After trivially finding the derivatives, it is again not that difficult to see
that the above optimization admits the following closed form solution

$\displaystyle\beta_{rr}(\lambda)=\frac{1}{m}\left(\lambda
I+\frac{1}{m}X^{T}X\right)^{-1}X^{T}{\bf y}=\left(\lambda
mI+X^{T}X\right)^{-1}X^{T}{\bf y}.$ (19)

Moreover, comparing (17) and (19), one easily recognizes that the GLS
estimator is basically a special case of the ridge regression one, obtained
for a particular value of ridge parameter $\lambda\rightarrow 0$. In other
words, one has

$\displaystyle\beta_{gls}=\lim_{\lambda\rightarrow 0}\beta_{rr}(\lambda).$
(20)

One should note that $\lambda$ is not allowed to take value zero in this
regime.

_3) Plain least squares (under-parameterized regime, $n<m$):_

$\displaystyle\beta_{ls}\triangleq\mbox{arg}\min_{\beta}\frac{1}{m}\|{\bf
y}-X\beta\|_{2}^{2}.$ (21)

After taking the derivative one again simply finds the closed form solution

$\displaystyle\beta_{ls}=(X^{T}X)^{-1}X^{T}{\bf y}.$ (22)

In this regime the definition of the ridge estimator can be extended to
$\lambda\geq 0$ and one would then have

$\displaystyle\beta_{ls}=\beta_{rr}(0).$ (23)

All three estimators, (17), (19), and (22) are clearly functions of $X$ and
${\bf y}$. In other words, they are functions of the available training data.
Given the above assumed statistics of $X$, ${\bf y}$, and ${\bf x}^{(t)}$, we
will in the rest of the paper be interested in proving a precise statistical
characterization of the (random) prediction risk

$\displaystyle R(\bar{\beta},\hat{\beta})$ $\displaystyle=$
$\displaystyle{\mathbb{E}}_{{\bf x}^{(t)}}\left(\left(\left({\bf
x}^{(t)}\right)^{T}\hat{\beta}-\left({\bf
x}^{(t)}\right)^{T}\bar{\beta}\right)^{2}|X,{\bf y}\right)$ (24)
$\displaystyle=$ $\displaystyle{\mathbb{E}}_{{\bf
x}^{(t)}}\left(\bar{\beta}-\hat{\beta}\right)^{T}{{\bf x}^{(t)}}\left({{\bf
x}^{(t)}}\right)^{T}\left(\bar{\beta}-\hat{\beta}\right)$ $\displaystyle=$
$\displaystyle\left(\bar{\beta}-\hat{\beta}\right)^{T}V\Sigma\Sigma
V^{T}\left(\bar{\beta}-\hat{\beta}\right),$

where, depending on the regime of interest, $\hat{\beta}$ will be one of
$\beta_{gls}$, $\beta_{rr}$, and $\beta_{ls}$. Our main concern however will
be the over-parameterized regime and consequently the GLS estimator.

###  2.4 Relevant literature and our contributions

As mentioned earlier in the introduction, in our view, two lines of work [61,
60, 8, 7, 41, 5, 60] and [24, 16, 17, 6] predominantly contributed to the
growing interest in studying the non-monotonic random structures behavior.
Within the last few years, in both machine learning and statistical
communities (as well as in many others), these initial considerations have
been followed with a large body of newly branched out different lines of work
with many of them interconnecting among themselves and with others as well. As
our results are of methodological type, we leave a detailed discussion related
to each of these new directions for topic specific survey papers and here
mention a few interesting ones that down the road might turn out to be
particularly relevant.

For example, a strong connection to kernel based machine learning methods has
been developed building further on initial interpolating type of observations
[41, 5, 37, 61, 60]. Relation between the problem architecture and implicit
regularization (considered earlier [37, 22] within deep learning and matrix
factorization contexts) was studied in [31] within the kernel ridgeless
regression with generalization error (as function of spectral decay)
displaying both monotonic and U-shape (non-monotonic) behavior. An even, so to
say, more non-monotonic behavior was observed through the appearance of
multiple descents in [32]. Another strong connection between the interpolators
and running NN training algorithms (usually of the gradient type) [2, 14, 30,
38, 62, 3, 19, 27, 29, 18] was observed as well (in a way, it also relates to
some earlier machine learning/regression cross-considerations [15, 59]).

On a more statistical side (and more closely related to our work), in parallel
with [24], [6] first study similar mathematical regression setup as a way of
providing a simple model for the appearance of the NN interpolating
generalization double-descent phenomenon. Working in an uncorrelated
(isotropic) standard normal context, it extends classical results of [11] to
over-parameterized regimes and achieves the double-descent. It then switches
to random features model of [39], utilizes empirical distribution of discrete
Fourier transform (DFT) matrices (see, e.g., [20]) and again obtains the
double-descent. After these initial considerations [24, 16, 17, 6], further
studies followed [40, 57] (see also, e.g., [58]). These contributions focus
specifically on technical aspects. In particular, similarly to [24], [40, 57]
also rely on the spectral random matrix theory but utilize a bit different
approach (more akin to [28]) to obtain slightly different results (the initial
results of [24] assumed a random $\bar{\beta}$ which, in a way, is similar to
a technical statistical assumption on $\bar{\beta}$ needed in [40]). The final
results and main points of [24] were, however, conceptually maintained in both
[40, 57]. There has been several contributions that also brought some
conceptual novelties. For example, [55, 4] consider potential benefits of the
so-called benign over-fitting concept. In particular, [4] shows that, in
linear regression, a mild over-parametrization can lead not only to a double-
descent phenomenon but to a consistency of the interpolators provided that a
specific “ _benign_ ” structure of the inter-features covariances is present
(the so-called effective rank needs to be properly related to the problem
dimensions, the sample size $m$ and the number of features $n$). Similar
conclusion is reached for the ridge regression as well in [55]. In [12], the
factor regression models (FRM) are considered and the very same consistency
property obtained in [55, 4] is demonstrated for the FRM’s GLS. Results of
[12] are in a way generalized in [10], where a bit different estimator is
introduced but [12]’s‘two key GLS properties, “beating the null risk” and
consistency, are shown as achievable again. [34] precisely analyzes nonlinear
random features models of [39] and considers statistical universality (which
was also discussed in [35, 26]).

As mentioned earlier, we study a standard linear regression setup (which is
similar to the one from, say e.g., [24, 16, 17, 6, 4]), albeit in a _fully
correlated_ context where the intra-sample (or time-series) correlations are
also allowed. Three classical estimators associated with such models given by
(15), (18), and (21) are considered. Differently from the spectral methods
used in [24, 16, 17, 6], we here present the utilization of a completely
different mathematical engine, called Random Duality Theory (RDT) (see, e.g.,
[52, 46, 47, 48, 42, 49, 50, 51, 45]). Following step-by-step main RDT
principles, we demonstrate the role of each of them in the analysis of the
optimization programs (15), (18), and (21). The RDT machinery is basically
shown as sufficiently powerful to enable very precise determining of _all_
optimizing quantities associated with each of these three programs. Among
them, of particular interest is the _prediction risk_ (generalization/testing
error) from (24). We observe that the GLS-interpolating risk (as a function of
over-parametrization ratio $\frac{1}{\alpha}$) exhibits the double-descent
with the potential for exhibiting the U-shape behavior in the interpolating
regime ($\frac{1}{\alpha}>1$), thereby creating another aspect of non-
monotonicity (this in general depends on the ratio
$\mbox{SNR}=\frac{1}{\sigma^{2}}$, or just $\sigma$ if one keeps in mind the
scaling invariance and the above mentioned fixing $\|\bar{\beta}\|_{2}=1$).
Moreover, numerical evaluations suggest (possibly somewhat counter-
intuitively) that the intra-sample correlations might not always imply
necessarily higher GLS interpolator’s prediction risk. Our results have
explicit closed forms where both bias and variance parts of the risk can
clearly be distinguished. Moreover, as they in special case of absent intra-
sample correlations match the ones of [24, 16, 17] (and in the fully isotropic
case the ones of [6]), all insight, intuitions, and conclusions gained therein
apply here as well.

##  3 Precise analysis of all three estimators

We below provide a precise performance analysis of all the three above
introduced classical estimators. Each of the estimators is discussed in a
separate subsection. As mentioned earlier when discussing underlying
statistics, we in this section consider scenarios with the cross-sectional (or
inter-features) correlations and intra-sample (or time-series) noise
correlations. The intra-sample (time-series) correlations among the rows of
$X$ will be discussed in Section 4. Separating these discussions allows to
emphasize two key points: (i) there is a substantial analytical difference
needed to complete the fully correlated models of Section 4; and (ii) despite
such a difference the analysis of the row-uncorrelated $X$ can still be
utilized for the fully correlated scenario.

We start with the GLS interpolator as it relates to the over-parameterized
regime that has gained a lot popularity in recent years due to its utilization
in machine learning and the architecture design of neural networks.

###  3.1 GLS interpolator

The analysis that we provide below will do slightly more than just providing
the characterization of the GLS estimator. Namely, we will actually provide a
precise statistical characterization of all the key quantiti4es associated
with the optimization program (15). It will turn out that the prediction risk
from (24) is among them as well. We start by defining the objective of the
program (15)

$\displaystyle\xi_{gls}\triangleq\min_{\beta}$
$\displaystyle\|\beta\|_{2}^{2}$ subject to $\displaystyle X\beta={\bf y}.$
(25)

To ensure that the presentation is not overloaded with a tone of special cases
and unnecessary tiny details that bring no conceptual insights, we assume that
all the key quantities appearing in the derivations below are bounded
(deterministically or randomly). Recalling on (11) and (12), we proceed by
writing a statistical equivalent to (25)

$\displaystyle\xi_{gls}\triangleq\min_{\beta}$
$\displaystyle\|\beta\|_{2}^{2}$ subject to $\displaystyle Z\Sigma
V^{T}\beta=Z\Sigma V^{T}\bar{\beta}+\sigma\overline{U}\overline{\Sigma}{\bf
v}.$ (26)

After writing the Lagrangian we further have

$\displaystyle\xi_{gls}=\min_{\beta}\max_{\nu}$
$\displaystyle\left(\|\beta\|_{2}^{2}+\nu^{T}\left(Z\Sigma V^{T}\beta-Z\Sigma
V^{T}\bar{\beta}-\sigma\overline{U}\overline{\Sigma}{\bf v}\right)\right).$
(27)

One should now note that the above actually holds generically, i.e., it holds
for any $Z$, ${\bf v}$, $V$, $\Sigma$, $\overline{U}$, $\overline{\Sigma}$,
$\sigma$, and $\bar{\beta}$. It then automatically applies to the random
instances as well. As precisely such instance are of our particular interest
here, the following would be a simple summary of the probabilistic
characterization of $\xi_{gls}$ that we are ultimately looking for.

Ultimate goal:Given:
$\displaystyle\alpha=\lim_{n\rightarrow\infty}\frac{m}{n}\in(1,\infty)\quad\mbox{and}\quad
V,\Sigma,\overline{U},\overline{\Sigma},\sigma,\bar{\beta}$ find
$\displaystyle\xi_{gls}^{(opt)}$ such that
$\displaystyle\forall\epsilon>0,\quad\lim_{n\rightarrow\infty}{\mathbb{P}}_{Z,{\bf
v}}\left((1-\epsilon)\xi_{gls}^{(opt)}\leq\xi_{gls}\leq(1+\epsilon)\xi_{gls}^{(opt)}\right)\longrightarrow
1.$

It goes without saying that, within their given intervals, $\alpha$ and
$\epsilon$ are allowed to be arbitrarily large or small but they do not change
as $n\rightarrow\infty$. As mentioned earlier, the subscripts next to
${\mathbb{P}}$ denote all sources of randomness with respect to which the
statistical evaluation is taken. To achieve the above goal we employ the
powerful Random Duality Theory (RDT) machinery.

####  3.1.1 Handling GLS estimator via RDT

We find it useful to first briefly recall on the main RDT principles. After
that we continue by showing, step-by-step, how each of them relates to the
problems of our interest here.

Summary of the RDT’s main principles [46, 52]
$\displaystyle\begin{array}[]{ll}\mbox{1) \emph{Finding underlying
optimization algebraic representation}}&\mbox{2) \emph{Determining the random
dual}}\\\ \mbox{3) \emph{Handling the random dual}}&\mbox{4) \emph{Double-
checking strong random duality.}}\end{array}$

To make the presentation easier to follow, as in [54], we formalize all key
results (simple to more complicated ones) as lemmas and theorems. Moreover,
similarly to [54], although some analytical steps can occasionally be done a
bit faster, we usually opt for a fully systematic approach ensuring that the
presentation is self-contained.

1) _Algebraic characterization:_ The above algebraic discussions are
summarized in the following lemma which ultimately provides a convenient
representation of the objective $\xi_{gls}$.

######  Lemma 1.

(Algebraic optimization representation) Let $V\in{\mathbb{R}}^{n\times n}$ and
$\overline{U}\in{\mathbb{R}}^{m\times m}$ be two given unitary (orthogonal)
matrices and let $\Sigma\in{\mathbb{R}}^{n\times n}$ and
$\overline{\Sigma}\in{\mathbb{R}}^{m\times m}$ be two given diagonal positive
definite matrices. Also, let vector $\bar{\beta}\in{\mathbb{R}}^{n}$ and
scalar $\sigma\geq 0$ be given as well. Assume that the components of any of
these given objects are fixed real numbers that do not change as
$n\rightarrow\infty$ and, for (possibly random) matrix
$Z\in{\mathbb{R}}^{m\times n}$ and vector ${\bf v}\in{\mathbb{R}}^{m}$, let
$\xi_{gls}$ be as in (25) or (26). Set

$\displaystyle f_{rp}(Z,{\bf v})$ $\displaystyle\triangleq$
$\displaystyle\min_{\beta}\max_{\nu}\left(\|\beta\|_{2}^{2}+\nu^{T}\left(Z\Sigma
V^{T}\beta-Z\Sigma V^{T}\bar{\beta}-\sigma\overline{U}\overline{\Sigma}{\bf
v}\right)\right)\hskip
57.81621pt({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\textbf{random
primal}})$ $\displaystyle\xi_{rp}$ $\displaystyle\triangleq$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{Z,{\bf v}}f_{rp}(Z,{\bf
v}).$ (30)

Then

$\xi_{gls}=f_{rp}(Z,{\bf
v})\quad\mbox{and}\quad\lim_{n\rightarrow\infty}{\mathbb{E}}_{Z,{\bf
v}}\xi_{gls}=\xi_{rp}.$ (31)

###### Proof.

Follows automatically via the Lagrangian from (27). ∎

Clearly, assuming that $V$, $\Sigma$, $\overline{U}$, $\overline{\Sigma}$,
$\sigma$, and $\beta$ are fixed and given, the above lemma holds for any $Z$
and ${\bf v}$. The RDT proceeds by imposing a statistics on $Z$ and ${\bf v}$.

2) _Determining the random dual:_ Following the common practice within the
RDT, we utilize the concentration of measure, which here implies that for any
fixed $\epsilon>0$, one can write (see, e.g. [46, 52, 47])

$\lim_{n\rightarrow\infty}{\mathbb{P}}_{Z,{\bf v}}\left(\frac{|f_{rp}(Z,{\bf
v})-{\mathbb{E}}_{Z,{\bf v}}(f_{rp}(Z,{\bf v}))|}{{\mathbb{E}}_{Z,{\bf
v}}(f_{rp}(Z,{\bf v}))}>\epsilon\right)\longrightarrow 0.$ (32)

The following, so-called random dual theorem, is another key RDT ingredient.
It provides a specific characterization of the objective of optimization
programs (15) and (26) used to obtain the GLS estimator, $\beta_{gls}$.

######  Theorem 1.

(Objective characterization via random dual) Assume the setup of Lemma 31 and
let the components of $Z$ and ${\bf v}$ be iid standard normals. Additionally,
let ${\bf g}\in{\mathbb{R}}^{m}$ and ${\bf h}\in{\mathbb{R}}^{n}$ be vectors
that are also comprised of iid standard normals. Set

$\displaystyle c_{2}$ $\displaystyle\triangleq$ $\displaystyle\|\Sigma
V^{T}\left(\beta-\bar{\beta}\right)\|_{2}$ $\displaystyle f_{rd}({\bf g},{\bf
h},{\bf v})$ $\displaystyle\triangleq$
$\displaystyle\min_{\beta}\max_{\nu}\left(\|\beta\|_{2}^{2}+c_{2}\nu^{T}{\bf
g}+\|\nu\|_{2}{\bf h}^{T}\Sigma
V^{T}\left(\beta-\bar{\beta}\right)-\sigma\nu^{T}\overline{U}\overline{\Sigma}{\bf
v}\right)\hskip
50.58878pt({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\textbf{random
dual}})$ $\displaystyle\xi_{rd}$ $\displaystyle\triangleq$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{{\bf g},{\bf h},{\bf
v}}f_{rd}({\bf g},{\bf h},{\bf v}).\vspace{-.0in}$ (33)

One then has

$\displaystyle\xi_{rd}$ $\displaystyle\triangleq$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{{\bf g},{\bf h},{\bf
v}}f_{rd}({\bf g},{\bf h},{\bf
v})\leq\lim_{n\rightarrow\infty}{\mathbb{E}}_{Z,{\bf v}}f_{rp}(Z,{\bf
v})\triangleq\xi_{rp}.\vspace{-.0in}$ (34)

and

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{{\bf g},{\bf h},{\bf
v}}\left(f_{rd}({\bf g},{\bf h},{\bf
v})\geq(1-\epsilon)\xi_{rd}\right)\leq\lim_{n\rightarrow\infty}{\mathbb{P}}_{Z,{\bf
v}}\left(f_{rp}(Z,{\bf v})\geq(1-\epsilon)\xi_{rd}\right).$ (35)

###### Proof.

Follows as an immediate application of the Gordon’s probabilistic comparison
theorem (see, e.g., Theorem B in [21] and also Theorem 1, Corollary 1, and
Section 2.7.2 in [53]). ∎

3) _Handling the random dual:_ We start by solving the inner maximization over
$\nu$ and obtain

$\displaystyle f_{rd}({\bf g},{\bf h},{\bf v})$ $\displaystyle\triangleq$
$\displaystyle\min_{\beta}\max_{\nu}\left(\|\beta\|_{2}^{2}+c_{2}\nu^{T}{\bf
g}+\|\nu\|_{2}{\bf h}^{T}\Sigma
V^{T}\left(\beta-\bar{\beta}\right)-\sigma\nu^{T}\overline{U}\overline{\Sigma}{\bf
v}\right)$ (36) $\displaystyle=$
$\displaystyle\min_{\beta}\max_{\|\nu\|_{2}}\left(\|\beta\|_{2}^{2}+\|\nu\|_{2}{\bf
h}^{T}\Sigma V^{T}\left(\beta-\bar{\beta}\right)+\|\nu\|_{2}\|c_{2}{\bf
g}-\sigma\overline{U}\overline{\Sigma}{\bf v}\|_{2}\right)$ $\displaystyle=$
$\displaystyle\min_{\beta}\max_{\|\nu\|_{2}}\left(\|V^{T}\beta\|_{2}^{2}+\|\nu\|_{2}{\bf
h}^{T}\Sigma\left(V^{T}\beta-V^{T}\bar{\beta}\right)+\|\nu\|_{2}\|c_{2}{\bf
g}-\sigma\overline{U}\overline{\Sigma}{\bf v}\|_{2}\right)$ $\displaystyle=$
$\displaystyle\min_{{\bf x},c_{2}\geq 0}\max_{\nu_{s}\geq 0}\left(\|{\bf
x}\|_{2}^{2}+\nu_{s}{\bf h}^{T}\Sigma\left({\bf x}-{\bf
c}\right)+\nu_{s}\|c_{2}{\bf g}-\sigma\overline{U}\overline{\Sigma}{\bf
v}\|_{2}\right),$

where the third equality follows due to $V$ being unitary and the fourth is a
consequence of the following change of variables

$\displaystyle{\bf x}=V^{T}\beta,\quad{\bf c}\triangleq
V^{T}\bar{\beta},\quad\nu_{s}=\|\nu\|_{2},$ (37)

and we also note that

$\displaystyle c_{2}=\|\Sigma\left({\bf x}-{\bf c}\right)\|_{2}.$ (38)

After setting

$\displaystyle{\mathcal{L}}\left({\bf x},c_{2},\nu_{s};{\bf g},{\bf h},{\bf
v}\right)\triangleq\|{\bf x}\|_{2}^{2}+\nu_{s}{\bf h}^{T}\Sigma\left({\bf
x}-{\bf c}\right)+\nu_{s}\|c_{2}{\bf
g}-\sigma\overline{U}\overline{\Sigma}{\bf v}\|_{2},$ (39)

it is not that difficult to see that (36) can be rewritten as

$\displaystyle f_{rd}({\bf g},{\bf h},{\bf v})=\min_{{\bf x},c_{2}\geq
0}\max_{\nu_{s}\geq 0}{\mathcal{L}}\left({\bf x},c_{2},\nu_{s};{\bf g},{\bf
h},{\bf v}\right).$ (40)

Keeping $c_{2}$ and $\nu_{s}$ fixed, we consider the following minimization
over ${\bf x}$

$\displaystyle{\mathcal{L}}_{1}\left(c_{2},\nu_{s}\right)\triangleq\min_{{\bf
x}}$ $\displaystyle\|{\bf x}\|_{2}^{2}+\nu_{s}{\bf h}^{T}\Sigma\left({\bf
x}-{\bf c}\right)+\nu_{s}\|c_{2}{\bf
g}-\sigma\overline{U}\overline{\Sigma}{\bf v}\|_{2}$ subject to
$\displaystyle\|\Sigma\left({\bf x}-{\bf c}\right)\|_{2}=c_{2},$ (41)

where the functional dependence on randomness is kept implicit to lighten the
exposition. After writing the Lagrangian we then obtain

$\displaystyle{\mathcal{L}}_{1}\left(c_{2},\nu_{s}\right)$ $\displaystyle=$
$\displaystyle\min_{{\bf x}}\max_{\gamma}\|{\bf x}\|_{2}^{2}+\nu_{s}{\bf
h}^{T}\Sigma\left({\bf x}-{\bf c}\right)+\nu_{s}\|c_{2}{\bf
g}-\sigma\overline{U}\overline{\Sigma}{\bf v}\|_{2}+\gamma\|\Sigma\left({\bf
x}-{\bf c}\right)\|_{2}^{2}-\gamma c_{2}^{2}$ (42) $\displaystyle=$
$\displaystyle\max_{\gamma}\min_{{\bf x}}\|{\bf x}\|_{2}^{2}+\nu_{s}{\bf
h}^{T}\Sigma\left({\bf x}-{\bf c}\right)+\nu_{s}\|c_{2}{\bf
g}-\sigma\overline{U}\overline{\Sigma}{\bf v}\|_{2}+\gamma\|\Sigma\left({\bf
x}-{\bf c}\right)\|_{2}^{2}-\gamma c_{2}^{2}$ $\displaystyle=$
$\displaystyle\max_{\gamma}\min_{{\bf x}}{\mathcal{L}}_{2}\left({\bf
x},\gamma;c_{2},\nu_{s}\right),$

where the second equality is implied by the strong Lagrange duality and the
third by introducing

$\displaystyle{\mathcal{L}}_{2}\left({\bf
x},\gamma;c_{2},\nu_{s}\right)\triangleq\|{\bf x}\|_{2}^{2}+\nu_{s}{\bf
h}^{T}\Sigma\left({\bf x}-{\bf c}\right)+\nu_{s}\|c_{2}{\bf
g}-\sigma\overline{U}\overline{\Sigma}{\bf v}\|_{2}+\gamma\|\Sigma\left({\bf
x}-{\bf c}\right)\|_{2}^{2}-\gamma c_{2}^{2}.$ (43)

After taking the derivative, we find

$\displaystyle\frac{{\mathcal{L}}_{2}\left({\bf
x},\gamma;c_{2},\nu_{s}\right)}{d{\bf x}}=2{\bf x}+\nu_{s}\Sigma{\bf
h}+2\gamma\Sigma\Sigma\left({\bf x}-{\bf c}\right).$ (44)

Equalling the above derivative to zero gives

$\displaystyle\hat{{\bf
x}}=\left(I+\gamma\Sigma\Sigma\right)^{-1}\left(-\frac{1}{2}\nu_{s}\Sigma{\bf
h}+\gamma\Sigma\Sigma{\bf c}\right).$ (45)

Plugging this back in (43) further gives

$\displaystyle\min_{{\bf x}}{\mathcal{L}}_{2}\left({\bf
x},\gamma;c_{2},\nu_{s}\right)$ $\displaystyle=$
$\displaystyle{\mathcal{L}}_{2}\left(\hat{{\bf
x}},\gamma;c_{2},\nu_{s}\right)$ (46) $\displaystyle=$
$\displaystyle-\left(-\frac{1}{2}\nu_{s}\Sigma{\bf h}+\gamma\Sigma\Sigma{\bf
c}\right)^{T}\left(I+\gamma\Sigma\Sigma\right)^{-1}\left(-\frac{1}{2}\nu_{s}\Sigma{\bf
h}+\gamma\Sigma\Sigma{\bf c}\right)$ $\displaystyle-\nu_{s}{\bf
h}^{T}\Sigma{\bf c}+\nu_{s}\|c_{2}{\bf
g}-\sigma\overline{U}\overline{\Sigma}{\bf v}\|_{2}+\gamma{\bf
c}^{T}\Sigma\Sigma{\bf c}-\gamma c_{2}^{2}.$

With appropriate scaling $\nu_{s}\rightarrow\frac{\nu_{1}}{\sqrt{n}}$ (where
$\nu_{1}$ does not change as $n$ grows), (46) can be rewritten as

$\displaystyle{\mathcal{L}}_{2}\left(\hat{{\bf
x}},\gamma;c_{2},\nu_{1}\right)$ $\displaystyle=$
$\displaystyle-\left(-\frac{1}{2\sqrt{n}}\nu_{1}\Sigma{\bf
h}+\gamma\Sigma\Sigma{\bf
c}\right)^{T}\left(I+\gamma\Sigma\Sigma\right)^{-1}\left(-\frac{1}{2\sqrt{n}}\nu_{1}\Sigma{\bf
h}+\gamma\Sigma\Sigma{\bf c}\right)$ (47)
$\displaystyle-\frac{1}{\sqrt{n}}\nu_{1}{\bf h}^{T}\Sigma{\bf
c}+\frac{1}{\sqrt{n}}\nu_{1}\|c_{2}{\bf
g}-\sigma\overline{U}\overline{\Sigma}{\bf v}\|_{2}+\gamma{\bf
c}^{T}\Sigma\Sigma{\bf c}-\gamma c_{2}^{2}.$

Setting ${\bf s}$ to be the column vector comprised of diagonal elements of
$\Sigma$, i.e., setting

$\displaystyle{\bf s}\triangleq\mbox{diag}\left(\Sigma\right),$ (48)

and keeping $c_{2}$, $\nu_{1}$, and $\gamma$ fixed, we then relying on
concentrations find

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{{\bf g},{\bf h},{\bf
v}}{\mathcal{L}}_{2}\left(\hat{{\bf x}},\gamma;c_{2},\nu_{1}\right)$
$\displaystyle=\lim_{n\rightarrow\infty}{\mathbb{E}}\Bigg{(}\Big{.}-\left(-\frac{\nu_{1}}{2\sqrt{n}}\Sigma{\bf
h}+\gamma\Sigma\Sigma{\bf
c}\right)^{T}\left(I+\gamma\Sigma\Sigma\right)^{-1}\left(-\frac{\nu_{1}}{2\sqrt{n}}\Sigma{\bf
h}+\gamma\Sigma\Sigma{\bf c}\right)$
$\displaystyle\quad-\frac{1}{\sqrt{n}}\nu_{1}{\bf h}^{T}\Sigma{\bf
c}+\frac{1}{\sqrt{n}}\nu_{1}\|c_{2}{\bf
g}-\sigma\overline{U}\overline{\Sigma}{\bf v}\|_{2}+\gamma{\bf
c}^{T}\Sigma\Sigma{\bf c}-\gamma c_{2}^{2}\Big{.}\Bigg{)}$
$\displaystyle=\lim_{n\rightarrow\infty}\Bigg{(}\Big{.}-\frac{\nu_{1}^{2}}{4n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{1+\gamma{\bf s}_{i}^{2}}-\sum_{i=1}^{n}\frac{\gamma^{2}{\bf
s}_{i}^{4}{\bf c}_{i}^{2}}{1+\gamma{\bf
s}_{i}^{2}}+\nu_{1}\sqrt{\alpha}\sqrt{c_{2}^{2}+\bar{\sigma}^{2}}+\gamma\sum_{i=1}^{n}{\bf
s}_{i}^{2}{\bf c}_{i}^{2}-\gamma c_{2}^{2}\Big{.}\Bigg{)},$

where

$\displaystyle\bar{\sigma}\triangleq\sigma\sqrt{\lim_{n\rightarrow\infty}\frac{{\rm
tr}\,\left(\overline{\Sigma}\overline{\Sigma}\right)}{m}}.$ (50)

As mentioned earlier, to make writing easier and neater, we adopt the
convention of avoiding repeatedly using $\lim_{n\rightarrow\infty}$. It is
assumed that all expressions involving $n$ (or $m$) are written within the
$\lim_{n\rightarrow\infty}$ context. Also, as mentioned earlier, all such
expressions are assumed to be bounded and the corresponding limiting values
well defined and existing. Combining (39)-(42), (46), and
(LABEL:eq:ta18a0b4c3), we arrive at the following optimization

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{{\bf g},{\bf h},{\bf
v}}f_{rd}({\bf g},{\bf h},{\bf v})$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\min_{c_{2}\geq 0}\max_{\nu_{1}\geq
0,\gamma}f_{0}(c_{2},\nu_{1},\gamma),$ (51)

where

$\displaystyle
f_{0}(c_{2},\nu_{1},\gamma)\triangleq-\frac{\nu_{1}^{2}}{4n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{1+\gamma{\bf s}_{i}^{2}}-\sum_{i=1}^{n}\frac{\gamma^{2}{\bf
s}_{i}^{4}{\bf c}_{i}^{2}}{1+\gamma{\bf
s}_{i}^{2}}+\nu_{1}\sqrt{\alpha}\sqrt{c_{2}^{2}+\bar{\sigma}^{2}}+\gamma\sum_{i=1}^{n}{\bf
s}_{i}^{2}{\bf c}_{i}^{2}-\gamma c_{2}^{2}.$ (52)

After taking the derivative with respect to $\nu_{1}$, we find

$\displaystyle\frac{df_{0}(c_{2},\nu_{1},\gamma)}{d\nu_{1}}=-\frac{\nu_{1}}{2n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{1+\gamma{\bf
s}_{i}^{2}}+\sqrt{\alpha}\sqrt{c_{2}^{2}+\bar{\sigma}^{2}}.$ (53)

Setting the above derivative to zero gives the following optimal $\nu_{1}$

$\displaystyle\hat{\nu}_{1}=\frac{2\sqrt{\alpha}\sqrt{c_{2}^{2}+\bar{\sigma}^{2}}}{\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{1+\gamma{\bf s}_{i}^{2}}}.$ (54)

Plugging this value for $\nu_{1}$ back in (52) gives

$\displaystyle\max_{\nu_{1}\geq
0}f_{0}(c_{2},\nu_{1},\gamma)=f_{0}(c_{2},\hat{\nu}_{1},\gamma)=-\sum_{i=1}^{n}\frac{\gamma^{2}{\bf
s}_{i}^{4}{\bf c}_{i}^{2}}{1+\gamma{\bf
s}_{i}^{2}}+\frac{\alpha\left(c_{2}^{2}+\bar{\sigma}^{2}\right)}{\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{1+\gamma{\bf s}_{i}^{2}}}+\gamma\sum_{i=1}^{n}{\bf s}_{i}^{2}{\bf
c}_{i}^{2}-\gamma c_{2}^{2}.$ (55)

A combination of (51) and (55) gives

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{{\bf g},{\bf h},{\bf
v}}f_{rd}({\bf g},{\bf h},{\bf v})$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\min_{c_{2}\geq
0}\max_{\gamma}f_{0}(c_{2},\hat{\nu}_{1},\gamma),$ (56)

where $f_{0}(c_{2},\hat{\nu}_{1},\gamma)$ as in (55). Taking derivatives with
respect $c_{2}$ and $\gamma$ and equalling them to zero, we further have

$\displaystyle\frac{df_{0}(c_{2},\hat{\nu}_{1},\gamma)}{dc_{2}}=\frac{2\alpha
c_{2}}{\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf s}_{i}^{2}}{1+\gamma{\bf
s}_{i}^{2}}}-2\gamma c_{2}=0.$ (57)

and

$\frac{df_{0}(c_{2},\hat{\nu}_{1},\gamma)}{d\gamma}=-\sum_{i=1}^{n}\frac{2\gamma{\bf
s}_{i}^{4}{\bf c}_{i}^{2}}{1+\gamma{\bf
s}_{i}^{2}}+\sum_{i=1}^{n}\frac{\gamma^{2}{\bf s}_{i}^{6}{\bf
c}_{i}^{2}}{\left(1+\gamma{\bf
s}_{i}^{2}\right)^{2}}+\frac{\alpha\left(c_{2}^{2}+\bar{\sigma}^{2}\right)}{\left(\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{1+\gamma{\bf
s}_{i}^{2}}\right)^{2}}\left(\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{4}}{\left(1+\gamma{\bf
s}_{i}^{2}\right)^{2}}\right)+\sum_{i=1}^{n}{\bf s}_{i}^{2}{\bf
c}_{i}^{2}-c_{2}^{2}=0.$ (58)

From (57) we have that the optimal $\hat{\gamma}$ satisfies the following
equation

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\frac{\hat{\gamma}{\bf
s}_{i}^{2}}{1+\hat{\gamma}{\bf s}_{i}^{2}}=\alpha.$ (59)

From (58) we have that the optimal $\hat{c}_{2}$ and $\hat{\gamma}$ satisfy
the following equation

$\displaystyle\sum_{i=1}^{n}\frac{{\bf s}_{i}^{2}{\bf
c}_{i}^{2}}{\left(1+\hat{\gamma}{\bf
s}_{i}^{2}\right)^{2}}+\frac{\alpha\left(\hat{c}_{2}^{2}+\bar{\sigma}^{2}\right)}{\left(\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{1+\hat{\gamma}{\bf
s}_{i}^{2}}\right)^{2}}\left(\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{4}}{\left(1+\hat{\gamma}{\bf
s}_{i}^{2}\right)^{2}}\right)-\hat{c}_{2}^{2}=0.$ (60)

Setting

$\displaystyle a_{2}=\frac{\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{4}}{\left(1+\hat{\gamma}{\bf
s}_{i}^{2}\right)^{2}}}{\left(\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{1+\hat{\gamma}{\bf s}_{i}^{2}}\right)^{2}},$ (61)

we from (60) find

$\displaystyle\hat{c}_{2}^{2}=\frac{\sum_{i=1}^{n}\frac{{\bf s}_{i}^{2}{\bf
c}_{i}^{2}}{\left(1+\hat{\gamma}{\bf
s}_{i}^{2}\right)^{2}}+\alpha\bar{\sigma}^{2}a_{2}}{1-\alpha a_{2}}.$ (62)

From (55) and (56), we then have

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{{\bf g},{\bf h},{\bf
v}}f_{rd}({\bf g},{\bf h},{\bf v})$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\min_{c_{2}\geq
0}\max_{\gamma}f_{0}(c_{2},\hat{\nu}_{1},\gamma)$ (63) $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}f_{0}(\hat{c}_{2},\hat{\nu}_{1},\hat{\gamma})$
$\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\left(-\sum_{i=1}^{n}\frac{\hat{\gamma}^{2}{\bf
s}_{i}^{4}{\bf c}_{i}^{2}}{1+\hat{\gamma}{\bf
s}_{i}^{2}}+\frac{\alpha\left(\hat{c}_{2}^{2}+\bar{\sigma}^{2}\right)}{\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{1+\hat{\gamma}{\bf s}_{i}^{2}}}+\hat{\gamma}\sum_{i=1}^{n}{\bf
s}_{i}^{2}{\bf c}_{i}^{2}-\hat{\gamma}\hat{c}_{2}^{2}\right)$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\left(\sum_{i=1}^{n}\frac{\hat{\gamma}{\bf
s}_{i}^{2}{\bf c}_{i}^{2}}{1+\hat{\gamma}{\bf
s}_{i}^{2}}+\frac{\alpha\left(\hat{c}_{2}^{2}+\bar{\sigma}^{2}\right)}{\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{1+\hat{\gamma}{\bf
s}_{i}^{2}}}-\hat{\gamma}\hat{c}_{2}^{2}\right)$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\sum_{i=1}^{n}\frac{\hat{\gamma}{\bf
s}_{i}^{2}{\bf c}_{i}^{2}}{1+\hat{\gamma}{\bf
s}_{i}^{2}}+\hat{\gamma}\left(\hat{c}_{2}^{2}+\bar{\sigma}^{2}\right)-\hat{\gamma}\hat{c}_{2}^{2}$
$\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\sum_{i=1}^{n}\frac{\hat{\gamma}{\bf
s}_{i}^{2}{\bf c}_{i}^{2}}{1+\hat{\gamma}{\bf
s}_{i}^{2}}+\hat{\gamma}\bar{\sigma}^{2},$

where $\hat{c}_{2}$ and $\hat{\gamma}$ are given through (59), (61), and (62).
For the very same $\hat{c}_{2}$ and $\hat{\gamma}$, we can then from (54)
obtain for the optimal $\nu_{1}$

$\displaystyle\hat{\nu}_{1}=\frac{2\sqrt{\alpha}\sqrt{\hat{c}_{2}^{2}+\bar{\sigma}^{2}}}{\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{1+\hat{\gamma}{\bf
s}_{i}^{2}}}=\frac{2\hat{\gamma}\sqrt{\hat{c}_{2}^{2}+\bar{\sigma}^{2}}}{\sqrt{\alpha}}.$
(64)

We summarize the above discussion in the following lemma.

######  Lemma 2.

(Characterization of random dual) Assume the setup of Theorem 1 with
$\xi_{rd}$ as in (33) and consider a large $n$ linear regime with
$\alpha=\lim_{n\rightarrow\infty}\frac{m}{n}$ that does not change as $n$
grows. Assume that all the considered limiting quantities are well defined and
bounded. Let ${\bf c}=V^{T}\bar{\beta}$, ${\bf s}=\mbox{diag}(\Sigma)$, and
$\bar{\sigma}\triangleq\sigma\sqrt{\lim_{n\rightarrow\infty}\frac{{\rm
tr}\,\left(\overline{\Sigma}\overline{\Sigma}\right)}{m}}$. Moreover, let
$\hat{\gamma}$ be the unique solution of

$\displaystyle\lim_{n\rightarrow\infty}\frac{1}{n}\sum_{i=1}^{n}\frac{\hat{\gamma}{\bf
s}_{i}^{2}}{1+\hat{\gamma}{\bf s}_{i}^{2}}=\alpha.$ (65)

Set

$\displaystyle
a_{2}=\frac{\lim_{n\rightarrow\infty}\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{4}}{\left(1+\hat{\gamma}{\bf
s}_{i}^{2}\right)^{2}}}{\left(\lim_{n\rightarrow\infty}\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{1+\hat{\gamma}{\bf
s}_{i}^{2}}\right)^{2}}=\frac{\hat{\gamma}^{2}}{\alpha^{2}}\lim_{n\rightarrow\infty}\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{4}}{\left(1+\hat{\gamma}{\bf s}_{i}^{2}\right)^{2}}.$ (66)

One then has

$\displaystyle\xi_{rd}$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{{\bf g},{\bf h},{\bf
v}}f_{rd}({\bf g},{\bf h},{\bf
v})=\lim_{n\rightarrow\infty}\sum_{i=1}^{n}\frac{\hat{\gamma}{\bf
s}_{i}^{2}{\bf c}_{i}^{2}}{1+\hat{\gamma}{\bf
s}_{i}^{2}}+\hat{\gamma}\bar{\sigma}^{2}$ (67)
$\displaystyle\lim_{n\rightarrow\infty}\hat{c}_{2}^{2}=\frac{\lim_{n\rightarrow\infty}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}{\bf c}_{i}^{2}}{\left(1+\hat{\gamma}{\bf
s}_{i}^{2}\right)^{2}}+\alpha\bar{\sigma}^{2}a_{2}}{1-\alpha a_{2}}$
$\displaystyle\lim_{n\rightarrow\infty}\hat{\nu}_{1}=\frac{2\hat{\gamma}\sqrt{\hat{c}_{2}^{2}+\bar{\sigma}^{2}}}{\sqrt{\alpha}},$

and for any fixed $\epsilon>0$

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{{\bf g},{\bf h},{\bf
v}}\left((1-\epsilon)\xi_{rd}\leq f_{rd}({\bf g},{\bf h},{\bf
v})\leq(1+\epsilon)\xi_{rd}\right)$ $\displaystyle\longrightarrow$
$\displaystyle 1$ $\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{{\bf
g},{\bf h},{\bf v}}\left((1-\epsilon)\hat{c}_{2}^{2}\leq
c_{2}^{2}\leq(1+\epsilon)\hat{c}_{2}^{2}\right)$
$\displaystyle\longrightarrow$ $\displaystyle 1$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{{\bf g},{\bf h},{\bf
v}}\left((1-\epsilon)\hat{\nu}_{1}\leq\nu_{1}\leq(1+\epsilon)\hat{\nu}_{1}\right)$
$\displaystyle\longrightarrow$ $\displaystyle 1.$ (68)

###### Proof.

Follows from the above discussion and trivial concentrations of $f_{rd}({\bf
g},{\bf h},{\bf v})$, $c_{2}$, and $\nu_{1}$. ∎

The above discussion allows us then to also formulate the following theorem.

######  Theorem 2.

(Characterization of GLS estimator) Assume the setup of Lemma 2 and let
$\hat{\beta}=\beta_{gls}$ where $\beta_{gls}$ is as in (15). Also, let
$\hat{\gamma}$, $a_{2}$, and $\hat{c}_{2}$ be as in (65), (66), and (67),
respectively/. Finally let the objective value of the GLS estimating
optimization, $\xi_{gls}$, be as in (25) or (26) and let the GLS estimator
prediction risk, $R(\bar{\beta},\hat{\beta})=R(\bar{\beta},\beta_{gls})$, be
as in (24). Then

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{Z,{\bf v}}\xi_{gls}$
$\displaystyle=$
$\displaystyle\xi_{rp}=\xi_{rd}=\lim_{n\rightarrow\infty}\sum_{i=1}^{n}\frac{\hat{\gamma}{\bf
s}_{i}^{2}{\bf c}_{i}^{2}}{1+\hat{\gamma}{\bf
s}_{i}^{2}}+\hat{\gamma}\bar{\sigma}^{2}$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{Z,{\bf
v}}R(\bar{\beta},\beta_{gls})$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{Z,{\bf
v}}\left(\bar{\beta}-\beta_{gls}\right)^{T}V\Sigma\Sigma
V^{T}\left(\bar{\beta}-\beta_{gls}\right)=\frac{\lim_{n\rightarrow\infty}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}{\bf c}_{i}^{2}}{\left(1+\hat{\gamma}{\bf
s}_{i}^{2}\right)^{2}}+\alpha\bar{\sigma}^{2}a_{2}}{1-\alpha a_{2}}.$

Moreover,

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{Z,{\bf
v}}\left((1-\epsilon){\mathbb{E}}_{Z,{\bf
v}}\xi_{gls}\leq\xi_{gls}\leq(1+\epsilon){\mathbb{E}}_{Z,{\bf
v}}\xi_{gls}\right)$ $\displaystyle\longrightarrow$ $\displaystyle 1$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{Z,{\bf
v}}\left((1-\epsilon){\mathbb{E}}_{Z,{\bf v}}R(\bar{\beta},\beta_{gls})\leq
R(\bar{\beta},\beta_{gls})\leq(1+\epsilon){\mathbb{E}}_{Z,{\bf
v}}R(\bar{\beta},\beta_{gls})\right)$ $\displaystyle\longrightarrow$
$\displaystyle 1.$ (70)

###### Proof.

For the first part of (2), we observe that

$\lim_{n\rightarrow\infty}{\mathbb{E}}_{Z,{\bf
v}}\xi_{gls}=\xi_{rp}\geq\xi_{rd}=\lim_{n\rightarrow\infty}\sum_{i=1}^{n}\frac{\hat{\gamma}{\bf
s}_{i}^{2}{\bf c}_{i}^{2}}{1+\hat{\gamma}{\bf
s}_{i}^{2}}+\hat{\gamma}\bar{\sigma}^{2},$ (71)

holds due to Theorem 1 (in particular, due to the inequality in (34)) and
(67). The underlying convexity and the fact that strong random duality is in
place ensure that all the reversal arguments from [52, 51] apply and that the
reversal inequality in (71) holds as well. For the second part of (2), we
first observe that (24), (37), and (38) imply

$R(\bar{\beta},\beta_{gls})=\left(\bar{\beta}-\beta_{gls}\right)^{T}V\Sigma\Sigma
V^{T}\left(\bar{\beta}-\beta_{gls}\right)=c_{2}^{2}.$ (72)

One then immediately has that a combination of (67) and (72) implies the
second part of (2).

We further observe that (70) is basically rewritten (68) and holds due to the
concentration of $\xi_{gls}$ and $R(\bar{\beta},\beta_{gls})$. In other words,

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{{\bf g},{\bf h},{\bf
v}}\left((1-\epsilon)\xi_{rd}\leq f_{rd}({\bf g},{\bf h},{\bf
v})\leq(1+\epsilon)\xi_{rd}\right)$ $\displaystyle\leq$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{{\bf g},{\bf h},{\bf
v}}\left(f_{rd}({\bf g},{\bf h},{\bf v})\geq(1-\epsilon)\xi_{rd}\right)$ (73)
$\displaystyle\leq$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{Z,{\bf
v}}\left(f_{rp}(Z,{\bf v})\geq(1-\epsilon)\xi_{rd}\right)$ $\displaystyle\leq$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{Z,{\bf
v}}\left(\xi_{gls}\geq(1-\epsilon){\mathbb{E}}_{Z,{\bf v}}\xi_{gls}\right),$

where the first inequality is implied by the probability axioms, the second by
(35), and the third by a combination of (31) and (2). Combining further (68)
and (73) gives

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{Z,{\bf
v}}\left(\xi_{gls}\geq(1-\epsilon){\mathbb{E}}_{Z,{\bf
v}}\xi_{gls}\right)\longrightarrow 1.$ (74)

The reversal arguments of [52, 51] also ensure that one has

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{Z,{\bf
v}}\left(\xi_{gls}\leq(1+\epsilon){\mathbb{E}}_{Z,{\bf
v}}\xi_{gls}\right)\longrightarrow 1.$ (75)

A combination of (74) and (75) finally confirms the concentration in the first
part of (70). Keeping in mind (72), the concentration stated ni the second
part of (70) is literally the same as the one stated in the second part of
(68). ∎

4) _Double checking strong random duality:_ As mentioned above, due to the
underlying convexity, the strong random duality and the reversal arguments of
[51, 52] are in place as well, and the above bounding results are tight and
consequently the exact characterizations.

It is not that difficult to see that when $\bar{\sigma}=\sigma$, the results
of the above theorem match the ones obtained in [24, 16, 17].

###  3.2 Ridge estimator

The mathematical machinery used above for the analysis of the GLS estimator is
very generic. In this section we show how it extends to cover the ridge
estimator. To ensure the easiness of following we will try to parallel the
presentation of the previous sections as closely as possible. However, we
often proceed in a much faster fashion by avoiding repeating same (or fairly
similar) arguments and focusing on the key differences.

Recalling on (18), we introduce the objective value of the underlying ridge
regression as

$\displaystyle\xi_{rr}(\lambda)\triangleq\min_{\beta}\left(\lambda\|\beta\|_{2}^{2}+\frac{1}{m}\|{\bf
y}-X\beta\|_{2}^{2}\right).$ (76)

One should note that the above objective is a function of the ridge parameter
$\lambda$ (throughout the ensuing analysis we take $\lambda$ as a given
nonnegative real number that does not depend on $n$ or any other quantity and
keep it fixed). It is also not that difficult to see that the above
optimization can also be rewritten as

$\displaystyle\xi_{rr}(\lambda)=\min_{\beta,{\bf z},c_{3,s}}$
$\displaystyle\lambda\|\beta\|_{2}^{2}+\frac{c_{3,s}^{2}}{m}$ subject to
$\displaystyle X\beta={\bf y}+{\bf z}$ (77) $\displaystyle\|{\bf
z}\|_{2}=c_{3,s}.$

Recalling on (11) and (12), we can also write a statistical equivalent to (77)

$\displaystyle\xi_{rr}(\lambda)\triangleq\min_{\beta,\|{\bf z}\|_{2}=c_{3,s}}$
$\displaystyle\lambda\|\beta\|_{2}^{2}+\frac{c_{3,s}^{2}}{m}$ subject to
$\displaystyle Z\Sigma V^{T}\beta=Z\Sigma
V^{T}\bar{\beta}+\sigma\overline{U}\overline{\Sigma}{\bf v}+{\bf z}.$ (78)

Following the main RDT algebraic fundamental ideas and writing the Lagrangian
we further have

$\displaystyle\xi_{rr}(\lambda)=\min_{\beta,\|{\bf
z}\|_{2}=c_{3,s}}\max_{\nu}\left(\lambda\|\beta\|_{2}^{2}+\nu^{T}\left(Z\Sigma
V^{T}\beta-Z\Sigma V^{T}\bar{\beta}-\sigma\overline{U}\overline{\Sigma}{\bf
v}-{\bf z}\right)+\frac{c_{3,s}^{2}}{m}\right).$ (79)

To analytically characterize the above problem we again proceed by employing
the remaining portions of the RDT machinery.

####  3.2.1 Handling Ridge estimator via RDT

As earlier, we systematically discuss, one-by-one, four main RDT principles
and start with the algebraic part.

1) _Algebraic characterization:_ The following lemma (basically a ridge
analogue to Lemma 31) summarizes the above algebraic discussions and provides
a convenient representation of the objective $\xi_{rr}(\lambda)$.

######  Lemma 3.

(Algebraic optimization representation) assume the setup of Lemma 31 and let
$\lambda\geq 0$ be a fixed real scalar independent of $n$ or any other
quantity. let $\xi_{rr}(\lambda)$ be as in (76) or (77). Set
${\mathcal{D}}=\\{\beta,{\bf z},c_{3,s}|\beta\in{\mathbb{R}}^{n},{\bf
z}\in{\mathbb{R}}^{m},c_{3,s}\in{\mathbb{R}},\|{\bf z}\|_{2}=c_{3,s}\\}$ and

$\displaystyle f_{rp,r}(Z,{\bf v})$ $\displaystyle\triangleq$
$\displaystyle\min_{{\mathcal{D}}}\max_{\nu}\left(\lambda\|\beta\|_{2}^{2}+\nu^{T}\left(Z\Sigma
V^{T}\beta-Z\Sigma V^{T}\bar{\beta}-\sigma\overline{U}\overline{\Sigma}{\bf
v}-{\bf z}\right)+\frac{c_{3,s}^{2}}{m}\right)\hskip
14.45377pt({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\textbf{random
primal}})$ $\displaystyle\xi_{rp,r}$ $\displaystyle\triangleq$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{Z,{\bf v}}f_{rp,r}(Z,{\bf
v}).$ (80)

Then

$\xi_{rr}(\lambda)=f_{rp,r}(Z,{\bf
v})\quad\mbox{and}\quad\lim_{n\rightarrow\infty}{\mathbb{E}}_{Z,{\bf
v}}\xi_{rr}(\lambda)=\xi_{rp,r}.$ (81)

###### Proof.

Follows automatically via the Lagrangian from (79). ∎

Clearly, assuming that $V$, $\Sigma$, $\overline{U}$, $\overline{\Sigma}$,
$\sigma$, and $\beta$ are fixed and given, the above lemma holds for any $Z$
and ${\bf v}$. The RDT proceeds by imposing a statistics on $Z$ and ${\bf v}$.

2) _Determining the random dual:_ As earlier, we utilize the concentration of
measure, which here implies that for any fixed $\epsilon>0$, one can write
(see, e.g. [46, 52, 47])

$\lim_{n\rightarrow\infty}{\mathbb{P}}_{Z,{\bf v}}\left(\frac{|f_{rp,r}(Z,{\bf
v})-{\mathbb{E}}_{Z,{\bf v}}(f_{rp,r}(Z,{\bf v}))|}{{\mathbb{E}}_{Z,{\bf
v}}(f_{rp,r}(Z,{\bf v}))}>\epsilon\right)\longrightarrow 0.$ (82)

We then have the following random dual ridge analogue to Theorem 1).

######  Theorem 3.

(Objective characterization via random dual – Ridge estimator) Assume the
setup of Lemma 81 and Theorem 1. Set

$\displaystyle f_{rd,r}({\bf g},{\bf h},{\bf v})$ $\displaystyle\triangleq$
$\displaystyle\min_{{\mathcal{D}}}\max_{\nu}\left(\lambda\|\beta\|_{2}^{2}+c_{2}\nu^{T}{\bf
g}+\|\nu\|_{2}{\bf h}^{T}\Sigma
V^{T}\left(\beta-\bar{\beta}\right)-\sigma\nu^{T}\overline{U}\overline{\Sigma}{\bf
v}-\nu^{T}{\bf z}+\frac{c_{3,s}^{2}}{m}\right)$ $\displaystyle\hskip
310.76122pt({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\textbf{random
dual}})$ $\displaystyle\xi_{rd,r}$ $\displaystyle\triangleq$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{{\bf g},{\bf h},{\bf
v}}f_{rd,r}({\bf g},{\bf h},{\bf v}).\vspace{-.0in}$ (83)

One then has

$\displaystyle\xi_{rd,r}$ $\displaystyle\triangleq$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{{\bf g},{\bf h},{\bf
v}}f_{rd,r}({\bf g},{\bf h},{\bf
v})\leq\lim_{n\rightarrow\infty}{\mathbb{E}}_{Z,{\bf v}}f_{rp,r}(Z,{\bf
v})\triangleq\xi_{rp,r}.\vspace{-.0in}$ (84)

and

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{{\bf g},{\bf h},{\bf
v}}\left(f_{rd,r}({\bf g},{\bf h},{\bf
v})\geq(1-\epsilon)\xi_{rd,r}\right)\leq\lim_{n\rightarrow\infty}{\mathbb{P}}_{Z,{\bf
v}}\left(f_{rp,r}(Z,{\bf v})\geq(1-\epsilon)\xi_{rd,r}\right).$ (85)

###### Proof.

As the proof of Theorem 1, it follows immediately as a direct application of
the Gordon’s probabilistic comparison theorem (see, e.g., Theorem B in [21]
and also Theorem 1, Corollary 1, and Section 2.7.2 in [53]). ∎

3) _Handling the random dual:_ We start by solving the inner maximization over
$\nu$ and obtain analogously to (36)

$\displaystyle f_{rd,r}({\bf g},{\bf h},{\bf v})$ $\displaystyle\triangleq$
$\displaystyle\min_{\beta,\|{\bf z}\|_{2}={\bf
c}_{3,s}}\max_{\nu}\left(\|\beta\|_{2}^{2}+c_{2}\nu^{T}{\bf g}+\|\nu\|_{2}{\bf
h}^{T}\Sigma
V^{T}\left(\beta-\bar{\beta}\right)-\sigma\nu^{T}\overline{U}\overline{\Sigma}{\bf
v}-\nu^{T}{\bf z}+\frac{c_{3,s}^{2}}{m}\right)$ (86) $\displaystyle=$
$\displaystyle\min_{{\bf x},\|{\bf z}\|_{2}=c_{3,s},c_{2}\geq
0}\max_{\nu_{s}\geq 0}\left(\lambda\|{\bf x}\|_{2}^{2}+\nu_{s}{\bf
h}^{T}\Sigma\left({\bf x}-{\bf c}\right)+\nu_{s}\|c_{2}{\bf
g}-\sigma\overline{U}\overline{\Sigma}{\bf v}-{\bf
z}\|_{2}+\frac{c_{3,s}^{2}}{m}\right),$

where ${\bf x},{\bf c},\nu_{s},$ and $c_{2}$ are as in (37) and (38). After
setting

$\displaystyle{\mathcal{L}}_{r}\left({\bf x},{\bf z},{\bf
c}_{3,s},c_{2},\nu_{s};{\bf g},{\bf h},{\bf v}\right)\triangleq\lambda\|{\bf
x}\|_{2}^{2}+\nu_{s}{\bf h}^{T}\Sigma\left({\bf x}-{\bf
c}\right)+\nu_{s}\|c_{2}{\bf g}-\sigma\overline{U}\overline{\Sigma}{\bf
v}-{\bf z}\|_{2}+\frac{c_{3,s}^{2}}{m},$ (87)

we rewrite (86) as

$\displaystyle f_{rd,r}({\bf g},{\bf h},{\bf v})=\min_{{\bf x},\|{\bf
z}\|_{2}=c_{3,s},c_{2}\geq 0}\max_{\nu_{s}\geq 0}{\mathcal{L}}_{r}\left({\bf
x},{\bf z},c_{3,s},c_{2},\nu_{s};{\bf g},{\bf h},{\bf v}\right).$ (88)

Keeping $c_{3,s}$, $c_{2}$, and $\nu_{s}$ fixed, we, analogously to (41),
consider the following minimization over ${\bf x}$ and ${\bf z}$

$\displaystyle{\mathcal{L}}_{1,r}\left(c_{3,s},c_{2},\nu_{s}\right)\triangleq\min_{{\bf
x},{\bf z}}$ $\displaystyle\lambda\|{\bf x}\|_{2}^{2}+\nu_{s}{\bf
h}^{T}\Sigma\left({\bf x}-{\bf c}\right)+\nu_{s}\|c_{2}{\bf
g}-\sigma\overline{U}\overline{\Sigma}{\bf v}-{\bf
z}\|_{2}+\frac{c_{3,s}^{2}}{m}$ subject to $\displaystyle\|\Sigma\left({\bf
x}-{\bf c}\right)\|_{2}=c_{2},\|{\bf z}\|_{2}=c_{3,s}.$ (89)

To lighten the notation, we again keep the functional dependence on randomness
(${\bf g},{\bf h},{\bf v}$) implicit. We then, analogously to (42), further
have

$\displaystyle{\mathcal{L}}_{1,r}\left(c_{3,s},c_{2},\nu_{s}\right)$
$\displaystyle=$ $\displaystyle\max_{\gamma}\min_{{\bf x},\|{\bf
z}\|_{2}=c_{3,s}}{\mathcal{L}}_{2,r}\left({\bf x},{\bf
z},\gamma;c_{3,s},c_{2},\nu_{s}\right),$ (90)

with

$\displaystyle{\mathcal{L}}_{2,r}\left({\bf x},{\bf
z},\gamma;c_{3,s},c_{2},\nu_{s}\right)$ $\displaystyle\triangleq$
$\displaystyle\lambda\|{\bf x}\|_{2}^{2}+\nu_{s}{\bf h}^{T}\Sigma\left({\bf
x}-{\bf c}\right)+\nu_{s}\|c_{2}{\bf
g}-\sigma\overline{U}\overline{\Sigma}{\bf v}-{\bf
z}\|_{2}+\frac{c_{3,s}^{2}}{m}$ (91) $\displaystyle+\gamma\|\Sigma\left({\bf
x}-{\bf c}\right)\|_{2}^{2}-\gamma c_{2}^{2}.$

Analogously to (46), we then have for optimal ${\bf x}$

$\displaystyle\hat{{\bf x}}=\left(\lambda
I+\gamma\Sigma\Sigma\right)^{-1}\left(-\frac{1}{2}\nu_{s}\Sigma{\bf
h}+\gamma\Sigma\Sigma{\bf c}\right),$ (92)

which (together with appropriate scaling
$\nu_{s}\rightarrow\frac{\nu_{1}}{\sqrt{n}}$ (where $\nu_{1}$ does not change
as $n$ grows)) gives the following analogue to (47)

$\displaystyle{\mathcal{L}}_{2,r}\left(\hat{{\bf x}},{\bf
z},\gamma;c_{3,s},c_{2},\nu_{1}\right)$ $\displaystyle=$
$\displaystyle-\left(-\frac{1}{2\sqrt{n}}\nu_{1}\Sigma{\bf
h}+\gamma\Sigma\Sigma{\bf c}\right)^{T}\left(\lambda
I+\gamma\Sigma\Sigma\right)^{-1}\left(-\frac{1}{2\sqrt{n}}\nu_{1}\Sigma{\bf
h}+\gamma\Sigma\Sigma{\bf c}\right)$
$\displaystyle-\frac{1}{\sqrt{n}}\nu_{1}{\bf h}^{T}\Sigma{\bf
c}+\frac{1}{\sqrt{n}}\nu_{1}\|c_{2}{\bf
g}-\sigma\overline{U}\overline{\Sigma}{\bf v}-{\bf
z}\|_{2}+\frac{c_{3,s}^{2}}{m}+\gamma{\bf c}^{T}\Sigma\Sigma{\bf c}-\gamma
c_{2}^{2}.$

One then also easily obtains for optimal ${\bf z}$

$\displaystyle\hat{{\bf z}}=c_{3,s}\frac{c_{2}{\bf
g}-\sigma\overline{U}\overline{\Sigma}{\bf v}}{\|c_{2}{\bf
g}-\sigma\overline{U}\overline{\Sigma}{\bf v}\|_{2}},$ (94)

which together with (LABEL:eq:ridgeta18a0b4c1) gives

$\displaystyle{\mathcal{L}}_{2,r}\left(\hat{{\bf x}},\hat{{\bf
z}},\gamma;c_{3,s},c_{2},\nu_{1}\right)$ $\displaystyle=$
$\displaystyle-\left(-\frac{1}{2\sqrt{n}}\nu_{1}\Sigma{\bf
h}+\gamma\Sigma\Sigma{\bf c}\right)^{T}\left(\lambda
I+\gamma\Sigma\Sigma\right)^{-1}\left(-\frac{1}{2\sqrt{n}}\nu_{1}\Sigma{\bf
h}+\gamma\Sigma\Sigma{\bf c}\right)$
$\displaystyle-\frac{1}{\sqrt{n}}\nu_{1}{\bf h}^{T}\Sigma{\bf
c}+\frac{1}{\sqrt{n}}\nu_{1}|\|c_{2}{\bf
g}-\sigma\overline{U}\overline{\Sigma}{\bf
v}\|_{2}-c_{3,s}|+\frac{c_{3,s}^{2}}{m}+\gamma{\bf c}^{T}\Sigma\Sigma{\bf
c}-\gamma c_{2}^{2}.$

Utilizing appropriate scaling $c_{3}\rightarrow\frac{c_{3,s}}{\sqrt{m}}$ and
keeping $c_{3}$, $c_{2}$, $\nu_{1}$, and $\gamma$ fixed, we then, relying on
concentrations, find analogously to (LABEL:eq:ta18a0b4c3)

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{{\bf g},{\bf h},{\bf
v}}{\mathcal{L}}_{2,r}\left(\hat{{\bf x}},\hat{{\bf
z}},\gamma;c_{3},c_{2},\nu_{1}\right)$
$\displaystyle=\lim_{n\rightarrow\infty}{\mathbb{E}}\Bigg{(}\Big{.}-\left(-\frac{\nu_{1}}{2\sqrt{n}}\Sigma{\bf
h}+\gamma\Sigma\Sigma{\bf c}\right)^{T}\left(\lambda
I+\gamma\Sigma\Sigma\right)^{-1}\left(-\frac{\nu_{1}}{2\sqrt{n}}\Sigma{\bf
h}+\gamma\Sigma\Sigma{\bf c}\right)$
$\displaystyle\quad-\frac{1}{\sqrt{n}}\nu_{1}{\bf h}^{T}\Sigma{\bf
c}+\frac{1}{\sqrt{n}}\nu_{1}|\|c_{2}{\bf
g}-\sigma\overline{U}\overline{\Sigma}{\bf
v}\|_{2}-c_{3}m|+c_{3}^{2}+\gamma{\bf c}^{T}\Sigma\Sigma{\bf c}-\gamma
c_{2}^{2}\Big{.}\Bigg{)}$
$\displaystyle=\lim_{n\rightarrow\infty}\Bigg{(}\Big{.}-\frac{\nu_{1}^{2}}{4n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\gamma{\bf s}_{i}^{2}}-\sum_{i=1}^{n}\frac{\gamma^{2}{\bf
s}_{i}^{4}{\bf c}_{i}^{2}}{\lambda+\gamma{\bf
s}_{i}^{2}}+\nu_{1}\sqrt{\alpha}\left|\sqrt{c_{2}^{2}+\bar{\sigma}^{2}}-c_{3}\right|+c_{3}^{2}$
$\displaystyle\quad+\gamma\sum_{i=1}^{n}{\bf s}_{i}^{2}{\bf c}_{i}^{2}-\gamma
c_{2}^{2}\Big{.}\Bigg{)},$

with $\bar{\sigma}$ as in(50). A combination of (87)-(90),
(LABEL:eq:ridgeta18a0b4c1d1), and (LABEL:eq:ridgeta18a0b4c3) allows us to
arrive at the following optimization

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{{\bf g},{\bf h},{\bf
v}}f_{rd,r}({\bf g},{\bf h},{\bf v})$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\min_{c_{3},c_{2}\geq
0}\max_{\nu_{1}\geq 0,\gamma}f_{0,r}(c_{2},\nu_{1},\gamma),$ (97)

where

$\displaystyle
f_{0,r}(c_{3},c_{2},\nu_{1},\gamma)\triangleq-\frac{\nu_{1}^{2}}{4n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\gamma{\bf s}_{i}^{2}}-\sum_{i=1}^{n}\frac{\gamma^{2}{\bf
s}_{i}^{4}{\bf c}_{i}^{2}}{\lambda+\gamma{\bf
s}_{i}^{2}}+\nu_{1}\sqrt{\alpha}\left|\sqrt{c_{2}^{2}+\bar{\sigma}^{2}}-c_{3}\right|+c_{3}^{2}+\gamma\sum_{i=1}^{n}{\bf
s}_{i}^{2}{\bf c}_{i}^{2}-\gamma c_{2}^{2}.$ (98)

After taking the derivative with respect to $\nu_{1}$ we, analogously to (54),
find the following optimal $\nu_{1}$

$\displaystyle\hat{\nu}_{1}=\frac{2\sqrt{\alpha}\left|\sqrt{c_{2}^{2}+\bar{\sigma}^{2}}-c_{3}\right|}{\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\gamma{\bf s}_{i}^{2}}}.$ (99)

which then, together with (98), gives

$\max_{\nu_{1}\geq
0}f_{0,r}(c_{3},c_{2},\nu_{1},\gamma)=f_{0,r}(c_{3},c_{2},\hat{\nu}_{1},\gamma)=-\sum_{i=1}^{n}\frac{\gamma^{2}{\bf
s}_{i}^{4}{\bf c}_{i}^{2}}{\lambda+\gamma{\bf
s}_{i}^{2}}+\frac{\alpha\left(\sqrt{c_{2}^{2}+\bar{\sigma}^{2}}-c_{3}\right)^{2}}{\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\gamma{\bf s}_{i}^{2}}}+c_{3}^{2}+\gamma\sum_{i=1}^{n}{\bf
s}_{i}^{2}{\bf c}_{i}^{2}-\gamma c_{2}^{2}.$ (100)

Combining (97) and (100) we obtain

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{{\bf g},{\bf h},{\bf
v}}f_{rd,r}({\bf g},{\bf h},{\bf v})$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\min_{c_{3},c_{2}\geq
0}\max_{\gamma}f_{0,r}(c_{3},c_{2},\hat{\nu}_{1},\gamma),$ (101)

with $f_{0,r}(c_{3},c_{2},\hat{\nu}_{1},\gamma)$ (concave in $\gamma$ and
convex in $c_{3}$) as in (100). After taking the derivative with respect to
$c_{3}$, we find the following optimal $c_{3}$

$\displaystyle\hat{c}_{3}=\frac{\sqrt{c_{2}^{2}+\bar{\sigma}^{2}}}{1+\frac{1}{\alpha
n}\sum_{i=1}^{n}\frac{{\bf s}_{i}^{2}}{\lambda+\gamma{\bf s}_{i}^{2}}},$ (102)

which, together with (100), gives

$\displaystyle\max_{c_{3}\geq
0}f_{0,r}(c_{3},c_{2},\hat{\nu}_{1},\gamma)=f_{0,r}(\hat{c}_{3},c_{2},\hat{\nu}_{1},\gamma)=-\sum_{i=1}^{n}\frac{\gamma^{2}{\bf
s}_{i}^{4}{\bf c}_{i}^{2}}{\lambda+\gamma{\bf
s}_{i}^{2}}+\frac{c_{2}^{2}+\bar{\sigma}^{2}}{1+\frac{1}{\alpha
n}\sum_{i=1}^{n}\frac{{\bf s}_{i}^{2}}{\lambda+\gamma{\bf
s}_{i}^{2}}}+\gamma\sum_{i=1}^{n}{\bf s}_{i}^{2}{\bf c}_{i}^{2}-\gamma
c_{2}^{2}.$ (103)

Taking derivatives with respect $c_{2}$ and $\gamma$ and equalling them to
zero, we further have

$\displaystyle\frac{df_{0,r}(\hat{c}_{3},c_{2},\hat{\nu}_{1},\gamma)}{dc_{2}}=\frac{2c_{2}}{1+\frac{1}{\alpha
n}\sum_{i=1}^{n}\frac{{\bf s}_{i}^{2}}{\lambda+\gamma{\bf s}_{i}^{2}}}-2\gamma
c_{2}=0.$ (104)

and

$\displaystyle\frac{df_{0,r}(\hat{c}_{3},c_{2},\hat{\nu}_{1},\gamma)}{d\gamma}$
$\displaystyle=$ $\displaystyle-\sum_{i=1}^{n}\frac{2\gamma{\bf s}_{i}^{4}{\bf
c}_{i}^{2}}{\lambda+\gamma{\bf s}_{i}^{2}}+\sum_{i=1}^{n}\frac{\gamma^{2}{\bf
s}_{i}^{6}{\bf c}_{i}^{2}}{\left(\lambda+\gamma{\bf
s}_{i}^{2}\right)^{2}}+\frac{\left(c_{2}^{2}+\bar{\sigma}^{2}\right)}{\left(1+\frac{1}{\alpha
n}\sum_{i=1}^{n}\frac{{\bf s}_{i}^{2}}{\lambda+\gamma{\bf
s}_{i}^{2}}\right)^{2}}\left(\frac{1}{\alpha n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{4}}{\left(\lambda+\gamma{\bf s}_{i}^{2}\right)^{2}}\right)$ (105)
$\displaystyle+\sum_{i=1}^{n}{\bf s}_{i}^{2}{\bf c}_{i}^{2}-c_{2}^{2}=0.$

From (104) we first have that the optimal $\hat{\gamma}$ satisfies the
following equation

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\frac{\hat{\gamma}{\bf
s}_{i}^{2}}{\lambda+\hat{\gamma}{\bf s}_{i}^{2}}=\alpha(1-\hat{\gamma}).$
(106)

For such a $\hat{\gamma}$ we then from (105) have that the optimal
$\hat{c}_{2}$ satisfies the following equation

$\displaystyle\sum_{i=1}^{n}\frac{\lambda^{2}{\bf s}_{i}^{2}{\bf
c}_{i}^{2}}{\left(\lambda+\hat{\gamma}{\bf
s}_{i}^{2}\right)^{2}}+\frac{\left(\hat{c}_{2}^{2}+\bar{\sigma}^{2}\right)}{\left(1+\frac{1}{\alpha
n}\sum_{i=1}^{n}\frac{{\bf s}_{i}^{2}}{\lambda+\hat{\gamma}{\bf
s}_{i}^{2}}\right)^{2}}\left(\frac{1}{\alpha n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{4}}{\left(\lambda+\hat{\gamma}{\bf
s}_{i}^{2}\right)^{2}}\right)-\hat{c}_{2}^{2}=0.$ (107)

Setting

$\displaystyle a_{2,r}=\frac{\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{4}}{\left(\lambda+\hat{\gamma}{\bf
s}_{i}^{2}\right)^{2}}}{\left(\alpha+\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\hat{\gamma}{\bf s}_{i}^{2}}\right)^{2}},$ (108)

we from (107) find

$\displaystyle\hat{c}_{2}^{2}=\frac{\sum_{i=1}^{n}\frac{\lambda^{2}{\bf
s}_{i}^{2}{\bf c}_{i}^{2}}{\left(\lambda+\hat{\gamma}{\bf
s}_{i}^{2}\right)^{2}}+\alpha\bar{\sigma}^{2}a_{2,r}}{1-\alpha a_{2,r}}.$
(109)

From (100) and (101), we then have

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{{\bf g},{\bf h},{\bf
v}}f_{rd,r}({\bf g},{\bf h},{\bf v})$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\min_{c_{2}\geq
0}\max_{\gamma}f_{0}(\hat{c}_{3},c_{2},\hat{\nu}_{1},\gamma)$ (110)
$\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}f_{0}(\hat{c}_{3},\hat{c}_{2},\hat{\nu}_{1},\hat{\gamma})$
$\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\left(-\sum_{i=1}^{n}\frac{\hat{\gamma}^{2}{\bf
s}_{i}^{4}{\bf c}_{i}^{2}}{\lambda+\hat{\gamma}{\bf
s}_{i}^{2}}+\frac{\alpha\left(\hat{c}_{2}^{2}+\bar{\sigma}^{2}\right)}{\alpha+\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\hat{\gamma}{\bf
s}_{i}^{2}}}+\hat{\gamma}\sum_{i=1}^{n}{\bf s}_{i}^{2}{\bf
c}_{i}^{2}-\hat{\gamma}\hat{c}_{2}^{2}\right)$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\left(\sum_{i=1}^{n}\frac{\hat{\gamma}{\bf
s}_{i}^{2}{\bf c}_{i}^{2}}{\lambda+\hat{\gamma}{\bf
s}_{i}^{2}}+\frac{\alpha\left(\hat{c}_{2}^{2}+\bar{\sigma}^{2}\right)}{\alpha+\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\hat{\gamma}{\bf
s}_{i}^{2}}}-\hat{\gamma}\hat{c}_{2}^{2}\right)$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\sum_{i=1}^{n}\frac{\hat{\gamma}{\bf
s}_{i}^{2}{\bf c}_{i}^{2}}{\lambda+\hat{\gamma}{\bf
s}_{i}^{2}}+\hat{\gamma}\left(\hat{c}_{2}^{2}+\bar{\sigma}^{2}\right)-\hat{\gamma}\hat{c}_{2}^{2}$
$\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\sum_{i=1}^{n}\frac{\hat{\gamma}{\bf
s}_{i}^{2}{\bf c}_{i}^{2}}{\lambda+\hat{\gamma}{\bf
s}_{i}^{2}}+\hat{\gamma}\bar{\sigma}^{2},$

where $\hat{c}_{2}$ and $\hat{\gamma}$ are given through (106), (108), and
(109). For the very same $\hat{c}_{2}$ and $\hat{\gamma}$, we can then from
(102) and (99) obtain for the optimal $c_{3}$ and $\nu_{1}$

$\displaystyle\hat{c}_{3}=\frac{\sqrt{\hat{c}_{2}^{2}+\bar{\sigma}^{2}}}{1+\frac{1}{\alpha
n}\sum_{i=1}^{n}\frac{{\bf s}_{i}^{2}}{\lambda+\gamma{\bf
s}_{i}^{2}}}=\hat{\gamma}\sqrt{\hat{c}_{2}^{2}+\bar{\sigma}^{2}},$ (111)
$\displaystyle\hat{\nu}_{1}=\frac{2\sqrt{\alpha}\left|\sqrt{\hat{c}_{2}^{2}+\bar{\sigma}^{2}}-\hat{c}_{3}\right|}{\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\hat{\gamma}{\bf
s}_{i}^{2}}}=\frac{2\hat{\gamma}\left|\sqrt{\hat{c}_{2}^{2}+\bar{\sigma}^{2}}-\hat{c}_{3}\right|}{\sqrt{\alpha}(1-\hat{\gamma})}=\frac{2\hat{\gamma}\sqrt{\hat{c}_{2}^{2}+\bar{\sigma}^{2}}}{\sqrt{\alpha}}.$
(112)

For the completeness we also determine the optimal
$\hat{c}_{4}^{2}=\lim_{n\rightarrow\infty}{\mathbb{E}}_{{\bf g},{\bf h},{\bf
v}}\|\hat{{\bf x}}\|_{2}^{2}$

$\displaystyle\hat{c}_{4}^{2}$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{{\bf g},{\bf h},{\bf
v}}\|\hat{{\bf x}}\|_{2}^{2}$ (113) $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{{\bf g},{\bf h},{\bf
v}}\left\|\left(\lambda
I+\hat{\gamma}\Sigma\Sigma\right)^{-1}\left(-\frac{\hat{\nu}_{1}}{2\sqrt{n}}\Sigma{\bf
h}+\gamma\Sigma\Sigma{\bf c}\right)\right\|_{2}^{2}$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\frac{\hat{\nu}_{1}^{2}}{4n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\left(\lambda+\hat{\gamma}{\bf
s}_{i}^{2}\right)^{2}}+\lim_{n\rightarrow\infty}\sum_{i=1}^{n}\frac{\hat{\gamma}^{2}{\bf
s}_{i}^{4}{\bf c}_{i}^{2}}{\left(\lambda+\hat{\gamma}{\bf
s}_{i}^{2}\right)^{2}}.$

We summarize the above discussion in the following theorem (basically a joint
Ridge analogoue to the GLS related Lemma 2 and Theorem 2).

######  Theorem 4.

(Characterization of Ridge estimator) For a given fixed real positive number
$\lambda$, assume the setup of Lemma 81 and Theorem 3 with $\xi_{rr}(\lambda)$
as in (76) or (77) and $\xi_{rd,r}$ as in (83). Let
$\hat{\beta}=\beta_{rr}(\lambda)$ where $\beta_{rr}(\lambda)$ is as in (18).
Also, let the Ridge estimator prediction risk,
$R(\bar{\beta},\hat{\beta})=R(\bar{\beta},\beta_{rr}(\lambda))$, be defined
via (24). Assuming a large $n$ linear regime with
$\alpha=\lim_{n\rightarrow\infty}\frac{m}{n}$, let unique $\hat{\gamma}$ be
such that

$\displaystyle\lim_{n\rightarrow\infty}\frac{1}{n}\sum_{i=1}^{n}\frac{\hat{\gamma}{\bf
s}_{i}^{2}}{\lambda+\hat{\gamma}{\bf s}_{i}^{2}}=\alpha(1-\hat{\gamma}).$
(114)

Set

$\displaystyle
a_{2}=\frac{\lim_{n\rightarrow\infty}\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{4}}{\left(\lambda+\hat{\gamma}{\bf
s}_{i}^{2}\right)^{2}}}{\left(\alpha+\lim_{n\rightarrow\infty}\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\hat{\gamma}{\bf
s}_{i}^{2}}\right)^{2}}=\frac{\hat{\gamma}^{2}}{\alpha^{2}}\lim_{n\rightarrow\infty}\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{4}}{\left(\lambda+\hat{\gamma}{\bf s}_{i}^{2}\right)^{2}}.$ (115)

One then has

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{Z,{\bf
v}}\xi_{rr}(\lambda)$ $\displaystyle=$
$\displaystyle\xi_{rp,r}=\xi_{rd,r}=\lim_{n\rightarrow\infty}{\mathbb{E}}_{{\bf
g},{\bf h},{\bf v}}f_{rd,r}({\bf g},{\bf h},{\bf
v})=\lim_{n\rightarrow\infty}\sum_{i=1}^{n}\frac{\hat{\gamma}{\bf
s}_{i}^{2}{\bf c}_{i}^{2}}{\lambda+\hat{\gamma}{\bf
s}_{i}^{2}}+\hat{\gamma}\bar{\sigma}^{2}$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{Z,{\bf
v}}R(\bar{\beta},\beta_{rr}(\lambda))$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\hat{c}_{2}^{2}=\frac{\lim_{n\rightarrow\infty}\sum_{i=1}^{n}\frac{\lambda^{2}{\bf
s}_{i}^{2}{\bf c}_{i}^{2}}{\left(\lambda+\hat{\gamma}{\bf
s}_{i}^{2}\right)^{2}}+\alpha\bar{\sigma}^{2}a_{2}}{1-\alpha a_{2}}$
$\displaystyle\lim_{n\rightarrow\infty}\hat{\nu}_{1}=\frac{2\hat{\gamma}\sqrt{\hat{c}_{2}^{2}+\bar{\sigma}^{2}}}{\sqrt{\alpha}}$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{Z,{\bf v}}\|{\bf
y}-X\beta_{rr}(\lambda)\|_{2}^{2}$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\hat{c}_{3}^{2}=\hat{\gamma}^{2}(\hat{c}_{2}^{2}+\bar{\sigma}^{2})$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{Z,{\bf
v}}\|\beta_{rr}(\lambda)\|_{2}^{2}$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\hat{c}_{4}^{2}=\lim_{n\rightarrow\infty}\frac{\hat{\nu}_{1}^{2}}{4n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\left(\lambda+\hat{\gamma}{\bf
s}_{i}^{2}\right)^{2}}+\lim_{n\rightarrow\infty}\sum_{i=1}^{n}\frac{\hat{\gamma}^{2}{\bf
s}_{i}^{4}{\bf c}_{i}^{2}}{\left(\lambda+\hat{\gamma}{\bf
s}_{i}^{2}\right)^{2}},$ (116)

and for any fixed $\epsilon>0$

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{Z,{\bf
v}}\left((1-\epsilon){\mathbb{E}}_{Z,{\bf
v}}\xi_{rr}(\lambda)\leq\xi_{rr}(\lambda)\leq(1+\epsilon){\mathbb{E}}_{Z,{\bf
v}}\xi_{rr}(\lambda)\right)$ $\displaystyle\longrightarrow$ $\displaystyle 1$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{Z,{\bf
v}}\left((1-\epsilon){\mathbb{E}}_{Z,{\bf
v}}R(\bar{\beta},\beta_{rr}(\lambda))\leq
R(\bar{\beta},\beta_{rr}(\lambda))\leq(1+\epsilon){\mathbb{E}}_{Z,{\bf
v}}R(\bar{\beta},\beta_{rr}(\lambda))\right)$ $\displaystyle\longrightarrow$
$\displaystyle 1$ $\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{{\bf
g},{\bf h},{\bf
v}}\left((1-\epsilon)\hat{\nu}_{1}\leq\nu_{1}\leq(1+\epsilon)\hat{\nu}_{1}\right)$
$\displaystyle\longrightarrow$ $\displaystyle 1$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{Z,{\bf
v}}\left((1-\epsilon){\mathbb{E}}_{Z,{\bf v}}\|{\bf
y}-X\beta_{rr}(\lambda)\|_{2}^{2}\leq\|{\bf
y}-X\beta_{rr}(\lambda)\|_{2}^{2}\leq(1+\epsilon){\mathbb{E}}_{Z,{\bf
v}}\|{\bf y}-X\beta_{rr}(\lambda)\|_{2}^{2}\right)$
$\displaystyle\longrightarrow$ $\displaystyle 1$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{Z,{\bf
v}}\left((1-\epsilon){\mathbb{E}}_{Z,{\bf
v}}\|\beta_{rr}(\lambda)\|_{2}^{2}\leq\|\beta_{rr}(\lambda)\|_{2}^{2}\leq(1+\epsilon){\mathbb{E}}_{Z,{\bf
v}}\|\beta_{rr}(\lambda)\|_{2}^{2}\right)$ $\displaystyle\longrightarrow$
$\displaystyle 1.$

###### Proof.

Follows from the above discussion, trivial concentrations of $f_{rd,r}({\bf
g},{\bf h},{\bf v})$, $c_{2}$, and $\nu_{1}$, and utilization of literally the
asme arguments as in the proof of Theorem 2. ∎

4) _Double checking strong random duality:_ As earlier due to the underlying
convexity, the strong random duality and the reversal arguments of [51, 52]
are in place as well.

As was the case earlier when we considered the GLS estimator, it is again not
that difficult to see that when $\bar{\sigma}=\sigma$, the results of the
above theorem match the ones obtained in [24, 16, 17].

###  3.3 Precise analysis of the LS estimator

While the formal definition of ridge regression typically assumes that the
value of the ridge parameter $\lambda$ is positive, the mathematical analysis
from Section 3.2 holds unaltered even if $\lambda=0$ provided that $\alpha>1$.
As that is precisely the scenario of the LS estimator (see (21)-(23)), all of
the above results automatically translate. However, many of the evaluations
simplify and one ultimately has the following (much simpler) corollary of
Theorem 4.

######  Corollary 1.

(Characterization of LS estimator) Assume the setup of Theorem 4 with
$\lambda=0$ and $\alpha>1$. Let unique $\hat{\gamma}$ be such that

$\displaystyle\hat{\gamma}=1-\frac{1}{\alpha}.$ (118)

Set

$\displaystyle a_{2}=\frac{1}{\alpha^{2}}.$ (119)

One then has

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{Z,{\bf v}}\xi_{ls}$
$\displaystyle=$ $\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{Z,{\bf
v}}\xi_{rr}(0)=\|\bar{\beta}|_{2}^{2}+\hat{\gamma}\bar{\sigma}^{2}$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{Z,{\bf
v}}R(\bar{\beta},\beta_{ls})$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{Z,{\bf
v}}R(\bar{\beta},\beta_{ls}(0))=\frac{\alpha\bar{\sigma}^{2}a_{2}}{1-\alpha
a_{2}}=\frac{\bar{\sigma}^{2}}{\alpha-1}$
$\displaystyle\lim_{n\rightarrow\infty}\hat{\nu}_{1}=2\bar{\sigma}\frac{\sqrt{\alpha-1}}{\alpha}$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{Z,{\bf v}}\|{\bf
y}-X\beta_{ls}\|_{2}^{2}$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{Z,{\bf v}}\|{\bf
y}-X\beta_{rr}(0)\|_{2}^{2}=\lim_{n\rightarrow\infty}\hat{c}_{3}^{2}=\bar{\sigma}^{2}\frac{\alpha-1}{\alpha}$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{Z,{\bf
v}}\|\beta_{ls}\|_{2}^{2}$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{Z,{\bf
v}}\|\beta_{rr}(0)\|_{2}^{2}=1+\lim_{n\rightarrow\infty}\frac{\hat{\nu}_{1}^{2}}{4\hat{\gamma}^{2}n}\sum_{i=1}^{n}\frac{1}{{\bf
s}_{i}^{2}}=\|\bar{\beta}\|_{2}^{2}+\frac{\bar{\sigma}^{2}}{\alpha-1}\lim_{n\rightarrow\infty}\frac{1}{n}\sum_{i=1}^{n}\frac{1}{{\bf
s}_{i}^{2}},$

and for any fixed $\epsilon>0$

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{Z,{\bf
v}}\left((1-\epsilon){\mathbb{E}}_{Z,{\bf
v}}\xi_{ls}\leq\xi_{ls}\leq(1+\epsilon){\mathbb{E}}_{Z,{\bf
v}}\xi_{ls}\right)$ $\displaystyle\longrightarrow$ $\displaystyle 1$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{Z,{\bf
v}}\left((1-\epsilon){\mathbb{E}}_{Z,{\bf v}}R(\bar{\beta},\beta_{ls})\leq
R(\bar{\beta},\beta_{ls})\leq(1+\epsilon){\mathbb{E}}_{Z,{\bf
v}}R(\bar{\beta},\beta_{ls})\right)$ $\displaystyle\longrightarrow$
$\displaystyle 1$ $\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{{\bf
g},{\bf h},{\bf
v}}\left((1-\epsilon)\hat{\nu}_{1}\leq\nu_{1}\leq(1+\epsilon)\hat{\nu}_{1}\right)$
$\displaystyle\longrightarrow$ $\displaystyle 1$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{Z,{\bf
v}}\left((1-\epsilon){\mathbb{E}}_{Z,{\bf v}}\|{\bf
y}-X\beta_{ls}\|_{2}^{2}\leq\|{\bf
y}-X\beta_{ls}\|_{2}^{2}\leq(1+\epsilon){\mathbb{E}}_{Z,{\bf v}}\|{\bf
y}-X\beta_{ls}\|_{2}^{2}\right)$ $\displaystyle\longrightarrow$ $\displaystyle
1$ $\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{Z,{\bf
v}}\left((1-\epsilon){\mathbb{E}}_{Z,{\bf
v}}\|\beta_{ls}\|_{2}^{2}\leq\|\beta_{ls}\|_{2}^{2}\leq(1+\epsilon){\mathbb{E}}_{Z,{\bf
v}}\|\beta_{ls}\|_{2}^{2}\right)$ $\displaystyle\longrightarrow$
$\displaystyle 1.$ (121)

###### Proof.

The discussion above Theorem 4 holds for $\lambda=0$ as well which implies
that all the expressions given in Theorem 4 are true for $\lambda=0$ as well.
Plugging $\lambda=0$ in (114), (115), and (116) then gives (118), (119), and
(LABEL:eq:lsridgethmaaeq3). ∎

###  3.4 Numerical results

We supplement the above theoretical results with the ones obtained through
numerical simulations. Let a matrix $\bar{{\mathcal{A}}}(q)$ be defined via
its $ij$-th entry, $\bar{{\mathcal{A}}}_{ij}(q)$, in the following way

$\displaystyle\bar{{\mathcal{A}}}_{ij}(q)=q^{|j-i|}.$ (122)

Let then ${\mathcal{A}}(q)$ be

$\displaystyle{\mathcal{A}}(q)=I+\bar{{\mathcal{A}}}(q).$ (123)

For the covariance matrices, we take

$\displaystyle A$ $\displaystyle=$ $\displaystyle{\mathcal{A}}(q)$
$\displaystyle\overline{A}$ $\displaystyle=$
$\displaystyle{\mathcal{A}}(q_{v}).$ (124)

In Figure 1, we choose $q=0.5,q_{v}=0.4$, and $n=600$. The full curves are the
theoretical predictions and the dots are the corresponding simulated values.
Even for fairly small dimensions, we observe an excellent agreement between
the theoretical predictions and simulations results.

Statistical setups in all simulations are chosen to perfectly match the ones
used in the corresponding theoretical analyses. However, as the theoretical
results hold way more generally, we conducted simulations for two additional
(and different) scenarios. In one of them we generated $A$ and $E$ as iid $\pm
1$ Bernoullis and in the other, as iid $\sqrt{12}\mbox{Unif}[-0.5,0.5]$. The
obtained results were virtually identical to those already shown in Figure 1
and there was no point including them..

Figure 1: Prediction risk – all three estimators (GLS, Ridge, and LS); row-
correlated features $X$; Covariance matrices are: $A={\mathcal{A}}(q)$, and
$\overline{A}={\mathcal{A}}(q_{v})$; $q=0.5,q_{v}=0.4$.

##  4 Inter-rows correlations

Models considered so far assumed that all feature vectors $X_{i,:}$ (basically
the rows of matrix $X$) are independent of each other. In this section we show
how the mathematical machinery introduced earlier covers scenarios with
correlated rows of $X$. To that end we now assume for a full rank
$\overline{\overline{A}}\in{\mathbb{R}}^{m\times m}$ that

$\displaystyle X=\overline{\overline{A}}ZA.$ (125)

Let the SVD of $\overline{\overline{A}}$ be given as

$\displaystyle\overline{\overline{A}}=\overline{\overline{U}}\overline{\overline{\Sigma}}\overline{\overline{V}}^{T}.$
(126)

One can then rewrite (1) and (6) as

$\displaystyle{\bf y}=X\bar{\beta}+{\bf
e}=\overline{\overline{A}}ZA\bar{\beta}+\sigma\overline{A}{\bf v}.$ (127)

Using the SVDs ((9) and (126) one can then write

$\displaystyle{\bf
y}=\overline{\overline{A}}ZA\bar{\beta}+\sigma\overline{A}{\bf
v}=\overline{\overline{U}}\overline{\overline{\Sigma}}\overline{\overline{V}}^{T}ZU\Sigma
V^{T}\bar{\beta}+\sigma\overline{U}\overline{\Sigma}\overline{V}^{T}{\bf v}.$
(128)

Due to rotational symmetry of both rows and columns of $Z$ and rows of ${\bf
v}$, (10) and (11) are statistically equivalent to the following

$\displaystyle{\bf
y}=\overline{\overline{U}}\overline{\overline{\Sigma}}Z\Sigma
V^{T}\bar{\beta}+\sigma\overline{U}\overline{\Sigma}{\bf v}.$ (129)

This basically mean that one can view $X$ and ${\bf e}$ as

$\displaystyle X=\overline{\overline{U}}\overline{\overline{\Sigma}}Z\Sigma
V^{T},\quad{\bf e}=\overline{U}\overline{\Sigma}{\bf v}.$ (130)

All three estimators (GLS, Ridge, and LS) analyzed earlier can be analyzed
again within the context of the generalized model given by (129) and (130). In
fact, all Section 3.1 GLS related results including Theorem 2, continue to
hold with only $\bar{\sigma}$ redefined as

$\displaystyle\bar{\sigma}=\sigma\sqrt{\frac{{\rm
tr}\,\left(\overline{\Sigma}\overline{U}^{T}\overline{\overline{U}}\overline{\overline{\Sigma}}\overline{\overline{\Sigma}}\overline{\overline{U}}^{T}\overline{U}\overline{\Sigma}\right)}{m}}.$
(131)

On the other hand the Ridge estimator results need to be carefully
readdressed. We do so by parallelling the presentation of Section 3.2 as
closely as possible. As expected, we proceed in a much faster fashion by
avoiding duplicating already shown arguments and focusing on emphasizing the
key differences.

We start by recognizing that, relying on (129) and (130) one, analogously to
(78), now has

$\displaystyle\bar{\xi}_{rr}(\lambda)\triangleq\min_{\beta,\|{\bf
z}\|_{2}=c_{3,s}}$
$\displaystyle\lambda\|\beta\|_{2}^{2}+\frac{c_{3,s}^{2}}{m}$ subject to
$\displaystyle\overline{\overline{U}}\overline{\overline{\Sigma}}Z\Sigma
V^{T}\beta=\overline{\overline{U}}\overline{\overline{\Sigma}}Z\Sigma
V^{T}\bar{\beta}+\sigma\overline{U}\overline{\Sigma}{\bf v}+{\bf z}.$ (132)

it is also not that difficult to see that writing the Lagrangian gives the
following analogue to (79)

$\displaystyle\bar{\xi}_{rr}(\lambda)=\min_{\beta,\|{\bf
z}\|_{2}=c_{3,s}}\max_{\nu}\left(\lambda\|\beta\|_{2}^{2}+\nu^{T}\left(\overline{\overline{U}}\overline{\overline{\Sigma}}Z\Sigma
V^{T}\beta-\overline{\overline{U}}\overline{\overline{\Sigma}}Z\Sigma
V^{T}\bar{\beta}-\sigma\overline{U}\overline{\Sigma}{\bf v}-{\bf
z}\right)+\frac{c_{3,s}^{2}}{m}\right).$ (133)

For the completeness we also define

$\displaystyle\bar{\beta}_{rr}(\lambda)\triangleq\mbox{arg}\min_{\beta,\|{\bf
z}\|_{2}=c_{3,s}}$
$\displaystyle\lambda\|\beta\|_{2}^{2}+\frac{c_{3,s}^{2}}{m}$ subject to
$\displaystyle\overline{\overline{U}}\overline{\overline{\Sigma}}Z\Sigma
V^{T}\beta=\overline{\overline{U}}\overline{\overline{\Sigma}}Z\Sigma
V^{T}\bar{\beta}+\sigma\overline{U}\overline{\Sigma}{\bf v}+{\bf z}.$ (134)

To analytically characterize the above problem we again utilize the RDT
machinery.

###  4.1 Analysis of the Ridge estimator under $X$ row-correlations

As usual, we proceed by discussing in detail each of the four main RDT
principles.

1) _Algebraic characterization:_ The following lemma is basically a correlated
rows analogue to Lemma 81) and conveniently summarizes the above algebraic
considerations.

######  Lemma 4.

(Algebraic optimization representation) Assume the setup of Lemmas 31 and 81
and let the unitary matrix $\overline{\overline{U}}\in{\mathbb{R}}^{m\times
m}$ and diagonal matrix $\overline{\overline{\Sigma}}\in{\mathbb{R}}^{m\times
m}$ be given. let $\bar{\xi}_{rr}(\lambda)$ be as in (132). Set
${\mathcal{D}}=\\{\beta,{\bf z},c_{3,s}|\beta\in{\mathbb{R}}^{n},{\bf
z}\in{\mathbb{R}}^{m},c_{3,s}\in{\mathbb{R}},\|{\bf z}\|_{2}=c_{3,s}\\}$ and

$\displaystyle\bar{f}_{rp,r}(Z,{\bf v})$
$\displaystyle\triangleq\min_{{\mathcal{D}}}\max_{\nu}\left(\lambda\|\beta\|_{2}^{2}+\nu^{T}\left(\overline{\overline{U}}\overline{\overline{\Sigma}}Z\Sigma
V^{T}\beta-\overline{\overline{U}}\overline{\overline{\Sigma}}Z\Sigma
V^{T}\bar{\beta}-\sigma\overline{U}\overline{\Sigma}{\bf v}-{\bf
z}\right)+\frac{c_{3,s}^{2}}{m}\right)\hskip
1.4457pt({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\textbf{random
primal}})$ $\displaystyle\bar{\xi}_{rp,r}$
$\displaystyle\triangleq\lim_{n\rightarrow\infty}{\mathbb{E}}_{Z,{\bf
v}}\bar{f}_{rp,r}(Z,{\bf v}).$ (135)

Then

$\bar{\xi}_{rr}(\lambda)=\bar{f}_{rp,r}(Z,{\bf
v})\quad\mbox{and}\quad\lim_{n\rightarrow\infty}{\mathbb{E}}_{Z,{\bf
v}}\bar{\xi}_{rr}(\lambda)=\bar{\xi}_{rp,r}.$ (136)

###### Proof.

Follows automatically via the Lagrangian from (133). ∎

2) _Determining the random dual:_ Utilizing concentration

$\lim_{n\rightarrow\infty}{\mathbb{P}}_{Z,{\bf
v}}\left(\frac{|\bar{f}_{rp,r}(Z,{\bf v})-{\mathbb{E}}_{Z,{\bf
v}}(\bar{f}_{rp,r}(Z,{\bf v}))|}{{\mathbb{E}}_{Z,{\bf
v}}(\bar{f}_{rp,r}(Z,{\bf v}))}>\epsilon\right)\longrightarrow 0,$ (137)

we have the following random dual analogue to Theorems 1 and 3.

######  Theorem 5.

(Random dual – Row-correlated $X$ Ridge estimator) Assume the setup of Lemmas
81 and 136 and Theorems 1 and 3. Set

$\displaystyle\bar{f}_{rd,r}({\bf g},{\bf h},{\bf v})$
$\displaystyle\triangleq\min_{{\mathcal{D}}}\max_{\nu}\left(\lambda\|\beta\|_{2}^{2}+c_{2}\nu^{T}\overline{\overline{U}}\overline{\overline{\Sigma}}{\bf
g}+\|\overline{\overline{\Sigma}}\overline{\overline{U}}^{T}\nu\|_{2}{\bf
h}^{T}\Sigma
V^{T}\left(\beta-\bar{\beta}\right)-\sigma\nu^{T}\overline{U}\overline{\Sigma}{\bf
v}-\nu^{T}{\bf z}+\frac{c_{3,s}^{2}}{m}\right)$ $\displaystyle\hskip
325.215pt({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\textbf{random
dual}})$ $\displaystyle\bar{\xi}_{rd,r}$
$\displaystyle\triangleq\lim_{n\rightarrow\infty}{\mathbb{E}}_{{\bf g},{\bf
h},{\bf v}}\bar{f}_{rd,r}({\bf g},{\bf h},{\bf v}).\vspace{-.0in}$ (138)

One then has

$\displaystyle\bar{\xi}_{rd,r}$ $\displaystyle\triangleq$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{{\bf g},{\bf h},{\bf
v}}\bar{f}_{rd,r}({\bf g},{\bf h},{\bf
v})\leq\lim_{n\rightarrow\infty}{\mathbb{E}}_{Z,{\bf v}}\bar{f}_{rp,r}(Z,{\bf
v})\triangleq\bar{\xi}_{rp,r}.\vspace{-.0in}$ (139)

and

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{{\bf g},{\bf h},{\bf
v}}\left(\bar{f}_{rd,r}({\bf g},{\bf h},{\bf
v})\geq(1-\epsilon)\bar{\xi}_{rd,r}\right)\leq\lim_{n\rightarrow\infty}{\mathbb{P}}_{Z,{\bf
v}}\left(\bar{f}_{rp,r}(Z,{\bf v})\geq(1-\epsilon)\bar{\xi}_{rd,r}\right).$
(140)

###### Proof.

As the proof of Theorems 1 and 3, it follows immediately as a direct
application of the Gordon’s probabilistic comparison theorem (see, e.g.,
Theorem B in [21] and also Theorem 1, Corollary 1, and Section 2.7.2 in [53]).
∎

3) _Handling the random dual:_ We start by solving the inner maximization over
$\nu$ and obtain analogously to (36) and (86)

$\displaystyle\bar{f}_{rd,r}({\bf g},{\bf h},{\bf v})$
$\displaystyle\triangleq$ $\displaystyle\min_{\beta,\|{\bf z}\|_{2}={\bf
c}_{3,s}}\max_{\nu}\left(\|\beta\|_{2}^{2}+c_{2}\nu^{T}\overline{\overline{U}}\overline{\overline{\Sigma}}{\bf
g}+\|\overline{\overline{\Sigma}}\overline{\overline{U}}^{T}\nu\|_{2}{\bf
h}^{T}\Sigma
V^{T}\left(\beta-\bar{\beta}\right)-\sigma\nu^{T}\overline{U}\overline{\Sigma}{\bf
v}-\nu^{T}{\bf z}+\frac{c_{3,s}^{2}}{m}\right)$ $\displaystyle=$
$\displaystyle\min_{\beta,\|{\bf z}\|_{2}={\bf
c}_{3,s}}\max_{\nu}\Bigg{(}\Big{.}\|\beta\|_{2}^{2}+c_{2}\nu^{T}\overline{\overline{U}}\overline{\overline{\Sigma}}{\bf
g}+\|\overline{\overline{\Sigma}}\overline{\overline{U}}^{T}\nu\|_{2}{\bf
h}^{T}\Sigma V^{T}\left(\beta-\bar{\beta}\right)$
$\displaystyle-\sigma\nu^{T}\overline{\overline{U}}\overline{\overline{\Sigma}}\overline{\overline{\Sigma}}^{-1}\overline{\overline{U}}^{T}\overline{U}\overline{\Sigma}{\bf
v}-\nu^{T}\overline{\overline{U}}\overline{\overline{\Sigma}}\overline{\overline{\Sigma}}^{-1}\overline{\overline{U}}^{T}{\bf
z}+\frac{c_{3,s}^{2}}{m}\Big{.}\Bigg{)}$ $\displaystyle=$
$\displaystyle\min_{{\bf x},\|{\bf z}\|_{2}=c_{3,s},c_{2}\geq
0}\max_{\nu_{s}\geq 0}\left(\lambda\|{\bf x}\|_{2}^{2}+\nu_{s}{\bf
h}^{T}\Sigma\left({\bf x}-{\bf c}\right)+\nu_{s}\|c_{2}{\bf
g}-\sigma\overline{\overline{\Sigma}}^{-1}\overline{\overline{U}}^{T}\overline{U}\overline{\Sigma}{\bf
v}-\overline{\overline{\Sigma}}^{-1}\overline{\overline{U}}^{T}{\bf
z}\|_{2}+\frac{c_{3,s}^{2}}{m}\right)$ $\displaystyle=$
$\displaystyle\min_{{\bf x},\|{\bf z}\|_{2}=c_{3,s},c_{2}\geq
0}\max_{\nu_{s}\geq 0}\left(\lambda\|{\bf x}\|_{2}^{2}+\nu_{s}{\bf
h}^{T}\Sigma\left({\bf x}-{\bf c}\right)+\nu_{s}\|c_{2}{\bf
g}-\sigma\overline{\overline{\Sigma}}^{-1}\overline{\overline{U}}^{T}\overline{U}\overline{\Sigma}{\bf
v}-\overline{\overline{\Sigma}}^{-1}{\bf
z}\|_{2}+\frac{c_{3,s}^{2}}{m}\right),$

where ${\bf x},{\bf c},$ and $c_{2}$ are as in (37) and (38) and the last
equality follows after unitary invariant change ${\bf
z}\rightarrow\overline{\overline{U}}^{T}{\bf z}$. After setting

$\displaystyle\bar{{\mathcal{L}}}_{r}\left({\bf x},{\bf z},{\bf
c}_{3,s},c_{2},\nu_{s};{\bf g},{\bf h},{\bf v}\right)\triangleq\lambda\|{\bf
x}\|_{2}^{2}+\nu_{s}{\bf h}^{T}\Sigma\left({\bf x}-{\bf
c}\right)+\nu_{s}\|c_{2}{\bf
g}-\sigma\overline{\overline{\Sigma}}^{-1}\overline{\overline{U}}^{T}\overline{U}\overline{\Sigma}{\bf
v}-\overline{\overline{\Sigma}}^{-1}{\bf z}\|_{2}+\frac{c_{3,s}^{2}}{m},$
(142)

one rewrites (LABEL:eq:corrridgeta18a0) as

$\displaystyle\bar{f}_{rd,r}({\bf g},{\bf h},{\bf v})=\min_{{\bf x},\|{\bf
z}\|_{2}=c_{3,s},c_{2}\geq 0}\max_{\nu_{s}\geq
0}\bar{{\mathcal{L}}}_{r}\left({\bf x},{\bf z},c_{3,s},c_{2},\nu_{s};{\bf
g},{\bf h},{\bf v}\right),$ (143)

and keeping $c_{3,s}$, $c_{2}$, and $\nu_{s}$ fixed, continues, analogously to
(41) and (89), by considering the following minimization over ${\bf x}$ and
${\bf z}$

$\displaystyle\bar{{\mathcal{L}}}_{1,r}\left(c_{3,s},c_{2},\nu_{s}\right)\triangleq\min_{{\bf
x},{\bf z}}$ $\displaystyle\lambda\|{\bf x}\|_{2}^{2}+\nu_{s}{\bf
h}^{T}\Sigma\left({\bf x}-{\bf c}\right)+\nu_{s}\|c_{2}{\bf
g}-\sigma\overline{\overline{\Sigma}}^{-1}\overline{\overline{U}}^{T}\overline{U}\overline{\Sigma}{\bf
v}-\overline{\overline{\Sigma}}^{-1}{\bf z}\|_{2}+\frac{c_{3,s}^{2}}{m}$
subject to $\displaystyle\|\Sigma\left({\bf x}-{\bf
c}\right)\|_{2}=c_{2},\|{\bf z}\|_{2}=c_{3,s},$ (144)

where as earlier, in order to simplify the notation, the functional dependence
on randomness (${\bf g},{\bf h},{\bf v}$) is kept implicit. Moreover,
analogously to (42) and (90), we further have

$\displaystyle\bar{{\mathcal{L}}}_{1,r}\left(c_{3,s},c_{2},\nu_{s}\right)$
$\displaystyle=$ $\displaystyle\max_{\gamma}\min_{{\bf x},\|{\bf
z}\|_{2}=c_{3,s}}\bar{{\mathcal{L}}}_{2,r}\left({\bf x},{\bf
z},\gamma;c_{3,s},c_{2},\nu_{s}\right),$ (145)

with

$\displaystyle\bar{{\mathcal{L}}}_{2,r}\left({\bf x},{\bf
z},\gamma;c_{3,s},c_{2},\nu_{s}\right)$ $\displaystyle\triangleq$
$\displaystyle\lambda\|{\bf x}\|_{2}^{2}+\nu_{s}{\bf h}^{T}\Sigma\left({\bf
x}-{\bf c}\right)+\nu_{s}\|c_{2}{\bf
g}-\sigma\overline{\overline{\Sigma}}^{-1}\overline{\overline{U}}^{T}\overline{U}\overline{\Sigma}{\bf
v}-\overline{\overline{\Sigma}}^{-1}{\bf z}\|_{2}+\frac{c_{3,s}^{2}}{m}$ (146)
$\displaystyle+\gamma\|\Sigma\left({\bf x}-{\bf c}\right)\|_{2}^{2}-\gamma
c_{2}^{2}.$

Taking the optimal ${\bf x}$ as in (46) and (92)

$\displaystyle\hat{{\bf x}}=\left(\lambda
I+\gamma\Sigma\Sigma\right)^{-1}\left(-\frac{1}{2}\nu_{s}\Sigma{\bf
h}+\gamma\Sigma\Sigma{\bf c}\right),$ (147)

with appropriate scaling $\nu_{s}\rightarrow\frac{\nu_{1}}{\sqrt{n}}$ gives
the following analogue to (LABEL:eq:ridgeta18a0b4c1)

$\displaystyle\bar{{\mathcal{L}}}_{2,r}\left(\hat{{\bf x}},{\bf
z},\gamma;c_{3,s},c_{2},\nu_{1}\right)$ $\displaystyle=$
$\displaystyle-\left(-\frac{1}{2\sqrt{n}}\nu_{1}\Sigma{\bf
h}+\gamma\Sigma\Sigma{\bf c}\right)^{T}\left(\lambda
I+\gamma\Sigma\Sigma\right)^{-1}\left(-\frac{1}{2\sqrt{n}}\nu_{1}\Sigma{\bf
h}+\gamma\Sigma\Sigma{\bf c}\right)$
$\displaystyle-\frac{1}{\sqrt{n}}\nu_{1}{\bf h}^{T}\Sigma{\bf
c}+\frac{1}{\sqrt{n}}\nu_{1}\|c_{2}{\bf
g}-\sigma\overline{\overline{\Sigma}}^{-1}\overline{\overline{U}}^{T}\overline{U}\overline{\Sigma}{\bf
v}-\overline{\overline{\Sigma}}^{-1}{\bf
z}\|_{2}+\frac{c_{3,s}^{2}}{m}+\gamma{\bf c}^{T}\Sigma\Sigma{\bf c}-\gamma
c_{2}^{2}.$

We now switch to the following optimization over ${\bf z}$,

$\displaystyle\bar{{\mathcal{L}}}_{3,r}\triangleq\min_{\bf z}$
$\displaystyle\|c_{2}{\bf
g}-\sigma\overline{\overline{\Sigma}}^{-1}\overline{\overline{U}}^{T}\overline{U}\overline{\Sigma}{\bf
v}-\overline{\overline{\Sigma}}^{-1}{\bf z}\|_{2}^{2}$ subject to
$\displaystyle\|{\bf z}\|_{2}=c_{3,s}.$ (149)

After setting

$\displaystyle\theta=c_{2}{\bf
g}-\sigma\overline{\overline{\Sigma}}^{-1}\overline{\overline{U}}^{T}\overline{U}\overline{\Sigma}{\bf
v},$ (150)

writing the Lagrangian and utilizing strong Lagrange duality, we obtain

$\displaystyle\bar{{\mathcal{L}}}_{3,r}=\min_{{\bf
z}}\max_{\gamma_{1}}\bar{{\mathcal{L}}}_{4,r}({\bf
z},\gamma_{1})=\max_{\gamma_{1}}\min_{{\bf z}}\bar{{\mathcal{L}}}_{4,r}({\bf
z},\gamma_{1})$ (151)

with

$\displaystyle\bar{{\mathcal{L}}}_{4,r}({\bf
z},\gamma_{1})=\|\theta-\overline{\overline{\Sigma}}^{-1}{\bf
z}\|_{2}^{2}+\gamma_{1}\|{\bf z}\|_{2}^{2}-\gamma_{1}c_{3,s}^{2}.$ (152)

Computing the derivative with respect to ${\bf z}$ gives

$\displaystyle\frac{d\bar{{\mathcal{L}}}_{4,r}({\bf z},\gamma_{1})}{d{\bf
z}}=2\overline{\overline{\Sigma}}^{-1}\overline{\overline{\Sigma}}^{-1}{\bf
z}-2\overline{\overline{\Sigma}}^{-1}\theta+2\gamma_{1}{\bf z}.$ (153)

Equalling the derivative to zero gives the optimal ${\bf z}$

$\displaystyle\hat{{\bf
z}}=\left(\gamma_{1}I+\overline{\overline{\Sigma}}^{-1}\overline{\overline{\Sigma}}^{-1}\right)^{-1}\overline{\overline{\Sigma}}^{-1}\theta,$
(154)

or in other words

$\displaystyle\hat{{\bf
z}}_{j}=\frac{1}{\gamma_{1}+\frac{1}{\overline{\overline{{\bf
s}}}_{j}^{2}}}\frac{\theta_{j}}{\overline{\overline{{\bf s}}}_{j}},$ (155)

where

$\displaystyle\overline{\overline{{\bf
s}}}\triangleq\mbox{diag}(\overline{\overline{\Sigma}}).$ (156)

Taking $\hat{{\bf z}}$ from (155) and plugging it back in (152) gives

$\displaystyle\bar{{\mathcal{L}}}_{4,r}(\hat{{\bf
z}},\gamma_{1})=\sum_{j=1}^{m}\left(\theta_{j}^{2}-\frac{1}{\gamma_{1}+\frac{1}{\overline{\overline{{\bf
s}}}_{j}^{2}}}\frac{\theta_{j}^{2}}{\overline{\overline{{\bf
s}}}_{j}^{2}}\right)-\gamma_{1}c_{3,s}^{2},$ (157)

which together with (151) gives

$\displaystyle\bar{{\mathcal{L}}}_{3,r}=\max_{\gamma_{1}}\min_{{\bf
z}}\bar{{\mathcal{L}}}_{4,r}({\bf
z},\gamma_{1})=\max_{\gamma_{1}}\bar{{\mathcal{L}}}_{4,r}(\hat{{\bf
z}},\gamma_{1})=\max_{\gamma_{1}}\sum_{j=1}^{m}\left(\theta_{j}^{2}-\frac{1}{\gamma_{1}+\frac{1}{\overline{\overline{{\bf
s}}}_{j}^{2}}}\frac{\theta_{j}^{2}}{\overline{\overline{{\bf
s}}}_{j}^{2}}\right)-\gamma_{1}c_{3,s}^{2}.$ (158)

Combining (LABEL:eq:corrridgeta18a0b4c1), (149), and (158), we further find

$\displaystyle\bar{{\mathcal{L}}}_{2,r}\left(\hat{{\bf x}},\hat{{\bf
z}},\gamma;c_{3,s},c_{2},\nu_{1}\right)$ $\displaystyle=$
$\displaystyle-\left(-\frac{1}{2\sqrt{n}}\nu_{1}\Sigma{\bf
h}+\gamma\Sigma\Sigma{\bf c}\right)^{T}\left(\lambda
I+\gamma\Sigma\Sigma\right)^{-1}\left(-\frac{1}{2\sqrt{n}}\nu_{1}\Sigma{\bf
h}+\gamma\Sigma\Sigma{\bf c}\right)$ (159)
$\displaystyle-\frac{1}{\sqrt{n}}\nu_{1}{\bf h}^{T}\Sigma{\bf
c}+\frac{1}{\sqrt{n}}\nu_{1}\sqrt{\bar{{\mathcal{L}}}_{3,r}}+\frac{c_{3,s}^{2}}{m}+\gamma{\bf
c}^{T}\Sigma\Sigma{\bf c}-\gamma c_{2}^{2}$ $\displaystyle=$
$\displaystyle-\left(-\frac{1}{2\sqrt{n}}\nu_{1}\Sigma{\bf
h}+\gamma\Sigma\Sigma{\bf c}\right)^{T}\left(\lambda
I+\gamma\Sigma\Sigma\right)^{-1}\left(-\frac{1}{2\sqrt{n}}\nu_{1}\Sigma{\bf
h}+\gamma\Sigma\Sigma{\bf c}\right)$
$\displaystyle-\frac{1}{\sqrt{n}}\nu_{1}{\bf h}^{T}\Sigma{\bf
c}+\frac{1}{\sqrt{n}}\nu_{1}\sqrt{\max_{\gamma_{1}}\bar{{\mathcal{L}}}_{4,r}(\hat{{\bf
z}},\gamma_{1})}+\frac{c_{3,s}^{2}}{m}+\gamma{\bf c}^{T}\Sigma\Sigma{\bf
c}-\gamma c_{2}^{2}$ $\displaystyle=$
$\displaystyle\max_{\gamma_{1}}\bar{{\mathcal{L}}}_{5,r}(\gamma_{1}),$

where

$\displaystyle\bar{{\mathcal{L}}}_{5,r}\left(\gamma_{1}\right)$
$\displaystyle=$ $\displaystyle-\left(-\frac{1}{2\sqrt{n}}\nu_{1}\Sigma{\bf
h}+\gamma\Sigma\Sigma{\bf c}\right)^{T}\left(\lambda
I+\gamma\Sigma\Sigma\right)^{-1}\left(-\frac{1}{2\sqrt{n}}\nu_{1}\Sigma{\bf
h}+\gamma\Sigma\Sigma{\bf c}\right)-\frac{1}{\sqrt{n}}\nu_{1}{\bf
h}^{T}\Sigma{\bf c}$
$\displaystyle+\frac{1}{\sqrt{n}}\nu_{1}\sqrt{\bar{{\mathcal{L}}}_{4,r}(\hat{{\bf
z}},\gamma_{1})}+\frac{c_{3,s}^{2}}{m}+\gamma{\bf c}^{T}\Sigma\Sigma{\bf
c}-\gamma c_{2}^{2}$ $\displaystyle=$
$\displaystyle-\left(-\frac{1}{2\sqrt{n}}\nu_{1}\Sigma{\bf
h}+\gamma\Sigma\Sigma{\bf c}\right)^{T}\left(\lambda
I+\gamma\Sigma\Sigma\right)^{-1}\left(-\frac{1}{2\sqrt{n}}\nu_{1}\Sigma{\bf
h}+\gamma\Sigma\Sigma{\bf c}\right)$
$\displaystyle-\frac{1}{\sqrt{n}}\nu_{1}{\bf h}^{T}\Sigma{\bf
c}+\frac{\sqrt{m}}{\sqrt{n}}\nu_{1}\sqrt{\frac{1}{m}\sum_{j=1}^{m}\left(\theta_{j}^{2}-\frac{1}{\gamma_{1}+\frac{1}{\overline{\overline{{\bf
s}}}_{j}^{2}}}\frac{\theta_{j}^{2}}{\overline{\overline{{\bf
s}}}_{j}^{2}}\right)-\gamma_{1}\frac{c_{3,s}^{2}}{m}}+\frac{c_{3,s}^{2}}{m}+\gamma{\bf
c}^{T}\Sigma\Sigma{\bf c}-\gamma c_{2}^{2}.$

Let

$\displaystyle{\mathcal{U}}$ $\displaystyle=$
$\displaystyle\overline{\overline{U}}^{T}\overline{U}$ $\displaystyle{\bf
q}_{j}$ $\displaystyle=$ $\displaystyle\frac{1}{\overline{\overline{{\bf
s}}}_{i}^{2}}\sum_{l=1}^{m}{\mathcal{U}}_{il}^{2}\bar{{\bf s}}_{l}^{2}.$ (161)

We then recognize that

$\displaystyle{\mathbb{E}}_{{\bf g},{\bf
v}}\theta_{j}^{2}=c_{2}^{2}+\sigma^{2}{\bf q}_{j}.$ (162)

Utilizing appropriate scaling $c_{3}\rightarrow\frac{c_{3,s}}{\sqrt{m}}$
(while keeping $c_{3}$, $c_{2}$, $\nu_{1}$, and $\gamma$ fixed) and relying on
concentrations, one finds analogously to (LABEL:eq:ta18a0b4c3) and
(LABEL:eq:ridgeta18a0b4c3)

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{{\bf g},{\bf h},{\bf
v}}\bar{{\mathcal{L}}}_{5,r}\left(\gamma_{1}\right)$
$\displaystyle=\lim_{n\rightarrow\infty}{\mathbb{E}}\Bigg{(}\Big{.}-\left(-\frac{1}{2\sqrt{n}}\nu_{1}\Sigma{\bf
h}+\gamma\Sigma\Sigma{\bf c}\right)^{T}\left(\lambda
I+\gamma\Sigma\Sigma\right)^{-1}\left(-\frac{1}{2\sqrt{n}}\nu_{1}\Sigma{\bf
h}+\gamma\Sigma\Sigma{\bf c}\right)$
$\displaystyle\quad-\frac{1}{\sqrt{n}}\nu_{1}{\bf h}^{T}\Sigma{\bf
c}+\frac{\sqrt{m}}{\sqrt{n}}\nu_{1}\sqrt{\frac{1}{m}\sum_{j=1}^{m}\left(\theta_{j}^{2}-\frac{1}{\gamma_{1}+\frac{1}{\overline{\overline{{\bf
s}}}_{j}^{2}}}\frac{\theta_{j}^{2}}{\overline{\overline{{\bf
s}}}_{j}^{2}}\right)-\gamma_{1}\frac{c_{3,s}^{2}}{m}}$
$\displaystyle\quad+\frac{c_{3,s}^{2}}{m}+\gamma{\bf c}^{T}\Sigma\Sigma{\bf
c}-\gamma c_{2}^{2}\Big{.}\Bigg{)}$
$\displaystyle=\lim_{n\rightarrow\infty}\Bigg{(}\Big{.}-\frac{\nu_{1}^{2}}{4n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\gamma{\bf s}_{i}^{2}}-\sum_{i=1}^{n}\frac{\gamma^{2}{\bf
s}_{i}^{4}{\bf c}_{i}^{2}}{\lambda+\gamma{\bf
s}_{i}^{2}}+\nu_{1}\sqrt{\alpha}\sqrt{l_{4}}+c_{3}^{2}+\gamma\sum_{i=1}^{n}{\bf
s}_{i}^{2}{\bf c}_{i}^{2}-\gamma c_{2}^{2}\Big{.}\Bigg{)},$ (163)

with

$\displaystyle l_{4}=\frac{1}{m}\sum_{j=1}^{m}\left(c_{2}^{2}+\sigma^{2}{\bf
q}_{j}\right)-\frac{1}{m}\sum_{j=1}^{m}\frac{1}{\gamma_{1}+\frac{1}{\overline{\overline{{\bf
s}}}_{j}^{2}}}\frac{c_{2}^{2}+\sigma^{2}{\bf q}_{j}}{\overline{\overline{{\bf
s}}}_{j}^{2}}-\gamma_{1}c_{3}^{2}.$ (164)

A combination of (142)-(145), (151), and (163) allows us to arrive at the
following optimization

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{{\bf g},{\bf h},{\bf
v}}\bar{f}_{rd,r}({\bf g},{\bf h},{\bf v})$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\min_{c_{3},c_{2}\geq
0}\max_{\nu_{1}\geq
0,\gamma,\gamma_{1}}\bar{f}_{0,r}(c_{3},c_{2},\nu_{1},\gamma,\gamma_{1}),$
(165)

where

$\displaystyle\bar{f}_{0,r}(c_{3},c_{2},\nu_{1},\gamma,\gamma_{1})\triangleq-\frac{\nu_{1}^{2}}{4n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\gamma{\bf s}_{i}^{2}}-\sum_{i=1}^{n}\frac{\gamma^{2}{\bf
s}_{i}^{4}{\bf c}_{i}^{2}}{\lambda+\gamma{\bf
s}_{i}^{2}}+\nu_{1}\sqrt{\alpha}\sqrt{l_{4}}+c_{3}^{2}+\gamma\sum_{i=1}^{n}{\bf
s}_{i}^{2}{\bf c}_{i}^{2}-\gamma c_{2}^{2}.$ (166)

After taking the derivative with respect to $\nu_{1}$ we, analogously to (54)
and (99), find the following optimal $\nu_{1}$

$\displaystyle\hat{\nu}_{1}=\frac{2\sqrt{\alpha}\sqrt{l_{4}}}{\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\gamma{\bf s}_{i}^{2}}}.$ (167)

which then, together with (166), gives

$\max_{\nu_{1}\geq
0}\bar{f}_{0,r}(c_{3},c_{2},\nu_{1},\gamma,\gamma_{1})=\bar{f}_{0,r}(c_{3},c_{2},\hat{\nu}_{1},\gamma,\gamma_{1})=-\sum_{i=1}^{n}\frac{\gamma^{2}{\bf
s}_{i}^{4}{\bf c}_{i}^{2}}{\lambda+\gamma{\bf s}_{i}^{2}}+\frac{\alpha
l_{4}}{\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf s}_{i}^{2}}{\lambda+\gamma{\bf
s}_{i}^{2}}}+c_{3}^{2}+\gamma\sum_{i=1}^{n}{\bf s}_{i}^{2}{\bf
c}_{i}^{2}-\gamma c_{2}^{2}.$ (168)

Combining further (165) and (168) we find

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{{\bf g},{\bf h},{\bf
v}}\bar{f}_{rd,r}({\bf g},{\bf h},{\bf v})$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\min_{c_{3},c_{2}\geq
0}\max_{\gamma,\gamma_{1}}\bar{f}_{0,r}(c_{3},c_{2},\hat{\nu}_{1},\gamma,\gamma_{1}),$
(169)

where $\bar{f}_{0,r}(c_{3},c_{2},\hat{\nu}_{1},\gamma,\gamma_{1})$ as in
(168). Computing derivatives with respect to $c_{3}$ and $\gamma_{1}$ gives

$\displaystyle\frac{d\bar{f}_{0,r}(c_{3},c_{2},\hat{\nu}_{1},\gamma,\gamma_{1})}{dc_{3}}=\frac{\alpha}{\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\gamma{\bf
s}_{i}^{2}}}\frac{dl_{4}}{dc_{3}}+2c_{3}=-2\frac{\alpha}{\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\gamma{\bf s}_{i}^{2}}}\gamma_{1}c_{3}+2c_{3},$ (170)

and

$\displaystyle\frac{d\bar{f}_{0,r}(c_{3},c_{2},\hat{\nu}_{1},\gamma,\gamma_{1})}{d\gamma_{1}}=\frac{\alpha}{\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\gamma{\bf
s}_{i}^{2}}}\frac{dl_{4}}{d\gamma_{1}}=\frac{\alpha}{\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\gamma{\bf
s}_{i}^{2}}}\left(\frac{1}{m}\sum_{j=1}^{m}\frac{1}{\left(\gamma_{1}+\frac{1}{\overline{\overline{{\bf
s}}}_{j}^{2}}\right)^{2}}\frac{c_{2}^{2}+\sigma^{2}{\bf
q}_{j}}{\overline{\overline{{\bf s}}}_{j}^{2}}-c_{3}^{2}\right).$ (171)

Equalling these derivatives to zero gives the following two equations for the
optimal $\gamma_{1}$ and $c_{3}$

$\displaystyle\hat{\gamma}_{1}=\frac{\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\gamma{\bf s}_{i}^{2}}}{\alpha},$ (172)

and

$\displaystyle\hat{c}_{3}^{2}=\frac{1}{m}\sum_{j=1}^{m}\frac{1}{\left(\hat{\gamma}_{1}+\frac{1}{\overline{\overline{{\bf
s}}}_{j}^{2}}\right)^{2}}\frac{c_{2}^{2}+\sigma^{2}{\bf
q}_{j}}{\overline{\overline{{\bf s}}}_{j}^{2}}.$ (173)

Combining (172) and (173) together with (168), gives

$\displaystyle\min_{c_{3}\geq
0}\max_{\gamma_{1}}\bar{f}_{0,r}(c_{3},c_{2},\hat{\nu}_{1},\gamma,\gamma_{1})=\bar{f}_{0,r}(\hat{c}_{3},c_{2},\hat{\nu}_{1},\gamma,\hat{\gamma}_{1}),$
(174)

with

$\displaystyle\bar{f}_{0,r}(\hat{c}_{3},c_{2},\hat{\nu}_{1},\gamma,\hat{\gamma}_{1})$
$\displaystyle=$ $\displaystyle-\sum_{i=1}^{n}\frac{\gamma^{2}{\bf
s}_{i}^{4}{\bf c}_{i}^{2}}{\lambda+\gamma{\bf s}_{i}^{2}}+\frac{\alpha
l_{4}}{\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf s}_{i}^{2}}{\lambda+\gamma{\bf
s}_{i}^{2}}}+\hat{c}_{3}^{2}+\gamma\sum_{i=1}^{n}{\bf s}_{i}^{2}{\bf
c}_{i}^{2}-\gamma c_{2}^{2}$ $\displaystyle=$
$\displaystyle-\sum_{i=1}^{n}\frac{\gamma^{2}{\bf s}_{i}^{4}{\bf
c}_{i}^{2}}{\lambda+\gamma{\bf
s}_{i}^{2}}+\frac{1}{\hat{\gamma_{1}}}\left(\frac{1}{m}\sum_{j=1}^{m}\left(c_{2}^{2}+\sigma^{2}{\bf
q}_{j}\right)-\frac{1}{m}\sum_{j=1}^{m}\frac{1}{\hat{\gamma}_{1}+\frac{1}{\overline{\overline{{\bf
s}}}_{j}^{2}}}\frac{c_{2}^{2}+\sigma^{2}{\bf q}_{j}}{\overline{\overline{{\bf
s}}}_{j}^{2}}-\hat{\gamma}_{1}\hat{c}_{3}^{2}\right)$
$\displaystyle+\hat{c}_{3}^{2}+\gamma\sum_{i=1}^{n}{\bf s}_{i}^{2}{\bf
c}_{i}^{2}-\gamma c_{2}^{2}$ $\displaystyle=$
$\displaystyle-\sum_{i=1}^{n}\frac{\gamma^{2}{\bf s}_{i}^{4}{\bf
c}_{i}^{2}}{\lambda+\gamma{\bf
s}_{i}^{2}}+\frac{1}{\hat{\gamma_{1}}}\left(\frac{1}{m}\sum_{j=1}^{m}\left(c_{2}^{2}+\sigma^{2}{\bf
q}_{j}\right)-\frac{1}{m}\sum_{j=1}^{m}\frac{\frac{1}{\overline{\overline{{\bf
s}}}_{j}^{2}}}{\hat{\gamma}_{1}+\frac{1}{\overline{\overline{{\bf
s}}}_{j}^{2}}}\left(c_{2}^{2}+\sigma^{2}{\bf q}_{j}\right)\right)$
$\displaystyle+\gamma\sum_{i=1}^{n}{\bf s}_{i}^{2}{\bf c}_{i}^{2}-\gamma
c_{2}^{2}$ $\displaystyle=$ $\displaystyle-\sum_{i=1}^{n}\frac{\gamma^{2}{\bf
s}_{i}^{4}{\bf c}_{i}^{2}}{\lambda+\gamma{\bf
s}_{i}^{2}}+\frac{1}{m}\sum_{j=1}^{m}\frac{c_{2}^{2}+\sigma^{2}{\bf
q}_{j}}{\hat{\gamma}_{1}+\frac{1}{\overline{\overline{{\bf
s}}}_{j}^{2}}}+\gamma\sum_{i=1}^{n}{\bf s}_{i}^{2}{\bf c}_{i}^{2}-\gamma
c_{2}^{2}$ $\displaystyle=$ $\displaystyle-\sum_{i=1}^{n}\frac{\gamma^{2}{\bf
s}_{i}^{4}{\bf c}_{i}^{2}}{\lambda+\gamma{\bf
s}_{i}^{2}}+\frac{1}{m}\sum_{j=1}^{m}\frac{c_{2}^{2}+\sigma^{2}{\bf
q}_{j}}{\frac{1}{\alpha n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\gamma{\bf s}_{i}^{2}}+\frac{1}{\overline{\overline{{\bf
s}}}_{j}^{2}}}+\gamma\sum_{i=1}^{n}{\bf s}_{i}^{2}{\bf c}_{i}^{2}-\gamma
c_{2}^{2}$

Taking derivatives with respect $c_{2}$ and $\gamma$ and equalling them to
zero, we also have

$\displaystyle\frac{d\bar{f}_{0,r}(\hat{c}_{3},c_{2},\hat{\nu}_{1},\gamma,\hat{\gamma}_{1})}{dc_{2}}=\frac{1}{m}\sum_{j=1}^{m}\frac{2c_{2}}{\frac{1}{\overline{\overline{{\bf
s}}}_{j}^{2}}+\frac{1}{\alpha n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\gamma{\bf s}_{i}^{2}}}-2\gamma c_{2}=0.$ (176)

and

$\displaystyle\frac{d\bar{f}_{0,r}(\hat{c}_{3},c_{2},\hat{\nu}_{1},\gamma,\hat{\gamma}_{1})}{d\gamma}$
$\displaystyle=$ $\displaystyle-\sum_{i=1}^{n}\frac{2\gamma{\bf s}_{i}^{4}{\bf
c}_{i}^{2}}{\lambda+\gamma{\bf s}_{i}^{2}}+\sum_{i=1}^{n}\frac{\gamma^{2}{\bf
s}_{i}^{6}{\bf c}_{i}^{2}}{\left(\lambda+\gamma{\bf s}_{i}^{2}\right)^{2}}$
$\displaystyle+\frac{1}{m}\sum_{j=1}^{m}\frac{\left(c_{2}^{2}+\sigma^{2}{\bf
q}_{j}\right)}{\left(\frac{1}{\overline{\overline{{\bf
s}}}_{j}^{2}}+\frac{1}{\alpha n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\gamma{\bf s}_{i}^{2}}\right)^{2}}\left(\frac{1}{\alpha
n}\sum_{i=1}^{n}\frac{{\bf s}_{i}^{4}}{\left(\lambda+\gamma{\bf
s}_{i}^{2}\right)^{2}}\right)+\sum_{i=1}^{n}{\bf s}_{i}^{2}{\bf
c}_{i}^{2}-c_{2}^{2}=0.$

From (176) we find that the optimal $\hat{\gamma}$ satisfies the following
equation

$\displaystyle\hat{\gamma}=\frac{1}{m}\sum_{j=1}^{m}\frac{1}{\frac{1}{\overline{\overline{{\bf
s}}}_{j}^{2}}+\frac{1}{\alpha n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\hat{\gamma}{\bf s}_{i}^{2}}}.$ (178)

Moreover, we then (for such a $\hat{\gamma}$) have from
(LABEL:eq:corrridgeta18a0b4c12) that the optimal $\hat{c}_{2}$ satisfies

$\displaystyle\sum_{i=1}^{n}\frac{\lambda^{2}{\bf s}_{i}^{2}{\bf
c}_{i}^{2}}{\left(\lambda+\hat{\gamma}{\bf
s}_{i}^{2}\right)^{2}}+\frac{1}{m}\sum_{j=1}^{m}\frac{\left(c_{2}^{2}+\sigma^{2}{\bf
q}_{j}\right)}{\left(\frac{1}{\overline{\overline{{\bf
s}}}_{j}^{2}}+\frac{1}{\alpha n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\gamma{\bf s}_{i}^{2}}\right)^{2}}\left(\frac{1}{\alpha
n}\sum_{i=1}^{n}\frac{{\bf s}_{i}^{4}}{\left(\lambda+\gamma{\bf
s}_{i}^{2}\right)^{2}}\right)-c_{2}^{2}=0.$ (179)

After setting

$\displaystyle\bar{a}_{2,r}$ $\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{4}}{\left(\lambda+\hat{\gamma}{\bf
s}_{i}^{2}\right)^{2}}\frac{1}{m}\sum_{j=1}^{m}\frac{1}{\left(\frac{\alpha}{\overline{\overline{{\bf
s}}}_{j}^{2}}+\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\hat{\gamma}{\bf s}_{i}^{2}}\right)^{2}}$
$\displaystyle\bar{a}_{3,r}$ $\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{4}}{\left(\lambda+\hat{\gamma}{\bf
s}_{i}^{2}\right)^{2}}\frac{1}{m}\sum_{j=1}^{m}\frac{{\bf
q}_{j}}{\left(\frac{\alpha}{\overline{\overline{{\bf
s}}}_{j}^{2}}+\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\hat{\gamma}{\bf s}_{i}^{2}}\right)^{2}},$ (180)

we then from (179) obtain

$\displaystyle\hat{c}_{2}^{2}=\frac{\sum_{i=1}^{n}\frac{\lambda^{2}{\bf
s}_{i}^{2}{\bf c}_{i}^{2}}{\left(\lambda+\hat{\gamma}{\bf
s}_{i}^{2}\right)^{2}}+\alpha\sigma^{2}\bar{a}_{3,r}}{1-\alpha\bar{a}_{2,r}}.$
(181)

Combining (174) and (LABEL:eq:corrridgeta18a0b4c10d1e0) together with (169),
we find

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{{\bf g},{\bf h},{\bf
v}}\bar{f}_{rd,r}({\bf g},{\bf h},{\bf v})$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\min_{c_{2}\geq
0}\max_{\gamma}f_{0}(\hat{c}_{3},c_{2},\hat{\nu}_{1},\gamma,\hat{\gamma}_{1})$
(182) $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}f_{0}(\hat{c}_{3},\hat{c}_{2},\hat{\nu}_{1},\hat{\gamma},\hat{\gamma}_{1})$
$\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\left(-\sum_{i=1}^{n}\frac{\hat{\gamma}^{2}{\bf
s}_{i}^{4}{\bf c}_{i}^{2}}{\lambda+\hat{\gamma}{\bf
s}_{i}^{2}}+\frac{1}{m}\sum_{j=1}^{m}\frac{\hat{c}_{2}^{2}+\sigma^{2}{\bf
q}_{j}}{\frac{1}{\alpha n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\hat{\gamma}{\bf
s}_{i}^{2}}+\frac{1}{\overline{\overline{{\bf
s}}}_{j}^{2}}}+\hat{\gamma}\sum_{i=1}^{n}{\bf s}_{i}^{2}{\bf
c}_{i}^{2}-\hat{\gamma}\hat{c}_{2}^{2}\right)$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\left(\sum_{i=1}^{n}\frac{\lambda\hat{\gamma}{\bf
s}_{i}^{2}{\bf c}_{i}^{2}}{\lambda+\hat{\gamma}{\bf
s}_{i}^{2}}+\frac{1}{m}\sum_{j=1}^{m}\frac{\hat{c}_{2}^{2}+\sigma^{2}{\bf
q}_{j}}{\frac{1}{\alpha n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\hat{\gamma}{\bf
s}_{i}^{2}}+\frac{1}{\overline{\overline{{\bf
s}}}_{j}^{2}}}-\hat{\gamma}\hat{c}_{2}^{2}\right)$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\sum_{i=1}^{n}\frac{\lambda\hat{\gamma}{\bf
s}_{i}^{2}{\bf c}_{i}^{2}}{\lambda+\hat{\gamma}{\bf
s}_{i}^{2}}+\sigma^{2}\frac{1}{m}\sum_{j=1}^{m}\frac{{\bf
q}_{j}}{\frac{1}{\alpha n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\hat{\gamma}{\bf
s}_{i}^{2}}+\frac{1}{\overline{\overline{{\bf s}}}_{j}^{2}}},$

where $\hat{c}_{2}$ and $\hat{\gamma}$ are given through (178), (180), and
(181). Taking the very same $\hat{c}_{2}$ and $\hat{\gamma}$, we then from
(173) and (167) find the optimal $c_{3}$ and $\nu_{1}$

$\displaystyle\hat{c}_{3}^{2}=\frac{1}{m}\sum_{j=1}^{m}\frac{1}{\left(\frac{1}{\alpha
n}\sum_{i=1}^{n}\frac{{\bf s}_{i}^{2}}{\lambda+\hat{\gamma}{\bf
s}_{i}^{2}}+\frac{1}{\overline{\overline{{\bf
s}}}_{j}^{2}}\right)^{2}}\frac{\hat{c}_{2}^{2}+\sigma^{2}{\bf
q}_{j}}{\overline{\overline{{\bf s}}}_{j}^{2}}.$ (183)

and

$\displaystyle\hat{\nu}_{1}$ $\displaystyle=$
$\displaystyle\frac{2\sqrt{\alpha}\sqrt{l_{4}}}{\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\hat{\gamma}{\bf s}_{i}^{2}}}$ (184) $\displaystyle=$
$\displaystyle\frac{2\sqrt{\alpha}}{\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\hat{\gamma}{\bf
s}_{i}^{2}}}\sqrt{\frac{1}{m}\sum_{j=1}^{m}\left(\hat{c}_{2}^{2}+\sigma^{2}{\bf
q}_{j}\right)-\frac{1}{m}\sum_{j=1}^{m}\frac{1}{\hat{\gamma}_{1}+\frac{1}{\overline{\overline{{\bf
s}}}_{j}^{2}}}\frac{\hat{c}_{2}^{2}+\sigma^{2}{\bf
q}_{j}}{\overline{\overline{{\bf
s}}}_{j}^{2}}-\hat{\gamma}_{1}\hat{c}_{3}^{2}}$ $\displaystyle=$
$\displaystyle\frac{2\sqrt{\alpha}}{\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\hat{\gamma}{\bf
s}_{i}^{2}}}\sqrt{\hat{\gamma}_{1}\frac{1}{m}\sum_{j=1}^{m}\frac{1}{\hat{\gamma}_{1}+\frac{1}{\overline{\overline{{\bf
s}}}_{j}^{2}}}\frac{\hat{c}_{2}^{2}+\sigma^{2}{\bf
q}_{j}}{\overline{\overline{{\bf
s}}}_{j}^{2}}-\hat{\gamma}_{1}\hat{c}_{3}^{2}}$ $\displaystyle=$
$\displaystyle\frac{2\sqrt{\alpha}}{\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\hat{\gamma}{\bf
s}_{i}^{2}}}\sqrt{\hat{\gamma}_{1}\frac{1}{m}\sum_{j=1}^{m}\frac{1}{\hat{\gamma}_{1}+\frac{1}{\overline{\overline{{\bf
s}}}_{j}^{2}}}\frac{\hat{c}_{2}^{2}+\sigma^{2}{\bf
q}_{j}}{\overline{\overline{{\bf
s}}}_{j}^{2}}-\hat{\gamma}_{1}\frac{1}{m}\sum_{j=1}^{m}\frac{1}{\left(\hat{\gamma}_{1}+\frac{1}{\overline{\overline{{\bf
s}}}_{j}^{2}}\right)^{2}}\frac{\hat{c}_{2}^{2}+\sigma^{2}{\bf
q}_{j}}{\overline{\overline{{\bf s}}}_{j}^{2}}}$ $\displaystyle=$
$\displaystyle\frac{2\sqrt{\alpha}\hat{\gamma}_{1}}{\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\hat{\gamma}{\bf
s}_{i}^{2}}}\sqrt{\frac{1}{m}\sum_{j=1}^{m}\frac{\hat{c}_{2}^{2}+\sigma^{2}{\bf
q}_{j}}{\left(\hat{\gamma}_{1}+\frac{1}{\overline{\overline{{\bf
s}}}_{j}^{2}}\right)^{2}}}$ $\displaystyle=$
$\displaystyle\frac{2}{\sqrt{\alpha}}\sqrt{\frac{1}{m}\sum_{j=1}^{m}\frac{\hat{c}_{2}^{2}+\sigma^{2}{\bf
q}_{j}}{\left(\hat{\gamma}_{1}+\frac{1}{\overline{\overline{{\bf
s}}}_{j}^{2}}\right)^{2}}}$ $\displaystyle=$
$\displaystyle\frac{2}{\sqrt{\alpha}}\sqrt{\frac{1}{m}\sum_{j=1}^{m}\frac{\hat{c}_{2}^{2}+\sigma^{2}{\bf
q}_{j}}{\left(\frac{1}{\alpha n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\hat{\gamma}{\bf
s}_{i}^{2}}+\frac{1}{\overline{\overline{{\bf s}}}_{j}^{2}}\right)^{2}}}.$

We also have, analogously to (113), for the optimal
$\hat{c}_{4}^{2}=\lim_{n\rightarrow\infty}{\mathbb{E}}_{{\bf g},{\bf h},{\bf
v}}\|\hat{{\bf x}}\|_{2}^{2}$

$\displaystyle\hat{c}_{4}^{2}$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{{\bf g},{\bf h},{\bf
v}}\|\hat{{\bf x}}\|_{2}^{2}$ (185) $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{{\bf g},{\bf h},{\bf
v}}\left\|\left(\lambda
I+\hat{\gamma}\Sigma\Sigma\right)^{-1}\left(-\frac{\hat{\nu}_{1}}{2\sqrt{n}}\Sigma{\bf
h}+\gamma\Sigma\Sigma{\bf c}\right)\right\|_{2}^{2}$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\frac{\hat{\nu}_{1}^{2}}{4n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\left(\lambda+\hat{\gamma}{\bf
s}_{i}^{2}\right)^{2}}+\lim_{n\rightarrow\infty}\sum_{i=1}^{n}\frac{\hat{\gamma}^{2}{\bf
s}_{i}^{4}{\bf c}_{i}^{2}}{\left(\lambda+\hat{\gamma}{\bf
s}_{i}^{2}\right)^{2}}.$

The above discussion in summarized in the following theorem.

######  Theorem 6.

(Characterization of Ridge estimator – Row-correlated $X$) For a given fixed
real positive number $\lambda$, assume the setup of Lemma 136 and Theorem 5
with $\bar{\xi}_{rr}(\lambda)$ as in (132) or (133) and $\bar{\xi}_{rd,r}$ as
in (83). Let $\hat{\beta}=\bar{\beta}_{rr}(\lambda)$ where
$\bar{\beta}_{rr}(\lambda)$ is as in (134). Also, let the Ridge estimator
prediction risk,
$R(\bar{\beta},\hat{\beta})=R(\bar{\beta},\bar{\beta}_{rr}(\lambda))$, be
defined via (24). Assuming a large $n$ linear regime with
$\alpha=\lim_{n\rightarrow\infty}\frac{m}{n}$, let unique $\hat{\gamma}$ be
such that

$\displaystyle\hat{\gamma}=\lim_{m\rightarrow\infty}\frac{1}{m}\sum_{j=1}^{m}\frac{1}{\frac{1}{\overline{\overline{{\bf
s}}}_{j}^{2}}+\lim_{n\rightarrow\infty}\frac{1}{\alpha
n}\sum_{i=1}^{n}\frac{{\bf s}_{i}^{2}}{\lambda+\hat{\gamma}{\bf s}_{i}^{2}}}.$
(186)

Set

$\displaystyle\bar{a}_{2,r}$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{4}}{\left(\lambda+\hat{\gamma}{\bf
s}_{i}^{2}\right)^{2}}\lim_{m\rightarrow\infty}\frac{1}{m}\sum_{j=1}^{m}\frac{1}{\left(\frac{\alpha}{\overline{\overline{{\bf
s}}}_{j}^{2}}+\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\hat{\gamma}{\bf s}_{i}^{2}}\right)^{2}}$
$\displaystyle\bar{a}_{3,r}$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{4}}{\left(\lambda+\hat{\gamma}{\bf
s}_{i}^{2}\right)^{2}}\lim_{m\rightarrow\infty}\frac{1}{m}\sum_{j=1}^{m}\frac{{\bf
q}_{j}}{\left(\frac{\alpha}{\overline{\overline{{\bf
s}}}_{j}^{2}}+\frac{1}{n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\lambda+\hat{\gamma}{\bf s}_{i}^{2}}\right)^{2}}.$ (187)

One then has

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{Z,{\bf
v}}\bar{\xi}_{rr}(\lambda)$ $\displaystyle=$
$\displaystyle\bar{\xi}_{rp,r}=\bar{\xi}_{rd,r}=\lim_{n\rightarrow\infty}{\mathbb{E}}_{{\bf
g},{\bf h},{\bf v}}\bar{f}_{rd,r}({\bf g},{\bf h},{\bf v})$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\sum_{i=1}^{n}\frac{\lambda\hat{\gamma}{\bf
s}_{i}^{2}{\bf c}_{i}^{2}}{\lambda+\hat{\gamma}{\bf
s}_{i}^{2}}+\sigma^{2}\lim_{m\rightarrow\infty}\frac{1}{m}\sum_{j=1}^{m}\frac{{\bf
q}_{j}}{\frac{1}{\overline{\overline{{\bf
s}}}_{j}^{2}}+\lim_{n\rightarrow\infty}\frac{1}{\alpha
n}\sum_{i=1}^{n}\frac{{\bf s}_{i}^{2}}{\lambda+\hat{\gamma}{\bf s}_{i}^{2}}}$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{Z,{\bf
v}}R(\bar{\beta},\beta_{rr}(\lambda))$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\hat{c}_{2}^{2}=\frac{\lim_{n\rightarrow\infty}\sum_{i=1}^{n}\frac{\lambda^{2}{\bf
s}_{i}^{2}{\bf c}_{i}^{2}}{\left(\lambda+\hat{\gamma}{\bf
s}_{i}^{2}\right)^{2}}+\alpha\sigma^{2}\bar{a}_{3,r}}{1-\alpha\bar{a}_{2,r}}$
$\displaystyle\lim_{n\rightarrow\infty}\hat{\nu}_{1}=\frac{2}{\sqrt{\alpha}}\sqrt{\lim_{m\rightarrow\infty}\frac{1}{m}\sum_{j=1}^{m}\frac{\hat{c}_{2}^{2}+\sigma^{2}{\bf
q}_{j}}{\left(\lim_{n\rightarrow\infty}\frac{1}{\alpha
n}\sum_{i=1}^{n}\frac{{\bf s}_{i}^{2}}{\lambda+\hat{\gamma}{\bf
s}_{i}^{2}}+\frac{1}{\overline{\overline{{\bf s}}}_{j}^{2}}\right)^{2}}}$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{Z,{\bf v}}\|{\bf
y}-X\bar{\beta}_{rr}(\lambda)\|_{2}^{2}$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\hat{c}_{3}^{2}=\lim_{m\rightarrow\infty}\frac{1}{m}\sum_{j=1}^{m}\frac{1}{\left(\lim_{n\rightarrow\infty}\frac{1}{\alpha
n}\sum_{i=1}^{n}\frac{{\bf s}_{i}^{2}}{\lambda+\hat{\gamma}{\bf
s}_{i}^{2}}+\frac{1}{\overline{\overline{{\bf
s}}}_{j}^{2}}\right)^{2}}\frac{\hat{c}_{2}^{2}+\sigma^{2}{\bf
q}_{j}}{\overline{\overline{{\bf s}}}_{j}^{2}}$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{Z,{\bf
v}}\|\bar{\beta}_{rr}(\lambda)\|_{2}^{2}$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\hat{c}_{4}^{2}=\lim_{n\rightarrow\infty}\frac{\hat{\nu}_{1}^{2}}{4n}\sum_{i=1}^{n}\frac{{\bf
s}_{i}^{2}}{\left(\lambda+\hat{\gamma}{\bf
s}_{i}^{2}\right)^{2}}+\lim_{n\rightarrow\infty}\sum_{i=1}^{n}\frac{\hat{\gamma}^{2}{\bf
s}_{i}^{4}{\bf c}_{i}^{2}}{\left(\lambda+\hat{\gamma}{\bf
s}_{i}^{2}\right)^{2}},$ (188)

and for any fixed $\epsilon>0$

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{Z,{\bf
v}}\left((1-\epsilon){\mathbb{E}}_{Z,{\bf
v}}\bar{\xi}_{rr}(\lambda)\leq\bar{\xi}_{rr}(\lambda)\leq(1+\epsilon){\mathbb{E}}_{Z,{\bf
v}}\bar{\xi}_{rr}(\lambda)\right)$ $\displaystyle\longrightarrow$
$\displaystyle 1$ $\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{Z,{\bf
v}}\left((1-\epsilon){\mathbb{E}}_{Z,{\bf
v}}R(\bar{\beta},\bar{\beta}_{rr}(\lambda))\leq
R(\bar{\beta},\bar{\beta}_{rr}(\lambda))\leq(1+\epsilon){\mathbb{E}}_{Z,{\bf
v}}R(\bar{\beta},\bar{\beta}_{rr}(\lambda))\right)$
$\displaystyle\longrightarrow$ $\displaystyle 1$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{{\bf g},{\bf h},{\bf
v}}\left((1-\epsilon)\hat{\nu}_{1}\leq\nu_{1}\leq(1+\epsilon)\hat{\nu}_{1}\right)$
$\displaystyle\longrightarrow$ $\displaystyle 1$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{Z,{\bf
v}}\left((1-\epsilon){\mathbb{E}}_{Z,{\bf v}}\|{\bf
y}-X\bar{\beta}_{rr}(\lambda)\|_{2}^{2}\leq\|{\bf
y}-X\bar{\beta}_{rr}(\lambda)\|_{2}^{2}\leq(1+\epsilon){\mathbb{E}}_{Z,{\bf
v}}\|{\bf y}-X\bar{\beta}_{rr}(\lambda)\|_{2}^{2}\right)$
$\displaystyle\longrightarrow$ $\displaystyle 1$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{Z,{\bf
v}}\left((1-\epsilon){\mathbb{E}}_{Z,{\bf
v}}\|\bar{\beta}_{rr}(\lambda)\|_{2}^{2}\leq\|\bar{\beta}_{rr}(\lambda)\|_{2}^{2}\leq(1+\epsilon){\mathbb{E}}_{Z,{\bf
v}}\|\bar{\beta}_{rr}(\lambda)\|_{2}^{2}\right)$
$\displaystyle\longrightarrow$ $\displaystyle 1.$

###### Proof.

Follows from the above discussion, trivial concentrations of
$\bar{f}_{rd,r}({\bf g},{\bf h},{\bf v})$, $c_{3}$, $c_{2}$, and $\nu_{1}$,
and utilization of literally the asme arguments as in the proof of Theorems 2
and 4. ∎

4) _Double checking strong random duality:_ As was the case when we considered
the uncorrelated rows of $X$, due to the underlying convexity one has that the
reversal arguments of [51, 52] and the strong random duality are in place as
well.

####  4.1.1 Additional observations

The corresponding LS estimator results are obtained by taking $\lambda=0$ in
the above theorem. The expressions do simplify a bit but not as they do in
case of uncorrelated rows of $X$. We therefore skip stating them as a separate
corollary. We also recall from the very beginning of this section, that the
results for the GLS interpolator when rows of $X$ are correlated are identical
to the ones obtained in Theorem 2 with $\bar{\sigma}$ as defined in (131).
Moreover, all results obtained for the GLS interpolator (with rows of $X$
correlated or uncorrelated) remain unaltered even if the rank of $A$ or
$\Sigma$ is not full. In, fact, assuming that the
$\mbox{rank}(A)=\mbox{rank}(\Sigma)=k$, where

$\displaystyle\kappa\triangleq\lim_{n\rightarrow\infty}\frac{k}{n}.$ (190)

then all GLS related results hold as long as $\kappa>\alpha$. When
$\kappa<\alpha$, interpolation is trivially impossible. All results related to
the Ridge estimator hold for any rank of $A$ or $\Sigma$.

###  4.2 Numerical results

As earlier, we supplement the above theoretical results with the ones obtained
through numerical simulations. We take for the covariance matrices

$\displaystyle\overline{\overline{A}}$ $\displaystyle=$
$\displaystyle{\mathcal{A}}(q_{y})$ $\displaystyle A$ $\displaystyle=$
$\displaystyle{\mathcal{A}}(q)$ $\displaystyle\overline{A}$ $\displaystyle=$
$\displaystyle{\mathcal{A}}(q_{v}).$ (191)

In Figure 2, we take $q_{y}=0.7,q=0.5,q_{v}=0.4$, and $n=600$. As earlier, the
full curves are the theoretical predictions and the dots are the corresponding
simulated values. We again observe an excellent agreement between the
theoretical predictions and simulations results.

Figure 2: Prediction risk – all three estimators (GLS, Ridge, and LS); row-
correlated features $X$; Covariance matrices are:
$\overline{\overline{A}}={\mathcal{A}}(q_{y})$, $A={\mathcal{A}}(q)$, and
$\overline{A}={\mathcal{A}}(q_{v})$; $q_{y}=0.7,q=0.5,q_{v}=0.4$.

In Figure 3, we show what kind of effect intra-sample correlation can have on
the prediction risk. All parameters take the same values as in Figure 2 except
$\alpha=0.5$ and $qy$ which is varied between zero and one. Also to adjust
that no correlation correspond to unitary covariance matrices, all
${\mathcal{A}}$’s are scaled by 2. Keeping in mind the adopted convention that
the full curves are the theoretical predictions and the dots are the
corresponding simulated values, we again observe an excellent agreement
between the theoretical predictions and simulations results. In low intra-
sample correlated regime, we also observe that the risk is not always
increasing as the correlation increases.

Figure 3: Prediction risk as a function of intra-sample correlation – GLS;
Covariance matrices are:
$\overline{\overline{A}}=\frac{1}{2}{\mathcal{A}}(q_{y})$,
$A=\frac{1}{2}{\mathcal{A}}(q)$, and
$\overline{A}=\frac{1}{2}{\mathcal{A}}(q_{v})$; $q=0.5,q_{v}=0.4$;
$q_{y}\in[0,1]$.

##  5 Conclusion

We studied classical linear regression models and three of the most well known
estimators associated with them: (i) minimum norm interpolators (generalized
least squares (GLS)); (ii) ordinary least squares (LS); and (ii) ridge
estimators. A statistical context with Gaussian feature matrix and noise is
considered. In addition to inter-feature (cross-sectional) correlations, the
intra-sample ones for both the features and noise are considered as well. The
(random) optimization programs that produce the above three estimators are
statistically analyzed through a utilization of a powerful mathematical engine
called _Random Duality Theory_ (RDT). Precise closed form characterizations of
all optimizing quantities associated with all three optimization programs are
obtained. Among these quantities, we particularly focused on the _prediction
risk_ (generalization/testing error) and observed that it exhibits the well
known non-monotonic (so-called double-descent) behavior as the over-