# Minimum $\ell_{1}$-norm interpolators:
Precise asymptotics and multiple descent

Yue Li Department of Statistics and Data Science, Carnegie Mellon University,
Pittsburgh, PA 15213, USA. Yuting Wei
Department of Statistics and Data Science, The Wharton School, University of
Pennsylvania, Philadelphia, PA 19104, USA.

###### Abstract

An evolving line of machine learning works observe empirical evidence that
suggests interpolating estimators — the ones that achieve zero training error
— may not necessarily be harmful. This paper pursues theoretical understanding
for an important type of interpolators: the minimum $\ell_{1}$-norm
interpolator, which is motivated by the observation that several learning
algorithms favor low $\ell_{1}$-norm solutions in the over-parameterized
regime. Concretely, we consider the noisy sparse regression model under
Gaussian design, focusing on linear sparsity and high-dimensional asymptotics
(so that both the number of features and the sparsity level scale
proportionally with the sample size).

We observe, and provide rigorous theoretical justification for, a curious
_multi-descent_ phenomenon; that is, the generalization risk of the minimum
$\ell_{1}$-norm interpolator undergoes multiple (and possibly more than two)
phases of descent and ascent as one increases the model capacity. This
phenomenon stems from the special structure of the minimum $\ell_{1}$-norm
interpolator as well as the delicate interplay between the over-parameterized
ratio and the sparsity, thus unveiling a fundamental distinction in geometry
from the minimum $\ell_{2}$-norm interpolator. Our finding is built upon an
exact characterization of the risk behavior, which is governed by a system of
two non-linear equations with two unknowns.

Keywords: minimum norm interpolators, multiple descent, Lasso, sparse linear
regression, exact asymptotics, approximate message passing

###### Contents

  1. 1 Introduction
    1. 1.1 Motivation: a multi-descent phenomenon
    2. 1.2 Main results and insights
    3. 1.3 A glimpse of our technical approach and novelty
    4. 1.4 Other related works
    5. 1.5 Notation
  2. 2 Risk characterization for the minimum $\ell_{1}$-norm interpolator
    1. 2.1 Modelling assumptions
    2. 2.2 Risk characterization
    3. 2.3 Connections to the Lasso estimator
  3. 3 Key analysis
    1. 3.1 Key analysis tool: approximate message passing
    2. 3.2 Analysis ingredients for the risk curve
  4. 4 Numerical simulations and discussion
  5. A Proof of Proposition 1
  6. B Properties of the state evolution parameters
    1. B.1 Main results
    2. B.2 Proof of Proposition B.1 and Proposition B.2
    3. B.3 Proof of Proposition B.3
  7. C Proofs about the AMP updates
    1. C.1 Proof of Theorem 3
    2. C.2 Proof of Lemma C.1
    3. C.3 Proof of supporting lemmas to Lemma C.1
    4. C.4 Proof of Lemma C.5 and Lemma C.7
  8. D Proofs about the risk curve
    1. D.1 Proof of Lemma 1 and Lemma 2
    2. D.2 Limiting orders of ${\alpha^{\star}}$ and ${\nu^{\star}}$ when $\delta\rightarrow 0^{+}$: proof of Lemma D.1
    3. D.3 Limiting orders of the partial derivatives: proof of Lemma D.2
    4. D.4 Proof of Lemma 3
  9. E Auxiliary lemmas and details
    1. E.1 An example satisfying Assumption 1
    2. E.2 Auxiliary lemma for Gaussian distributions

##  1 Introduction

At the core of statistical learning lies the problem of understanding the
generalization performance (e.g., out-of-sample errors) of the learning
algorithms in use. Conventional wisdom in statistics held that including too
many covariates when training statistical models can hurt generalization
(despite improving training accuracy), due to the undesired over-fit. This
leads to the classical conclusion that: proper regularization — through either
adding certain penalty functions to the loss function or algorithmic self-
regularization — seems to be critical in achieving the desired accuracy (e.g.,
Friedman et al., (2001); Wei et al., (2019)). However, an evolving line of
works in machine learning observes empirical evidence that suggests, to the
surprise of many statisticians, over-parameterization is not necessarily
harmful. Indeed, many machine learning models (such as random forests or deep
neural networks) are trained until the training error vanishes to zero —
meaning that they are able to perfectly interpolate the data — while still
generalizing well (e.g., Zhang et al., (2021); Wyner et al., (2017); Belkin et
al., (2019)). As a key observation to explain this phenomenon, many models
when trained by gradient type methods (e.g., gradient descent, stochastic
gradient descent, AdaBoost) converge to certain minimum norm interpolators,
which implicitly favor models with smaller model complexity.

These empirical mysteries inspire a recent flurry of activity towards
understanding the generalization properties of various interpolators. A
dominant fraction of recent efforts, however, concentrated on studying certain
minimum $\ell_{2}$-norm interpolators, primarily in the context of linear
and/or kernel regression (see, e.g., Liang and Rakhlin, (2020); Mei and
Montanari, (2019); Hastie et al., (2019); Belkin et al., (2020); Bartlett et
al., (2020, 2021) and the references therein). This was in part due to the
existence of closed-form expressions for minimum $\ell_{2}$-norm
interpolators, which are particularly handy when determining the statistical
risk. In contrast, the theoretical underpinnings for minimum $\ell_{1}$-norm
interpolators, despite growing interest (e.g., Ju et al., (2020); Liang and
Sur, (2020); Chinot et al., (2020)), remain highly inadequate and considerably
more challenging to establish. Given that multiple learning algorithms are
known to favor low $\ell_{1}$-norm solutions in the over-parameterized regime
(such as Rosset et al., (2004); Gunasekar et al., (2018)), understanding the
statistical properties of the minimum $\ell_{1}$-norm interpolation plays a
pivotal role in unveiling the trade-offs between over-parameterization and
generalization, which we seek to explore in this paper.

###  1.1 Motivation: a multi-descent phenomenon

An intriguing empirical phenomenon called “ _double descent_ ” has recently
emerged in the study of over-parameterized learning models (Neyshabur et al.,,
2014; Nakkiran et al.,, 2019; Belkin et al.,, 2018, 2019; Belkin,, 2021).
Consider, for example, a risk curve that depicts how the generalization error
varies as more parameters are added to the model. Following the classical
bias-variance trade-off U-shape curve before entering the interpolation (or
over-parameterized) regime (Friedman et al.,, 2001), the generalization error
of various models descends again as one further increases the number of
parameters beyond the interpolation limit. In addition, this double-descent
phenomenon is also closely related to a curious observation — the non-
monotonicy of risk as the model capacity grows — that has attracted much
recent attention (Viering et al.,, 2019).

Aimed at distilling insights that help explain this phenomenon, a recent body
of works studied the behavior of the minimum $\ell_{2}$-norm interpolator in
the presence of a linear model, which solidified the double-descent phenomenon
for this interpolator (see, e.g., Mei and Montanari, (2019); Hastie et al.,
(2019); Bartlett et al., (2020); Belkin et al., (2020) and the references
therein). Moving beyond minimum $\ell_{2}$-norm interpolators, empirical
observations have been discussed regarding the minimum $\ell_{1}$-norm
interpolator as well; for instance, similar double descent was numerically
observed in Muthukumar et al., (2020), with heuristic justification provided
in Mitra, (2019) based on statistical physics intuitions. Our own numerical
experiments uncover even more intriguing risk behavior of the minimum
$\ell_{1}$-norm interpolator. As illustrated in Figure 1 and Figure 2, we
observe “ _multiple descent_ ” in certain parameter regimes; that is, as the
model complexity continues to grow, the out-of-sample risk of the minimum
$\ell_{1}$-norm interpolator undergoes multiple phases of increase and
decrease, and ultimately becomes non-increasing even as the over-parameterized
ratio tends to infinity. There is, however, lack of theoretical support that
elucidates this empirical observation. It remains unclear how to interpret the
striking distinction in the risk behavior between the minimum $\ell_{1}$-norm
and the minimum $\ell_{2}$-norm interpolators.

Figure 1: Triple descent in sparse linear regression (see model (1)), when the
ratio of the sparsity $s$ of the true signal and the sample size $n$ stays
fixed. More specifically, we fix $s/n=0.3$ and $s/n\cdot M^{2}=10$ (where $M$
is the magnitude of non-zero entries). When $s\leq p$, the true signal
$\bm{\theta}^{\star}$ is set as an $s$-sparse vector. When $p<s$, we still set
the true signal $\bm{\theta}^{\star}$ as an $s$-dimensional vector, while
assuming we only have access to a subset of $p$ features. We set the sample
size as $n=100$, and choose $500$ values of $p/n$ such that the $\log(p/n)$’s
are uniformly spaced over $[-2,2.2]$. In each run and for each $p/n$ ratio, we
generate a random instance and compute the minimum $\ell_{1}$-norm
interpolator and its risk. We report the average risk and error bar over these
30 independent runs for each $p/n$ ratio. The solid line represents the fitted
risk curve: when $p/n<1$, we use the theoretical risk of least-square
estimators in the current setting; when $p/n>1$, we employ cubic spline
smoothing to fit an empirical risk curve.  Figure 2:  Multiple-descent
phenomenon observed in numerical experiments. We generate data from a linear
model (1) with i.i.d. Gaussian design, where parameters are set as $\sigma=1$,
SNR$\coloneqq\epsilon M^{2}=2$, and sparsity level $\epsilon=0.01$. The sample
size is fixed at $n=100$, and choice of $p$’s and the calculation of error
bars are the same as Figure 1. The theoretical curve, predicted by results in
the present paper, is shown in solid line, and the $p/n\rightarrow 0$ and
$p/n\rightarrow\infty$ limits are shown in dotted lines. When $p\geq n$, two
descending phases are observed here, where the first descending regime happens
at the interpolation point where $n=p$, which is common for various types of
models including the minimum $\ell_{2}$-norm interpolation. The second descent
appears when $p/n$ is large enough, presenting a unique behavior for
$\ell_{1}$-norm minimization problem.

###  1.2 Main results and insights

In this paper, we concentrate on linear models, and investigate the
generalization error (in terms of the out-of-sample squared error) of the
minimum $\ell_{1}$-norm interpolator — or equivalently, the Lasso estimator
with regularization parameter approaching zero. We pursue a comprehensive
understanding of such estimators in the _proportional growth_ and _over-
parameterized_ regime, where the number of parameters $p$ scales linearly
with, but larger than, the number of samples $n$. Recognize that Figure 1 and
Figure 2 (whose difference only lies in how the sparsity levels are chosen)
exhibit very similar behavior in the over-parameterized regime. To streamline
presentation and avoid repetition, we shall restrict our attention to the
geometric properties of the risk curve in the setting of Figure 2. In what
follows, we formulate the problem precisely, followed by a summary of our main
results.

##### Models.

Setting the stage, imagine that we have gathered $n$ i.i.d. noisy training
data drawn from a linear model

$\displaystyle y_{i}=\langle\bm{x}_{i},\bm{\theta}^{\star}\rangle+z_{i},\qquad
1\leq i\leq n,$ (1)

where $\bm{\theta}^{\star}\in\mathbb{R}^{p}$ is a vector composed of $p$
unknowns, $\bm{x}_{i}\in\mathbb{R}^{p}$ stands for a (random) design vector
known a priori, and the $z_{i}$’s denote i.i.d. Gaussian noise. In addition,
we consider the linear sparsity regime, where (i) the unknown signal
$\bm{\theta}^{\star}$ is $(\epsilon\cdot p)$-sparse for some fixed constant
$\epsilon>0$, and (ii) all the $\epsilon\cdot p$ non-zero entries have
magnitudes proportional to some given quantity $M$ (to be made precise
momentarily in Section 2.1).

Under the well-specified linear model, the generalization error (or out-of-
sample risk) of any estimator $\widehat{\bm{\theta}}$ is defined as the
expected prediction risk over a new sample data
$(\bm{x}_{\text{new}},y_{\text{new}})$:111The expectation is not taken w.r.t.
$\bm{\theta}^{\star}$ here, which is however not important as the risk will
converge almost surely to the expected risk in all cases considered in this
paper.

$\displaystyle\mathsf{Risk}(\widehat{\bm{\theta}})\coloneqq\mathbb{E}\big{[}(\bm{x}_{\text{new}}^{\top}\widehat{\bm{\theta}}-y_{\text{new}})^{2}\big{]}$
(2)

where the new sample data follows the same distributions as the training data
and is independent of the estimator $\widehat{\bm{\theta}}$. Our focal point
is the high-dimensional asymptotics (or the large system limit), that is, we
study the case when $n,p\rightarrow$ with their ratio $n/p$ held fixed. For
notational convenience, we shall often abbreviate the limiting risk as follows
as long as the limit exists almost surely:

$\displaystyle\mathsf{Risk}\big{(}\widehat{\bm{\theta}};\delta\big{)}\coloneqq\lim_{\begin{subarray}{c}n/p=\delta\\\
n,\,p\to\infty\end{subarray}}\mathsf{Risk}\big{(}\widehat{\bm{\theta}}\big{)}.$
(3)

##### Main findings: the risk curve of the minimum $\ell_{1}$-norm
interpolator.

When it comes to the over-parametrized regime where $p>n$, the system of
equations $y_{i}=\langle\bm{x}_{i},\bm{\theta}\rangle$, $1\leq i\leq n$ is
under-determined, thus implying the existence of multiple regression
parameters $\bm{\theta}$ that interpolate the training data perfectly. Among
all possible interpolators, the focal point of this paper is the minimum
$\ell_{1}$-norm intepolator, which enjoys the smallest $\ell_{1}$-norm as
defined below

$\displaystyle\widehat{\bm{\theta}}^{\mathsf{Int}}\coloneqq\arg\\!\min_{\bm{\theta}\in\mathbb{R}^{p}}\|\bm{\theta}\|_{1}\qquad\text{subject
to}\quad y_{i}=\langle\bm{x}_{i},\,\bm{\theta}\rangle,~{}~{}1\leq i\leq n.$
(4)

In an attempt to understand its generalization behavior, we seek to pin down
the exact asymptotics of the above risk metric. Encouragingly, the large
system limit of $\mathsf{Risk}(\widehat{\bm{\theta}}^{\mathsf{Int}})$ can be
accurately pinpointed by solving a system of two nonlinear equations with two
unknowns (to be formalized in Theorem 2). In turn, such risk characterizations
provide a rigorous footing for the multi-descent behavior numerically observed
in Figure 2, as asserted by the following theorem.

######  Theorem 1 (Shape of the risk curve).

Suppose that $0<\delta<1$, and fix $n=\delta p$. Assume i.i.d. Gaussian
design, i.i.d. Gaussian noise, and linear sparsity (to be made precise in
Section 2.1). Then the generalization error (cf. (3)) of the minimum
$\ell_{1}$-norm interpolator (4) satisfies the following properties:

  1. (a)

There exist two constants $1<\eta_{1}<\eta_{2}<\infty$ such that
$\mathsf{Risk}(\widehat{\bm{\theta}}^{\mathsf{Int}};\delta)$ decreases with
$p/n$ within the range $p/n\in(1,\eta_{1})\cup(\eta_{2},\infty)$.

  2. (b)

$\mathsf{Risk}(\widehat{\bm{\theta}}^{\mathsf{Int}};\delta)$ approaches the
risk of the zero estimator (i.e., $\mathsf{Risk}(\bm{0})$) as $p/n$ tends to
infinity.

  3. (c)

For any fixed signal-to-noise ratio (to be defined precisely in (12)), there
exists a constant $\epsilon^{*}>0$ such that if the sparsity ratio $\epsilon$
obeys $\epsilon<\epsilon^{*}$, then one can find a region within the range
$p/n\in(\eta_{1},\eta_{2})$ such that
$\mathsf{Risk}(\widehat{\bm{\theta}}^{\mathsf{Int}};\delta)$ increases with
$p/n$.

  4. (d)

In addition, for every given $\delta$, there exists a threshold
$\tilde{\epsilon}(\delta)$ such that
$\mathsf{Risk}(\widehat{\bm{\theta}}^{\mathsf{Int}};\delta)$ decreases with
$p/n$ at this particular point $\delta$ as long as the sparsity ratio
$\epsilon$ satisfies $\epsilon\leq\tilde{\epsilon}(\delta).$

##### Geometric implications and insights.

Theorem 1 reveals certain geometric properties of the risk curve of the
minimum $\ell_{1}$-norm estimator in the over-parameterized regime (i.e.,
$p>n$). Let us take a moment to discuss the implications regarding how the
risk changes in the over-parameterized ratio $p/n$.

  * •

Theorem 1(a) identifies two non-overlapping regions within the over-
parameterized regime that exhibit risk descent. Consequently, the total number
of descent depends largely on the risk behavior in between these two regions.

  * •

Theorem 1(c) indicates that the risk in between the above-mentioned two
regions exhibits contrastingly different behavior depending on the sparsity
ratio.

    * –

When the sparsity ratio is relatively small, the generalization error exhibits
an intriguing “ _decreasing – increasing – decreasing again_ ” pattern in the
over-parameterized regime. This taken together with what happens in the under-
parameterized regime unveils a _“triple-descent”_ behavior, which matches the
numerical findings in Figure 3. Interestingly, the minimum $\ell_{2}$-norm
interpolator for such a model often enjoys a double-descent behavior rather
than triple descent, thus uncovering a fundamental difference between the
minimum $\ell_{1}$-norm and the minimum $\ell_{2}$-norm interpolation.

    * –

In stark contrast, if the sparsity ratio is relatively large (in the sense
that $\epsilon>\epsilon^{\star}$), the generalization error might actually
decrease monotonically with $p/n$ in the entire over-parameterized regime. If
this were true, then taking it together with the classical conclusion in the
under-parameterized regime would justify the double-descent behavior that has
also been empirically observed in Muthukumar et al., (2020); Mitra, (2019).

  * •

In view of Theorem 1(b), the minimum $\ell_{1}$-norm interpolator is
essentially no better than a trivial estimator (i.e., the zero estimator) when
the over-parameterized ratio $p/n$ is overly large.

  * •

Finally, Theorem 1(d) reveals that at any over-parameterized ratio, the
generalization risk can be decreasing with $p/n$ as long as the sparsity ratio
is small enough.

Figure 3:  Theoretical risk curves for the minimum $\ell_{1}$-norm
interpolation (obtained by solving the system of equations (15)). Here, we set
SNR $=2$, and consider different values of the sparsity ratio $\epsilon$. When
$p/n<1$, the risk curves share similar behavior as the ordinary least square
estimator. When $p/n>1$ and when $\epsilon$ drops below a certain level, the
risk curves present one more descent phase. In contrast, the minimum
$\ell_{2}$-norm interpolation curve exhibits just one descent phase in the
$p>n$ regime in all cases, as plotted in black.

###  1.3 A glimpse of our technical approach and novelty

