Year: 2021

Abstract:
State equations (SEs) were firstly introduced in the approximate message passing (AMP) to describe the mean square error (MSE) in compressed sensing. Since then a set of state equations have appeared in studies of logistic regression, robust estimator and other high-dimensional statistics problems. Recently, a convex Gaussian min-max theorem (CGMT) approach was proposed to study highdimensional statistic problems accompanying with another set of different state equations. This paper provides a uniform viewpoint on these methods and shows the equivalence of their reduction forms, which causes that the resulting SEs are essentially equivalent and can be converted into the same expression through parameter transformations. Combining these results, we show that these different state equations are derived from several equivalent reduction forms. We believe that this equivalence will shed light on discovering a deeper structure in highdimensional statistics.

heading: 1 INTRODUCTION
text: Classical statistical methods often failed in the high-dimensional data where the number of features is larger than the number of observed samples. Studies in high dimensional data have attracted lots of attentions in past decades. A set of state equations (SEs) were first introduced in approximate message passing (AMP) algorithm in (Donoho et al., 2009) to precisely characterize the meansquare-error (MSE) and the phase transition phenomenon for true signal recovery in compressed sensing (CS). Since then, SEs, associated to certain AMP algorithm, have played indispensable role in various high-dimensional problems. For example, (Donoho et al., 2011) investigated the phase transition phenomenon and the precise MSE of LASSO estimator; (Donoho & Montanari, 2016) studied the variance of asymptotic distribution of M-estimator; (Huang, 2020) provided a precise characterization of min-max MSE of l1 penalized robust M-estimator and the corresponding phase transition phenomenon.
Though the SEs were first introduced through certain AMP type algorithms, researchers meet them in a variety of models through different methods. For example, the SEs appeared in (El Karoui et al., 2013) when they performed the leaving-one-out (LOO) analysis of M-estimator in high dimensions. They showed that asymptotic normality, asymptotically unbiased property also hold as in the low dimension, nevertheless the variance of asymptotic distribution of M-estimators is higher. (Sur & Candès, 2019) employed the similar idea to analyze the properties of MLE in logistic regression where the SEs were used to show that (1) asymptotically unbiased property does not hold; (2) variance of asymptotic distribution increases; (3) likelihood ratio test is not distributed as chi-square. SEs also appeared in another line of researches where Thrompoulidies et al. performed analysis of a family of high dimensional problems through the Convex Gaussian min-max theorem (CGMT). More precisely, (Thrampoulidis et al., 2018) characterized the MSE precisely for general regularized M-estimator problem in high-dimensions; (Salehi et al., 2019) established the correlation and MSE of the resulting estimator of regularized logistic regression; (Deng et al., 2019) showed the changing trend of MSE with the growth of features in support vector machine and logistic regression.
Lastly, an insightful series of works (Barbier et al., 2019; Ricci-Tersenghi & Semerjian, 2009; Moore, 2014; Krzakala et al., 2016; Coja-Oghlan et al., 2018; Mézard & Parisi, 2003; Del Ferraro et al., 2014) have utilized the SEs (named as cavity method in statistical physics) as a ubiquitous tool when they studied the high dimensional statistical problem through the perspective of statisti-
cal physics. Importantly, this tool has exhibited as a powerful weapon in applications of a lot of fields(Mezard & Montanari, 2009; Obuchi & Kabashima, 2016; Vuffray, 2014; Lesieur et al., 2015; 2016).
Though many papers have explicitly written down the corresponding state equations, none of them have shown that these sets of state equations are compatible. To the best of our knowledge, only (Deng et al., 2019) mentioned there is another set of state equation but without any comparison.
Although SEs were proved to be important in high dimensional problems, it is awkward that for one specific problem, the resulting SEs from AMP, CGMT and LOO are different. To be more clear, let us take a look at logistic regression. The SEs derived from CGMT (20) in (Deng et al., 2019) are obviously different from the SEs derived from LOO (19) in (Sur & Candès, 2019). This is annoying, since the asymptotic performance for a specific high-dimensional problem should be unique no matter which method was used.
Therefore, we are interested in the following questions:
Are SEs derived from different methods all equivalent in some sense? If so, from what viewpoint these methods are equivalent and are there more inner equivalence?
Among them, as the most direct, accessible, basic tool, equivalence of SEs is the basis of equivalence of methods and more inner equivalence.
Our contributions. We successfully show that for various high dimensional problem, the different sets of SEs derived through different methods are actually equivalent to each other. More precisely, we construct the equivalence between different sets of SEs through explicit parameter transforms for LASSO, M-estimator and logistic regression. These transformations are inspired by the statistical meanings of certain quantities appeared in the SEs. Moreover, we also provide a heuristic explanation on the relation between the different methods: AMP, CGMT and LOO. To the best of our knowledge, this is the first work to clearly clarify the equivalence among SEs derived from different methods and try to establish the equivalence of different methods.
Outlines. In section 2, we show that the SEs for M-estimator from AMP, LOO and CGMT are equivalent to each other. In section 3.1, we show the equivalence of SEs derived from AMP and CGMT for another example and explain the essential reasons behind this equivalence. In Section 3.2, we illustrate the similar work regarding the equivalence between CGMT and LOO. Section 4 provides some discussions and future directions. Most proofs are deferred to the appendix.
Notations. Let N (0, Id),N (0, 1) denote the d-dimensional standard Gaussian distribution and 1- dimensional standard Gaussian distribution respectively. For a vector x, we denote ∥x∥p as the lp norm of x. For an integer n we denote [n] as {1, · · · , n}. We abbreviate independent and identically distributed to i.i.d.. For a function f : R 7→ R, variable x ∈ R and t > 0, we denote the Moreau envelope associated with f as
Mf (x; t) := min z∈R
f(z) + 1
2t (x− z)2 (1)
and the proximal operator, which is the solution of this minimization as
Proxf (x; t) := argmin z∈R
f(z) + 1
2t (x− z)2. (2)
For multi-dimensional case x = (x1, · · · , xd)T ∈ Rd, Moreau envelope and proximal operator are applied element-wisely: Mf (x; t) := (Mf (xi; t)) ∈ Rd and Proxf (x; t) := (Proxf (xi; t)) ∈ Rd.

heading: 2 AN ILLUSTRATIVE EXAMPLE
text: Suppose that xi i.i.d.∼ N (0, 1dId) and yi ∈ R satisfying that
yi = x T i β ∗ + ϵi, for i ∈ [n] (3)
where ϵi are drawn i.i.d. from distribution Pϵ with mean 0 and variance σ2∗. We assume that the entries β∗i of β ∗ are independently distributed as Π which has finite second moment r2∗ = Eβ∼Πβ2.
Let ρ be a non-negative convex function. We are interested in the the Mean-squared-error (MSE) performance limn,p→∞ 1n∥β − β ∗∥2 of the M-estimator:
β̂ = argmin β n∑ i=1 ρ(yi − xTi β) (4)
when both n and d go to infinity satisfying that limn,d→∞ dn = κ∗ ∈ (0,∞).
This problem first studied by (El Karoui et al., 2013) where they showed that the MSE of β̂ can be characterized by a set of SEs. More precisely, they proved the following proposition.
Proposition 2.1. (El Karoui et al., 2013) Given ratio κ∗ < 1. Consider the following system of nonlinear equations (SEs) regarding (τ1, γ1) :
1− κ∗ = E[ ∂Proxρ
∂x (W1 + τ1Z1;λ1)]
κ∗τ 2 1 := E[W1 + τ1Z1 − Proxρ(W1 + τ1Z1;λ1)]2
(5)
where W1 ∼ Pϵ, Z1 ∼ N (0, 1) is independent of W1. If this system of nonlinear equations possesses a unique solution (τ̄1, λ̄1), then the τ̄1 is exactly the MSE of β̂ appeared in (4).
The M -estimator was also studied by (Donoho & Montanari, 2016) where they proved the following proposition.
Proposition 2.2. (Donoho & Montanari, 2016) Given ratio κ∗ < 1. Consider the following system of nonlinear equations (SEs) regarding (τ2, γ2) :
τ22 = 1
κ∗ λ22E[ ∂Mρ ∂x (W2 + τ2Z2;λ2)] 2
κ∗ = λ2E[ ∂2Mρ ∂x2 (W2 + τ2Z2;λ2)]
(6)
where W2 ∼ Pϵ, Z2 ∼ N (0, 1) is independent of W2. If this system of nonlinear equations possesses a unique solution (τ̄2, λ̄2), then the τ̄2 is exactly the MSE of β̂ appeared in (4).
Moreover, inspired by the work (Thrampoulidis et al., 2014), we employ the CGMT techniques to study the M -estimator and show that the asymptotic MSE can be characterized by the the following SEs. To avoid unnecessary digression, we defer the detailed proof to the appendix A. Proposition 2.3. Given ratio κ∗ < 1. Consider the following system of nonlinear equations (SEs) regarding (τ3, α, µ) :
0 = α
2 − τ3
√ κ∗ − α
µ2 E[ ∂Mρ ∂t (W3 + τ3Z3;α/µ)]
0 =− µ √ κ∗ + E[Z3 ∂Mρ ∂x (W3 + τ3Z3;α/µ)] 0 = µ
2 +
1 µ E[ ∂Mρ ∂t (W3 + τ3Z3;α/µ)]
(7)
where W3 ∼ Pϵ, Z3 ∼ N (0, 1) is independent of W3. If this system of nonlinear equations possesses a unique solution (τ̄3, ᾱ, µ̄), then the τ̄3 is exactly the MSE of β̂ appeared in (4).
On the one hand, these three sets of SEs are different at the first glance. On the other hand, since they are all supposed to describe the MSE of the M -estimators in high dimension, there shall be some relation between these three sets of equations. A striking fact is that we can actually show that all these three set of SEs are equivalent to each other. More precisely, we have the following theorem.
Theorem 1. For M-estimator(4), the SEs derived from AMP (6), LOO (5) and CGMT (7) are equivalent. Specifically, (6) can be converted into the same form as (5) after the following parameter transformations:
τ1 = τ2, λ1 = λ2. (8)
(6) can be converted into the same form as (7) after the following parameter transformations:
τ1 = τ3, λ1 = α
µ . (9)
The equivalence of these three sets of SEs seems straightforward, however, it suggests us that all the three procedures: AMP, CGMT and LOO might be deeply entangled in some sense. This will be investigated in this manuscript.
The proof of this theorem is deferred to the appendix B.

