Equivalence of State Equations from Different Methods in High-dimensional Regression
Authors: Saidi Luo
Songtao Tian
Qian Lin
Venue: ICLR 2022 Submitted (2022)
Keywords: Approximate message passing
Lasso
High dimensional statistics

Abstract: State equations 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 high-dimensional 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 SE 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 this equivalence shed light on discovering a deeper structure in high dimensional statistics.

Under review as a conference paper at ICLR 2022
EQUIVALENCE OF STATE EQUATIONS FROM DIFFERENT METHODS IN HIGH-DIMENSIONAL REGRESSION
Anonymous authors Paper under double-blind review
ABSTRACT
State equations (SEs) were firstly introduced in the approximate message passing (AMP) describe the mean square error (MSE) in compressed sensing. Since then set of state equations have appeared in studies of logistic regression, ro- bust estimator and other high-dimensional statistics problems. Recently, a con- vex Gaussian min-max theorem (CGMT) approach was proposed to study high- dimensional statistic problems accompanying with another set of different state equations. This paper provides uniform viewpoint the equivalence their reduction forms, which causes that the resulting SEs are essentially equivalent and be converted into the same expression through pa- rameter transformations. Combining these results, we show that these different state equations derived from several equivalent reduction forms. We believe that this equivalence will shed light on discovering a deeper structure in high- dimensional statistics.
these methods and shows
INTRODUCTION
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 of state equations (SEs) were first introduced in approximate
message passing (AMP) algorithm in (Donoho et al. 2009 to precisely characterize the mean- square-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. 201T) investigated the phase transition phenomenon and the precise MSE of LASSO estimator; (Donoho & Montanari] (016) studied the variance of asymptotic distribution of M-estimator; (Huang, 2020) provided precise characterization of min-max MSE of 1 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 & Candè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 family of high dimensional problems through the Convex Gaussian min-max theorem (CGMT). More precisely, (Thrampoulidis et al. (001)) characterized the MSE precisely for general regularized M-estimator problem in nigh-dimensions: (Salchi et al.) 2019) established the correlation and MSE of the resulting estimator 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- RercinTers & Semerjian 2009 Moore, 2014. Krzakala et al. 2016 Coja-Oghlan et al. 20188] 8 Mézard & Parisi] 2003 Del Ferraro et al. (014)) 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-

---

Under review as a conference paper at ICLR 2022
cal physics. Importantly, this tool has exhibited as powerful weapon in applications of lot of Heels(Mezarr) & Montanari, 2009; Obuchi & Kabashima 2016 2016
Vuftray 2014 Lesieur et al. 2015
Though many papers have explicitly written down the corresponding state equations, none of them have shown that these sets of state equations compatible. To the best of 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 look logistic regression. The SEs derived from CGMT (20) in (Deng al. 2019) are obviously different from the SEs derived from LOO (19) in (Sur & Candès) 2019). This 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 heuristic expla- nation 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 different methods.
Outlines. In section 2, show that the SEs for M-estimator from AMP, LOO and CGMT equivalent to each other. In section 3.T 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 provides some discussions and future directions. Most proof's are deferred to the appendix.
Notations. Let (O, WO, 1) denote the d-dimensional standard Gaussian distribution and 1- dimensional standard Gaussian distribution respectively. For a vector æ, denote ||a||p as the Ip norm of æ. For an integer we denote [n] as {1.-.. n). We abbreviate independent and identically distributed i.i.d.. For a function f + E. variable F and O. we denote the Moreau envelope associated with ff as
Mj (z: = min f(z) + lz 2)2 2)²
(1)
sER
21
and the proximal operator, which is the solution of this minimization as
Prox = arg min f(=) + sER
(ar 2)2.
(2)
21
,,, E Rd Moreau envelope and proximal operator are applied element-wiscly, (x; = (My(rat)) Rd and Proz (x;;) t) (2, Rdd
For multi-dimennional case x = (I1, ... Fz)
2 AN ILLUSTRATIVE EXAMPLE
Suppose that x; sid N(, 4 and y, E R satisfying that
y, y = B + G, for E [m]
where e, are drawn i.idd from distribution P. with mean and variance of3 We assume that the entries 88 of 3 are independently distributed II which has finite second moment re E2-n
2

---

Under review as a conference paper at ICLR 2022
Let p be non-negative convex function. We are interested in the the Mean-squared-error (MSE) performance pimo. 1 B01 of the M-estimator:
β arg min
ply: xf
(4)
when both and d go infinity satisfying that lim ddd-2 d hia E (0,
This problem first studied by (El Karoui et al. 2013) where they showed that the MSE of 3 can be characterized by of SEs. More precisely, they proved the following proposition.
2013) Given ratio Na < 1. Consider the following system of nonlinear equations (SEs) regarding (T1, h):
Proposition 2.1. (El Karoui et al.
K. = E. @Prox
(Wi + +T
dr
(5)
K4 K == IE[W + TZ - Prox, + 21;11
where W1 Pe. (0, 1) is independent Wf : Ifthis system of nonlinear equations possesses a unique solution (Fi, A1), then the 5i is exactly the MSE of (3 appeared in (4).
The Messtmmator was also studied by (Donoho & Montanari 2016) where they proved the following proposition.
Proposition 2.2. (Donoho & Montanari of nonlinear equations (SEs) regarding
2016)
Given ratio K, < 1. Consider the following system
T2,
72):
A OM, 1
(W₂ + T2Zz2 22)
Ōr
(6)
82 Mp
N. A
(W₂ + TzZ2;; X2)
Ox²
where W2 Pe, ~N(0,)) 1) is independent of 22. this system of nonlinear equations possesses unique solution (F2, A2), then the ig is exactly the MSE of f 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 characterized by the the following SEs. To avoid unnecessary digression, we defer the detailed proof to the appendix A
Proposition 2.3. Given ratio Ri < Consider the following system of nonlinear equations (SEs)
regarding (Ta, a. u):
HM,
0 T3V Kr
E 412
(W3s + TzZ3; a/p)]
0M, / (W3 + 33Z3i
0 MVE. + E| dr
MM, (W3 + T3 7zZ3 a/p)]
0 +
E
P Öt
where W3 Pc, Zo (N 1) is independent Wa. a. 1f system of nonlinear equations possesses a unique solution (Fs, a. p.,, then the Ty exactly the MSE of B 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 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 alent. Specifically, (6) be converted into the same form 5 after the following parameter transformations:
LOO 5) and CGMT 7 are equiv-
T2
A1
(8)
3

---

Under review as a conference paper at ICLR 2022
can be converted into the same form as 7 after the following parameter transformations:
OR
A1
(9)
P
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 manuseript.
The proof this theorem is deferred to the appendix
GENERAL RESULTS
In this section, show that the aforementioned equivalence between different sets of SEs holds not only for M-estimator, but also for Lasso and logistic regression high dimensions.
3.1 EQUIVALENCE BETWEEN THE SES DERIVED FROM CGMT AND AMP
Let us consider the following optimization
1 |ly X,612 + 1.11 2
min
(10)
13 and A. 2 0 is the regularized where = =x +e, with x; iid. NOO, La) r. lim..pp-os Vn parameter, 6; are drawn i.i.d. from distribution P. with mean O and variance of.
performance li 11 3 of the LASSO. (Donoho al., (011). (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.
We are interested in the the Mean- Bean-squared-error(MMM.
Proposition 3.1. Mousavi et al. 2018) Given noise scale o² and ratio R., consider the following system of nonlinear equations (SEs) regarding (Ti ").::)
7 = + (11 + Z1; X, 71 31)² "1 k> + A. E |/ (81 T ZZ + +1)
(11)
where Z₁ (N,01) 1) is a standard normal variable, 31 II independent of Zz. n1())) is the soft threshold function:
n1=;t) (la) 1)+
F. means max( 0} and
1 if 0
sign(z) =
0 ifz= 0.
if 0
If this system of nonlinear equations possesses a unique solution (1, then the in is exactly the MSE of 3 appeared in 10
Inspired by the sequence of work (Thampouliddi et al. 2014 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.
2015 2018 Salehi al. 2019),
4

---

Under review as a conference paper at ICLR 2022
Proposition 3.2. Given noise scale of, signal strength r2, in model (3) and ratio Ra. Consider the following system of nonlinear equations (SEs) regarding (a, o, T2, 0, A, 72):
a x+ A
+
TT2
X+1
0
2r² + 20
T2k.
E[ (P2r *
2
A+1 (a A)3 + 0² + X²
1/ - K4 - + 21(a + A)r + Ao
X+1
(A + 1)2
(12)
K.O a - 022k E[ Pror ( 72 + X.)]
Orrox yl (72Z2 + 082; X.)
022 E
dx
o
k.aa
ok.
+
E Proo (2222 082; X.))
2T
2012
2
where Z2 N(00,) 1) is standard normal variable, B2 il independent of Zz f(z) |z] If this system of nonlinear equations possesses a unique solution (ā, o. T2, 0, X, 922, then the Ay exactly the MSE of [3 appeared in (10
The detailed proof is deferred until the Appendix C The following proposition illustrate the equiv- alence between these two of SEs.
Theorem 2. The SEs of LASSO derived from AMP (TT) are equivalent to the SEs derived from CGMT (T2)- Specifically, (72) can be converted into the same form (TT) after the following parameter transformations:
72
71
X.
(13)
The detailed proof is deferred until Appendix
C.1
We provided heuristic explanation 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
I) AMP first transform initial optimization problem into pursuing Bayesian posterior distri- bution where objective function is transformed into probability distribution.
2) Based on the corresponding factor graph of this distribution, invokes the message pass- ing(MP) algorithm to compute the Bayesian posterior distribution.
3) The MP is then further approximated by some large system limit, large 3 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 min-max form, which is called the primary optimization (PO) problem.
2) CGMT perform 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 vari- ables, which is called scalar optimization (SO) problem.
5

