# Theoretical Analysis of Leave-one-out Cross Validation for Non-
differentiable Penalties under High-dimensional Settings

Haolin Zou  Arnab Auddy  Kamiar Rahnama Rad  Arian Maleki  m1 University of
Pennsylvania
m2 Columbia University
m3 Baruch College, City University of New York

###### Abstract

Despite a large and significant body of recent work focused on estimating the
out-of-sample risk of regularized models in the high dimensional regime, a
theoretical understanding of this problem for non-differentiable penalties
such as generalized LASSO and nuclear norm is missing. In this paper we
resolve this challenge. We study this problem in the proportional high
dimensional regime where both the sample size $n$ and number of features $p$
are large, and $n/p$ and the signal-to-noise ratio (per observation) remain
finite. We provide finite sample upper bounds on the expected squared error of
leave-one-out cross-validation (${\rm LO}$) in estimating the out-of-sample
risk. The theoretical framework presented here provides a solid foundation for
elucidating empirical findings that show the accuracy of ${\rm LO}$.

and

##  1 Introduction

###  1.1 Main goal

Estimating the out-of-sample risk (OO) to assess model performance and to set
model complexity is a crucial task in statistical learning. A large body of
recent work has studied the theoretical and empirical properties of cross-
validation (or its variants) for estimating OO (Rahnama Rad et al., 2020;
Rahnama Rad and Maleki, 2020; Patil et al., 2021, 2022, 2023; Xu et al., 2021;
Bellec, 2023; Beirami et al., 2017; Auddy et al., 2023; Stephenson and
Broderick, 2020; Stephenson et al., 2021; Luo et al., 2023).

In spite of these recent advances, a complete quantitative description of the
risk in using leave-one-out cross-validation (LO) is missing when it comes to
problems that have the following characteristics 1) non-differentiable
penalties such as generalized LASSO and nuclear norm, and 2) finite signal-to-
noise ratio when the dimension of the feature space grows proportionally with
the number of observations. In this paper, we focus on the aforementioned
characteristics for regularized generalized linear models (including logistic
and Poisson regression). We use minor assumptions about the data generating
process to provide finite sample upper bounds on the expected squared error of
leave-one-out cross-validation in estimating the out-of-sample error. A
consequence of our theory is that leave-one-out cross-validation is a
consistent estimator of the out-of-sample risk.

###  1.2 Problem statement and related work

Consider the dataset $\mathcal{D}=\\{(y_{i},\mathbf{x}_{i})\\}_{i=1}^{n}$,
where $\mathbf{x}_{i}\in\mathbb{R}^{p}$ and $y_{i}\in\mathbb{R}$ denote the
features and response of the $i^{\rm th}$ data point, respectively.
Observations are independent and identically distributed (iid) draws from some
unknown joint distribution
$q(y_{i}|\mathbf{x}_{i}^{\top}\bm{\beta}^{*})p(\mathbf{x}_{i})$, where
$\bm{\beta}^{*}\in\mathbb{R}^{p}$ represents the true parameter.

The class of estimates, known as regularized empirical risk minimizers
(R-ERM), are based on the following optimization:

$\widehat{\bm{\beta}}:=\underset{\bm{\beta}\in\bm{\Theta}}{\operatorname{argmin}}\sum_{i=1}^{n}\ell(y_{i},\mathbf{x}_{i}^{\top}\bm{\beta})+\lambda
r(\bm{\beta}),$

where $\ell(y,z)$ is a non-negative convex loss function between $y$ and $z$,
e.g., square loss $\ell(y,z)=\frac{1}{2}(y-z)^{2}$, $r(\bm{\beta})$ is a non-
negative convex regularizer, and $\bm{\Theta}$ is a convex set to which
$\bm{\beta}^{*}$ belongs. By selecting particular forms for $\ell$ and $r$ we
can cover a wide range of popular estimators within the high-dimensional
setting. For instance, one may use logistic or Poisson for the loss function,
and fused LASSO or nuclear norm for the regularizer.

One widely used criterion for model selection and evaluating the accuracy of
$\widehat{\bm{\beta}}$ is the out-of-sample prediction error (${\rm OO}$),
defined as

${\rm
OO}:=\mathbb{E}[\phi(y_{0},\mathbf{x}_{0}^{\top}\widehat{\bm{\beta}})|{\cal
D}],$

where $\phi(y,z)$ is a function measuring the difference between $y$ and $z$
(often, but not necessarily the same as $\ell(y,z)$), and
$(y_{0},\mathbf{x}_{0})$ is a sample from the same joint distribution
$q(y|\mathbf{x}^{\top}\bm{\beta}^{*})p(\mathbf{x})$, independent of the
training set ${\cal D}=\\{(y_{i},\mathbf{x}_{i})\\}_{i=1}^{n}$.

Several methods are proposed to estimate ${\rm OO}$ such as $K$-fold cross-
validation, Generalized Cross-Validation, and Bootstrap, among others. In this
paper, we employ the term “risk estimate” as a generic term for referring to
these techniques. Despite the abundance of theoretical and empirical results
in the literature, studies specifically examining the accuracy of risk
estimates in high-dimensional settings, where the number of features is either
larger than or comparable to the sample size $n$, are noticeably scarce. As a
result many fundamental questions regarding the performance of risk estimates
have remained open.

The main objective of this paper is to prove the accuracy of the leave one out
risk estimate ${\rm LO}$ for a large class of R-ERMs under the high-
dimensional setting. For $1\leq i\leq n$, define

$\widehat{\bm{\beta}}_{/i}:=\underset{\bm{\beta}\in\bm{\Theta}}{\operatorname{argmin}}\sum_{j\neq
i}\ell(y_{j},\mathbf{x}_{j}^{\top}\bm{\beta})+\lambda r(\bm{\beta}).$

${\rm LO}$ is defined as:

${\rm
LO}:=\frac{1}{n}\sum_{i=1}^{n}\phi(y_{i},\mathbf{x}_{i}^{\top}\widehat{\bm{\beta}}_{/i}).$

The success of ${\rm LO}$ in practical scenarios has encouraged numerous
researchers to investigate its accuracy and develop several computationally-
efficient approximations for it (Rahnama Rad et al., 2020; Rahnama Rad and
Maleki, 2020; Patil et al., 2021, 2022, 2023; Xu et al., 2021; Bellec, 2023;
Beirami et al., 2017; Auddy et al., 2023; Stephenson and Broderick, 2020;
Stephenson et al., 2021; Luo et al., 2023; Austern and Zhou, 2020). Notably,
key references that are related to our current work are (Rahnama Rad et al.,
2020; Burman, 1989). In their study, (Burman, 1989) studied the accuracy of
${\rm LO}$ in the low-dimensional setting, $p$ fixed, while
$n\rightarrow\infty$ and established the consistency of ${\rm LO}$. In other
words, they proved that ${\rm LO}\stackrel{{\scriptstyle p}}{{\to}}{\rm OO}$.
In the more recent paper (Rahnama Rad et al., 2020), the authors studied the
accuracy of the ${\rm LO}$ under the high-dimensional setting, similar to the
setting we consider in this paper. However, it is worth noting that the
conclusions drawn in (Rahnama Rad et al., 2020) are contingent upon the
following two assumptions that restrict the broader applicability of their
outcomes:

  1. 1.

Restriction 1: The regularizer is twice differentiable.

  2. 2.

Restriction 2: The set $\bm{\Theta}$ is the same as $\mathbb{R}^{p}$.

The first assumption excludes a majority of crucial regularizers commonly
employed in practical scenarios, including the $\ell_{1}$ norm, nuclear norm,
group-LASSO, etc. Additionally, the second assumption eliminates scenarios
where parameters adhere to a specific set. Instances of such situations arise
when a practitioner seeks to estimate a positive definite matrix or when the
elements of $\bm{\beta}^{*}$ are required to be positive, increasing, or both.

Our paper aims to eliminate Restriction 1 and Restriction 2, which constrained
the applicability of the results in (Rahnama Rad et al., 2020) to numerous
real-world problems, and still obtain a sharp upper bound on the error ${\rm
LO}-{\rm OO}$.

The main technical novelties that have enabled us to achieve these goals are
clarified in Section 2.

###  1.3 Notations

In this section, we summarize the symbols we use throughout the article.
Vectors are denoted with boldfaced lowercase letter, such as $\mathbf{x}$.
Matrices are represented by boldfaced capital letters, such as $\mathbf{X}$.
For a matrix $\mathbf{X}$, $\sigma_{\min}(\mathbf{X})$, $\|\mathbf{X}\|$,
$\operatorname{tr}(\mathbf{X})$ denote the minimum singular value, the
spectral norm (equal to the maximum singular value
$\sigma_{\max}(\mathbf{X})$), and the trace of the matrix $\mathbf{X}$
respectively.

We denote ${\cal D}$ as the full dataset
$\\{(y_{i},\mathbf{x}_{i})\\}_{i=1}^{n}$, and ${\cal D}_{/i}$ as the dataset
excluding the $i^{\rm th}$ observation, i.e. ${\cal
D}_{/i}=\\{(y_{j},\mathbf{x}_{j}):j\neq i\\}$. We also use
$[n]:=\\{1,2,...,n\\}$ for any positive integer $n$.

For brevity we denote
$\ell_{j}(\bm{\beta}):=\ell(y_{j},\mathbf{x}_{j}^{\top}\bm{\beta})$, and
similarly $\phi_{j}(\bm{\beta}):=\phi(y_{j},\mathbf{x}_{j}^{\top}\bm{\beta})$.
The following definitions are also used:

$\displaystyle\dot{\ell}_{i}(\bm{\beta})$
$\displaystyle:=\frac{\partial\ell(y_{i},z)}{\partial
z}\bigg{|}_{z=\mathbf{x}_{i}^{\top}\bm{\beta}},\dot{\phi}_{i}(\bm{\beta}):=\frac{\partial\phi(y_{i},z)}{\partial
z}\bigg{|}_{z=\mathbf{x}_{i}^{\top}\bm{\beta}}.$

Polynomials of $\log(n)$ are denoted by ${\rm PolyLog}(n)$. When it is
specifically defined, a subscript is added. For $x,y\in\mathbb{R}$, we write
$x\wedge y$ and $x\vee y$ to denote $\min\\{x,y\\}$ and $\max\\{x,y\\}$
respectively.

The usage of $O(1)$ and $o(1)$ are conventional, and $a_{n}=\Theta(1)$ iff
both $a_{n}$ and $a_{n}^{-1}$ are $O(1)$. Similarly, for a sequence of random
variables, $X_{n}=O_{p}(1)$ means $X_{n}$ being stochastically bounded, i.e.
$\exists C>0$ s.t. $\mathbb{P}(|X_{n}|>C)\to 0$. Similarly $X_{n}=o_{p}(1)$
means $X_{n}$ converge to zero in probability, and $X_{n}=\Theta_{p}(1)$ iff
both $X_{n}$ and $X_{n}^{-1}$ are $O_{p}(1)$.

For a closed subset $\bm{\Theta}$ of $\mathbb{R}^{p}$, let ${\cal
C}^{k}(\bm{\Theta})$ denote the collection of all functions on $\bm{\Theta}$
with continuous $k^{{\rm th}}$ Fréchet derivative on the interior of
$\bm{\Theta}$. In particular, ${\cal C}^{0}(\bm{\Theta})$ consists of all
continuous functions on $\bm{\Theta}$.

###  1.4 Organization of our paper

The rest of the paper is organized as follows. The assumptions are listed in
Section 2.1, followed by discussions on them in Section 2.2. The main theorem
is stated in Section 2.3. In Section 3 we introduce the main challenges and
proof techniques (Section 3.1) and a proof sketch of the main theorem (Section
3.2). The concluding remarks are in Section 4. Detailed proofs of the lemmas
are postponed to the Appendix.

##  2 Main result

###  2.1 Assumptions

As we discussed in Section 1.2 our goal is to prove the accuracy of LO under
the high-dimensional settings. Before we state our main theorem we explain
some of the assumptions we have made and discuss their validity.

  1. A1

$\bm{\Theta}\subset\mathbb{R}^{p}$ is a closed convex set.

  2. A2

Both $n$ and $p$ are large, while $n/p\equiv\gamma_{0}\in(0,\infty)$.

  3. A3

$\mathbf{X}=(\mathbf{x}_{1},\cdots,\mathbf{x}_{n})^{\top}$ where
$\mathbf{x}_{i}\in\mathbb{R}^{p}$ are i.i.d. $N(0,\bm{\Sigma})$ samples.
Moreover, there exist constants $0<c_{X}\leq C_{X}$ such that
$p^{-1}c_{X}\leq\sigma_{\min}(\bm{\Sigma})\leq\sigma_{\max}(\bm{\Sigma})\leq
p^{-1}C_{X}$.

  4. A4

$r(\bm{\beta})=(1-\eta)r_{0}(\bm{\beta})+\eta\bm{\beta}^{\top}\bm{\beta}$
where $\eta\in(0,1)$ and $r_{0}$ is non-negative, convex and Lipschitz
continuous.

  5. A5

Assume that $\ell(y,z)$ and $\phi(y,z)$ are non-negative, convex and
continuously differentiable with respect to $z$ and that $\ell$, $\dot{\ell}$,
$\phi$ and $\dot{\phi}$ (defined in Section 1.3) grow polynomially in $y,z$,
i.e., there exist constants $s$ and $C>0$ such that

$\displaystyle\max\\{|\ell(y,z)|,|\dot{\ell}(y,z)|,|\phi(y,z)|,|\dot{\phi}(y,z)|\\}$
$\displaystyle\leq$ $\displaystyle C(1+|y|^{s}+|z|^{s})$

for all $(y,z)$. Furthermore, assume that all moments of $|y_{i}|$ are
bounded, i.e. $\forall m>0$ , $\exists$ constant $C_{Y}(m)$ depending only on
$m$, such that $\forall n\geq 1,\forall i\in[n]$:

$\mathbb{E}|y_{i}|^{m}\leq C_{Y}(m).$

###  2.2 Discussion of Assumptions

The goal of this section is to provide further intuition on the assumptions we
introduced in the previous section.

Assumption A1 is standard in convex optimization. Assumption A2 has become one
of the standard frameworks for studying high-dimensional problems (Obuchi and
Sakata, 2019; Mousavi et al., 2018; Xu et al., 2021; Miolane and Montanari,
2021; Donoho et al., 2009, 2011; Bu et al., 2019; Patil et al., 2021, 2022;
Jalali and Maleki, 2016; Bellec, 2023; Celentano et al., 2023; Li and Wei,
2022; Liang and Sur, 2022; Fan, 2022; Dudeja and Bakhshizadeh, 2022; Dudeja et
al., 2023), since it has been able to prove some of the peculiar features
estimators exhibit in high-dimensional settings, such as phase transitions
(Weng et al., 2018).

The Gaussianity of $\mathbf{x}_{i}$ in Assumption A3 is prevalent in
theoretical papers dealing with high-dimensional problems. While it is
straightforward to relax this assumption to sub-Gaussianity, we focus on
Gaussian distribution to keep the notations clear and simple. The scaling we
have adopted here, i.e.,

$p^{-1}c_{X}\leq\sigma_{\min}(\bm{\Sigma})\leq\sigma_{\max}(\bm{\Sigma})\leq
p^{-1}C_{X},$

is based on the following rationale. First note that

$\frac{c_{X}}{p}\|\bm{\beta}^{*}\|_{2}^{2}\leq\mathbb{E}(\mathbf{x}_{i}^{\top}\bm{\beta}^{*})^{2}\leq\frac{C_{X}}{p}\|\bm{\beta}^{*}\|_{2}^{2}.$

When $n,p\rightarrow\infty$ with $n/p\equiv\gamma_{0}$ and when the elements
of $\bm{\beta}^{*}$ are $O(1)$, we have $\|\bm{\beta}^{*}\|=O(\sqrt{p})$, and
hence $\mathbb{E}(\mathbf{x}_{i}^{\top}\bm{\beta}^{*})^{2}=O(1)$. Therefore,
under the settings of the paper we can see that the signal-to-noise ratio
(SNR) of each data point, defined as
$\frac{\operatorname{var}(\mathbf{x}_{i}^{\top}\bm{\beta}^{*})}{\operatorname{var}(y_{i}|\mathbf{x}_{i}^{\top}\bm{\beta}^{*})}$,
remains bounded. The reader may check Appendix B for details. Intuitively
speaking, if SNR per datapoint is very large, the estimation problem will be
easy and the problem of risk estimation is not of particular interest; maximum
likelihood estimators perform very well. On the other hand, if SNR per data
point is very small, the accurate estimation of $\widehat{\bm{\beta}}$ will
not be possible unless we impose conditions on $\bm{\beta}^{*}$, such as
stringent sparsity assumption. However, since we want our results to be
generic in terms of $\bm{\beta}^{*}$, we do not want to impose any stringent
constraint on $\bm{\beta}^{*}$.

Another way we can justify the scaling in Assumption A3 is that under this
scaling, neither the loss
$\sum_{j}\ell(y_{j},\mathbf{x}_{j}^{\top}\bm{\beta}^{*})$ nor the regularizer
$\lambda r(\bm{\beta}^{*})$ dominate each other when $n,p\to\infty$. In other
words, for a large class of losses
$\sum_{j}\ell(y_{j},\mathbf{x}_{j}^{\top}\bm{\beta}^{*})=O_{p}(n)$ and for a
large class of regularizers $\lambda r(\bm{\beta}^{*})=O_{p}(p)$. Given that
$n/p=\gamma_{0}$, the two terms have the same order. Effectively, this makes
the optimal choice of $\lambda$ (that gives the minimum out-of-sample error),
$O_{p}(1)$. For more precise arguments behind this, we refer the reader to
(Mousavi et al., 2018; Wang et al., 2020, 2022).