Demonstrating the multi-descent phenomenon requires understanding the
asymptotic risk of the interpolator of interest, which can be achieved by
analyzing an iterative algorithm called _Approximate Message Passing_ (AMP),
originally proposed by Donoho et al., (2009) in the context of compressed
sensing. Most relevant to our paper is the series of papers by Bayati and
Montanari, 2011a ; Bayati and Montanari, 2011b  that determined the asymptotic
Lasso risk with a fixed and _strictly_ positive regularization. In order to
analyze the minimum $\ell_{1}$-norm interpolator, the present work extends the
AMP machinery to accommodate Lasso with the regularization parameter
approaching zero, which can be accomplished by running a sequence of AMP that
changes the algorithm parameters in an epoch-based manner. Noteworthily,
previous analyses relied on the observation that having positive
regularization encourages sparse solutions and, in turn, induces certainty
restricted strong convexity around the solution. This, however, fails to
capture our AMP dynamics due to the absence of positive regularization. To
remedy this issue, we develop a new type of structural properties that allows
one to analyze AMP iterates with changing parameters. As it turns out, the
minimum $\ell_{1}$-norm solution coincides with the fixed-point of the new AMP
updates, whose risk behavior can be characterized by a new system of two
nonlinear equations with two unknowns. Obtaining the exact characterization of
the minimum $\ell_{1}$-norm is beyond what prior AMP theory has to offer.

With the risk characterization in place, everything boils down to analyzing
the above-mentioned nonlinear systems of equations — in particular, how its
solutions vary with the aspect ratio $\delta$. This, however, is challenging
to cope with, as there is no closed-form expression of the solution points.
While the prior work Miolane and Montanari, (2018) studied the existence and
uniqueness of the state evolution solutions, it is unclear how the solution
varies with $\delta$, particularly in the absence of strictly positive
regularization. All this is addressed in the present paper via careful
analysis of the first- and second-order properties of the system of equations,
which constitutes much of our analysis. We expect our analysis idea to be
useful to analyze other estimators such as more general M-estimators (Donoho
and Montanari,, 2016) or the SLOPE estimator (Su and Candes,, 2016).

###  1.4 Other related works

##### Multiple descent.

While the emergence of the multi-descent phenomenon in our setting is caused
by the special structure of minimum $\ell_{1}$-norm interpolators as well as
the interplay between the over-parameterized ratio and the sparsity level,
this phenomenon has also been observed in other settings for $\ell_{2}$-norm
minimization — albeit of different nature compared to ours. It is noteworthy
that the presence of multiple descent can be caused by various other
structures of the design matrix. As concrete examples, this might arise in
non-isotropic linear regression where the covariance of the design matrix
possesses two eigenspaces of different variance (Nakkiran et al.,, 2020);
another possibility that leads to this phenomenon is to tweak the change
points of the risk curve of the minimum $\ell_{2}$-norm solution by carefully
adding new columns (features) to the design matrix (with either standard
Gaussian or Gaussian mixtures distributions) (Chen et al.,, 2020).
Additionally, this phenomenon might also stem from the regression kernel in
use. For instance, Adlam and Pennington, (2020) derived the high-dimensional
asymptotics for the risk curve when using neural tangent kernels in a two-
layer neural network; Liang et al., (2020) studied the convergence properties
of the minimum kernel-Hilbert norm interpolators under various scaling of
$p=n^{\alpha}$, $\alpha\in(0,1)$, and suggested possible change points (from
ascent to descent) at $\alpha=\frac{1}{l+1/2}$ for every integer $l.$ In
addition, d’Ascoli et al., (2020) empirically observed the multi-descent
phenomenon under the random Fourier feature model.

##### Minimum $\ell_{1}$-norm solutions.

In the over-parametrized regime ($p>n$), the minimum $\ell_{1}$-norm
interpolator considered herein is closely related to the problem of Basis
Pursuit (BP) in the compressed sensing literature (e.g., Chen et al., (2001);
Wojtaszczyk, (2010); Candes and Tao, (2006); Donoho, (2006); Donoho et al.,
(2005)). In particular, the algorithm (4) has been well-established paradigm
for finding a sparse solution to a noiseless linear system. When it comes to
the proportional growth and linear sparsity regime in the noiseless case,
Donoho and Tanner, (2009); Amelunxen et al., (2014) characterized the exact
phase transition boundary regarding the sample size in achieving perfect
recovery. Moving to the noisy scenario, Ju et al., (2020) considered the same
estimator and exhibited a double-descent phenomenon when $p$ is exponentially
larger than $n$. Chinot et al., (2020) studied the setting with $p$ exceeding
the order of $n\log^{1-\beta}(n)$ for some constant $\beta\in(0,1)$, which did
not focus on determining exact pre-constants and the double- or multi-descent
phenomenon. Another recent work Liang and Sur, (2020) studied a drastically
different problem — binary classification, and pinned down exact asymptotics
of the minimum $\ell_{1}$-norm solution when the data are separable, which has
intimate connection to AdaBoost.

##### Exact high-dimensional asymptotics.

The exact asymptotic framework adopted in this work is closely related to the
risk characterization of the Lasso estimator (for positive $\lambda$) that has
been obtained in prior literature. In the proportional growth regime (so that
$p$ and $n$ are comparable), the Lasso risk under i.i.d. Gaussian designs has
been determined by Bayati and Montanari, 2011b ; Stojnic, (2013); Oymak et
al., (2013). In particular, the AMP machinery is a powerful tool for
determining exact asymptotics in this regime, and we postpone further
discussions to Section 3.1. The distributional characterization of the Lasso
has been recently established by Miolane and Montanari, (2018) under the
i.i.d. Gaussian designs, and by Celentano et al., (2020); Bellec and Zhang,
(2019) under general correlated Gaussian designs, where the first two works
were built upon the convex Gaussian min-max theorem. Going beyond the
$\ell_{1}$-penalty, the estimation risk of the robust regression estimators
was pioneered by El Karoui, (2013, 2018); Donoho and Montanari, (2016) and
extensively studied by, e.g., Dobriban and Wager, (2018); Thrampoulidis et
al., (2018); Hastie et al., (2019); Patil et al., (2021).

##### Approximate message passing.

Inspired by statistical physics and information theory literature, AMP was
first proposed as an efficient scheme to solve compressed sensing problems
(Donoho et al.,, 2009). Bayati and Montanari, 2011a ; Javanmard and Montanari,
(2013) then rigorously proved that the dynamics of AMP can be accurately
tracked by a simple small-dimensional recursive formula called the _state
evolution_. This state-evolution characterization made AMP amenable as a
analysis device to describe the statistical behaviors for various problems,
despite that AMP is an effective algorithm on its own. The AMP algorithm and
machinery has been successfully applied to a variety of problems beyond
compressed sensing, including but not limited to robust M-estimators (Donoho
and Montanari,, 2016), SLOPE (Bu et al.,, 2020), low-rank matrix estimation
and PCA (Rangan and Fletcher,, 2012; Montanari and Venkataramanan,, 2021;
Fan,, 2020; Zhong et al.,, 2021), stochastic block models (Deshpande et al.,,
2015), phase retrieval (Ma et al.,, 2018), phase synchronization (Celentano et
al.,, 2021), and generalized linear models (Rangan,, 2011; Sur et al.,, 2019;
Sur and Candès,, 2019; Barbier et al.,, 2019). See Feng et al., (2021) for an
accessible introduction of this machinery and its applications. Moreover, a
dominant fraction of the AMP works focused on high-dimensional asymptotics (so
that the problem dimension tends to infinity first before the number of
iterations), except for Rush and Venkataramanan, (2018) that derived finite-
sample guarantees allowing the number of iterations to grow up to $O(\log
n/\log\log n)$.

###  1.5 Notation

Here, we provide a summary of notation to be used throughout the present
paper. In general, scalars are denoted by lowercase letters, vectors are
represented by boldface lowercase letters, while matrices are denoted by
boldface uppercase letters. For every $q\in[1,\infty]$ and any vector
$\bm{x}\in{}^{p}$, we use
$\|\bm{x}\|_{q}\coloneqq(\sum_{i=1}^{p}|x_{i}|^{q})^{1/q}$ to represent the
$\ell_{q}$-norm of $\bm{x}$, and let $\|\bm{x}\|_{0}$ indicate the number of
non-zero coordinates in $\bm{x}$. We denote by

$\displaystyle\left\langle\bm{x}\right\rangle\coloneqq\frac{1}{p}\sum_{i=1}^{p}x_{i},\quad\text{the
average of the entries of the vector }\bm{x}\in{}^{p}.$

Additionally, let $\sigma_{\min}(\bm{M})$ and $\sigma_{\max}(\bm{M})$ denote
respectively the minimum and the maximum singular values of a matrix $\bm{M}$.
Define $[n]\coloneqq\\{1,\cdots,n\\}$ for an integer $n$.

For two functions $f(\cdot)$ and $g(\cdot)$, we often employ the convenient
notation $f(\delta)\lesssim g(\delta)$ (resp. $f(\delta)\gtrsim g(\delta)$) to
indicate that

$\lim_{\delta\rightarrow\delta_{0}}f(\delta)/g(\delta)\leq 1\qquad\text{(resp.
}\lim_{\delta\rightarrow\delta_{0}}f(\delta)/g(\delta)\geq 1),$

where $\delta_{0}$ is a certain limiting point that will be clear from the
context. We also write $f(\delta)\sim g(\delta)$ when both $f(\delta)\lesssim
g(\delta)$ and $f(\delta)\gtrsim g(\delta)$ hold true. In addition, the soft-
thresholding function is defined as

$\displaystyle\eta(x;\zeta)\coloneqq(|x|-\zeta)_{+}\,\mathsf{sign}(x)$ (5)

for any $x\in\mathbb{R}$ and a given threshold $\zeta\in\mathbb{R}^{+}$, where
$z_{+}\coloneqq\max\\{z,0\\}$. Further, we let $\eta^{\prime}(\cdot;\cdot)$
denote differentiation with respect to the first variable. When a function is
applied to a vector, it should be understood as being applied in a component-
wise manner. Following conventional notation, we denote by $\partial f$ the
sub-differential of a function $f$. When it comes to the $\ell_{1}$-norm
$\|\cdot\|_{1}$, its sub-gradient at the point $\bm{x}\in\mathbb{R}^{p}$ can
be any vector $\bm{v}=[v_{i}]_{1\leq i\leq p}$ satisfying