---

Under review as a conference paper at ICLR 2022
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 relaxation of PO in the sense that the feasible region of AO 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 AMP and CGMT: 1) Constructing the AMP corresponds to the first step CGMT LASSO, which suggests that iteration AMP is actually equiv- alent 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
(Rangan et al. 2016) For LASSO, the fixed point of AMP is just the solution of first-order optimality conditions of PO in CGMT.
Proposition 3.3.
Proof. For CGMT, by introducing u to constrain u PO can be written as:
X,8 and Lagrange vector v, the corresponding
min max
2 | yd u yyl1 + A. |1 (XB - u).
8.u
Consider the first-order optimality conditions of PO:
X, sign(( X
0 = u - - v
(14)
u X,3.
Comparing above formulas in 14 leads to
X.sign( + X T (X, - y) =0
For AMP algorithm, the iteration LASSO
g++1 = n1 +
x
20 A. + 7²)
z y X,3 +
(B 1 + xt=111; 1; + x1-1))
dr
n² k. (A. +
x A ((1))
Oa
where á acts component For some vector x, (x) Σ xy denotes the entry-sum of æ.
dz
The fixed point ( x x,, ,xx) satisfy the following equations:
0 = (X, + 7)sggn())) + --- 1-
(15a)
y X,3 + c
(15b)
(A. +70
(15c)
where c(B, 2, about the soft thresholding function:
az ( X 2x Ar + 7)) and 15al is given by the following property
t. sign(z) - 0
for 2 = 7)(;; t) and some scalar ar
Simplifying (15b) and (15ch leads
z y - XX3
1 KCC K,C),
(16)
7 C

---