Assumptions A4 guarantees the loss function to be $2\lambda\eta$-strongly
convex. Researchers have noticed that in wide range of applications, adding
$\eta\bm{\beta}^{\top}\bm{\beta}$ in addition to the non-differentiable
regularizer often improves the prediction performance (Hastie et al., 2017;
Mazumder et al., 2023; Wang et al., 2022; Guo et al., 2023).

Assumption A4 also posits the Lipschitz continuity of $r_{0}$. Nearly all
popular non-differentiable regularizers satisfy this condition. Appendix C.1
presents several examples including LASSO, generalized LASSO and Schatten
norms with the nuclear norm as a special case.

Assumption A5 also holds for a wide range of models that are used in practice.
For instance Appendix C.2 considers standard data generation mechanisms that
are used in linear regression, logistic regression and Poisson regression, and
show that for all those models Assumption A5 holds.

###  2.3 Main theorem

The following theorem and its discussion are the main contributions of this
paper:

######  Theorem 2.1.

Under Assumption A1-A5, there exists a constant $C_{v}$ depending only on
$\\{\gamma_{0},\lambda,\eta,s,C_{X},C_{Y}(\cdot)\\}$ such that

$\displaystyle\mathbb{E}({\rm LO}-{\rm OO})^{2}$
$\displaystyle\leq\frac{C_{v}}{n}.$

Before we present the sketch of the proof, we would like to discuss this
theorem and provide some intuition.

######  Remark 2.1.

A simple conclusion of this theorem is that under the asymptotic setting in
which $n,p\rightarrow\infty$ and the ratio $n/p$ remains fixed, and
$p^{-1}c_{X}\leq\sigma_{\min}(\bm{\Sigma})\leq\sigma_{\max}(\bm{\Sigma})\leq
p^{-1}C_{X}$, LO offers a consistent estimate of the out-of-sample prediction
error in the sense that ${\rm LO}\rightarrow{\rm OO}$ in probability. However,
note that Theorem 2.1 offers more than the consistency, and it captures the
convergence rate as well.

######  Remark 2.2.

The rate $\frac{1}{n}$ obtained in Theorem 2.1 is expected to be sharp. Note
that the leave-one-out cross-validation takes an average of $n$ estimates of
the OO, namely $\phi(y_{i};\mathbf{x}_{i}^{\top}\widehat{\bm{\beta}}_{/i})$.
The variance of each of these estimates is $O(1)$. Hence, if all these
estimates were independent, the variance of LO would be still proportional to
$O(1/n)$, which is the same as the bound we have obtained.

######  Remark 2.3.

The rate $O(1/n)$ has also been seen in the previous work on the analysis of
LO under the low-dimensional asymptotic, where $p$ is fixed, while
$n\rightarrow\infty$. For instance, (Burman, 1989) provided a rate estimate of
the variance of ${\rm LO}$ (Theorem 6.2(c) in (Burman, 1989), notations
modified) and showed:

$\displaystyle\operatorname{var}({\rm LO}-{\rm OO})=O(1/n).$

Note that $\operatorname{var}({\rm LO}-{\rm OO})\leq\mathbb{E}({\rm LO}-{\rm
OO})^{2}$. Our result show that the rate is still $O(1/n)$ in high-dimensional
settings. More recently, the paper (Austern and Zhou, 2020) has characterized
the limiting distribution of the $k$-fold cross-validation under the low-
dimensional setting. In order to obtain a non-degenerate limiting distribution
for LO, (Austern and Zhou, 2020) has to scale ${\rm LO}-{\rm OO}$ with
$\sqrt{n}$. This scaling translates to the same scaling as the one in (Burman,
1989).

##  3 Proofs

###  3.1 Main challenges and novel techniques

As mentioned earlier, (Rahnama Rad et al., 2020) established a result akin to
Theorem 2.1 in the case where the regularizer is twice differentiable, and
there is no constraint, i.e. $\bm{\Theta}=\mathbb{R}^{p}$.

In our proof, there are two new challenges: the non-smoothness of the
regularizer $r$, and the existence of the convex constraint $\bm{\Theta}$. We
introduce two novel elements that allowed us to significantly broaden the
scope of Theorem 2.1 well beyond what was offered by (Rahnama Rad et al.,
2020): smoothing and projection.

  1. 1.

Smoothing: We start with approximating the non-smooth regularizer,
$r_{0}(\bm{\beta})$ with a smooth function:

$r_{0}^{\alpha}(\bm{\beta})=\int_{\bm{\Theta}}r_{0}(\bm{\beta}-\mathbf{z})\alpha\phi(\alpha\mathbf{z})d\mathbf{z}$

where
$\phi(\mathbf{z})=(2\pi)^{-p/2}e^{-\frac{1}{2}\mathbf{z}^{\top}\mathbf{z}}$ is
the density of a standard Gaussian vector.***Note that when $\bm{\beta}$ is a
$p_{1}$ by $p_{2}$ matrix, we concatenate its rows to form a vector of
dimension $p=p_{1}\times p_{2}$. The following lemma shows one of the
properties of this approximation that will be used throughout the paper.

######  Lemma 1.

Suppose $\bm{\Theta}$ is closed and $r\in{\cal C}^{0}(\bm{\Theta})$.

    1. (a)

Suppose there exists a positive integer $K$ such that
$r(\mathbf{z})\left\lVert\mathbf{z}\right\rVert_{2}^{k}e^{-\frac{1}{2}\left\lVert\bm{\beta}-\mathbf{z}\right\rVert_{2}^{2}}$
is integrable. Then $r^{\alpha}$ defined in (1) is in ${\cal
C}^{k}(\bm{\Theta}_{0})$ where $\bm{\Theta}_{0}$ is the interior of
$\bm{\Theta}$.

    2. (b)

Suppose there exist constants $L>0$ and $k\in(0,1]$ such that for all
$\mathbf{x},\mathbf{y}\in\bm{\Theta}$,

$|r(\mathbf{x})-r(\mathbf{y})|\leq
L\left\lVert\mathbf{x}-\mathbf{y}\right\rVert_{2}^{k}.$

Then as $\alpha\to\infty$, we have

$\left\lVert r^{\alpha}-r\right\rVert_{\infty}\to 0.$

The proof of this lemma is presented in Appendix D.1. Note that all
assumptions in Lemma 1 are satisfied when $r$ is Lipschitz continuous as in
Assumption A4. This lemma implies that $r_{0}^{\alpha}(\bm{\beta})$ is an
accurate approximation of $r_{0}(\bm{\beta})$ for all values of $\bm{\beta}$.
Define

$\displaystyle\widehat{\bm{\beta}}^{\alpha}$
$\displaystyle:=\underset{\bm{\beta}\in\bm{\Theta}}{\operatorname{argmin}}\sum_{j=1}^{n}\ell_{j}(\bm{\beta})+\lambda(1-\eta)r_{0}^{\alpha}(\bm{\beta})+\lambda\eta\bm{\beta}^{\top}\bm{\beta}$
$\displaystyle\widehat{\bm{\beta}}^{\alpha}_{/i}$
$\displaystyle:=\underset{\bm{\beta}\in\bm{\Theta}}{\operatorname{argmin}}\sum_{j\neq
i}\ell_{j}(\bm{\beta})+\lambda(1-\eta)r_{0}^{\alpha}(\bm{\beta})+\lambda\eta\bm{\beta}^{\top}\bm{\beta}.$

Our final goal is to show that by analyzing the ${\rm LO}$ for the surrogate
estimates $\widehat{\bm{\beta}}_{/i}^{\alpha}$ and
$\widehat{\bm{\beta}}^{\alpha}$ we can also analyze the ${\rm LO}$ for the
original estimates $\widehat{\bm{\beta}}_{/i}$ and $\widehat{\bm{\beta}}$.
This will be clarified in Section 3.2.

  2. 2.

Projection operator: The second challenge we have to address in proving
Theorem 2.1 is the existence of the constraint set $\bm{\Theta}$. One can
write the optimization problem
$\widehat{\bm{\beta}}=\underset{\bm{\beta}\in\bm{\Theta}}{\operatorname{argmin}}\sum_{i=1}^{n}\ell_{i}(\bm{\beta})+\lambda
r(\bm{\beta})$ as

$\displaystyle\widehat{\bm{\beta}}=\underset{\bm{\beta}}{\operatorname{argmin}}\sum_{i=1}^{n}\ell_{i}(\bm{\beta})+\lambda
r(\bm{\beta})+{\mathbf{I}}_{\bm{\Theta}}(\bm{\beta}),$

where ${\mathbf{I}}_{\bm{\Theta}}(\bm{\beta})$ is the convex indicator
function of the set $\bm{\Theta}$, and treat the constraint as another non-
differentiable regularizer and use smoothing again. However, indicator
function ${\mathbf{I}}_{\bm{\Theta}}(\bm{\beta})$ is not a Lipschitz function
and cannot be uniformly approximated by smooth functions. Hence the smoothing
argument discussed before will not work. Hence, we pick a different approach
and represent $\widehat{\bm{\beta}}^{\alpha}$ in a different way. The
following lemma provides this alternative representation:

######  Lemma 2.

Suppose

     * •

$R:\mathbb{R}^{p}\to\mathbb{R}\cup\\{-\infty,\infty\\}$ is proper convex with
$dom(R)$ being closed.

     * •

$L:\mathbb{R}^{p}\to\mathbb{R}$ is differentiable on the relative interior of
$dom(R)$ and proper convex on $dom(R)$.

Define the proximal operator of the function $R$ as

$\mathbf{prox}_{R}(\mathbf{u}):=\operatorname{argmin}_{\mathbf{x}}\left\\{R(\mathbf{x})+\frac{1}{2}\|\mathbf{u}-\mathbf{x}\|_{2}^{2}\right\\}.$

Then a solution of the following equation:

$\mathbf{x}=\mathbf{prox}_{R}(\mathbf{x}-\nabla L(\mathbf{x}))$

is also a minimizer of the problem

$\min_{\mathbf{x}}\left\\{L(\mathbf{x})+R(\mathbf{x})\right\\}$

and vice versa.

###### Proof.

See Propositon 3.1 (iii)(b) in (Combettes and Wajs, 2005). ∎

Using this lemma we find a new representation for $\widehat{\bm{\beta}}$.
Consider the problem with a convex constraint:

$\widehat{\bm{\beta}}=\underset{\bm{\beta}\in\bm{\Theta}}{\operatorname{argmin}}\sum_{i}\ell_{i}(\bm{\beta})+\lambda
r(\bm{\beta}).$

where $\ell$ and $r$ are smooth, $\bm{\Theta}$ is a closed convex set. Using
Lemma 2 with $L(\bm{\beta})=\sum_{i}\ell_{i}(\bm{\beta})+\lambda
r(\bm{\beta})$ and $R(\bm{\beta})=\mathbf{I}_{\bm{\Theta}}(\bm{\beta})$ where
$\mathbf{I}_{\bm{\Theta}}(\bm{\beta})$ is the convex indicator
function†††Convex indicator function of set $\bm{\Theta}$ is defined as:
$\mathbf{I}_{\bm{\Theta}}(\bm{\beta})=0$ if $\bm{\beta}\in\bm{\Theta}$ and
$\mathbf{I}_{\bm{\Theta}}(\bm{\beta})=+\infty$ otherwise, we have that
$\widehat{\bm{\beta}}$ should satisfy

$\displaystyle\widehat{\bm{\beta}}$
$\displaystyle=\mathbf{prox}_{\mathbf{I}_{\bm{\Theta}}}(\widehat{\bm{\beta}}-\sum_{i}\dot{\ell}_{i}(\widehat{\bm{\beta}})\mathbf{x}_{i}-\lambda\nabla
r(\widehat{\bm{\beta}}))$
$\displaystyle=\bm{\Pi}_{\bm{\Theta}}(\widehat{\bm{\beta}}-\sum_{i}\dot{\ell}_{i}(\widehat{\bm{\beta}})\mathbf{x}_{i}-\lambda\nabla
r(\widehat{\bm{\beta}})),$ (6)

where $\bm{\Pi}_{\bm{\Theta}}$ is the metric projection operator

$\bm{\Pi}_{\bm{\Theta}}(\mathbf{x}):=\underset{\mathbf{z}\in\bm{\Theta}}{\operatorname{argmin}}\|\mathbf{x}-\mathbf{z}\|_{2}.$

Note that to obtain the last equality in (6), we have used the fact that the
proximal operator of $\mathbf{I}_{\bm{\Theta}}$ is the same as the metric
projection onto set $\bm{\Theta}$.

Using (6), instead of representing $\widehat{\bm{\beta}}^{\alpha}$ as the
minimizer of $\sum_{i=1}^{n}\ell_{i}(\bm{\beta})+\lambda
r^{\alpha}(\bm{\beta})+{\mathbf{I}}_{\bm{\Theta}}(\bm{\beta})$, we represent
it as the solution of the following fix point equation:

$\displaystyle\widehat{\bm{\beta}}^{\alpha}=\bm{\Pi}_{\bm{\Theta}}(\widehat{\bm{\beta}}^{\alpha}-\nabla
h^{\alpha}(\widehat{\bm{\beta}}^{\alpha}))$

where $\bm{\Pi}_{\bm{\Theta}}(\cdot)$ denotes the metric projection onto
$\bm{\Theta}$. Similarly, $\widehat{\bm{\beta}}_{/i}^{\alpha}$ satisfies:

$\displaystyle\widehat{\bm{\beta}}_{/i}^{\alpha}=\bm{\Pi}_{\bm{\Theta}}(\widehat{\bm{\beta}}_{/i}^{\alpha}-\nabla
h_{/i}^{\alpha}(\widehat{\bm{\beta}}_{/i}^{\alpha})),$

The following lemma establishes some of the important properties of the
projection operators that are particularly useful in our paper:

######  Lemma 3.

Suppose $\bm{\Theta}$ is a closed convex set in $\mathbb{R}^{p}$, and
$\mathbf{x},\mathbf{y}\in\mathbb{R}^{p}$. Let $\bm{\Pi}_{\bm{\Theta}}$ be the
metric projection onto $\bm{\Theta}$. Then there exists a matrix-valued
function $\mathbf{J}(t)$ with

$0\leq\lambda_{\min}(\mathbf{J}(t))\leq\lambda_{\max}(\mathbf{J}(t))\leq
1,\quad\forall t\in[0,1]$

such that

$\bm{\Pi}_{\bm{\Theta}}(\mathbf{y})-\bm{\Pi}_{\bm{\Theta}}(\mathbf{x})=\int_{0}^{1}\mathbf{J}(t)dt(\mathbf{y}-\mathbf{x}).$

For completeness, we include the proof of this well known result in Section
D.2.

In the next section, we explain how using the surrogate estimates
$\widehat{\bm{\beta}}_{/i}^{\alpha}$ and $\widehat{\bm{\beta}}^{\alpha}$ and
representing them as the solution of, e.g.

$\displaystyle\widehat{\bm{\beta}}_{/i}^{\alpha}=\bm{\Pi}_{\bm{\Theta}}(\widehat{\bm{\beta}}_{/i}^{\alpha}-\nabla
h_{/i}^{\alpha}(\widehat{\bm{\beta}}_{/i}^{\alpha})),$

enable us to obtain an upper bound on the difference ${\rm LO}-{\rm OO}$.

###  3.2 Proof summary of Theorem 2.1

In this subsection, we present a brief sketch of the proof. Similar to the
proof of Theorem 1 in (Rahnama Rad et al., 2020) we use the following two
definitions:

$\displaystyle V_{1}$ $\displaystyle={\rm
LO}-\frac{1}{n}\sum_{i\in[n]}\mathbb{E}[\phi_{i}(\widehat{\bm{\beta}}_{/i})|{\cal
D}_{/i}],$ $\displaystyle V_{2}$
$\displaystyle=\frac{1}{n}\sum_{i\in[n]}\mathbb{E}[\phi_{i}(\widehat{\bm{\beta}}_{/i})|{\cal
D}_{/i}]-{\rm OO},$

and use the following upper bound on $\mathbb{E}\left[{\rm LO}-{\rm
OO}\right]^{2}$:

$\displaystyle\mathbb{E}\left[{\rm LO}-{\rm
OO}\right]^{2}=\mathbb{E}\left(V_{1}+V_{2}\right)^{2}\leq
2\mathbb{E}V_{1}^{2}+2\mathbb{E}V_{2}^{2}.$ (7)

Hence, the remaining steps are to obtain upper bounds for
$\mathbb{E}V_{1}^{2}$ and $\mathbb{E}V_{2}^{2}$. To see how the ideas we
introduced in Section 3.1 enable us to obtain the required upper bound, we
provide the details of proving an upper bound for $\mathbb{E}V_{2}^{2}$ (which
is shorter) here, and postpone the problem of finding an upper bound for
$\mathbb{E}V_{1}^{2}$ to Appendix D.6.

To bound $\mathbb{E}V_{2}^{2}$, first notice that for all $j\neq i$ we have

$\displaystyle\mathbb{E}[\phi_{j}(\widehat{\bm{\beta}}_{/i})|{\cal D}_{/i}]$
$\displaystyle=\mathbb{E}[\phi_{0}(\widehat{\bm{\beta}}_{/i})|{\cal
D}_{/i}]=\mathbb{E}[\phi_{0}(\widehat{\bm{\beta}}_{/i})|{\cal D}].$

By the mean-value theorem, for each $i$ there exists a random variable
$\bm{\xi}_{i}=t_{i}\widehat{\bm{\beta}}_{/i}+(1-t_{i})\widehat{\bm{\beta}}$
with $t_{i}\in[0,1]$ such that