$\displaystyle\left\\{\begin{matrix}v_{i}=\mathsf{sign}(x_{i}),&\text{if
}x_{i}\neq 0;\\\\[0.56905pt] v_{i}\in[-1,1],&\text{if
}x_{i}=0.\end{matrix}\right.$

Moreover, a function $\psi:\mathbb{R}^{2}\rightarrow\mathbb{R}$ is said to be
pseudo-Lipschitz if there exists a constant $L>0$ such that

$\displaystyle|\psi(x)-\psi(y)|\leq L(1+\|x\|_{2}+\|y\|_{2})\|x-y\|_{2}$ (6)

holds for all $x,y\in\mathbb{R}^{2}$. Additionally, we shall often suppress
a.s. in the notation $\overset{\mathrm{a.s.}}{=}$ for almost sure convergence
if it is clear from the context.

##  2 Risk characterization for the minimum $\ell_{1}$-norm interpolator

###  2.1 Modelling assumptions

For notational simplicity, we shall often adopt the vector and matrix notation
as follows

$\displaystyle\bm{z}\coloneqq[z_{i}]_{1\leq i\leq n}$
$\displaystyle\in\mathbb{R}^{n},\qquad\bm{X}\coloneqq[\bm{x}_{1},\cdots,\bm{x}_{n}]^{\top}\in\mathbb{R}^{n\times
p},$ (7a) $\displaystyle\bm{y}\coloneqq[y_{i}]_{1\leq i\leq
n}=\bm{X}\bm{\theta}^{\star}+\bm{z}\in\mathbb{R}^{n}.$ (7b)

To formalize the problem setting, we first impose the following assumptions on
the sampling process throughout the paper.

  * •

Gaussian design. We study i.i.d. Gaussian design, where each design vector is
independently drawn:

$\bm{x}_{i}\overset{\text{i.i.d.}}{\sim}\mathcal{N}\bigg{(}0,\frac{1}{n}\textbf{I}_{p}\bigg{)},\qquad
1\leq i\leq n.$ (8)

Here, the scaling factor $1/n$ is introduced merely for normalization purpose.
This tractable model is widely adopted when studying the high-dimensional
asymptotics of Lasso (e.g. Bayati and Montanari, 2011b ; Miolane and
Montanari, (2018); Su et al., (2017)) and has been extended to other
statistical learning problems (e.g., Donoho and Montanari, (2016); El Karoui,
(2013); Sur et al., (2019); Thrampoulidis et al., (2018)). While Gaussian
design is typically not satisfied in practice, it allows for useful
mathematical insights that might shed light on practical contexts.

  * •

Gaussian noise. It is assumed that the noise components are independent and
obey

$\displaystyle\bm{z}\sim\mathcal{N}(0,\sigma^{2}\textbf{I}_{n}).$ (9)

Under the above Gaussian design and Gaussian noise model, the generalization
error (2) of an estimator $\widehat{\bm{\theta}}$ should be defined when
$(\bm{x}_{\text{new}},y_{\text{new}})$ is drawn from the same assumption,
i.e.,
$y_{\text{new}}=\langle\bm{x}_{\text{new}},\bm{\theta}^{\star}\rangle+z_{\text{new}}$
with
$\bm{x}_{\text{new}}\sim\mathcal{N}\big{(}0,\frac{1}{n}\textbf{I}_{p}\big{)}$
and $z_{\text{new}}\sim\mathcal{N}(0,\sigma^{2})$. This leads to

$\displaystyle\mathsf{Risk}(\widehat{\bm{\theta}})\coloneqq\mathbb{E}\big{[}(\bm{x}_{\text{new}}^{\top}\widehat{\bm{\theta}}-y_{\text{new}})^{2}\big{]}=\mathbb{E}\big{[}\big{(}\bm{x}_{\text{new}}^{\top}(\widehat{\bm{\theta}}-\bm{\theta}^{\star})\big{)}^{2}\big{]}+\sigma^{2}=\frac{1}{n}\big{\|}\widehat{\bm{\theta}}-\bm{\theta}^{\star}\big{\|}_{2}^{2}+\sigma^{2}.$
(10)

In addition, we shall make assumptions regarding how the ground truth is
generated, as formalized below.

  * •

Linear sparsity. Suppose that each coordinate of
$\bm{\theta}^{\star}=[\theta^{\star}_{i}]_{1\leq i\leq p}$ is identically and
independently drawn as follows

$\theta^{\star}_{i}\overset{\mathrm{i.i.d.}}{\sim}\epsilon\mathcal{P}_{M\sqrt{\delta}}+(1-\epsilon)\mathcal{P}_{0},$
(11)

where $\mathcal{P}_{c}$ denotes the Dirac measure at point $c\in\mathbb{R}$,
and $M>0$ is some given quantity that determines the magnitude of a non-zero
entry. In words, each coordinate is non-zero (and with magnitude
$M\sqrt{\delta}$) with probability $\epsilon$. Here, the scaling factor
$\sqrt{\delta}$ is introduced solely for notational convenience, which ensures
that the _signal-to-noise-ratio_ (SNR) obeys

$\displaystyle\mathrm{SNR}\coloneqq\frac{\mathbb{E}\big{[}(\bm{x}^{\top}\bm{\theta}^{\star})^{2}\big{]}}{\sigma^{2}}=\frac{\epsilon
M^{2}}{\sigma^{2}}.$ (12)

When $\epsilon$ is a fixed constant, the number of non-zero coordinates
concentrates around $\epsilon\cdot p$, meaning that $\epsilon$ determines the
sparsity level of $\bm{\theta}^{\star}$. Noteworthily, a model with linear
sparsity lends itself well to high-dimensional applications with only moderate
degrees of sparsity (for instance, in various problems in genomics, the
relevant signals are observed to be spread out across a good fraction of the
genome (Boyle et al.,, 2017; Tam et al.,, 2019)).

######  Remark 1.

It is worth noting that the linear sparsity regime often precludes consistency
results in both estimation and support recovery, which is in stark contrast to
the regime where the sparsity level is vanishingly small compared to the
sample size (Bickel et al.,, 2009; Wainwright,, 2009; Bühlmann and van de
Geer,, 2011). In fact, results featuring this regime often require an
additional adjustment due to the effect of undersampling, as discussed in El
Karoui et al., (2013).

###  2.2 Risk characterization

In order to depict the shape of the risk curve, we first characterize the
precise asymptotics of
$\mathsf{Risk}(\widehat{\bm{\theta}}^{\mathsf{Int}};\delta)$ with a fixed
aspect ratio $0<\delta<1$. As alluded to previously, this is accomplished by
considering sequences of instances of increasing sizes, along which the
minimum $\ell_{1}$-norm interpolator (cf. (4)) has a non-trivial limiting risk
behavior.

Towards this end, we consider a more general distribution on
$\bm{\theta}^{\star}$ by assuming that

$\displaystyle\text{The empirical distribution of }\bm{\theta}^{\star}\text{
converges weakly to a probability measure }P_{\Theta}.$ (13)

The following theorem determines the exact asymptotics of
$\mathsf{Risk}(\widehat{\bm{\theta}}^{\mathsf{Int}};\delta)$ for any given
$0<\delta<1$.

######  Theorem 2 (Risk of min $\ell_{1}$-norm interpolation).

Consider the linear model (1), and suppose that the assumptions (8), (9) and
(13) hold. Consider any given $0<\delta<1$. If $\mathbb{E}[\Theta^{2}]<\infty$
and $\mathbb{P}(\Theta\neq 0)>0$, then the prediction risk of the minimum
$\ell_{1}$-norm interpolator obeys

$\displaystyle\lim_{\begin{subarray}{c}n/p=\delta\\\
n,\,p\to\infty\end{subarray}}\mathsf{Risk}\big{(}\widehat{\bm{\theta}}^{\mathsf{Int}}\big{)}~{}\overset{\mathrm{a.s.}}{=}~{}{\tau^{\star}}^{2}.$
(14)

Here, $({\tau^{\star}},{\alpha^{\star}})$ stands for the unique solution to
the following system of equations

$\displaystyle\tau^{2}$
$\displaystyle=\sigma^{2}+\frac{1}{\delta}\mathbb{E}\left[\big{(}\eta(\Theta+\tau
Z;\alpha\tau)-\Theta\big{)}^{2}\right],$ (15a) $\displaystyle\delta$
$\displaystyle=\mathbb{P}\big{(}|\Theta+\tau Z|>\alpha\tau\big{)},$ (15b)

where $\Theta\sim P_{\Theta}$, and $Z\sim\mathcal{N}(0,1)$ and is independent
of $\Theta$.

######  Remark 2.

It is noteworthy that Theorem 2 is completely general regarding the
distribution of $\bm{\theta}^{\star}$ as long as its empirical distribution
converges to a fixed measure; in particular, it does not require $\Theta$ to
follow the sparse distribution specified in the expression (11).

First, there exists a unique solution pair to the set of equations (15) as
asserted by Proposition B.1 (see Section B for more details). Experienced
readers who are familiar with literature on Lasso shall immediately recognize
the similarity between these equations and the ones used to determine the
Lasso risk in the proportional regime (Bayati and Montanari, 2011b, ). We
shall elaborate a bit more on their connections and differences in Section
2.3.

We now pause to interpret the above result. The risk of the minimum
$\ell_{1}$-norm interpolator — when the ratio $n/p$ is held fixed — converges
to a quantity ${\tau^{\star}}^{2}$, which is a function of
$(\sigma,\delta,P_{\Theta})$ and can be determined by solving a system of two
nonlinear equations with two unknowns. At a high level, the equation (15a)
indicates that ${\tau^{\star}}>\sigma$, which can be viewed as variance
inflation as a result of undersampling. In addition, ${\tau^{\star}}$ taken
together with the other parameter ${\alpha^{\star}}$ controls the sparsity
level of $\widehat{\bm{\theta}}^{\mathsf{Int}}$. In fact, as can be seen from
the equation (15b) and our analysis, we have

$\displaystyle\lim_{\begin{subarray}{c}n/p=\delta\\\
n,\,p\to\infty\end{subarray}}\frac{1}{p}\|\widehat{\bm{\theta}}^{\mathsf{Int}}\|_{0}~{}\overset{\mathrm{a.s.}}{=}~{}\mathbb{P}\big{(}|\Theta+{\tau^{\star}}Z|>{\alpha^{\star}}{\tau^{\star}}\big{)}=\delta,$

which is essentially saying that the support size of
$\widehat{\bm{\theta}}^{\mathsf{Int}}$ converges to $n$ in the limit. The
proof of Theorem 2 is established via analyzing a sequence of _Approximate
Message Passing_ (AMP) updates with careful choices of parameters, such that
the minimum $\ell_{1}$-norm solution is the fixed point of these updates. The
state evolution formula that characterizes the large $n$ limit for each
iterate is derived, and its large $t$ limit corresponds to the risk of the
minimum $\ell_{1}$-norm solution. The readers are referred to Section 3.1 for
details.

##### Multi-descent phenomenon.

Having obtained an exact characterization of
$\mathsf{Risk}(\widehat{\bm{\theta}}^{\mathsf{Int}})$ in a general manner, we
are ready to specialize Theorem 2 to the ground-truth distribution (11) and
examine how ${\tau^{\star}}$ changes as a function of the aspect ratio
$\delta$. Specifically, if denote $\nu\coloneqq M/\tau$, then the equations
(15) simplify to

$\displaystyle 1$
$\displaystyle=\frac{\nu^{2}}{M^{2}}\sigma^{2}+\frac{\epsilon}{\delta}\mathbb{E}\left[\big{(}\eta(\sqrt{\delta}\nu+Z;\alpha)-\sqrt{\delta}\nu\big{)}^{2}\right]+\frac{1-\epsilon}{\delta}\mathbb{E}\left[\eta^{2}(Z;\alpha)\right]$
(16a) $\displaystyle\delta$
$\displaystyle=\epsilon\mathbb{P}\big{(}|\nu\sqrt{\delta}+Z|>\alpha\big{)}+(1-\epsilon)\mathbb{P}(|Z|>\alpha)$
(16b)

in the presence of the distribution (11). From equation set (16), we can
readily examine how ${\tau^{\star}}$ varies with $\delta$, which is the
content of Section 3.2 (along with the corresponding appendix). In particular,
we can use (16) to demonstrate that: the risk curve undergoes a phase
transition in terms of the sparsity level $\epsilon$ — as summarized in
Theorem 1 — such that the curve transitions from a single descent to multiple
descent in the over-parameterized regime. To the best of our knowledge, this
provides the first theoretical justification for the multiple-descent
phenomenon associated with the minimum $\ell_{1}$-norm interpolator, and might
shed light on understanding the behavior of other interpolators such as the
M-estimators with a general family of objective functions.

##### Comparisons with ridgeless regression.

Hastie et al., (2019) investigated the risk behavior of the ridge estimator
when the penalized parameter $\lambda$ tends to zero — which corresponds to
the minimum $\ell_{2}$-norm interpolator in the over-parameterized regime —
and solidified a double-descent phenomenon as one increases the over-
parameterized ratio $p/n$. To facilitate comparisons to their results, we
first translate the results in Hastie et al., (2019) using our notation.
Specifically, the generalization error of the minimum $\ell_{2}$ interpolator
— denoted by $\widehat{\bm{\theta}}^{\mathsf{Int},\ell_{2}}$ — obeys

$\lim_{\begin{subarray}{c}n/p=\delta\\\
n,\,p\to\infty\end{subarray}}\mathsf{Risk}(\widehat{\bm{\theta}}^{\mathsf{Int},\ell_{2}})~{}\overset{\mathrm{a.s.}}{=}~{}\begin{cases}\frac{\delta}{\delta-1}\sigma^{2},&\text{if
}\delta>1\\\\[5.69046pt] \epsilon
M^{2}(1-\delta)+\frac{1}{1-\delta}\sigma^{2},&\text{if }\delta<1\end{cases}$
(17)

under the model (11). By calculating the derivative of the right-hand side of
(17) w.r.t. $\delta$, one can easily demonstrate that the exact asymptotics of
$\mathsf{Risk}(\widehat{\bm{\theta}}^{\mathsf{Int},\ell_{2}})$ decays
with222Following the convention, we study the relation regarding
$1/\delta=p/n$ instead of $\delta=n/p$. $1/\delta$ when
$\epsilon\leq\sigma^{2}/M^{2}$; otherwise, if $\epsilon>\sigma^{2}/M^{2}$,
then the risk curve undergoes a decreasing phase before hitting the point
associated with $\delta=1-\frac{\sigma}{\sqrt{\epsilon}M}$, and starts to
increase with $1/\delta$ afterward. Next, we single out a few key differences
between their results and ours in Theorem 1.

  * •

The current paper considers the case where the sparsity ratio of
$\bm{\theta}^{\star}$ is held fixed across different random instances of
increasing dimension, with the SNR frozen to be $\epsilon M^{2}/\sigma^{2}$.
The role of over-parametrization is studied when the minimum $\ell_{1}$-norm
estimator (which naturally promotes sparse solutions) is fitted with full
model dimension $p$.

In contrast, Hastie et al., (2019) studied the case where the underlying
signal $\bm{\theta}^{\star}$ has a bounded $\ell_{2}$-norm and potentially
dense.

  * •

Interestingly, Theorem 1 suggests that the minimum $\ell_{1}$-norm
interpolator often exhibits more than two descent, thus revealing a
fundamental difference between these two types of interpolation.

  * •

There exists a convenient closed-form expression for the minimum
$\ell_{2}$-norm interpolator, which assists in characterizing the precise
asymptotics (i.e., one can decompose the risk formula into bias and variance
terms, and pin down each term with the aid of random matrix theory).
Unfortunately, the minimum $\ell_{1}$-norm interpolator does not admit a
concise closed-form expression, thus making it considerably more challenging
to analyze. In light of this, Section 3.2 is devoted to the analysis of the
above-mentioned nonlinear system of equations, with the aim of determining
(local) monotoncity of the corresponding quantities of interest.

###  2.3 Connections to the Lasso estimator

Apparently, the minimum $\ell_{1}$-norm interpolator (4) is closely related to
the classical Lasso estimator studied extensively in high-dimensional
statistics (Tibshirani,, 1996). Given a positive regularization parameter
$\lambda>0$, the Lasso estimates the regression coefficients by solving the
following optimization problem

$\displaystyle\widehat{\bm{\theta}}_{\lambda}\coloneqq\arg\\!\min_{\bm{\theta}\in\mathbb{R}^{p}}\left\\{\frac{1}{2}\left\|\bm{y}-\bm{X}\bm{\theta}\right\|_{2}^{2}+\lambda\left\|\bm{\theta}\right\|_{1}\right\\}.$
(18)

As a consequence, the minimum $\ell_{1}$-norm interpolator corresponds to the
limit of $\widehat{\bm{\theta}}_{\lambda}$ when taking $\lambda$ to zero.

Several prior works have attempted to characterize the exact asymptotics of
the Lasso risk $\mathsf{Risk}(\widehat{\bm{\theta}}_{\lambda})$ in the
proportional regime. Specifically, it has been proven that for any given
$\lambda>0$, $\mathsf{Risk}(\widehat{\bm{\theta}}_{\lambda})$ converges to a
non-trivial limit ${\tau^{\star}}(\lambda)$. Here,
$({\tau^{\star}}(\lambda),\alpha^{*}(\lambda))$ represents the solution pair
to the following set of nonlinear equations

$\displaystyle\tau^{2}$
$\displaystyle=\sigma^{2}+\frac{1}{\delta}\mathbb{E}\left[\big{(}\eta(\Theta+\tau
Z,\alpha\tau)-\Theta\big{)}^{2}\right],$ (19a) $\displaystyle\lambda$
$\displaystyle=\alpha\tau\left(1-\frac{1}{\delta}\mathbb{P}\big{(}|\Theta+\tau
Z|>\alpha\tau\big{)}\right),$ (19b)

where $\Theta\sim P_{\Theta}$ and $Z\sim\mathcal{N}(0,1)$ are independent
random variables. The interested reader can consult Bayati and Montanari,
2011b ; Miolane and Montanari, (2018); Celentano et al., (2020), which
determined the Lasso risk using either the AMP machinery or the convex
Gaussian min-max theorem.

As can be easily seen, the system of equations (19) bears much resemblance to
(15). More precisely, by directly setting $\lambda$ to $0$, the equation set
(19) reduces to the one in (15). In other words, one has

$\displaystyle\lim_{\lambda\to 0}\lim_{\begin{subarray}{c}n/p=\delta\\\
n,p\to\infty\end{subarray}}\mathsf{Risk}(\widehat{\bm{\theta}}_{\lambda})~{}\overset{\mathrm{a.s.}}{=}~{}\lim_{\lambda\to
0}[{\tau^{\star}}(\lambda)]^{2}={\tau^{\star}}^{2}.$ (20)

where ${\tau^{\star}}$ denotes the quantity in Theorem 2, and the last
identity holds under certin continuity assumptions w.r.t. the equations (19).

Intuitively, Theorem 2 can be directly established if it is legitimate to
switch the order of limits between $\lambda$ and $p$ on the left hand side of
expression (20), given that the minimum $\ell_{1}$-norm interpolator is the
limit of the Lasso by taking $\lambda$ to zero. However, formally establishing
the validity of exchanging limits is quite challenging, since doing so
normally requires the loss function being strongly convex (at least locally
strongly convex around the solution point). Such a strong convexity property,
however, is lacking in our problem structure when $\lambda$ is taken to zero.
In fact, this presents a major roadblock to directly applying the established
AMP theory for the Lasso estimator.

Fortunately, we can directly argue that exchanging the two limits leads to the
same result, as formalized in the proposition below. The proof of this result
is postponed to Section A.

######  Proposition 1 (The Lasso limit when $\lambda\rightarrow 0$).

In the setting of Theorem 2, the Lasso risk obeys the following asymptotically
exact characterization:

  1. 1.

When $\delta<1$, the asymptotic Lasso risk converges to the risk of min
$\ell_{1}$-norm interpolator (4):

$\displaystyle\lim_{\lambda\rightarrow
0}\lim_{\begin{subarray}{c}n/p=\delta\\\
n,p\to\infty\end{subarray}}\mathsf{Risk}(\widehat{\bm{\theta}}_{\lambda})~{}\overset{\mathrm{a.s.}}{=}~{}{\tau^{\star}}^{2},$

with ${\tau^{\star}}$ being the solution to the system of equations (15).

  2. 2.

When $\delta>1$, the asymptotic Lasso risk converges to the risk of the
ordinary least-square solution, namely,

$\displaystyle\lim_{\lambda\rightarrow
0}\lim_{\begin{subarray}{c}n/p=\delta\\\
n,p\to\infty\end{subarray}}\mathsf{Risk}(\widehat{\bm{\theta}}_{\lambda})~{}\overset{\mathrm{a.s.}}{=}~{}\frac{\delta}{\delta-1}\sigma^{2}.$

In words, the above result reveals that: while the connection between the set
of equations (19) and the Lasso risk was previously only shown for a positive
$\lambda$, such exact asymptotics continue be valid even in the limit when
$\lambda$ approaches zero.

##  3 Key analysis

This section presents the key ideas for proving our main results. We start by
presenting the proof strategy for Theorem 2, which is built upon the recently
developed approximate message passing machinery. It is then followed by the
proof of Theorem 1 that characterizes the geometric properties of the risk
curve.

###  3.1 Key analysis tool: approximate message passing

The major technical enabler for proving Theorem 2 lies in the recent
development of an iterative algorithm called the _Approximate Message Passing_
(AMP) algorithms. As mentioned previously, Bayati and Montanari, 2011b
employed AMP to pin down the risk of the Lasso estimator with positive
regularization. Motivated by this line of works, this paper resorts to the AMP
technique as a proof device towards understanding the risk behavior of the
minimum $\ell_{1}$-norm interpolators.

For our purpose, we need to generalize the original AMP updates (Bayati and
Montanari, 2011b ) — which were designed to solve a single Lasso problem in
the large-system limit — to approximate a sequence of Lasso problems with
changing (and converging) regularization parameters. To better illustrate this
idea, we shall first provide a brief review of how AMP is invoked to solve a
single Lasso problem, followed by a generalization of this framework to
accommodate the minimum $\ell_{1}$-norm interpolator.

####  3.1.1 AMP for the Lasso estimator

##### AMP updates for Lasso.

Recall that the soft-thresholding function is defined in expression (5) and
$\left\langle\cdot\right\rangle$ denotes the average of the coordinates for
the target vector. When initialized at $\bm{\theta}^{0}=\bm{0}$ and
$\bm{z}^{-1}=\bm{0}$, the AMP algorithm proceeds recursively in the following
fashion

$\displaystyle\bm{\theta}^{t+1}$
$\displaystyle=\eta(\bm{X}^{\top}\bm{z}^{t}+\bm{\theta}^{t};\zeta_{t});$ (21a)
$\displaystyle\bm{z}^{t}$
$\displaystyle=\bm{y}-\bm{X}\bm{\theta}^{t}+\frac{1}{\delta}\bm{z}^{t-1}\left\langle\eta^{\prime}(\bm{X}^{\top}\bm{z}^{t-1}+\bm{\theta}^{t-1};\zeta_{t-1})\right\rangle.$
(21b)

Here, $\\{\zeta_{t}\\}_{t=0}^{\infty}$ is an appropriate sequence of scalars
to be selected. To approximate the Lasso solution with positive $\lambda>0$
(defined in (18)), Bayati and Montanari, 2011b  showed that it suffices to set

$\displaystyle\zeta_{t}={\alpha^{\star}}(\lambda)\cdot\tau_{t}(\lambda),\quad\text{for
all }t\geq 0,$ (22)

where ${\alpha^{\star}}(\lambda)$ is taken as the corresponding solution to
the fixed-point equation (19) and $\tau_{t}(\lambda)$ shall be specified
momentarily. Given this choice of parameters, Bayati and Montanari, 2011b (,
Theorem 1.8) proved that the corresponding AMP update $\bm{\theta}^{t}$
converges to the Lasso solution in the following sense: as long as
$\mathbb{E}[\Theta^{2}]<\infty$ and $\mathbb{P}(\Theta\neq 0)>0$, it holds
that

$\displaystyle\lim_{t\rightarrow\infty}\lim_{\begin{subarray}{c}n/p=\delta\\\
n,p\to\infty\end{subarray}}\frac{1}{p}\|\bm{\theta}^{t}-\widehat{\bm{\theta}}_{\lambda}\|_{2}^{2}~{}\overset{\mathrm{a.s.}}{=}~{}0.$
(23)

We emphasize that this convergence result requires taking the limit of the
model dimensions before taking the limit of the iteration steps; hence, it
should be understood as high-dimensional asymptotics. Equipped with this
result, one is able to study the limiting performance of Lasso via the AMP
iterations at each fixed step $t$; the latter is made possible by the state
evolution characterization to be introduced below.

##### State evolution.

Consider the AMP procedure (21) with an arbitrary sequence of thresholds
$\\{\zeta_{t}\\}>0$. The state evolution sequence
$\\{\tau_{t}^{2}\\}_{t=0}^{\infty}$ is a one-dimensional iteration sequence,
recursively defined for all $t\geq 0$ as follows

$\displaystyle\tau_{t+1}^{2}$
$\displaystyle=\mathsf{F}(\tau_{t}^{2},\zeta_{t})$ (24a)
$\displaystyle\text{where }~{}\mathsf{F}(\tau^{2},\zeta)$
$\displaystyle\coloneqq\sigma^{2}+\frac{1}{\delta}\mathbb{E}\left[\big{[}\eta(\Theta+\tau
Z;\zeta)-\Theta\big{]}^{2}\right]$ (24b)

with initialization $\tau_{0}^{2}=\sigma^{2}+\mathbb{E}[\Theta^{2}]/\delta$.
Here, $\Theta$ is the distribution of the true signal, and
$Z\sim\mathcal{N}(0,1)$ is independent of $\Theta$. The above sequence is
known to characterize the limiting variance of the AMP recursion, as
formalized by the following result.

######  Proposition 2 (Theorem 1.1, Bayati and Montanari, 2011b ).

Consider the linear model (1) and i.i.d. Gaussian design. If
$\mathbb{E}[\Theta^{2}]<\infty$ and $\mathbb{P}(\Theta\neq 0)>0$, then for any
positive sequence $\\{\zeta_{t}\\}$ and any pseudo-Lipschitz function $\psi$,
it holds that

$\displaystyle\lim_{p\rightarrow\infty}\frac{1}{p}\sum_{i=1}^{p}\psi(\theta_{i}^{t+1},\theta^{\star}_{i})~{}\overset{\mathrm{a.s.}}{=}~{}\mathbb{E}\big{[}\psi\big{(}\eta(\Theta+\tau_{t}Z;\zeta_{t}),\Theta\big{)}\big{]},$

where $Z\sim\mathcal{N}(0,1)$ is independent of $\Theta$.

In words, this proposition asserts that the coordinates of
$\bm{X}^{\top}\bm{z}^{t}+\bm{\theta}^{t}$ have roughly the same distribution
as $\Theta+\tau_{t}Z$. Taking $\psi(x,y)=(x-y)^{2}$ and combining this with
the expression (24b) indicate that: the asymptotic risk of the AMP in the
$t$-th iteration is characterized by $\tau_{t}^{2}$. Indeed, the state
evolution $\tau_{t}^{2}$ quantifies how this asymptotic risk evolves with the
iteration count. If we let the iteration number $t$ tend to infinity, then
$\tau_{t}^{2}$ converges to a nonzero limit — i.e., the solution to the system
of equations (19) — which is precisely the limiting risk for the Lasso
estimator by virtue of the property (23).

####  3.1.2 AMP for the minimum $\ell_{1}$-norm interpolator

As discussed above, when AMP adopts the choice of
$\zeta_{t}={\alpha^{\star}}(\lambda)\cdot\tau_{t}(\lambda)$, then in each
iteration, it makes progress towards the Lasso solution in the presence of a
positive regularization parameter $\lambda$. Intuitively, one can run AMP in
an epoch-based manner, and gradually reduce the value of $\lambda$ by taking a
vanishing sequence of $\left\\{\lambda_{t}\right\\}$ and set
$\zeta_{t}={\alpha^{\star}}(\lambda_{t})\cdot\tau_{t}(\lambda_{t})$.
Heuristically, each epoch solves a Lasso problem approximately with parameter
$\lambda_{t}$ and, in the end, one can recover the minimum $\ell_{1}$-norm
interpolator in the limit. Similar heuristics have been pointed out by Donoho
et al., (2010) without a rigorous argument.

It turns out this intuition can be solidified as long as one selects the
sequence $\left\\{\lambda_{t}\right\\}$ appropriately. Let us now describe our
choice of the $\left\\{\lambda_{t}\right\\}$ sequence, and use them to
construct $\left\\{\zeta_{t}\right\\}$ in the AMP updates.

##### Choice of $\\{\zeta_{t}\\}$ in our setting.

Our first step is to construct a positive sequence of
$\left\\{\lambda_{t}\right\\}$ satisfying the following assumption:

######  Assumption 1.

For every $t=1,2,\ldots$, define
$\Lambda_{t}\coloneqq\sum_{s=1}^{t}\lambda_{s}$. We assume that
$\left\\{\lambda_{t}\right\\}_{t=1}^{\infty}$ satisfies the following
conditions:

  * •

$\lim_{t\rightarrow\infty}\lambda_{t}=0$ and
$\lim_{t\rightarrow\infty}\lambda_{t}/\lambda_{t+1}=1$;

  * •

$\sum_{j=t/2}^{t}\lambda_{j}\geq c\log t$ for every constant $c$ and
sufficiently large $t$;

  * •

The following two sequences are summable for every constant $c$,

$\displaystyle\sum_{t=1}^{+\infty}\exp\left\\{-c\Lambda_{t}\right\\}<\infty,\qquad\text{
and }~{}~{}~{}\sum_{t=1}^{+\infty}\sqrt{l_{t}}<\infty,$ (25)
$\displaystyle\text{where
}~{}~{}l_{t}\coloneqq\sum_{s=1}^{t}\big{|}\lambda_{s}-\lambda_{s+1}\big{|}\exp\big{(}-c[\Lambda_{t}-\Lambda_{s}]\big{)}.$

In words, Assumption 1 requires that $\left\\{\lambda_{t}\right\\}$ converges
to $0$, but the convergence rate should be slow enough. We shall provide an
example of $\\{\lambda_{t}\\}$ satisfying this assumption in Section E.1. As
will be made clear from the proof, having $\lambda_{t}\rightarrow 0$
guarantees that the solution to the system of equations converges to the
minimum $\ell_{1}$-norm solution, whereas other conditions ensure that the AMP
iterates do not experience drastic changes in adjacent iterations, such that
the state evolution formula still accurately describe the behavior of their
limit. Specifically, under these other conditions, the difference between the
support sets of consecutive iterates can be properly controlled.

With this choice of $\left\\{\lambda_{t}\right\\}$ sequence, we define a
series of nonlinear systems of equations with two unknowns, indexed by $t$ as
follows:

$\displaystyle\begin{aligned} \tau^{2}&=\mathsf{F}(\tau^{2},\alpha\tau),\\\
\lambda_{t}&=\alpha\tau\left(1-\frac{1}{\delta}\mathbb{E}\big{[}\eta^{\prime}(\Theta+\tau
Z;\alpha\tau)\big{]}\right),\end{aligned}$ (26)

where the function $\mathsf{F}(\cdot,\cdot)$ is specified in expression (24b).
As usual, $Z$ is a standard Gaussian random variable that is independent of
$\Theta$. Recognizing the existence and uniqueness property shown in Section
B, we can guarantee that the equation set (26) yields a unique solution pair,
which shall be denoted by $({\alpha^{\star}_{t}},{\tau^{\star}_{t}})$.
Further, we define the threshold $\zeta_{t}$ for our AMP updates (21) as
follows

$\displaystyle\zeta_{t}\coloneqq{\alpha^{\star}_{t}}\cdot\tau_{t}\qquad\text{for
all }t>0,$ (27)

where $\zeta_{0}\coloneqq 1$ and $\tau_{t}$ corresponds to the state evolution
formula provided in the expression (24a). In view of the correspondence
between the AMP updates and the Lasso estimator, iteration $t$ of our AMP
updates takes a step towards approximating the Lasso estimator with parameter
$\lambda_{t}$. As $\lambda_{t}$ converges to zero, the iteration procedure has
the minimum $\ell_{1}$-norm interpolator as a limiting point. The informal
intuition is illustrated in Figure 4.

Figure 4: Illustration of the AMP updates for the minimum $\ell_{1}$-norm
interpolator. At each step, $\bm{\theta}^{t+1}$ is computed as in the
expression (21a), with $\zeta_{t}$ chosen according to (27). The plateau of
the blue curve stands for all the interpolators that satisfy
$\bm{y}=\bm{X}\bm{\theta}$, among which $\widehat{\bm{\theta}}^{\mathsf{Int}}$
has the smallest $\ell_{1}$-norm. The curves in green stand for the Lasso loss
functions (with parameter $\lambda_{t}$ changing with $t$) where AMP aims to
move towards its minimizer in each $t$.

We are now ready to state our main result on the risk of the min
$\ell_{1}$-norm solution.

######  Theorem 3.

Consider the linear model (1) and i.i.d. Gaussian design. If
$\mathbb{E}[\Theta^{2}]<\infty$ and $\mathbb{P}(\Theta\neq 0)>0$, then for any
pseudo-Lipschitz function $\psi$, one has

$\lim_{p\rightarrow\infty}\frac{1}{p}\sum_{i=1}^{p}\psi(\widehat{\theta}^{\mathsf{Int}}_{i},\theta_{i}^{\star})~{}\overset{\mathrm{a.s.}}{=}~{}\mathbb{E}\big{[}\psi(\eta(\Theta+{\tau^{\star}}Z;{\alpha^{\star}}{\tau^{\star}}),\Theta)\big{]},$
(28)

where $Z\sim\mathcal{N}(0,1)$ is independent of $\Theta$. Here,
$({\alpha^{\star}},{\tau^{\star}})$ is the solution to the following equations

$\tau^{2}=\mathsf{F}(\tau^{2},\alpha\tau);\quad\frac{1}{\delta}\mathbb{E}\big{[}\eta^{\prime}(\Theta+\tau
Z;\alpha\tau)\big{]}=1.$ (29)

We now point out an immediate consequence of Theorem 3. In view of the pseudo-
Lipschitz property of the function $\psi(a,b)=(a-b)^{2}$, we can obtain
Theorem 2 as a corollary, namely, the limiting risk of the minimum
$\ell_{1}$-norm solution obeys

$\displaystyle\lim_{p\rightarrow\infty}\frac{1}{p}\big{\|}\widehat{\bm{\theta}}^{\mathsf{Int}}-\bm{\theta}^{\star}\big{\|}_{2}^{2}~{}\overset{\mathrm{a.s.}}{=}~{}{{\tau^{\star}}}^{2}.$
(30)

This enables us to study the risk curve by examining the equations (29).

##### Proof ideas.

Before proceeding, let us highlight several key challenges and differences in
this part of the proof in comparison to Bayati and Montanari, 2011b . The
complete details are deferred to Section C. As already mentioned, we look at a
sequence of AMP updates, each targeting at solving a Lasso problem with a
different regularization parameter $\lambda_{t}$ that obeys
$\lim_{t\to\infty}\lambda_{t}=0$. In the fixed $\lambda$ scenario, it is known
that even if $p>n$, the loss function around the Lasso estimate enjoys certain
restricted strongly convexity. This is, however, not the case for the minimum
$\ell_{1}$-norm interpolator, whose support size equals $n$; this implies that
the condition number of $\bm{X}^{\top}\bm{X}$ (restricted to the support)
might be very large. Consequently, it calls for the development of a new
structural property tailored to the minimum $\ell_{1}$-norm solution, as we
shall detail in Lemma C.2.

Moreover, for each $\lambda_{t}$, the AMP iterations are contractive towards
different fixed points (i.e., minimizers of different Lasso problems). One
thus needs to investigate how the pesudo-state evolution point
$\tau^{\star}_{t}$ varies with the iteration number $t$. In addition, to
demonstrate that AMP converges to the new system of equations as specified in
(15), at a high level, we construct some distance measure between
$\bm{\theta}^{t+1}$ and $\bm{\theta}^{t}$ so as to guarantee that

$\displaystyle\mathsf{dist}(\bm{\theta}^{t+1},\bm{\theta}^{t})\leq\exp(-\lambda_{t})\cdot\mathsf{dist}(\bm{\theta}^{t},\bm{\theta}^{t-1})+c|\lambda_{t}-\lambda_{t+1}|.$
(31)

In the case of a fixed $\lambda$, the above relation simplifies to
$\mathsf{dist}(\bm{\theta}^{t+1},\bm{\theta}^{t})\leq\exp(-\lambda)\cdot\mathsf{dist}(\bm{\theta}^{t},\bm{\theta}^{t-1}),$
which means that $\mathsf{dist}(\bm{\theta}^{t+1},\bm{\theta}^{t})$ converges
linearly and $\bm{\theta}^{t}$ converges to the corresponding limit. In
contrast, the second term on the right-hand side of (31) reflects the price
one needs to pay when $\lambda_{t}$ varies across iterations. Assumption 1 is
imposed to help ensure that these errors — albeit accumulated over time — stay
bounded.

###  3.2 Analysis ingredients for the risk curve

Thus far, we have demonstrated that the risk curve of the minimum
$\ell_{1}$-norm interpolator can be characterized by the solutions to the
system of equations (15). In order to analyze the shape of the risk curve and
establish Theorem 1, this section takes a close look at the geometric
properties of these solutions. For ease of exposition, let us assume without
loss of generality that $\sigma^{2}=1$ throughout the proof; clearly, having a
different value of $\sigma^{2}$ does not change the shape of the curve as long
as the SNR remains unchanged.

##### Roadmap of the proof.

We start by providing a roadmap of our proof. To begin with, it is challenging
to track the behavior of the solution ${\tau^{\star}}$ directly in the
original form of the equations (15); in fact, ${\tau^{\star}}$ blows up as
$\delta\rightarrow 1$. Hence, we find it more convenient to work with a new
parameter $\nu\coloneqq M/\tau$ (resp. ${\nu^{\star}}\coloneqq
M/{\tau^{\star}}$) that leads to alternative versions of Theorem 1 and (15).
With this change of variables in place, it suffices to study how
${\nu^{\star}}$ behaves as one varies $\delta$. Towards this end, we first
eliminate the parameter $\alpha$ and express $\nu$ purely as a function of
$\delta$. We then proceed to analyze the derivative of ${\nu^{\star}}(\delta)$
using the implicit function theorem, with a special focus on the sign of
${\nu^{\star}}^{\prime}(\delta)$ when $\delta$ is close to $0$ or $1$, as well
as when $\epsilon\rightarrow 0$. As we shall argue momentarily, these steps
suffice in establishing Theorem 1.

##### An equivalent formulation.

As mentioned above, let us denote $\nu\coloneqq M/\tau$, and define two
functions of $(\nu,\delta,\alpha)$ as follows

$\displaystyle F_{1}(\nu,\delta,\alpha)$
$\displaystyle\coloneqq\epsilon\mathbb{P}\left(\big{|}\nu\sqrt{\delta}+Z\big{|}>\alpha\right)+(1-\epsilon)\mathbb{P}\left(\left|Z\right|>\alpha\right)-\delta,$
(32a) $\displaystyle F_{2}(\nu,\delta,\alpha)$
$\displaystyle\coloneqq\frac{\nu^{2}}{M^{2}}-1+\frac{\epsilon}{\delta}\mathbb{E}\left[\big{(}\eta(\sqrt{\delta}\nu+Z;\alpha)-\sqrt{\delta}\nu\big{)}^{2}\right]+\frac{1-\epsilon}{\delta}\mathbb{E}\left[\eta^{2}(Z;\alpha)\right],$
(32b)

where $Z\sim\mathcal{N}(0,1)$ and is independent of $\Theta\sim P_{\Theta}$.
Under our assumptions on $\Theta$ (cf. (11)), solving the equations (15a) and
(15b) can be accomplished by first finding the solutions
$\big{(}{\nu^{\star}}(\delta),{\alpha^{\star}}(\delta)\big{)}$ to

$\displaystyle\begin{cases}F_{1}(\nu,\delta,\alpha)=0,\\\
F_{2}(\nu,\delta,\alpha)=0,\end{cases}$ (33)

and then mapping ${\nu^{\star}}$ back to ${\tau^{\star}}$.

####  3.2.1 Step 1: existence of the mapping ${\nu^{\star}}(\delta)$

We now attempt to eliminate the variable $\alpha$ in (33), and expressing
${\nu^{\star}}$ as a function of $\delta$. For any $\delta\in(0,1)$ and
$\nu>0$, direct computation of the derivative of the function
$F_{1}(\nu,\delta,\alpha)$ yields

$\displaystyle\nabla_{\alpha}F_{1}(\nu,\delta,\alpha)=-\epsilon\left[\phi(\alpha-\sqrt{\delta}\nu)+\phi(\alpha+\sqrt{\delta}\nu)\right]-2(1-\epsilon)\phi(\alpha)<0.$

It is also straightforward to calculate the limiting values

$\displaystyle\lim_{\alpha\rightarrow
0^{+}}F_{1}(\nu,\delta,\alpha)=1-\delta>0;\quad\lim_{\alpha\rightarrow+\infty}F_{1}(\nu,\delta,\alpha)=-\delta<0.$

Based on the above observations, given any $\delta$ and $\nu$, the function
$F_{1}(\nu,\delta,\alpha)$ is monotonically non-increasing in $\alpha$, and
can take both positive and negative values within the interval $(0,\infty)$.
As a result, there exists a mapping from $(\nu,\delta)\to\alpha$ that
satisfies $F_{1}(\nu,\delta,\alpha)=0$; with an abuse of notation, we often
denote this function as $\alpha(\nu,\delta)$. Substitution into the function
$F_{2}$ allows us to define

$F_{3}(\nu,\delta)\coloneqq F_{2}(\nu,\delta,\alpha(\nu,\delta)).$ (34)

Here, the function $F_{3}$ depends solely on the two parameters
$(\nu,\delta).$ Armed with the derivations above, solving (33) comes down to
finding a solution to $F_{3}(\nu,\delta)=0$.

By construction of the function $F_{3}$, we know that the solutions to
$F_{3}(\nu,\delta)=0$ correspond to the solutions to the system of equations
(15). As we shall demonstrate in Proposition B.1, for every $0<\delta<1$,
there exists a unique pair of $(\tau,\alpha)$ satisfying (15); therefore,
$F_{3}(\nu,\delta)=0$ yields a unique solution for every $0<\delta<1$ — which
shall be denoted by ${{\nu^{\star}}}(\delta)$ in the sequel. Correspondingly,
the solution pair for (15) shall be written as
$({\tau^{\star}}(\delta),{\alpha^{\star}}(\delta))$ where
${\alpha^{\star}}(\delta)\coloneqq\alpha({\tau^{\star}}(\delta),\delta)$. We
also note that since both $F_{1}$ and $F_{2}$ are smooth functions with
bounded derivatives w.r.t. all parameters, ${{\nu^{\star}}}^{\prime}(\delta)$
exists and is continuous.

####  3.2.2 Step 2: derivative of ${\nu^{\star}}(\delta)$

With the mapping ${\nu^{\star}}(\delta)$ in place, we can translate Theorem 1
into statements about ${{\nu^{\star}}}^{\prime}(\delta)$. Before doing so,
recall that the risk incurred by using $\bm{\theta}=\bm{0}$ as the estimator
satisfies

$\displaystyle\mathsf{Risk}(\bm{0})=\mathbb{E}\left[(\langle\bm{x}_{i},\,\bm{\theta}^{\star}\rangle+z_{i})^{2}\right]=1+\frac{1}{n}\|\bm{\theta}^{\star}\|_{2}^{2}~{}\overset{\mathrm{a.s.}}{\longrightarrow}~{}1+\epsilon
M^{2}\eqqcolon\tau_{0}^{2}.$ (35)

Let us define the corresponding value of $\nu$ as $\nu_{0}\coloneqq
M/\tau_{0}$. Formally, to prove the first two claims in Theorem 1, it suffices
to establish the following proposition.

######  Proposition 3.

In the setting of Theorem 1, for $\delta\in(0,1)$, ${\nu^{\star}}(\delta)$
satisfies the following properties:

  1. 1.

$\lim_{\delta\rightarrow 0^{+}}{\nu^{\star}}(\delta)=\nu_{0}$;

  2. 2.

There exist two constants $0<\delta_{1},\delta_{2}<1$ such that when
$0<\delta<\delta_{1}$ and $\delta_{2}<\delta<1$,
${{\nu^{\star}}}^{\prime}(\delta)<0$.

Clearly, if Proposition 3 were valid, then the first two claims in Theorem 1
would follow immediately by invoking the change of variables $\tau=M/\nu$. Now
we discuss how to establish this proposition. For notational simplicity, we
use ${\nu^{\star}}$ and ${\alpha^{\star}}$ to denote the unique solution to
(15a) and (15b) for any $\delta\in(0,1)$, which should be understood as
${\nu^{\star}}(\delta)$ and ${\alpha^{\star}}(\delta)$. To begin with,
recognizing the fact that $F_{1}({\nu^{\star}},\delta,{\alpha^{\star}})=0$,
the implicit function theorem implies that

$\displaystyle\nabla_{\nu}\alpha({\nu^{\star}},\delta)=\left.-\frac{\nabla_{\nu}F_{1}(\nu,\delta,\alpha)}{\nabla_{\alpha}F_{1}(\nu,\delta,\alpha)}\right|_{({\nu^{\star}},\delta,{\alpha^{\star}})};\quad\nabla_{\delta}\alpha({\nu^{\star}},\delta)=\left.-\frac{\nabla_{\delta}F_{1}(\nu,\delta,\alpha)}{\nabla_{\alpha}F_{1}(\nu,\delta,\alpha)}\right|_{({\nu^{\star}},\delta,{\alpha^{\star}})}.$
(36)

We are now ready to derive an explicit expression of
${\nu^{\star}}^{\prime}(\delta)$. A little algebra leads to

$\displaystyle{\nu^{\star}}^{\prime}(\delta)=\left.-\frac{\nabla_{\delta}F_{3}(\nu,\delta)}{\nabla_{\nu}F_{3}(\nu,\delta)}\right|_{({\nu^{\star}},\delta)}$
$\displaystyle=\left.-\frac{\nabla_{\delta}F_{2}(\nu,\delta,\alpha)+\nabla_{\delta}\alpha(\nu,\delta)\nabla_{\alpha}F_{2}(\nu,\delta,\alpha)}{\nabla_{\nu}F_{2}(\nu,\delta,\alpha)+\nabla_{\nu}\alpha(\nu,\delta)\nabla_{\alpha}F_{2}(\nu,\delta,\alpha)}\right|_{({\nu^{\star}},\delta,{\alpha^{\star}})}$
$\displaystyle=\left.-\frac{\nabla_{\delta}F_{2}\nabla_{\alpha}F_{1}-\nabla_{\alpha}F_{2}\nabla_{\delta}F_{1}}{\nabla_{\nu}F_{2}\nabla_{\alpha}F_{1}-\nabla_{\alpha}F_{2}\nabla_{\nu}F_{1}}\right|_{({\nu^{\star}},\delta,{\alpha^{\star}})},$
(37)

where the second equality invokes the relation (36). This expression plays a
crucial role in our subsequent analysis in understanding how ${\tau^{\star}}$
changes with $\delta$.

In order to establish Proposition 3, we gather in the following two lemmas
some key facts on the limiting behavior of ${\nu^{\star}}^{\prime}(\delta)$
and ${\nu^{\star}}(\delta)$, when $\delta\rightarrow 0^{+}$ and
$\delta\rightarrow 1^{-}$, respectively. All of these are stated with the
assumptions of Theorem 1 imposed, with the proofs deferred to Section D.1.

######  Lemma 1.

When $\delta\rightarrow 0^{+}$, the numerator and denominator in (3.2.2)
satisfy respectively the following properties

$\displaystyle\nabla_{\delta}F_{2}\nabla_{\alpha}F_{1}-\nabla_{\alpha}F_{2}\nabla_{\delta}F_{1}\sim-2{{\alpha^{\star}}}^{-3},$
(38a)
$\displaystyle\nabla_{\nu}F_{2}\nabla_{\alpha}F_{1}-\nabla_{\alpha}F_{2}\nabla_{\nu}F_{1}\sim-4\nu_{0}^{-1}\phi({\alpha^{\star}}),$
(38b)

where all the partial derivatives of $F_{1}$ and $F_{2}$ are evaluated at the
point $({\nu^{\star}},\delta,{\alpha^{\star}})$. Additionally, it holds that

$\displaystyle\lim_{\delta\rightarrow 0^{+}}{\nu^{\star}}=\nu_{0}.$ (39)

######  Lemma 2.

When $\delta\rightarrow 1^{-}$, it satisfies that

$\lim_{\delta\rightarrow 1^{-}}{{\nu^{\star}}}^{\prime}(\delta)=-\infty.$ (40)

Note that the property (39) in Lemma 1 validates the first claim in
Proposition 3 directly. Therefore, to prove Proposition 3, we are only left
with verifying the second claim in Proposition 3. In view of Lemma 1, it is
guaranteed that as $\delta\rightarrow 0^{+}$, both the denominator and the
numerator in (3.2.2) are negative. By continuity of
${\nu^{\star}}^{\prime}(\delta)$, there exists some $\delta_{1}>0$ such that
when $0<\delta<\delta_{1}$, one has ${\nu^{\star}}^{\prime}(\delta)<0$.
Finally, Lemma 2 immediately suggests that one can find $\delta_{2}>0$ such
that: when $\delta_{2}<\delta<1$, one has ${\nu^{\star}}^{\prime}(\delta)<0$.
Taking these properties collectively concludes the proof of Proposition 3.

####  3.2.3 Step 3: limit behavior for the case with $\epsilon\rightarrow 0$

Finally, let us move on to establishing the third and fourth claims of Theorem
1. Specifically, fixing some $\delta>0$, we shall study how the risk limit
${\tau^{\star}}$ behaves as $\epsilon$ varies, particularly as it tends to
zero. Thus far, we have focused on the case when both $\epsilon$ and $M$ are
regarded as fixed constants while the value of $\delta$ varies; in this case,
the analyses were primarily performed w.r.t. ${\nu^{\star}}^{\prime}(\delta)$,
since studying ${\nu^{\star}}(\delta)$ and ${\nu^{\star}}(\delta)/M$ are
equivalent when $M$ is taken to be a fixed constant. However, in the case when
we fix SNR (namely, $\epsilon M^{2}$) as opposed to $M$, one has
$M\rightarrow\infty$ as $\epsilon\rightarrow 0$, and hence studying
${\nu^{\star}}(\delta)$ and studying ${\nu^{\star}}(\delta)/M$ are no longer
equivalent. As a result, we need to analyze ${\nu^{\star}}(\delta)/M$
directly, that is, to examine the behavior of ${\nu^{\star}}(\delta)/M$ and
${\nu^{\star}}^{\prime}(\delta)/M$ in a fixed-SNR regime as $\epsilon$
approaches zero.

The readers shall also bear in mind that we always focus on the derivative of
the risk of the model (11) with given $(M,\epsilon)$ but varying $\delta$. In
other words, the function ${\nu^{\star}}(\delta):(0,1)\mapsto\mathbb{R}_{+}$
is defined for any given $(M,\epsilon)$, and we do not associate the change of
$(M,\epsilon)$ and the change of $\delta$ together. To emphasize that we now
work with a _fixed_ ratio, we shall use $\delta_{0}$ in place of $\delta$. At
this given ratio $\delta_{0}$, the quantities ${\alpha^{\star}}$ and
${\nu^{\star}}$ are treated as functions of $\epsilon$.

##### Proof for part (d) of Theorem 1.

When $\epsilon\rightarrow 0$, we first make a key observation on the behavior
of $\frac{{\nu^{\star}}^{\prime}(\delta_{0})}{M}$, as summarized in the lemma
below.

######  Lemma 3.

In the setting of Theorem 1, given any fixed SNR$=\epsilon M^{2}$ and
$\delta_{0}\in(0,1)$, the derivative ${\nu^{\star}}^{\prime}$ (with respect to
$\delta$) obeys

$\displaystyle\lim_{\epsilon\rightarrow
0}\frac{{\nu^{\star}}^{\prime}(\delta_{0})}{M}>0.$ (41)

The proof of Lemma 3 contains two main parts, whose details are deferred to
Section D.4. First, letting $\alpha_{0}\coloneqq-\Phi^{-1}(\delta_{0}/2)$ for
this given $\delta_{0}$, we establish the following relation

$\displaystyle{\alpha^{\star}}\rightarrow\alpha_{0};\quad\text{ and
}~{}\frac{{\nu^{\star}}}{M}\rightarrow\sqrt{1-2\delta_{0}^{-1}[-\alpha_{0}\phi(\alpha_{0})+(\alpha_{0}^{2}+1)\Phi(-\alpha_{0})]},$
(42)

as one takes $\epsilon\rightarrow 0$; the details can be found in Section D.4.
It is worth noting that both ${\alpha^{\star}}$ and $\frac{{\nu^{\star}}}{M}$
converge to fixed quantities that are determined only by $\delta_{0}$ in this
limit.

Equipped with these two limiting values, we proceed to consider the numerator
and denominator of $\frac{{\nu^{\star}}^{\prime}}{M}$, with the assistance of
the expression (3.2.2). In fact, one can pin down the limiting orders of these
two parts as follows

$\displaystyle\nabla_{\delta}F_{2}\nabla_{\alpha}F_{1}-\nabla_{\alpha}F_{2}\nabla_{\delta}F_{1}$
$\displaystyle~{}\rightarrow~{}2\delta_{0}^{-2}\phi(\alpha_{0})\left[-2\alpha_{0}\phi(\alpha_{0})+(\alpha_{0}^{2}+1)\delta_{0}\right]-2\delta_{0}^{-1}\left[2\phi(\alpha_{0})-\alpha_{0}\delta_{0}\right],$
(43a) and $\displaystyle
M(\nabla_{\nu}F_{2}\nabla_{\alpha}F_{1}-\nabla_{\alpha}F_{2}\nabla_{\nu}F_{1})$
$\displaystyle~{}\rightarrow~{}-4\phi(\alpha_{0})\sqrt{1-2\delta_{0}^{-1}[-\alpha_{0}\phi(\alpha_{0})+(\alpha_{0}^{2}+1)\Phi(-\alpha_{0})]}.$
(43b)

The details can be found in Step 2 in Section D.4.

Putting these together, we can conclude that

$\displaystyle\lim_{\epsilon\to
0}\frac{{\nu^{\star}}^{\prime}(\delta_{0})}{M}$
$\displaystyle=\frac{2\delta_{0}^{-2}\left[-2\alpha_{0}\phi^{2}(\alpha_{0})+(\alpha_{0}^{2}+1)\delta_{0}\phi(\alpha_{0})-2\delta_{0}\phi(\alpha_{0})+\alpha_{0}\delta_{0}^{2}\right]}{4\phi(\alpha_{0})\sqrt{1-2\delta_{0}^{-1}[-\alpha_{0}\phi(\alpha_{0})+(\alpha_{0}^{2}+1)\Phi(-\alpha_{0})]}}<0,$

where the last inequality follows due to the fact that
$\Phi(-\alpha_{0})=\delta_{0}/2$ and the basic relation

$\displaystyle\Phi(-\alpha_{0})\in\Big{[}\phi(\alpha_{0})\bigg{(}\frac{1}{\alpha_{0}}-\frac{1}{\alpha_{0}^{3}}\bigg{)},~{}\phi(\alpha_{0})\bigg{(}\frac{1}{\alpha_{0}}-\frac{1}{\alpha_{0}^{3}}+\frac{1}{\alpha_{0}^{5}}\bigg{)}\Big{]}.$

In summary, in view of Lemma 3, we can conclude that there exists
$\epsilon^{\star}>0$, depending only on SNR and $\delta_{0}$, such that: when
$\epsilon<\epsilon^{\star}$, one has ${\nu^{\star}}^{\prime}(\delta_{0})/M<0$.
Translating this back to ${\tau^{\star}}=M/{\nu^{\star}}$ ensures the
existence of an $\epsilon^{\star}$ such that: when
$\epsilon<\epsilon^{\star}$, one has ${\tau^{\star}}^{\prime}<0$. We have thus
completed the proof of Part (d) of Theorem 1.

##### Proof of part (c) of Theorem 1.

The idea for proving this result is to find $\delta\in(0,1)$ such that the
value of ${{\tau^{\star}}}^{2}(\delta)$ is strictly below
$\mathsf{Risk}(\bm{0})$. Recognizing that ${{\tau^{\star}}}^{2}(\delta)$
decays to $\mathsf{Risk}(\bm{0})$ as $p/n$ approaches infinity, there must
exist an ascending regime for ${\tau^{\star}}$ as a function of $p/n.$

More concretely, let us view ${\nu^{\star}}/M$ as a function of $\delta$
within the interval $\delta\in(0,1)$. Rewriting the relation (42) ensures that
as $\epsilon\to 0$, one has

$\displaystyle\frac{1}{{\tau^{\star}}(\delta)}=\frac{{\nu^{\star}}(\delta)}{M}\rightarrow\sqrt{\frac{\alpha\phi(\alpha)-\alpha^{2}\Phi(-\alpha)}{\Phi(-\alpha)}}\eqqcolon
H(\delta)\qquad\text{for }~{}\alpha\coloneqq-\Phi^{-1}(\delta/2).$

It can be easily verified that the function $H(\cdot)$ is a continuous and
decreasing function of $\delta$ on $(0,1)$. Additionally, direct calculations
yield

$\displaystyle\lim_{\delta\rightarrow
1^{-}}H(\delta)=0;\qquad\lim_{\delta\rightarrow 0^{+}}H(\delta)=1.$ (44)

As a result, the continuity of $H(\cdot)$ guarantees that there exists
$\delta_{\mathrm{SNR}}>0$ such that

$\displaystyle H(\delta)\coloneqq\lim_{\epsilon\rightarrow
0}\frac{{\nu^{\star}}(\delta)}{M}>\frac{1}{\sqrt{1+\mathrm{SNR}}}=\frac{1}{\sqrt{\mathsf{Risk}(\bm{0})}}\in(0,1),\qquad\text{for
}~{}\delta<\delta_{\mathrm{SNR}},$

where we recall $\mathrm{SNR}\coloneqq\epsilon M^{2}$. In other words,
recognizing the relation ${\tau^{\star}}(\delta)\coloneqq
M/{\nu^{\star}}(\delta)$, we can show the existence of a regime for
$\delta\in(0,1)$ where the $\epsilon$-limit of ${\tau^{\star}}(\delta)$ lies
below $\sqrt{\mathsf{Risk}(\bm{0})}$.

In addition, for any given $(\epsilon,M)$, recall that the limiting value (as
$\delta\rightarrow 0^{+}$) obeys

$\displaystyle\lim_{\delta\rightarrow
0^{+}}\frac{{\nu^{\star}}(\delta)}{M}=\frac{1}{\sqrt{1+\mathrm{SNR}}}.$ (45)

It further implies that for any fixed $\delta_{0}<\delta_{\mathrm{SNR}}$, one
can find a corresponding $\epsilon_{0}$ depending on $\delta_{0}$ such that

$\displaystyle{\tau^{\star}}(\delta_{0})<\lim_{\delta\to
0^{+}}{\tau^{\star}}(\delta)$

holds for every $\epsilon\leq\epsilon_{0}$. Consequently,
${\tau^{\star}}(\delta)$ has an ascending phase w.r.t. $p/n.$ Putting the
above pieces together establishes the claimed result.

##  4 Numerical simulations and discussion

This section conducts numerical experiments to confirm the applicability of
our results in finite samples and non-Gaussian designs. Along the way, we
shall also point out several directions worthy of future investigation.

##### Finite-sample behavior.

Although the theorems obtained in the paper are asymptotic in nature, our
numerical experiments suggest that they are accurate descriptions of the risk
behavior even when $p$ and $n$ are on the order of 10s or 100s. As an
illustration, we plot in Figure 5 two cases when $n=100$ and $n=1000$,
respectively, with $p/n$ varying between $[10^{-2},~{}10^{2}]$. In these
plots, the multi-descent phenomenon already manifests itself in the case when
$n=100$.

Figure 5:  Finite-sample behavior. The data are generated from a linear model
(1) under i.i.d. Gaussian design, where SNR$=4$ and the sparsity level is
$\epsilon=0.05$. The sample size is set as $n=100$ in the left figure, and
$n=1000$ in the right figure. The theoretical curve, computed by solving the
equations (15), is displayed in solid line, where the limits with
$p/n\rightarrow 0$ and $p/n\rightarrow\infty$ are plotted in dotted lines.
Here, both the $x$-axis and the $y$-axis are plotted in logarithmic scale. We
choose $100$ different values of $p/n$ in a way that the $\log(p/n)$’s are
uniformly spaced over $[-2,2]$. For each $p/n$, we generate a random instance,
compute the minimum $\ell_{1}$-norm interpolator and its risk, and repeat this
procedure for $30$ times. We report the average risk and error bar over 30
independent runs.

##### Beyond Gaussian design.

Thus far, our risk characterization focuses on the idealistic case with i.i.d.
Gaussian design matrices. There is no shortage of practical scenarios where
such distributional assumptions are violated. To see whether our prediction
continues to be valid beyond Gaussian design, we carry out several empirical
experiments concerning design matrices that are composed of i.i.d. non-
Gaussian entries. Figure 6 illustrates two cases where the entries are
generated from the Bernoulli distributions and the $t$-distribution with
parameter $3$, respectively. Our theoretical risk characterization remains
fairly accurate in these numerical experiments. This is perhaps not
unexpected, due to a _universality_ phemoneon that has been justified in
multiple other problems with i.i.d. random design (see, e.g., Bayati et al.,
(2015); Oymak and Tropp, (2018); Montanari and Nguyen, (2017); Chen and Lam,
(2021)). These predictions might, however, be completely off when the
covariates are correlated, meaning that the covariance structure of the design
matrix plays a pivotal role in determining the shape of the risk curves.
Leveraging the current effort towards understanding Lasso under correlated
designs (Celentano et al.,, 2020), we conjecture that the risk of the
interpolator is dictated by a more complicated nonlinear system of equations
that reflects the covariance structure. Given that the main message of this
paper is to verify the existence of a multiple-descent phenomenon, we leave
these more general cases to future investigation.

Figure 6:  Experiments for non-Gaussian designs. In these plots, the sample
size is fixed as $n=100$, and the data is drawn from a linear model (1) with
SNR$=4$ and sparsity level $\epsilon=0.05$. The entries of the design matrix
$\sqrt{n}\bm{X}$ are i.i.d. sampled from the $\mathsf{Bernoulli}(0.5)$
distribution for the left plot, and from $t(3)/\sqrt{3}$ distribution for the
right plot (where the $1/\sqrt{3}$ is introduced to make the variance equals
to 1). The other experiment settings are the same with Figure 5.

##### Distributional characterization.

We perform another series of numerical experiments about the minimum
$\ell_{1}$-norm interpolators $\widehat{\bm{\theta}}^{\mathsf{Int}}$ under
i.i.d. Gaussian design, and report in Figure 7 _(i)_ the empirical
distribution of its $p$ coordinates over $30$ independent runs, and _(ii)_ the
empirical distribution of the corresponding
$\widehat{\bm{\theta}}^{\mathsf{Int}}$ coordinates when the underlying
$\theta^{\star}_{i}$ is zero (resp. non-zero). As can be seen from the plots,
the estimates are close to being unbiased, with the estimates for non-zero
entries exhibiting a higher level of uncertainty than the zero entries.
However, how to develop a distributional theory remains unclear. A recent line
of works (Bellec and Zhang,, 2019; Miolane and Montanari,, 2018; Celentano et
al.,, 2020) established distributional guarantees for a debiased Lasso
estimator with positive regularization (so that the estimates after de-biasing
exhibit Gaussian distributions). We conjecture that the analysis framework
(via the convex Gaussian min-max theorem) developed in Miolane and Montanari,
(2018); Celentano et al., (2020) might be useful in establishing a fine-
grained finite-sample distributional characterization for the interpolators of
interest.

Figure 7:  Empirical distribution for coordinates of
$\widehat{\theta}^{\mathsf{Int}}_{i}$. Here, we fix the sample size $n=100$,
and generate data from the linear model (1) with i.i.d. Gaussian design, where
SNR$=4$ and sparsity level $\epsilon=0.05$. The other experiment settings are
the same with Figure 5. We collect the empirical distribution of
$\widehat{\theta}^{\mathsf{Int}}_{i}$’s coordinates (corresponding to those
$i$ such that $\theta^{\star}_{i}\neq 0$ / $\theta^{\star}_{i}=0$ / for every
$i$, respectively) across all repeats, and generate their histograms. In the
top row of the plots, set $p=600$, and in the bottom row, set $p=6000$. All
the results reported are based on $30$ random trials. The empirical averages
and the ground truth $\theta^{\star}_{i}$ values are marked in the dotted
vertical line and the solid vertical line respectively.

## Acknowledgment

The authors would like to thank Linjun Zhang for discussing this open problem
with Y. Wei when she was visiting the statistics department at Rutgers
University in 2020. This work was partially supported by the NSF grants DMS
2147546/2015447 and CCF 2106778. Part of this work was done while Y. Li and Y.
Wei were visiting the Simons Institute for the Theory of Computing.

## References

  * Adlam and Pennington, (2020) Adlam, B. and Pennington, J. (2020).  The neural tangent kernel in high dimensions: Triple descent and a multi-scale theory of generalization.  In International Conference on Machine Learning, pages 74–84. PMLR.
  * Amelunxen et al., (2014) Amelunxen, D., Lotz, M., McCoy, M. B., and Tropp, J. A. (2014).  Living on the edge: Phase transitions in convex programs with random data.  Information and Inference: A Journal of the IMA, 3(3):224–294.
  * Bai and Silverstein, (2010) Bai, Z. and Silverstein, J. W. (2010).  Spectral analysis of large dimensional random matrices, volume 20.  Springer.
  * Barbier et al., (2019) Barbier, J., Krzakala, F., Macris, N., Miolane, L., and Zdeborová, L. (2019).  Optimal errors and phase transitions in high-dimensional generalized linear models.  Proceedings of the National Academy of Sciences, 116(12):5451–5460.
  * Bartlett et al., (2020) Bartlett, P. L., Long, P. M., Lugosi, G., and Tsigler, A. (2020).  Benign overfitting in linear regression.  Proceedings of the National Academy of Sciences, 117(48):30063–30070.
  * Bartlett et al., (2021) Bartlett, P. L., Montanari, A., and Rakhlin, A. (2021).  Deep learning: a statistical viewpoint.  arXiv preprint arXiv:2103.09177.
  * Bayati et al., (2015) Bayati, M., Lelarge, M., and Montanari, A. (2015).  Universality in polytope phase transitions and message passing algorithms.  The Annals of Applied Probability, 25(2):753–822.
  * (8) Bayati, M. and Montanari, A. (2011a).  The dynamics of message passing on dense graphs, with applications to compressed sensing.  IEEE Transactions on Information Theory, 57(2):764–785.
  * (9) Bayati, M. and Montanari, A. (2011b).  The LASSO risk for gaussian matrices.  IEEE Transactions on Information Theory, 58(4):1997–2017.
  * Belkin, (2021) Belkin, M. (2021).  Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation.  arXiv preprint arXiv:2105.14368.
  * Belkin et al., (2019) Belkin, M., Hsu, D., Ma, S., and Mandal, S. (2019).  Reconciling modern machine-learning practice and the classical bias–variance trade-off.  Proceedings of the National Academy of Sciences, 116(32):15849–15854.
  * Belkin et al., (2020) Belkin, M., Hsu, D., and Xu, J. (2020).  Two models of double descent for weak features.  SIAM Journal on Mathematics of Data Science, 2(4):1167–1180.
  * Belkin et al., (2018) Belkin, M., Ma, S., and Mandal, S. (2018).  To understand deep learning we need to understand kernel learning.  In International Conference on Machine Learning, pages 541–549. PMLR.
  * Bellec and Zhang, (2019) Bellec, P. C. and Zhang, C.-H. (2019).  Second order Poincaré inequalities and de-biasing arbitrary convex regularizers when $p/n\to\gamma$.  arXiv preprint arXiv:1912.11943.
  * Bickel et al., (2009) Bickel, P. J., Ritov, Y., and Tsybakov, A. B. (2009).  Simultaneous analysis of Lasso and Dantzig selector.  The Annals of statistics, 37(4):1705–1732.
  * Boyle et al., (2017) Boyle, E. A., Li, Y. I., and Pritchard, J. K. (2017).  An expanded view of complex traits: from polygenic to omnigenic.  Cell, 169(7):1177–1186.
  * Bu et al., (2020) Bu, Z., Klusowski, J. M., Rush, C., and Su, W. J. (2020).  Algorithmic analysis and statistical estimation of SLOPE via approximate message passing.  IEEE Transactions on Information Theory, 67(1):506–537.
  * Bühlmann and van de Geer, (2011) Bühlmann, P. and van de Geer, S. (2011).  Statistics for high-dimensional data: methods, theory and applications.  Springer Science & Business Media.
  * Candes and Tao, (2006) Candes, E. J. and Tao, T. (2006).  Near-optimal signal recovery from random projections: Universal encoding strategies?  IEEE transactions on Information Theory, 52(12):5406–5425.
  * Celentano et al., (2021) Celentano, M., Fan, Z., and Mei, S. (2021).  Local convexity of the TAP free energy and AMP convergence for Z2-synchronization.  arXiv preprint arXiv:2106.11428.
  * Celentano et al., (2020) Celentano, M., Montanari, A., and Wei, Y. (2020).  The Lasso with general Gaussian designs with applications to hypothesis testing.  arXiv preprint arXiv:2007.13716.
  * Chen et al., (2020) Chen, L., Min, Y., Belkin, M., and Karbasi, A. (2020).  Multiple descent: Design your own generalization curve.  arXiv preprint arXiv:2008.01036.
  * Chen et al., (2001) Chen, S. S., Donoho, D. L., and Saunders, M. A. (2001).  Atomic decomposition by basis pursuit.  SIAM review, 43(1):129–159.
  * Chen and Lam, (2021) Chen, W.-K. and Lam, W.-K. (2021).  Universality of approximate message passing algorithms.  Electronic Journal of Probability, 26:1–44.
  * Chen and Dongarra, (2005) Chen, Z. and Dongarra, J. J. (2005).  Condition numbers of gaussian random matrices.  SIAM Journal on Matrix Analysis and Applications, 27(3):603–620.
  * Chinot et al., (2020) Chinot, G., Löffler, M., and van de Geer, S. (2020).  On the robustness of minimum-norm interpolators.  arXiv preprint arXiv:2012.00807.
  * d’Ascoli et al., (2020) d’Ascoli, S., Sagun, L., and Biroli, G. (2020).  Triple descent and the two kinds of overfitting: Where & why do they appear?  arXiv preprint arXiv:2006.03509.
  * Deshpande et al., (2015) Deshpande, Y., Abbe, E., and Montanari, A. (2015).  Asymptotic mutual information for the two-groups stochastic block model.  arXiv preprint arXiv:1507.08685.
  * Dobriban and Wager, (2018) Dobriban, E. and Wager, S. (2018).  High-dimensional asymptotics of prediction: Ridge regression and classification.  The Annals of Statistics, 46(1):247–279.
  * Donoho and Montanari, (2016) Donoho, D. and Montanari, A. (2016).  High dimensional robust m-estimation: Asymptotic variance via approximate message passing.  Probability Theory and Related Fields, 166(3):935–969.
  * Donoho and Tanner, (2009) Donoho, D. and Tanner, J. (2009).  Counting faces of randomly projected polytopes when the projection radically lowers dimension.  Journal of the American Mathematical Society, 22(1):1–53.
  * Donoho, (2006) Donoho, D. L. (2006).  Compressed sensing.  IEEE Transactions on Information Theory, 52(4):1289–1306.
  * Donoho et al., (2005) Donoho, D. L., Elad, M., and Temlyakov, V. N. (2005).  Stable recovery of sparse overcomplete representations in the presence of noise.  IEEE Transactions on Information Theory, 52(1):6–18.
  * Donoho et al., (2009) Donoho, D. L., Maleki, A., and Montanari, A. (2009).  Message-passing algorithms for compressed sensing.  Proceedings of the National Academy of Sciences, 106(45):18914–18919.
  * Donoho et al., (2010) Donoho, D. L., Maleki, A., and Montanari, A. (2010).  Message passing algorithms for compressed sensing: II. Analysis and validation.  In 2010 IEEE Information Theory Workshop on Information Theory (ITW 2010, Cairo), pages 1–5. IEEE.
  * El Karoui, (2013) El Karoui, N. (2013).  Asymptotic behavior of unregularized and ridge-regularized high-dimensional robust regression estimators: rigorous results.  arXiv preprint arXiv:1311.2445.
  * El Karoui, (2018) El Karoui, N. (2018).  On the impact of predictor geometry on the performance on high-dimensional ridge-regularized generalized robust regression estimators.  Probability Theory and Related Fields, 170(1):95–175.
  * El Karoui et al., (2013) El Karoui, N., Bean, D., Bickel, P. J., Lim, C., and Yu, B. (2013).  On robust regression with high-dimensional predictors.  Proceedings of the National Academy of Sciences, 110(36):14557–14562.
  * Fan, (2020) Fan, Z. (2020).  Approximate message passing algorithms for rotationally invariant matrices.  accepted to the Annals of Statistics.
  * Feng et al., (2021) Feng, O. Y., Venkataramanan, R., Rush, C., and Samworth, R. J. (2021).  A unifying tutorial on approximate message passing.  arXiv preprint arXiv:2105.02180.
  * Friedman et al., (2001) Friedman, J., Hastie, T., Tibshirani, R., et al. (2001).  The elements of statistical learning, volume 1.  Springer series in statistics New York.
  * Gunasekar et al., (2018) Gunasekar, S., Woodworth, B., Bhojanapalli, S., Neyshabur, B., and Srebro, N. (2018).  Implicit regularization in matrix factorization.  In 2018 Information Theory and Applications Workshop (ITA), pages 1–10. IEEE.
  * Hastie et al., (2019) Hastie, T., Montanari, A., Rosset, S., and Tibshirani, R. J. (2019).  Surprises in high-dimensional ridgeless least squares interpolation.  arXiv preprint arXiv:1903.08560.
  * Javanmard and Montanari, (2013) Javanmard, A. and Montanari, A. (2013).  State evolution for general approximate message passing algorithms, with applications to spatial coupling.  Information and Inference: A Journal of the IMA, 2(2):115–144.
  * Ju et al., (2020) Ju, P., Lin, X., and Liu, J. (2020).  Overfitting can be harmless for basis pursuit, but only to a degree.  arXiv preprint arXiv:2002.00492.
  * Liang and Rakhlin, (2020) Liang, T. and Rakhlin, A. (2020).  Just interpolate: Kernel “ridgeless” regression can generalize.  The Annals of Statistics, 48(3):1329–1347.
  * Liang et al., (2020) Liang, T., Rakhlin, A., and Zhai, X. (2020).  On the multiple descent of minimum-norm interpolants and restricted lower isometry of kernels.  In Conference on Learning Theory, pages 2683–2711. PMLR.
  * Liang and Sur, (2020) Liang, T. and Sur, P. (2020).  A precise high-dimensional asymptotic theory for boosting and min-l1-norm interpolated classifiers.  arXiv preprint arXiv:2002.01586.
  * Ma et al., (2018) Ma, J., Xu, J., and Maleki, A. (2018).  Optimization-based AMP for phase retrieval: The impact of initialization and $\ell\\_2$-regularization.  arXiv preprint arXiv:1801.01170.
  * Mei and Montanari, (2019) Mei, S. and Montanari, A. (2019).  The generalization error of random features regression: Precise asymptotics and the double descent curve.  Communications on Pure and Applied Mathematics.
  * Miolane and Montanari, (2018) Miolane, L. and Montanari, A. (2018).  The distribution of the Lasso: Uniform control over sparse balls and adaptive parameter tuning.  arXiv preprint arXiv:1811.01212.
  * Mitra, (2019) Mitra, P. P. (2019).  Understanding overfitting peaks in generalization error: Analytical risk curves for $l_{2}$ and $l_{1}$ penalized interpolation.  arXiv preprint arXiv:1906.03667.
  * Montanari and Nguyen, (2017) Montanari, A. and Nguyen, P.-M. (2017).  Universality of the elastic net error.  In 2017 IEEE International Symposium on Information Theory (ISIT), pages 2338–2342. IEEE.
  * Montanari and Venkataramanan, (2021) Montanari, A. and Venkataramanan, R. (2021).  Estimation of low-rank matrices via approximate message passing.  The Annals of Statistics, 49(1):321–345.
  * Muthukumar et al., (2020) Muthukumar, V., Vodrahalli, K., Subramanian, V., and Sahai, A. (2020).  Harmless interpolation of noisy data in regression.  IEEE Journal on Selected Areas in Information Theory, 1(1):67–83.
  * Nakkiran et al., (2019) Nakkiran, P., Kaplun, G., Bansal, Y., Yang, T., Barak, B., and Sutskever, I. (2019).  Deep double descent: Where bigger models and more data hurt.  arXiv preprint arXiv:1912.02292.
  * Nakkiran et al., (2020) Nakkiran, P., Venkat, P., Kakade, S., and Ma, T. (2020).  Optimal regularization can mitigate double descent.  arXiv preprint arXiv:2003.01897.
  * Neyshabur et al., (2014) Neyshabur, B., Tomioka, R., and Srebro, N. (2014).  In search of the real inductive bias: On the role of implicit regularization in deep learning.  arXiv preprint arXiv:1412.6614.
  * Oymak et al., (2013) Oymak, S., Thrampoulidis, C., and Hassibi, B. (2013).  The squared-error of generalized Lasso: A precise analysis.  In 2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1002–1009. IEEE.
  * Oymak and Tropp, (2018) Oymak, S. and Tropp, J. A. (2018).  Universality laws for randomized dimension reduction, with applications.  Information and Inference: A Journal of the IMA, 7(3):337–446.
  * Patil et al., (2021) Patil, P., Wei, Y., Rinaldo, A., and Tibshirani, R. (2021).  Uniform consistency of cross-validation estimators for high-dimensional ridge regression.  In International Conference on Artificial Intelligence and Statistics, pages 3178–3186. PMLR.
  * Rangan, (2011) Rangan, S. (2011).  Generalized approximate message passing for estimation with random linear mixing.  In 2011 IEEE International Symposium on Information Theory Proceedings, pages 2168–2172. IEEE.
  * Rangan and Fletcher, (2012) Rangan, S. and Fletcher, A. K. (2012).  Iterative estimation of constrained rank-one matrices in noise.  In 2012 IEEE International Symposium on Information Theory Proceedings, pages 1246–1250. IEEE.
  * Robbins, (1955) Robbins, H. (1955).  A remark on Stirling’s formula.  The American Mathematical Monthly, 62(1):26–29.
  * Rosset et al., (2004) Rosset, S., Zhu, J., and Hastie, T. (2004).  Boosting as a regularized path to a maximum margin classifier.  The Journal of Machine Learning Research, 5:941–973.
  * Rush and Venkataramanan, (2018) Rush, C. and Venkataramanan, R. (2018).  Finite sample analysis of approximate message passing algorithms.  IEEE Transactions on Information Theory, 64(11):7264–7286.
  * Stojnic, (2013) Stojnic, M. (2013).  A framework to characterize performance of LASSO algorithms.  arXiv preprint arXiv:1303.7291.
  * Su et al., (2017) Su, W., Bogdan, M., and Candes, E. (2017).  False discoveries occur early on the lasso path.  The Annals of statistics, pages 2133–2150.
  * Su and Candes, (2016) Su, W. and Candes, E. (2016).  Slope is adaptive to unknown sparsity and asymptotically minimax.  The Annals of Statistics, 44(3):1038–1068.
  * Sur and Candès, (2019) Sur, P. and Candès, E. J. (2019).  A modern maximum-likelihood theory for high-dimensional logistic regression.  Proceedings of the National Academy of Sciences, 116(29):14516–14525.
  * Sur et al., (2019) Sur, P., Chen, Y., and Candès, E. J. (2019).  The likelihood ratio test in high-dimensional logistic regression is asymptotically a rescaled chi-square.  Probability Theory and Related Fields, 175(1-2):487–558.
  * Tam et al., (2019) Tam, V., Patel, N., Turcotte, M., Bossé, Y., Paré, G., and Meyre, D. (2019).  Benefits and limitations of genome-wide association studies.  Nature Reviews Genetics, 20(8):467–484.
  * Thrampoulidis et al., (2018) Thrampoulidis, C., Abbasi, E., and Hassibi, B. (2018).  Precise error analysis of regularized $m$-estimators in high dimensions.  IEEE Transactions on Information Theory, 64(8):5592–5628.
  * Tibshirani, (1996) Tibshirani, R. (1996).  Regression shrinkage and selection via the lasso.  Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267–288.
  * Viering et al., (2019) Viering, T., Mey, A., and Loog, M. (2019).  Open problem: Monotonicity of learning.  In Conference on Learning Theory, pages 3198–3201. PMLR.
  * Wainwright, (2009) Wainwright, M. J. (2009).  Sharp thresholds for high-dimensional and noisy sparsity recovery using $\ell_{1}$-constrained quadratic programming (lasso).  IEEE transactions on information theory, 55(5):2183–2202.
  * Wei et al., (2019) Wei, Y., Yang, F., and Wainwright, M. J. (2019).  Early stopping for kernel boosting algorithms: A general analysis with localized complexities.  IEEE Transactions on Information Theory, 65(10):6685–6703.
  * Wojtaszczyk, (2010) Wojtaszczyk, P. (2010).  Stability and instance optimality for gaussian measurements in compressed sensing.  Foundations of Computational Mathematics, 10(1):1–13.
  * Wyner et al., (2017) Wyner, A. J., Olson, M., Bleich, J., and Mease, D. (2017).  Explaining the success of adaboost and random forests as interpolating classifiers.  The Journal of Machine Learning Research, 18(1):1558–1590.
  * Zhang et al., (2021) Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, O. (2021).  Understanding deep learning (still) requires rethinking generalization.  Communications of the ACM, 64(3):107–115.
  * Zhong et al., (2021) Zhong, X., Wang, T., and Fan, Z. (2021).  Approximate message passing for orthogonally invariant ensembles: Multivariate non-linearities and spectral initialization.  arXiv preprint arXiv:2110.02318.

APPENDIX

##  Appendix A Proof of Proposition 1

In what follows, we intend to establish the two claims separately.

##### Case I: $n/p>1$.

In this part, we aim to prove that, for any $\delta>1$, the Lasso risk
converges to the risk of the least-square estimator — denoted by
$\widehat{\bm{\theta}}^{\mathsf{LS}}$ — as $\lambda\rightarrow 0$. To begin
with, the risk of $\widehat{\bm{\theta}}^{\mathsf{LS}}$ can be characterized
using standard random matrix theory results; see, for example, Hastie et al.,
(2019, Theorem 1). As $p\rightarrow\infty$, one has

$\displaystyle\mathsf{Risk}(\widehat{\bm{\theta}}^{\mathsf{LS}})=\sigma^{2}+\frac{1}{n}\mathbb{E}\big{[}\|\widehat{\bm{\theta}}^{\mathsf{LS}}-\bm{\theta}^{\star}\|_{2}^{2}\big{]}~{}{\rightarrow}~{}\sigma^{2}\frac{\delta}{\delta-1}.$
(46)

In view of the KKT condition for the corresponding loss functions, we can see
that the Lasso and the least-square estimator obey

$\displaystyle\widehat{\bm{\theta}}_{\lambda}-\bm{\theta}^{\star}=(\bm{X}^{\top}\bm{X})^{-1}(\bm{X}^{\top}\bm{z}-\lambda\bm{s})\qquad\text{and}\qquad\widehat{\bm{\theta}}^{\mathsf{LS}}-\bm{\theta}^{\star}=(\bm{X}^{\top}\bm{X})^{-1}\bm{X}^{\top}\bm{z}.$

Here, $\bm{s}=[s_{j}]_{1\leq j\leq p}$ denotes the sub-gradient of the
$\ell_{1}$ norm at point $\widehat{\bm{\theta}}_{\lambda}$, which obeys
$s_{j}\in\left[-1,1\right]$. Thus, the risk of the Lasso satisfies

$\displaystyle\mathbb{E}\big{[}\|\widehat{\bm{\theta}}_{\lambda}-\bm{\theta}^{\star}\|_{2}^{2}\big{]}=\mathbb{E}\big{[}\|\widehat{\bm{\theta}}^{\mathsf{LS}}-\bm{\theta}^{\star}\|_{2}^{2}\big{]}-2\lambda\mathbb{E}\big{[}\langle(\bm{X}^{\top}\bm{X})^{-2}\bm{X}^{\top}\bm{z},\,\bm{s}\rangle\big{]}+\lambda^{2}\mathbb{E}\big{[}\|(\bm{X}^{\top}\bm{X})^{-1}\bm{s}\|_{2}^{2}\big{]},$

which combined with the Cauchy-Schwarz inequality further leads to

$\displaystyle\
\left|\frac{1}{n}\mathbb{E}[\|\widehat{\bm{\theta}}_{\lambda}-\bm{\theta}^{\star}\|_{2}^{2}]-\frac{1}{n}\mathbb{E}[\|\widehat{\bm{\theta}}^{\mathsf{LS}}-\bm{\theta}^{\star}\|_{2}^{2}]\right|$
$\displaystyle\leq$ $\displaystyle\
2\lambda\sqrt{\frac{1}{n}\mathbb{E}\left[\left\|(\bm{X}^{\top}\bm{X})^{-1}\bm{X}^{\top}\bm{z}\right\|_{2}^{2}\right]}\sqrt{\frac{1}{n}\mathbb{E}\big{[}\|(\bm{X}^{\top}\bm{X})^{-1}\|_{2}^{2}\|\bm{s}\|_{2}^{2}\big{]}}+\lambda^{2}\frac{1}{n}\mathbb{E}\left[\|(\bm{X}^{\top}\bm{X})^{-1}\|_{2}^{2}\|\bm{s}\|_{2}^{2}\right]$
$\displaystyle\leq$ $\displaystyle\
2\lambda\sqrt{\mathsf{Risk}(\widehat{\bm{\theta}}^{\mathsf{LS}})-\sigma^{2}}\sqrt{\mathbb{E}\left[\frac{1}{\delta}\sigma_{\min}^{-4}(\bm{X})\right]}+\frac{\lambda^{2}}{\delta}\mathbb{E}\left[\sigma_{\min}^{-4}(\bm{X})\right].$
(47)

Now it is sufficient to control the two terms on the right-hand side above,
and show that both terms converge to $0$ when $p\rightarrow\infty.$ First, it
has been shown in the proof of Chen and Dongarra, (2005, Lemma 4.1) that

$\mathbb{P}\left(\sigma_{\min}(\bm{X})\leq\frac{\sqrt{n}}{x^{2}}\right)<\frac{n^{n-p+1}}{(n-p+1)!}\frac{1}{x^{n-p+1}}\leq\left(\frac{e}{x}\right)^{n-p+1}$

for any $x>0$, where the last inequality comes from the well-known Stirling
inequality $\sqrt{2\pi}m^{m+\frac{1}{2}}e^{-m}\leq m!$ (Robbins,, 1955).
Consequently,

$\displaystyle\mathbb{E}\left[\sigma_{\min}^{-4}(\bm{X})\right]$
$\displaystyle\leq\bigg{(}\frac{2}{1-1/\sqrt{\delta}}\bigg{)}^{4}\mathbb{P}\left\\{\sigma_{\min}^{-1}(\bm{X})\leq\frac{2}{1-1/\sqrt{\delta}}\right\\}+{\displaystyle\int}_{\big{(}\frac{2}{1-1/\sqrt{\delta}}\big{)}^{4}}^{\infty}\mathbb{P}\left\\{\sigma_{\min}^{-4}(\bm{X})>z\right\\}\mathrm{d}z$
$\displaystyle\leq
2\bigg{(}\frac{2}{1-1/\sqrt{\delta}}\bigg{)}^{4}+{\displaystyle\int}_{\big{(}\frac{2}{1-1/\sqrt{\delta}}\big{)}^{4}}^{\infty}\mathbb{P}\left\\{\sigma_{\min}(\bm{X})<\frac{1}{z^{1/4}}\right\\}\mathrm{d}z$
$\displaystyle\leq
2\bigg{(}\frac{2}{1-1/\sqrt{\delta}}\bigg{)}^{4}+{\displaystyle\int}_{\big{(}\frac{2}{1-1/\sqrt{\delta}}\big{)}^{4}}^{\infty}\left(\frac{e}{z^{1/8}n^{1/4}}\right)^{n-p+1}\mathrm{d}z$
$\displaystyle\leq 4\bigg{(}\frac{2}{1-1/\sqrt{\delta}}\bigg{)}^{4}$

for sufficiently large $n$. In addition, by virtue of (46), it is guaranteed
that

$\displaystyle\sqrt{\mathsf{Risk}(\widehat{\bm{\theta}}^{\mathsf{LS}})-\sigma^{2}}\rightarrow\sqrt{\frac{\sigma^{2}}{\delta-1}}.$

Substitution into (47) yields

$\displaystyle\lim_{\lambda\rightarrow
0}\lim_{n\rightarrow\infty}\frac{1}{n}\mathbb{E}[\|\widehat{\bm{\theta}}_{\lambda}-\bm{\theta}^{\star}\|_{2}^{2}]=\lim_{n\rightarrow\infty}\frac{1}{n}\mathbb{E}\big{[}\|\widehat{\bm{\theta}}^{\mathsf{LS}}-\bm{\theta}^{\star}\|_{2}^{2}\big{]}$

for any $0<\delta<1$ that is strictly bounded away from $1$.

##### Case II: $n/p<1$.

When $\delta<1$, our goal is to demonstrate that

$\lim_{\lambda\rightarrow
0}\lim_{p\rightarrow\infty}\mathsf{Risk}(\widehat{\bm{\theta}}_{\lambda})=\lim_{p\rightarrow\infty}\mathsf{Risk}(\widehat{\bm{\theta}}^{\mathsf{Int}}).$

To this end, let us first state one known result about
$\mathsf{Risk}(\widehat{\bm{\theta}}_{\lambda})$. Specifically, the lemma
below associates the Lasso risk with the solution to the system of equations
(19a) and (19b).

######  Lemma A.1 (Corollary 1.6 in Bayati and Montanari, 2011b ).

The system of equations (19) admits one unique solution pair
$({\tau^{\star}}(\lambda),{\alpha^{\star}}(\lambda))$. With the Lasso problem
formulated in (18), it holds that

$\displaystyle\lim_{p\rightarrow\infty}\mathsf{Risk}(\widehat{\bm{\theta}}_{\lambda})=\big{(}{{\tau^{\star}}(\lambda)}\big{)}^{2},$

as long as $\mathbb{P}(\bm{\theta}^{\star}\neq\bm{0})>0$.

In view of Theorem 2, it is guaranteed that

$\displaystyle\lim_{p\rightarrow\infty}\mathsf{Risk}(\widehat{\bm{\theta}}^{\mathsf{Int}})={{\tau^{\star}}}^{2}.$

Therefore, to obtain the desired conclusion, it suffices to show that
$\lim_{\lambda\rightarrow 0}{\tau^{\star}}(\lambda)={\tau^{\star}}$, where
${\tau^{\star}}(\lambda),$ and ${\tau^{\star}}$ correspond to the solution to
a different set of equations respectively. Equivalently, for any converging
sequence $\left\\{\lambda_{t}\right\\}_{t=1}^{+\infty}$ with $\lambda_{t}>0$
and $\lambda_{t}\rightarrow 0$, denote the corresponding
$(\tau^{\star}(\lambda_{t}),\alpha^{\star}(\lambda_{t}))$ sequence as
$\left\\{(\tau^{\star}_{t},\alpha^{\star}_{t})\right\\}$. We now aim to show
that the $\lim_{t\rightarrow\infty}\tau^{\star}_{t}=\tau^{\star}$.

In order to achieve this goal, we make two useful observations. First, as will
be demonstrated in Lemma B.1(1), we know that as $\lambda_{t}\rightarrow 0$,
$\left\\{\alpha^{\star}_{t}\right\\}$ is a non-increasing sequence and is
lower bounded by $\alpha_{\min}(\delta)$. Therefore,
$\left\\{\alpha^{\star}_{t}\right\\}$ has a finite and positive limit; we
shall denote this limit by $\alpha^{\star}_{\infty}$. In addition, applying
Lemma B.1(2) ensures that
$\left\\{\tau^{\star}_{t}=\tau_{*}(\alpha^{\star}_{t})\right\\}$ converges; we
shall denote the limiting value by $\tau^{\star}_{\infty}$. Consequently,
taking $t\rightarrow\infty$ on both sides of

$\displaystyle\lambda_{t}=\alpha^{\star}_{t}\tau^{\star}_{t}\left(1-\frac{1}{\delta}\mathbb{E}\left[\eta^{\prime}(\Theta+\tau^{\star}_{t}Z;\alpha^{\star}_{t}\tau^{\star}_{t})\right]\right),$

(note that the right-hand side is continuously differentiable with respect to
both parameters) leads to the observation that
$(\alpha^{\star}_{\infty},\tau^{\star}_{\infty})$ yields
$\delta=\mathbb{P}\left(|\Theta+\tau^{\star}_{\infty}Z|>\alpha^{\star}_{\infty}\tau^{\star}_{\infty}\right)$,
thus solving the equation (15b). Similarly, one can show that
$(\alpha^{\star}_{\infty},\tau^{\star}_{\infty})$ solves the equation (15a).

Putting these pieces together and using the uniqueness of the solution to
(15a) and (15b), we arrive that
$\lim_{t\rightarrow\infty}\tau^{\star}_{t}=\tau^{\star}_{\infty}=\tau^{\star}$.
We have thus established the advertised property.

##  Appendix B Properties of the state evolution parameters

In this section, we collect some results about the state evolution parameters
$\left\\{{\alpha^{\star}_{t}},{\tau^{\star}_{t}},\tau_{t}\right\\}_{t=1}^{\infty}$.
We remind the readers that $\tau_{t}$ is the state evolution in the $t$-th
iteration, while
$({\alpha^{\star}_{t}},{\tau^{\star}_{t}})=({\alpha^{\star}}(\lambda_{t}),{\tau^{\star}}(\lambda_{t}))$
represents the fixed point of the state evolution recursion with
$\lambda_{t}$.

###  B.1 Main results

We first make note of several useful results about the solutions to the
equations (19a) and (19b), which have been proved in Bayati and Montanari,
2011b . Before proceeding, first recall the following mapping
$\mathsf{F}(\tau^{2},\zeta)$ previously introduced in (21b):

$\displaystyle\mathsf{F}(\tau^{2},\zeta)=\sigma^{2}+\frac{1}{\delta}\mathbb{E}\left\\{\big{[}\eta(\Theta+\tau
Z;\zeta)-\Theta\big{]}^{2}\right\\},$

where $Z\sim\mathcal{N}(0,1)$ is independent of $\Theta$. We also recall that
$\alpha_{\min}=\alpha_{\min}(\delta)$ corresponds to the non-negative solution
of the equation

$\displaystyle(1+\alpha^{2})\Phi(-\alpha)-\alpha\phi(\alpha)=\frac{\delta}{2}.$

We now record the following properties.

######  Lemma B.1 (Proposition 1.3, Proposition 1.4, Corollary 1.7 in Bayati
and Montanari, 2011b ).