Under review as a conference paper at ICLR 2022
Comparing (16) with 15a gives,
X
sign(
(y-33) O.
R.C
1- K4C
which finishes the proof.
Remark 3.2. needs to be discussed component-wisel. according to whether each entry of the optimal [ is 0 not. The above proof holds for the entries that B; + O. For i such that B; 0, the optimality from PO gives -X, + [X"(3 y)); < and X2 + (X" (X33 y)) > O. This is equivalent to (x" (X33)) (x3-y))dl Xr, where (X" (X3 y)), denote the i-th entry of
X (X33 (X3 y). This is still equivalent to the fixed-point condition in AMP. Hence the equivalence holds for all entries of B.
3.2 EQUIVALENCE BETWEEN THE SES DERIVED FROM CGMT AND LOO
Suppose that x
No, à Ia) and ys E (-1,1) drawn from logistic model: itd ~
ply, - 1/x,) - o'xx for i [n]]
(17)
where p(t) log(1 te). Each entry of ß is independently distributed as which has finite second moment r 1B
We are interested in the following optimization problem:
3 arg min B n
-
(yxTT9
(18)
where ((t) = log(1 + e- When the 3 exists, we are interested in the the Mcan-squared- error(MSE) performance lim A 3 112 of the Logistic regression.
Logistic regression in high dimensions have been studied recently by (Candès & Sur 2020: Mousavi et al. 2018). Deng et al. 2019). The asymptotic MSE of 3 was characterized by the following two propositions.
Proposition 3.4. (Srr & Candès 2019 Given signal strength r in logistic model 17 and ratio Ky, Consider the following system of nonlinear equations (SEs) regarding (A1, a1.
1 a El2p' (Qi) (Pr
R
0 Elp' (Q1'(QQ)) (101)QQ>>p (Prox, (Q2; X1))
(19)
2p' (Q1)
K. E[ \1p" (Prox,
where
(2) ~ N N(D:
2
- or?
o2r2 + asks -
and p(t) == log(1
If this system of nonlinear equations possesses a unique solution (A1, oi, o), then the MSE of (3. appeared in 188 is [(ō 1)E33133 +
Remark 3.3. In (Sur & Candès 2019), it is assumed that Xi,j ~ NO n La) and rス k. E. which is slightly dijferent Jrom the setting in this paper. However, this difference only leads constant change related to K., 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 r...
Consider the following system of nonlinear equations (SEs) regarding (A2, a2 p):
0 = EVVE E (Prore(or 7 + μV; X2))
az = (E
+ μV; 2
(20)
(PPoo + pV;
K= = A
I+ (roocsozz2 x2))
7

---

Under review as a conference paper at ICLR 2022
where Z 1)) V Z,Y,.. in which Z1 1)) is independent of Z and Y,, Ber(p'(r.Z.)) Ber(p) denotes the Bernoulli distribution with probability p for the value +1 and probability 1- for the value -1. If this system of nonlinear equations possesses unique solution (2,,02, P., then the MSE of B3 appeared in 18) is [( Ve. 1) (
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 (00 are equiv-
alent. Specifically, 1 can be converted into the same form 120 after the following parameter transformations:
02
11
01
A1 = A2.
(21)
R4
Fx
The proof of this theorem is deferred to appendix
B
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 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 3, b) leaving one predictor, corresponding solution is denoted as 3(-5) and c) leaving one predictor and one observation, corresponding solution is denoted ((-)).(-))
2) Two properties derived from comparing three version of first-order conditions: a) The i-th fitted value X has an asymptotic expression composed of independent random vectors (-)())) and B(-)),(-))- b) Each coordinate By can be written as sum of n random variables which are asymptotically independent.
3) Using above two properties, B, has the same distribution as combination of several scalar variables when n. + oc. Hence every statistic of & (such as expectation, variance and first order condition of optimization) be expressed by these scalar variables, from which the SEs of B are derived.
Briefly reviewing the procedures of LOO approach, we find that the sample matrix X (which is Raxp 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 first- order 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.
4 DISCUSSION AND FUTURE DIRECTIONS
In this paper, 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 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 respectively. The equivalence between these SEs sheds us light on looking for more comprehensive theories explain this intriguing phenomenon.
characterized by the corresponding SEs
8

---

Under review as a conference paper at ICLR 2022
REFERENCES
Jean Barbier, Florent Krzakala, Nicolas Macris, Léo Miolane, and Lenka Zácborová. Optimal errors and phase transitions high-dimensional generalized linear models, Proceedings of the National Academy of Sciences, 116(12):4551-446 2019.
Mohsen Bayati and Andrea Montanari. The lasso risk for gaussian matrices. IEEE Transactions on Information Theory, 58(4): 2011.
Emmanuel J Candès and Pragya Sur. The phase transition for the existence of the maximum like- lihood estimate in high-dimensional logistic regression. The Annals of Statistics, 48(1):27-42, 2020.
Amin Coja-Oghlan, Florent Krzakala, Will Perkins, and Lenka Zdeborová. Informatiin-theorrtic thresholds from the cavity method. Advances in Mathematics, 333:694-795, 2018.
Gino Del Ferraro, Chuang Wang, Dani Martí, and Mare Mézard. Cavity method: Message passing from physics perspective. arXiv preprint arXiv:1409.3000 2014.
7eyu Deng, Abla Kammoun, and Christos Thrampoulidis. A model of double descent for high- dimensional binary linear classification. arXiv preprint arXiv:1911.05820 2019.
David Donoho and Andrea Montanari. High dimensional robust m-estimation: Asymptotic variance via approximate message passing. Probability Theory and Related Fields, (66(3):935-966 2016.
David Donoho, Arian Maleki, and Andrea Montanari. Messuge-passing algorithms for com-
pressed sensing, Proceedings of the National Academy of Sciences, 106(45): 2009.
David L Donoho, Arian Maleki, and Andrea Montanari. The noise-sensitivitty phase transition in compressed sensing. IEEE Transactions on Information Theory, 57(10))6920--944, 2011.
Noureddine El Karoui, Derek Bean, Peter Bickel, Chinghway Lim, and Bin Yu. On robust regres- sion with high-dimensional predictors. Proceedings of the National Academy of Sciences, 110 (36): 1555:-4455144 2013.
Hanwen Huang. Asymptotic risk and phase transition of Annals of Statistics, (8(5):3000-3111, 2020.
robust estimator. The
Adel Javanmard and Andrea Montanari. Debiasing the lasso: Optimal sample size for gaussian designs. The Annals of Statistics, 46(6A):2593 2018.
Florent Krzakala, Federico Ricei-Ters,nghi, Lenka Zdeborova, Eric W Tramel, Riccardo Zecchina, and Leticia F Cugliandolo. Statistical Physics, Optimization, Inference, and Pessage-Passing Algorithms: Lecture Notes of the Les Houches School of Physics: Special Issue, October 2013. Number 2013. Oxford University Press, 2016.
Thibault Lesieur, Florent Krzakala, and Lenka Zdeborová. Mmse of probabilistic low-rank ma- trix estimation: Universality with respect to the output channel. In 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 680-687. IEEE, 2015.
Thibault Lesieur, Caterina De Bacco, Jess Banks, Florent Krzakala, Cris Moore, and Lenka Zde- borová. Phase transitions and optimal algorithms in high-dimensional gaussian mixture clus- tering. In 20/6 54th Annual Allerion Conference on Communication, Control, and Computing (Allerton), pp. 601-608. IEEE, 2016.
Mare Mezard and Andrea Montanari. Information, physics, and computation. Oxford University Press. 2009.
Mare Mézard and Giorgio Parisi. The cavity method at zero temperature. Journal of Statistical Physics, 111(1))-33, 2003.
Léo Miolane and Andrea Montanari. The distribution of the lasso: Uniform control over sparse balls and adaptive parameter tuning. arXiv preprint arXiv: 1.01212 2018.

---

Under review as a conference paper at ICLR 2022
Cristopher Moore. The cavity method, belief propagation, and phase transitions in community detection. In APS March Meeting Abstracts, volume 2014, pp. D14-002, 2014.
Ali Mousavi, Arian Maleki, and Richard G Baraniuk. Consistent parameter estimation for lasso and approximate message passing. The Annals of Statistics, 46(1): 19-148, 2018.
Tomoyuki Obuchi and Yoshiyuki Kabashima. Cross validation in lasso and its acceleration, Journal of Statistical Mechanics: Theory and Experiment, 2016(5):053304 2016.
Sundeep Rangan, Philip Schniter, Erwin Riegler, Alyson K. Fletcher, and Volkan Cevher. Fixed points of generalized approximate message passing with arbitrary matrices. IEEE Transactions Information Theory, (211))7464-74774 2016.
Federico Ricci-Tersenghi and Guilhem Semerjian. On the cavity method for decimated random straint satisfaction problems and the analysis of belief propagation guided decimation algorithms. Journal of Statistical Mechanics: Theory and Experiment, (009(09))P09011, 2009.
Fariborz Salehi, Ehsan Abbasi, and Babak Hassibi. The impact of regularization on high- dimensional logistic regression. arXiv preprint arXiv: 2019.
Pragya Sur and Emmanuel J Candès. A modern maximum-likellhenn theory for high high-dimensiioal logistic regression. Proceedings of the National Academy of Sciences, 116(29):14516-1455 2019.
Christos Thrampoulidis, Samet Oymak, and Babak Hassibi. tight version of the gaussian min-max theorem in the presence of convexity. 2014.
Christos Thrampoulidis, Samet Oymak, and Babak Hassibi. Regularized linear regression: A precise analysis of the estimation error. In Conference on Learning Theory, pp. 1683-1709, PMLR, 2015.
Christos Thrampoulidis, Ehsan Abbasi, and Babak Hassibi. Precise error analysis regularized m-estimators in high dimensions. IEEE Transactions Information Theory, 64(8):5592-562) 2018.
Mare Vuffray, The cavity method in coding theory. Technical report, EPFL. 2014.
10