$\phi_{0}(\widehat{\bm{\beta}}_{/i})-\phi_{0}(\widehat{\bm{\beta}})=\dot{\phi}_{0}(\bm{\xi}_{i})\mathbf{x}_{0}^{\top}(\widehat{\bm{\beta}}_{/i}-\widehat{\bm{\beta}}).$

Then we have

$\displaystyle\mathbb{E}(V_{2}^{2})$
$\displaystyle=\mathbb{E}\left(\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}[\phi_{i}(\widehat{\bm{\beta}}_{/i})|{\cal
D}_{/i}]-\mathbb{E}[\phi_{0}(\widehat{\bm{\beta}})|{\cal D}]\right)^{2}$
$\displaystyle=\mathbb{E}\left(\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}[\phi_{0}(\widehat{\bm{\beta}}_{/i})|{\cal
D}]-\mathbb{E}[\phi_{0}(\widehat{\bm{\beta}})|{\cal D}]\right)^{2}$
$\displaystyle=\frac{1}{n^{2}}\mathbb{E}\left(\sum_{i=1}^{n}\mathbb{E}[\dot{\phi}_{0}(\bm{\xi}_{i})\mathbf{x}_{0}^{\top}(\widehat{\bm{\beta}}_{/i}-\widehat{\bm{\beta}})|{\cal
D}]\right)^{2}$
$\displaystyle=\frac{1}{n^{2}}\sum_{i=1}^{n}\sum_{j=1}^{n}\mathbb{E}\Big{(}\mathbb{E}[\dot{\phi}_{0}(\bm{\xi}_{i})\mathbf{x}_{0}^{\top}(\widehat{\bm{\beta}}_{/i}-\widehat{\bm{\beta}})|{\cal
D}]$ $\displaystyle\hskip
56.9055pt\cdot\mathbb{E}[\dot{\phi}_{0}(\bm{\xi}_{j})\mathbf{x}_{0}^{\top}(\widehat{\bm{\beta}}_{/j}-\widehat{\bm{\beta}})|{\cal
D}]\Big{)}$
$\displaystyle\leq\frac{1}{n^{2}}\sum_{i=1}^{n}\sum_{j=1}^{n}\sqrt{\mathbb{E}\Big{(}\mathbb{E}[\dot{\phi}_{0}(\bm{\xi}_{i})\mathbf{x}_{0}^{\top}(\widehat{\bm{\beta}}_{/i}-\widehat{\bm{\beta}})|{\cal
D}]\Big{)}^{2}}$ $\displaystyle\hskip
56.9055pt\cdot\sqrt{\mathbb{E}\Big{(}\mathbb{E}[\dot{\phi}_{0}(\bm{\xi}_{j})\mathbf{x}_{0}^{\top}(\widehat{\bm{\beta}}_{/j}-\widehat{\bm{\beta}})|{\cal
D}]\Big{)}^{2}}$
$\displaystyle=\mathbb{E}\Big{(}\mathbb{E}[\dot{\phi}_{0}(\bm{\xi}_{1})\mathbf{x}_{0}^{\top}(\widehat{\bm{\beta}}_{/1}-\widehat{\bm{\beta}})|{\cal
D}]\Big{)}^{2},$ (8)

where we use Cauchy Schwarz inequality in the penultimate step. Next we have

$\displaystyle\left\lvert\mathbb{E}[\dot{\phi}_{0}(\bm{\xi}_{i})\mathbf{x}_{0}^{\top}(\widehat{\bm{\beta}}_{/i}-\widehat{\bm{\beta}})|{\cal
D}]\right\rvert$ $\displaystyle\leq$
$\displaystyle\sqrt{\mathbb{E}[\dot{\phi}_{0}^{2}(\bm{\xi}_{i})|{\cal
D}]\mathbb{E}[(\widehat{\bm{\beta}}_{/i}-\widehat{\bm{\beta}})^{\top}\mathbf{x}_{0}\mathbf{x}_{0}^{\top}(\widehat{\bm{\beta}}_{/i}-\widehat{\bm{\beta}})|{\cal
D}]}$ $\displaystyle\leq$
$\displaystyle\sqrt{\mathbb{E}[\dot{\phi}_{0}^{2}(\bm{\xi}_{i})|{\cal
D}]}\sqrt{\frac{C_{X}}{p}\|\widehat{\bm{\beta}}_{/i}-\widehat{\bm{\beta}}\|^{2}}$
(9)

where the last inequality uses the independence between $\mathbf{x}_{0}$ and
${\cal D}$ and also the fact that
$\sigma_{\max}(\bm{\Sigma})\leq\frac{C_{X}}{p}$ by Assumption A3.

Hence, in order to bound $\mathbb{E}(V_{2}^{2})$, we have to obtain bounds on
$\|\widehat{\bm{\beta}}-\widehat{\bm{\beta}}_{/i}\|$ and also
$\mathbb{E}[\dot{\phi}_{0}^{2}(\bm{\xi}_{i})|{\cal D}]$. That is what the next
two lemmas aim to do. The first lemma connects $\widehat{\bm{\beta}}_{/i}$ and
$\widehat{\bm{\beta}}$:

######  Lemma 4.

Under assumptions A1-A4, we have for all $\alpha>0$ that

$\displaystyle\left\lVert\widehat{\bm{\beta}}-\widehat{\bm{\beta}}_{/i}\right\rVert\leq\frac{|\dot{\ell}_{i}(\widehat{\bm{\beta}}_{/i})|\left\lVert\mathbf{x}_{i}\right\rVert}{2\lambda\eta\wedge
1}.$

The proof of this lemma is presented in Section D.3 and uses the ideas that we
mentioned in Section 2, i.e. smoothing and projection operator.

The next lemma bounds the moments of $\phi_{0}$ and $\dot{\phi}_{0}$:

######  Lemma 5.

Suppose assumptions A1-A5 hold. Then there exists a constant $C_{\phi}$
depending only on $s$ (from Assumption A5) and $C_{X}$ (from Assumption A3)
such that $\forall\bm{\beta}\in\mathbb{R}^{p}$:

$\displaystyle\sqrt{\mathbb{E}[\phi_{0}^{2}(\bm{\beta})]}$ $\displaystyle\leq
C_{\phi}+C_{\phi}\left(\frac{1}{p}\|\bm{\beta}\|^{2}\right)^{s/2},$
$\displaystyle\sqrt{\mathbb{E}[\dot{\phi}_{0}^{2}(\bm{\beta})]}$
$\displaystyle\leq
C_{\phi}+C_{\phi}\left(\frac{1}{p}\|\bm{\beta}\|^{2}\right)^{s/2},$
$\displaystyle\sqrt{\mathbb{E}[\dot{\phi}_{0}^{4}(\bm{\beta})]}$
$\displaystyle\leq
C_{\phi}^{2}+C_{\phi}^{2}\left(\frac{1}{p}\|\bm{\beta}\|^{2}\right)^{s}.$

The proof of this lemma can be found in Section D.4.

Inserting Lemma 4 and Lemma 5 back into (9) we have

$\displaystyle\left\lvert\mathbb{E}[\dot{\phi}_{0}(\bm{\xi}_{1})\mathbf{x}_{0}^{\top}(\widehat{\bm{\beta}}_{/1}-\widehat{\bm{\beta}})|{\cal
D}]\right\rvert$ $\displaystyle\leq$
$\displaystyle\left(C_{\phi}+C_{\phi}\left(\frac{1}{p}\|\bm{\xi}_{1}\|^{2}\right)^{\frac{s}{2}}\right)\sqrt{\frac{C_{X}}{p}}\frac{|\dot{\ell}_{1}(\widehat{\bm{\beta}}_{/1})|\|\mathbf{x}_{1}\|}{2\lambda\eta\wedge
1}.$

Hence, if we use (3.2), then we will obtain

$\displaystyle\mathbb{E}V_{2}^{2}$ $\displaystyle\leq$
$\displaystyle\mathbb{E}\left(C_{\phi}^{2}\left(1+\frac{\|\bm{\xi}_{1}\|^{s}}{p^{s/2}}\right)^{2}\frac{C_{X}}{p(2\lambda\eta\wedge
1)^{2}}\dot{\ell}_{1}^{2}(\widehat{\bm{\beta}}_{/1})\|\mathbf{x}_{1}\|^{2}\right)$
$\displaystyle\overset{(a)}{\leq}$
$\displaystyle\frac{C_{\phi}^{2}C_{X}}{p(2\lambda\eta\wedge
1)^{2}}\sqrt{\mathbb{E}\left(1+\frac{1}{p^{s/2}}\|\bm{\xi}_{1}\|^{s}\right)^{4}}\times$
$\displaystyle~{}\hskip
56.9055pt\times\sqrt{\mathbb{E}\left(\dot{\ell}_{1}^{4}(\widehat{\bm{\beta}}_{/1})\|\mathbf{x}_{1}\|^{4}\right)}$
$\displaystyle\overset{(b)}{\leq}$
$\displaystyle\frac{1}{n}\frac{C_{\phi}^{2}C_{X}\gamma_{0}}{(2\lambda\eta\wedge
1)^{2}}\sqrt{8\left(1+\mathbb{E}\left(\frac{1}{p}\|\bm{\xi}_{1}\|^{2}\right)^{2s}\right)}$
$\displaystyle\times\left(\mathbb{E}\dot{\ell}_{1}^{8}(\widehat{\bm{\beta}}_{/1})\right)^{\frac{1}{4}}\cdot\left(\mathbb{E}\|\mathbf{x}_{1}\|^{8}\right)^{\frac{1}{4}}.$
(10)

where steps (a) and (b) both used Cauchy Schwarz Inequality. The following
lemma bounds
$\mathbb{E}\left(\frac{1}{p}\|\widehat{\bm{\beta}}\|^{2}\right)^{t}$ and
$\mathbb{E}\dot{\ell}_{1}^{8}(\widehat{\bm{\beta}}_{/1})$:

######  Lemma 6.

Under assumptions A1-A5, there exist constants $C_{\beta}(t)$ depending on
$\\{\gamma_{0},\lambda,\eta,C_{Y}(\cdot),s,t\\}$ and $C_{\ell}$ depending on
$\\{\gamma_{0},\lambda,\eta,C_{Y}(\cdot),s,C_{X}\\}$ such that

  1. (a)

For $t\geq 1$,

$\displaystyle\mathbb{E}[p^{-1}\|\widehat{\bm{\beta}}\|^{2}]^{t}$
$\displaystyle\leq C_{\beta}(t)$
$\displaystyle\mathbb{E}[p^{-1}\|\widehat{\bm{\beta}}_{/1}\|^{2}]^{t}$
$\displaystyle\leq C_{\beta}(t),$

  2. (b)

$\mathbb{E}\dot{\ell}_{1}^{8}(\widehat{\bm{\beta}}_{/1})\leq C_{\ell}$.

The proof of this lemma can be found in Section D.5. Observe that
$\bm{\xi}_{1}$ is a convex combination of $\widehat{\bm{\beta}}$ and
$\widehat{\bm{\beta}}_{/i}$, then using part (a) of Lemma 6 we have that the
same bound applies to $p^{-1}\|\bm{\xi}_{1}\|^{2}$. Next, by Lemma 8 we have
$\mathbb{E}\|\mathbf{x}_{1}\|^{8}\leq 24C_{X}^{4}$. Inserting the above bounds
into (10) we have

$\displaystyle\mathbb{E}V_{2}^{2}$
$\displaystyle\leq\frac{1}{n}\frac{C_{\phi}^{2}C_{X}\gamma_{0}}{(2\lambda\eta\wedge
1)^{2}}\sqrt{8\left(1+C_{\beta}(2s)\right)}\cdot
C_{\ell}^{\frac{1}{4}}\cdot(24C_{X}^{4})^{\frac{1}{4}}$
$\displaystyle\leq\frac{1}{n}\frac{7C_{\phi}^{2}C_{X}^{2}C_{\ell}^{1/4}\gamma_{0}}{(2\lambda\eta\wedge
1)^{2}}\sqrt{1+C_{\beta}(2s)}$ $\displaystyle:=\frac{C_{v2}}{n}.$ (11)

The second line uses the fact that $\sqrt{8}(24)^{1/4}\leq 7$.

Obtaining an upper bound for $\mathbb{E}(V_{1}^{2})$ uses similar techniques,
although it involves more cumbersome calculations. In fact we can prove that

######  Lemma 7.

Under assumptions A1-A5, for large enough $n,p$ we have:

$\displaystyle\mathbb{E}V_{1}^{2}\leq\dfrac{C_{v1}}{n}$

for $C_{v1}>0$ depending only on
$\\{\gamma_{0},\lambda,\eta,C_{Y}(\cdot),s,C_{X}\\}$.

The proof of Lemma 7 is given in Section D.6.

Combining Lemma 7 and (11) with (7) completes the proof of Theorem 2.1:

$\mathbb{E}[{\rm LO}-{\rm OO}]^{2}\leq
2\mathbb{E}V_{1}^{2}+2\mathbb{E}V_{2}^{2}\leq\frac{2(C_{v1}+C_{v2})}{n}:=\frac{C_{v}}{n}.$

##  4 Conclusion

In this paper, our focus was on the class of regularized empirical risk
minimization (R-ERM) techniques that incorporate non-differentiable
regularizers. We studied the accuracy of leave-one-out cross-validation
techniques within a high-dimensional setting, where both the number of
observations $n$ and the number of features $p$ are large while the ratio
$n/p$ is bounded. We derived a finite-sample upper bound for the difference
between the out-of-sample prediction error and its leave-one-out cross-
validation estimate. Our upper bound shows that if ${\rm OO}$ and ${\rm LO}$
represent the out-of-sample prediction error and its leave-one-out estimate,
then $\mathbb{E}({\rm LO}-{\rm OO})^{2}=O(\frac{1}{n})$.

## Acknowledgments

Arian Maleki would like to thank NSF (National Science Foundation) for their
generous support through grant number DMS-2210506. Kamiar Rahnama Rad would
like to thank NSF (National Science Foundation) for their generous support
through grant number DMS-1810888.