The solution to the equations (19a) and (19b) obeys

  1. 1.

For any $\alpha>\alpha_{\min}(\delta)$, the first equation
$\tau^{2}=\mathsf{F}(\tau^{2},\alpha\tau)$ admits a unique solution; denote
this solution as ${\tau^{\star}}={\tau^{\star}}(\alpha)$. Additionally we know
that $\alpha\mapsto{\tau^{\star}}(\alpha)$ is continuously differentiable on
$(\alpha_{\min}(\delta),+\infty)$.

  2. 2.

For any $\lambda>0$, there exists one unique $\alpha>0$ satisfying (19a) and
(19b) with $\alpha>\alpha_{\min}(\delta)$, and the mapping from $\lambda>0$ to
$\alpha$ is continuous, differentiable and non-decreasing. Its inverse mapping

$\displaystyle\lambda(\alpha)\coloneqq\alpha\tau^{\star}(\alpha)\left[1-\frac{1}{\delta}\mathbb{E}\left\\{\eta^{\prime}(\Theta+\tau^{\star}(\alpha)Z;\alpha\tau^{\star}(\alpha))\right\\}\right]$
(48)

is continuous and differentiable on $(\alpha_{\min}(\delta),+\infty)$, with
$\lambda(\alpha_{\min}(\delta)+)=-\infty$ and
$\lim_{\alpha\rightarrow\infty}\lambda(\alpha)=+\infty$.

  3. 3.