---

Under review as a conference paper at ICLR 2022
A PROOF OF PROPOSITION 2.3
By the following linear parameter transformation:
w := B 3" 3",
the M-estimator optimization problem becomes:
min Σ
p(e: - x xx, w))
(22)
1=1
Introducing the Lagrange multiplier leads to:
min max
Σ p(vz) + vn
ur(u; - ci + x
W0,3 71
where u. = (ui,.... M, = (UI,..., v.))
Then we rewrite it in the matrix form:
n
min max 8. &
Vn u X
Σ
p(us) + - (u² u E)
n
where e == (El,,.., ? This is just the PO problem in CGMT.
Denote X = VTX, v
s then we have Xz, i.i.d. (N0 1), = 8-8" This means ||/|| vn
just the MSE of interest and X a standard Gaussian matrix composed of iid standard normal variable.
However, in the following, we rewrite X, v 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 the following min-max problem:
1
1 (u v uTe E)
min max
p(vx) + [ w + /1 u)) + Σ 1=1
vn
where g E Rd and h E R have i..d. N(0 1) entries.
Let ||ll|22 73, note that now
33 |/3 1-1
(23)
which is just the MSE.
Then the optimization becomes:
(i-Ts|uu|lzlgn T3hTun + p(u;) + 1 _ - ue)).
min max V3.0 t
vn
Letting |uila = then We have the following optimization:
min max
Tall vn
12
1
Σ
p(u))
Th ccl22
(24)
na.0 420
vn
equivalently:
min max Ta p20
Σ p(v)) + pl
13h + + -cl12 T3
(25)
vn
vn

---