## References

  * Auddy et al. (2023) Arnab Auddy, Haolin Zou, Kamiar Rahnama Rad, and Arian Maleki.  Approximate leave-one-out cross validation for regression with $\ell_{1}$ regularizers (extended version).  _arXiv preprint arXiv:2310.17629_ , 2023.
  * Austern and Zhou (2020) Morgane Austern and Wenda Zhou.  Asymptotics of cross-validation.  _arXiv preprint arXiv:2001.11111_ , 2020.
  * Beirami et al. (2017) Ahmad Beirami, Meisam Razaviyayn, Shahin Shahrampour, and Vahid Tarokh.  On optimal generalizability in parametric learning.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Bellec (2023) Pierre C Bellec.  Out-of-sample error estimation for m-estimators with convex penalty.  _Information and Inference: A Journal of the IMA_ , 12(4):2782–2817, 2023.
  * Bu et al. (2019) Zhiqi Bu, Jason M. Klusowski, Cynthia Rush, and Weijie J. Su.  Algorithmic Analysis and Statistical Estimation of SLOPE via Approximate Message Passing.  _IEEE Transactions on Information Theory_ , 67:506–537, 2019.
  * Burman (1989) Prabir Burman.  A comparative study of ordinary cross-validation, v-fold cross-validation and the repeated learning-testing methods.  _Biometrika_ , 76(3):503–514, 1989.
  * Celentano et al. (2023) Michael Celentano, Andrea Montanari, and Yuting Wei.  The lasso with general gaussian designs with applications to hypothesis testing.  _The Annals of Statistics_ , 51(5):2194–2220, 2023.
  * Combettes and Wajs (2005) Patrick L. Combettes and Valérie R. Wajs.  Signal recovery by proximal forward-backward splitting.  _Multiscale Modeling & Simulation_, 4(4):1168–1200, 2005.
  * Donoho et al. (2009) David L Donoho, Arian Maleki, and Andrea Montanari.  Message-passing algorithms for compressed sensing.  _Proceedings of the National Academy of Sciences_ , 106(45):18914–18919, 2009.
  * Donoho et al. (2011) David L Donoho, Arian Maleki, and Andrea Montanari.  The noise-sensitivity phase transition in compressed sensing.  _IEEE Transactions on Information Theory_ , 57(10):6920–6941, 2011.
  * Dudeja and Bakhshizadeh (2022) Rishabh Dudeja and Milad Bakhshizadeh.  Universality of linearized message passing for phase retrieval with structured sensing matrices.  _IEEE Transactions on Information Theory_ , 68(11):7545–7574, 2022.
  * Dudeja et al. (2023) Rishabh Dudeja, Yue M. Lu, and Subhabrata Sen.  Universality of approximate message passing with semirandom matrices.  _The Annals of Probability_ , 51(5):1616–1683, 2023.
  * Fan (2022) Zhou Fan.  Approximate message passing algorithms for rotationally invariant matrices.  _The Annals of Statistics_ , 50(1):197–224, 2022\.
  * Guo et al. (2023) Yilin Guo, Haolei Weng, and Arian Maleki.  Signal-to-noise ratio aware minimaxity and higher-order asymptotics.  _IEEE Transactions on Information Theory_ , 2023.
  * Hastie et al. (2017) Trevor Hastie, Robert Tibshirani, and Ryan J Tibshirani.  Extended comparisons of best subset selection, forward stepwise selection, and the lasso.  _arXiv preprint arXiv:1707.08692_ , 2017.
  * Ibragimov and Sharakhmetov (2001) R. Ibragimov and Sh. Sharakhmetov.  The best constant in the rosenthal inequality for nonnegative random variables.  _Statistics & Probability Letters_, 55(4):367–376, 2001.
  * Jalali and Maleki (2016) Shirin Jalali and Arian Maleki.  New approach to bayesian high-dimensional linear regression.  _Information and Inference: A Journal of the IMA_ , 7, 07 2016.
  * Li and Wei (2022) Gen Li and Yuting Wei.  A non-asymptotic framework for approximate message passing in spiked models.  _arXiv preprint arXiv:2208.03313_ , 2022.
  * Liang and Sur (2022) Tengyuan Liang and Pragya Sur.  A precise high-dimensional asymptotic theory for boosting and minimum-$\ell_{1}$-norm interpolated classifiers.  _The Annals of Statistics_ , 50(3):1669–1695, 2022.
  * Luo et al. (2023) Yuetian Luo, Zhimei Ren, and Rina Barber.  Iterative approximate cross-validation.  In _International Conference on Machine Learning_ , pages 23083–23102. PMLR, 2023.
  * Mazumder et al. (2023) Rahul Mazumder, Peter Radchenko, and Antoine Dedieu.  Subset selection with shrinkage: Sparse linear modeling when the snr is low.  _Operations Research_ , 71(1):129–147, 2023.
  * Miolane and Montanari (2021) Léo Miolane and Andrea Montanari.  The distribution of the Lasso: Uniform control over sparse balls and adaptive parameter tuning.  _The Annals of Statistics_ , 49(4):2313–2335, 2021.
  * Mousavi et al. (2018) Ali Mousavi, Arian Maleki, and Richard G. Baraniuk.  Consistent parameter estimation for LASSO and approximate message passing.  _The Annals of Statistics_ , 46(1):119 – 148, 2018.
  * Obuchi and Sakata (2019) Tomoyuki Obuchi and Ayaka Sakata.  Cross validation in sparse linear regression with piecewise continuous nonconvex penalties and its acceleration.  _Journal of Physics A: Mathematical and Theoretical_ , 52(41):414003, 2019.
  * Patil et al. (2021) Pratik Patil, Yuting Wei, Alessandro Rinaldo, and Ryan Tibshirani.  Uniform Consistency of Cross-Validation Estimators for High-Dimensional Ridge Regression.  In _Proceedings of The 24th International Conference on Artificial Intelligence and Statistics_ , volume 130 of _Proceedings of Machine Learning Research_ , pages 3178–3186. PMLR, 2021.
  * Patil et al. (2022) Pratik Patil, Alessandro Rinaldo, and Ryan Tibshirani.  Estimating Functionals of the Out-of-Sample Error Distribution in High-Dimensional Ridge Regression.  In _Proceedings of The 25th International Conference on Artificial Intelligence and Statistics_ , volume 151 of _Proceedings of Machine Learning Research_ , pages 6087–6120. PMLR, 2022.
  * Patil et al. (2023) Pratik Patil, Yuchen Wu, and Ryan Tibshirani.  Failures and successes of cross-validation for early-stopped gradient descent in high-dimensional least squares.  2023\.
  * Rahnama Rad and Maleki (2020) Kamiar Rahnama Rad and Arian Maleki.  A scalable estimate of the out-of-sample prediction error via approximate leave-one-out cross-validation.  _Journal of the Royal Statistical Society Series B: Statistical Methodology_ , 82(4):965–996, 2020.
  * Rahnama Rad et al. (2020) Kamiar Rahnama Rad, Wenda Zhou, and Arian Maleki.  Error bounds in estimating the out-of-sample prediction error using leave-one-out cross validation in high-dimensions.  In _International Conference on Artificial Intelligence and Statistics_ , pages 4067–4077. PMLR, 2020.
  * Rosenthal (1970) H.P. Rosenthal.  On the subspaces of $L_{p}(p>2)$ spanned by sequences of independent random variables.  _Israel Journal of Mathematics_ , 8:273–303, 1970.
  * Stephenson et al. (2021) Will Stephenson, Zachary Frangella, Madeleine Udell, and Tamara Broderick.  Can we globally optimize cross-validation loss? quasiconvexity in ridge regression.  _Advances in Neural Information Processing Systems_ , 34:24352–24364, 2021.
  * Stephenson and Broderick (2020) William Stephenson and Tamara Broderick.  Approximate cross-validation in high dimensions with guarantees.  In _International Conference on Artificial Intelligence and Statistics_ , pages 2424–2434. PMLR, 2020.
  * Vershynin (2018) Roman Vershynin.  _High-dimensional probability: An introduction with applications in data science_ , volume 47.  Cambridge university press, 2018.
  * Wang et al. (2020) Shuaiwen Wang, Haolei Weng, and Arian Maleki.  Which bridge estimator is the best for variable selection?  _The Annals of Statistics_ , 48(5):2791 – 2823, 2020.
  * Wang et al. (2022) Shuaiwen Wang, Haolei Weng, and Arian Maleki.  Does SLOPE outperform bridge regression?  _Information and Inference: A Journal of the IMA_ , 11(1):1–54, 2022.
  * Weng et al. (2018) Haolei Weng, Arian Maleki, and Le Zheng.  Overcoming the limitations of phase transition by higher order analysis of regularization techniques.  _The Annals of Statistics_ , 46(6A):3099 – 3129, 2018.
  * Xu et al. (2021) Ji Xu, Arian Maleki, Kamiar Rahnama Rad, and Daniel Hsu.  Consistent risk estimation in moderately high-dimensional linear regression.  _IEEE Transactions on Information Theory_ , 67(9):5997–6030, 2021.
  * Yuan and Lin (2005) Ming Yuan and Yi Lin.  Model Selection and Estimation in Regression with Grouped Variables.  _Journal of the Royal Statistical Society Series B: Statistical Methodology_ , 68(1):49–67, 12 2005.  ISSN 1369-7412.

##  Appendix A Technical Lemmas

To improve the readability of the rest of the manuscript, we include several
standard technical results used in our detailed proofs which are presented in
the rest of the Appendix.

######  Lemma 8.

Suppose Assumption A2 holds. Then for $p\geq 2$ we have

$\mathbb{E}\|\mathbf{x}_{i}\|^{8}\leq 24C_{X}$

###### Proof.

Let $\mathbf{z}=\bm{\Sigma}^{-\frac{1}{2}}\mathbf{x}_{i}$ then $\mathbf{z}\sim
N(0,\mathbf{I}_{p})$ and $\|\mathbf{z}\|^{2}\sim\chi^{2}(p)$. By standard
results on $\chi^{2}$ distribution we have

$\mathbb{E}\|\mathbf{z}\|^{8}=p(p+2)(p+4)(p+6)$

. Then we have for $p\geq 2$:

$\displaystyle\mathbb{E}\|\mathbf{x}_{i}\|^{8}$
$\displaystyle=\mathbb{E}(\mathbf{z}^{\top}\bm{\Sigma}\mathbf{z})^{4}$
$\displaystyle\leq\mathbb{E}\left(\frac{C_{X}}{p}\|\mathbf{z}\|^{2}\right)^{4}$
$\displaystyle\leq\frac{C_{X}^{4}}{p^{4}}\mathbb{E}\|\mathbf{z}\|^{8}$
$\displaystyle\leq
C_{X}^{4}\left(1+\frac{2}{p}\right)\left(1+\frac{4}{p}\right)\left(1+\frac{6}{p}\right)$
$\displaystyle\leq 24C_{X}^{4}.$

∎

######  Lemma 9 ((Rosenthal, 1970)).

Let $\\{X_{i}\\}_{i\in[n]}$ be a sequence of independent non-negative random
variables, and $t\geq 1$. Then we have

$\mathbb{E}\left(\sum_{i\in[n]}X_{i}\right)^{t}\leq
A(t)\max\left\\{\sum_{i\in[n]}\mathbb{E}X_{i}^{t},\left(\sum_{i\in[n]}\mathbb{E}X_{i}\right)^{t}\right\\}.$

###### Proof.

See Theorem 3 in (Rosenthal, 1970). For a discussion on sharp choice of
$A(t)$, the readers may refer to (Ibragimov and Sharakhmetov, 2001). ∎

##  Appendix B Bounded Signal-to-noise Ratio

First we explain what we mean by ’bounded SNR’ in Section 2.1, using the three
examples of linear, logistic and Poisson regression (with log exponential
link):

  * •

Linear: $y_{i}|\mathbf{x}_{i}\sim
N(\mathbf{x}_{i}^{\top}\bm{\beta}^{*},\sigma^{2})$

  * •

Logistic: $y_{i}|\mathbf{x}_{i}\sim{\rm
Binomial}((1+e^{-\mathbf{x}_{i}^{\top}\bm{\beta}^{*}})^{-1})$

  * •

Poisson: $y_{i}|\mathbf{x}_{i}\sim{\rm
Poisson}(\log(1+e^{\mathbf{x}_{i}^{\top}\bm{\beta}^{*}}))$

Define the signal-to-noise ratio as

${\rm
SNR}:=\frac{\operatorname{var}(\mathbf{x}_{i}^{\top}\bm{\beta}^{*})}{\operatorname{var}(y_{i}|\mathbf{x}_{i}^{\top}\bm{\beta}^{*})}.$

When $\|\bm{\beta}^{*}\|_{2}=O(\sqrt{p})$ or each elements of of
$\bm{\beta}^{*}$ is $O(1)$, by Assumption A2 we have

$\operatorname{var}(\mathbf{x}_{i}^{\top}\bm{\beta}^{*})=\bm{\beta}^{*\top}\bm{\Sigma}\bm{\beta}^{*}\leq\frac{C_{X}}{p}\|\bm{\beta}^{*}\|_{2}^{2}=O(1).$

On the other hand,

$\displaystyle[\operatorname{var}(y_{i}|\mathbf{x}_{i})]^{-1}=\begin{cases}\sigma^{-2},&\text{
Linear }\\\
(e^{-\frac{1}{2}\mathbf{x}_{i}^{\top}\bm{\beta}^{*}}+e^{\frac{1}{2}\mathbf{x}_{i}^{\top}\bm{\beta}^{*}})^{2},&\text{
Logistic}\\\ [\log(1+e^{\mathbf{x}_{i}^{\top}\bm{\beta}^{*}})]^{-1},&\text{
Poisson}\end{cases}$

They are all $O_{p}(1)$ when $n,p$ increase. To see this, notice that

$\mathbf{x}_{i}^{\top}\bm{\beta}^{*}\sim
N(0,\bm{\beta}^{*\top}\bm{\Sigma}\bm{\beta}^{*})$

and

$\displaystyle 4\leq(e^{-\frac{1}{2}z}+e^{\frac{1}{2}z})^{2}\leq
2(e^{|z|}+1),$ $\displaystyle(\log(2)+z_{+})^{-1}\leq[\log(1+e^{z})]^{-1}\leq
z_{+}^{-1}$

where $z_{+}=z$ when $z\geq 0$ and $0$ otherwise. Suppose $C_{1}\leq
p^{-1/2}\|\bm{\beta}^{*}\|\leq C_{2}$ for some constants $C_{1},C_{2}$, then
$\mathbf{x}_{i}^{\top}\bm{\beta}^{*}=\Theta_{p}(1)$ and so is the ratio
$\frac{\operatorname{var}(\mathbf{x}_{i}^{\top}\bm{\beta}^{*})}{\operatorname{var}(y_{i}|\mathbf{x}_{i}^{\top}\bm{\beta}^{*})}$.

##  Appendix C Discussion of the assumptions

###  C.1 On Assumption A4

In this subsection we present several commonly used regularizers in machine
learning, and show that they are all Lipshitz continuous.

######  Example C.1 (LASSO).

The classic LASSO penalty is $r_{0}(\bm{\beta})=\|\bm{\beta}\|_{1}$ and is
clearly non-negative, convex and Lipschitz continuous.

######  Example C.2 (Group LASSO).

The group LASSO was introduced in (Yuan and Lin, 2005) to achieve joint
variable selection among different data groups. Assume the features are
partitioned in $G$ groups $J_{1},J_{2},\ldots,J_{G}$, and the penalty takes
the form
$r_{0}(\bm{\beta})=\sum_{j=1}^{G}(\bm{\beta}_{J_{j}}^{\top}\mathbf{K}_{j}\bm{\beta}_{J_{j}})^{1/2}$
where $\bm{\beta}_{J_{j}}\in\mathbb{R}^{p_{j}}$ is the coefficient vector for
group $j$, $\mathbf{K}_{j}\in\mathbb{R}^{p_{j}\times p_{j}}$ is a positive
definite matrix,
$\bm{\beta}=(\bm{\beta}_{J_{1}}^{\top},\cdots,\bm{\beta}_{J_{G}}^{\top})^{\top}\in\mathbb{R}^{p}$
is the concatenated coefficient with $p=\sum_{j=1}^{G}p_{j}$.

Clearly $r_{0}$ is non-negative. Moreover it is also convex since it is a sum
of convex functions
$r_{0j}(\bm{\beta})=(\bm{\beta}_{J_{j}}^{\top}\mathbf{K}_{j}\bm{\beta}_{J_{j}})^{1/2}$.
Finally, $r_{0}$ is also $\sqrt{\sum_{k=1}^{J}\sigma_{\max}(K_{j})}$-Lipschitz
with respect to $\bm{\beta}$.

######  Example C.3 (Generalized LASSO).

The generalized LASSO penalty takes the form of
$r_{0}(\bm{\beta})=\|\mathbf{D}\bm{\beta}\|_{1}$ and encompasses many LASSO
type penalty such as LASSO ($\mathbf{D}=\mathbf{I}_{p}$) and fused LASSO
($\mathbf{D}=(d_{ij})_{(p-1)\times p}$ where $d_{ij}=1$ if $i=j$, $d_{ij}=-1$
if $j=i+1$ and $d_{ij}=0$ otherwise). The nonnegativity and convexity are
immediate since $r_{0}$ is the $\ell_{1}$ norm of $\mathbf{D}\bm{\beta}$.
Moreover, it follows that $\|\mathbf{D}\bm{\beta}\|_{1}$ is
$\sigma_{\max}(\mathbf{D})$-Lipschitz in $\bm{\beta}$.

######  Example C.4 (Nuclear norm and Schatten norms).

When the estimand is a matrix $\mathbf{B}$ with rank $d$, the nuclear norm is
a popular regularizer:

$r_{0}(\mathbf{B})=\sum_{i=1}^{d}\sigma_{i}(\mathbf{B})$

where $\sigma_{i}(\mathbf{B})$ is the $i$-th largest singular value of
$\mathbf{B}$. More generally, the Schatten norm of $\mathbf{B}$ is defined as

$r_{0}(\mathbf{B})=\left(\sum_{i=1}^{d}\sigma_{i}^{p}(\mathbf{B})\right)^{\frac{1}{p}}$

and takes the nuclear norm as a special case when $p=1$. Since
$r_{0}(\mathbf{B})$ is a norm on the singular values of $\mathbf{B}$, we
obtain the nonnegativity and convexity of $r_{0}$. To show the Lipschitz
continuity we argue as follows. Since $r_{0}(\mathbf{B})$ is the p-norm of the
vector $(\sigma_{1}(\mathbf{B}),\cdots,\sigma_{d}(\mathbf{B}))$ and using the
triangular inequality we have

$\displaystyle|r_{0}(\mathbf{x})-r_{0}(\mathbf{y})|\leq$
$\displaystyle~{}r_{0}(\mathbf{x}-\mathbf{y})$ $\displaystyle\leq$
$\displaystyle\begin{cases}K^{\frac{1}{p}-\frac{1}{2}}\left\lVert\mathbf{x}-\mathbf{y}\right\rVert_{2}\quad&\text{if
}1\leq p\leq 2\\\
\left\lVert\mathbf{x}-\mathbf{y}\right\rVert_{2}\quad&\text{if }p\geq
2\end{cases}$ $\displaystyle\leq$
$\displaystyle~{}\sqrt{K}\left\lVert\mathbf{x}-\mathbf{y}\right\rVert_{2},$

where $\left\lVert\mathbf{B}\right\rVert_{2}$ denotes the Frobenius norm of
$\mathbf{B}$. The second line uses the relationship between p-norms: for
$\mathbf{u}\in\mathbb{R}^{p}$,

$\displaystyle\|\mathbf{u}\|_{p}$
$\displaystyle=\left(\sum_{k=1}^{K}u_{k}^{p}\right)^{\frac{1}{p}}$
$\displaystyle\leq\begin{cases}K^{\frac{1}{p}-\frac{1}{2}}\left\lVert\mathbf{u}\right\rVert_{2}\quad&\text{if
}1\leq p\leq 2\\\ \left\lVert\mathbf{u}\right\rVert_{2}\quad&\text{if }p\geq
2.\end{cases}$

Then if we let
$\mathbf{u}=(\sigma_{1}(\mathbf{B}),\cdots,\sigma_{K}(\mathbf{B}))^{\top}$ we
then have $\|\mathbf{u}\|_{p}=r_{0}(\mathbf{B})$ and

$\|\mathbf{u}\|_{2}=\left(\sum_{k=1}^{K}\sigma_{k}^{p}(\mathbf{B})\right)^{\frac{1}{2}}=\sqrt{\operatorname{tr}(\mathbf{B}^{\top}\mathbf{B})}=\|\mathbf{B}\|_{2}.$

###  C.2 On Assumption A5