heading: 3 GENERAL RESULTS
text: In this section, we show that the aforementioned equivalence between different sets of SEs holds not only for M-estimator, but also for Lasso and logistic regression in high dimensions.

heading: 3.1 EQUIVALENCE BETWEEN THE SES DERIVED FROM CGMT AND AMP
text: Let us consider the following optimization
min β
1 2 ∥y −Xβ∥22 + λ∗∥β∥1 (10)
where yi = x τ i β ∗+ϵi with xi i.i.d.∼ N (0, 1nId) , r∗ := limn,p→∞ ∥β∗∥√ n
and λ∗ ≥ 0 is the regularized parameter, ϵi are drawn i.i.d. from distribution Pϵ with mean 0 and variance σ2∗. We are interested in the the Mean-squared-error(MSE) performance limn,p→∞ 1n∥β − β ∗∥2 of the LASSO. (Donoho et al., 2011), (Mousavi et al., 2018), (Bayati & Montanari, 2011; Miolane & Montanari, 2018; Javanmard & Montanari, 2018) have utilized the AMP to study the asymptotic performance of the Lasso estimator. For our purpose, we briefly recall the results in (Mousavi et al., 2018) below.
Proposition 3.1. (Mousavi et al., 2018) Given noise scale σ2∗ and ratio κ∗, consider the following system of nonlinear equations (SEs) regarding (τ1, γ1) :
τ21 = σ 2 ∗ + κ∗E[η(β1 + τ1Z1;λ∗ + γ1)− β1]2 γ1 = κ∗(γ1 + λ∗)E[η′(β1 + τ1Z1;λ∗ + γ1)] . (11)
where Z1 ∼ N (0, 1) is a standard normal variable, β1 ∼ Π is independent of Z1, η(·; ·) is the soft threshold function:
η(x; t) := sign(x)(|x| − t)+,
x+ means max{x, 0} and
sign(x) :=  1 if x > 0 0 if x = 0
−1 if x < 0 .
If this system of nonlinear equations possesses a unique solution (τ̄1, λ̄1), then the τ̄1 is exactly the MSE of β̂ appeared in (10).
Inspired by the sequence of work (Thrampoulidis et al., 2014; 2015; 2018; Salehi et al., 2019), we apply the CGMT to study the asymptotic performance of the Lasso estimator appeared in (10) and find that it is characterized by the following set of SEs.
Proposition 3.2. Given noise scale σ2∗, signal strength r2∗ in model (3) and ratio κ∗, Consider the following system of nonlinear equations (SEs) regarding (α, σ, τ2, θ, λ, γ2):
0 = − α στ2 + θ − 1 + α+ λ λ+ 1 0 = − 1 2τ2 + r2∗κ∗α 2 2σ2τ2 − τ2κ∗ 2 E[(Proxf̃ (γ2Z2 + θβ2;λ∗)) 2] + σ λ+ 1 0 = γ22 − r2∗κ∗ − σ2∗ + 2[(α+ λ)r2∗κ∗ + λσ 2 ∗]
λ+ 1 − (α+ λ)
2r2∗κ∗ + σ 2 + λ2σ2∗
(λ+ 1)2
0 = r2∗κ∗α− στ2κ∗E[β2Proxf̃ (γ2Z2 + θβ2;λ∗)]
λ = στ2κ∗E[ ∂Proxf̃ (γ2Z2 + θβ2;λ∗)
∂x ]
0 = σ
2τ22 +
r2∗κ∗α 2
2στ22 − σκ∗ 2 E[(Proxf̃ (γ2Z2 + θβ2;λ∗)) 2]
(12)
where Z2 ∼ N (0, 1) is a standard normal variable, β2 ∼ Π is independent of Z2, f̃(x) := |x|.
If this system of nonlinear equations possesses a unique solution (ᾱ, σ̄, τ̄2, θ̄, λ̄, γ̄2), then the λ̄2θ̄ is exactly the MSE of β̂ appeared in (10)
The detailed proof is deferred until the Appendix C. The following proposition illustrate the equivalence between these two sets of SEs.
Theorem 2. The SEs of LASSO derived from AMP (11) are equivalent to the SEs derived from CGMT (12). Specifically, (12) can be converted into the same form as (11) after the following parameter transformations:
τ1 = γ2 θ , γ1 = λ∗ θ − λ∗. (13)
The detailed proof is deferred until Appendix C.1.
We provided a heuristic explanation on the equivalence of the SEs derived from AMP and CGMT. For the sake of the self-contentment, we briefly review the procedures of how to derive SEs from AMP and CGMT respectively.
Deriving SEs from AMP. The derivation of SE from AMP can be divided into two stages:
(1) Constructing an iterative algorithm
1) AMP first transform initial optimization problem into pursuing a Bayesian posterior distribution where objective function is transformed into a probability distribution.
2) Based on the corresponding factor graph of this distribution, it invokes the message passing(MP) algorithm to compute the Bayesian posterior distribution.
3) The MP is then further approximated by some large system limit, large β limit and the approximation of iteration.
(2) The asymptotic behavior of AMP is then characterized by the state evolution equations/SEs.
Deriving SEs from CGMT. The derivation of SE from CGMT can be divided into four steps.
1) The initial optimization problem is transformed into a min-max form, which is called the primary optimization (PO) problem.
2) CGMT perform a dimensionality reduction on PO and obtain the auxiliary optimization (AO) problem
3) AO is further simplified to an optimization problem only depending on several scalar variables, which is called scalar optimization (SO) problem.
4) SEs are derived by finding first-order optimality conditions of the asymptotic version of SO.
Remark 3.1. We find that AO can be viewed as a relaxation of PO in the sense that the feasible region of AO is larger than that of PO. Concrete examples, such as M-estimator, Logistic regression, Support vector machine and so on, are deferred to the appendix. We believe that this relaxation can help us understand the equivalence between the resulting SEs from AMP and CGMT respectively.
We now present a uniform viewpoint on AMP and CGMT: 1) Constructing the AMP corresponds to the first step of CGMT in LASSO, which suggests that the iteration of AMP is actually equivalent to the process of solving PO. 2) Deriving the SEs from AMP corresponds to the last three steps of CGMT. Both of them aim to deriving SEs and characterizing asymptotic performance by approximating the initial optimization problem. We proved the first statement in Proposition 3.3.
Proposition 3.3. (Rangan et al., 2016) For LASSO, the fixed point of AMP is just the solution of first-order optimality conditions of PO in CGMT.
Proof. For CGMT, by introducing u to constrain u = Xβ and Lagrange vector v, the corresponding PO can be written as:
min β,u max v
1 2 ∥u∥22 − yTu+ 1 2 ∥y∥22 + λ∗∥β∥1 + vT (Xβ − u).
Consider the first-order optimality conditions of PO: 0 = λ∗sign(β) +XTv 0 = u− y − v 0 = u−Xβ.
(14)
Comparing above formulas in (14) leads to
λ∗sign(β) +XT (Xβ − y) = 0. For AMP algorithm, the iteration of LASSO is
βt+1 = η(βt +XTzt;λ∗ + γ t)
zt = y −Xβt + κ∗zt−1⟨ ∂
∂x η(βt−1 +XTzt−1;λ∗ + γ t−1)⟩
γt = κ∗(λ∗ + γ t−1)⟨ ∂
∂x η(βt−1 +XTzt−1;λ∗ + γ t−1)⟩
where ∂∂x acts component-wisely. For some vector x, ⟨x⟩ := ∑d i=1 xi denotes the entry-sum of x. The fixed point (β∞, z∞, γ∞) satisfy the following equations:
0 = (λ∗ + γ)sign(β) + β − (β +XTz) (15a) z = y −Xβ + κ∗z · c (15b) γ = κ∗(λ∗ + γ)c (15c)
where c = c(β, z, γ) = ⟨ ∂∂xη(β + X Tz;λ∗ + γ)⟩ and (15a) is given by the following property about the soft thresholding function:
t · sign(z) + z − x = 0
for z = η(x; t) and some scalar x.
Simplifying (15b) and (15c) leads to:
z = y −Xβ 1− κ∗c γ = κ∗cλ∗ 1− κ∗c .
(16)
Comparing (16) with (15a) gives, λ∗
1− κ∗c sign(β)− 1 1− κ∗c XT (y −Xβ) = 0.
which finishes the proof.
Remark 3.2. It needs to be discussed component-wisely according to whether each entry of the optimal β is 0 or not. The above proof holds for the entries that βi ̸= 0. For i such that βi = 0, the optimality from PO gives −λ∗ + (XT (Xβ − y))i < 0 and λ∗ + (XT (Xβ − y))i > 0. This is equivalent to |(XT (Xβ−y))i| ≤ λ∗, where (XT (Xβ−y))i denote the i-th entry of XT (Xβ−y). This is still equivalent to the fixed-point condition in AMP. Hence the equivalence holds for all entries of β.