Under review as a conference paper at ICLR 2022
In order to make the 11rhh + c/12 separable, use the following optimization:
x²
x min
a>0
2
2a
for any x and O. Replace by v 13h + c|12. the optimization problem 25
becomes:
min max 13.0
Tal 1
Σ ((v) (max
n
1
13h + v
e el
2am
Then what optimization about a scalar. First, flipping in the order of min-max by (Thrampoulidis et al. 2018
do the scalarization procedure: make the optimization about becoming
min max 73.4
73/4 vn
ggll2 + mmin Σ plvi) +
H (rah, + - =).
(26)
2a
Introducing Moreau envelope function Mp(r; t). the optimization problem (26)
becomes:
" Σ
min max
aj
Tsf
vn |gl|2 +
Mple - T3h;
73.0
2
By Lemma in Appendix A in Thrampoulidis et al.
2018 considering asymptotic n, p 7
00: p/n k" leads
ap Tall 1gll2 Vn
Σ
Mpla (glaaahhhaapp) 3 01p
T3K/K, EM,(W, 73Z3:a/P1
where Z3- _N(0,1 1) is independent of everything else.
Introduce W3 ~ Pe. Then, asymptotically, we can deal with the following problem:
ap -S + EM,(WW, + TzZ:a/1)
min max
(27)
Ta.a F 2
Denoting the objective function of (7 by d, then since á is convex about (73, a) and concave about 14, the saddle point of & can be precisely characterized by its first order optimality condition:
06
aM, (W, 133733///11
0 =
2 T3
1 EE
0p
at
de
= 0 7 -KVE. + E MM,
(W3 + Ty Zz: 23300/111))
Ør
dr
0ø = 0 "
0Mp
2 E
(W3s + TzZ3: a/1)] =0
da
Øt
Combining with 23 completes the proof.
B EQUIVALENCE OF SES OF M-ESTIMATOR FROM AMP, LOO, CGMT
Recall that the SEs of M-estimator from LOO are:
Orroz
K.
(W1 + Z1;1;
dr
(28)
K4 T = E(W + 71
Prox, (Wi + Ti Zz)
SEs of M-estimator from AMP are:
0M, (W₂ T2Zz;
- Ko
A
dr
(29)
8 M
K₂ = AxE
(Wz + T T2)2)
dx
12

---

Under review as a conference paper at ICLR 2022
Next, show that these two sets of SEs are equivalent.
First, Simple calculation leads to:
(x, p((Proz,(z;;)) dr
8 M M,, (Proz Ox.
(2; θ @rronpla; ("(Pron((5;1))
(30)
Ox
1 (Prox
Prox, (x;t) ('(rozz(xxtt)
Combine this, SEs from AMP can be rewritten as:
2 1 E (Pror, ( (W2 T222; A2]]]²
(31)
A d (Pror ( 2 + 72 Z2; 12))
(Prox [W, T2Z2i
which verify that SEs from LOO and SEs from AMP are equivalent.
Next prove equivalence of SEs from AMP and SEs from CGMT by parameter transformations suggested.
Recall the SEs from CGMT
OM,
TaVk, 122 Ōt
(W3 T3Z3; a/p]
2
412
-KVK, + E[ 0Mp
(W3 + Ta Zz: a/1)) = 0
dr
1
0Mg
+ E
(W3 + T3 T3233 0.
2 11
01
Let b 2. then have:
jub
0M e (W3s + TzZ3;b)] =
Ta KR.
E
2
112
Øl.
UM,
MVR. R.. + E|
(Wg + TzZz;b]]
Ōr
aM
+ E
(W + +Z;bb]] = 0.
2
Oy
Comparing these results leads to:
MM, (W3 + b3)
T2 82
8d
E
E
(W3 + Tz]3;b)]
(32)
dr
dx2
Combining stein lemma and
MMp Øt
1 0r
1 M.M
(W3 b))
-
(Wa bT]3;b))
(33)
completes our proof.
C EQUIVALENCE OF SEs OF LASSO FROM AMP AND CGMT
In this proof, we refer to the technique developed in (Donoho & Montanari 2016). The Lasso problem solves
13

---

Under review as a conference paper at ICLR 2022
X
arg min
|| + ly - X,312 2n
(34)
Notice that lyy - X,312 =>= [ into
2y,r, B + v.
The optimization can transformed
arg min B
-
||
n
(c) (r] y 3
(35)
In the following proof, we consider more general optimization than Lasso:
arg min ((B) Σ 12
(36)
where p(-) and f(+) are "separable" in the sense that there exist scalar functions p(.), f(-) so that p(-) and f-)) can be expressed as the following form: p(x) = (p(x1), -. p(za)) and f(x) =
f(x)) In particular, in Lasso, p(t) = 1 and f(x) |
In order to apply CGMT, we introduce a new variable u and have following optimization
min f((3 + (17 p(u) - y²²u) B.u
(37)
1
== X3
Ha
Vn
Ltd NOO, 1). By using Lagrange multiplier we where H' VnX Raxd and hence H rewrite 37 as min-max optimization:
1 y u max T p(u)
A |1 + v=(n (u
min BER" MER"
H)
(38)
n
vn
Denote P (,*) as the projection matrix of true signal 3 and p- = la P as the orthogonal
||
complement. To apply CGMT, we need first decompose H into
H H
H = H P... H Hi Hr.
(39)
In addition, Recalling the linear model 3 have y X,3 +6= 1 H'
- 1H, Hence Vn
vn
38 can be rewritten as
1 max - p(u) y u n n
((3) 1 - (u
1
1 " H2G. (40)
min mERn
Hi3)
n
nyn
By using CGMT for a H3 as in Salehi al. 2019 by Corollary 3 in the corresponding AO of 44 is
max -1 1 p(u) 1 -y u
A ((3) +
1 - (u H13)
min HER"
Vn
(41)
nyn (uTh| B||2 + ||0|21 T Tp! 33)
where h No In) and N(O,, Ta) two independent gaussian vectors.
14

---

Under review as a conference paper at ICLR 2022
We first consider the maximization with respect to the direction of The part related to in optimization 41 is:
max VER" nVn
10llggppPBBBp B _o-
u H
vn
h 1111 (112))))1))
(42)
Denoting
|ella
and maximizing along the direction of v give va
('
|| B h112
maxr
3+ +1 u H
(43)
r20
vn
Inserting this into gives
A ((B) +r g" min max 1dT p(u) y"uu+ Buu r20 n n
| B112
vn u
H3
n
n
n
(44)
In addition, introduce μ to replace ,3 in ||3]]] Lagrangian and w. Then
can be rewritten as,
min 1 T p(u)
1 y
aut A. f(1) +
g
n Buaad wead
n
(45)
1
| B112
1 zw0 ( B). d
+ r
u
H
vn
We define Gaussian vector and
," gr | 1
1
|P
B1|2
and q
where r1.
1 llz Vn
Then q is standard
Vn
H'
d a
HiB = (P3)
33
Tix nqq.
(46)
Decomposing w (P + p )w, then the last item in (55) can be rewritten as
1 w ( 3) (Pw) T u + 1 (p 1 (Pw) 1 (P-
(47)
Inserting 46 and
into
we have,
1 Ty
d f(w) +r (- ( (P-
min
max - T p(u)
n1
(48)
ar1.
T + 1 (PW) u (p)
w) 4 (Pw)
+
u
q
Vn
Then we can fix P3 and consider the minimization along the direction of P+B. Considering the optimization related to p B, we have
min Lg" p- 3 7 (P- P-g n
= min _
-
P
P-B
d
= B1
r p
p w
(49)
n
r
=
p
w
v
dr
15

---

Under review as a conference paper at ICLR 2022
Notice that 48
reaches optimal when p
B. Inserting (49
into (8 leads to
1 A ((1) - a. 1n P g v
min A =R0020
max = +20; n werd
T
p(u)
-V
11
u1
+
n1
vn
dri.
wil
(50)
071x
-h h
+ (P
q
Vn
Vn
vn
For the simplifying procedures in the following steps in our analysis, we change || -/12 + +|1.1 by
rz = min FV 2
+
2v
(51)
2 2 2
0x max
T20
2T
Applying (51)
we are able to rewrite (50
min uER*, oeR",
max -1" p(u)
1
-1 u
A
-
f())
0T
P
P
we2d4 T
2T
2
v1
dri.
1,20
TU
ar1
σ
h
1
p w)
2v
/n
vn
Vn
d
(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
OT
9 - V
pl w
+ j
(P''w)"
(P
w)
2
Vn
dx
oT
vn
P-1 9
V
dki,
1
plw
w
vd/RoOT
p-
(53)
OTT2
|| 4 orrp!
g|?
| gl1
2noT
2n
1) For the last item in 533. since g NNO. Ia) and p is a (n 1)- dimensional projection
matrix, we derive that | gl1
|[(0 (P }3) d xa_ and
0rr
a.s. OTT
I
g
(54)
2n
2
2) Since p. = Ia P, the second item in
53 can be rewritten as
p p + o
gl|
l| + orrgl? 1
_ PPll
71
(55)
(OTr)?
20Tr
Pgll
(Pg) μ.
| Op(
The last two items of 55 can be omitted in the limit of d. - oc because
n
and _ (Pg))" μ O,( The second item of (55 is =1 PM| 1 P3] a² 2r by definition.
3) The first item in 153 reaches 0 when maximizing w.
The optimization 52 can be rewritten
16

---

Under review as a conference paper at ICLR 2022
X f(v)
1
a²r9.
OTr hi
min
max -1---- 11" p(u)
y
1f
u
+
k +
orrgll
uea peRd, 6,720
n
2r
2not
20T
2
oER,v..20
r
ru
1
a71
0 h
+
+
u
2v
2
vn
Vn
(56)
Optimization respect to μ.: Consider the items related to f in (56
d
min MERd
I(m) |1 otrgll
2noT
(57)
s.l.
1 B.
Notice that y ~ NO, Ia), |/ orrgll3 || orrgle. We rewrite as
A min - f(w) +
2not 1| otrgl
HER
(58)
8.1.
g μ = n n
g
-aari arr
Introducing Lagrangian 0, (58) can be rewrite as
d f(L) r # +
min max eERd PER 2not
|| arrgl
(59)
Applying the completion of squares to 1,3 items in 159 we have,
0
2n0t 1 orrgl
1
11 otrg -orrg-orrrra 11
2nat (0oT)²
(60)
0ra²
11,3-112
2not g 1
2noT
The third item can be omitted since g² (0or)²
Opl and the second item has limit
||
(0or)²
2no7 nr?. =
Hence we rewrite right side of (60 as
2no7
g
1l orrgll T μ
2not || a
(61)
2no7
Next, denote f(xx) single-entry form of (x)) We can rewrite the (61 in terms of Moreau envelope entry-wisely as follows
0 Be - f(w))
X
min max eERd 2not || 2rrg|12
μ + atri.
n
n
(62)
max - M, M, ((r(() + a0r? n
OT02
Substituting 62 in 56
we have,
1 TT p(u)
1 Ty u
1 1.
a²r?
min
max vor 11 BER
11
nn
n
2T
20T
(63)
GTT 2 K.
r
OTR2
+
+
My, (oT((g+ + (3"):00) + adn
2
2v
2
17

---

Under review as a conference paper at ICLR 2022
Optimization respect to u: First we consider the items related to The optimization is
min 1" p(u) y + 2
ru ar1
0 v
h
(64)
uER
vn
vn
Applying the completion of squares we have,
1
T
TU
1
OF
f
TU
1
af1+
Vni h
1
y/
2
71
2
2
v1l
vn
ru
(65)
|1v12
rla0
a
y q
y The h.
2run
n
Using the strong law of large numbers we have,
|181| 0.g. 1 + o²
2ron T1+at
2rv
T
0.3- -ra.a
(66)
0.3 0. vrhh h
Next, by substituting 65
666 in
64).
rewritten the optimization as,
min uER
1 1T puu)
T
TV
11
Of''s
2
Vn
V
n
Vn
min
pu) +
TU
1
u
aT
q
h
(67)
uER
2
n
TU
12
7 +
2ro
Then we can rewrite (67) in terms of Moreau envelope,
min -1T p(u) +
1
rv
1
Or
q
h
1
!
"ER" n
2
vt
n
vn
ru
r
n
(68)
1
1
1
M Maolariiq + oh +
y;
rv
Substituting 66
668
in
66
we have
1
1
14. + 0
min oC3: 2,020
max T20 dex
M Ma
oh
_
rv
2rv
a²r7.
OTT r
(69)
atr?
2r
20T
20
1
033))
Final scalarization: Using the strong law of large number (q, h, y. g, 3 are entry-wise i.i.d),, we rewrite (69) as
18

---

Under review as a conference paper at ICLR 2022
min max oee 2r e.e20 dek
0
a²r9.
OTT
K4
+
r
+ atrr.
oT82r9.
ri. t
ri.
2T
20T
2
2v
2
2ro
E Mp(ari.2. 21 0
(ri. Z1 + o. Za);
(70)
M (o (1 (100):0r) R
where Z1, 22, (0, 1). 0.23 P. and by 11 are all independent.
For LASSO, f(z) = |z|. The Moreau envelope Mx has property:
0bo): aT) oT My, jrZ + 0bo: 1).
(71)
Besides, for p(x) = _x²² in LASSO, the Moreau envelope M has explict form:
Mp(c;t) = 2(t + 1)
(72)
and the second last item of 770 can be simplified to:
E M Mac)(ari-Z) + o22 + - + to _ E
((a + 1 11 + 0 + ru 7s)
ru
2 +1)
r (arv + 1)² + 22 + +
re)rr
(73)
In order simplify
73 denote
in place of At this time, min.20 is replaced by
maxx2o and
(arv 1)2 2220 + o²
(a 2)2 0 + o?X² 2(A + 1)
(74)
2(1 + rv)rv
Substituting
(74) in 70
we have the final optimization for LASSO:
min
max agR: #20
0
OTT
Ke
+
22
+ a00? 1x
OT021
(1 +
17.0
2r
20T
2
2
2
BeRl
(a + 1) + 0² + 0112
M f(7 + Abo: 1)] OTKK.
E.
2(x+1)
(75)
which is smooth function with respect a, a, A, Let denote the objective function of
75
Deriving SEs from function di The SEs given by the first order optimality conditions of o
1) For de de
O:
a+ À + 14
X+1 0. OT
(76)
86 2) For
Za
1
2
T..0 2
T0
+ TK,
E[M ELM,, 0bo: 1)]
X+1 0. (77)
2T
20
19

---

Under review as a conference paper at ICLR 2022
3) For Be 0: 8x
21(a + A)ri. Ao
(a+ 1)3 + +2202
72 ri. o +
=0.
(78)
A+1
(A + 1)²
4) For 06
00
ri. OTK, Boe (Prox x. (ProO + 0b.))) 0.
f(2
(79)
where use the definition [[b]]] E11 = r2.
5) For de 0: Dr
OTTK, rA + OTK, B(rZ + Obo Proæ x, j 0bo: 1))2] 0.
(80)
Since E| = 1, E|bbl] = 0. For any function f(x), the Moreau envelope and proximal operator of f stratifies
T - Proxtf(1;1 (1;() Or (((tt))
(81)
t
Then rewrite the equation
80 as
r OTK, Eroox (r + bbo; 1) 0.
(82)
Using Stein lemma,
Prror, x, (( Abo: 1)
E P (rZZ Abu: 1)2 Eir
Ox
(83)
OP OProz frZ + Abo: 1)
E
07
82
can be rewritten as
Orrox x, j(r + Abo: 1))
OTR.E.
(84)
Ox
6) For 8r
σT 2 K+
ri.a²
12.002
+ tOR,E|M, Fr, + 0b;: 1)] = 0.
(85)
2r2
2
20T²
2
For any function
f(x), the Moreau envelope and proximal operator of f stratifies
x²
[Proz X.b)a
Mx, = (0;
1,,b>0,.E
(86)
2b
2b
Using this property, we can rewrite
85
as
2 K4
12. a
(rZ + (rZ+0b)) 06,)
[Proz "irox,,irTZZ + 0b;: 1)]²
+ tox,
2r2
2072
(87)
i.e.,
2 112
ok
+
E [Prox x- f 0b,; 1)) = 0.
(88)
2,2
2072
2
20