Combining 1 and 2, we can see that for any $\lambda>0$, there is a unique pair
$({\alpha^{\star}}(\lambda),{\tau^{\star}}(\lambda))$ that solves (19a) and
(19b).

Through careful investigations about the constructed mappings
${\tau^{\star}}(\alpha)$ and ${\alpha^{\star}}(\lambda)$ for every
$\lambda>0$, we establish the existence and uniqueness of the solution to the
equations (15a) and (15b). The proof of this result is provided in Section
B.2.

######  Proposition B.1 (Uniqueness of the solution).

When $\mathbb{P}(\Theta\neq 0)>0$, there exists one unique pair
$({\alpha^{\star}},{\tau^{\star}})$ with
${\alpha^{\star}}>\alpha_{\min}(\delta)$ that satisfies (15a) and (15b).

It turns out that both ${\tau^{\star}}(\alpha)$ and
${\alpha^{\star}}(\lambda)$ are Lipschitz functions of $\lambda$, which can be
rigorized in the following proposition. The proof of this result can be found
in Section B.2.

######  Proposition B.2 (Convergence of ${\alpha^{\star}_{t}}$ and
${\tau^{\star}_{t}}$).

The following properties hold for the solutions to the equation set (26) as
$t\rightarrow\infty$.

  1. 1.