heading: 3.2 EQUIVALENCE BETWEEN THE SES DERIVED FROM CGMT AND LOO
text: Suppose that xi i.i.d.∼ N (0, 1dId) and yi ∈ {−1, 1} drawn from logistic model: P(yi = 1|xi) = ρ′(xTi β∗), for i ∈ [n] (17) where ρ(t) = log(1+et). Each entry of β is independently distributed as Π which has finite second moment r2∗ = Eβ∼Πβ2.
We are interested in the following optimization problem:
β̂ = argmin β
1
n n∑ i=1 ℓ(yix T i β) (18)
where ℓ(t) := log(1 + e−t). When the β̂ exists, we are interested in the the Mean-squarederror(MSE) performance limn,p→∞ 1n∥β − β
∗∥2 of the Logistic regression. Logistic regression in high dimensions have been studied recently by (Candès & Sur, 2020; Mousavi et al., 2018), (Deng et al., 2019). The asymptotic MSE of β̂ was characterized by the following two propositions. Proposition 3.4. (Sur & Candès, 2019) Given signal strength r2∗ in logistic model (17) and ratio κ∗, Consider the following system of nonlinear equations (SEs) regarding (λ1, α1, σ):
α21 = 1
κ2∗ E[2ρ′(Q1) (λ1ρ′(Proxρ(Q2;λ1))) 2 ]
0 = E[ρ′(Q1)Q1λ1ρ′(Proxρ(Q2;λ1))]
1− κ∗ = E[ 2ρ′(Q1)
1 + λ1ρ′′(Proxρ(Q2;λ1)) ]
(19)
where
(Q1, Q2) ∼ N ( 0; [ r2∗ −σr2∗
−σr2∗ σ2r2∗ + α21κ∗ ]) and ρ(t) := log(1 + et).
If this system of nonlinear equations possesses a unique solution (λ̄1, ᾱ1, σ̄), then the MSE of β̂ appeared in (18) is [(σ̄ − 1)Eβ∼Πβ]2 + ᾱ2. Remark 3.3. In (Sur & Candès, 2019), it is assumed that Xi,j ∼ N (0, 1nId) and r 2 ∗ = κ∗Eβ∼Πβ2, which is slightly different from the setting in this paper. However, this difference only leads to a constant change related to κ∗ in the final parameter transformations (21) and does not affect the equivalence of these two set of SE. Proposition 3.5. (Deng et al., 2019) Given signal strength r2∗ in logistic model (17) and ratio κ∗, Consider the following system of nonlinear equations (SEs) regarding (λ2, α2, µ):
0 = E[V ℓ′(Proxℓ(α2Z + µV ;λ2))] α22κ∗ = λ 2 2E[(ℓ′(Proxℓ(α2Z + µV ;λ2)))2]
κ∗ = λ2E[ ℓ′′(Proxℓ(α2Z + µV ;λ2))
1 + λℓ′′(Proxℓ(α2Z + µV ;λ2)) ]
(20)
where Z ∼ N (0, 1), V = Z1Yr∗ , in which Z1 ∼ N (0, 1) is independent of Z and Yr∗ ∼ Ber(ρ′(r∗Z1)). Ber(p) denotes the Bernoulli distribution with probability p for the value +1 and probability 1− p for the value −1. If this system of nonlinear equations possesses a unique solution (λ̄2, ᾱ2, µ̄), then the MSE of β̂ appeared in (18) is [( ᾱ2√κ∗ − 1)Eβ∼Πβ] 2 + ( µ̄r∗ ) 2.
As before, we can show that (19) and (20) are equivalent.
Theorem 3. For logistic regression (18), the SEs derived from LOO (19) and CGMT (20) are equivalent. Specifically, (19) can be converted into the same form as (20) after the following parameter transformations:
α1 = α2√ κ∗ , σ = µ r∗ , λ1 = λ2. (21)
The proof of this theorem is deferred to appendix E
For the sake of self-contentment, we briefly review the procedure on deriving SEs from LOO.
Deriving SEs from LOO The derivation can be divided into 4 steps.
1) First, for the original optimization problem, LOO considers first-order conditions of three cases: a) keeping all observations and predictors, corresponding solution is denoted as β̂, b) leaving one predictor, corresponding solution is denoted as β̂(−j) and c) leaving one predictor and one observation, corresponding solution is denoted as β̂(−i),(−j)
2) Two properties are derived from comparing three version of first-order conditions: a) The i-th fitted value Xiβ̂ has an asymptotic expression composed of two independent random vectors Xi,(−j) and β̂(−i),(−j). b) Each coordinate β̂j can be written as a sum of n random variables which are asymptotically independent.
3) Using above two properties , β̂j has the same distribution as a combination of several scalar variables when n, p → ∞. Hence every statistic of β̂ (such as expectation, variance and first order condition of optimization) can be expressed by these scalar variables, from which the SEs of β̂ are derived.
Briefly reviewing the procedures of LOO approach, we find that the sample matrix X (which is a Rn×p Gaussian matrix)is decomposed into two independent Gaussian vectors through some special techniques in both LOO and CGMT, which allows the law of large numbers to simplify the firstorder equations into scalar equations. This may help us understand the equivalence between CGMT and LOO. The more intrinsic equivalence of these two methods is still under investigation.

heading: 4 DISCUSSION AND FUTURE DIRECTIONS
text: In this paper, we first showed that for the high dimensional M -estimator, the three sets of SEs derived from AMP, CGMT and LOO are equivalent. We then further show that this equivalence actually appears in various high dimensional problems. This strongly suggests us that there should be a deep relation between these three approaches.
Though AMP, CGMT and LOO are different at the first glance, we find that they all can be treated as approximations of the same first order optimality conditions. To be more precise, LOO decouples the correlation between samples and estimator after comparing first-order optimality conditions of the initial optimization with two leaving-one-out version; CGMT simplifies the first-order optimality conditions by making some relaxation of the PO problem; AMP solves the first order optimality conditions directly. All their asymptotic behaviours are characterized by the corresponding SEs respectively. The equivalence between these SEs sheds us light on looking for a more comprehensive theories to explain this intriguing phenomenon.