In this section, we show that the moment bound of $y_{i}$ and polynomial
growth of $\ell,\dot{\ell},\phi,\dot{\phi}$ in Assumption A5 are justified for
many popular data generating mechanisms. We show this for three examples:
linear, logistic and Poisson regression (with log exponential link). In this
subsection we assume Assumptions A2 and A3 hold, namely,
$n/p\equiv\gamma_{0}>0$ and $\mathbf{x}_{i}$ are i.i.d. $N(0,\bm{\Sigma})$
with $\sigma_{\max}(\bm{\Sigma})\leq C_{X}/p$. In addition we assume
$p^{-1/2}\|\bm{\beta}^{*}\|\leq\xi$ for some $\xi>0$. Finally, both $\ell$ and
$\phi$ are set to the negative log-likelihood.

######  Example C.5 (Linear).

Suppose $y_{i}|\mathbf{x}_{i}\sim
N(\mathbf{x}_{i}^{\top}\bm{\beta}^{*},\sigma^{2})$. Then $y_{i}\sim
N(0,\tilde{\sigma}^{2})$ where
$\tilde{\sigma}^{2}=\sigma^{2}+\bm{\beta}^{*\top}\bm{\Sigma}\bm{\beta}^{*}$.
Using standard results on Gaussian moments, we have

$\mathbb{E}|y|^{m}=\tilde{\sigma}^{m}\times\dfrac{2^{m/2}\Gamma\left(\frac{m+1}{2}\right)}{\sqrt{\pi}}\leq\left(\sigma^{2}+C_{X}\xi^{2}\right)^{m/2}\dfrac{2^{m/2}\Gamma\left(\frac{m+1}{2}\right)}{\sqrt{\pi}}\,\,\text{for
any }m\geq 0.$

For Gaussian linear model, the negative log-likelihood is known to be the
$\ell_{2}$ loss:

$\ell(y,z)=\frac{1}{2}(y-z)^{2}\leq y^{2}+z^{2},$

and $|\dot{\ell}(y,z)|=|z-y|\leq|z|+|y|$.

######  Example C.6 (Logistic).

Suppose $y_{i}|\mathbf{x}_{i}\sim{\rm Bernoulli}(p)$ where
$p=(1+e^{-\mathbf{x}_{i}^{\top}\bm{\beta}^{*}})^{-1}$. Then
$y_{i}\in\\{0,1\\}$ and obviously

$\mathbb{E}|y|^{m}\leq 1\,\,\text{for all }m\geq 0.$

The negative log-likelihood of this model is

$\ell(y,z)=y\log(1-e^{-z})+(1-y)\log(1+e^{z}),\quad y\in\\{0,1\\},$

and

$|\ell(y,z)|\leq 2\log(2)+2|z|.$

For its derivative,

$|\dot{\ell}(y,z)|=\left\lvert\frac{e^{z}}{1+e^{z}}-y\right\rvert\leq
1+|y|.\\\ $

######  Example C.7 (Poisson).

Suppose $y_{i}|\mathbf{x}_{i}\sim{\rm Poisson}(\mu)$ with
$\mu=\log(1+e^{\mathbf{x}_{i}^{\top}\bm{\beta}^{*}})$. Then $y_{i}$ are non-
negative. Using the equivalence between Poisson and exponential distributions,
it can be shown that $y\sim{\rm Poisson}(\mu)$ implies $y\sim{\rm Sub-
exp}(\mu)$. It then follows by results for sub-exponential random variables
(see, e.g., Proposition 2.7.1 of (Vershynin, 2018)) that

$\mathbb{E}\left(|y|^{m}|\mathbf{x}_{i}\right)\leq(C_{*}\mu)^{m}m^{m}$

whence taking expectation over $\mathbf{x}$ it follows that for any $m\geq 0$
we have

$\mathbb{E}y^{m}\leq\mathbb{E}(\log(1+e^{\mathbf{x}^{\top}\bm{\beta}^{*}}))^{m}\times(C_{*}m)^{m}\leq(C_{*}m)^{m}\mathbb{E}e^{m\mathbf{x}^{\top}\bm{\beta}^{*}}\leq(C_{*}m)^{m}e^{\bm{\beta}^{*\top}\bm{\Sigma}\bm{\beta}^{*}m^{2}/2}\leq(C_{*}m)^{m}e^{m^{2}C_{X}\xi^{2}/2}.$

for a numerical constant $C_{*}>0$. In the last series of inequalities we have
used first the fact that $\log(1+x)\leq x$ for $x>0$. Next we have used the
moment generating function of the normal distribution
$\mathbf{x}^{\top}\bm{\beta}^{*}\sim
N(0,\bm{\beta}^{*\top}\bm{\Sigma}\bm{\beta}^{*})$ and finally the inequality
$\bm{\beta}^{*\top}\bm{\Sigma}\bm{\beta}\leq C_{X}\xi^{2}$ in the last step.

The negative log-likelihood is

$\displaystyle\ell(y,z)|$
$\displaystyle=\log(y!)+\log(1+e^{z})-y\log\log(1+e^{z})$
$\displaystyle\leq|y\log(y)|+\log(2)+|z|+|y\log(\log(2)+|z|)|$
$\displaystyle\leq y^{2}+\log(2)+|z|+|y(\log\log(2)+\frac{z}{\log(2)})|$
$\displaystyle\leq
y^{2}+\log(2)+|z|+\log\log(2)|y|+\frac{1}{2\log(2)}(y^{2}+z^{2})$
$\displaystyle\leq C(y^{2}+z^{2}+1),$

and the derivative satisfies

$|\dot{\ell}(y,z)|=\left\lvert\frac{1}{1+e^{-z}}-\frac{ye^{z}}{(1+e^{z})\log(1+e^{z})}\right\rvert\leq
1+|y|.$

##  Appendix D Detailed Proofs

###  D.1 Proof of Lemma 1

We start with the proof of Part (a). First we extend $r_{0}$ to
$\mathbb{R}^{p}$ by simply letting $r_{0}(\bm{\beta})=0$ for
$\bm{\beta}\notin\bm{\Theta}$. Then we have

$\displaystyle r_{0}^{\alpha}(\bm{\beta})$
$\displaystyle=\int_{\mathbb{R}^{p}}r_{0}(\bm{\beta}-\mathbf{z})\alpha\phi(\alpha\mathbf{z})d\mathbf{z}$
$\displaystyle=\alpha\int_{\mathbb{R}^{p}}r_{0}(\mathbf{z})\phi(\alpha(\bm{\beta}-\mathbf{z}))d\mathbf{z}.$

For a point $\bm{\beta}\in\bm{\Theta}_{0}$, consider its directional
derivative over a direction $\mathbf{v}\in\mathbb{R}^{p}$ with
$\left\lVert\mathbf{v}\right\rVert_{2}=1$:

$\displaystyle~{}\nabla_{\mathbf{v}}r_{0}^{\alpha}(\bm{\beta})$
$\displaystyle:=\lim_{h\to
0}\frac{1}{h}[r_{0}^{\alpha}(\bm{\beta}+h\mathbf{v})-r_{0}^{\alpha}(\bm{\beta})]$
$\displaystyle\leq
2\alpha\nabla_{\mathbf{v}}\phi(\alpha(\bm{\beta}-\mathbf{z}))$
$\displaystyle=\lim_{h\to
0}\alpha\int_{\mathbb{R}^{p}}r_{0}(\mathbf{z})\frac{1}{h}[\phi(\alpha(\bm{\beta}-\mathbf{z}+h\mathbf{v}))-\phi(\alpha(\bm{\beta}-\mathbf{z}))]d\mathbf{z}$

Since $\phi\in{\cal C}^{\infty}(\mathbb{R}^{p})$, we have that for small
enough $h$:

$\displaystyle~{}\frac{1}{h}[\phi(\alpha(\bm{\beta}-\mathbf{z}+h\mathbf{v}))-\phi(\alpha(\bm{\beta}-\mathbf{z}))]$
$\displaystyle\leq
2\alpha\mathbf{v}^{\top}\nabla\phi(\alpha(\bm{\beta}-\mathbf{z}))$
$\displaystyle\leq
2\alpha\left\lVert\nabla\phi(\alpha(\bm{\beta}-\mathbf{z}))\right\rVert$
$\displaystyle\leq
2\alpha(2\pi)^{-p/2}e^{-\frac{1}{2}\alpha^{2}\left\lVert\bm{\beta}-\mathbf{z}\right\rVert_{2}^{2}}\left\lVert\bm{\beta}-\mathbf{z}\right\rVert_{2}.$

By assumption
$r_{0}(\mathbf{z})e^{-\frac{1}{2}\alpha^{2}\left\lVert\bm{\beta}-\mathbf{z}\right\rVert_{2}^{2}}\left\lVert\bm{\beta}-\mathbf{z}\right\rVert_{2}$
is integrable, then using Dominated Convergence, the limit can be taken within
the integral, so that $\nabla_{\mathbf{v}}r_{0}^{\alpha}(\bm{\beta})$ exists.
Using similar arguments, in order that
$\nabla_{\mathbf{v}}^{k}r_{0}^{\alpha}(\bm{\beta})$ exists, we only need
$r_{0}(\mathbf{z})\nabla_{\mathbf{v}}^{k}\phi(\alpha(\bm{\beta}-\mathbf{z}))$
to be integrable. To see this, notice that

$\frac{\partial^{k}}{\partial u_{1}^{k_{1}}\cdots\partial
u_{p}^{k_{p}}}\phi(\mathbf{u})=e^{-\frac{1}{2}\left\lVert\mathbf{u}\right\rVert^{2}}P_{k_{1}\cdots
k_{p}}(\mathbf{u})$

where $P_{k_{1}\cdots k_{p}}(\mathbf{u})=u_{1}^{k_{1}}u_{2}^{k_{2}}\cdots
u_{p}^{k_{p}}+o(u_{1}^{k_{1}}u_{2}^{k_{2}}\cdots u_{p}^{k_{p}})$ is a
polynomial with its dominating term being $u_{1}^{k_{1}}u_{2}^{k_{2}}\cdots
u_{p}^{k_{p}}$ with order $K$. Then we have

$\displaystyle~{}\left\lvert\nabla_{\mathbf{v}}^{k}\phi(\mathbf{u})\right\rvert$
$\displaystyle=\left\lvert\sum_{k_{1}+\cdots+k_{p}=k}\frac{\partial^{k}}{\partial
u_{1}^{k_{1}}\cdots\partial u_{p}^{k_{p}}}\phi(\mathbf{u})v_{1}^{k_{1}}\cdots
v_{p}^{k_{p}}\right\rvert$
$\displaystyle\leq\sum_{k_{1}+\cdots+k_{p}=k}\left\lvert v_{1}^{k_{1}}\cdots
v_{p}^{k_{p}}\right\rvert
e^{-\frac{1}{2}\left\lVert\mathbf{u}\right\rVert^{2}}P_{k_{1}\cdots
k_{p}}(\mathbf{u})$
$\displaystyle\leq\left(\sum_{k_{1}+\cdots+k_{p}=k}\left\lvert P_{k_{1}\cdots
k_{p}}(\mathbf{u})\right\rvert\right)e^{-\frac{1}{2}\left\lVert\mathbf{u}\right\rVert^{2}}\left(\sum|v_{i}|\right)^{k}$
$\displaystyle=O(\left\lVert\mathbf{u}\right\rVert^{k}e^{-\frac{1}{2}\left\lVert\mathbf{u}\right\rVert^{2}}p^{k/2}\left\lVert\mathbf{v}\right\rVert_{2}^{k})$
$\displaystyle=O(\left\lVert\mathbf{u}\right\rVert^{k}e^{-\frac{1}{2}\left\lVert\mathbf{u}\right\rVert^{2}})$

Inserting $\mathbf{u}=\alpha(\bm{\beta}-\mathbf{z})$ we have

$\displaystyle\left\lvert\nabla_{\mathbf{v}}^{k}\phi(\alpha(\bm{\beta}-\mathbf{z}))\right\rvert$
$\displaystyle=O(\alpha^{k}\left\lVert\bm{\beta}-\mathbf{z}\right\rVert_{2}^{k}e^{-\frac{1}{2}\alpha^{2}\left\lVert\bm{\beta}-\mathbf{z}\right\rVert_{2}^{2}})$
$\displaystyle=O(\left\lVert\mathbf{z}\right\rVert_{2}^{k}e^{-\frac{1}{2}\alpha^{2}\left\lVert\bm{\beta}-\mathbf{z}\right\rVert_{2}^{2}})$

So
$r_{0}(\mathbf{z})\nabla_{\mathbf{v}}^{k}\phi(\alpha(\bm{\beta}-\mathbf{z}))$
is integrable if
$r_{0}(\mathbf{z})\left\lVert\mathbf{z}\right\rVert_{2}^{k}e^{-\frac{1}{2}\left\lVert\bm{\beta}-\mathbf{z}\right\rVert_{2}^{2}}$
is integrable. The continuity of the derivatives follows then from exchanging
the integration and differentiation.

We now turn tho the proof of Part (b) of the paper. For all
$\bm{\beta}\in\bm{\Theta}_{0}$,

$\displaystyle|r_{0}^{\alpha}(\bm{\beta})-r_{0}(\bm{\beta})|$
$\displaystyle\leq\int_{\mathbb{R}^{p}}|r_{0}(\bm{\beta}-\mathbf{z})-r_{0}(\bm{\beta})|\alpha\phi(\alpha\mathbf{z})d\mathbf{z}$
$\displaystyle=\int_{\mathbb{R}^{p}}|r_{0}(\bm{\beta}-\alpha^{-1}\mathbf{u})-r_{0}(\bm{\beta})|d\Phi(\mathbf{u})$
$\displaystyle\leq\frac{L}{\alpha^{k}}\int_{\mathbb{R}^{p}}\left\lVert\mathbf{u}\right\rVert_{2}^{k}d\Phi(\mathbf{u})$
$\displaystyle\to 0\quad(\alpha\to\infty)$

The second line uses change of variable $\mathbf{u}=\alpha\mathbf{z}$ and the
third line uses our assumption on $r_{0}$. The last line is because the
integral is finite. ∎

######  Remark D.1.

Although Lemma 1 adopts a weaker assumption than Lipschitz continuity, it can
be shown that $k=1$ is the only value that allows $r_{0}$ to be convex. In
fact, for $k<1$ we have

$r_{0}(\mathbf{x})\leq L\|\mathbf{x}\|^{k}.$

It is obvious that unless $r_{0}$ is constant, it would eventually increase at
least linearly thus cannot be bounded by $L\|\mathbf{x}\|^{k}$ for some $k<1$.

######  Example D.1.

Generalized LASSO:
$r_{0}(\bm{\beta})=\left\lVert\mathbf{D}\bm{\beta}\right\rVert_{1}$ for a
fixed $\mathbf{D}\in\mathbb{R}^{m\times p}$. It is continuous, and
$|r_{0}(\mathbf{x})-r_{0}(\mathbf{y})|=|\left\lVert\mathbf{D}\mathbf{x}\right\rVert_{1}-\left\lVert\mathbf{D}\mathbf{y}\right\rVert_{1}|\leq\left\lVert\mathbf{D}\mathbf{x}-\mathbf{D}\mathbf{y}\right\rVert_{1}\leq\sqrt{m}\left\lVert\mathbf{x}-\mathbf{y}\right\rVert_{2}$.
Note that the classical LASSO is a special case with
$\mathbf{D}=\mathbf{I}_{p}$.

######  Remark D.2.

In fact if $r_{0}$ is a norm such that $\mathbb{E}r_{0}(\bm{\beta})<\infty$
where $\bm{\beta}$ has i.i.d. $N(0,1)$ entries, then the results of the above
two lemmas hold.

###  D.2 Proof of Lemma 3

Fix $\mathbf{x},\mathbf{y}$ and consider
$f(t):=\bm{\Pi}_{\bm{\Theta}}((1-t)\mathbf{x}+t\mathbf{y})$. By the firm non-
expansiveness of projection operators, we have $\forall t_{1},t_{2}\in[0,1]$,

$\displaystyle 0$ $\displaystyle\leq(f(t_{1})-f(t_{2}))^{2}$ $\displaystyle=$
$\displaystyle\|\bm{\Pi}_{\bm{\Theta}}((1-t_{1})\mathbf{x}+t_{1}\mathbf{y})-\bm{\Pi}_{\bm{\Theta}}((1-t_{2})\mathbf{x}+t_{2}\mathbf{y})\|^{2}$
$\displaystyle\leq$
$\displaystyle~{}\langle\bm{\Pi}_{\bm{\Theta}}((1-t_{1})\mathbf{x}+t_{1}\mathbf{y})-\bm{\Pi}_{\bm{\Theta}}((1-t_{2})\mathbf{x}+t_{2}\mathbf{y}),(t_{1}-t_{2})(\mathbf{y}-\mathbf{x})\rangle$
$\displaystyle=$ $\displaystyle\langle
f(t_{1})-f(t_{2}),(t_{1}-t_{2})(\mathbf{y}-\mathbf{x})\rangle$
$\displaystyle\leq$
$\displaystyle(t_{1}-t_{2})^{2}\|\mathbf{y}-\mathbf{x}\|^{2}.$ (12)

By taking a square root, we thus have $f(t)$ is $\|\mathbf{x}-\mathbf{y}\|$
Lipschitz on $[0,1]$. Therefore it is absolutely continuous and differentiable
almost everywhere. Let $t_{1}=t+\epsilon$ and $t_{2}=t$, and then divide (12)
by $\epsilon^{2}$, then if $f^{\prime}(t)$ exists we have:

$\displaystyle 0\leq\|f^{\prime}(t)\|^{2}\leq\langle
f^{\prime}(t),\mathbf{y}-\mathbf{x}\rangle\leq\|\mathbf{y}-\mathbf{x}\|^{2}$

For each $t$, consider solving the following equation for $\mathbf{J}(t)$:

$f^{\prime}(t)=\mathbf{J}(t)(\mathbf{y}-\mathbf{x}).$