${\alpha^{\star}_{t}}\rightarrow{\alpha^{\star}}$,
${\tau^{\star}_{t}}\rightarrow{\tau^{\star}}$; the sequence
$\left\\{{\alpha^{\star}_{t}}\right\\}$ increases monotonically with $t$ when
$t$ is large enough.

  2. 2.

The function $\alpha^{\star}(\lambda)$ is continuously differentiable w.r.t.
$\lambda$, and there exist some constants $c$ and $C$ determined by $\Theta$,
$\sigma$ and $\delta$, such that $c\leq{\alpha^{\star}}^{\prime}(0)\leq C$; as
such, we can find some $L_{\alpha}$ determined by $\Theta$, $\sigma$ and
$\delta$, such that

$\displaystyle|{\alpha^{\star}_{t}}-\alpha^{\star}_{t+1}|\leq
L_{\alpha}|\lambda_{t}-\lambda_{t+1}|.$

  3. 3.

The function ${\tau^{\star}}(\lambda)$ is Lipschitz w.r.t. $\lambda$ for some
$L_{\tau}$ determined by $\Theta$, $\sigma$ and $\delta$; in particular,

$\displaystyle|{\tau^{\star}_{t}}-\tau^{\star}_{t+1}|\leq
L_{\tau}|\lambda_{t}-\lambda_{t+1}|.$