heading: A PROOF OF PROPOSITION 2.3
text: By the following linear parameter transformation:
w := β − β∗,
the M-estimator optimization problem becomes:
min w
1
n n∑ i=1 ρ(ϵi − xTi w). (22)
Introducing the Lagrange multiplier leads to:
min w,v max u
1
n n∑ i=1 ρ(vi) + 1√ n ui(vi − ϵi + xTi w)
where u := (u1, ..., un);v = (v1, ..., vn).
Then we rewrite it in the matrix form:
min w,v max u 1√ n uTXw + 1 n n∑ i=1 ρ(vi) + 1√ n (uTv − uT ϵ)
where ϵ := (ϵ1, ..., ϵn)T . This is just the PO problem in CGMT. Denote X̃ = √ nX, w̃ = w√
n , then we have X̃i,j
i.i.d.∼ N (0, 1), w̃ = β−β ∗
√ n . This means ∥w∥2
is just the MSE of interest and X̃ is a standard Gaussian matrix composed of iid standard normal variable.
However, in the following, we rewrite X̃, w̃ as X,w respectively for the simplicity of notation.
Using CGMT about X̃ as in (Salehi et al., 2019) by Corollary 3 in it, then the AO problem associated to it is the following min-max problem:
min w,v max u 1√ n (||u||2gTw + ||w||2hTu) + 1 n n∑ i=1 ρ(vi) + 1√ n (uTv − uT ϵ)
where g ∈ Rd and h ∈ Rn have i.i.d. N (0, 1) entries. Let ∥w∥2 = τ3, note that now
τ23 = 1
n ||β − β∗||2 (23)
which is just the MSE.
Then the optimization becomes:
min τ3,v max u 1√ n (−τ3||u||2||g||2 + τ3hTu) + 1 n n∑ i=1 ρ(vi) + 1√ n (uTv − uT ϵ).
Letting ||u||2 = µ, then We have the following optimization:
min τ3,v max µ>0 −τ3µ√ n ||g||2 + 1 n n∑ i=1 ρ(vi) + µ√ n ||τh+ v − ϵ||2. (24)
equivalently:
min τ3,v max µ>0
1
n n∑ i=1 ρ(vi) + µ( 1√ n ||τ3h+ v − ϵ||2 − τ3√ n ||g||2). (25)
In order to make the ||τ3h+ v − ϵ||2 separable, we use the following optimization:
x = min α>0
α 2 +
x2
2α
for any x and α > 0. Replace x by 1√ n ||τ3h+ v − ϵ||2, the optimization problem (25) becomes:
min τ3,v max µ −τ3µ√ n ||g||2 + 1 n n∑ i=1 ρ(vi) + µ(max α>0 α 2 + 1 2αn ||τ3h+ v − ϵ||22).
Then what we want to do the scalarization procedure: make the optimization about v becoming optimization about a scalar. First, flipping in the order of min-max by (Thrampoulidis et al., 2018):
min τ3,α max µ
αµ 2 − τ3µ√ n ||g||2 + 1 n [min v n∑ i=1 ρ(vi) + µ 2α (τ3hi + vi − ϵi)2]. (26)
Introducing Moreau envelope function Mρ(x; t), the optimization problem (26) becomes:
min τ3,α max µ
αµ 2 − τ3µ√ n ||g||2 + 1 n n∑ i=1 Mρ(ϵi − τ3hi;α/µ).
By Lemma 9 in Appendix A in (Thrampoulidis et al., 2018), considering asymptotic n, p → ∞, p/n → κ∗ leads to:
αµ 2 − τ3µ√ n ||g||2 + 1 n n∑ i=1 Mρ(ϵi − τ3hi;α/µ) a.s.→ αµ 2 − τ3µ √ κ∗ + EMρ(W3 − τ3Z3;α/µ)
where Z3 ∼ N (0, 1) is independent of everything else. Introduce W3 ∼ Pϵ. Then, asymptotically, we can deal with the following problem:
min τ3,α max µ
αµ
2 − τ3µ
√ κ∗ + EMρ(W3 + τ3Z;α/µ). (27)
Denoting the objective function of (27) by ϕ, then since ϕ is convex about (τ3, α) and concave about µ, the saddle point of ϕ can be precisely characterized by its first order optimality condition:
∂ϕ ∂µ = 0 ⇒ α 2 − τ3 √ κ∗ − α µ2 E[ ∂Mρ ∂t (W3 + τ3Z3;α/µ)] = 0
∂ϕ ∂τ = 0 ⇒ −µ √ κ∗ + E[Z3 ∂Mρ ∂x (W3 + τ3Z3;α/µ)] = 0 ∂ϕ
∂α = 0 ⇒ µ 2 + 1 µ E[ ∂Mρ ∂t (W3 + τ3Z3;α/µ)] = 0.
Combining with (23) completes the proof.

heading: B EQUIVALENCE OF SES OF M-ESTIMATOR FROM AMP, LOO, CGMT
text: Recall that the SEs of M-estimator from LOO are:
1− κ∗ = E[ ∂Proxρ
∂x (W1 + τ1Z1;λ1)]
κ∗τ 2 1 := E[W1 + τ1Z1 − Proxρ(W1 + τ1Z1;λ1)]2.
(28)
SEs of M-estimator from AMP are:
τ22 = 1
κ∗ λ22E[ ∂Mρ ∂x (W2 + τ2Z2;λ2)] 2
κ∗ = λ2E[ ∂2Mρ ∂x2 (W2 + τ2Z2;λ2)].
(29)
Next, we show that these two sets of SEs are equivalent.
First, Simple calculation leads to:
∂Mρ(x, t)
∂x = ρ′(Proxρ(x; t))
∂2Mρ(x, t)
∂x2 = ρ′′(Proxρ(x; t))
∂Proxρ(x; t)
∂x =
ρ′′(Proxρ(x; t))
1 + tρ′′(Proxρ(x; t))
x− Proxρ(x; t) t = ρ′(Proxρ(x; t)).
(30)
Combine this, SEs from AMP can be rewritten as:
τ22 = 1
κ∗ λ22E[ρ′(Proxρ(W2 + τ2Z2;λ2))]2
κ∗ = λ2E[ ρ′′(Proxρ(W2 + τ2Z2;λ2))
1 + λ2ρ′′(Proxρ(W2 + τ2Z2;λ2)) ].
(31)
which verify that SEs from LOO and SEs from AMP are equivalent.
Next we prove equivalence of SEs from AMP and SEs from CGMT by parameter transformations suggested.
Recall the SEs from CGMT are:
α 2 − τ3 √ κ∗ − α µ2 E[ ∂Mρ ∂t (W3 + τ3Z3;α/µ)] = 0
−µ √ κ∗ + E[Z3 ∂Mρ ∂x (W3 + τ3Z3;α/µ)] = 0
µ 2 + 1 µ E[ ∂Mρ ∂t (W3 + τ3Z3;α/µ)] = 0.
Let b = αµ , then we have:
µb
2 − τ3
√ κ∗ − α
µ2 E[ ∂Mρ ∂t (W3 + τ3Z3; b)] = 0
−µ √ κ∗ + E[Z3 ∂Mρ ∂x (W3 + τ3Z3; b)] = 0
µ 2 + 1 µ E[ ∂Mρ ∂y (W + τZ; b)] = 0.
Comparing these results leads to:
E[ ∂Mρ ∂x (W3 + τ3Z3; b)] 2 = τ23κ∗ b2 E[ ∂2Mρ ∂x2 (W3 + τ3Z3; b)] = κ∗ b . (32)
Combining stein lemma and
∂Mρ ∂t (W3 + τ3Z3; b) = − 1 2 [ ∂Mρ ∂x (W3 + τ3Z3; b)] 2. (33)
completes our proof.