The claim is that we can find $\mathbf{J}(t)$ with its eigenvalues between
$[0,1]$ such that (D.2) holds. In fact, since the rotation in $\mathbb{R}^{p}$
is a unitary matrix with all eigenvalues being $1$, we can choose
$\mathbf{J}(t)=\frac{\|f^{\prime}(t)\|}{\|\mathbf{y}-\mathbf{x}\|}\mathbf{R}$
where $\mathbf{R}$ is a rotation that rotates $\mathbf{y}-\mathbf{x}$ to the
direction of $f^{\prime}(t)$, and this choice of $\mathbf{J}(t)$ has its all
eigenvalues being
$\frac{\|f^{\prime}(t)\|}{\|\mathbf{y}-\mathbf{x}\|}\in[0,1]$.

With a slight abuse of notation we assume $f^{\prime}(t)=\mathbf{0}$ wherever
the derivative does not exist. Then by the Newton-Leibniz formula (for
Lebesgue integral and absolute continuous functions):

$\displaystyle\bm{\Pi}_{\bm{\Theta}}(\mathbf{y})-\bm{\Pi}_{\bm{\Theta}}(\mathbf{x})$
$\displaystyle=f(1)-f(0)$ $\displaystyle=\int_{0}^{1}f^{\prime}(t)dt$
$\displaystyle=\int_{0}^{1}\mathbf{J}(t)(\mathbf{y}-\mathbf{x})dt$

where the last line uses (D.2).∎

######  Remark D.3.

In the proof of Lemma 3, the matrix $\mathbf{J}(t)$ is not explicitly derived.
However by equation (D.2) one can easily see that, when
$\bm{\Pi}_{\bm{\Theta}}((1-t)\mathbf{x}+t\mathbf{y})$ is smooth at $t=t_{0}$,
we can use its Jacobian as $\mathbf{J}(t)$, i.e.

$\mathbf{J}(t_{0})=\left.\frac{\partial}{\partial\mathbf{z}}\bm{\Pi}_{\bm{\Theta}}(\mathbf{z})\right|_{\mathbf{z}=(1-t_{0})\mathbf{x}+t_{0}\mathbf{y}}.$

###  D.3 Proof of Lemma 4

###### Proof.

Begin we start the proof, let us introduce the following notations:

$\displaystyle h(\bm{\beta})$
$\displaystyle:=\sum_{j=1}^{n}\ell_{j}(\bm{\beta})+\lambda(1-\eta)r_{0}(\bm{\beta})+\lambda\eta\bm{\beta}^{\top}\bm{\beta},$
$\displaystyle h^{\alpha}(\bm{\beta})$
$\displaystyle:=\sum_{j=1}^{n}\ell_{j}(\bm{\beta})+\lambda(1-\eta)r_{0}^{\alpha}(\bm{\beta})+\lambda\eta\bm{\beta}^{\top}\bm{\beta},$
$\displaystyle h_{/i}(\bm{\beta})$ $\displaystyle:=\sum_{j\neq
i}^{n}\ell_{j}(\bm{\beta})+\lambda(1-\eta)r_{0}(\bm{\beta})+\lambda\eta\bm{\beta}^{\top}\bm{\beta},$
$\displaystyle h_{/i}^{\alpha}(\bm{\beta})$ $\displaystyle:=\sum_{j\neq
i}^{n}\ell_{j}(\bm{\beta})+\lambda(1-\eta)r_{0}^{\alpha}(\bm{\beta})+\lambda\eta\bm{\beta}^{\top}\bm{\beta}.$

As mentioned before, in order to obtain a bound on
$\|\widehat{\bm{\beta}}-\widehat{\bm{\beta}}_{/i}\|_{2}$ we use the smoothing
trick. Hence, we first obtain an upper bound for
$\|\widehat{\bm{\beta}}^{\alpha}-\widehat{\bm{\beta}}_{/i}^{\alpha}\|$.

Similar to $h$ and $h^{\alpha}$, let $h_{/i}$ and $h_{/i}^{\alpha}$ denote the
loss functions for $\widehat{\bm{\beta}}_{/i}$ and
$\widehat{\bm{\beta}}_{/i}^{\alpha}$ respectively. By Lemma 2,
$\widehat{\bm{\beta}}^{\alpha}$ and $\widehat{\bm{\beta}}_{/i}^{\alpha}$
satisfy

$\displaystyle\widehat{\bm{\beta}}^{\alpha}=\bm{\Pi}_{\bm{\Theta}}(\widehat{\bm{\beta}}^{\alpha}-\nabla
h^{\alpha}(\widehat{\bm{\beta}}^{\alpha}))$
$\displaystyle\widehat{\bm{\beta}}_{/i}^{\alpha}=\bm{\Pi}_{\bm{\Theta}}(\widehat{\bm{\beta}}_{/i}^{\alpha}-\nabla
h_{/i}^{\alpha}(\widehat{\bm{\beta}}_{/i}^{\alpha})).$

By subtracting one from the other we have

$\displaystyle\widehat{\bm{\beta}}^{\alpha}-\widehat{\bm{\beta}}_{/i}^{\alpha}=$
$\displaystyle\bm{\Pi}_{\bm{\Theta}}(\widehat{\bm{\beta}}^{\alpha}-\nabla
h^{\alpha}(\widehat{\bm{\beta}}^{\alpha}))-\bm{\Pi}_{\bm{\Theta}}(\widehat{\bm{\beta}}_{/i}^{\alpha}-\nabla
h_{/i}^{\alpha}(\widehat{\bm{\beta}}_{/i}^{\alpha}))$ $\displaystyle=$
$\displaystyle\bar{\mathbf{J}}\times\left(\widehat{\bm{\beta}}^{\alpha}-\nabla
h^{\alpha}(\widehat{\bm{\beta}}^{\alpha})-\widehat{\bm{\beta}}_{/i}^{\alpha}+\nabla
h_{/i}^{\alpha}(\widehat{\bm{\beta}}_{/i}^{\alpha})\right)$ (14)

where the second line comes from Lemma 3 and

$\bar{\mathbf{J}}:=\int_{0}^{1}\mathbf{J}(t)dt.$

It is straightforward to use Lemma 3 to show that

$0\leq\lambda_{\min}(\bar{\mathbf{J}})\leq\lambda_{\max}(\bar{\mathbf{J}})\leq
1.$

On the other hand,

$\displaystyle\widehat{\bm{\beta}}^{\alpha}-\nabla
h^{\alpha}(\widehat{\bm{\beta}}^{\alpha})-\widehat{\bm{\beta}}_{/i}^{\alpha}+\nabla
h_{/i}^{\alpha}(\widehat{\bm{\beta}}_{/i}^{\alpha})$ $\displaystyle=$
$\displaystyle\widehat{\bm{\beta}}^{\alpha}-\widehat{\bm{\beta}}_{/i}^{\alpha}-\sum_{j\in[n]}\left[\dot{\ell}_{j}(\widehat{\bm{\beta}}^{\alpha})-\dot{\ell}_{j}(\widehat{\bm{\beta}}_{/i}^{\alpha})\right]\mathbf{x}_{j}-\lambda\left[\nabla
r^{\alpha}(\widehat{\bm{\beta}}^{\alpha})-\nabla
r^{\alpha}(\widehat{\bm{\beta}}_{/i}^{\alpha})\right]-\dot{\ell}_{i}(\widehat{\bm{\beta}}_{/i}^{\alpha})\mathbf{x}_{i}$
$\displaystyle=$
$\displaystyle\left(\mathbf{I}-\mathbf{X}^{\top}\operatorname{diag}[\ddot{\ell}_{j}(\bm{\xi}_{j})]_{j\in[n]}\mathbf{X}-\lambda\nabla^{2}r^{\alpha}(\bm{\Xi})\right)(\widehat{\bm{\beta}}^{\alpha}-\widehat{\bm{\beta}}_{/i}^{\alpha})-\dot{\ell}_{i}(\widehat{\bm{\beta}}_{/i}^{\alpha})\mathbf{x}_{i}$
(15)

where the second line uses the definition of $h^{\alpha}$ and the third line
uses mean-value-theorem on $\dot{\ell}_{j}$ and $\nabla r^{\alpha}$:

$\ddot{\ell}_{j}(\bm{\xi}_{j}):=\int_{0}^{1}\ddot{\ell}_{j}(t\widehat{\bm{\beta}}^{\alpha}+(1-t)\widehat{\bm{\beta}}_{/i}^{\alpha})dt$

with

$\dot{\ell}_{j}(\widehat{\bm{\beta}}^{\alpha})-\dot{\ell}_{j}(\widehat{\bm{\beta}}_{/i}^{\alpha})=\ddot{\ell}_{j}(\bm{\xi}_{j})\mathbf{x}_{j}^{\top}(\widehat{\bm{\beta}}^{\alpha}-\widehat{\bm{\beta}}_{/i}^{\alpha})$

and likewise

$\nabla^{2}r^{\alpha}(\bm{\Xi}):=\int_{0}^{1}\nabla^{2}r^{\alpha}(t\widehat{\bm{\beta}}^{\alpha}+(1-t)\widehat{\bm{\beta}}_{/i}^{\alpha})dt$

with

$\nabla r^{\alpha}(\widehat{\bm{\beta}}^{\alpha})-\nabla
r^{\alpha}(\widehat{\bm{\beta}}_{/i}^{\alpha})=\nabla^{2}r^{\alpha}(\bm{\Xi})(\widehat{\bm{\beta}}^{\alpha}-\widehat{\bm{\beta}}_{/i}^{\alpha}).$

Inserting this back to (14) we have

$\widehat{\bm{\beta}}^{\alpha}-\widehat{\bm{\beta}}_{/i}^{\alpha}=-\mathbf{G}^{-1}\bar{\mathbf{J}}\left(\dot{\ell}_{i}(\widehat{\bm{\beta}}_{/i}^{\alpha})\mathbf{x}_{i}\right)$

where

$\displaystyle\mathbf{G}$
$\displaystyle:=\mathbf{I}+\bar{\mathbf{J}}\left(\mathbf{X}^{\top}\operatorname{diag}[\ddot{\ell}_{j}(\bm{\xi}_{j})]_{j\in[n]}\mathbf{X}+\lambda\nabla^{2}r^{\alpha}(\bm{\Xi})-\mathbf{I}\right)$
$\displaystyle=\mathbf{I}-\bar{\mathbf{J}}+\bar{\mathbf{J}}\left(\mathbf{X}_{/i}^{\top}\operatorname{diag}[\ddot{\ell}_{j}(\bm{\xi}_{j})]_{j\neq
i}\mathbf{X}_{/i}+\lambda\nabla^{2}r^{\alpha}(\bm{\Xi})\right).$

Since $\mathbf{I}-\bar{\mathbf{J}}$ is positive semidefinite (note that all
the eigenvalues of $\bar{\mathbf{J}}$ are in $[0,1]$ ) and
$\mathbf{X}^{\top}\operatorname{diag}[\ddot{\ell}_{j}(\bm{\xi}_{j})]_{j\in[n]}\mathbf{X}+\lambda\nabla^{2}r^{\alpha}(\bm{\Xi})$
is positive definite (due to the ridge component), $\mathbf{G}$ is also
positive definite. Hence, we have

$\left\lVert\widehat{\bm{\beta}}^{\alpha}-\widehat{\bm{\beta}}_{/i}^{\alpha}\right\rVert_{2}\leq\left[\sigma_{\min}(\mathbf{G})\right]^{-1}\sigma_{\max}(\bar{\mathbf{J}})\left\|\dot{\ell}_{i}(\widehat{\bm{\beta}}_{/i}^{\alpha})\mathbf{x}_{i}\right\|_{2}.$

We have already established $\sigma_{\max}(\bar{\mathbf{J}})\leq 1$. Now we
bound $\sigma_{\min}(\mathbf{G})$:

$\displaystyle\sigma_{\min}(\mathbf{G})$
$\displaystyle=\lambda_{\min}(\mathbf{G})$
$\displaystyle=1+\lambda_{\min}\left(\bar{\mathbf{J}}\left(\mathbf{X}_{/i}^{\top}\operatorname{diag}[\ddot{\ell}_{j}(\bm{\xi}_{j})]_{j\notin
I_{i}}\mathbf{X}_{/i}+\lambda\nabla^{2}r^{\alpha}(\bm{\Xi})-\mathbf{I}\right)\right)$
$\displaystyle:=1+\lambda_{\min}(\bar{\mathbf{J}}\mathbf{M})$

where
$\mathbf{M}:=\mathbf{X}_{/i}^{\top}\operatorname{diag}[\ddot{\ell}_{j}(\bm{\xi}_{j})]_{j\notin
I_{i}}\mathbf{X}_{/i}+\lambda\nabla^{2}r^{\alpha}(\bm{\Xi})-\mathbf{I}$.
Observe that due to the existence of the ridge component in $r$, we have

$\lambda_{\min}(\mathbf{M})\geq 2\lambda\eta-1.$

  * •

If $\lambda_{\min}(\mathbf{M})\geq 0$, then we have

$\lambda_{\min}\left(\bar{\mathbf{J}}\mathbf{M}\right)\geq\lambda_{\min}(\bar{\mathbf{J}})\lambda_{\min}(\mathbf{M})\geq
0.$

  * •

If $2\lambda\eta-1\leq\lambda_{\min}(\mathbf{M})<0$, then we have

$\lambda_{\min}\left(\bar{\mathbf{J}}\mathbf{M}\right)\geq\lambda_{\max}(\bar{\mathbf{J}})\lambda_{\min}(\mathbf{M})\geq
2\lambda\eta-1.$

Therefore we have

$\sigma_{\min}(\mathbf{G})\geq 1+(2\lambda\eta-1)\wedge 0=2\lambda\eta\wedge
1.$

inserting this back to (D.3) we have

$\left\lVert\widehat{\bm{\beta}}^{\alpha}-\widehat{\bm{\beta}}_{/i}^{\alpha}\right\rVert\leq\frac{\left\lVert\dot{\ell}_{i}(\widehat{\bm{\beta}}_{/i}^{\alpha})\mathbf{x}_{i}\right\rVert}{2\lambda\eta\wedge
1}.$

The next step of the proof is to use this upper bound on the smoothed
estimates and obtain an upper bound for
$\left\lVert\widehat{\bm{\beta}}-\widehat{\bm{\beta}}_{/i}\right\rVert$.
Towards this goal, we first prove the following lemma:

######  Lemma 10.

Under assumptions A1-A4, we have that

$\left\lVert\widehat{\bm{\beta}}^{\alpha}-\widehat{\bm{\beta}}\right\rVert\leq\sqrt{\frac{2(1-\eta)}{\eta}\left\lVert
r_{0}^{\alpha}-r_{0}\right\rVert_{\infty}},$

and similarly

$\left\lVert\widehat{\bm{\beta}}^{\alpha}_{/i}-\widehat{\bm{\beta}}_{/i}\right\rVert\leq\sqrt{\frac{2(1-\eta)}{\eta}\left\lVert
r_{0}^{\alpha}-r_{0}\right\rVert_{\infty}}.$

###### Proof.

We have

$\displaystyle
h^{\alpha}(\widehat{\bm{\beta}})-h^{\alpha}(\widehat{\bm{\beta}}^{\alpha})=h^{\alpha}(\widehat{\bm{\beta}})-h(\widehat{\bm{\beta}}^{\alpha})+h(\widehat{\bm{\beta}}^{\alpha})-h^{\alpha}(\widehat{\bm{\beta}}^{\alpha})$
$\displaystyle\leq
h^{\alpha}(\widehat{\bm{\beta}})-h(\widehat{\bm{\beta}})+h(\widehat{\bm{\beta}}^{\alpha})-h^{\alpha}(\widehat{\bm{\beta}}^{\alpha})\leq
2\lambda(1-\eta)\left\lVert r_{0}^{\alpha}-r_{0}\right\rVert_{\infty}$ (17)

where the first inequality uses the fact that
$\widehat{\bm{\beta}},\widehat{\bm{\beta}}^{\alpha}$ are the minimizers of
$h(\bm{\beta})$ and $h^{\alpha}(\bm{\beta})$ respectively, and the last
inequality uses the definition of $h,h^{\alpha}$. On the other hand we also
have from the second order mean value theorem (or Taylor expansion) that

$\displaystyle
h^{\alpha}(\widehat{\bm{\beta}})-h^{\alpha}(\widehat{\bm{\beta}}^{\alpha})$
$\displaystyle=$ $\displaystyle\nabla
h^{\alpha}(\widehat{\bm{\beta}}^{\alpha})^{\top}(\widehat{\bm{\beta}}-\widehat{\bm{\beta}}^{\alpha})+\frac{1}{2}(\widehat{\bm{\beta}}-\widehat{\bm{\beta}}^{\alpha})^{\top}\nabla^{2}h^{\alpha}(\bm{\Xi})(\widehat{\bm{\beta}}-\widehat{\bm{\beta}}^{\alpha})$
$\displaystyle\geq$
$\displaystyle\frac{1}{2}(\widehat{\bm{\beta}}-\widehat{\bm{\beta}}^{\alpha})^{\top}\nabla^{2}h^{\alpha}(\bm{\Xi})(\widehat{\bm{\beta}}-\widehat{\bm{\beta}}^{\alpha})$
$\displaystyle\geq$
$\displaystyle~{}\lambda\eta\|\widehat{\bm{\beta}}-\widehat{\bm{\beta}}^{\alpha}\|^{2}.$
(18)