As a direct consequence of the third claim above, for every $t\geq 1$, one has

$\displaystyle{\tau^{\star}_{t}}\leq{\tau^{\star}}+L_{\tau}\max_{i}\lambda_{i}\eqqcolon\tau_{\max}^{\star};\quad{\alpha^{\star}_{t}}\leq{\alpha^{\star}}+L_{\alpha}\max_{i}\lambda_{i}=:\alpha_{\max}^{\star}.$

Finally, we can demonstrate that: the state evolution sequence $\tau_{t}$
(defined in (24)) approaches the solution of the equations (15a) and (15b) as
$t\rightarrow\infty$. The proof is deferred to Section B.3.

######  Proposition B.3 (Convergence of the state evolution).

The state evolution sequence obeys $\tau_{t}\rightarrow{\tau^{\star}}$ as
$t\rightarrow\infty$.

###  B.2 Proof of Proposition B.1 and Proposition B.2

To begin with, we introduce the following result on the derivatives of
$\lambda^{\prime}(\alpha)$ and ${\tau^{\star}}^{\prime}(\alpha)$, whose proof
is provided in Section B.2.1.

######  Lemma B.2.

For any $\alpha_{0}>\alpha_{\min}(\delta)$ with $\lambda(\alpha_{0})=0$ (cf.
(48)), we have

$\displaystyle 0<C_{1}<\lambda^{\prime}(\alpha_{0})<C_{2};$ (49)
$\displaystyle{\tau^{\star}}^{\prime}(\alpha_{0})\leq C_{3}.$ (50)

Here, $C_{1},C_{2},C_{3}$ are constants that depend only on
$\alpha_{0},\delta$ and $\Theta$.

We are ready to prove Proposition B.1 and Proposition B.2 with the assistance
of Lemma B.2.

##### Proof of Proposition B.1.