heading: C EQUIVALENCE OF SES OF LASSO FROM AMP AND CGMT
text: In this proof, we refer to the technique developed in (Donoho & Montanari, 2016). The Lasso problem solves
argmin β λ∗ n ∥β∥1 + 1 2n ∥y −Xβ∥2. (34)
Notice that ∥y −Xβ∥2 = ∑n
i=1 [ (xTi β) 2 − 2yixTi β + y2i ]
. The optimization can be transformed into
argmin β λ∗ n ∥β∥1 + 1 n n∑ i=1 [ 1 2 (xTi β) 2 − yixTi β ] . (35)
In the following proof, we consider a more general optimization than Lasso:
argmin β λ∗ n f(β) + 1 n n∑ i=1 [ 1Tρ(u)− yixTi β ] (36)
where ρ(·) and f(·) are ’separable’ in the sense that there exist scalar functions ρ(·), f̃(·) so that ρ(·) and f(·) can be expressed as the following form: ρ(x) = (ρ(x1), · · · , ρ(xd))T and f(x) =∑d
i=1 f̃(xi). In particular, in Lasso, ρ(t) = 1 2 t 2 and f(x) = ∥x∥1. In order to apply CGMT, we introduce a new variable u and have following optimization
min β,u λ∗ n f(β) + 1 n
( 1T ρ(u)− yTu ) s.t. u = Xβ =
1√ n H∗β
(37)
where H∗ = √ nX ∈ Rn×d and hence H∗ij
i.i.d.∼ N (0, 1). By using Lagrange multiplier we can rewrite (37) as a min-max optimization:
min β∈Rd,u∈Rn max v
1 n 1T ρ(u)− 1 n yTu+ λ∗ n ∥β∥1 + 1 n vT (u− 1√ n H∗β). (38)
Denote P = β ∗(β∗)T
∥β∗∥2 as the projection matrix of true signal β ∗ and P⊥ = Id −P as the orthogonal
complement. To apply CGMT, we need first decompose H∗ into
H∗1 = H ∗ · P, H∗2 = H∗ · P⊥
H∗ =H∗1 +H ∗ 2.
(39)
In addition, Recalling the linear model (3) we have y = Xβ∗ + ϵ = 1√ n H∗β∗ = 1√ n H∗1β ∗. Hence (38) can be rewritten as
min β∈Rd,u∈Rn max v
1 n 1T ρ(u)− 1 n yTu+ λ∗ n f(β) + 1 n vT (u− 1√ n H∗1β)− 1 n √ n vTH∗2β. (40)
By using CGMT for vTH∗2β as in (Salehi et al., 2019) by Corollary 3 in it, the corresponding AO of (40) is
min β∈Rd,u∈Rn max v
1 n 1T ρ(u)− 1 n yTu+ λ∗ n f(β) + 1 n vT (u− 1√ n H∗1β)
− 1 n √ n
( vTh∥P⊥β∥2 + ∥v∥2gTP⊥β ) (41) where h ∼ N (0, In) and g ∼ N (0, Id) are two independent gaussian vectors.
We first consider the maximization with respect to the direction of v. The part related to v in optimization (41) is:
max v∈Rn
1
n √ n ∥v∥2gTP⊥β +
1 n vT
( u− 1√
n H∗1β − 1√ n h∥P⊥β∥2
) . (42)
Denoting r := ∥v∥2√ n and maximizing along the direction of v give
max r≥0 r
( 1
n gTP⊥β + ∥ 1√ n u− 1 n H∗1β − ∥P⊥β∥2 n
h∥2 ) . (43)
Inserting this into (41) gives
min β,u max r≥0
1 n 1T ρ(u)− 1 n yTu+ λ∗ n f(β) + r
( 1
n gTP⊥β + ∥∥∥∥ 1√nu− 1nH∗1β − ∥P⊥β∥2n h ∥∥∥∥ 2 ) .
(44)
In addition, introduce µ to replace β in ∥β∥1 Lagrangian and w. Then (44) can be rewritten as,
min u∈Rn; β,µ∈Rd max r≥0; w∈Rd
1 n 1T ρ(u)− 1 n yTu+ λ∗ n f(µ) + r
( 1
n gTP⊥β
)
+ r ∥∥∥∥ 1√nu− 1nH∗1β − ∥P⊥β∥2n h ∥∥∥∥ 2 + 1 d wT (µ− β).
(45)
We define α = β Tβ∗
∥β∗∥22 , σ = 1√ n ∥P⊥β∥2 and q = H
∗β∗ r1∗ √ n where r1∗ = ∥β∗∥2√ n . Then q is a standard
Gaussian vector and
1 n H∗1β = 1 n H∗(Pβ) =
H∗
n · αβ∗ d= α n r1∗ √ nq. (46)
Decomposing w = (P + P⊥)w, then the last item in (45) can be rewritten as
1 d wT (µ− β) = 1 d (Pw)Tµ+ 1 d (P⊥w)Tµ− 1 d (Pw)Tβ − 1 d (P⊥w)Tβ. (47)
Inserting (46) and (47) into (45), we have,
min u∈Rn; β,µ∈Rd max r≥0; w∈Rd
1 n 1T ρ(u)− 1 n yTu+ λ∗ n f(µ) + r
( 1
n gTP⊥β
) − 1
d (P⊥w)Tβ
+ r ∥∥∥∥ 1√nu− αr1∗√n q− σ√nh ∥∥∥∥ 2 + 1 d (Pw)Tµ+ 1 d (P⊥w)Tµ− 1 d (Pw)Tβ. (48)
Then we can fix Pβ and consider the minimization along the direction of P⊥β. Considering the optimization related to P⊥β, we have
min P⊥β
r n gTP⊥β − 1 d (P⊥w)Tβ = min P⊥β ( r n gT − 1 d wT )P⊥β
= −∥P⊥β∥2 · ∥ r n P⊥g − 1 d P⊥w∥2
= −σ · ∥ r√ n P⊥g −
√ 1
dκ∗ P⊥w∥2.
(49)
Notice that (48) reaches optimal when µ = β. Inserting (49) into (48) leads to
min u∈Rn,µ∈Rd;
α∈R,σ≥0 max r≥0; w∈Rd
1 n 1T ρ(u)− 1 n yTu+ λ∗ n f(µ)− σ · ∥ r√ n P⊥g −
√ 1
dκ∗ P⊥w∥
+ r ∥∥∥∥ 1√nu− αr1∗√n q− σ√nh ∥∥∥∥+ 1d (P⊥w)Tµ.
(50)
For the simplifying procedures in the following steps in our analysis, we change ∥ · ∥2 → ∥ · ∥22 by
rx = min v≥0
r
2v +
rv
2 x2
−σx = max τ≥0 − σ 2τ − στ 2 x2.
(51)
Applying (51), we are able to rewrite (50) as
min u∈Rn,µ∈Rd;α∈R,v,σ≥0 max w∈Rd; r,τ≥0
1 n 1T ρ(u)− 1 n yTu+ λ∗ n f(µ)− σ 2τ − στ 2 ∥ r√ n P⊥g −
√ 1
dκ∗ P⊥w∥2
+ r
2v +
rv
2 ∥∥∥∥ 1√nu− αr1∗√n q− σ√nh ∥∥∥∥2 + 1d (P⊥w)Tµ.
(52)
Optimization with respect to w: Next we consider the maximization with respect to w. We first extract the item related to w in (52) and apply the completion of squares:
max w − στ 2 ∥∥∥∥ r√nP⊥g − √ 1 dκ∗ P⊥w ∥∥∥∥2 + 1d (P⊥w)Tµ = max
w − στ 2 ∥∥∥∥∥ r√nP⊥g − √ 1 dκ∗ P⊥w + 1√ d/κ∗στ P⊥µ ∥∥∥∥∥ 2
+ 1
2nστ ∥∥P⊥µ+ στrP⊥g∥∥2 − στr2 2n ∥P⊥g∥2.
(53)
1) For the last item in (53), since g ∼ N (0, Id) and P⊥ is a (n − 1)-dimensional projection matrix, we derive that ∥P⊥g∥22 ∼ ∥∥d(0, (P⊥)2)∥∥2 2 d = χ2d−1 and
στr2
2n ∥P⊥g∥2 a.s.→ στr 2κ∗ 2 . (54)
2) Since P⊥ = Id − P , the second item in (53) can be rewritten as
1
n ∥∥P⊥µ+ στrP⊥g∥∥2 =1 n ∥µ+ στrg∥2 − 1 n ∥Pµ∥2
− (στr) 2 n ∥Pg∥2 − 2στr n (Pg)Tµ.
(55)
The last two items of (55) can be omitted in the limit of d, n → ∞ because ∥Pg∥ 2
n = Op( 1 n )
and 1n (Pg) Tµ = Op( 1√ n ). The second item of (55) is 1n∥Pµ∥ 2 = 1n∥Pβ∥ 2 = α2r1∗ 2 by definition.
3) The first item in (53) reaches 0 when maximizing w.
The optimization (52) now can be rewritten as
min u∈Rn,µ∈Rd; α∈R,v,σ≥0 max r,τ≥0
1 n 1T ρ(u)− 1 n yTu+ λ∗ n f(µ)− σ 2τ + 1 2nστ ∥µ+ στrg∥2 − α 2r21∗ 2στ − στr 2κ∗ 2
+ r
2v +
rv
2 ∥∥∥∥ 1√nu− αr1∗√n q− σ√nh ∥∥∥∥2 .
(56)
Optimization respect to µ: Consider the items related to µ in (56)
min µ∈Rd λ∗ n f(µ) + 1 2nστ ∥µ+ στrg∥22
s.t. µ = β.
(57)
Notice that g ∼ N (0, Id), ∥µ+ στrg∥22 d = ∥µ− στrg∥22. We rewrite (57) as
min µ∈Rd λ∗ n f(µ) + 1 2nστ ∥µ− στrg∥22
s.t. 1
n β∗Tµ =
1 n β∗Tβ = 1 n nαr21∗ = αr 2 1∗.
(58)
Introducing Lagrangian θ, (58) can be rewrite as
min µ∈Rd max θ∈R
1 2nστ ∥µ− στrg∥2 + λ∗ n f(µ)− θ n β∗Tµ+ αθr21∗. (59)
Applying the completion of squares to 1,3 items in (59) we have,
1 2nστ ∥µ− στrg∥2 − θ n β∗Tµ = 1 2nστ ∥µ− στrg − θστβ∗∥2
− (θστ) 2 2nστ ∥β∗∥2 − θrσ 2τ2 2nστ gTβ∗.
(60)
The third item can be omitted since g Tβ∗
n = Op( 1√ n ) and the second item has limit
− (θστ) 2 2nστ ∥β ∗∥2 → − (θστ) 2 2nστ · nr 2 1∗ = − στθ2r21∗ 2 . Hence we rewrite right side of (60) as
1 2nστ ∥µ− στrg∥2 − θ n β∗Tµ = 1 2nστ ∥µ− στrg − θστβ∗∥2 − στθ 2r21∗ 2 . (61)
Next, denote f̃(x) as single-entry form of f(x). We can rewrite the (61) in terms of Moreau envelope entry-wisely as follows
min µ∈Rd max θ∈R
1 2nστ ∥µ− στrg∥2 + λ∗ n f(µ)− θ n β∗Tµ+ αθr21∗
=max θ
1 n Mλ∗f̃ (στ(rg + θβ ∗);στ) + αθr21∗ − στθ2r21∗ 2 .
(62)
Substituting (62) in (56) we have,
min u∈Rn;
α∈R,σ,v≥0 max r,τ≥0; θ∈R
1 n 1T ρ(u)− 1 n yTu+ rv 2 ∥∥∥∥ 1√nu− αr1∗√n q− σ√nh ∥∥∥∥2 − σ2τ − α2r21∗2στ
− στr 2κ∗ 2 + r 2v + 1 n Mλ∗f (στ(rg + θβ ∗);στ) + αθr21∗ − στθ2r21∗ 2 .
(63)
Optimization respect to u: First we consider the items related to u. The optimization is
min u∈Rn
1 n 1T ρ(u)− 1 n yTu+ rv 2 ∥∥∥∥ 1√nu− αr1∗√n q− σ√nh ∥∥∥∥2 . (64)
Applying the completion of squares we have,
− 1 n yTu+ rv 2 ∥∥∥∥ 1√nu− αr1∗√n q− σ√nh ∥∥∥∥2 =rv2 ∥∥∥∥ 1√nu− αr1∗√n q− σ√nh− 1rv√ny ∥∥∥∥2
− 1 2rvn ∥y∥2 − r1∗α n yTq− σ n yTh.
(65)
Using the strong law of large numbers we have,
− 1 2rvn ∥y∥2 a.s.→ −r 2 1∗ + σ 2 ∗ 2rv
−r1∗α n yTq a.s.→ −r21∗α
−σ n yTh a.s.→ 0.
(66)
Next, by substituting (65), (66) in (64), we can rewritten the optimization as,
min u∈Rn
1 n 1T ρ(u)− 1 n yTu+ rv 2 ∥∥∥∥ 1√nu− αr1∗√n q− σ√nh ∥∥∥∥2
= min u∈Rn
1 n 1T ρ(u) + rv 2 ∥∥∥∥ 1√nu− αr1∗√n q− σ√nh− 1rv√ny ∥∥∥∥2 − r 2 1∗ + σ 2 ∗
2rv − r21∗α.
(67)
Then we can rewrite (67) in terms of Moreau envelope,
min u∈Rn
1 n 1T ρ(u) + rv 2 ∥∥∥∥ 1√nu− αr1∗√n q− σ√nh− 1rv√ny ∥∥∥∥2
= 1
n Mρ(·)(αr1∗q+ σh+
1
rv y;
1
rv ).
(68)
Substituting (67), (68) in (63) we have
min α∈R; σ,v≥0 max r,τ≥0; θ∈R
1 n Mρ(αr1∗q+ σh+ 1 rv y; 1 rv )− r
2 1∗ + σ 2 ∗
2rv − r21∗α
− σ 2τ − α 2r21∗ 2στ − στr 2κ∗ 2 + r 2v + αθr21∗ − στθ2r21∗ 2 + 1
n Mλ∗f (στ(rg + θβ
∗);στ).
(69)
Final scalarization: Using the strong law of large number (q, h, y, g,β∗ are entry-wise i.i.d.), we can rewrite (69) as
min α∈R, σ,v≥0 max r,τ≥0; θ∈R
− σ 2τ − α 2r21∗ 2στ − στr 2κ∗ 2 + r 2v + αθr21∗ − στθ2r21∗ 2 − r 2 1∗ + σ 2 ∗ 2rv − r21∗α
+ E [ Mρ(αr1∗Z1 + σZ2 + 1
rv (r1∗Z1 + σ∗Z3);
1
rv ) ] + E [ Mλ∗f̃ (στ(rZ + θb0);στ) ] · d n
(70)
where Z1, Z2, Z ∼ N (0, 1), σ∗Z3 ∼ Pϵ and b0 ∼ Π are all independent.
For LASSO, f̃(x) = |x|. The Moreau envelope Mλf̃ (·; ·) has property:
Mλ∗f̃ (στ(rZ + θb0);στ) = στ ·Mλ∗f̃ (rZ + θb0; 1). (71)
Besides, for ρ(x) = 12x 2 in LASSO, the Moreau envelope Mρ(·; ·) has explict form:
Mρ(v; t) = v2
2(t+ 1) (72)
and the second last item of (70) can be simplified to:
E [ Mρ(·)(αr1∗Z1 + σZ2 + 1
rv (r1∗Z1 + σ∗Z3);
1
rv )
] = E [( (α+ 1rv )r1∗Z1 + σZ2 + σ∗ rvZ3 )2 2( 1rv + 1) ]
= r21∗(αrv + 1) 2 + r2v2σ2 + σ2∗ 2(1 + rv)rv .
(73)
In order to simplify (73), we denote λ = 1rv in place of v. At this time, minv≥0 is replaced by maxλ≥0 and
r21∗(αrv + 1) 2 + r2v2σ2 + σ2∗
2(1 + rv)rv =
(α+ λ)2r21∗ + σ 2 + σ2∗λ 2
2(λ+ 1) . (74)
Substituting (74) in (70) we have the final optimization for LASSO:
min α∈R; σ≥0 max r,τ,λ≥0; θ∈R
− σ 2τ − α 2r21∗ 2στ − στr 2κ∗ 2 + r2λ 2 + αθr21∗ − στθ2r21∗ 2 − (r 2 1∗ + σ 2 ∗)λ 2 − r21∗α
+ (α+ λ)2r21∗ + σ 2 + σ2∗λ 2
2(λ+ 1) + E
[ Mλ∗f̃ (rZ + θb0; 1) ] · στκ∗
(75)
which is a smooth function with respect to α, σ, r, τ, λ, θ. Let ϕ denote the objective function of (75).
Deriving SEs from function ϕ: The SEs are given by the first order optimality conditions of ϕ :
1) For ∂ϕ∂α = 0:
− α στ + θ − 1 + α+ λ λ+ 1 = 0. (76)
2) For ∂ϕ∂σ = 0:
− 1 2τ − τr 2κ∗ 2 + r21∗α 2 2σ2τ − r 2 1∗τθ 2 2 + τκ∗E[Mλ∗f̃ (rZ + θb0; 1)] + σ λ+ 1 = 0. (77)
3) For ∂ϕ∂λ = 0:
r2 − r21∗ − σ2∗ + 2[(α+ λ)r21∗ + λσ 2 ∗] λ+ 1 − (α+ λ) 2r21∗ + σ 2 + λ2σ2∗ (λ+ 1)2 = 0. (78)
4) For ∂ϕ∂θ = 0:
r21∗α− στκ∗E[b0(Proxλ∗f̃ (rZ + θb0))] = 0. (79)
where we use the definition E[b20] = EΠX2 = r21∗ 5) For ∂ϕ∂r = 0:
− στrκ∗ + rλ+ στκ∗E[(rZ + θb0 − Proxλ∗f̃ (rZ + θb0; 1))Z] = 0. (80)
Since E[Z2] = 1,E[Zb0] = 0. For any function f̃(x), the Moreau envelope and proximal operator of f̃ stratifies
∂
∂x Mf̃ (x; t) = x− Proxf̃ (x; t) t . (81)
Then we rewrite the equation (80) as
rλ− στκ∗E[Proxλ∗f̃ (rZ + θb0; 1)Z] = 0. (82)
Using Stein lemma,
E[Proxλ∗f̃ (rZ + θb0; 1)Z] = E[r ∂Proxλ∗f̃ (rZ + θb0; 1)
∂x ]
= E[ ∂Proxλ∗f̃ (rZ + θb0; 1)
∂Z ],
(83)
(82) can be rewritten as
λ = στκ∗E[ ∂Proxλ∗f̃ (rZ + θb0; 1))
∂x ]. (84)
6) For ∂ϕ∂τ = 0:
σ 2τ2 − σr 2κ∗ 2 + r21∗α 2 2στ2 − r 2 1∗σθ 2 2 + σκ∗E[Mλ∗f̃ (rZ + θb0; 1)] = 0. (85)
For any function f̃(x), the Moreau envelope and proximal operator of f̃ stratifies
Mλ∗f̃ (x; b) = λ∗Mf̃ (x;λ∗b) = x2
2b −
[Proxf̃ (x;λ∗b)] 2
2b , ∀λ∗, b > 0, x ∈ R (86)
Using this property, we can rewrite (85) as
σ 2τ2 − σr 2κ∗ 2 + r21∗α 2 2στ2 − r 2 1∗σθ 2 2 +σκ∗E[ (rZ + θb0) 2 2 − [Proxλ∗f̃ (rZ + θb0; 1)] 2 2 ] = 0 (87) i.e.,
σ
2τ2 +
r21∗α 2
2στ2 − σκ∗ 2 E[(Proxλ∗f̃ (rZ + θb0; 1)) 2] = 0. (88)
Similarly, the equation (77) derived by ∂ϕ∂σ = 0 can be rewritten as
− 1 2τ − τr 2κ∗ 2 + r21∗α 2 2σ2τ − r 2 1∗τθ 2 2 +τκ∗E[ (rZ + θb0) 2 2 − [Proxλ∗f̃ (rZ + θb0; 1)] 2 2 ]+ σ λ+ 1 = 0 (89) i.e.,
− 1 2τ + r21∗α 2 2σ2τ − τκ∗ 2 E[(Proxλ∗f̃ (rZ + θb0; 1)) 2] + σ λ+ 1 = 0. (90)
Hence we get the SEs by summarizing equations (76), (90), (78), (79), (84), (88)
0 = − α στ + θ − 1 + α+ λ λ+ 1
0 = − 1 2τ + r21∗α 2 2σ2τ − τκ∗ 2 E[(Proxλ∗f̃ (rZ + θb0; 1)) 2] + σ λ+ 1 0 = r2 − r21∗ − σ2∗ + 2[(α+ λ)r21∗ + λσ 2 ∗]
λ+ 1 − (α+ λ)
2r21∗ + σ 2 + λ2σ2∗
(λ+ 1)2
0 = r21∗α− στκ∗E[b0(Proxλ∗f̃ (rZ + θb0; 1))] λ = στκ∗E[ ∂Proxλ∗f̃ (rZ + θb0; 1))
∂x ]
0 = σ
2τ2 +
r21∗α 2
2στ2 − σκ∗ 2 E[(Proxλ∗f̃ (rZ + θb0; 1)) 2].
(91)
regarding (α, σ, λ, θ, r, τ).
Since r2∗ = Eb0∼Πb20 = r21∗ κ∗ , the SEs (91) can be rewritten as
0 = − α στ + θ − 1 + α+ λ λ+ 1
(92a)
0 = − 1 2τ + r2∗κ∗α 2 2σ2τ − τκ∗ 2 E[(Proxλ∗f̃ (rZ + θb0; 1)) 2] + σ λ+ 1 (92b) 0 = r2 − r2∗κ∗ − σ2∗ + 2[(α+ λ)r2∗κ∗ + λσ 2 ∗]
λ+ 1 − (α+ λ)
2r2∗κ∗ + σ 2 + λ2σ2∗
(λ+ 1)2 (92c)
0 = r2∗κ∗α− στκ∗E[b0(Proxλ∗f̃ (rZ + θb0; 1))] (92d) λ = στκ∗E[ ∂Proxλ∗f̃ (rZ + θb0; 1))
∂x ] (92e)
0 = σ
2τ2 +
r2∗κ∗α 2
2στ2 − σκ∗ 2 E[(Proxλ∗f̃ (rZ + θb0; 1)) 2]. (92f)
regarding (α, σ, λ, θ, r, τ). This is equivalent to the SEs (12) except for the notations are slightly different.
C.1 EQUIVALENCE OF SES
We first rewrite r, τ , Z and b0 in (92) to γ2, τ2 and Z2 β2 respectively, the equation (92e) becomes
λ = στ2κ∗E[ ∂Proxf̃ (γ2Z2 + θβ2;λ∗)
∂x ] = στ2κ∗E[η′(γ2Z2 + θβ2;λ∗)] (93)
for f̃(x) = |x|. Then we simplify the SEs (92). Consider equations (92b) and (92f) and we have
στ2 = λ+ 1, (94)
substituting (94) in (92a) we have
θ = 1
λ+ 1 =
1
στ2 . (95)
For the second equation of AMP in (11), which is
γ1 = κ∗(γ1 + λ∗)E[η′(β1 + τ1Z1;λ∗ + γ1)], (96)
it is obviously equivalent to the equation (92e) if we have parameter transformations τ1 = γ2θ and γ1 = λ∗( 1 θ − 1). A property of η(·; ·) is used for the equivalence:
η′(cx; ct) = η′(x; t), ∀c > 0. (97)
Using the parameter transformations mentioned above and denote W = η(β1 + τ1Z1;λ∗ + γ1), the first equation of AMP in (11) can be rewritten as
γ22 θ2 = σ2∗ + κ∗E[W − β2]2 (98)
i.e., γ22 θ2 = σ2∗ + κ∗(E[W 2] + E[β22 ]− 2E[Wβ2]). (99)
Substituting (92d), (92f) and E(β22) = r2∗, we have
E(W 2) = E(η2(β1 + τ1Z1;λ∗ + γ1))
= E(η2(β1 + γ2 θ Z1; λ∗ θ )) = 1
θ2 E(η2(θβ2 + γ2Z2;λ∗)) (because η(cx; ct) = cη(x; t))
= 1
θ2
[ 1
τ22κ∗ +
r2∗α 2 σ2τ22
] (using (92f))
−2E(Wβ2) = −2E(η(β1 + τ1Z1;λ∗ + γ1) · β1)
= −2 θ E(η(θβ2 + γ2Z2;λ∗) · β2) = −2 θ r2∗α στ2 (using (92d)),
(100)
then (99) can be rewritten as
r2 θ2 = σ2∗ + κ∗
( 1
θ2τ22κ∗ +
r2∗α 2
θ2σ2τ22 − 2r
2 ∗α
θστ2 + r2∗ .
) (101)
Using (95) in (101) we have
r2(στ2) 2 = σ2∗ + σ 2 + κ∗(α− 1)2r2∗. (102)
Besides, for CGMT, the equation (92c) can be written as
(λ+ 1)2r2 − (α− 1)2r2∗κ∗ − σ2 − σ2∗ = 0. (103)
Using (95) in (103) we have
(στ2) 2r2 = σ2∗ + (α− 1)2r2∗κ∗ + σ2. (104)
The equation (102) and (104) are equivalent. Hence the equations (92d), (92f) and (92c) of CGMT can be shown to be a decomposition of the first equation of AMP in (11) after some parameter transformations. In conclusion we prove the equivalence between SEs from CGMT and AMP in Lasso framework.