In the first equality, by a slight abuse of the notation, we have written
$\nabla^{2}h^{\alpha}(\bm{\Xi})$ as the Hessian in the second order Taylor
expansion.‡‡‡Since the mean-value theorem doesn’t exist for vector-valued
functions, the matrix $\nabla^{2}h^{\alpha}(\bm{\Xi})$ is actually the Hessian
of $h^{\alpha}$, with each row evaluated at a different convex combination of
$\widehat{\bm{\beta}}$ and $\widehat{\bm{\beta}}^{\alpha}$, as the matrix
$\bm{\Xi}$ indicates. To obtain the second line, observe that

$\nabla
h_{\alpha}(\widehat{\bm{\beta}}^{\alpha})^{\top}(\widehat{\bm{\beta}}-\widehat{\bm{\beta}}^{\alpha})=\left.\frac{\partial}{\partial
t}h^{\alpha}((1-t)\widehat{\bm{\beta}}^{\alpha}+t\widehat{\bm{\beta}})\right|_{t=0}.$

Since $\widehat{\bm{\beta}}^{\alpha}$ is the minimizer of $h^{\alpha}$, $t=0$
is the minimizer of
$h^{\alpha}((1-t)\widehat{\bm{\beta}}^{\alpha}+t\widehat{\bm{\beta}})$ for
$t\in[0,1]$. And since $h^{\alpha}$ is smooth on $(0,1)$ we must have $\nabla
h_{\alpha}(\widehat{\bm{\beta}}^{\alpha})^{\top}(\widehat{\bm{\beta}}-\widehat{\bm{\beta}}^{\alpha})=\left.\frac{\partial}{\partial
t}h^{\alpha}((1-t)\widehat{\bm{\beta}}^{\alpha}+t\widehat{\bm{\beta}})\right|_{t=0}\geq
0$. The last line of (D.3) is because $\nabla^{2}h^{\alpha}(\bm{\Xi})$ is
positive-definite and $\sigma_{\min}(\nabla^{2}h^{\alpha}(\bm{\Xi}))\geq
2\lambda\eta$ due to the existence of the ridge component.

Combining (D.3) and (D.3) we have

$\displaystyle\left\lVert\widehat{\bm{\beta}}-\widehat{\bm{\beta}}^{\alpha}\right\rVert^{2}\leq\frac{2(1-\eta)}{\eta}\left\lVert
r_{0}^{\alpha}-r_{0}\right\rVert_{\infty}.$

Using a similar argument we can also prove that

$\left\lVert\widehat{\bm{\beta}}_{/i}-\widehat{\bm{\beta}}_{/i}^{\alpha}\right\rVert^{2}\leq\frac{2(1-\eta)}{\eta}\left\lVert
r_{0}^{\alpha}-r_{0}\right\rVert_{\infty}.$

∎

From lemma 1 we can see that $\left\lVert
r_{0}^{\alpha}-r_{0}\right\rVert_{\infty}\rightarrow 0$ as
$\alpha\rightarrow\infty$.

Continuing with the proof of Lemma 4, by Lemma 10,
$\widehat{\bm{\beta}}^{\alpha}\to\widehat{\bm{\beta}}$ and
$\widehat{\bm{\beta}}_{/i}^{\alpha}\to\widehat{\bm{\beta}}_{/i}$ when
$\alpha\to\infty$. Hence, we can let $\alpha\to\infty$ and have

$\left\lVert\widehat{\bm{\beta}}-\widehat{\bm{\beta}}_{/i}\right\rVert\leq\frac{\left\lVert\dot{\ell}_{i}(\widehat{\bm{\beta}}_{/i})\mathbf{x}_{i}\right\rVert}{2\lambda\eta\wedge
1}.$

∎

###  D.4 Proof of Lemma 5

We first obtain an upper bound for the $4^{\rm th}$ moment. Using Assumption
A5, we have

$\displaystyle\sqrt{\mathbb{E}\dot{\phi}_{0}^{4}(\bm{\beta})}$
$\displaystyle\leq\sqrt{\mathbb{E}\left(1+|y_{0}|^{s}+|\mathbf{x}_{0}^{\top}\bm{\beta}|^{s}\right)^{4}}$
$\displaystyle\leq\sqrt{27(1+\mathbb{E}|y_{0}|^{4s}+\mathbb{E}|\mathbf{x}_{0}^{\top}\bm{\beta}|^{4s})}$
$\displaystyle\leq\sqrt{27\left(1+C_{Y}(4s)+(4s-1)!!\left(\frac{C_{X}}{p}\|\bm{\beta}\|^{2}\right)^{2s}\right)}$
$\displaystyle\leq\sqrt{27(1+C_{Y}(4s))}+\sqrt{27(4s-1)!!}C_{X}^{s}\left(\frac{C_{X}}{p}\|\bm{\beta}\|^{2}\right)^{s}.$

where the second line uses the simple equation $(a+b+c)^{4}\leq
27a^{4}+27b^{4}+27c^{4}$, the third line uses
$\mathbf{x}_{0}^{\top}\bm{\beta}\sim
N(0,\bm{\beta}^{\top}\bm{\Sigma}\bm{\beta})$ with
$\bm{\beta}^{\top}\bm{\Sigma}\bm{\beta}\leq\frac{C_{X}}{p}\|\bm{\beta}\|^{2}$.
It also uses the moment formula for standard Gaussian variable. The last line
uses the equation $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ for $a,b\geq 0$. Define
$C_{\phi}^{2}=\max\\{\sqrt{27(1+C_{Y}(4s))},\sqrt{27(4s-1)!!}C_{X}^{s}\\}$,
then

$\displaystyle\sqrt{\mathbb{E}\dot{\phi}_{0}^{4}(\bm{\beta})}\leq
C_{\phi}^{2}\left(1+\left(\frac{C_{X}}{p}\|\bm{\beta}\|^{2}\right)^{s}\right)$

For the second moment, notice that

$\displaystyle\sqrt{\mathbb{E}\dot{\phi}_{0}^{2}(\bm{\beta})}$
$\displaystyle\leq[\mathbb{E}\dot{\phi}_{0}^{4}(\bm{\beta})]^{\frac{1}{4}}$
$\displaystyle\leq
C_{\phi}\sqrt{1+\left(\frac{C_{X}}{p}\|\bm{\beta}\|^{2}\right)^{s}}$
$\displaystyle\leq
C_{\phi}\left(1+\left(\frac{C_{X}}{p}\|\bm{\beta}\|^{2}\right)^{s/2}\right).$

where the last step uses $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ again. The same
arguments lead to the same bound for
$\sqrt{\mathbb{E}\phi_{0}^{2}(\bm{\beta})}$.

###  D.5 Proof of Lemma 6

###### Proof.

  1. (a)

Without loss of generality we assume $C=1$ in Assumption A5. Throughout this
proof we use $h(\bm{\beta}),h_{/i}(\bm{\beta}),h^{\alpha}(\bm{\beta})$ and
$h_{/i}^{\alpha}(\bm{\beta})$ for the loss functions of the corresponding
models, defined as:

$\displaystyle h(\bm{\beta})$
$\displaystyle:=\sum_{j=1}^{n}\ell_{j}(\bm{\beta})+\lambda(1-\eta)r_{0}(\bm{\beta})+\lambda\eta\bm{\beta}^{\top}\bm{\beta},$
$\displaystyle h^{\alpha}(\bm{\beta})$
$\displaystyle:=\sum_{j=1}^{n}\ell_{j}(\bm{\beta})+\lambda(1-\eta)r_{0}^{\alpha}(\bm{\beta})+\lambda\eta\bm{\beta}^{\top}\bm{\beta},$
$\displaystyle h_{/i}(\bm{\beta})$ $\displaystyle:=\sum_{j\neq
i}^{n}\ell_{j}(\bm{\beta})+\lambda(1-\eta)r_{0}(\bm{\beta})+\lambda\eta\bm{\beta}^{\top}\bm{\beta},$
$\displaystyle h_{/i}^{\alpha}(\bm{\beta})$ $\displaystyle:=\sum_{j\neq
i}^{n}\ell_{j}(\bm{\beta})+\lambda(1-\eta)r_{0}^{\alpha}(\bm{\beta})+\lambda\eta\bm{\beta}^{\top}\bm{\beta}.$

It is straightforward to show that

$\displaystyle\lambda\eta\|\widehat{\bm{\beta}}\|_{2}^{2}\leq$
$\displaystyle~{}\sum_{j\in[n]}\ell(y_{j},\mathbf{x}_{j}^{\top}\widehat{\bm{\beta}})+\lambda(1-\eta)r_{0}(\widehat{\bm{\beta}})+\lambda\eta\|\widehat{\bm{\beta}}\|_{2}^{2}\leq~{}\sum_{j=1}^{n}\ell(y_{j},0),$

where the last inequality is due to the fact that $h(\widehat{\bm{\beta}})\leq
h(\mathbf{0})$ and that $\ell(y,z)\geq 0$. Similarly we have
$\lambda\eta\|\widehat{\bm{\beta}}_{/i}\|_{2}^{2}\leq\sum_{j=1}^{n}\ell(y_{j},0)$.

We can then use Assumption A5 to obtain

$\displaystyle\mathbb{E}\left(\frac{1}{p}\|\widehat{\bm{\beta}}\|^{2}\right)^{t}\leq(p\lambda\eta)^{-t}\mathbb{E}[n+|y_{1}|^{s}+\cdots+|y_{n}|^{s}]^{t}.$

By Rosenthal inequality (Lemma 9), we have

$\displaystyle\mathbb{E}\left(\frac{1}{p}\|\widehat{\bm{\beta}}\|^{2}\right)^{t}$
$\displaystyle\leq(p\lambda\eta)^{-t}A(t)\max\left\\{n^{t}+n\mathbb{E}|y_{1}|^{st},(n+n\mathbb{E}|y_{1}|^{s})^{t}\right\\}$
$\displaystyle\leq\left(\frac{\gamma_{0}}{\lambda\eta}\right)^{t}A(t)\max\left\\{1+n^{1-t}C_{Y}(st),(1+C_{Y}(s))^{t}\right\\}$
$\displaystyle\leq\left(\frac{\gamma_{0}}{\lambda\eta}\right)^{t}A(t)\max\left\\{1+C_{Y}(st),(1+C_{Y}(s))^{t}\right\\}:=C_{\beta}(t),$
(19)

where $C_{Y}(\cdot)$ is the constant in Assumption A5, and $A(\cdot)$ is the
Rosenthal constant in Lemma 9.

  2. (b)

Our next goal is to obtain an upper bound for
$\mathbb{E}\dot{\ell}_{1}^{8}(\widehat{\bm{\beta}}_{/1})$. By using Assumption
A5 we have

$\displaystyle\mathbb{E}\dot{\ell}_{1}^{8}(\widehat{\bm{\beta}}_{/1})$
$\displaystyle\leq\mathbb{E}[1+|y_{1}|^{s}+|\mathbf{x}_{1}^{\top}\widehat{\bm{\beta}}_{/1}|^{s}]^{8}$
$\displaystyle\leq
3^{7}\left(1+\mathbb{E}|y_{1}|^{8s}+\mathbb{E}|\mathbf{x}_{1}^{\top}\widehat{\bm{\beta}}_{/1}|^{8s}\right).$
(20)

Next we bound
$\mathbb{E}|\mathbf{x}_{1}^{\top}\widehat{\bm{\beta}}_{/1}|^{8s}$:

$\displaystyle\mathbb{E}|\mathbf{x}_{1}^{\top}\widehat{\bm{\beta}}_{/1}|^{8s}$
$\displaystyle=\mathbb{E}\left[\mathbb{E}[|\mathbf{x}_{1}^{\top}\widehat{\bm{\beta}}_{/1}|^{8s}|\widehat{\bm{\beta}}_{/1}]\right]$
$\displaystyle\leq\mathbb{E}[(8s-1)!!(\widehat{\bm{\beta}}_{/1}^{\top}\bm{\Sigma}\widehat{\bm{\beta}}_{/1})^{4s}]$
$\displaystyle\leq(8s-1)!!\mathbb{E}\left(\frac{C_{X}}{p}\|\widehat{\bm{\beta}}_{/1}\|^{2}\right)^{4s}$
$\displaystyle\leq(8s-1)!!C_{X}^{4s}C_{\beta}(4s)$

where the second line uses the fact that
$\mathbf{x}_{1}^{\top}\widehat{\bm{\beta}}_{/1}|\widehat{\bm{\beta}}_{/1}\sim
N(0,\widehat{\bm{\beta}}_{/1}^{\top}\bm{\Sigma}\widehat{\bm{\beta}}_{/1})$ and
that the $t^{\rm th}$ moment of a standard Gaussian variable is $(t-1)!!$
whenever $t$ is a positive even number. The last line uses (19). Inserting
this back to (20) we have:

$\displaystyle\mathbb{E}\dot{\ell}_{1}^{8}(\widehat{\bm{\beta}}_{/1})\leq
3^{7}(1+C_{Y}(8s)+(8s-1)!!C_{X}^{4s}C_{\beta}(4s)):=C_{\ell}.$

∎

###  D.6 Proof of Lemma 7

Recall that

${\rm LO}=\frac{1}{n}\sum_{i=1}^{n}\phi_{j}(\widehat{\bm{\beta}}_{/i}).$

Then we have

$\displaystyle\mathbb{E}V_{1}^{2}=$ $\displaystyle\mathbb{E}\left({\rm
LO}-\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}[\phi_{i}(\widehat{\bm{\beta}}_{/i})|{\cal
D}_{/i}]\right)^{2}$ $\displaystyle=$
$\displaystyle\frac{1}{n}\mathbb{E}\left(\phi_{1}(\widehat{\bm{\beta}}_{/1})-\mathbb{E}[\phi_{1}(\widehat{\bm{\beta}}_{/1})|{\cal
D}_{/1}]\right)^{2}$
$\displaystyle+\frac{n-1}{n}\mathbb{E}\left(\phi_{1}(\widehat{\bm{\beta}}_{/1})-\mathbb{E}[\phi_{1}(\widehat{\bm{\beta}}_{/1})|{\cal
D}_{/1}]\right)\cdot\left(\phi_{2}(\widehat{\bm{\beta}}_{/2})-\mathbb{E}[\phi_{2}(\widehat{\bm{\beta}}_{/2})|{\cal
D}_{/2}]\right).$ (21)

Note that

$\displaystyle~{}\mathbb{E}\left[\left(\phi_{1}(\widehat{\bm{\beta}}_{/1})-\mathbb{E}(\phi_{1}(\widehat{\bm{\beta}}_{/1})|{\cal
D}_{/1})\right)\right]^{2}$ $\displaystyle=$
$\displaystyle~{}\mathbb{E}\operatorname{var}(\phi_{1}(\widehat{\bm{\beta}}_{/1})|{\cal
D}_{/1})$ $\displaystyle\leq$
$\displaystyle~{}\mathbb{E}\left(\mathbb{E}[\phi_{1}^{2}(\widehat{\bm{\beta}}_{/1})|{\cal
D}_{/1}]\right)$ $\displaystyle\leq$
$\displaystyle~{}\mathbb{E}\left(C_{\phi}+C_{\phi}\left(\frac{1}{p}\|\widehat{\bm{\beta}}_{/1}\|^{2}\right)^{\frac{s}{2}}\right)^{2}$
$\displaystyle\leq$
$\displaystyle~{}2C_{\phi}^{2}+2C_{\phi}^{2}\mathbb{E}\left(\frac{1}{p}\|\widehat{\bm{\beta}}_{/1}\|^{2}\right)^{s}$
$\displaystyle\leq$
$\displaystyle~{}2C_{\phi}^{2}\left(1+C_{\beta}(s)\right):=C_{v1,1}$ (22)

where the fourth line uses Lemma 5, and the last line uses part (a) of Lemma
6. Next, we study

$\mathbb{E}\left(\phi_{1}(\widehat{\bm{\beta}}_{/1})-\mathbb{E}(\phi_{1}(\widehat{\bm{\beta}}_{/1})|{\cal
D}_{/1})\right)\cdot\left(\phi_{2}(\widehat{\bm{\beta}}_{/2})-\mathbb{E}(\phi_{2}(\widehat{\bm{\beta}}_{/2})|{\cal
D}_{/2})\right).$

Define
$\widehat{\bm{\beta}}_{/12}:=\underset{\bm{\beta}\in\bm{\Theta}}{\operatorname{argmin}}\Bigl{\\{}\sum_{j\geq
3}\ell(y_{j},\mathbf{x}_{j}^{\top}\bm{\beta})+\lambda
r(\bm{\beta})\Bigr{\\}}$. By the mean-value theorem, there exists a random
variable $t\in[0,1]$ such that

$\phi_{1}(\widehat{\bm{\beta}}_{/1})=\phi_{1}(\widehat{\bm{\beta}}_{/12})+\dot{\phi}_{1}(t\widehat{\bm{\beta}}_{/1}+(1-t)\widehat{\bm{\beta}}_{/12})\mathbf{x}_{1}^{\top}(\widehat{\bm{\beta}}_{/1}-\widehat{\bm{\beta}}_{/12}).$

Hence,

$\displaystyle~{}\mathbb{E}[\phi_{1}(\widehat{\bm{\beta}}_{/1})|{\cal
D}_{/1}]$ $\displaystyle=$
$\displaystyle~{}\mathbb{E}[\phi_{1}(\widehat{\bm{\beta}}_{/12})|{\cal
D}_{/1}]+\mathbb{E}[\dot{\phi}_{1}(t\widehat{\bm{\beta}}_{/1}+(1-t)\widehat{\bm{\beta}}_{/12})\mathbf{x}_{1}^{\top}(\widehat{\bm{\beta}}_{/1}-\widehat{\bm{\beta}}_{/12})|{\cal
D}_{/1}]$ $\displaystyle=$
$\displaystyle~{}\mathbb{E}[\phi_{0}(\widehat{\bm{\beta}}_{/12})|{\cal
D}_{/12}]+\mathbb{E}[\dot{\phi}_{0}(t\widehat{\bm{\beta}}_{/1}+(1-t)\widehat{\bm{\beta}}_{/12})\mathbf{x}_{0}^{\top}|{\cal
D}_{/1}](\widehat{\bm{\beta}}_{/1}-\widehat{\bm{\beta}}_{/12}).$