---

Under review as a conference paper at ICLR 2022
Similarly, the equation
77
derived by De Öe
0 can be rewritten
Tr²K,
19
a²
(rZ 0bu)
[Proxx, f(r2 + 0bo; 1)]2
TR, E
1+
2r
2
2
x
(89)
i.e.,
1 a²
The E (rror (Pr (r777
+ 0b;; 1))
+ +
(90)
2r
20
2
Hence we get the SEs by summarizing equations (76). (90). (78).
79
84
a
a+
0
+
1+
X+1
The
El(Pron ((PProx,,(122
0 (])]] (bbb A 1 (a+ 2)2 + t + X²
Obo:
2r
20
2
2 + A)r + Ao
0 == 2 2 0²
+
x+1
(A + 1)2
(91)
0 r.a OTK, Elbol (Prox X- (r 2 + 0bo; 1))]
OProz, (rZ 1 + obu: 1))
X = OTK, E'
dx
0 272
ahe
E((Pronx, + Bbo: 1))
20T2
2
regarding (a, o, X, T)
Since r Ebo
Di the SEs
(91)
can be rewritten as
X
+ 0 1+
(92a)
OT
A+1
1
a²,
THe E E| (rZ + 0bo: 1)) + x+1
0
2r +
(92b)
20²T
2 K. k. - 0 + 2((a + 2)r2k, Ao
(a+ ,)2
0² - X²
(92c)
1+1
(A+ + 1)2
0 = r K. a - OTH, E (roor, x. . (rZ z + Abu: 1))]
(92d)
Proor x. (r2 + Obn; 1))
X OTK, E
(92e)
dx
σ
a
ok₁ [[(Prrox,, + 0b;; 1))
0
+
(92f)
2T
20T2
regarding (a, 0,, This is equivalent to the SEs 12 except for the notations are slightly different.
C.1 EQUIVALENCE OF SEs
We first rewrite Z and by in 92 to 72, T2 and Z2 B2 respectively, the equation 92e becomes
Pror (12 + 032; A.). TT2K, Eiy (re + 0:3;; X.)]
A OT2K,
(93)
dr
for f(z) lr].
Then we simplify the SEs 92p. Consider equations
92bb and 92n and we have
OT2
1+1,
(94)
21

---