heading: D RELAXATION PHENOMENON
text: D.1 RELAXATION PHENOMENON OF M-ESTIMATOR
Notice that (24) is equivalent to
min τ3,v
1
n n∑ i=1 ρ(vi) s.t. 1√ n ||τ3h+ v − ϵ||2 ≤ τ3√ n ||g||2. (105)
On the other hand, by rotation invariance of Gaussian distribution, (22) becomes
min ||w||2,v
1
n n∑ i=1 ρ(vi) s.t. ||v − ϵ+ ||w||2Z ′|| = 0 (106)
where Z ′ ∼ N (0, 1), ϵ := (ϵ1, ..., ϵn)T . Comparing (105) with (106) can verify the relaxation phenomenon, i.e. the only difference between AO and PO is that the feasible region of PO is a subset of the feasible region of AO.
D.2 RELAXATION PHENOMENON OF SUPPORT VECTOR MACHINE AND LOGISTIC REGRESSION
The relaxation phenomenon of support vector machine and logistic regression can be similarly shown as we have done in Appendix D.1, so we omit the proof here.

heading: E EQUIVALENCE OF SES OF LOGISTIC REGRESSION FROM LOO AND CGMT
text: By doing the following parameter transformations: α2 = √ κ∗α1, µ = r∗σ, λ2 = λ1, SEs of CGMT become:
0 = E[V l′(Proxλ1l( √ κ∗α1Z + r∗σV ))]
κ2∗(α1) 2 = (λ1) 2E[(l′(Proxλ1l( √ κ∗α1Z + r∗σV ))) 2]
κ∗ = λ1E[ l′′(Proxλ1l(
√ κ∗α1Z + r∗σV ))
1 + λ1l′′(Proxλ1l( √ κ∗α1Z + r∗σV )) ].
(107)
What we want to prove is that:
E[(l′(proxλ1l( √ κ∗α1Z + r∗σV ))) 2] = E[2ρ′(Q1)(ρ′(proxλ1ρ(Q2)))2]
1− λ1E[ l′′(proxλ1l(
√ κ∗α1Z + r∗σV ))
1 + λ1l′′(proxλ1l( √ κ∗α1Z + r∗σV ))
] = E[ 2ρ′(Q1)
1 + λ1ρ′′(proxλ1ρ(Q2)) ]
E[V l′(proxλ1l( √ κ∗α1Z + r∗σV ))] = cE[ρ′(Q1)Q1ρ′(proxλ1ρ(Q2))]
where c is a constant.
First, we verify the following identity:
E[(l′(proxλ1l( √ κ∗α1Z + r∗σV ))) 2] = E[2ρ′(Q1)(ρ′(proxλ1ρ(Q2)))2]. (108)
Note that
l(t) = ρ(−t) l′(t) = −ρ′(−t) l′′(t) = ρ(t)
Proxλ1l(z) = −Proxλ1ρ(−z)
(109)
and the probability density function (pdf) of V = GY is
PV (v) = 1√ 2π e− v2 2 2 1 + e−r∗v ,
we have:
E[(l′(Proxλ1l( √ κ∗α1Z + r∗σV ))) 2] = ∫∫ (l′(Proxλ1l( √ κ∗α1h+ r∗σv))) 2PZ(h)PV (v)dhdv
= ∫∫ 2(ρ′(Proxλ1ρ(− √ κ∗α1h− r∗σv)))2 1
2π e−
h2+v2
2 ρ′(r∗v)dhdv
(110)
where PZ(h) := 1√2π e −h22 is the pdf of Z. Meanwhile,
E[2ρ′(Q1)(ρ′(proxλ1ρ(Q2)))2] = ∫∫ 2ρ′(q1)(ρ ′(proxλ1ρ(q2))) 2PQ1,Q2(q1, q2)dq1dq2. (111)
Now we introduce the following parameter transformations: q1 = r∗v, q2 = − √ κ∗α1h− r∗σv. Then (111) becomes∫∫ √ κ∗α1r∗ ∗2ρ′(r∗v)(ρ′(proxλ1ρ(− √ κ∗α1h−r∗σv)))2PQ1,Q2(r∗v,− √ κ∗α1h−r∗σv)dhdv.
In order to verify (108), we only need to prove that:
1
2π e−
h2+v2 2 = √ κ∗α1r∗PQ1,Q2(r∗v,− √ κ∗α1h− r∗σv).
Construct Q′1, Q ′ 2 as follows: assume Z ′, V ′ i.i.d.∼ N (0, 1) and(
Q′1 Q′2
) = ( 0 r∗
−√κ∗α1 −r∗σ
)( Z ′
V ′
) .
We can easily verify that:
E[(Q′1, Q′2)T ] = (0, 0)T
Cov[(Q′1, Q ′ 2) T ] =
( r2∗ −r∗σr∗
−r∗σr∗ √ κ∗α 2 1 + r∗σ 2 ) which means (Q′1, Q ′ 2) has identical distribution of (Q1, Q2).
On the other hand, since
PQ′1,Q′2(q ′ 1, q ′ 2)dq ′ 1q ′ 2 = PZ′,V ′(h ′, v′)dh′dv′
dq′1q ′ 2 dh′dv′ = r∗ √ κ∗α1,
q′1 = r∗v ′, q′2 = − √ κ∗α1h ′ − r∗σv′,
we have: 1
2π e−
h′2+v′2 2 = √ κ∗α1r∗PQ′1,Q′2(r∗v ′,− √ κ∗α1h ′ − r∗σv′)
which completes our proof of (108).
Secondly, we prove:
1− λ1E[ l′′(proxλ1l(
√ κ∗α1Z + r∗σV ))
1 + λ1l′′(proxλ1l( √ κ∗α1Z + r∗σV ))
] = E[ 2ρ′(Q1)
1 + λ1ρ′′(proxλ1ρ(Q2)) ]. (112)
Left hand side (LHS) of (112) is
E[ 1
1 + λ1l′′(proxλ1l( √ κ∗α1Z + r∗σV )) ] =
∫∫ 1
1 + λ1l′′(proxλ1l( √ κ∗α1h+ r∗σv)) PZ(h)PV (v)dhdv
=
∫∫ 1
1 + λ1l′′(proxλ1l( √ κ∗α1h+ r∗σv))
1
2π e−
h2+v2
2 2ρ′(r∗v)dhdv
=
∫∫ 1
1 + λ1ρ′′(proxλ1ρ(− √ κ∗α1h− r∗σv))
1
2π e−
h2+v2
2 2ρ′(r∗v)dhdv.
(113)
Through parameter transformations q1 = r∗v, q2 = − √ κ∗α1h− r∗σv, RHS of (112) becomes
∫∫ 2ρ′(q1)
1 + λ2ρ′′(proxλ1ρ(q2)) PQ1,Q2(q1, q2)dq1dq2
=
∫∫ 2ρ′(r∗v)
1 + λ1ρ′′(proxλ1ρ(− √ κ∗α1h− r∗σv))
PQ1,Q2(r∗v,− √ κ∗α1h− r∗σv)r∗ √ κ∗α1dhdv.
Combining with
1
2π e−
h2+v2 2 = PQ1,Q2(r∗v,− √ κ∗α1h− r∗σv)r∗ √ κ∗α1
completes the proof of (112).
The proof of
E[V l′(proxλ1l( √ κ∗α1Z + r∗σV ))] = cE[ρ′(Q1)Q1ρ′(proxλ1ρ(Q2))]
can be derived similarly. So we omit the proof here.