Similarly, we have

$\phi_{2}(\widehat{\bm{\beta}}_{/2})=\phi_{2}(\widehat{\bm{\beta}}_{/12})+\dot{\phi}_{2}(t\widehat{\bm{\beta}}_{/2}+(1-t)\widehat{\bm{\beta}}_{/12})\mathbf{x}_{2}^{\top}(\widehat{\bm{\beta}}_{/2}-\widehat{\bm{\beta}}_{/12}).$

and

$\mathbb{E}[\phi_{2}(\widehat{\bm{\beta}}_{/2})|{\cal
D}_{/2}]=\mathbb{E}[\phi_{0}(\widehat{\bm{\beta}}_{/12})|{\cal
D}_{/12}]+\mathbb{E}[\dot{\phi}_{0}(t\widehat{\bm{\beta}}_{/2}+(1-t)\widehat{\bm{\beta}}_{/12})\mathbf{x}_{0}^{\top}|{\cal
D}_{/2}](\widehat{\bm{\beta}}_{/2}-\widehat{\bm{\beta}}_{/12})$

Then (D.6) can be decomposed into four terms:

$\displaystyle\mathbb{E}\left(\phi_{1}(\widehat{\bm{\beta}}_{/1})-\mathbb{E}(\phi_{1}(\widehat{\bm{\beta}}_{/1})|{\cal
D}_{/1})\right)\cdot\left(\phi_{2}(\widehat{\bm{\beta}}_{/2})-\mathbb{E}(\phi_{2}(\widehat{\bm{\beta}}_{/2})|{\cal
D}_{/2})\right)$ $\displaystyle=$ $\displaystyle A_{1}+B_{1}+C_{1}+D_{1},$
(24)

where $A_{1},B_{1},C_{1},$ and $D_{1}$ are defined as

$\displaystyle A_{1}$
$\displaystyle:=~{}\mathbb{E}\left(\phi_{1}(\widehat{\bm{\beta}}_{/12})-\mathbb{E}[\phi_{0}(\widehat{\bm{\beta}}_{/12})|{\cal
D}_{/12}]\right)\left(\phi_{2}(\widehat{\bm{\beta}}_{/12})-\mathbb{E}[\phi_{0}(\widehat{\bm{\beta}}_{/12})|{\cal
D}_{/12}]\right)$ $\displaystyle B_{1}$
$\displaystyle:=\mathbb{E}\Big{[}\left(\phi_{1}(\widehat{\bm{\beta}}_{/12})-\mathbb{E}\bigl{[}\phi_{0}(\widehat{\bm{\beta}}_{/12})|{\cal
D}_{/12}\bigr{]}\right)$
$\displaystyle\quad\times\Big{(}\dot{\phi}_{2}(\widehat{\bm{\beta}}_{/2}+(1-t)\widehat{\bm{\beta}}_{/12})\mathbf{x}_{2}^{\top}(\widehat{\bm{\beta}}_{/2}-\widehat{\bm{\beta}}_{/12})-\mathbb{E}[\dot{\phi}_{2}(\widehat{\bm{\beta}}_{/2}+(1-t)\widehat{\bm{\beta}}_{/12})\mathbf{x}_{2}^{\top}(\widehat{\bm{\beta}}_{/2}-\widehat{\bm{\beta}}_{/12})|{\cal
D}_{/2}]\Big{)}\Big{]}$ $\displaystyle C_{1}$
$\displaystyle:=\mathbb{E}\Big{[}\left(\phi_{2}(\widehat{\bm{\beta}}_{/12})-\mathbb{E}[\phi_{0}(\widehat{\bm{\beta}}_{/12})|{\cal
D}_{/12}]\right)$
$\displaystyle\quad\times\Big{(}\dot{\phi}_{1}(\widehat{\bm{\beta}}_{/1}+(1-t)\widehat{\bm{\beta}}_{/12})\mathbf{x}_{1}^{\top}(t\widehat{\bm{\beta}}_{/1}-\widehat{\bm{\beta}}_{/12})-\mathbb{E}\left[\dot{\phi}_{1}(t\widehat{\bm{\beta}}_{/1}+(1-t)\widehat{\bm{\beta}}_{/12})\mathbf{x}_{1}^{\top}(\widehat{\bm{\beta}}_{/1}-\widehat{\bm{\beta}}_{/12})|{\cal
D}_{/1}\right]\Big{)}\Big{]}$ $\displaystyle D_{1}$
$\displaystyle:=\mathbb{E}\Biggl{\\{}\biggl{(}\dot{\phi}_{1}(t\widehat{\bm{\beta}}_{/1}+(1-t)\widehat{\bm{\beta}}_{/12})\mathbf{x}_{1}^{\top}(\widehat{\bm{\beta}}_{/1}-\widehat{\bm{\beta}}_{/12})-\mathbb{E}\bigl{[}\dot{\phi}_{1}(t\widehat{\bm{\beta}}_{/1}+(1-t)\widehat{\bm{\beta}}_{/12})\mathbf{x}_{1}^{\top}(\widehat{\bm{\beta}}_{/1}-\widehat{\bm{\beta}}_{/12})|{\cal
D}_{/1}\bigr{]}\biggr{)}$
$\displaystyle\quad\times\biggl{(}\dot{\phi}_{2}(\widehat{\bm{\beta}}_{/2}+(1-t)\widehat{\bm{\beta}}_{/12})\mathbf{x}_{2}^{\top}(\widehat{\bm{\beta}}_{/2}-\widehat{\bm{\beta}}_{/12})-\mathbb{E}\bigl{[}\dot{\phi}_{2}(\widehat{\bm{\beta}}_{/2}+(1-t)\widehat{\bm{\beta}}_{/12})\mathbf{x}_{2}^{\top}(\widehat{\bm{\beta}}_{/2}-\widehat{\bm{\beta}}_{/12})|{\cal
D}_{/2}\bigr{]}\biggr{)}\Biggr{\\}}.$

We bound each of these four terms below. For $A_{1}$ we have

$\displaystyle A_{1}:=$
$\displaystyle~{}\mathbb{E}\left(\phi_{1}(\widehat{\bm{\beta}}_{/12})-\mathbb{E}[\phi_{0}(\widehat{\bm{\beta}}_{/12})|{\cal
D}_{/12}]\right)\left(\phi_{2}(\widehat{\bm{\beta}}_{/12})-\mathbb{E}[\phi_{0}(\widehat{\bm{\beta}}_{/12})|{\cal
D}_{/12}]\right)$ $\displaystyle=$
$\displaystyle~{}\mathbb{E}\left[\mathbb{E}\left[\left(\phi_{1}(\widehat{\bm{\beta}}_{/12})-\mathbb{E}[\phi_{0}(\widehat{\bm{\beta}}_{/12})|{\cal
D}_{/12}]\right)\left.\left(\phi_{2}(\widehat{\bm{\beta}}_{/12})-\mathbb{E}[\phi_{0}(\widehat{\bm{\beta}}_{/12})|{\cal
D}_{/12}]\right)\right|{\cal D}_{/12}\right]\right]$ $\displaystyle=$
$\displaystyle~{}0.$ (25)

where the last equality is correct, because given ${\cal D}_{/12}$,
$\phi_{1}(\widehat{\bm{\beta}}_{/12})$ and
$\phi_{2}(\widehat{\bm{\beta}}_{/12})$ are conditionally independent, and
hence the inner expectation can be taken to each term separately. Similarly,

$\displaystyle B_{1}$
$\displaystyle:=\mathbb{E}\Big{[}\left(\phi_{1}(\widehat{\bm{\beta}}_{/12})-\mathbb{E}\bigl{[}\phi_{0}(\widehat{\bm{\beta}}_{/12})|{\cal
D}_{/12}\bigr{]}\right)$
$\displaystyle\quad\times\Big{(}\dot{\phi}_{2}(\widehat{\bm{\beta}}_{/2}+(1-t)\widehat{\bm{\beta}}_{/12})\mathbf{x}_{2}^{\top}(\widehat{\bm{\beta}}_{/2}-\widehat{\bm{\beta}}_{/12})-\mathbb{E}[\dot{\phi}_{2}(\widehat{\bm{\beta}}_{/2}+(1-t)\widehat{\bm{\beta}}_{/12})\mathbf{x}_{2}^{\top}(\widehat{\bm{\beta}}_{/2}-\widehat{\bm{\beta}}_{/12})|{\cal
D}_{/2}]\Big{)}\Big{]}$
$\displaystyle=\mathbb{E}\Big{\\{}\mathbb{E}\Big{[}\left(\phi_{1}(\widehat{\bm{\beta}}_{/12})-\mathbb{E}\bigl{[}\phi_{0}(\widehat{\bm{\beta}}_{/12})|{\cal
D}_{/12}\bigr{]}\right)$
$\displaystyle\quad\times\left.\Big{(}\dot{\phi}_{2}(\widehat{\bm{\beta}}_{/2}+(1-t)\widehat{\bm{\beta}}_{/12})\mathbf{x}_{2}^{\top}(\widehat{\bm{\beta}}_{/2}-\widehat{\bm{\beta}}_{/12})-\mathbb{E}[\dot{\phi}_{2}(\widehat{\bm{\beta}}_{/2}+(1-t)\widehat{\bm{\beta}}_{/12})\mathbf{x}_{2}^{\top}(\widehat{\bm{\beta}}_{/2}-\widehat{\bm{\beta}}_{/12})|{\cal
D}_{/2}]\Big{)}\right|{\cal D}_{/2}\Big{]}\Big{\\}}$ $\displaystyle=0.$ (26)

Again, the last equality is correct, because given ${\cal D}_{/2}$,
$\phi_{1}(\widehat{\bm{\beta}}_{/12})$ and
$\dot{\phi}_{2}(\widehat{\bm{\beta}}_{/2}+(1-t)\widehat{\bm{\beta}}_{/12})\mathbf{x}_{2}$
are conditionally independent. Similarly,

$\displaystyle C_{1}$
$\displaystyle:=\mathbb{E}\Big{[}\left(\phi_{2}(\widehat{\bm{\beta}}_{/12})-\mathbb{E}[\phi_{0}(\widehat{\bm{\beta}}_{/12})|{\cal
D}_{/12}]\right)$
$\displaystyle\quad\times\Big{(}\dot{\phi}_{1}(\widehat{\bm{\beta}}_{/1}+(1-t)\widehat{\bm{\beta}}_{/12})\mathbf{x}_{1}^{\top}(t\widehat{\bm{\beta}}_{/1}-\widehat{\bm{\beta}}_{/12})-\mathbb{E}\left[\dot{\phi}_{1}(t\widehat{\bm{\beta}}_{/1}+(1-t)\widehat{\bm{\beta}}_{/12})\mathbf{x}_{1}^{\top}(\widehat{\bm{\beta}}_{/1}-\widehat{\bm{\beta}}_{/12})|{\cal
D}_{/1}\right]\Big{)}\Big{]}$ $\displaystyle=0.$ (27)

Finally,

$\displaystyle D_{1}$
$\displaystyle:=\mathbb{E}\Biggl{\\{}\biggl{(}\dot{\phi}_{1}(t\widehat{\bm{\beta}}_{/1}+(1-t)\widehat{\bm{\beta}}_{/12})\mathbf{x}_{1}^{\top}(\widehat{\bm{\beta}}_{/1}-\widehat{\bm{\beta}}_{/12})-\mathbb{E}\bigl{[}\dot{\phi}_{1}(t\widehat{\bm{\beta}}_{/1}+(1-t)\widehat{\bm{\beta}}_{/12})\mathbf{x}_{1}^{\top}(\widehat{\bm{\beta}}_{/1}-\widehat{\bm{\beta}}_{/12})|{\cal
D}_{/1}\bigr{]}\biggr{)}$
$\displaystyle\quad\times\biggl{(}\dot{\phi}_{2}(\widehat{\bm{\beta}}_{/2}+(1-t)\widehat{\bm{\beta}}_{/12})\mathbf{x}_{2}^{\top}(\widehat{\bm{\beta}}_{/2}-\widehat{\bm{\beta}}_{/12})-\mathbb{E}\bigl{[}\dot{\phi}_{2}(\widehat{\bm{\beta}}_{/2}+(1-t)\widehat{\bm{\beta}}_{/12})\mathbf{x}_{2}^{\top}(\widehat{\bm{\beta}}_{/2}-\widehat{\bm{\beta}}_{/12})|{\cal
D}_{/2}\bigr{]}\biggr{)}\Biggr{\\}}$
$\displaystyle\overset{(a)}{\leq}\mathbb{E}\operatorname{var}\left[\dot{\phi}_{1}(t\widehat{\bm{\beta}}_{/1}+(1-t)\widehat{\bm{\beta}}_{/12})\mathbf{x}_{1}^{\top}(\widehat{\bm{\beta}}_{/1}-\widehat{\bm{\beta}}_{/12})|{\cal
D}_{/1}\right]$
$\displaystyle\leq\mathbb{E}\left[\mathbb{E}\left[\dot{\phi}_{1}^{2}(t\widehat{\bm{\beta}}_{/1}+(1-t)\widehat{\bm{\beta}}_{/12})[\mathbf{x}_{1}^{\top}(\widehat{\bm{\beta}}_{/1}-\widehat{\bm{\beta}}_{/12})]^{2}|{\cal
D}_{/1}\right]\right]$
$\displaystyle\overset{(b)}{\leq}\mathbb{E}\left[\sqrt{\mathbb{E}[\dot{\phi}_{1}^{4}(\bm{\xi}_{1})|{\cal
D}_{/1}]}\sqrt{\mathbb{E}\left[[\mathbf{x}_{1}^{\top}(\bm{\beta}_{/1}-\bm{\beta}_{/12})]^{4}|{\cal
D}_{/1}\right]}\right]$
$\displaystyle\overset{(c)}{\leq}\mathbb{E}\left[C_{\phi}^{2}\left(1+\left(\frac{1}{p}\|\bm{\xi}\|^{2}\right)^{s}\right)\cdot\frac{\sqrt{3}C_{X}}{p}\|\widehat{\bm{\beta}}_{/1}-\widehat{\bm{\beta}}_{/12}\|^{2}\right]$
$\displaystyle\overset{(d)}{\leq}\frac{\sqrt{3}C_{\phi}^{2}C_{X}}{p(2\lambda\eta\wedge
1)^{2}}\mathbb{E}\left[\left(1+\left(p^{-1}\|\bm{\xi}\|^{2}\right)^{s}\right)|\dot{\ell}_{2}(\widehat{\bm{\beta}}_{/12})|^{2}\|\mathbf{x}_{2}\|^{2}\right]$
$\displaystyle\overset{(e)}{\leq}\frac{\sqrt{3}C_{\phi}^{2}C_{X}}{p(2\lambda\eta\wedge
1)^{2}}\sqrt{\mathbb{E}\left(1+\left(p^{-1}\|\bm{\xi}\|^{2}\right)^{s}\right)^{2}}\cdot\left(\mathbb{E}|\dot{\ell}_{2}(\widehat{\bm{\beta}}_{/12})|^{8}\right)^{\frac{1}{4}}\left(\mathbb{E}\|\mathbf{x}_{2}\|^{8}\right)^{\frac{1}{4}}$
$\displaystyle\overset{(f)}{\leq}\frac{\sqrt{3}\gamma_{0}C_{\phi}^{2}C_{X}}{n(2\lambda\eta\wedge
1)^{2}}\sqrt{2+2C_{\beta}(2s)}C_{\ell}^{\frac{1}{4}}(24C_{X}^{4})^{\frac{1}{4}}$
$\displaystyle:=\frac{C_{v1,2}}{n}.$ (28)

where inequality (a) uses Cauchy Schwarz inequality and symmetry between
$\dot{\phi}_{1}$ and $\dot{\phi}_{2}$, (b) uses Cauchy Schwarz again, (c) uses
Lemma 5 and the fact that, conditioned on ${\cal D}$,
$\mathbf{x}_{1}^{\top}(\widehat{\bm{\beta}}_{/1}-\widehat{\bm{\beta}}_{/12})\sim
N(0,\widehat{\bm{\beta}}_{/1}-\widehat{\bm{\beta}}_{/12}^{\top}\bm{\Sigma}\widehat{\bm{\beta}}_{/1}-\widehat{\bm{\beta}}_{/12})$.
Inequality (d) uses Lemma 4. Inequality (e) uses Cauchy Schwarz twice. Finally
inequality (f) uses Lemma 6 and Lemma 8. Plugging in the results of equations
(D.6)-(28) into (D.6), and then using (22), the bound in (D.6) boils down to

$\displaystyle\mathbb{E}V_{1}^{2}\leq\dfrac{C_{v1,1}+C_{v1,2}}{n}:=\frac{C_{v1}}{n}$

where, after some simplification:

$C_{v1}=2C_{\phi}^{2}\left(1+C_{\beta}(s)\right)+\frac{\sqrt{6}(24)^{\frac{1}{4}}C_{\phi}^{2}C_{X}^{2}C_{\ell}^{\frac{1}{4}}\gamma_{0}}{(2\lambda\eta\wedge
1)^{2}}\sqrt{1+C_{\beta}(2s)}.$

This finishes the proof of Lemma 7. ∎