Consider the function $\lambda(\alpha)$ defined in (48). Suppose there exist
two different $\alpha_{0}\neq\alpha_{0}^{\prime}$ where
$\lambda(\alpha_{0})=\lambda(\alpha_{0}^{\prime})=0$; by Lemma B.2, we know
$\lambda^{\prime}(\alpha_{0})$ and $\lambda^{\prime}(\alpha_{0}^{\prime})$ are
both positive and bounded away from $0$. Thus, in view of the continuity of
$\lambda(\cdot)$, there must exist some $\lambda_{0}>0$ such that
$\lambda(\alpha)=\lambda_{0}$ has at least two solutions. This, however,
contradicts Lemma B.1(2).

##### Proof of Proposition B.2.

We consider each claim separately. For the first claim, by virtue of the
second statement in Lemma B.1, the mapping $\alpha\mapsto\lambda(\alpha)$ is
continuous and differentiable on $(\alpha_{\min},+\infty)$, and for any
$\lambda\geq 0$, the solution of $\lambda(\alpha)=\lambda$ exists and is
unique. As such, the inverse mapping $\lambda\mapsto{\alpha^{\star}}(\lambda)$
is well-defined on $\lambda\geq 0$ and is continuous. Then we can see that
${\alpha^{\star}_{t}}\to{\alpha^{\star}}$. Moreover, recognizing that
${\tau^{\star}_{t}}={\tau^{\star}}({\alpha^{\star}_{t}})$ and
${\tau^{\star}}={\tau^{\star}}({\alpha^{\star}})$ and using the continuously
differentiable mapping $\alpha\mapsto{\tau^{\star}}(\alpha)$ defined in Lemma
B.1(1), we conclude that ${\tau^{\star}_{t}}\to{\tau^{\star}}$. Lastly, in
light of inequality (49), when $\lambda_{t}\neq\lambda_{t+1}$ we have

$\displaystyle\frac{{\alpha^{\star}_{t}}-\alpha^{\star}_{t+1}}{\lambda_{t}-\lambda_{t+1}}\to{\alpha^{\star}}^{\prime}(0)\geq\frac{1}{C_{1}}.$

We can thus conclude that ${\alpha^{\star}_{t}}$ is monotonously increasing
when $t$ is large enough.

We now turn to the second claim. As ensured by Proposition B.1, there exists
one unique solution to $\lambda(\alpha_{0})$; therefore, the expression (49)
translates to

$\displaystyle 0<C_{1}<\lambda^{\prime}({\alpha^{\star}})<C_{2},$

or equivalently, $C_{2}^{-1}<{\alpha^{\star}}^{\prime}(0)<C_{1}^{-1}$. We have
thus finished the proof of the second claim.

The third claim follows directly from the second claim and the bound (50), and
the proof of Proposition B.1 is completed. Finally, we make the remark that
$L_{\tau}$ and $L_{\alpha}$ depend on $C_{1},C_{2}$ and $C_{3}$ from Lemma
B.2; from Proposition B.1, we know that $\alpha_{0}={\alpha^{\star}}$ is the
unique value of $\alpha_{0}$ satisfying Proposition B.1. Therefore, the
expressions (55) (56)(58) and (57) with $\alpha_{0}={\alpha^{\star}}$ and
${\tau^{\star}}(\alpha_{0})={\tau^{\star}}$ give us the explicit from of
$L_{\tau}$ and $L_{\alpha}$ in terms of ${\alpha^{\star}}$ and
${\tau^{\star}}$.

####  B.2.1 Proof of Lemma B.2

We first make note of an inequality proved in (Miolane and Montanari,, 2018,
Lemma A.5) as follows:

$\displaystyle{\tau^{\star}}^{\prime}(\alpha_{0})\leq(\alpha_{0}+1)\frac{{\tau^{\star}}^{3}(\alpha_{0})}{\delta\sigma^{2}}=:C_{3}.$
(51)

which validates the inequality (50).

It then suffices to establish the first inequality. Towards this, let us first
derive the explicit expressions for the derivative, and prove the upper and
lower bounds. For any $\alpha>\alpha_{\min}(\delta)$, define
$\Xi\coloneqq\Theta/\tau^{\star}(\alpha)$, and the following quantities:

$\displaystyle
E_{1}\coloneqq\mathbb{E}\left[\Phi(-\Xi-\alpha)+\Phi(\Xi-\alpha)\right],\quad
E_{2}\coloneqq\mathbb{E}\left[\Xi\phi(-\Xi-\alpha)-\Xi\phi(\Xi-\alpha)\right],$
$\displaystyle
E_{3}\coloneqq\mathbb{E}\left[\phi(-\Xi-\alpha)+\phi(\Xi-\alpha)\right],\quad
E_{4}\coloneqq\mathbb{E}\left[\Xi^{2}\left[\Phi(\alpha-\Xi)-\Phi(-\alpha-\Xi)\right]\right].$

It is easily seen that $E_{1},E_{2},E_{3}$ and $E_{4}$ are continuous and
differentiable with respect to $\alpha$.

##### Explicit expression for the derivatives at $\alpha=\alpha_{0}$.

Let us first derive ${\tau^{\star}}^{\prime}(\alpha)$ with
${\tau^{\star}}(\alpha)$ defined in Lemma B.1(1). Recall the definition
$\mathsf{F}(\tau^{2},\zeta)=\sigma^{2}+\frac{1}{\delta}\mathbb{E}\left\\{\left[\eta(\Theta+\tau
Z;\zeta)-\Theta\right]^{2}\right\\}$; direct calculations yield

$\displaystyle\frac{\partial\mathsf{F}}{\partial\alpha}(\tau^{2},\tau\alpha)=$
$\displaystyle\frac{2{\tau^{\star}(\alpha)}^{2}}{\delta}\left\\{\alpha\mathbb{E}\left[\Phi(\Xi-\alpha)+\Phi(-\Xi-\alpha)\right]-\mathbb{E}\left[\phi(\Xi-\alpha)+\phi(-\Xi-\alpha)\right]\right\\}=\frac{2{\tau^{\star}(\alpha)}^{2}}{\delta}\left[\alpha
E_{1}-E_{3}\right];$
$\displaystyle\frac{\partial\mathsf{F}}{\partial\tau}(\tau^{2},\tau\alpha)=$
$\displaystyle\frac{2\tau^{\star}(\alpha)}{\delta}\left\\{(1+\alpha^{2})\mathbb{E}\left[\Phi(\Xi-\alpha)+\Phi(-\Xi-\alpha)\right]-\mathbb{E}\left[(\Xi+\alpha)\phi(\Xi-\alpha)-(\Xi-\alpha)\phi(-\Xi-\alpha)\right]\right\\}$
$\displaystyle=$
$\displaystyle\frac{2\tau^{\star}(\alpha)}{\delta}\left[(1+\alpha^{2})E_{1}+E_{2}-\alpha
E_{3}\right].$

Invoking the implicit function theorem, we can guarantee that

$\displaystyle{\tau^{\star}}^{\prime}(\alpha)=\frac{\partial_{\alpha}\mathsf{F}(\tau^{2},\alpha\tau)}{2\tau-\partial_{\tau}\mathsf{F}(\tau^{2},\alpha\tau)}=-\frac{\tau^{\star}(\alpha)\left[\alpha
E_{1}-E_{3}\right]}{(1+\alpha^{2})E_{1}+E_{2}-\alpha E_{3}-\delta}.$

For $\alpha_{0}$ with $\lambda(\alpha_{0})=0$, we know $E_{1}=\delta$, and
then

$\displaystyle{\tau^{\star}}^{\prime}(\alpha_{0})=-\frac{\tau^{\star}(\alpha_{0})\left[\alpha_{0}\delta-
E_{3}\right]}{\alpha_{0}^{2}\delta+E_{2}-\alpha_{0}E_{3}}.$

In terms of $\lambda^{\prime}(\alpha)$, one has

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}\alpha}\mathbb{E}\left[\eta^{\prime}(\Theta+\tau_{\star}(\alpha)Z;\tau^{\star}(\alpha)\alpha)\right]$
$\displaystyle=\mathbb{E}\left[(-1+\Xi\frac{{\tau^{\star}}^{\prime}(\alpha)}{\tau_{\star}(\alpha)})\phi(-\Xi-\alpha)+(-1-\Xi\frac{{\tau^{\star}}^{\prime}(\alpha)}{\tau_{\star}(\alpha)})\phi(\Xi-\alpha)\right]$
$\displaystyle=-\frac{\alpha\left[\alpha
E_{1}E_{3}-E_{3}^{2}+E_{1}E_{2}\right]+E_{3}(E_{1}-\delta)}{(1+\alpha^{2})E_{1}+E_{2}-\alpha
E_{3}-\delta}.$

Finally, we are ready to calculate the derivative $\lambda^{\prime}(\alpha)$
at $\alpha=\alpha_{0}$. By expression (19), and noticing that
$\lambda(\alpha_{0})=0$ and $E_{1}=\delta$ in this case, we calculate

$\displaystyle\lambda^{\prime}(\alpha_{0})$
$\displaystyle=\frac{\alpha_{0}{\tau^{\star}}^{\prime}(\alpha_{0})+\tau^{\star}(\alpha_{0})}{\alpha_{0}\tau^{\star}(\alpha_{0})}\lambda(\alpha_{0})-\left.\frac{\alpha_{0}\tau^{\star}(\alpha_{0})}{\delta}\frac{d}{d\alpha}\mathbb{E}\left[\eta^{\prime}(\Theta+\tau^{\star}(\alpha)Z;\tau^{\star}(\alpha)\alpha)\right]\right|_{\alpha=\alpha_{0}}$
(52)
$\displaystyle=\frac{\alpha_{0}^{2}\tau^{\star}(\alpha_{0})}{\delta}\cdot\frac{\delta\alpha_{0}E_{3}-E_{3}^{2}+\delta
E_{2}}{\delta\alpha_{0}^{2}+E_{2}-\alpha_{0}E_{3}}.$

##### Bounding the derivatives.

To establish the inequality (49), it is sufficient for us to control the
following quantities

$\displaystyle\delta\alpha_{0}E_{3}-E_{3}^{2}+\delta E_{2}~{}\text{ and
}~{}\delta\alpha_{0}^{2}+E_{2}-\alpha_{0}E_{3},$

respectively. Let us first express the function
$\mathsf{F}(\tau^{2},\tau\alpha)$ in an explicit fashion. For every fixed
$\xi$, we have

$\displaystyle\mathbb{E}\left[\eta(\xi+Z;\alpha)-\xi\right]^{2}=$
$\displaystyle(-\alpha-\xi)\phi(\alpha-\xi)+(\alpha^{2}+1)\Phi(-\alpha+\xi)+(-\alpha+\xi)\phi(\alpha+\xi)+(\alpha^{2}+1)\Phi(-\alpha-\xi)$
$\displaystyle+\xi^{2}\left[\Phi(\alpha-\xi)-\Phi(-\alpha-\xi)\right].$

Taking expectation with respect to $\xi=\Theta/\tau^{\star}(\alpha)$ on both
sides, we arrive at

$\displaystyle{\tau^{\star}(\alpha)}^{2}=\mathsf{F}({\tau^{\star}(\alpha)}^{2},\tau^{\star}(\alpha)\alpha)=\sigma^{2}+\frac{{\tau^{\star}(\alpha)}^{2}}{\delta}\left[(\alpha^{2}+1)E_{1}+E_{2}-\alpha
E_{3}+E_{4}\right].$ (53)

For $\alpha_{0}>\alpha_{\min}(\delta)>0$ with $\lambda(\alpha_{0})=0$, one has
$E_{1}=\delta$ and $E_{4}\geq 0$. As a result, the equation (53) leads to

$\displaystyle\alpha_{0}^{2}\delta+E_{2}-\alpha
E_{3}\leq-\sigma^{2}\delta{{\tau^{\star}}^{-2}(\alpha_{0})}<0.$ (54)

Next we control the quantity $\delta\alpha_{0}E_{3}-E_{3}^{2}+\delta E_{2}$ by
looking at two cases separately. Observing that
$\alpha_{0}^{2}\delta+E_{2}-\alpha
E_{3}\leq-\sigma^{2}\delta{{\tau^{\star}}^{-2}(\alpha_{0})}$, $E_{3}\geq 0$
and $E_{2}\leq 0$, we know

$\displaystyle\delta\alpha_{0}E_{3}-E_{3}^{2}+\delta
E_{2}<E_{3}\left[-\frac{\sigma^{2}\delta}{{\tau^{\star}}^{2}(\alpha_{0})\alpha_{0}}-\frac{E_{2}}{\alpha_{0}}\right]+\delta
E_{2}=-\frac{\sigma^{2}\delta}{{\tau^{\star}}^{2}(\alpha_{0})\alpha_{0}}E_{3}+\frac{\alpha_{0}\delta-
E_{3}}{\alpha_{0}}E_{2}.$

Then we have

$\displaystyle\delta\alpha_{0}E_{3}-E_{3}^{2}+\delta
E_{2}\leq\left\\{\begin{aligned}
&-\frac{\sigma^{2}\delta}{{\tau^{\star}}^{2}(\alpha_{0})\alpha_{0}}E_{3},&&\alpha_{0}\delta-
E_{3}>0;\\\ &\delta E_{2},&&\alpha_{0}\delta-E_{3}\leq 0.\end{aligned}\right.$

Taking the above properties collectively with (52), we now move on to prove
the conclusion in (49) for two cases respectively, namely,

$\displaystyle\lambda^{\prime}(\alpha_{0})\left\\{\begin{aligned}
&\geq\frac{\sigma^{2}\alpha_{0}}{\tau^{\star}(\alpha_{0})}\frac{E_{3}}{|E_{2}|-\alpha_{0}\left[\delta\alpha_{0}-E_{3}\right]}\geq\frac{\sigma^{2}\alpha_{0}}{\tau^{\star}(\alpha_{0})}\frac{E_{3}}{|E_{2}|},&\alpha_{0}\delta-
E_{3}>0;\\\
&=\frac{\alpha_{0}^{2}\tau^{\star}(\alpha_{0})}{\delta}\frac{E_{3}\left[\alpha_{0}\delta-
E_{3}\right]+\delta E_{2}}{\alpha_{0}\left[\alpha_{0}\delta-
E_{3}\right]+E_{2}}\geq\frac{\alpha_{0}^{2}\tau^{\star}(\alpha_{0})}{\delta}\min\left\\{\delta,\frac{E_{3}}{\alpha_{0}}\right\\}=\min\left\\{\alpha_{0}^{2}\tau^{\star}(\alpha_{0}),\frac{\alpha_{0}\tau^{\star}(\alpha_{0})E_{3}}{\delta}\right\\},&\alpha_{0}\delta-
E_{3}\leq 0.\end{aligned}\right.$ (55)

For the upper bound of $\lambda^{\prime}(\alpha_{0})$, we can directly verify
that

$\displaystyle\delta\alpha_{0}E_{3}-E_{3}^{2}+\delta E_{2}\geq\delta E_{2}-4,$

which combined with the expression (54) leads to

$\displaystyle\lambda^{\prime}(\alpha_{0})\leq\frac{\alpha_{0}^{2}\tau^{\star}(\alpha_{0})}{\delta}\frac{\delta|E_{2}|+4}{\sigma^{2}\delta{\tau^{\star}}^{-2}(\alpha_{0})}.$
(56)

From our assumption $\mathbb{E}[\Theta^{2}]<\infty$, we can find $M$, such
that

$\mathbb{E}[\Theta^{2}\textbf{1}\left\\{|\Theta|\leq
M\right\\}]\geq\mathbb{E}[\Theta^{2}]/2.$

Then we know that $\mathbb{P}(|\Theta|\leq
M)\geq\mathbb{E}[\Theta^{2}/M^{2}\textbf{1}\left\\{|\Theta|\leq
M\right\\}]\geq\mathbb{E}[\Theta^{2}]/(2M^{2})$. Combining with the definition
of $E_{3}$ yields

$\displaystyle
E_{3}\geq\mathbb{E}\left[\phi(|\Xi|-\alpha_{0})\right]\geq\mathbb{E}\left[\phi\left(\frac{|\Theta|}{{\tau^{\star}}(\alpha_{0})}+\alpha_{0}\right)\right]\geq\frac{\mathbb{E}[\Theta^{2}]}{2M^{2}}\phi\left(\frac{M}{{\tau^{\star}}(\alpha_{0})}+\alpha_{0}\right).$
(57)

Also, it is easily seen that

$\displaystyle|E_{2}|\leq\max_{x\in\mathbb{R}}\left\\{x\phi(x-\alpha_{0})-x\phi(-x-\alpha_{0})\right\\},$
(58)

where the right-hand side is positive and bounded away from $0$ whenever
$\alpha_{0}$ is positive. Therefore, the right-hand side of the expression
(55) and the expression (56) are both bounded away from $0$ and $\infty$ for
any fixed $\alpha_{0}\geq\alpha_{\min}$. Combining these two cases, we have
proved the advertised inequality (49).

###  B.3 Proof of Proposition B.3

From the proof of Bayati and Montanari, 2011b (, Proposition 1.3), we know
that the function $\tau^{2}\mapsto\mathsf{F}(\tau^{2},\alpha\tau)$ is concave
for any $\alpha>0$ and $\Theta$ not equal to $0$. Therefore, we obtain

$\displaystyle\Big{|}\frac{\tau_{t+1}^{2}-{\tau^{\star}_{t}}^{2}}{\tau_{t}^{2}-{\tau^{\star}_{t}}^{2}}\Big{|}\leq\frac{{\tau^{\star}_{t}}^{2}-\sigma^{2}}{{\tau^{\star}_{t}}^{2}-0}\leq
1-\frac{\sigma^{2}}{{\tau^{\star}_{\max}}^{2}}=:\eta,$

as $\tau_{t+1}^{2}=\mathsf{F}(\tau^{2},\alpha\tau)$ and
$\sigma^{2}=\mathsf{F}(0,0).$ Consequently, it leads to

$\displaystyle\left|\tau_{t+1}^{2}-{\tau^{\star}_{t+1}}^{2}\right|\leq\eta\left|\tau_{t}^{2}-{\tau^{\star}_{t}}^{2}\right|+\left|{\tau^{\star}_{t}}^{2}-{\tau^{\star}_{t+1}}^{2}\right|.$

Without loss of generality, assume $\left\\{\lambda_{t}\right\\}$ decays with
$t$. Invoking the above relation recursively, we obtain

$\displaystyle\frac{\left|\tau_{t+1}^{2}-{\tau^{\star}_{t+1}}^{2}\right|}{\eta^{t+1}}$
$\displaystyle\leq\frac{\left|\tau_{1}^{2}-{\tau^{\star}_{1}}^{2}\right|}{\eta}+\sum_{s=1}^{t}\frac{\left|{\tau^{\star}_{s}}^{2}-{\tau^{\star}_{s+1}}^{2}\right|}{\eta^{s}}$
(since ${\tau^{\star}}(\lambda)$ is $L_{\tau}$-Lipschitz )