Review summaries:
This paper provides derivations of equivalences between what they refer to as "state evolution" (SE) equations derived from different perspectives: convex Gaussian min-max (CGMT), approximate message-passing (AMP) and leave-one-out (LOO) approaches. They focus on M-estimators for high-dimensional linear regression. The SE equations describe the mean-square error reconstruction of the M-estimator.

This paper considers the state evolution equations obtained via different methods (AMP, LOO and CGMT), and it shows that their fixed points are the same for some high-dimensional inference problems (M-estimation, LASSO, and logistic regression).  Most of these state evolutions were obtained in recent work (which is properly cited here). An exception is Proposition 3.2, which gives the state evolution for CGMT in the case of LASSO. However, the proof of this result closely follows the existing literature. Consequently, the main novelty of this contribution is in showing that the fixed points (when unique) are the same for different methods. 

This paper compares the so-called "State Evolution" equations from 3 different derivations for the MSE of  high dimensional M-estimators in the proportional asymptotic regime (number of samples and features go to infinity at a fixed rate). There are currently 3 well-known frameworks for analysis in this regime: 1. Approximate Message Passing (AMP) 2. Convex Gaussian Min-Max Theorem (CGMT) 3. Leave One Out (LOO) The paper shows that there lies an equivalence between the results derived by the 3 methods via a parameter transformation. Two important special cases of LASSO and Binary Logistic Regression are considered and the results are clearly stated.