Under review as a conference paper at ICLR 2022
substituting (4) in 92a we have
1
1
(95)
A+1
072
For the second equation of AMP in which is
71 (71 + A. AB) (31 Zi A +o +,)),
(96)
it is obviously equivalent the equation (92 if we have parameter transformations Ti '1 Xb 1). property of n(:3)) is used for the equivalence:
2a and
1/ (cr; ct) rx;;t)
Ve > 0.
(97)
Using the parameter transformations mentioned above and denote W 11(1 Z1; X. +1), the first equation AMP in (T1) can be rewritten as
12 o². K.E.W B2]²
(98)
8²
i.e.
= : + n. (E[W E 2E[W3,)
(99)
8²
Substituting 92d).
922 and E(33) = ? we have
E(W2) (31 + 21 +
E31 + 1 Z1i A
An)
0
E(n + 72 X.))
(because n)(ex; ct) = cn)(x:t)
82
+
(using (92
82
T2T T2
(100)
32)
2E(n(31 11 + (1)-31)
-ET(( + 72 A.)
2 2rza
(using (9dd),
0T2
then 999 can be rewritten
2
r2a²
2r 00T2 +
o Nr
(101)
g2
8273kx
Po2
Using 955 in
101
we have
20 = o² + o² + ka - 1)2
(102)
Besides. for CGMT, the equation 92c can be written as
1) - (a 1) 0² -2-
(103)
Using 955 in 103 have
222 = o² + (a: - 1) +
(104)
The equation 1022 and (044 are equivalent. Hence the equations 92d). 992 and 92cc of CGMT
be shown to be decomposition of the first equation of AMP in (1]) after some parameter transformations. conclusion we prove the equivalence between SEs from CGMT and AMP in
Lasso framework.
22

---

Under review as a conference paper at ICLR 2022
D RELAXATION PHENOMENON
D.1 RELAXATION PHENOMENON OF M-ESTIMATOR
Notice that 24 is equivalent to
min Σ p(v))
8.1. 11ys + - -el22 5 T3
g 2--
(105)
==1
On the other hand, by rotation invariance Gaussian distribution, 22
becomes
Σ p(u)) [ 12.0
min
s.t. ||0 - E ||0||
22
(106)
where Z' (0, == (,)) 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 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 Appendix D.I so we omit the proof here.
E EQUIVALENCE OF SES OF LOGISTIC REGRESSION FROM LOO AND CGMT
By doing the following parameter transformations:
02 11=01,4=rro0 = X
SEs of CGMT become:
0 VI +r.oV)))
(a1) (A)) [((P(((Poors.l//aaa +roo))))
(107)
1 ("Proex((1/501122rmm))
What we want to prove is that:
(Q2)))
(" +r,o\))
(p))
X E
E 1 (pro x1 (A2
X1""(proonni(//E.00222 +r,v)))
2 = ('p(:i)) x1 (Q2))]
(EIp'(Q))Q1p)
where a constant.
First, we verify the following identity:
(108)
Note that
[(t) p(-t)
(((1) (/(-()
(109)
("(1) p(L)
(ro -Proo
23

---

Under review as a conference paper at ICLR 2022
and the probability density function (pdf) of V GY is
1
Pv(u)
22T
e
1 1te
we have:
B[( (Prors, +roo)))))++ - //
2/p(PPocspl-V/aaa rr,o)))
2n e -240" d'(rv)ddhdo
(110)
where Pz(h)= 2x --= is the pdf of Z. Meanwhile,
/ʃ
(Q)) (proz), (proz ((2)))
2 (a.. (111)
Now we introduce the following parameter transformations: q1 = TsU, Q2 = - //aa1 reov.
Then becomes
|| Vaair. * (r. ( (o.
In order to verify (108). we only need to prove that:
VK,,arr Pu.. Vn.anh- r.ov).
2m
Construct Q1 Q22 as follows: assume Z', Vi i.ddd N(O, and
(8) (-Vhnon -nao)
7. V
We can casily verify that:
BI((), (0,
Coul(Qi 03)²1 -r-or,
-r2or. VR + r
which means (Q), Q2) has identical distribution of Q2). On the other hand, since
o (ch 12d2//422 = P2,,v.(h', (' d') do'
dg'42 dh do r. T
d1 = rzv'. d -VEsail - r.oo',
we have:
= VV..0rr.Po -/BaA - -rovn')
e
2x
which completes our proof of (108)
Secondly, we prove:
( +roo))
2p'(1))
A
=
(112)
1+ [+ +roV))
1 1 (proxx
24

---

Under review as a conference paper at ICLR 2022
Left hand side (LHS) of 112 is
//
1 + (= (v()dddd
+ (praarrass +roo)))
= =Iʃ 1 [==a"""press(((aaart+tt+t.))))
1
20 (r((ro)dddd
2T
1
12 2p (r=vvv)lll v)dddv.
1+ 1 VVraa r.oo))
2T
(113)
Through parameter transformations Q1 = 02
Vk,ath r.ov, RHS of 112 becomes
(11(
(21,
1 Xzp" (prox
d1 (prox
(92))
= -//
2p' (r.u)
- /t or
Combining with
Pen. - -
e
2x
completes the proof of 112
The proof of
EIV (proos,)(Vaaar 2 = (proxxi
can be derived similarly. So we omit the proof here.
25


Reviews:
[{"review_id": "XzBgVNnCm9B", "reviewer": "Reviewer_e98M", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "While the main results of the paper were believed to be true by many researchers, to my knowledge this is the first paper that lays out clearly what the equivalence is between the outcomes of these 3 techniques. Hence the contribution of the paper is undeniable.\n\nHowever, on closer inspection, the paper does not provide any insight into why this equivalence holds, most of the explanations are cursory at best.\n\nTo my knowledge, the derivation from the CGMT technique is based solely on the fixed points of an optimization problem. This provides a somewhat geometric method since KKT conditions are essentially geometric in nature.\nOn the other hand, the AMP derivation is essentially carefully constructing a dynamical system that has an equivalent scalar dynamical system. That this dynamical system reaches the fixed point of an optimization problem is an added benefit. Thus AMP-based derivations are in principle based on some iterative decorrelation given by the Onsager correction. This ends up being some sort of adaptive curvature adjustment in an energy landscape.\n\nThere is little discussion about the LOO technique or insights related to it. The bit on page 8 is more confusing than clear.\n", "summary_of_the_paper": "This paper compares the so-called \"State Evolution\" equations from 3 different derivations for the MSE of \nhigh dimensional M-estimators in the proportional asymptotic regime (number of samples and features go to infinity at a fixed rate).\nThere are currently 3 well-known frameworks for analysis in this regime:\n1. Approximate Message Passing (AMP)\n2. Convex Gaussian Min-Max Theorem (CGMT)\n3. Leave One Out (LOO)\nThe paper shows that there lies an equivalence between the results derived by the 3 methods via a parameter transformation.\nTwo important special cases of LASSO and Binary Logistic Regression are considered and the results are clearly stated.", "summary_of_the_review": "The claims made in the paper are correct to the best of my knowledge. \n\nThe paper deserves to be published even though it lacks in several other ways, mainly because it is the first of its kind in establishing an equivalence between 3 different derivations for the asymptotic analysis of estimators.\n\nThis body of work can serve as a way for researchers using one method to check their predictions with another method using a parameter transformation suggested in this paper.\n\nHowever, there is serious room for improvement in the presentation of the material discussed. The lack of insight provided is also a concern but perhaps can be clarified in future works.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "IVH60NHiUEC", "reviewer": "Reviewer_rXB2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The only strength for me is the a-priori good intention of the paper; as a specialist of the field I was a-priori interested by the paper's goal, but unfortunately it did not convince me at all. \n\nThe weaknesses are:\n\n0) it is not written (nor very interesting) for the ICLR audience; it is a paper for specialists, on a a-priori interesting field to ICLR readers, but the way it is written makes it completely inaccessible to non-specialists.\n\n1) It is badly written and full of typos. The authors should make a important effort to make it readable.\n\n2) It clearly is oriented towards specialists of the field but most of the text is only recalling known results by others. \"Pedagogical parts\" like \"Derived SEs from AMP\", \"Derived SEs from CGMT\", \"Derived SEs from LOO\" are completely useless: a specialist does not need it (and anyway it is badly written I believe), and a non-specialist will get nothing out of it.\n\n3) The main results are very restricted: a) they only considered M-estimators for linear regression (and to a lesser extend logistic regression) with random design; b) the results, being (sometimes quite straighforward) consequences of change of variables which link the non-linear equations derived from the 3 different perspectives, bring absolutely no insight to the reader, other than a formal equivalence.\n\n4) The authors seem to miss important knowledge of the field: not a single paper from the community of physics of spin glasses is cited. But the leave-one-out approach is actually the cavity method from spin glasses with just another name. Having some knowledge on the cavity method, it is completely obvious that the SE equation derived from leave-one-out = cavity method yields he same as AMP, because AMP is just an approximation to Belief Propagation, which is derived from the cavity method. I mean: AMP or BP are just the algorithmic counterpart of the cavity method, and the cavity method is precisely designed to study the statistical properties of BP/AMP, and there are thus of course equivalent up ti simple transformations that simply depend of the details on how the computation have been performed. So to me, this part of the \"equivalence results\" was trivial and know for a very long time. Not everyone is familiar with these concepts and literature, so a-priori it may be interesting to show a relation between AMP and LOO, but it is not possible to do so by completely skipping all that is known.. \nAgain, what is really not re-assuring, is that the authors did not even mention these know facts and related literature.\nThe part on the equivalence between CGMT and the rest seems more interesting to me. But in the appendix the authors repeat in their own way computations mostly known already in the literature (that they cite: Thrampoulidis et al, etc). And because their computations bring no additional insights, I don't see the added value (as such) of the contribution.\n\n4) Whole chunk of related literature are completely skipped and not discussed or even cited; it misses too much here to provide a list", "summary_of_the_paper": "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.", "summary_of_the_review": "To summarize, I believe that despite the potential A-PRIORI interest by some specialised readers, the paper will not convince these specialist readers either. And it will noot bring much to non-specialists. It is badly written, and no real insights are provided. Many computations are just adaptations of things present elsewhere. Many known facts and equivalences are not cited nor even alluded to (again the equivalence between the AMP state evolution and LOO = cavity method is known to any physicist with some experience in spin glasses). The relevant literature is hugely missing. \n\nI suggest the authors to completely re-write the paper, and consider instead a direct journal submission, I really do not see the point too submit this work to ICLR. And, importantly, to cite much more carefully and expmain more thoroughly what is new or not in the paper (as such, I do not believe that much is actually new).", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "9ynlKThZ6tK", "reviewer": "Reviewer_12zP", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "STRENGHTS\n\nAMP, LOO and CGMT have been widely studied in the recent literature, and it has been already pointed out that, in some cases, results concerning the performance of a certain high-dimensional inference task can be obtained using different methods (with very different proof techniques). Thus, understanding the deep connections underlying this fact is certainly a worthwhile goal. \n\n------------\n\nWEAKNESSES\n\nThis paper falls short from this goal and does not offer much insight into *why* the fixed points are the same. The proofs of the equivalence of the fixed point are rather simple and they do not shed much light into the deep connections between e.g. AMP and CGMT. Proposition 3.2 appears to be novel, but its proof can be derived from existing work.\n\nFrom a stylistic viewpoint, the paper contains several typos (especially in the appendix; e.g. Appendix D.2 is repeated twice). Thus, I would recommend the authors to perform a thorough check during the revision.", "summary_of_the_paper": "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).\n\nMost 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. ", "summary_of_the_review": "While the paper focuses on a very interesting subject, unfortunately it does not seem to offer much insight into why the different state evolutions lead to the same fixed point. As a result, the contribution of this work appears to be clearly below the acceptance bar. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "9KOl19JEwIm", "reviewer": "Reviewer_U2rr", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "-- Strengths:\n- Establishing the connection between these different state evolutions is interesting. Of course we expected them to all have the same fixed points for MSE but showing that even the recursions are the same is novel and interesting.\n\n-- Weaknesses:\n- The main issue I have with this paper is significance and novelty of the results. As I said, it is interesting to show that the recursion can be turned into each other for all these methods, but the paper does not give any intuition what the implications of such results are? The authors just say that they hope this leads to finding a deeper structure in such high-dimensional problems. I find it interesting to see that the SEs can be turned into each other, but I believe it is not surprising and unless showing this equivalence leads to more interesting results, I do not see this result to be significant enough to be accepted for ICLR.\n\n- Theorem 3 is not new. It is well known that fixed points of AMP correspond to critical points of Lasso objective function and the min-max problem in CGMT is of course equivalent to Lasso which is essentially the result of the theorem. In fact, AMP and its variants such as VAMP can be used to solve many problems and showing that their fixed points if they converge satisfies the first order optimality conditions is rather easy.\n\n-- Minor comments/typos:\n- The paper has some grammatical and typographical errors. It needs a quick revision to correct for such errors. For example:\n1. spacing between a word and parenthesis after it is often missing.\n2.  beginning of page 8: self-content\n3. remark 3.1: equivalent -> equivalence\nand many more.", "summary_of_the_paper": "The paper establishes equivalence of state evolution for approximate message passing (AMP), convex min-max Gaussian theorem (CGMT), and Leaving-one-out (LOO) for three different problems: 1. a robust linear model estimator called the M-estimator throughout the paper; 2. Lasso; and 3. logistic regression.", "summary_of_the_review": "I believe the contributions of this paper are not significant enough.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Three out of the four reviews rated this paper well below the acceptance threshold. Although the review scores show a relatively large spread, I think that the review contents are more or less coherent across the four reviewers.
The equivalence of the state equations (SEs; a set of equations that macroscopically characterizes optimal solutions of certain high-dimensional regression problems) derived from three different approaches (AMP, CGMT, and LOO) is well expected to hold, as the optimal solutions should be independent of how their macroscopic characterization in the form of an SE is derived, and this paper concretely showed such equivalence to hold for three problems. More concretely, Theorem 1 states the equivalence of the SEs for M-estimator derived from the three approaches, Theorem 2 states the equivalence of the SEs for LASSO derived from AMP and CGMT, and Theorem 4 states the equivalence of the SEs for logistic regression derived from LOO and CGMT. The main concern raised by all the reviewers is that this paper does not provide novel and significant insights as to why and how the equivalence arises.
Some reviewers also pointed out that this paper lacks citation to the relevant statistical-mechanics literature, as well as that this paper contains so many typos, grammatical errors, and inappropriate typesetting styles. The authors responses were not instrumental in persuading the reviewers with negative evaluation. On the basis of these I would not be able to recommend acceptance of this paper for presentation at ICLR 2021.
Decision: Reject