Asymptotics of Non-Convex Generalized Linear Models in High-Dimensions: A proof of the replica formula Matteo Vilucchio, Yatin Dandi, Matéo Pirio Rossignol, Cedric Gerbelot, Florent Krzakala Abstract The analytic characterization of the high-dimensional behavior of optimization for Generalized Linear Models (GLMs) with Gaussian data has been a central focus in statistics and probability in recent years. While convex cases, such as the LASSO, ridge regression, and logistic regression, have been extensively studied using a variety of techniques, the non-convex case remains far less understood despite its significance. A non-rigorous statistical physics framework has provided remarkable predictions for the behavior of high-dimensional optimization problems, but rigorously establishing their validity for non-convex problems has remained a fundamental challenge. In this work, we address this challenge by developing a systematic framework that rigorously proves replica-symmetric formulas for non-convex GLMs and precisely determines the conditions under which these formulas are valid. Remarkably, the rigorous replica-symmetric predictions align exactly with the conjectures made by physicists, and the so-called replicon condition . The originality of our approach lies in connecting two powerful theoretical tools: the Gaussian Min-Max Theorem, which we use to provide precise lower bounds, and Approximate Message Passing (AMP), which is shown to achieve these bounds algorithmically. We demonstrate the utility of this framework through significant applications: (i) by proving the optimality of the Tukey loss over the more commonly used Huber loss under a ε \varepsilon contaminated data model, (ii) establishing the optimality of negative regularization in high-dimensional non-convex regression and (iii) characterizing the performance limits of linearized AMP algorithms. By rigorously validating statistical physics predictions in non-convex settings, we aim to open new pathways for analyzing increasingly complex optimization landscapes beyond the convex regime. 1 Introduction High-dimensional optimization problems are ubiquitous in modern machine learning and statistics, with applications ranging from sparse regression, to kernels, to neural networks. In statistics, mathematics, and theoretical machine learning, a large body of works have been dedicated to the characterization of the analytical asymptotic performance with synthetic data (see e.g. ( Donoho and Tanner, 2009 ; Bayati and Montanari, 2011 ; Thrampoulidis et al., 2018 ; Sur and Candès, 2019 ; Thrampoulidis et al., 2020 ; Loureiro et al., 2021a ; Mei and Montanari, 2022a ; Tan and Bellec, 2024 ) ). While substantial progress has been made in understanding convex problems, such as LASSO ( Donoho et al., 2010 ; Bayati and Montanari, 2011 ; Miolane and Montanari, 2021 ) or random feature regression ( Mei and Montanari, 2022b ; Hu et al., 2024 ) , the non-convex landscape remains largely unexplored despite its practical significance. We shall be interested here in the asymptotic performances of non convex generalized linear models in high-dimension. We consider a supervised learning task where we are given n input output pairs in the form of a dataset \mathcal{D}=\{(\mathbf{x}_{\mu},y_{\mu})\}_{\mu\in[n]} where each one of the pairs (\mathbf{x}_{\mu},y_{\mu})\in\mathbb{R}^{d}\times\mathbb{R} and we perform an estimation of parameters \hat{\mathbf{w}}\in\mathbb{R}^{d} through the minimization of a (possibly non-convex) objective. We define the minimization objective \mathcal{A}_{d}({\mathbf{w}})\mathrel{\mathop{:}}=\frac{1}{d}\quantity[ \sum_{\dataidx=1}^n \lossfun\qty(y_\dataidx, \frac{\w^\top\x_\dataidx}{\sqrt{d}} ) + \sum_{\dimidx=1}^{d} \regfun(\w_\dimidx) ]\,, (2) where \mathscr{L}:\mathbb{R}\crossproduct\mathbb{R}\to\mathbb{R} is the loss function, \mathscr{R}:\mathbb{R}\to\mathbb{R} a regularization function. Given hyperparameters 0\leq a\leq b\leq\infty , we study the constrained optimization problem \displaystyle{\mathcal{A}}^{\star}_{d} \displaystyle\mathrel{\mathop{:}}=\min_{{\mathbf{w}}\in\mathcal{K}_{a,b}}\mathcal{A}_{d}({\mathbf{w}})\,, (3) \displaystyle\hat{{\mathbf{w}}} \displaystyle\in\argmin_{{\mathbf{w}}\in\mathcal{K}_{a,b}}\mathcal{A}_{d}({\mathbf{w}})\,, (4) where \mathcal{K}_{a,b}\mathrel{\mathop{:}}=\{{\mathbf{w}}\in\mathbb{R}^{d}:a\leq\frac{1}{d}\|{\mathbf{w}}\|_{2}^{2}\leq b\} defines a spherical shell constraint. When b=\infty , the upper bound constraint is omitted, resulting in \mathcal{K}_{a,\infty}=\{{\mathbf{w}}\in\mathbb{R}^{d}:a\leq\frac{1}{d}\|{\mathbf{w}}\|_{2}^{2}\} . Note that for a>0 , the constraint set \mathcal{K}_{a,b} is non-convex, introducing an additional source of non-convexity beyond the potential non-convexity of \mathscr{L} and \mathscr{R} . We consider that the input-output pairs that make up the dataset are sampled independently from a distribution P_{\tilde{{\mathbf{w}}}}(\mathbf{x},y) . This probability distribution depends on a target linear model parameterized by \tilde{{\mathbf{w}}}\in\mathbb{R}^{d} called teacher weights. Specifically the generative setting is the one where \displaystyle P(\mathbf{x},y)=P_{\mathrm{out}}\quantity( y \mid\frac{\langle\wteacher, \x\rangle}{\sqrt{d}})P_{\mathrm{in}}(\mathbf{x})\,, (5) where P_{\mathrm{in}} is a probability density function over \mathbb{R}^{d} and P_{\mathrm{out}}\quantity( \cdot\mid z):\mathbb{R}\to\mathbb{R} encodes our assumption that the label is a (potentially non-deterministic) function of \langle\tilde{{\mathbf{w}}},\mathbf{x}\rangle/\sqrt{d} . We equivalently say that the output labels are generated by y_{\mu}=\varphi(\frac{1}{\sqrt{d}}\langle\tilde{{\mathbf{w}}},\mathbf{x}_{\mu}\rangle) , where \varphi:\mathbb{R}\to\mathbb{R} is possibly stochastic. In the rest of the manuscript we will consider the Gaussian case where the samples \mathbf{x} have Gaussian distribution P_{\mathrm{in}}=\mathcal{N}(\mathbf{0},\operatorname{Id}_{d}) . The convex setting is well understood, as powerful theoretical tools have emerged to analyze these high-dimensional problems. Two such important tools, in particular, are the Gaussian min-max theorem ( Gordon, 1988 ; Stojnic, 2009 ; Thrampoulidis et al., 2015 ; Loureiro et al., 2021a ) , and the analysis of fixed-points of the approximate message passing algorithms (AMP) ( Donoho et al., 2010 ; Bayati and Montanari, 2011 ; Bolthausen, 2014 ; Loureiro et al., 2021b ) . Another, different, approach, has been through analyses based on random matrix theory ( Dobriban and Wager, 2018 ; Richards et al., 2021 ; Bach, 2024 ) . However, extending these results beyond convex setting has remained a fundamental challenge, as the existing techniques heavily rely on convex analysis. Yet, there are strong indication that these limits are not fundamental. Indeed powerful heuristic have been developed for these problem by the statistical physics community though the use of the replica and cavity methods ( Mézard et al., 1987 ; Mezard and Montanari, 2009 ; Advani et al., 2013 ; Zdeborová and Krzakala, 2016 ) . These methods predict a whole range of formula very similar to the ones appearing in convex cases, but it is notably difficult to establish their validity ( Talagrand, 2003 ) . In particular, convexity does not play a fundamental role in these predictions, which instead rely on the so-called replica symmetric assumption. In this work, we bridge this gap, and provide a rigorous proof of the statistical physics predictions for the loss and the generalization predicted by these formulae in the non-convex case, that matches exactly the validity range of the replica symmetric assumption predicted by physicists. The originality of our approach is that we use a combination of both the Gaussian min-max theorem, and the message passing techniques. Specifically we use Gaussian min-max theorem as a lower bound for the true minimum of the optimization problem . This true minimum can be characterized as the solution of a low dimensional problem. Later, we show how this bound can be achieved through a carefully designed AMP algorithm that depends only on the solution of the low dimensional problem, and whose convergence can be checked from a low dimensional integral depending on the solution of the low dimensional problem. This framework not only provides rigorous mathematical guarantees but also validates numerous predictions from statistical physics that have long suggested the existence of such characterizations beyond the convex regime. These low-dimensional fixed-point equations we provide emerge naturally from both the Gaussian min-max theorem analysis and the state evolution of AMP algorithms. Furthermore, our analysis reveals that the validity of these characterizations does not depend on convexity. Instead, it relies on a more subtle stability condition (known in physics as the replicon or de Almeida-Thouless condition ( de Almeida and Thouless, 1978 ; De Dominicis and Kondor, 1983 ) ) that can be verified directly — and trivially — from the low-dimensional equations. Interestingly, this condition turns out to be the same as the point-wise stability convergence criterion of the message passing algorithm ( Bolthausen, 2014 ) . The replicon condition, which we fully characterize, determines when the high-dimensional optimization landscape is sufficiently well-behaved for our analysis to hold. Notably, this condition can be satisfied even in clearly non-convex settings, explaining the empirically observed success of certain optimization procedures in non-convex high-dimensional problems. The validity of our results are precisely those conjectured to be necessary by statistical physics: when this condition is not satisfied the replica symmetric formula are known to be wrong (and needs to be replaced by the more involved replica symmetry broken ones ( Talagrand, 2006 ) , which are beyond the scope of this paper). We demonstrate the power of this approach through some applications that have attracted significant recent attention: negative regularization in high-dimensional regression for generic losses ( Tsigler and Bartlett, 2023 ; Kobak et al., 2020 ) , the performance of spectral algorithms ( Mondelli and Montanari, 2018 ; Lu and Li, 2020 ; Maillard et al., 2022 ) , and the study of non convex losses ( Loh, 2017 ; Chang et al., 2018 ) in robust training ( Vilucchio et al., 2024 ; Adomaityte et al., 2024 ) . Our results open new pathways for analyzing increasingly complex optimization landscapes in high-dimensional statistics, offering both theoretical insights and practical algorithmic implications for modern machine learning problems. 1.1 Further related works Our work synthesizes and extends several fundamental theoretical frameworks in high-dimensional statistics and optimization, as well as in the mathematical spin glass litterature. The Gaussian Min-Max Theorem (GMT) — The GMT ( Gordon, 1988 ) , later strengthened to the Convex GMT ( Thrampoulidis et al., 2015 ) , is a powerful tool for analyzing high-dimensional problems. While it has proven highly effective for convex problems Thrampoulidis et al. (2018) ; Javanmard and Soltanolkotabi (2022) ; Loureiro et al. (2021a) , its application to non-convex settings has remained limited. Our work demonstrates how GMT can be extended beyond convexity through careful analysis of the associated low-dimensional optimization landscape. Approximate Message Passing (AMP) — Originating in spin glass theory as the Thouless-Anderson-Palmer (TAP) equations ( Thouless et al., 1977 ) for the Sherrington-Kirpatrick model ( Mézard et al., 1987 ) , these message passing algorithms have witnessed a burst of popularity after the work of Bolthausen (2014) and its extension to compressed sensing in Donoho et al. (2010) . They have become a cornerstone of high-dimensional inference with synthetic data. The precise analysis of AMP dynamics ( Bayati and Montanari, 2011 ) revealed that these algorithms can often achieve fundamental statistical limits. Recent work has extended the analysis of AMP to a broader class of inference problems through oriented graph representations ( Gerbelot and Berthier, 2023 ) . Related to us are the works of Montanari and Richard (2015) , who characterized phase transitions in estimation error for non-negative PCA, and Celentano et al. (2023) ; Celentano (2024) , who established local convexity of the so-called TAP free energy and finite-sample convergence guarantees for Z2-synchronization. Their approach also relies on a combination of Gaussian comparison inequalities and message passing iterations, albeit for a restricted class of problems. In our approach, we use AMP across a much broader class of non-convex problems. Spin glass theory — Our work builds upon fundamental results in spin glass theory. The mathematical treatment of replica symmetry was pioneered by Talagrand (2003) . This was later extended to the full Parisi solution ( Talagrand, 2006 ; Panchenko, 2013 ) , establishing the exactness of the replica method predictions. In this work, we focus on the simpler replica symmetric regime. Applications — Our framework also yields new insights in two important areas that have attracted significant recent attention. The first concerns negative regularization, which has been primarily studied in the specific context of ridge regression ( Hastie et al., 2022 ; Wu and Xu, 2020 ; Richards et al., 2021 ) , and the analysis can be carried out because of the quadratic loss. Our results extend these insights to general loss functions, providing an interest in robust statistics where non-convex losses such as Tukey’s biweight and Cauchy loss functions are used for handling outliers ( Lozano and Meinshausen, 2013 ; Loh, 2024 ) . Another application provides a comprehensive analysis of linearized AMP algorithms, and the performance of spectral method, where we show we can recover directly the results from ( Montanari and Richard, 2015 ; Mondelli and Montanari, 2018 ; Lu and Li, 2020 ; Maillard et al., 2022 ) , without resorting to random matrix theory tools. Notation: Given a function f:\mathbb{R}\to\mathbb{R} , we define its Moreau envelope \mathcal{M}_{f}:\mathbb{R}\to\mathbb{R} as \mathcal{M}_{f}(\omega)=\inf_{z\in\mathbb{R}}\quantity[\frac{1}{2} (\omega- z)^2 + f(z)]\,. (6) The associated proximal operator \mathcal{P}_{f}:\mathbb{R}\to\mathscr{P}(\mathbb{R}) is the set-valued mapping defined as \mathcal{P}_{f}(\omega)=\argmin_{z\in\mathbb{R}}\quantity[\frac{1}{2} (\omega- z)^2 + f(z)]\,, (7) where \mathscr{P}(\mathbb{R}) denotes the power set of \mathbb{R} . When the minimizer is unique, \mathcal{P}_{f}(\omega) is singleton-valued and more specifically when the function f is convex we recover the usual proximal function. We define a function f:\mathbb{R}\to\mathbb{R} to be coercive if \lim_{\absolutevalue{x}\to\infty}f(x)=\infty and the function f is said to be lower semi-continuous if \liminf_{x\to x_{0}}f(x)\geq f(x_{0}) for all values x_{0} where it is defined. Additionally we say that a function f:\mathbb{R}\to\mathbb{R} is V_{0} -weakly convex for V_{0}\in[0,\infty) if the function x\mapsto V_{0}f(x)+\frac{x^{2}}{2} is convex. Additionally we say that a function f is said to be prox-coercive if for any \delta\in\mathbb{R} , the function x\mapsto f(x)+\frac{(\delta-x)^{2}}{2} is coercive in x . 2 Statement of Main Result Our main result characterizes the asymptotic behavior of the minimum and minimizers of the high-dimensional optimization problem Eq. 2 through a low-dimensional auxiliary problem involving six order parameters. Before stating this result precisely, we establish our model assumptions and introduce the necessary notation. Our goal is to study the behavior in the asymptotic regime Assumption 2.1 (High-dimensional limit) . We consider the limit where n,d\to\infty and their ratio is kept fixed at n/d\to\alpha\in(0,\infty) . We will refer to \alpha as the sample complexity . We also make the following assumption on the channel generating the data Assumption 2.2 (Teacher second moment and Output channel) . For each d , let \tilde{{\mathbf{w}}}\in\mathbb{R}^{d} be a teacher vector satisfying \|\tilde{{\mathbf{w}}}\|_{2}^{2}/d\to\rho\in(0,\infty) almost surely as d\to\infty . Moreover, the empirical distribution of the coordinates of \tilde{{\mathbf{w}}} converges almost surely to a probability law P_{\tilde{w}} on \mathbb{R} with \mathbb{E}[\tilde{w}^{2}]=\rho . Let \mathbf{x}\sim\mathcal{N}(0,\operatorname{Id}_{d}) and define s\mathrel{\mathop{:}}=\langle\tilde{{\mathbf{w}}},\mathbf{x}\rangle/\sqrt{d} . Conditionally on s , the response y is generated according to an output channel y\sim P_{\mathrm{out}}(\cdot\mid s)\,, (8) where P_{\mathrm{out}} is fixed (independent of d ) and such that y is almost surely bounded. We consider loss and regularization functions satisfying the following assumption Assumption 2.3 (Regularity of loss and regularization functions) . The functions \mathscr{L} and \mathscr{R} are pseudo-Lipschitz of finite order (see Definition 5.1 ) and respectively V_{L} and V_{R} -weakly convex (see Definition 5.4 ) for some V_{L},V_{R}>0 . When b=\infty , we further require that both \mathscr{L} and \mathscr{R} are bounded below and that there exist constants C_{R},W_{0}>0 such that \mathscr{R}(w)\geq C_{R}w^{2} for all |w|\geq W_{0} . The pseudo-Lipschitz condition allows for non-smooth losses while still maintaining sufficient regularity for our theoretical analysis. When the norm constraint b is infinite, the coercivity condition guarantees the existence of minimizers by preventing the objective from having escaping sequences. With these modeling assumptions in place, we now introduce the low-dimensional characterization. We thus define the low-dimensional objective of interest as \mathcal{E}(m,q,\tau,\kappa,\nu,\eta)\mathrel{\mathop{:}}=\frac{\kappa\tau}{2}-\frac{1}{2\eta}(\nu^{2}\rho+\kappa^{2})+\nu m-\frac{\eta q}{2}-\alpha\mathcal{E}_{\mathscr{L}}-\mathcal{E}_{\mathscr{R}}\,, (9) where \displaystyle\mathcal{E}_{\mathscr{L}} \displaystyle\mathrel{\mathop{:}}=\mathbb{E}_{g,s}\quantity[ \frac{\kappa}{\tau}\mathcal{M}_{\frac{\tau}{\kappa} \lossfun(y, \cdot)}\qty( \frac{m}{\sqrt{\rho}} s + \sqrt{q - \frac{m^2}{\rho}} h ) ]\,, (10) \displaystyle\mathcal{E}_{\mathscr{R}} \displaystyle\mathrel{\mathop{:}}=\mathbb{E}_{\tilde{w},h}\quantity[ \eta\mathcal{M}_{\frac{1}{\eta} \regfun(\cdot)}\qty( \frac{1}{\eta} \qty(\nu\tilde{w} + \kappa g) ) ]\,, (11) and the expectations are taken with respect to independent standard Gaussian random variables s,g,h\sim\mathcal{N}(0,1) , the teacher coordinates \tilde{w}\sim P_{\tilde{w}} , and the output y\sim P_{\mathrm{out}}(\cdot\mid s) . The Moreau envelope \mathcal{M}_{f(\cdot)} is defined in Eq. 6 . We define \mathcal{S}^{\star} as the set of extremizers of the following min-max problem: \mathcal{S}^{\star}=\quantity{ \hat{m}, \hat{q}, \hat{\tau}, \hat{\kappa}, \hat{\nu}, \hat{\eta}: \energyfun(\hat{m}, \hat{q}, \hat{\tau}, \hat{\kappa}, \hat{\nu}, \hat{\eta})= \sup_{\kappa, \nu, \eta} \inf_{ \substack{m, q, \tau\\ a \leq q \leq b} } \energyfun(m, q, \tau, \kappa, \nu, \eta) }\,. (12) Under the assumptions, \mathcal{S}^{\star} is non-empty and fully characterizes the high-dimensional optimization landscape. While the previous assumptions can be considered standard, our analysis relies on two additional key assumptions. The first ensures regularity of the proximal operators, while the second provides a crucial stability condition that emerges from the statistical physics of complex systems. Assumption 2.4 (Weak Convexity of scaled Loss and Regularization Functions) . There exist (m^{\star},q^{\star},\tau^{\star},\kappa^{\star},\nu^{\star},\eta^{\star})\in\mathcal{S}^{\star} such that \frac{\tau^{\star}}{\kappa^{\star}}1 and \eta^{\star}V_{R}>1 respectively. Remark 2.1 . As established in Appendix A , this assumption is both necessary and sufficient for the existence of Lipschitz continuous proximal selections. Specifically, under these conditions, the proximal operators \mathcal{P}_{\frac{\tau^{\star}}{\kappa^{\star}}\mathscr{L}(y,\cdot)} and \mathcal{P}_{\frac{1}{\eta^{\star}}\mathscr{R}} admit unique L_{L} -Lipschitz and L_{R} -Lipschitz selections \tilde{\mathcal{P}}_{\frac{\tau^{\star}}{\kappa^{\star}}\mathscr{L}(y,\cdot)}(\omega)\in\mathcal{P}_{\frac{\tau^{\star}}{\kappa^{\star}}\mathscr{L}(y,\cdot)}(\omega),\quad\tilde{\mathcal{P}}_{\frac{1}{\eta^{\star}}\mathscr{R}}(w)\in\mathcal{P}_{\frac{1}{\eta^{\star}}\mathscr{R}}(w),\quad\forall\omega,w,y\in\mathbb{R}\,, (13) with L_{L}\mathrel{\mathop{:}}=\frac{\kappa^{*}V_{L}}{\kappa^{*}V_{L}-\tau^{*}}>1 and L_{R}\mathrel{\mathop{:}}=\frac{\eta^{*}V_{R}}{\eta^{*}V_{R}-1}>1 . This equivalence justifies our choice of assumption as the minimal regularity condition needed for our algorithmic framework. Similar characterizations have appeared in the literature ( Gribonval and Nikolova, 2020 ; Gribonval and Nikolova, 2021 ) , but our result establishes the tightness of this condition. An example of loss function violating the condition is given by \mathscr{L}(z)=\mathbf{1}_{z\geq\kappa} for some \kappa\in\mathbb{R} , corresponding to the setting of perceptron ( Gardner, 1988 ) . The previous assumption and remark allows us to define two Lipschitz-continuous update functions that will be used in the message passing algorithm {g^{\star}}(\omega,y)=\frac{\kappa^{\star}}{\tau^{\star}}\quantity(\tilde{\mathcal{P}}_{\frac{\tau^\star}{\kappa^\star}\lossfun(y,\cdot)}(\omega) -\omega)\,,\quad{f^{\star}}(w)=\tilde{\mathcal{P}}_{\frac{1}{\eta^{\star}}\mathscr{R}}(w)\,. (14) We now introduce the concept of Replicon Stability for the family of problems we consider, as follows: Definition 2.1 (Replicon Stability) . We say that (m^{\star},q^{\star},\tau^{\star},\kappa^{\star},\nu^{\star},\eta^{\star})\in\mathcal{S}^{\star} already satisfying Assumption 2.4 are stable if \alpha\mathbb{E}_{\tilde{w},z}\quantity[ \qty(\partial\inden[\star] \qty( \frac{\nu^\star}{\eta^\star} \tilde{w} + \frac{\kappa^\star}{\eta^\star} z) )^2 ]\mathbb{E}_{y,z}\quantity[ \qty(\partial\outden[\star] \qty( \frac{m^\star}{\rho} s + \sqrt{q^\star- \frac{(m^\star)^2}{\rho}} z, y) )^2 ]<1\,, (15) where z,s\sim\mathcal{N}(0,1) , y\sim P_{\mathrm{out}}\quantity(\cdot\mid s) , \tilde{w} as in Assumption 2.2 and {g^{\star}},{f^{\star}} are defined in Eq. 14 . Our second assumption ensures stability of the optimization algorithm as follows Assumption 2.5 . We suppose that for some (m^{\star},q^{\star},\tau^{\star},\kappa^{\star},\nu^{\star},\eta^{\star})\in\mathcal{S}^{\star} the condition in Definition 2.1 is valid. The above condition corresponds to the replicon condition from statistical physics ( Engel and Van den Broeck, 2001 ) and generalizes the stability criterion of Bolthausen (2014, Eq. (2.1)) . Most importantly, it provides a necessary condition for the replica symmetric ansatz to remain valid for the setting considered here, making it an essential requirement for our analysis. However, the condition itself is not sufficient. As an example, for the case of spherical perceptron, corresponding to \mathscr{L}(z)=\mathbf{1}_{z\geq\kappa} , the minimum value of the objective deviates from the replica-symmetric prediction even under the validity of the Replicon Stability condition ( Franz and Parisi, 2016 ; Sclocchi and Urbani, 2022 ) . Hence, both the 2.4 and 2.5 are fundamental rather than technical. Our main theorem establishes the asymptotic behavior of the high-dimensional optimization problem as follows Theorem 2.1 . Consider the sequence of random optimization objectives \mathcal{A}_{d} defined in Eq. 2 . Under 2.4 , 2.5 , 2.3 , 2.1 and 2.2 , we have 1. The minimum risk {\mathcal{A}}^{\star}_{d} concentrates almost surely to a low-dimensional sup-inf problem as {\mathcal{A}}^{\star}_{d}\xrightarrow{a.s.}{\mathcal{A}}^{\star}\mathrel{\mathop{:}}=\sup_{\kappa,\nu,\eta}\inf_{\begin{subarray}{c}m,q,\tau\\ a\leq q\leq b\end{subarray}}\mathcal{E}(m,q,\tau,\kappa,\nu,\eta)\,. (16) 2. For any pseudo-lipschitz \psi:\mathbb{R}^{2}\rightarrow\mathbb{R} such that \Psi(s)\mathrel{\mathop{:}}=\sup_{\kappa,\nu,\eta}\inf_{\begin{subarray}{c}m,q,\tau\\ a\leq q\leq b\end{subarray}}\quantity[ \energyfun(m, q, \tau, \kappa, \nu, \eta) + s \psi(m, q) ] (17) is differentiable at s=0 , any sequence of global minimizers \hat{\mathbf{w}} satisfies \psi\quantity(\frac{1}{d} \langle\wminimizer, \wteacher\rangle, \frac{1}{d} \norm{\wminimizer}_2^2 )\xrightarrow[d\to\infty]{a.s.}\evaluated{\dv{s} \Psi(s) }_{s=0}\,. (18) Our proof combines two complementary approaches. We first establish a lower bound using Gordon’s Min-Max Theorem ( Gordon, 1988 ; Thrampoulidis et al., 2015 ) . We then construct a matching upper bound through an algorithmic realization using a message passing algorithm. The main steps of the proof are presented in the following section, while a full derivation is deferred in the appendices. The previous theorem presents both an asymptotic characterization of the minimum (first case) and a characterization of function of minimizers (second case) through the choice of the function \psi . A key consequence of this theorem is that it precisely characterizes the high-dimensional estimation error. Indeed, by choosing \psi:(m,q)\mapsto\rho-2m+q , we obtain \frac{1}{d}\norm{\wminimizer- \wteacher}^{2}_{2}=\psi\quantity(\frac{1}{d} \langle\wminimizer, \wteacher\rangle, \frac{1}{d} \norm{\wminimizer}_2^2 )\,. (19) 3 Applications of the Main Result We now demonstrate three fundamental settings where our theoretical framework provides novel insights either by exploring a setting that previously was inaccessible for previous tools, proving already known results in the literature or by proving optimality of a loss function in the case of \varepsilon contaminated outlier model. Figure 1 : (Left) Presentation of some loss functions used in robust statistics. (Right) Comparison of different performances under a Gaussian \varepsilon -contaminated model. We see that non-convex losses attain a lower estimation error than the convex ones. The lines represent the solution for \psi(m,q)=\rho-2m+q from Eqs. 17 and 18 , while the error bars the ERM simulations on generated data. 3.1 Non Convex Loss Function for Robust M-Estimation A fundamental challenge in high-dimensional statistics is developing estimators that are robust to outliers while maintaining statistical efficiency. Classical robust statistics has extensively studied this problem in the low-dimensional regime ( Huber, 1981 ; Maronna et al., 2019 ) , with particular focus on M-estimators. The design and analysis of loss functions that effectively handle outliers in regression has been central to robust statistics. The classical literature has introduced numerous such functions, emphasizing non-convex alternatives to least squares estimation. Notable examples include Tukey’s biweight function ( Tukey, 1960 ) and the Cauchy loss ( Lehmann and Casella, 2006 ) , which offer superior robustness properties compared to convex alternatives. Recent work by Lozano and Meinshausen (2013) and Loh (2017) has renewed interest in this area, studying stationary points of nonconvex functions for robust linear regression within a local neighborhood of the true regression vector. The theoretical analysis of these estimators in the proportional high-dimensional regime has remained challenging due to their non-convex nature. Our theorem provides a framework to address this challenge, yielding sharp asymptotic characterizations of both convex and non-convex robust regression estimators. To illustrate our results, we consider the performance of the ERM estimator from Eq. 4 with L2 loss \mathscr{L}_{\mathrm{L2}}(u)=\frac{u^{2}}{2} , the Huber Loss function \mathscr{L}^{\xi}_{\mathrm{H}}(u)=\xi^{2}\int_{0}^{\absolutevalue{u}/\xi}\min(1,x)\differential{x} , the Tukey biweight loss function \mathscr{L}^{\xi}_{\mathrm{T}}(u) , and the Cauchy loss function \mathscr{L}^{\xi}_{\mathrm{C}}(u) defined as \mathscr{L}^{\xi}_{\mathrm{T}}(u)=\begin{cases}\frac{\xi^{2}}{6}\quantity[1 - \left(1 - \frac{u^2}{\xi^2}\right)^3],&\text{if }|u|\leq\xi,\\ \frac{\xi^{2}}{6}+\varrho\absolutevalue{u - \xi}^{3},&\text{if }u>\xi,\\ \frac{\xi^{2}}{6}+\varrho\absolutevalue{u + \xi}^{3},&\text{if }u<-\xi.\end{cases}\,,\quad\mathscr{L}^{\xi}_{\mathrm{C}}(u)=\frac{\xi^{2}}{2}\log\left(1+\frac{u^{2}}{\xi^{2}}\right)\,, (20) where u\mathrel{\mathop{:}}=y-z and with \ell_{2} regularization \mathscr{R}_{\lambda}(w)=\frac{\lambda}{2}w^{2} . The Tukey loss includes an additional coercive term with parameter \varrho , required for our theoretical framework to apply. In practice, for sufficiently small \varrho , this modification has negligible effect on the estimator’s behavior. In Figure 1 we present a comparison of the optimally tuned regularization parameters for the four different loss functions, showing that for the chosen noise model, the Tukey loss achieves lower estimation error compared to the Huber, Cauchy, and L2 losses. Since our theory shows that the estimation error converges to a deterministic function of the model parameters, optimizing the hyperparameters (\xi,\lambda) reduces to a two-dimensional optimization problem. While a rigorous justification of this hyperparameter optimization, which requires strengthening our statement from pointwise to uniform convergence, could likely be obtained using techniques similar to those in Miolane and Montanari (2021) , we defer this analysis to a longer version of this work. Nonetheless, we observe strong agreement between our asymptotic predictions and finite-dimensional simulations. Figure 2 : (Left) Training loss profiles as a function of parameter norm for varying regularization strengths \lambda . (Right) Gradient descent trajectories in dimension d=1000 for different initialization norms. Trajectories initialized with norms smaller than the local maxima converge to the local minimum, while the others diverge. 3.2 Phase Transitions in Negative Regularization for Generalized Linear Models We will now consider the phenomenon of negative regularization in high-dimensional GLMs. While this effect has been extensively studied for ridge regression ( Hastie et al., 2022 ; Wu and Xu, 2020 ; Richards et al., 2021 ) , its behavior for non-quadratic loss functions and \ell_{2} regularization remains poorly understood. This is a technical hurdle as the previous results strongly rely on Random Matrix Theory. We provide a characterization of this phenomenon for a broad class of loss functions. For a convex \mathscr{L}(y,z) with sub-quadratic growth at infinity, setting \lambda<0 leads the minimization objective to diverge to -\infty as \norm{\w}\rightarrow\infty . However, up to a threshold, the objective admits a local minimizer. While Theorem 2.1 does not directly hold for the case of negative regularization we characterize the training landscape by studying the problem defined in Eq. 2 with a=b=q , as a function of q . For a non-negative regularization strength ( \lambda\geq 0 ), convexity of the loss ensures the existence of a unique minimizer whose normalized squared norm converges almost surely to a finite value. As we move into negative regularization, there exists a critical threshold \lambda_{c}<0 that separates the case with and without a local minima. For \lambda\in(\lambda_{c},0] , the loss landscape admits at least two distinct minimizers: a local minimizer at finite norm and a global minimizer whose norm diverges to infinity. Below the critical threshold ( \lambda<\lambda_{c} ), the landscape no longer presents any finite-norm minimizer, and the objective function is minimized through a sequence of solutions with diverging norms. These theoretical predictions are validated by numerical experiments shown in Figure 2 (Left) for the Huber loss \mathscr{L}_{H}^{\xi} , which presents the limiting training objective {\mathcal{A}}^{\star} as a function of the norm of the solution q for different values of \lambda . For \lambda>0 the loss objective presents a single minima because of convexity. For \lambda<0 the training loss develops both a local minimum at finite q (which continuously extends from the global minimum at positive \lambda ) and a global minimum at diverging q . The minima exists only for values of \lambda<0 not too negative. Crucially, these two minima are separated by a local maximum, suggesting that local optimization algorithms initialized at small norm will converge to the non-trivial local minimum. Additionally, in Figure 2 (Right) we consider gradient descent initialized at different norms in the training profile for \lambda\in(\lambda_{c},0) . We see that the dynamics of GD follow the landscape already at finite dimension. 3.3 Spectral Method in Generalized Linear Models Last but not least we now present interesting results in the analysis of spectral methods. A standard question is how many observations are required to obtain a better-than-random prediction within a class of algorithms, also known as weak learnability . This can be studied both statistically (within the class of all, including exponential time algorithms) or computationally (restricted to a particular computational class, such as first-order algorithms). For generalized linear models, often called single-index model in this context, weak learnability has been heavily studied. The statistical threshold for learnability has been characterised by Barbier et al. (2019) when the covariate dimension d is large. Optimal computational thresholds for the class of first-order iterative algorithms were also derived in ( Mondelli and Montanari, 2018 ; Luo et al., 2019 ; Celentano et al., 2020 ; Maillard et al., 2020 ) . A natural question is wether spectral methods can capture this optimal threshold, and several works have considered this problem, in particular, Lu and Li (2020) and Mondelli and Montanari (2018) considered the problem with random matrix theory tools and discussed the weak recovery phase transition. More recently, Maillard et al. (2022) connected these spectral methods to approximate message passing algorithms. The traditional analyses of such spectral methods often rely on intricate random matrix theory arguments, requiring careful control of both the bulk distribution of eigenvalues and the behavior of isolated eigenvalues. We shall show that our framework provides a more direct route to analyzing these estimators. Specifically, consider the analysis of spectral estimators for matrices of the form A=\sum_{\mu=1}^{n}\mathcal{T}(y_{\mu})\mathbf{x}_{\mu}\mathbf{x}_{\mu}^{\top}, (21) where \mathcal{T}:\mathbb{R}\to\mathbb{R} is a preprocessing function and the observations follow a GLM as y_{\mu}=\varphi(\frac{1}{d}\langle\tilde{{\mathbf{w}}},\mathbf{x}_{\mu}\rangle) . The classical spectral method estimates the signal by computing the leading eigenvector of A . By the Courant-Fischer-Weyl min-max principle, this is equivalent to solving \lambda_{\mathrm{true}}=\min_{{\mathbf{w}}\in\mathcal{K}_{1,1}}\sum_{\mu=1}^{n}\mathcal{T}(y_{\mu})\quantity(\w^\top\x_\dataidx)^{2}\,,\quad\hat{{\mathbf{w}}}=\argmin_{{\mathbf{w}}\in\mathcal{K}_{1,1}}\sum_{\mu=1}^{n}\mathcal{T}(y_{\mu})\quantity(\w^\top\x_\dataidx)^{2}\,, (22) where \mathcal{K}_{1,1} denotes the unit sphere. Consider the estimate \hat{{\mathbf{w}}} obtained from Algorithm 1 and its associated eigenvalue estimate \lambda_{\mathrm{amp}}=\langle\hat{{\mathbf{w}}},A\hat{{\mathbf{w}}}\rangle/\norm{\wminimizer}_{2}^{2} . In the high-dimensional limit where both the dimension d and sample size n grow to infinity at a fixed ratio \alpha=n/d , we prove that \lambda_{\mathrm{amp}} converges almost surely to the true spectral estimate \lambda_{\mathrm{true}} . This convergence result relies on showing that the AMP algorithm converges to a fixed point that necessarily satisfies the first-order optimality conditions of the original spectral optimization problem. Specifically, let m=\langle\tilde{{\mathbf{w}}},\hat{\mathbf{w}}\rangle/d denote the overlap of the solution with the teacher vector. In the high-dimensional limit, for \rho=\lim_{d\to\infty}\norm{\wteacher}_{2}^{2}/d=1 , our main theorem proves that m behaves as the solution of the following system of equations \displaystyle m \displaystyle=\frac{a(m,\tau)}{\sqrt{\alpha a^{2}(m,\tau)+b(m,\tau)}}\,, \displaystyle\,a(m,\tau) \displaystyle=\mathbb{E}\quantity[\qty(s - \frac{m h}{\sqrt{1 - m^2}} ) P(m,\tau)]\,, (23) \displaystyle\tau \displaystyle=\frac{1}{\alpha\sqrt{\alpha a^{2}(m,\tau)+b(m,\tau)}}\,, \displaystyle\,b(m,\tau) \displaystyle=\frac{1}{\tau^{2}}\mathbb{E}\quantity[\qty(s - \frac{m h}{\sqrt{1 - m^2}} - P(m,\tau) )^2]\,, (24) where the expectation is taken over s,h\sim\mathcal{N}(0,1) , y\sim P_{\mathrm{out}}\quantity(\cdot\mid s) , and where P(m,\tau)\mathrel{\mathop{:}}=\mathcal{P}_{\tau\mathscr{L}(y,\cdot)}\quantity(s - \sfrac{m h}{\sqrt{1 - m^2}}) with \mathscr{L}(y,z)=\mathcal{T}(y)z^{2} . These equations fully characterize the performance of both the spectral method and the AMP algorithm in the high-dimensional limit. This result provides a precise analytical description of the spectral estimator’s performance without requiring random matrix theory tools. Our analysis reveals that the algorithmic and statistical aspects of spectral estimation are intimately connected through the state evolution of AMP. In particular, the fixed point equations above allow us to precisely characterize the phase transition boundary between successful and unsuccessful recovery, as well as the asymptotic correlation achieved in the recovery phase. 4 Outline of Proof The key steps of the proof are three: a non-constructive lower bound derived from Gaussian comparison inequalities, a constructive upper bound obtained through an algorithmic procedure and a matching argument showing these bounds coincide. The algorithmic way to attain the lower bound is the message passing algorithm as the one presented in Algorithm 1 . Algorithm 1 General Approximate Message Passing (GAMP). Input: Feature Matrix \boldsymbol{X}\in\mathbb{R}^{n\times d} , the vector of outputs \mathbf{y}\in\mathbb{R}^{n} , initialization {\mathbf{w}}^{0}\in\mathbb{R}^{d} , set of functions \{{g^{t}},{f^{t}}\}_{t\geq 0} Output: Value of {\mathbf{w}}\in\mathbb{R}^{d} and {\mathbf{p}}\in\mathbb{R}^{n} at termination 1 while \lnot Termination Condition do // Output Node Update 2 b^{t}:=\frac{1}{d}\sum_{\mu=1}^{n}\partial{g^{t}}\quantity(p_\dataidx^t, y_\dataidx) 3 {\mathbf{p}}^{t}=\frac{1}{\sqrt{d}}\boldsymbol{X}{f^{t}}\quantity( \w^t )-b^{t}{g^{t-1}}\quantity(\p^{t-1}, \y) // Input Node Update 4 c^{t}:=\frac{1}{d}\sum_{i=1}^{d}\partial{f^{t}}\quantity(w_\dimidx^t) 5 {\mathbf{w}}^{t+1}=\frac{1}{\sqrt{d}}\boldsymbol{X}^{\top}{g^{t}}\quantity(\p^t, \y)-c^{t}{f^{t}}\quantity( \w^t ) The first step is to derive the lower bound on the minimum achievable risk in the high-dimensional limit. This is the following result Proposition 4.1 . Let {\mathcal{A}}^{\star} be the minimal value of the risk defined in Eq. 16 and {\mathcal{A}}^{\star}_{d} be the minimum value defined in Eq. 3 . Then, in the high-dimensional limit where n,d\to\infty and \alpha=n/d we have that for every \varepsilon>0 \Pr[\liminf_{d\rightarrow\infty}{\mathcal{A}}^{\star}_{d}\geq{\mathcal{A}}^{\star}-\varepsilon]=1\,. (25) This proposition establishes that the limiting risk {\mathcal{A}}^{\star} serves as an asymptotic lower bound for the finite-dimensional minimum {\mathcal{A}}^{\star}_{d} . This lower bound admits an explicit characterization in terms of Moreau envelopes of the loss and regularization functions that is stated in full generality in Section 6 . The next step in the proof is to use the scalar parmeters found from the minimisation of Eq. 16 and use them to build an initializiation for Algorithm 1 . We show that under our assumptions this implies the termination of the algorithm in the following Lemma 4.2 (Convergence of GAMP algorithm) . Let (m^{\star},q^{\star},\tau^{\star},\kappa^{\star},\nu^{\star},\eta^{\star})\in\mathcal{S}^{\star} defined in Eq. 12 , denote a set of parameters satisfying 2.4 and 2.5 . Consider Algorithm 1 initialized as {\mathbf{w}}^{0}=\frac{m^{\star}}{\rho}\tilde{{\mathbf{w}}}+\sqrt{q^{\star}-\frac{(m^{\star})^{2}}{\rho}}\boldsymbol{\xi}\,, (26) where \boldsymbol{\xi}\sim\mathcal{N}(\boldsymbol{0},\operatorname{Id}_{d}) independently from all other quantities. We will indicate as {\mathbf{w}}^{t} the iterates of Algorithm 1 with non linearities \{g^{t}={g^{\star}},f^{t}={f^{\star}}\}_{t\geq 0} , defined in Eq. 14 . Then there exist constants C_{1},C_{2}>0 and 0<\rho_{1},\rho_{2}<1 such that: \mathcal{E}_{w,\rho_{1},d}\coloneqq\quantity{ \frac{1}{\sqrt{d}} \norm{\w^{t+1} - \w^{t}}_2 \leq C_1 {\rho_1}^t }\,,\qquad\mathcal{E}_{p,\rho_{2},d}\coloneqq\quantity{ \frac{1}{\sqrt{n}} \norm{\p^{t+1} - \p^{t}}_2 \leq C_2 {\rho_2}^t }\,, (27) hold almost surely as n,d\rightarrow\infty i.e: \Pr[\cap_{d\geq d_{0}}\mathcal{E}_{w,\rho_{1},d}]\rightarrow 1,\,\quad\Pr[\cap_{d\geq d_{0}}\mathcal{E}_{p,\rho_{2},d}]\rightarrow 1, (28) as d_{0}\rightarrow\infty . The previous lemma is proven by considering the reduction of the message passing algorithm to its state evolution dynamics and then showing the contractivity of the evolution. Because of the separable form of the regularization term we analyze an equivalent version of the algorithm where the dependence on the norm is exchanged by a rescaling by a constant. Finally we show that the fixed points of Algorithm 1 obtained with the previous initialization reach the lower bound on the energy thus proving that it is attainable. Proposition 4.3 . Let (m^{\star},q^{\star},\tau^{\star},\kappa^{\star},\nu^{\star},\eta^{\star})\in\mathcal{S}^{\star} denote a set of parameters satisfying Assumptions 2.4 and 2.5 . Then for the sequence of iterates obtained by applying Algorithm 1 starting from initialization of Eq. 26 we have \lim_{t\to\infty}\lim_{d\to\infty}\mathcal{A}_{d}(\hat{{\mathbf{w}}}^{t})={\mathcal{A}}^{\star}\,, (29) almost surely. We have thus proved that the estimate returned by the message passing algorithm reaches the lower-bound given from the Gaussian comparison theorem, ending the main part of the proof. Our proof technique’s originality lies in synthesizing two established methodologies in high-dimensional statistics. While each approach has been studied separately, their combination yields a framework that mirrors the intuition from statistical mechanics. Specifically, our approach first derives equations for the order parameters through comparison inequalities, analogous to the replica method, and then verifies their physical realizability through the stability analysis of the corresponding dynamics. The methodology developed in this paper opens several promising research directions. A natural extension would be to problems exhibiting replica symmetry breaking, where the current Gaussian comparison bounds would need to be generalized to account for multiple pure states. Such an extension could provide insights into problems like sparse PCA or community detection in the hard phase. Furthermore, our proof technique suggests a general recipe for analyzing non-convex optimization landscapes: first establishing information-theoretic limits through comparison inequalities, then constructing explicit algorithms that achieve these bounds. 5 Preliminaries This section will be devoted to the statement of definitions, preliminary results and theorems that will be used in the following. We will use the following definition extensively. Definition 5.1 (Pseudo-Lipschitz function) . A function f\colon\mathbb{R}\to\mathbb{R} is said to be pseudo-Lipschitz of order k if there exists a constant L such that for any x,y\in\mathbb{R} , \absolutevalue{f(x) - f(y)}\leq L\quantity( 1 + \abs{x}^{k-1} + \abs{y}^{k-1} )\absolutevalue{x - y}\,. (30) We also define the following two proprierties of a function Definition 5.2 (Prox-Coercive function) . A function f is said to be prox-coercive if for any r,\delta\in\mathbb{R}\mapsto f(r)+\frac{(\delta-r)^{2}}{2} is coercive in r ; i.e. \lim_{|r|\rightarrow\infty}f(r)+\frac{(\delta-r)^{2}}{2}=\infty\,. (31) Definition 5.3 (Locally lower bounded) . A function f is said to be locally lower bounded if, for any point r\in\mathbb{R} , there exists a neighborhood U\subset\mathbb{R} of r such that \inf_{U}f>-\infty\,. (32) Definition 5.4 (Weakly convex function) . Fix V_{0}\in[0,\infty) . A function f is said to be V_{0} -weakly convex (resp. strictly V_{0} -weakly convex) if the function r\mapsto V_{0}f(r)+\frac{r^{2}}{2} is convex (resp. strictly convex). A function f is said to be weakly convex if it is V_{0} -weakly convex for some V_{0}\in(0,\infty) . Remark 5.1 . From this definition three remarks are in order • f is convex if and only if it is V_{0} -weakly convex for any V_{0}\in[0,\infty) . • For a given V_{0}\in[0,\infty) f is V_{0} -weakly convex if and only if V_{0}f is 1 -weakly convex. • If f is V_{0} weakly convex for some V_{0}>0 , then f is strictly V -weakly convex for V\in[0,V_{0}) . To require that f is weakly convex is much less restrictive than the name might suggest. Informally, it can be understood as having a lower bounded second derivative almost everywhere. Remark 5.2 . We additionally note that the notable example of the negative perceptron, where the considered function is the negative step function is not considered in our framework. Definition 5.5 (Effective Domain of Proximal Operator) . For a function f:\mathbb{R}\to\mathbb{R} , we define E_{f}:=\{\delta\in\mathbb{R}:\mathcal{P}_{f}(\delta)\neq\emptyset\} as the set of points for which the proximal is non-empty. For analyzing the regularity properties of proximal selections, we introduce two auxiliary functions that capture the behavior of the modified function r\mapsto f(r)+\tfrac{r^{2}}{2} : Definition 5.6 (Chord Slope Functions) . For a function f:\mathbb{R}\to\mathbb{R} , we define s:\mathbb{R}\to\mathbb{R}\cup\{\infty\} and i:\mathbb{R}\to\mathbb{R}\cup\{-\infty\} by s_{f}(r_{0}):=\sup_{rr_{0}}\left[\frac{f(r)-f(r_{0})}{r-r_{0}}+\frac{r+r_{0}}{2}\right]\,. (33) Remark 5.3 . The functions s_{f}(r_{0}) and i_{f}(r_{0}) represent the supremum and infimum, respectively, of the slopes of the chords at r_{0} of the function r\mapsto f(r)+\tfrac{r^{2}}{2} . When f is 1 -weakly convex (i.e., r\mapsto f(r)+\tfrac{r^{2}}{2} is convex), we have s=f^{\prime}_{-}+\mathrm{id} and i=f^{\prime}_{+}+\mathrm{id} where f^{\prime}_{-} and f^{\prime}_{+} denote the left and right derivatives of f , respectively. 5.1 Useful Lemmas about Moreau Envelopes and Proximal Selections The first lemma that we need to use in the following has already appeared as ( Loureiro et al., 2021a , Lemma 5) but the proof relied on convexity. We thus extend it to the setting considered in this manuscript. Lemma 5.1 (Pseudo-Lipschitz property of Moreau envelopes) . Suppose that \mathscr{L}:\mathbb{R}\times\mathbb{R}\rightarrow\mathbb{R},\mathscr{R}:\mathbb{R}\rightarrow\mathbb{R} are pseudo-Lipschitz of order k , and such that E_{\mathscr{L}(y,\cdot)}=\mathbb{R} , E_{\mathscr{R}}=\mathbb{R} for all y\in\mathbb{R} , then (y,\omega)\mapsto\mathcal{M}_{\mathscr{L}(y,\cdot)}(\omega) , \omega\mapsto\mathcal{M}_{\mathscr{R}(\cdot)}(\omega) are pseudo-Lipschitz. Proof of Lemma 5.1 : We prove the result for \mathcal{M}_{\mathscr{L}(y,\cdot)} ; the argument for \mathcal{M}_{\mathscr{R}(\cdot)} is analogous. Let (y_{1},\omega_{1}),(y_{2},\omega_{2})\in\mathbb{R}^{2} be arbitrary and let z_{1},z_{2} denote any of the corresponding extremizers of \mathcal{M}_{\mathscr{L}(y_{1},\cdot)}(\omega_{1}) and \mathcal{M}_{\mathscr{L}(y_{2},\cdot)}(\omega_{2}) respectively. Define: \displaystyle\Phi_{y}(z,\omega)\coloneqq\mathscr{L}(y,z)+\frac{1}{2}\absolutevalue{z - \omega}^{2}\,. (34) Recall that: \displaystyle\mathcal{M}_{\mathscr{L}(y_{i},\cdot)}(z_{i})=\inf_{z\in\mathbb{R}}\Phi_{y_{i}}(z,\omega_{i}), (35) for i=1,2 . In particular, \displaystyle\mathscr{L}(y_{1},z_{1})+\frac{1}{2}\absolutevalue{z_1 - \omega_1}^{2}=\mathcal{M}_{\mathscr{L}(y_{1},\cdot)}(\omega_{1})\leq\mathscr{L}(y_{1},z_{2})+\frac{1}{2}\absolutevalue{z_2 - \omega_1}^{2}\,, (36) \displaystyle\mathscr{L}(y_{2},z_{2})+\frac{1}{2}\absolutevalue{z_2 - \omega_2}^{2}=\mathcal{M}_{\mathscr{L}(y_{2},\cdot)}(\omega_{2})\leq\mathscr{L}(y_{2},z_{1})+\frac{1}{2}\absolutevalue{z_1 - \omega_2}^{2}\,. (37) Hence we deduce : \displaystyle\mathcal{M}_{\mathscr{L}(y_{1},\cdot)}(\omega_{1})-\mathcal{M}_{\mathscr{L}(y_{2},\cdot)}(\omega_{2})\leq\mathscr{L}(y_{1},z_{2})+\frac{1}{2}\absolutevalue{z_2 - \omega_1}^{2}-\mathscr{L}(y_{2},z_{2})-\frac{1}{2}\absolutevalue{z_2 - \omega_2}^{2}\,, (38) \displaystyle\mathcal{M}_{\mathscr{L}(y_{1},\cdot)}(\omega_{1})-\mathcal{M}_{\mathscr{L}(y_{2},\cdot)}(\omega_{2})\geq\mathscr{L}(y_{1},z_{1})+\frac{1}{2}\absolutevalue{z_1 - \omega_1}^{2}-\mathscr{L}(y_{2},z_{1})-\frac{1}{2}\absolutevalue{z_1 - \omega_2}^{2}\,. (39) Furthermore, again by the optimality of z_{i} , we have \Phi_{y_{i}}(z_{i},\omega_{i})\leq\Phi_{y_{i}}(0,\omega_{i}) i.e. : \mathscr{L}(y_{i},z_{i})+\frac{1}{2}\absolutevalue{\omega_i - z_i}^{2}\leq\mathscr{L}(y_{i},0)+\frac{1}{2}\absolutevalue{\omega_i}^{2}\,. (40) for i=1,2 . Since \mathscr{L} is bounded below by Assumption 2.3 by some constant \mu_{L} , we obtain \absolutevalue{z_i-\omega_i}\leq\sqrt{2(\mathscr{L}(y_{i},0)-\mu_{L})+\absolutevalue{\omega_i}^{2}}\,, (41) for i=1,2 . Using the pseudo-Lipschitzness of \mathscr{L} yields: \absolutevalue{z_i-\omega_i}\leq\sqrt{c_{1}+c_{2}\absolutevalue{y_i}^{k}+\absolutevalue{\omega_i}^{2}}\,, (42) for some constants c_{1},c_{2}>0 . Using the triangular inequality, z_{i} is also bounded by a polynomial in |y_{i}|,|\omega_{i}| . Now let i,j=1,2 be distinct. Using the polynomial bounds above, we deduce that \displaystyle\left|\frac{1}{2}|z_{i}-\omega_{j}|^{2}-\frac{1}{2}|z_{i}-\omega_{i}|^{2}\right| \displaystyle=\frac{1}{2}|\omega_{j}-\omega_{i}||2z_{i}-\omega_{j}-\omega_{i}|\leq\frac{1}{2}|\omega_{j}-\omega_{i}|(2|z_{i}|+|\omega_{j}|+|\omega_{i}|)\,, (43) is bounded by a polynomial in |y_{1}|,|y_{2}|,|\omega_{1}|,|\omega_{2}| times |\omega_{1}-\omega_{2}| . All that remains now to conclude using Eq. 38 and Eq. 39 is to deal with the terms \mathscr{L}(y_{j},z_{i})-\mathscr{L}(y_{i},z_{i}) . Next, by the pseudo-Lipschitzness of order k_{L} of \mathscr{L} we have: \displaystyle\mathscr{L}(y_{1},z_{2})-\mathscr{L}(y_{2},z_{2}) \displaystyle\leq L(1+2\absolutevalue{z_2}^{k_{L}-1}+\absolutevalue{y_1}^{k_{L}-1}+\absolutevalue{y_2}^{k_{L}-1})\absolutevalue{y_1-y_2} (44) \displaystyle\mathscr{L}(y_{2},z_{1})-\mathscr{L}(y_{1},z_{1}) \displaystyle\leq L(1+2\absolutevalue{z_1}^{k_{L}-1}+\absolutevalue{y_1}^{k_{L}-1}+\absolutevalue{y_2}^{k_{L}-1})\absolutevalue{y_1-y_2} (45) Similarly, since we can bound the terms |z_{1}|^{k_{L}-1},|z_{2}|^{k_{L}-1} polynomialy in |y_{1}|,|y_{2}|,|\omega_{1}|,|\omega_{2}| , we obtain the desired result. Similarly, we can obtain the corresponding result for \mathscr{R} . ∎ Lemma 5.2 (Coercivity of Moreau Envelopes) . For any coercive function f:\mathbb{R}\to\mathbb{R} lower bounded by C , the Moreau envelope \mathcal{M}_{f(\cdot)} is coercive. Proof of Lemma 5.2 : By the definition of Moreau Envelope form Eq. 6 , we have: \mathcal{M}_{f(\cdot)}(x)=\inf_{y\in\mathbb{R}}\left\{f(y)+\frac{1}{2}\absolutevalue{x - y}^{2}\right\}\,. (46) The coercivity of f implies that for any M>0 , \exists R(M)>0 such that: \forall\absolutevalue{x}>R(M)\implies f(x)>M. (47) Now, set \tilde{R}=R(M)+\sqrt{2(M+|C|)} . Suppose that \absolutevalue{x}>\tilde{R} . Then, for any y\in\mathbb{R} with \absolutevalue{y}>R(M) , we have: f(y)+\frac{1}{2}\absolutevalue{x - y}^{2}\geq f(y)>M\,, (48) while for any y\in\mathbb{R} with \absolutevalue{y}\leq R(M) : \displaystyle f(y)+\frac{1}{2}\absolutevalue{x - y}^{2} \displaystyle\geq\frac{1}{2}\absolutevalue{x - y}^{2}-C\geq\frac{1}{2}(\absolutevalue{x}-\absolutevalue{y})^{2}-C\geq\frac{1}{2}(\absolutevalue{x}-R(M))^{2}-C>\frac{1}{2}(\sqrt{2(M+|C|})^{2}-C\geq M\,, (49) where the last inequality follows since \absolutevalue{x}>\tilde{R}=R(M)+\sqrt{2M} . Therefore, for any y\in\mathbb{R} , we have that f(y)+\frac{1}{2}\absolutevalue{x - y}^{2}>M . Taking the infimum over y , we conclude that \absolutevalue{x}>\tilde{R}\implies\mathcal{M}_{f(\cdot)}(x)\geq M , establishing the coercivity of \mathcal{M}_{f(\cdot)} . ∎ The other two tools that are needed in the subsequent analysis concern the characterization of proximal selections under weak convexity conditions. The following theorem is the main technical tool that allows us to translate weak convexity assumptions on the loss and regularization functions into Lipschitz continuity properties of their proximal operators. Theorem 5.3 (Main Characterization of Proximal Selections) . Suppose f:\mathbb{R}\to\mathbb{R} is lower semi-continuous and prox-coercive. Then the proximal operator \mathcal{P}_{f} of f is never empty-valued, that is, E_{f}=\mathbb{R} . When this condition holds, any proximal selection r_{\min} of f is non-decreasing, almost everywhere differentiable, and the following equivalences are satisfied: (i)\qquad r_{\min}\in C^{0}(\mathbb{R},\mathbb{R})\iff f\text{ is strictly }1\text{-weakly convex}, (50) (ii)\qquad r_{\min}\text{ is }1\text{-Lipschitz continuous over }\mathbb{R}\iff f\text{ is convex}, (51) and for any L\in(1,\infty) , (iii)\qquad r_{\min}\text{ is }L\text{-Lipschitz continuous over }\mathbb{R}\iff f\text{ is }\frac{L}{L-1}\text{-weakly convex}. (52) Furthermore, when any of these conditions hold, r_{\min} is uniquely determined by the set equality \forall\delta\in\mathbb{R},\quad\mathcal{P}_{f}(\delta)=\{r_{\min}(\delta)\}\,. (53) In this case, r_{\min} is onto, and for r_{0}\in\mathbb{R} , the interval over which r_{\min} takes the constant value r_{0} is given by [r_{0}+f^{\prime}_{-}(r_{0}),r_{0}+f^{\prime}_{+}(r_{0})]\,. (54) In particular, r_{\min} is increasing if and only if f is differentiable. The following corollary establishes that Assumption 2.4 guarantees the existence and uniqueness of Lipschitz continuous proximal selections for both the loss and regularization functions appearing in Eq. 14 . Corollary 5.4 (Scaled Proximal Operators) . Let f:\mathbb{R}\to\mathbb{R} be V_{0} -weakly convex for some V_{0}>0 . For any V\in(0,V_{0}) , Vf is V_{0}/V -weakly convex and E_{Vf}=\mathbb{R} . Furthermore, with L=\frac{V_{0}}{V_{0}-V} , there exists a unique L -Lipschitz continuous selection \tilde{r}:\mathbb{R}\to\mathbb{R} such that \forall\delta\in\mathbb{R},\>\tilde{r}(\delta)\in\argmin_{r\in\mathbb{R}}\left\{\frac{(\delta-r)^{2}}{2}+Vf(r)\right\}. Moreover under Assumption 2.4 the function \mathscr{L}(y,\cdot) (respectively \mathscr{R} ) define a unique L_{L} -Lipschitz continuous (respectively L_{R} -Lipschitz continuous) selection of their respective proximal operators. The proofs of Theorems 5.3 and 5.4 are deferred to Appendix A . 5.2 Technical Framework Our analysis relies on two theoretical frameworks: Generalized Approximate Message Passing (GAMP) and the Gaussian Min-max Theorem (GMT). GAMP is a class of iterative algorithms characterized by coupled iterations, as in Algorithm 1 , which we defined from a set of separable functions \{{g^{t}},{f^{t}}\}_{t\geq 0} and their associated Onsager correction terms b^{t},c^{t} defined as b^{t}:=\frac{1}{d}\sum_{\mu=1}^{n}\partial{g^{t}}\quantity(p_i^t, y_i)\,,\quad c^{t}:=\frac{1}{d}\sum_{i=1}^{d}\partial{f^{t}}\quantity(w_j^t)\,, (55) where derivatives are taken with respect to the first argument. In the high-dimensional limit of Assumption 2.1 , the algorithm admits a dimensional reduction through its State Evolution equations ( Javanmard and Montanari, 2013 ; Berthier et al., 2020 ; Feng et al., 2022 ; Gerbelot and Berthier, 2023 ) . These equations track one-dimensional statistics of the iterates through \displaystyle\beta_{t} \displaystyle=\frac{\mathbb{E}\quantity[ \tilde{w} \inden[t]( \mu_t \tilde{w} + u^t ) ]}{\mathbb{E}\quantity[(\tilde{w})^2]}\,, (56) \displaystyle\Omega_{s,t} \displaystyle=\mathbb{E}\quantity[ \inden[s](\mu_s \tilde{w} + u^{s}) \inden[t](\mu_t \tilde{w} + u^{t}) ]-\mathbb{E}\quantity[(\tilde{w})^2]\beta_{t}\beta_{s}\,, (57) \displaystyle\mu_{t+1} \displaystyle=\alpha\mathbb{E}\quantity[ v^\star\outden[t](\beta_t v^\star+ v^t) ]\,, (58) \displaystyle\Sigma_{s+1,t+1} \displaystyle=\alpha\mathbb{E}\quantity[ \outden[s](\beta_s v^\star+ v^s) \outden[t](\beta_t v^\star+ v^t) ]\,, (59) where (u^{1},\dots u^{t})\sim\mathcal{N}(\boldsymbol{0},\boldsymbol{\Sigma}) and (v^{0},\dots v^{t})\sim\mathcal{N}(\boldsymbol{0},\boldsymbol{\Omega}) are independent Gaussian vectors, v^{\star}\sim\mathcal{N}(0,1) and \tilde{w} comes from Assumption 2.2 . The previous quantities are defined recursively from the initial condition \mu_{0}=\mathbb{E}\quantity[\tilde{w} \outden[0](u^0)] and \Sigma_{0,0}=\mathbb{E}\quantity[ \outden[0](u^0)^2 ] where u_{0} is distributed as the initialisation of the problem. The validity of the state evolution equations is then provided by the following result: Theorem 5.5 ( Javanmard and Montanari (2013) ; Berthier et al. (2020) ; Gerbelot and Berthier (2023) ) . Consider Algorithm 1 with pseudo-Lipschitz functions \{{f^{t}},{g^{t}}\}_{t\geq 0} and initialization {\mathbf{w}}^{0} such that the joint empirical distribution of ({\mathbf{w}}^{0},\tilde{{\mathbf{w}}}) converges almost surely to a probability measure P_{0} on \mathbb{R}^{2} with bounded k -th moments for some k\geq 2 . Let u^{0} and \tilde{w} denote random variables with law P_{0} , and define the initial values for the recursion as \mu_{0}=\mathbb{E}\quantity[\tilde{w} \outden[0](u^0)]\,,\quad\Sigma_{0,0}=\mathbb{E}\quantity[ \outden[0](u^0)^2 ]\,. (60) Then, under Assumption 2.1 , for any finite time t\in\mathbb{N} and any pseudo-Lipschitz function \psi:\mathbb{R}^{t+1}\rightarrow\mathbb{R} , we have \displaystyle\frac{1}{d}\sum_{i=1}^{d}\psi(\tilde{w}_{i},w^{1}_{i},\dots,w^{t}_{i})-\mathbb{E}\quantity[\psi(\tilde{w}, \mu_1 \tilde{w} + u^1, \dots, \mu_t \tilde{w} + u^t) ] \displaystyle\xrightarrow{a.s.}0\,, (61) \displaystyle\frac{1}{n}\sum_{\mu=1}^{n}\psi(p^{\star}_{\mu},p^{0}_{\mu},\dots,p^{t}_{\mu})-\mathbb{E}\quantity[\psi(v^\star, \beta_0 v^\star+ v^0, \dots, \beta_t v^\star+ v^t ) ] \displaystyle\xrightarrow{a.s.}0\,, (62) where (u^{1},\dots u^{t}) and (v^{0},\dots v^{t}) denote zero-mean Gaussian vectors with (u^{1},\dots u^{t})\sim\mathcal{N}(\boldsymbol{0},\boldsymbol{\Sigma}) and (v^{0},\dots v^{t})\sim\mathcal{N}(\boldsymbol{0},\boldsymbol{\Omega}) where \boldsymbol{\Sigma},\boldsymbol{\Omega}\in\mathbb{R}^{{(t+1)}\times{(t+1)}} are defined recursively by Eqs. 56 , 57 , 58 and 59 with initial conditions Eq. 60 and with p_{\mu}^{\star}=\mathbf{x}_{\mu}^{\top}\tilde{{\mathbf{w}}}/\sqrt{d} . For any value t\in\mathbb{N} we also note that one can estimate the value of the minimizer with \hat{\mathbf{w}}^{t}={f^{t}}({\mathbf{w}}^{t}) ( Feng et al., 2022 ) , where {\mathbf{w}}^{t} is the iterate from Algorithm 1 . Complementing the previous is Gordon’s Gaussian comparison inequality ( Gordon, 1988 ) , that allows us to study challenging non-convex optimization problems by comparing them to simpler auxiliary problems involving only vectorial Gaussian processes. Theorem 5.6 (GMT Gordon (1988) ) . Let \boldsymbol{G}\in\mathbb{R}^{m\times n} be an i.i.d. standard normal matrix and \mathbf{g}\in\mathbb{R}^{m} , \mathbf{h}\in\mathbb{R}^{n} two i.i.d. standard normal vectors independent of one another. Let \mathcal{S}_{{\mathbf{w}}} , \mathcal{S}_{\boldsymbol{u}} be two compact sets such that \mathcal{S}_{{\mathbf{w}}}\subset\mathbb{R}^{n} and \mathcal{S}_{\boldsymbol{u}}\subset\mathbb{R}^{m} . Consider the two following optimization problems for any continuous \psi on \mathcal{S}_{{\mathbf{w}}}\times\mathcal{S}_{\boldsymbol{u}} \displaystyle\mathbf{C}(\boldsymbol{G}) \displaystyle:=\min_{{\mathbf{w}}\in\mathcal{S}_{{\mathbf{w}}}}\max_{\boldsymbol{u}\in\mathcal{S}_{\boldsymbol{u}}}\boldsymbol{u}^{\top}\boldsymbol{G}{\mathbf{w}}+\psi({\mathbf{w}},\boldsymbol{u}) (63) \displaystyle\mathcal{C}(\mathbf{g},\mathbf{h}) \displaystyle:=\min_{{\mathbf{w}}\in\mathcal{S}_{{\mathbf{w}}}}\max_{\boldsymbol{u}\in\mathcal{S}_{\boldsymbol{u}}}\|{\mathbf{w}}\|_{2}\mathbf{g}^{\top}\boldsymbol{u}+\|\boldsymbol{u}\|_{2}\mathbf{h}^{\top}{\mathbf{w}}+\psi({\mathbf{w}},\boldsymbol{u}) (64) Then for all c\in\mathbb{R} we have \Pr[\mathbf{C}(\boldsymbol{G})0 such that: \frac{1}{n}\sum_{\mu=1}^{n}\mathscr{L}(y_{\mu},Z_{\mu})\leq C_{L}(a)+C^{\prime}\,, (72) with probability at least 1-2\exp(-cn) for some absolute constant c>0 . Since \mathscr{L} is bounded below by some \mu_{L} , we have \alpha\mu_{L}+\frac{1}{d}\sum_{i=1}^{d}\mathscr{R}\left(\hat{w}_{i}\right)\leq\alpha(C_{L}(a)+C^{\prime})+\mathscr{R}(\sqrt{a})\,, (73) with probability at least 1-2\exp(-cn) . Under Assumption 2.3 , using the quadratic lower bound \mathscr{R}(w)\geq C_{R}w^{2} for |w|\geq W_{0} we have that Eq. 73 implies: \frac{1}{d}\sum_{i=1}^{d}\hat{w}_{i}^{2}\leq C\left(\alpha,a,\mu_{L},\mathscr{R}(\sqrt{a}),C_{R},W_{0}\right), (74) with probability at least 1-2\exp(-cn) , where the constant is independent of d,n . Therefore \frac{1}{d}\|\hat{\mathbf{w}}\|_{2}^{2}\leq C_{w} with probability at least 1-2\exp(-cn) for some C_{w}>0 . To bound \hat{{\mathbf{z}}} we recall that \hat{{\mathbf{z}}}=\frac{1}{\sqrt{d}}\boldsymbol{X}\hat{\mathbf{w}} . We start by applying ( Vershynin, 2018 , Theorem 4.4.5) with t=\sqrt{d} , which gives \frac{1}{\sqrt{d}}\norm{\datamat}_{\mathrm{op}}\leq K(2+\sqrt{\alpha})=:C_{\mathrm{op}}\,, (75) with probability at least 1-2\exp(-d) for a positive constant K . We can thus bound the following \frac{1}{n}\norm{\hat{\z}}_{2}^{2}\leq\frac{1}{d}\norm{\datamat}_{\mathrm{op}}^{2}\frac{1}{\alpha}\frac{1}{d}\norm{\what}_{2}^{2}\leq\frac{C_{\mathrm{op}}^{2}C_{w}}{\alpha}\,, (76) with probability at least 1-2\exp(-d) . By the optimality conditions of Eq. 68 we have that \hat{f}_{\mu}\in\partial_{z}\mathscr{L}(y_{\mu},z_{\mu}) . To bound the norm of \hat{\mathbf{f}} , since \mathscr{L} is pseudo-Lipschitz of some order k_{L} with constant C^{\prime\prime}>0 , and \frac{1}{\sqrt{n}}\hat{{\mathbf{z}}} is bounded with high probability, one can adopt the following \frac{1}{n}\|\hat{\mathbf{f}}\|_{2}^{2}\leq\frac{C^{\prime\prime}}{n}\sum_{\mu}(1+|z_{\mu}|^{k_{L}-1}+|y_{\mu}|^{k_{L}-1})^{2}\,, (77) An application of the Borel–Cantelli lemma then ensures that the above bounds on \hat{{\mathbf{w}}},\hat{{\mathbf{z}}},\hat{\mathbf{f}} hold almost surely. ∎ Remark 6.1 . If we just suppose that \mathscr{R}(w)\geq C_{R}\absolutevalue{w} for some C_{R}>0 , by the equivalence of norms in any finite dimension, we have that \frac{1}{d}\norm{\w}_{2}^{2}\leq\norm{\w}_{1}\leq C_{w}d . This allows us to apply Theorem 5.6 in any finite dimension d but the convergence of the extremizers of the high dimensional problem has to be considered separately. Proof of Proposition 4.1 : The start of our analysis is the problem in Eq. 68 with the restriction of the extremization domain {\mathcal{A}}^{\star}_{d}=\inf_{{\mathbf{w}}\in\mathcal{S}_{C,d},{\mathbf{z}}\in\mathcal{S}_{C,n}}\sup_{\mathbf{f}\in\mathcal{S}_{C,n}}\frac{1}{d}\quantity[ \frac{1}{\sqrt{d}} \f^\top\datamat\w- \f^\top\z+ \sum_{\dataidx=1}^{n} \lossfun\qty(y_\dataidx, z_\dataidx) + \sum_{\dimidx=1}^{d} \regfun\qty(w_\dimidx) ]\,, (78) with C the constant determined by Proposition 6.1 . Additionally we introduce the norm q=\norm{\w}_{2}^{2}/d and the overlap with the teacher m=\tilde{{\mathbf{w}}}^{\top}{\mathbf{w}}/d obtaining \displaystyle{\mathcal{A}}^{\star}_{d}=\inf_{{\mathbf{w}},{\mathbf{z}},q,m}\sup_{\mathbf{f},\eta,\nu}\frac{1}{d}\Bigg[ \displaystyle\frac{1}{\sqrt{d}}\mathbf{f}^{\top}\boldsymbol{X}{\mathbf{w}}-\mathbf{f}^{\top}{\mathbf{z}}+\sum_{\mu=1}^{n}\mathscr{L}\quantity(y_\dataidx, z_\dataidx)+\sum_{i=1}^{d}\mathscr{R}\quantity(w_\dimidx)+\nu(md-\tilde{{\mathbf{w}}}^{\top}{\mathbf{w}})+\frac{\eta}{2}(\norm{\w}_{2}^{2}-qd)\Bigg] (79) where because of Cauchy-Schwartz we have that q\geq m^{2}/\rho , where recall that by Assumption 2.2 \norm{\wteacher}_{2}^{2}/d\to\rho . Now we want to separate the data dependence between the teacher subspace and the one orthogonal to the teacher subspace. We define {\mathbf{s}}=\boldsymbol{X}\tilde{{\mathbf{w}}}/\sqrt{d\rho} and introduce an independent Gaussian matrix \tilde{\boldsymbol{X}} where \tilde{X}_{ij}\sim\mathcal{N}(0,1) and we have that in distribution is the same as \displaystyle{\mathcal{A}}^{\star}_{d}=\inf_{{\mathbf{w}},{\mathbf{z}},m,q}\sup_{\mathbf{f},\nu,\eta} \displaystyle\frac{m}{\sqrt{\rho}}\frac{\mathbf{f}^{\top}{\mathbf{s}}}{d}+\frac{1}{\sqrt{d^{3}}}\mathbf{f}^{\top}\tilde{\boldsymbol{X}}\quantity(\w- \frac{m}{\rho}\wteacher)-\frac{\mathbf{f}^{\top}{\mathbf{z}}}{d}+\frac{1}{d}\sum_{\mu=1}^{n}\mathscr{L}\quantity(y_\dataidx, z_\dataidx) (80) \displaystyle+\frac{1}{d}\sum_{i=1}^{d}\mathscr{R}\quantity(w_\dimidx)+\nu m-\nu\frac{\tilde{{\mathbf{w}}}^{\top}{\mathbf{w}}}{d}+\frac{\eta}{2}\frac{\norm{\w}_{2}^{2}}{d}-\frac{\eta q}{2}\,. (81) Having expressed {\mathcal{A}}^{\star}_{d} in the above min-max form, we recognize a problem of the form of Eq. 63 from Theorem 5.6 with \mathbf{G}=\tilde{\boldsymbol{X}} . We can can therefore write down a lower bound as \forall c\in\mathbb{R}\,,\quad\Pr[{\mathcal{A}}^{\star}_{d}0}\frac{\tau}{2}+\frac{\norm{\vv}_{2}^{2}}{2\tau} for any vector \mathbf{v} and get \displaystyle\tilde{A}_{d}\geq\sup_{\kappa,\nu,\eta}\inf_{{\mathbf{w}},{\mathbf{z}},m,q,\tau} \displaystyle\frac{\tau\kappa}{2}+\frac{\kappa}{2\tau d}\norm{\frac{m}{\sqrt{\rho}} \s+ \sqrt{q - \frac{m^2}{\rho}} \gaussvectwo- \z}_{2}^{2}-\frac{\kappa}{d}\mathbf{g}^{\top}\quantity(\w- \frac{m}{\rho} \wteacher) (88) \displaystyle+\frac{1}{d}\sum_{\mu=1}^{n}\mathscr{L}\quantity(y_\dataidx, z_\dataidx)+\frac{1}{d}\sum_{i=1}^{d}\mathscr{R}\quantity(w_\dimidx)+\nu m-\nu\frac{\tilde{{\mathbf{w}}}^{\top}{\mathbf{w}}}{d}+\frac{\eta}{2}\frac{\norm{\w}_{2}^{2}}{d}-\frac{\eta q}{2}\,. (89) We recognize the definition of Moreau envelope and get \displaystyle\tilde{A}_{d}\geq\sup_{\kappa,\nu,\eta}\inf_{{\mathbf{w}},m,q,\tau} \displaystyle\frac{\tau\kappa}{2}+\frac{1}{d}\sum_{\mu=1}^{n}\frac{\kappa}{\tau}\mathcal{M}_{\frac{\tau}{\kappa}\mathscr{L}(y_{\mu},\cdot)}\quantity(\frac{m}{\sqrt{\rho}} s_\dataidx+ \sqrt{q - \frac{m^2}{\rho}} h_\dataidx)+\frac{m}{\rho}\frac{\kappa}{d}\mathbf{g}^{\top}\tilde{{\mathbf{w}}} (90) \displaystyle+\frac{1}{d}\sum_{i=1}^{d}\mathscr{R}\quantity(w_\dimidx)-\frac{\kappa}{d}\mathbf{g}^{\top}{\mathbf{w}}-\nu\frac{\tilde{{\mathbf{w}}}^{\top}{\mathbf{w}}}{d}+\frac{\eta}{2}\frac{\norm{\w}_{2}^{2}}{d}+\nu m-\frac{\eta q}{2}\,. (91) We now consider the last minimization over {\mathbf{w}} . To perform it we first complete the square \displaystyle\tilde{A}_{d}\geq\sup_{\kappa,\nu,\eta}\inf_{{\mathbf{w}},m,q,\tau} \displaystyle\frac{\tau\kappa}{2}+\frac{1}{d}\sum_{\mu=1}^{n}\frac{\kappa}{\tau}\mathcal{M}_{\frac{\tau}{\kappa}\mathscr{L}(y_{\mu},\cdot)}\quantity(\frac{m}{\sqrt{\rho}} s_\dataidx+ \sqrt{q - \frac{m^2}{\rho}} h_\dataidx)+\frac{m}{\rho}\frac{\kappa}{d}\mathbf{g}^{\top}\tilde{{\mathbf{w}}} (92) \displaystyle+\frac{1}{d}\sum_{i=1}^{d}\mathscr{R}\quantity(w_\dimidx)+\frac{\eta}{2d}\norm{\w- \frac{1}{\eta}(\kappa\gaussvecone+ \nu\wteacher)}_{2}^{2}-\frac{1}{2d\eta}\norm{\nu\wteacher+ \kappa\gaussvecone}_{2}^{2}+\nu m-\frac{\eta q}{2}\,. (93) We now restrict the domain of \eta to positive values, which is necessary for the completed square to define a minimization over {\mathbf{w}} . Since we are establishing a lower bound, this restriction of the supremum domain only preserves or strengthens the inequality. We then apply the definition of the Moreau envelope \displaystyle\tilde{A}_{d}\geq\sup_{\kappa,\nu,\eta}\inf_{m,q,\tau} \displaystyle\frac{\tau\kappa}{2}+\frac{1}{d}\sum_{\mu=1}^{n}\frac{\kappa}{\tau}\mathcal{M}_{\frac{\tau}{\kappa}\mathscr{L}(y_{\mu},\cdot)}\quantity(\frac{m}{\sqrt{\rho}} s_\dataidx+ \sqrt{q - \frac{m^2}{\rho}} h_\dataidx)+\frac{m}{\rho}\frac{\kappa}{d}\mathbf{g}^{\top}\tilde{{\mathbf{w}}} (94) \displaystyle+\frac{1}{d}\sum_{\mu=1}^{d}\eta\mathcal{M}_{\frac{1}{\eta}\mathscr{R}(\cdot)}\quantity(\frac{1}{\eta} \qty(\nu(\wteacher)_\dimidx+ \kappa g_\dimidx) )-\frac{1}{2d\eta}\norm{\nu\wteacher+ \kappa\gaussvecone}_{2}^{2}+\nu m-\frac{\eta q}{2}\,, (95) where the optimization is taken over the set \mathcal{S}=\quantity{(m,q,\tau,\kappa, \nu, \eta) \in\RR^6 \mid\frac{m^2}{\rho} \leq q , a \leq q \leq b, \tau> 0, \eta> 0, \kappa\geq 0}\,. (96) Define the following high-dimensional objective: \displaystyle\mathcal{E}_{d}(m,q,\tau,\kappa,\nu,\eta) \displaystyle\mathrel{\mathop{:}}=\frac{\tau\kappa}{2}+\frac{1}{d}\sum_{\mu=1}^{n}\frac{\kappa}{\tau}\mathcal{M}_{\frac{\tau}{\kappa}\mathscr{L}(y_{\mu},\cdot)}\quantity(\frac{m}{\sqrt{\rho}} s_\dataidx+ \sqrt{q - \frac{m^2}{\rho}} h_\dataidx)+\frac{m}{\rho}\frac{\kappa}{d}\mathbf{g}^{\top}\tilde{{\mathbf{w}}} (97) \displaystyle+\frac{1}{d}\sum_{\mu=1}^{d}\eta\mathcal{M}_{\frac{1}{\eta}\mathscr{R}(\cdot)}\quantity(\frac{1}{\eta} \qty(\nu(\wteacher)_\dimidx+ \kappa g_\dimidx) )-\frac{1}{2d\eta}\norm{\nu\wteacher+ \kappa\gaussvecone}_{2}^{2}+\nu m-\frac{\eta q}{2}\,. We are left with taking the high dimensional limit of \mathcal{E}_{d}(m,q,\tau,\kappa,\nu,\eta) . By Lemma 5.1 , the Moreau envelopes are pseudo-Lipschitz of finite order. By the Strong Law of Large Numbers we have that \frac{1}{d}\sum_{i=1}^{d}\eta\mathcal{M}_{\frac{1}{\eta}\mathscr{R}(\cdot)}\quantity(\frac{1}{\eta} \qty(\nu(\wteacher)_\dimidx+ \kappa g_\dimidx) )-\mathbb{E}\quantity[ \eta\mathcal{M}_{\frac{1}{\eta} \regfun(\cdot)} \qty(\frac{1}{\eta} \qty(\nu\tilde{w} + \kappa g) ) ]\xrightarrow{a.s.}0\,, (98) and likewise for the term with \mathscr{L} . Subsequently, by the Borel-Cantelli Lemma and standard concentration inequalities for Gaussian random variables, we obtain that, as n,d\to\infty , \norm{\gaussvecone}_{2}^{2}/d\xrightarrow{a.s.}1 and that for any \mathbf{v}\in\mathbb{R}^{d} , \mathbf{v}^{\top}\mathbf{g}/d\xrightarrow{a.s.}0 . This yields the point-wise a.s. convergence of \mathcal{E}_{d}(m,q,\tau,\kappa,\nu,\eta) to the dimension-independent deterministic objective \mathcal{E} : \mathcal{E}_{d}(m,q,\tau,\kappa,\nu,\eta)\xrightarrow[d\rightarrow\infty]{a.s.}\mathcal{E}(m,q,\tau,\kappa,\nu,\eta)\,, (99) where we recall the definition of \mathcal{E} from Eq. 9 as being \displaystyle\mathcal{E}(m,q,\tau,\kappa,\nu,\eta) \displaystyle\mathrel{\mathop{:}}=\frac{\tau\kappa}{2}+\alpha\mathbb{E}\quantity[ \frac{\kappa}{\tau}\mathcal{M}_{\frac{\tau}{\kappa} \lossfun(y, \cdot)} \qty(\frac{m}{\sqrt{\rho}} s + \sqrt{q - \frac{m^2}{\rho}} h) ] (100) \displaystyle+\mathbb{E}\quantity[ \eta\mathcal{M}_{\frac{1}{\eta} \regfun(\cdot)} \qty(\frac{1}{\eta} \qty(\nu\tilde{w} + \kappa g) ) ]-\frac{1}{2\eta}(\nu^{2}\rho+\kappa^{2})+\nu m-\frac{\eta q}{2}\,. (101) We next translate the pointwise convergence of \mathcal{E}_{d} to \mathcal{E} into convergence of the extremal values associated with the sup-inf objective. This is done in Lemmas 6.2 and 6.3 and the proof is then completed. ∎ By Assumption 2.3 the expectations of Moreau operators and thus \mathcal{E}_{d}(m,q,\tau,\kappa,\nu,\eta) are equi-continuous in the parameters m,q,\tau,\kappa,\nu,\eta . Therefore, by the Arzela-Ascoli Theorem, \mathcal{E}_{d}(m,q,\tau,\kappa,\nu,\eta) converges uniformly on compact sets. The following Lemma shows that the sequence of extremizers m,q,\tau,\kappa,\nu,\eta can be restricted to fixed compact sets. Lemma 6.2 . Under Assumption 2.3 there exists a compact set \mathcal{S} with a diameter independent of d such that the extremizers of \mathcal{E}_{d} in Eq. 97 which we denote by (\hat{m}_{d},\hat{q}_{d},\hat{\tau}_{d},\hat{\kappa}_{d},\hat{\nu}_{d},\hat{\eta}_{d}) satisfy \Pr[\cap_{d\geq d_{0}}\quantity{ (\hat{m}_d, \hat{q}_d, \hat{\tau}_d, \hat{\kappa}_d, \hat{\nu}_d, \hat{\eta}_d) \in\mathcal{S} }]\rightarrow 1\,, (102) as d_{0}\rightarrow\infty . Proof of Lemma 6.2 : From Proposition 6.1 we have that the optimal values of \hat{q}_{d} and \hat{\kappa}_{d} are finite because q_{d}=\norm{\w}_{2}^{2}/d and \kappa_{d}=\norm{\f}_{2}/d . Moreover, the finiteness of the optimal value for \hat{m}_{d} follows from an application of the Cauchy-Schwarz inequality. We want now to prove that the optimal value of the remaining parameters is finite as well. We notice the following uniform upper bound of the Moreau envelope of the regularization \frac{1}{d}\eta\mathcal{M}_{\frac{1}{\eta}\mathscr{R}(\cdot)}\quantity( \frac{1}{\eta}\qty(\nu(\wteacher)_i + \kappa g_i) )\leq\frac{1}{d}\mathscr{R}(0)+\frac{1}{2d\eta}\quantity(\nu(\wteacher)_i + \kappa g_i)^{2}\,. (103) By setting m=0 and taking \tau\to 0^{+} in the inner problem, the above inequality implies that for any fixed \kappa and \nu , as \eta\to\infty the objective \mathcal{E}_{d} tends to -\infty . This forces the optimal \hat{\eta}_{d} to remain bounded. Similarly, with \eta_{d} and \kappa_{d} bounded, one may apply again Eq. 103 in the definition of \mathcal{E}_{d} yields that the terms depending on \nu satisfy \frac{1}{d}\sum_{\mu=1}^{d}\eta\mathcal{M}_{\frac{1}{\eta}\mathscr{R}(\cdot)}\quantity(\frac{1}{\eta} \qty(\nu(\wteacher)_\dimidx+ \kappa g_\dimidx) )-\frac{1}{2d\eta}\norm{\nu\wteacher+ \kappa\gaussvecone}_{2}^{2}+\nu m\leq\mathscr{R}(0)+\nu m\,. (104) For any fixed \varepsilon>0 , setting m=\varepsilon in the inner minimization gives an upper bound on \mathcal{E}_{d} . As \nu\to+\infty , the term \nu\varepsilon dominates, forcing \mathcal{E}_{d}\to-\infty . Similarly, setting m=-\varepsilon yields \mathcal{E}_{d}\to-\infty as \nu\to-\infty . Since the supremum of \mathcal{E}_{d} over \nu must be finite, the optimal \hat{\nu}_{d} is necessarily bounded. Finally, for the parameter \tau , note that for fixed and finite \kappa we have \lim_{\tau\rightarrow+\infty}\frac{1}{d}\frac{\kappa}{\tau}\mathcal{M}_{\frac{\tau}{\kappa}\mathscr{L}(y_{\mu},\cdot)}\quantity( \frac{m}{\sqrt{\rho}} s_\dataidx+ \sqrt{q - \frac{m^2}{\rho}} h_\dataidx)=\frac{1}{d}\inf_{z\in\mathbb{R}}\mathscr{L}(y_{\mu},z) (105) and by Assumption 2.3 the right-hand side is lower bounded. Hence, \mathcal{E}_{d}(m,q,\tau,\kappa,\nu,\eta) tends to +\infty as \tau\to+\infty , which implies that the optimal \hat{\tau}_{d} must also be bounded. We conclude that there exists an R>0 , independent of d , such that \absolutevalue{\hat{m}_d}\leq R\,,\absolutevalue{\hat{q}_d}\leq R\,,\absolutevalue{\hat{\tau}_d}\leq R\,,\absolutevalue{\hat{\kappa}_d}\leq R\,,\absolutevalue{\hat{\nu}_d}\leq R\,,\absolutevalue{\hat{\eta}_d}\leq R\,. (106) That is, the extremizers (\hat{m}_{d},\hat{q}_{d},\hat{\tau}_{d},\hat{\kappa}_{d},\hat{\nu}_{d},\hat{\eta}_{d}) lie in the compact set \mathcal{S}\cap B(R) , where \mathcal{S} is defined in Eq. 96 . This completes the proof. ∎ In light of Lemma 6.2 , we define \tilde{\mathcal{E}}_{d} to be the restriction of \mathcal{E}_{d} to the compact set \mathcal{S} defined from the previous result. Lemma 6.3 . In the high-dimensional limit d,n\to\infty of Assumption 2.1 we have that \absolutevalue{ \sup_{\kappa, \nu, \eta} \min_{m, q, \tau} \tilde{\mathcal{E}}_d(m, q, \tau, \kappa, \nu, \eta) - \minriskfun}\xrightarrow[d\to\infty]{a.s.}0 (107) where {\mathcal{A}}^{\star} is defined in Eq. 16 . Proof of Lemma 6.3 : Let \mathcal{S}_{d,C} denote the following event \mathcal{S}_{d,C}\coloneqq\quantity{ \frac{1}{d} \norm{\mathbf{s}}_1 < C, \frac{1}{d}\norm{\gaussvecone}_1 < C, \frac{1}{d}\norm{\mathbf{\tilde{w}}}_1 < C, \frac{1}{d}\norm{\mathbf{h}}_1 < C}\,, (108) where C denotes a fixed positive constant. Then, concentration of sub-Gaussian random variables ( Vershynin, 2018 ) and the Borel-Cantelli Lemma imply that \exists C>0 such that: \lim_{d\rightarrow\infty}\Pr[\mathcal{S}_{d,C}]=1 (109) Assumption 2.3 then implies that over \mathcal{S}_{d,C} , the objective \mathcal{E}_{d} is equicontinuous in m,q,\tau,\kappa,\nu,\eta . The Lemma then follows by noting that point-wise convergence on a dense set for equicontinuous functions implies point-wise convergence everywhere. ∎ We are now interested in showing an equivalent description of the limiting energy that comes after the minimization over the low dimensional parameters (m,q,\tau,\kappa,\nu,\eta) . Corollary 6.4 (Stationary Condition) . Any (m,q,\tau,\kappa,\nu,\eta)\in\mathcal{S}^{\star} satisfies the following set of equations \displaystyle\partial_{\eta}: \displaystyle q=\mathbb{E}\quantity[ \mathcal{P}_{\frac{1}{\eta} \regfun(\cdot)} \qty(\frac{1}{\eta} (\nu\tilde{w} + \kappa g))^2 ] (110) \displaystyle\partial_{\nu}: \displaystyle m=\mathbb{E}\quantity[ \tilde{w} \mathcal{P}_{\frac{1}{\eta} \regfun(\cdot)} \qty(\frac{1}{\eta} (\nu\tilde{w} + \kappa g)) ] \displaystyle\partial_{\kappa}: \displaystyle\tau=\mathbb{E}\quantity[ g \mathcal{P}_{\frac{1}{\eta} \regfun(\cdot)} \qty(\frac{1}{\eta} (\nu\tilde{w} + \kappa g)) ] \displaystyle\partial_{m}: \displaystyle\nu=\alpha\mathbb{E}\quantity[ \qty(\frac{s}{\sqrt{\rho}} - \frac{\sfrac{m}{\rho} h}{\sqrt{q - \frac{m^2}{\rho}}}) \mathcal{P}_{\frac{\tau}{\kappa}\lossfun(y,\cdot)} \qty(\frac{m}{\sqrt{\rho}} s + \sqrt{q - \frac{m^2}{\rho^2}} h) ] \displaystyle\partial_{\tau}: \displaystyle\kappa^{2}=\frac{\alpha\kappa^{2}}{\tau^{2}}\mathbb{E}\quantity[ \qty( \frac{m}{\sqrt{\rho}} s + \sqrt{q - \frac{m^2}{\rho}} h - \mathcal{P}_{\frac{\tau}{\kappa}\lossfun(y,\cdot)} \qty(\frac{m}{\sqrt{\rho}} s + \sqrt{q - \frac{m^2}{\rho}} h) )^2 ] \displaystyle\partial_{q}: \displaystyle\alpha\frac{\kappa}{\tau}-\eta=\frac{\alpha}{\sqrt{q-\frac{m^{2}}{\rho}}}\mathbb{E}\quantity[ h \, \mathcal{P}_{\frac{\tau}{\kappa}\lossfun(y,\cdot)} \qty(\frac{m}{\sqrt{\rho}} s + \sqrt{q - \frac{m^2}{\rho}} h) ] where the expectation is taken over s,g,h\sim\mathcal{N}(0,1) , \tilde{w}\sim\pi_{\tilde{{\mathbf{w}}}} and y\sim P(\cdot\mid s) from Assumption 2.2 . Proof of Corollary 6.4 : These fixed point equations can be found by application of the two following rules \frac{\partial\mathcal{M}_{\tau f}(z)}{\partial z}=z-\mathcal{P}_{\tau f}(z)\,,\quad\frac{\partial\left(\frac{1}{\tau}\mathcal{M}_{\tau f}(z)\right)}{\partial\tau}=-\frac{\left(z-\mathcal{P}_{\tau f}(z)\right)^{2}}{2\tau^{2}}\,. (111) they hold almost everywhere because of the regularity assumptions made, specifically Assumption 2.3 . Non-emptiness of proximals is because of assumptions made on \mathscr{L} and \mathscr{R} as described in Appendix A . ∎ Remark 6.2 . Since \mathcal{M} is pseudo-Lipschitz from Assumption 2.3 and Lemma 5.1 , it is differentiable almost everywhere. Dominated convergence theorem (finite differences dominated by the pseudo-Lipschitzness) then ensures that the above expressions are well-defined. Corollary 6.5 . For any (m^{\star},q^{\star},\tau^{\star},\kappa^{\star},\nu^{\star},\eta^{\star})\in\mathcal{S}^{\star} defined in Eq. 12 , it holds that {\mathcal{A}}^{\star}=\alpha\mathbb{E}\quantity[ \lossfun\qty(y, \mathcal{P}_{\frac{\tau^\star}{\kappa^\star}\lossfun(y,\cdot)} \qty(\frac{m^\star}{\sqrt{\rho}} s + \sqrt{q^\star- \frac{(m^\star)^2}{\rho}} h)) ]+\mathbb{E}\quantity[ \regfun\qty(\mathcal{P}_{\frac{1}{\eta^\star} \regfun(\cdot)} \qty(\frac{1}{\eta^\star} (\nu^\star\tilde{w} + \kappa^\star g))) ]\,, (112) where the expectation is taken over s,g,h\sim\mathcal{N}(0,1) , \tilde{w}\sim\pi_{\tilde{{\mathbf{w}}}} and y\sim P(\cdot\mid s) from Assumption 2.2 . Proof of Corollary 6.5 : First we notice that one can always write the Moreau envelope as \mathcal{M}_{f}(\omega)=f\quantity(z)+\frac{1}{2}\quantity(z - \omega)^{2}\,, (113) for any z\in\mathcal{P}_{f}(\omega) , which is non-empty by 2.3 and 2.4 about \mathscr{L} and \mathscr{R} . We can thus exchange the two Moreau envelopes in Eq. 9 with the previous identities. Then it follows from algebraic manipulation of the equations presented in Corollary 6.4 the final form we are interested in. ∎ 7 Proofs for the Upper Bound We will now construct a sequence of iterates of the approximate message passing algorithm attaining the lower bound defined by Proposition 4.1 with the goal in mind of proving Lemma 4.2 . We will analyze two different instances of Algorithm 1 with different choices of non linear functions \{{f^{t}}\}_{t\geq 0} and same initialization given by Eq. 26 and same choice of \{{g^{t}}\}_{t\geq 0} . In both cases we chose {g^{t}}={g^{\star}} acting component wise. We will refer to the first algorithm as the unprojected algorithm and have \forall t\geq 0 the non linear function to be {f^{t}}({\mathbf{w}}_{i})={f^{\star}}({\mathbf{w}}_{i})\mathrel{\mathop{:}}=\argmin_{z\in\mathbb{R}}\quantity[ \regfun(z) + \frac{\eta^\star}{2} (z - \w_i)^2 ]\,, (114) where {f^{\star}} comes from Eq. 14 acting component wise. The second algorithm will be the projected version of it where \forall t\geq 0 the non linear function is chosen as \tilde{{f^{t}}}({\mathbf{w}},c)=\frac{c}{\norm{\inden[t](\w)}_{2}}{f^{t}}({\mathbf{w}})\,, (115) with the definition of {f^{t}} from Eq. 114 . Additionally we define the pre-compued value of the rescaled norm as c\coloneqq\frac{\nu^{\star}}{\eta^{\star}}+\frac{\kappa^{\star}}{\eta^{\star}}\,. (116) Our choice of initialization ( Eq. 26 ) and Theorem 5.5 imply that the uprojected algorithm for any t\in\mathbb{N} , the state-evolution parameters remain at fixed values: Proposition 7.1 . For any (m^{\star},q^{\star},\tau^{\star},\kappa^{\star},\nu^{\star},\eta^{\star})\in\mathcal{S}^{\star} , let c^{\star} be as defined in Eq. 116 and let {\mathbf{w}}^{0} be initialized as Eq. 26 . Consider Algorithm 1 with {g^{t}}={g^{\star}} and {f^{t}}={f^{\ }}({\mathbf{w}}) from Eq. 114 (the unprojected algorithm). Then, the parameters \beta,\Omega,\mu,\Sigma defined as \beta=\frac{m^{\star}}{\rho}\,,\qquad\Omega=q^{\star}-\frac{(m^{\star})^{2}}{\rho}\,,\qquad\mu=\frac{\nu^{\star}}{\eta^{\star}}\,,\qquad\Sigma=\frac{\kappa^{\star}}{\eta^{\star}}\,, (117) satisfy the fixed point conditions for the state-evolution equations in Eqs. 56 , 57 , 58 and 59 . Furthermore the estimate \hat{{\mathbf{w}}}^{t} for any t\in\mathbb{N} : \frac{1}{d}\norm{\hat{\w}^t}^{2}\xrightarrow[d\rightarrow\infty]{a.s.}c\,. (118) Proof of Proposition 7.1 : With the choice of initialization as in Eq. 26 , the fixed point conditions for the state evolution Eqs. 58 and 59 under our choice of {g^{t}}={g^{\star}} become: \displaystyle\mu \displaystyle=\alpha\mathbb{E}\quantity[ v^\star\mathcal{P}_{\frac{\tau^\star}{\kappa^\star}\lossfun(y,\cdot)} \qty(\frac{m^\star}{\sqrt{\rho}} v^\star+ v ) ]\,, (119) \displaystyle\Sigma \displaystyle=\alpha\mathbb{E}\quantity[ \mathcal{P}_{\frac{\tau^\star}{\kappa^\star}\lossfun(y,\cdot)} \qty(\frac{m^\star}{\sqrt{\rho}} v^\star+ v )^2 ]\,, (120) where v^{\star}\sim\mathcal{N}(0,1) and v\sim\mathcal{N}(0,q^{\star}-\nicefrac{{(m^{\star})^{2}}}{{\rho}}) . We next establish that Eqs. 120 and 119 follow from the fourth and fifth stationary conditions in Eq. 110 . To show this, we follow the argument presented in ( Loureiro et al., 2021a , Appendix C.2) . The computation proceeds in two steps: first, we substitute the expressions for \mu and \Sigma from Eq. 117 into the relevant conditions in Eq. 110 ; second, we apply a change of variables followed by Gaussian integration to demonstrate the equivalence. Equations 56 and 57 become in our case \displaystyle\beta \displaystyle=\frac{1}{\rho}\mathbb{E}\quantity[ \tilde{w} \inden\qty(\mu\tilde{w} + u, c) ]\,, (121) \displaystyle\Omega \displaystyle=\mathbb{E}\quantity[ \inden\qty(\mu\tilde{w} + u, c)^2 ]-\frac{(m^{\star})^{2}}{\rho}\,, (122) where, under Assumption 2.2 , we have \rho=\mathbb{E}\quantity[(\tilde{w})^2] and u\sim\mathcal{N}(0,\nicefrac{{(\kappa^{\star})^{2}}}{{(\eta^{\star})^{2}}}) . By substitution of the value of \beta and \Omega in Eq. 117 we directly see that Eq. 121 matches the second equation from Corollary 6.4 and that Eq. 122 matches the first one. Similarly, by inductively applying the above fixed-point iterations and Theorem 5.5 , we obtain that the value of \mathbb{E}[\nicefrac{{1}}{{d}}\|{\mathbf{w}}\|_{2}^{2}] , remains constant across iterations and equal to the value c defined in Eq. 116 . ∎ Proposition 7.2 . Let {\mathbf{w}}^{t} be the iterate of the unprojected algorithm with initialization given by Eq. 26 and with the choice of {f^{t}} being proximal as per Eq. 114 . Let \bar{{\mathbf{w}}}^{t} denote the iterates of the projected algorithm with initialization given by Eq. 26 and with the choice of {f^{t}}({\mathbf{w}})=\tilde{{f^{\ }}}({\mathbf{w}},c) defined in Eq. 115 where the constant c>0 is defined above in Eq. 116 . Then, for all t\in\mathbb{N} \frac{1}{d}\norm{ \w^{t} - \bar{\w}^t }^{2}\xrightarrow[d\to\infty]{a.s.}0\,. (123) Proof of Proposition 7.2 : We proceed by induction. Let \bar{{\mathbf{p}}}^{t} denote the pre-activations corresponding to Algorithm 1 with iterates replaced by \bar{{\mathbf{w}}}^{t} defined above, i.e.: \bar{{\mathbf{p}}}^{t}=\frac{1}{\sqrt{d}}\boldsymbol{X}{f^{t}}\quantity( \bar{\w}^t )-b^{t}{g^{t-1}}\quantity(\bar{\p}^{t-1}, \y)\ (124) Suppose that the following claim holds at time t-1 : \frac{1}{d}\norm{\w^{t-1}-\bar{\w}^{t-1}}^{2}\xrightarrow[d\to\infty]{a.s.}0\,,\quad\frac{1}{d}\norm{\p^{t-1}-\bar{\p}^{t-1}}^{2}\xrightarrow[d\to\infty]{a.s.}0\,. ( \star ) We have, by line 5 in Algorithm 1 : \displaystyle\frac{1}{d}\norm{\w^{t}-\bar{\w}^t}^{2} \displaystyle=\frac{1}{d}\norm{\datamat}^{2}_{\mathrm{op}}\norm{g^t(\p^t, \y)-g^t(\bar{\p}^t, \y)}^{2}_{2}+\frac{1}{d}\norm{ \inden(\w^{t-1}) - \tilde{\inden}(\bar{\w}^{t-1},c) }^{2} (125) \displaystyle\leq\frac{1}{d}\norm{\datamat}^{2}_{\mathrm{op}}\norm{g^t(\p^t, \y)-g^t(\bar{\p}^t, \y)}^{2}_{2}+\frac{1}{d}\norm{ \tilde{\inden}(\w^{t-1},c) - \tilde{\inden}(\bar{\w}^{t-1},c) }^{2} (126) \displaystyle\quad+\frac{1}{d}\norm{ \inden\qty(\w^{t-1}) - \tilde{\inden}(\w^{t-1},c) }^{2}\,. (127) We recall from Eq. 75 that \frac{1}{\sqrt{d}}\norm{\datamat}_{\mathrm{op}}\leq C_{\text{op}} , a.s as d\rightarrow\infty for some constant C_{\text{op}}>0 . Hence, the first two-terms vanish by the induction hypothesis ( ⋆ ‣ 7 ) and pseudo-lipschitzness of g while the last two terms vanishes by the pseudo-lipschitzness of \tilde{{f^{\ }}} and Eq. 118 . ∎ We can now proceed to show that Assumption 2.5 implies the convergence of the message passing algorithm. Proof of Lemma 4.2 : In the following proof, we will denote \Omega=q^{\star}-\frac{(m^{\star})^{2}}{\rho}\quad\mbox{and}\quad\Sigma=\frac{\kappa^{\star}}{\eta^{\star}}. (128) We will also use the following shorthands for the update functions of our AMP iteration, for any real valued input x : f(x)=f^{\star}\left(\frac{\nu^{*}}{\eta^{*}}\tilde{w}+x\right)\,,\quad g(x)=g^{\star}\left(\frac{m^{*}}{\rho}s+x,y\right)\,, (129) where \tilde{w} and s are real-valued random variables as defined in Definition 2.1 . We are interested in the evolution of the large system limits of the quantities \displaystyle\frac{1}{d}\norm{\mathbf{p}^{t}-\mathbf{p}^{t-1}}_{2}^{2} \displaystyle=\frac{1}{d}\norm{\mathbf{p}^{t}}_{2}^{2}+\frac{1}{d}\norm{\mathbf{p}^{t-1}}_{2}^{2}-2\frac{1}{d}\langle\mathbf{p}^{t},\mathbf{p}^{t-1}\rangle, (130) \displaystyle\frac{1}{d}\norm{\mathbf{w}^{t}-\mathbf{w}^{t-1}}_{2}^{2} \displaystyle=\frac{1}{d}\norm{\mathbf{w}^{t}}_{2}^{2}+\frac{1}{d}\norm{\mathbf{w}^{t-1}}_{2}^{2}-2\frac{1}{d}\langle\mathbf{w}^{t},\mathbf{w}^{t-1}\rangle. (131) Owing to Theorem 5.5 applied to the unprojected algorithm we get Proposition 7.2 , then because of Proposition 7.1 it holds that, for any t\geq 0 , \lim_{d\to\infty}\frac{1}{d}\norm{\mathbf{p}^{t}}_{2}^{2}=\Omega\quad\mbox{and}\quad\lim_{d\to\infty}\frac{1}{d}\norm{\mathbf{w}^{t}}_{2}^{2}=\Sigma; (132) furthermore, the quantities \lim_{d\to\infty}\frac{1}{d}\langle\mathbf{p}^{t},\mathbf{p}^{t-1}\rangle\quad\mbox{and}\quad\lim_{d\to\infty}\frac{1}{d}\langle\mathbf{w}^{t},\mathbf{w}^{t-1}\rangle, (133) are well defined. From now on, we will respectively denote these quantities \hat{C}_{t} and C_{t} , so that \displaystyle\lim_{d\to\infty}\frac{1}{d}\norm{\mathbf{p}^{t}-\mathbf{p}^{t-1}}_{2}^{2} \displaystyle=2(\Omega-\hat{C}_{t}), (134) \displaystyle\lim_{d\to\infty}\frac{1}{d}\norm{\mathbf{w}^{t}-\mathbf{w}^{t-1}}_{2}^{2} \displaystyle=2(\Sigma-C_{t}). (135) Note that the Cauchy-Schwarz inequality ensures that \hat{C}_{t}\leq\Omega and C_{t}\leq\Sigma . To establish convergence of the AMP sequence, we thus need to study the convergence of the sequences \{C_{t}\}_{t\geq 0},\{\hat{C}_{t}\}_{t\geq 0} . Using Theorem 5.5 and a similar argument to Bolthausen (2014) , we may represent the state evolution equations governing the evolution of C_{t},\hat{C}_{t} as follows \displaystyle C^{t+1} \displaystyle=\mathbb{E}\left[g(\sqrt{\hat{C}_{t}}z_{1}+\sqrt{\Omega-\hat{C}_{t}}z^{\prime}_{1})g(\sqrt{\hat{C}_{t}}z_{1}+\sqrt{\Omega-\hat{C}_{t}}z^{\prime\prime}_{1})\right], (136) \displaystyle\hat{C}_{t} \displaystyle=\alpha\mathbb{E}\left[f(\sqrt{C_{t}}z_{2}+\sqrt{\Sigma-C_{t}}z^{\prime}_{2})f(\sqrt{C_{t}}z_{2}+\sqrt{\Sigma-C_{t}}z^{\prime\prime}_{2})\right]. (137) Starting with the first equation, we compute the partial derivative w.r.t. \hat{C}_{t} , so that we obtain \displaystyle\partial_{\hat{C}_{t}}C_{t+1} \displaystyle=\frac{1}{\sqrt{\hat{C}_{t}}}\mathbb{E}\left[z_{1}g^{\prime}(\sqrt{\hat{C}_{t}}z_{1}+\sqrt{\Omega-\hat{C}_{t}}z^{\prime}_{1})g(\sqrt{\hat{C}_{t}}z_{1}+\sqrt{\Omega-\hat{C}_{t}}z^{\prime\prime}_{1})\right] (138) \displaystyle-\frac{1}{\sqrt{\Omega-\hat{C}_{t}}}\mathbb{E}\left[z^{\prime}_{1}g^{\prime}(\sqrt{\hat{C}_{t}}z_{1}+\sqrt{\Omega-\hat{C}_{t}}z^{\prime}_{1})g(\sqrt{\hat{C}_{t}}z_{1}+\sqrt{\Omega-\hat{C}_{t}}z^{\prime\prime}_{1})\right]. (139) Gaussian integration by parts (Stein’s lemma) then yields \partial_{\hat{C}_{t}}C_{t+1}=\mathbb{E}\left[g^{\prime}(\sqrt{\hat{C}_{t}}z_{1}+\sqrt{\Omega-\hat{C}_{t}}z^{\prime}_{1})g^{\prime}(\sqrt{\hat{C}_{t}}z_{1}+\sqrt{\Omega-\hat{C}_{t}}z^{\prime\prime}_{1})\right]. (140) Integrating our the independent variables z_{1}^{\prime},z_{1}^{\prime\prime} , we obtain that the above quantity is strictly positive so that, for any t\geq 0 , the function C_{t+1}(.) is strictly increasing. Taking an additional derivative, we obtain \displaystyle\partial^{2}_{\hat{C}_{t}}C_{t+1}=\mathbb{E}\left[g^{\prime}(\sqrt{\hat{C}_{t}}z_{1}+\sqrt{\Omega-\hat{C}_{t}}z^{\prime}_{1})g^{\prime}(\sqrt{\hat{C}_{t}}z_{1}+\sqrt{\Omega-\hat{C}_{t}}z^{\prime\prime}_{1})\right], (141) which is also positive, so that C_{t+1}(.) is convex on [0,\Omega] . We can therefore bound both C_{t+1} and its derivative with their values at \hat{C}_{t}=\Omega , giving the following upper bound |\partial_{\hat{C}_{t}}C_{t+1}|\leq\mathbb{E}\left[g^{\prime}\left(\sqrt{\hat{C}_{t}}z_{1}\right)^{2}\right]. (142) A similar computation gives the upper bound |\partial_{C_{t}}\hat{C}_{t}|\leq\alpha\mathbb{E}\left[f^{\prime}\left(\sqrt{C_{t}}z_{2}\right)^{2}\right]. (143) Under the replicon condition 2.1 , we thus find that the iterations \hat{C}_{t+1}=\mathcal{F}_{1}(\hat{C}_{t}) and C_{t+1}=\mathcal{F}_{2}(C_{t}) are non-expansive, so that the only fixed point is given by C=\Omega and \hat{C}=\Sigma , leading to \displaystyle\lim_{t\to\infty}\lim_{d\to\infty}\frac{1}{d}\norm{\mathbf{w}^{t}-\mathbf{w}^{t-1}}_{2}^{2}=0\quad\mbox{and}\quad\lim_{t\to\infty}\lim_{d\to\infty}\frac{1}{d}\norm{\mathbf{p}^{t}-\mathbf{p}^{t-1}}_{2}^{2}=0. (144) Finally, assuming that the replicon stability condition in Definition 2.1 holds strictly gives the linear convergence of the AMP sequence and concludes this proof. ∎ 8 Proofs for Matching Upper and Lower Bounds This section is dedicated to the proof of Proposition 4.3 . In this section we will use the following auxiliary objective \mathcal{C}_{d}({\mathbf{p}}^{t},{\mathbf{w}}^{t})\mathrel{\mathop{:}}=\frac{\alpha}{n}\sum_{\mu=1}^{n}\mathscr{L}\quantity( y_\dataidx, \tilde{ \mathcal{P} } _{\frac{\tau^\star}{\kappa^\star} \lossfun(y_\dataidx, \cdot)} (p_\dataidx) )+\frac{1}{d}\sum_{i=1}^{d}\mathscr{R}\quantity( \tilde{ \mathcal{P} } _{\frac{1}{\eta^\star}\regfun(\cdot)}(w_\dimidx) )\,, (145) Lemma 8.1 . We define the risk of the iterates of Algorithm 1 at time t as begin \mathcal{A}_{d}(\hat{\mathbf{w}}^{t}) where \hat{\mathbf{w}}^{t}={f^{\star}}({\mathbf{w}}^{t}) . Under 2.4 and 2.5 , there exist constants K>0 and \rho^{\prime}<1 such that the following holds for any t \absolutevalue{\riskfun_d(\what^t) - \mathcal{C}_d(\p^t, \w^t)}\leq K(\rho^{\prime})^{t}, (146) with probability \rightarrow 1 as n,d\rightarrow\infty . Proof of Lemma 8.1 : From Algorithm 1 , the preactivations {\mathbf{z}}^{t} at time t can be expressed as {\mathbf{z}}^{t}\mathrel{\mathop{:}}=\frac{1}{\sqrt{d}}\boldsymbol{X}f({\mathbf{w}}^{t})={\mathbf{p}}^{t}+b^{t}g^{t-1}({\mathbf{p}}^{t-1},\mathbf{y}), (147) where b^{t} is a scalar. The objective value at time t is therefore given by \displaystyle\mathcal{A}_{d}(\hat{\mathbf{w}}^{t}) \displaystyle=\frac{\alpha}{n}\sum_{\mu=1}^{n}\mathscr{L}(y_{\mu},z^{t}_{\mu})+\frac{1}{d}\sum_{i=1}^{d}\mathscr{R}({f^{\star}}(w^{t}_{i})) (148) \displaystyle=\frac{\alpha}{n}\sum_{\mu=1}^{n}\mathscr{L}(y^{t}_{\mu},p^{t}_{\mu}+b^{t}g^{t-1}(p^{t-1}_{\mu},y_{\mu}))+\frac{1}{d}\sum_{i=1}^{d}\mathscr{R}({f^{\star}}(w^{t}_{i}))\,. (149) The above objective depends on the correlation between {\mathbf{p}}^{t},{\mathbf{p}}^{t-1} . We need to show that as \frac{1}{n}\norm{\p^t-\p^{t-1}}^{2}_{2}\rightarrow 0 , i.e. the algorithm is converging \mathcal{A}_{d}(\hat{\mathbf{w}}^{t})\rightarrow\mathcal{C}_{d}({\mathbf{p}}^{t},{\mathbf{w}}^{t}) . From the specific choice of {g^{\star}} from Eq. 14 , we have that b^{t}{g^{\star}}(p^{t-1}_{\mu},y_{\mu})\xrightarrow[d\to\infty]{a.s.}\mathcal{P}_{\frac{\tau^{\star}}{\kappa^{\star}}\mathscr{L}(y_{\mu},\cdot)}(p_{\mu}^{t-1})-p^{t-1}_{\mu}\,, (150) and thus \mathcal{A}_{d}(\hat{\mathbf{w}}^{t})=\frac{\alpha}{n}\sum_{\mu=1}^{n}\mathscr{L}\quantity( y_\dataidx, p_\dataidx^t - p_\dataidx^{t-1} + \tilde{\mathcal{P}}_{\frac{\tau^\star}{\kappa^\star} \lossfun(y_\dataidx, \cdot)}(p_\dataidx^{t-1}) )+\frac{1}{d}\sum_{i=1}^{d}\mathscr{R}\quantity(\inden[\star](w^t_\dimidx))\,. (151) Now, since \mathscr{L} is pseudo-Lipschitz of finite-order k_{L} because of Assumption 2.3 , there exists a constant L>0 , such that: \displaystyle\mathscr{L}(y_{\mu},p_{\mu}^{t}-p_{\mu}^{t-1}+\tilde{\mathcal{P}}_{\tau\mathscr{L}(y,\cdot)}(p_{\mu}^{t-1})) \displaystyle\leq\mathscr{L}(y_{\mu},\tilde{\mathcal{P}}_{\tau\mathscr{L}(y,\cdot)}(p_{\mu}^{t-1})) (152) \displaystyle+L\absolutevalue{p^t_\dataidx- p^{t-1}_\dataidx}\quantity( 1 + \abs{\tilde{\mathcal{P}}_{\tau\lossfun(y, \cdot)}(p_\dataidx^{t-1})}^{k_L} + \qty(p^t_\dataidx- p^{t-1}_\dataidx)^{k_L} )\,. (153) Combining the previous equation in the definition of the risk and the definition of {f^{\star}} from Eq. 14 , we have that \displaystyle\absolutevalue{\riskfun_d(\what^t) - \mathcal{C}_d(\p^t, \w^t)}\leq\underbrace{L\frac{\alpha}{n}\sum_{\mu=1}^{n}\absolutevalue{p^t_\dataidx- p^{t-1}_\dataidx}\quantity( 1 + \abs{\tilde{\mathcal{P}}_{\tau\lossfun(y, \cdot)}(p_\dataidx^{t-1})}^{k_L} + \abs{p^t_\dataidx- p^{t-1}_\dataidx}^{k_L} )}_{\delta}\,. (154) It suffices to show that \delta\rightarrow 0 as t\rightarrow\infty . We obtain by Cauchy-Schwarz inequality the following \delta\leq\frac{1}{\sqrt{n}}\norm{\p^t - \p^{t-1}}_{2}\sqrt{\frac{1}{n}\sum_{\mu=1}^{n}\quantity( 1 + \abs{\tilde{\mathcal{P}}_{\tau\lossfun(y, \cdot)}(p_\dataidx^{t-1})}^{k_L} + \abs{p^t_\dataidx- p^{t-1}_\dataidx}^{k_L} )^{2}}\,. (155) The convergence of \frac{1}{\sqrt{n}}\norm{\p^t - \p^{t-1}}_{2} is established by Lemma 4.2 . The remaining term can be upper bounded in probability by a constant as it is a pseudo-Lipschitz function by Theorem 5.5 . Therefore, \delta decays in t with high probability in n , yielding Eq. 146 almost surely and completing the proof. ∎ Lemma 8.2 . From the definition of the auxiliary objective in Eq. 145 we have that for any t\geq 1 : \mathcal{C}_{d}({\mathbf{p}}^{t},{\mathbf{w}}^{t})\xrightarrow[n,d\to\infty]{a.s.}{\mathcal{A}}^{\star}\,. (156) Proof of Lemma 8.2 : The function we are interested in is separable and thus amenable for Theorem 5.5 . At fixed point, by the state-evolution description, we have that the distribution for {\mathbf{p}} and {\mathbf{w}} are {\mathbf{p}}\approx\frac{m^{\star}}{\rho}{\mathbf{s}}+\sqrt{q^{\star}-\frac{(m^{\star})^{2}}{\rho}}\mathbf{h}\,,\quad{\mathbf{w}}\approx\frac{nu^{\star}}{\eta^{\star}}\tilde{{\mathbf{w}}}+\frac{\kappa^{\star}}{\eta^{\star}}\mathbf{g}\,, (157) where \mathbf{s},\mathbf{h}\sim\mathcal{N}(\mathbf{0},\mathrm{Id}_{n}) and \mathbf{g}\sim\mathcal{N}(\mathbf{0},\mathrm{Id}_{d}) and \tilde{{\mathbf{w}}}\sim\pi_{\tilde{{\mathbf{w}}}} . We can thus see by substituting that we obtain the specific form for the follows by Corollary 6.5 . ∎ The proof of Proposition 4.3 follows from combining Lemmas 8.2 and 8.1 . The key observation is that both the projected or the unprojected algorithm converge to the same energy value. To see this, note that the projection onto the spherical shell amounts to rescaling by a factor that converges almost surely to a constant by Proposition 7.1 this implies convergences of all higher moments are converging for both algorithms iterates. By the pseudo-Lipschitz of both \mathscr{L} and \mathscr{R} from Assumption 2.3 , the auxiliary objective \mathcal{C}_{d}({\mathbf{p}}^{t},{\mathbf{w}}^{t}) for both algorithms converges almost surely to the same limit characterized in Corollary 6.5 , completing the argument. 8.1 Proof of the Main Statement We now proceed to the proof of Theorem 2.1 under 2.4 , 2.5 , 2.3 , 2.1 and 2.2 . To establish the convergence of the statistic \psi from Theorem 2.1 we leverage the following theorem which is a consequence of ( Rockafellar, 1970 , Theorem 24.5) . Theorem 8.3 . Let f_{1},f_{2}\cdots be a sequence of convex functions on \mathbb{R} converging almost-surely pointwise to f on an open interval O\subset\mathbb{R} . Then, for any \varepsilon>0 : \Pr[\cap_{d>d_{0}}\quantity{\partial f_d(s) \in\partial f(s) + \varepsilon B}]\rightarrow 1, (158) as d_{0}\rightarrow\infty , and where B denotes the unit ball in \mathbb{R} and we indicate by \partial f(s) the subdifferential of f at the point s . Proof of Theorem 8.3 : Let \partial_{+}f_{d}(s),\partial_{-}f_{d}(s) denote the right and left derivatives of f_{d} respectively defined as \partial_{+}f_{d}(s)=\lim_{t\downarrow 0^{+}}\frac{f_{d}(s+t)-f_{d}(s)}{t}\,,\qquad\partial_{-}f_{d}(s)=\lim_{t\uparrow 0^{-}}\frac{f_{d}(s+t)-f_{d}(s)}{t}\,, (159) where the above limits exist and are finite by the convexity of f_{d}(s) and monotone-convergence theorem. The subdifferential \partial f_{d}(s) at a point s is then given by the interval \partial f_{d}(s)=[\partial_{-}f_{d}(s),\partial_{+}f_{d}(s)] ( Rockafellar, 1970 , Theorem 23.4) . Using the same notation for f (instead of f_{d} ), by the definition of \partial_{+}f(s),\partial_{-}f(s) , for any \varepsilon>0 small enough, there exist s^{+}_{\varepsilon},s^{-}_{\varepsilon}\in O such that: \frac{f(s^{+}_{\varepsilon})-f(s)}{s^{+}_{\varepsilon}-s}\leq\partial_{+}f(s)+\frac{\varepsilon}{2}, (160) and \frac{f(s^{-}_{\varepsilon})-f(s)}{s^{-}_{\varepsilon}-s}\geq\partial_{-}f(s)-\frac{\varepsilon}{2}\,. (161) By the convexity of f_{d}(s) , we further have \partial_{+}f_{d}(s)\leq\frac{f_{d}(s^{+}_{\epsilon})-f_{d}(s)}{s^{+}_{\varepsilon}-s}\,, (162) and \partial_{-}f_{d}(s)\geq\frac{f_{d}(s^{-}_{\epsilon})-f_{d}(s)}{s^{-}_{\varepsilon}-s}\,. (163) Define the following sequence of events \displaystyle\mathcal{E}^{+}_{d,\varepsilon} \displaystyle:\absolutevalue{\frac{f_d(s^+_\varepsilon)-f(s^+_\varepsilon)}{s^+_\varepsilon-s}}\leq\frac{\varepsilon}{4}\,, (164) \displaystyle\mathcal{E}^{-}_{d,\varepsilon} \displaystyle:\absolutevalue{\frac{f_d(s^-_\varepsilon)-f(s^-_\varepsilon)}{s^-_\varepsilon-s}}\leq\frac{\varepsilon}{4}\,, (165) \displaystyle\mathcal{E}^{s}_{d,\varepsilon} \displaystyle:\absolutevalue{f_d(s)-f(s)}\leq\frac{\varepsilon}{4}\operatorname{min}\left({\absolutevalue{s^-_\varepsilon-s},\absolutevalue{s^+_\varepsilon-s}}\right)\,, (166) By the point-wise a.s convergence of f_{d}(s) to f(s) , we have \lim_{d_{0}\rightarrow\infty}\Pr[\cap_{d\geq d_{0}}\mathcal{E}^{+}_{d,\varepsilon}]=1\,,\quad\lim_{d_{0}\rightarrow\infty}\Pr[\cap_{d\geq d_{0}}\mathcal{E}^{-}_{d,\varepsilon}]=1\,,\quad\lim_{d_{0}\rightarrow\infty}\Pr[\cap_{d\geq d_{0}}\mathcal{E}^{s}_{d,\varepsilon}]=1\,. (167) Applying a union-bound to the complements [\cap_{d\geq d_{0}}\mathcal{E}^{+}_{d,\varepsilon}]^{\complement},[\cap_{d\geq d_{0}}\mathcal{E}^{-}_{d,\varepsilon}]^{\complement},[\cap_{d\geq d_{0}}\mathcal{E}^{s}_{d,\varepsilon}]^{\complement} , we obtain that for any \varepsilon>0 \Pr[\cap_{d\geq d_{0}}[\mathcal{E}^{+}_{d,\varepsilon}\cap\mathcal{E}^{-}_{d,\varepsilon}\cap\mathcal{E}^{s}_{d,\varepsilon}]]\rightarrow 1\,, (168) as d_{0}\rightarrow\infty . Next, suppose that the events \mathcal{E}^{+}_{d,\varepsilon},\mathcal{E}^{-}_{d,\varepsilon},\mathcal{E}^{s}_{d,\varepsilon} hold for some d\in\mathbb{N} . Then, adding and subtracting \frac{f_{d}(s^{+}_{\varepsilon})-f(s^{+}_{\varepsilon})}{s^{+}_{\varepsilon}-s} and \frac{f_{d}(s)-f(s)}{s^{+}_{\varepsilon}-s} in the RHS of Eq. 162 and applying triangle inequality yields: \partial_{+}f_{d}(s)\leq\frac{f(s^{+}_{\epsilon})-f(s)}{s^{+}_{\varepsilon}-s}+\absolutevalue{\frac{f_d(s^+_\epsilon)-f(s_\epsilon^+)}{s^+_\varepsilon-s}}+\absolutevalue{\frac{f_d(s)-f(s)}{s^+_\varepsilon-s}}\leq\frac{f(s^{+}_{\epsilon})-f(s)}{s^{+}_{\varepsilon}-s}+\frac{\varepsilon}{2}\,. (169) Combining the above with Eq. 160 , we obtain: \partial_{+}f_{d}(s)\leq\partial_{+}f(s)+\varepsilon. (170) Analogously, Eqs. 163 and 161 imply that: \partial_{-}f_{d}(s)\leq\partial_{-}f(s)+\varepsilon\,. (171) Recalling the relations, \partial f_{d}(s)=[\partial_{-}f_{d}(s),\partial_{+}f_{d}(s)] and \partial f(s)=[\partial_{-}f(s),\partial_{+}f(s)] we obtain: \partial f_{d}(s)\in\partial f(s)+\varepsilon B\,. (172) Since the above event holds under \mathcal{E}^{+}_{d,\varepsilon}\cap\mathcal{E}^{-}_{d,\varepsilon}\cap\mathcal{E}^{s}_{d,\varepsilon} , Eq. 168 implies Eq. 158 . ∎ We are ready to conclude the proof of our main result. Proof of Theorem 2.1 : We prove each part separately. Part 1. We establish almost sure convergence through a sandwich argument. For any \varepsilon>0 , we show that the sequence {\mathcal{A}}^{\star}_{d} is eventually bounded between {\mathcal{A}}^{\star}\pm\varepsilon almost surely. By Proposition 4.1 , with probability 1 , there exists d_{\varepsilon}\in\mathbb{N} satisfying {\mathcal{A}}^{\star}_{d}(\omega)\geq{\mathcal{A}}^{\star}-\varepsilon\quad\forall d>d_{\varepsilon}\,. (173) Similarly, by Proposition 4.3 , with probability 1 , there exists \tilde{d}_{\varepsilon}\in\mathbb{N} satisfying {\mathcal{A}}^{\star}_{d}(\omega)\leq{\mathcal{A}}^{\star}+\varepsilon\quad\forall d>\tilde{d}_{\varepsilon}(\omega)\,. (174) Then, taking D_{\varepsilon}=\max\{d_{\varepsilon},\tilde{d}_{\varepsilon}\} , we have: |{\mathcal{A}}^{\star}_{d}-{\mathcal{A}}^{\star}|\leq\varepsilon\quad\forall d>D_{\varepsilon}\,. (175) This implies that for all \varepsilon>0 \Pr[\limsup_{d\to\infty}|{\mathcal{A}}^{\star}_{d}-{\mathcal{A}}^{\star}|\geq\varepsilon]=0\,, (176) which establishes the almost sure convergence in Eq. 16 . Part 2. For any finite dimension d , define the perturbed minimum for s\in\mathbb{R} \Psi_{d}(s)=\min_{{\mathbf{w}}\in\mathcal{K}_{a,b}}\Big\{\mathcal{A}_{d}({\mathbf{w}})+s\psi\Big(\frac{1}{d}\langle{\mathbf{w}},\tilde{{\mathbf{w}}}\rangle,\frac{1}{d}\norm{\w}_{2}^{2}\Big)\Big\}\,. (177) By Danskin’s theorem ( Bertsekas, 1997 ) , for s=0 , the subdifferential \partial\Psi_{d}(0) contains the set \psi\Big(\frac{1}{d}\langle\hat{\mathbf{w}},\tilde{{\mathbf{w}}}\rangle,\frac{1}{d}\norm{\what}_{2}^{2}\Big):\hat{\mathbf{w}}\in\quantity{ \psi\Big(\frac{1}{d} \langle\what, \wteacher\rangle, \frac{1}{d} \norm{\what}_2^2\Big) : \what\in\argmin_{\w\in\mathcal{K}_{a,b}} \riskfun_d(\w) }_{{\mathbf{w}}\in\mathcal{K}_{a,b}}\mathcal{A}_{d}({\mathbf{w}})\,. (178) The limiting function \Psi(s) defined in Eq. 17 is concave as an infimum of affine functions in s again because of Danskin’s theorem. By assumption, it is differentiable at s=0 . By Theorem 8.3 , for any \varepsilon>0 , with probability 1 , there exists d_{\psi} satisfying \psi\Big(\frac{1}{d}\langle\hat{{\mathbf{w}}},\tilde{{\mathbf{w}}}\rangle,\frac{1}{d}\norm{\wminimizer}_{2}^{2}\Big)\in\Big[\evaluated{\dv{s} \Psi(s)}_{s=0}-\varepsilon,\evaluated{\dv{s} \Psi(s)}_{s=0}+\varepsilon\Big] (179) for all d>d_{\psi} . The fact that \varepsilon is arbitrary establishes Eq. 18 . ∎ Appendix A Connection between Weak Convexity and Lipshitzness of Proximals This appendix shows how Assumption 2.4 is both necessary and sufficient for the existence of Lipschitz-continuous proximal selections required in our framework, by building up the tools and preliminary results to prove Theorems 5.3 and 5.4 . As this appendix may be of broader interest beyond the setting of the main paper, we slightly modify the notation. We will work, whenever possible, with a generic function f\,:\,\mathbb{R}\rightarrow\mathbb{R} and denote E_{f}\subseteq\mathbb{R} as the set of inputs \delta\in\mathbb{R} such that \mathcal{P}_{f}(\cdot) is non-empty, where \mathcal{P}_{f}(\cdot) is here defined as : \mathcal{P}_{f}(\delta)\mathrel{\mathop{:}}=\argmin_{r\in\mathbb{R}}\frac{(r-\delta)^{2}}{2}+f(r). (180) Similarly, the Moreau enveloppe is here defined as : \mathcal{M}_{f}(\delta)\mathrel{\mathop{:}}=\min_{r\in\mathbb{R}}\frac{(r-\delta)^{2}}{2}+f(r). (181) Throughout, we denote by r_{\min}:\mathbb{R}\rightarrow\mathbb{R} an arbitrary proximal selection defined on E_{f} , i.e. \forall\,\delta\in E_{f},r_{\min}(\delta)\in\mathcal{P}_{f}(\delta) . When the proximal operator is singleton-valued, the proximal selection is uniquely determined. Before starting we also recall a fundamental property of convex functions that will be used repeatedly. Lemma A.1 (Properties of Convex Functions) . Let g:\mathbb{R}\to\mathbb{R}\cup\{\infty\} be a convex function. The set of points where g is finite is an interval J . On the interior \mathring{J} , the left and right derivatives g^{\prime}_{-} and g^{\prime}_{+} exist everywhere and satisfy: (i) g^{\prime}_{-} and g^{\prime}_{+} are non-decreasing functions with g^{\prime}_{-}\leq g^{\prime}_{+} . (ii) g^{\prime} is defined almost everywhere on J and is non-decreasing. (iii) For all x\in\mathring{J} , g^{\prime}_{-}(x)=g^{\prime}(x^{-}) and g^{\prime}_{+}(x)=g^{\prime}(x^{+}) . (iv) g is differentiable at \delta\in\mathring{J} if and only if g^{\prime}_{-}(\delta)=g^{\prime}_{+}(\delta) , which holds if and only if g^{\prime} is continuous at \delta . A.1 Existence and Basic Properties of Proximal Operators Although it is a necessary condition, asking that f is lower semi continuous (l.s.c.) does not guarantee non-emptiness of the proximal operator of f . Indeed, r\mapsto\exp(-r^2)-\frac{r^{2}}{2} is l.s.c. but its proximal operator at \delta=0 is empty because the minimizer has fled to infinity. The purpose of the prox-coercive property that we impose on f is to prevent this from happening. We first recall key properties of proximal operators for weakly convex functions. Proposition A.2 . Suppose f is lower semi-continuous and prox-coercive. For V\in[0,1] , E_{Vf}=\mathbb{R} and in particular the Moreau envelope of Vf is always finite. Furthermore, for any \delta\in\mathbb{R} , \mathcal{P}_{Vf}(\delta) is a compact set. Proof of Proposition A.2 : Fix \delta\in\mathbb{R} and V\in(0,1] . Consider a minimizing sequence (r_{n})_{n\in\mathbb{N}}\subset\mathbb{R} such that \frac{(\delta-r_{n})^{2}}{2}+Vf(r_{n})\to\mathcal{M}_{Vf}(\delta)\in[-\infty,\infty). Suppose by contradiction that (|r_{n}|)_{n} is unbounded. Then it has a subsequence with |r_{n_{k}}|\to\infty . Since f is prox-coercive, \limsup_{k\to\infty}\left[(\delta-r_{n_{k}})^{2}/2+f(r_{n_{k}})\right]=\infty . However, for any n\in\mathbb{N} , \frac{(\delta-r_{n})^{2}}{2}+Vf(r_{n})=V\left[\frac{(\delta-r_{n})^{2}}{2}+f(r_{n})\right]+(1-V)\frac{(\delta-r_{n})^{2}}{2}. Since V\in(0,1] and the second term is non-negative, taking \limsup along the subsequence yields a contradiction to the convergence of the left-hand side. Thus (r_{n})_{n} is bounded. Let r be an accumulation point. By lower semi-continuity, taking \liminf along a convergent subsequence yields (\delta-r)^{2}/2+Vf(r)\leq\mathcal{M}_{Vf}(\delta) . The reverse inequality holds by definition of the Moreau envelope, establishing that r\in\mathcal{P}_{Vf}(\delta) . The same argument shows \mathcal{P}_{Vf}(\delta) is closed and bounded, hence compact. ∎ Proposition A.3 . The following function is convex: g:\delta\in\mathbb{R}\mapsto\frac{\delta^{2}}{2}-\mathcal{M}_{f}(\delta)\in\mathbb{R}\cup\{\infty\}. Hence, \mathcal{M}_{f} is almost everywhere twice differentiable on the interval I_{f}:=\{\delta\in\mathbb{R}\mid\mathcal{M}_{f}(\delta)>-\infty\} . In addition, for \delta\in I_{f} , \mathcal{P}_{f}(\delta)\subset[g^{\prime}_{-}(\delta),g^{\prime}_{+}(\delta)]. If \mathcal{M}_{f} is differentiable at \delta\in E_{f} (i.e., \mathcal{M}^{\prime}_{f} is continuous at \delta ), then \mathcal{P}_{f}(\delta) is a singleton. Furthermore, any proximal selection of f is non-decreasing on E_{f} . If there exists a non-trivial interval I\subset I_{f} such that I\subset E_{f} , this selection is continuous at \delta if and only if \mathcal{M}_{f} is differentiable at \delta , and differentiable almost everywhere on I . Proof of Proposition A.3 : We can rewrite g(\delta) as g(\delta)=\sup_{r\in\mathbb{R}}\left[\delta r-\frac{r^{2}}{2}-f(r)\right]. Since \delta\mapsto\delta r-\frac{r^{2}}{2}-f(r) is convex for any r\in\mathbb{R} , g is convex as a supremum of convex functions. By Lemma A.1 , g is differentiable almost everywhere on I_{f} , hence so is \mathcal{M}_{f} . Now fix \delta\in I_{f} and suppose \mathcal{P}_{f}(\delta) is non-empty. Take r_{\min}(\delta)\in\mathcal{P}_{f}(\delta) . For r\in\mathbb{R} and \delta^{\prime}\neq\delta , \frac{\delta^{\prime 2}}{2}-\mathcal{M}_{f}(\delta^{\prime})\geq\frac{\delta^{\prime 2}}{2}-\frac{(\delta^{\prime}-r)^{2}}{2}-f(r)=\frac{\delta^{2}}{2}-\frac{(\delta-r)^{2}}{2}-f(r)+(\delta^{\prime}-\delta)r. At r=r_{\min}(\delta) , this gives g(\delta^{\prime})-g(\delta)\geq(\delta^{\prime}-\delta)r_{\min}(\delta). Dividing by \delta^{\prime}-\delta\neq 0 yields r_{\min}(\delta)\in[g^{\prime}_{-}(\delta),g^{\prime}_{+}(\delta)] . By Lemma A.1 , g is differentiable at \delta if and only if g^{\prime}_{-}(\delta)=g^{\prime}_{+}(\delta) , which implies \mathcal{P}_{f}(\delta) is a singleton. For any proximal selection r_{\min} defined on E_{f} and \delta<\delta^{\prime} in E_{f} , r_{\min}(\delta)\leq g^{\prime}_{+}(\delta)=g^{\prime}(\delta^{+})\leq g^{\prime}(\delta^{\prime-})=g^{\prime}_{-}(\delta^{\prime})\leq r_{\min}(\delta^{\prime}), where we used Lemma A.1 . Thus r_{\min} is non-decreasing. For continuity, suppose \delta\in\mathring{I} and \mathcal{M}_{f} is differentiable at \delta . Since \mathcal{M}^{\prime}_{f} is continuous at \delta , there exist sequences (\delta_{n,\pm})_{n}\subset I with \delta_{n,\pm}\to\delta^{\pm} and \mathcal{M}_{f} differentiable at each \delta_{n,\pm} . Then r_{\min}(\delta_{n,\pm})=\delta_{n,\pm}-\mathcal{M}^{\prime}_{f}(\delta_{n,\pm})\to\delta-\mathcal{M}^{\prime}_{f}(\delta)=r_{\min}(\delta), establishing continuity. Conversely, the above chain of inequalities yield at \delta\in\mathring{I} r_{\min}(\delta^{-})\leq g^{\prime}_{+}(\delta^{-})\leq g^{\prime}_{-}(\delta^{+})\leq r_{\min}(\delta^{+}). If r_{\min} is continuous at \delta then so are g^{\prime} and \mathcal{M}_{f}^{\prime} . In particular, \mathcal{M}_{f} is differentiable at \delta . Almost everywhere differentiability follows from Lebesgue’s theorem on monotone functions. ∎ Remark A.1 . In particular, if E_{f}=\mathbb{R} , such as when f is lower semi-continuous and prox-coercive (by Proposition A.2 ), then any proximal selection of f is non-decreasing. A.2 Characterization via Chord Slope Functions Proposition A.4 . Take r_{\min} to be a proximal selection of f defined on E_{f} . Then we have E_{f}=\{\delta\in\mathbb{R}\mid\exists r_{0}\in\mathbb{R},\,s_{f}(r_{0})\leq\delta\leq i_{f}(r_{0})\}, (182) and for any r_{0},\delta\in\mathbb{R} , r_{0}\in\mathcal{P}_{f}(\delta)\iff s_{f}(r_{0})\leq\delta\leq i_{f}(r_{0}), (183) where s_{f} and i_{f} come from Definition 5.6 . Proof of Proposition A.4 : For any r_{0},\delta\in\mathbb{R} , by the definition of \mathcal{P}_{f}(\delta) , r_{0}\in\mathcal{P}_{f}(\delta)\iff\forall r\in\mathbb{R},\quad\delta(r-r_{0})\leq f(r)-f(r_{0})+\frac{r+r_{0}}{2}(r-r_{0}). Separating the cases r>r_{0} and rr_{0},\quad\delta\leq\frac{f(r)-f(r_{0})}{r-r_{0}}+\frac{r+r_{0}}{2}\quad\text{and}\quad\forall r-\infty . Then f is locally lower-bounded. Proof of Proposition A.7 : Suppose by contradiction that f is not locally lower-bounded at some r_{\infty}\in\mathbb{R} . Thus, for any n\in\mathbb{N}^{*} , there exists r_{n}\in(r_{\infty}-\frac{1}{n},r_{\infty}+\frac{1}{n}) with f(r_{n})\leq-n . Thus r_{n}\to r_{\infty} and \mathcal{M}_{f}(\delta)\leq\frac{(r_{n}-\delta)^{2}}{2}+f(r_{n})\leq\frac{(r_{n}-\delta)^{2}}{2}-n\to-\infty, which contradicts \mathcal{M}_{f}(\delta)>-\infty . ∎ Remark A.4 . In particular, if there exists \delta\in\mathbb{R} such that \mathcal{P}_{f}(\delta)\neq\emptyset , then f is locally lower-bounded. Proposition A.8 . Suppose there exists a sequence (\delta_{n})_{n\in\mathbb{N}}\subset\mathbb{R} such that for all n\in\mathbb{N} , \mathcal{P}_{f}(\delta_{n})\neq\emptyset and |\delta_{n}|\to\infty . Then any proximal selection r_{\min} of f satisfies |r_{\min}(\delta_{n})|\to\infty . Proof of Proposition A.8 : Suppose by contradiction that |r_{\min}(\delta_{n})| does not diverge. Then there exists M>0 such that a subsequence (still denoted (\delta_{n}) ) satisfies |r_{\min}(\delta_{n})|\leq M for all n and converges to some r_{\infty}\in\mathbb{R} . By Proposition A.7 , f is locally lower-bounded. Thus there exists an open set U\subset\mathbb{R} containing r_{\infty} with \inf_{U}f>-\infty . Without loss of generality, assume r_{\min}(\delta_{n})\in U for all n . For n such that |\delta_{n}|\geq M , by the triangle inequality, \mathcal{M}_{f}(\delta_{n})\geq\frac{(|\delta_{n}|-M)^{2}}{2}+\inf_{U}f. However, for any r\in\mathbb{R} , \mathcal{M}_{f}(\delta_{n})\leq\frac{(\delta_{n}-r)^{2}}{2}+f(r). Setting r_{n}=\mathrm{sign}(\delta_{n})(M+1) and defining M^{\prime}=\frac{(M+1)^{2}}{2}+\max(f(M+1),f(-(M+1))) , we obtain M^{\prime}\geq\mathcal{M}_{f}(\delta_{n})-\frac{\delta_{n}^{2}}{2}+r_{n}\delta_{n}\geq\frac{M^{2}}{2}-M|\delta_{n}|+r_{n}\delta_{n}+\inf_{U}f=|\delta_{n}|+\frac{M^{2}}{2}+\inf_{U}f\to\infty, which is a contradiction. ∎ Corollary A.9 . Suppose E_{f}=\mathbb{R} . Let r_{\min} be a proximal selection of f . Then r_{\min}\in C^{0}(\mathbb{R},\mathbb{R})\iff f\text{ is strictly }1\text{-weakly convex}. Furthermore, when this is the case, \mathcal{P}_{f} is singleton-valued and r_{\min} is an onto function. Proof of Corollary A.9 : With E_{f}=\mathbb{R} , \mathcal{M}_{f} is finite everywhere and Proposition A.3 shows r_{\min} is non-decreasing, and Proposition A.8 shows |r_{\min}| is coercive. Hence r_{\min} is continuous if and only if it is onto. Suppose r_{\min} is onto. Proposition A.4 guarantees s_{f}\leq i_{f} . By Proposition A.5 , this implies f is 1 -weakly convex. Since r_{\min} is continuous, Proposition A.3 shows \mathcal{M}_{f} is differentiable and thus \mathcal{P}_{f} is singleton-valued. Suppose by contradiction that f is not strictly 1 -weakly convex. By Corollary A.6 , there exist r_{1}1 . Then, E_{f}=\mathbb{R} . Furthermore, let r_{\min} be a proximal selection of f . Then r_{\min} is \frac{V_{0}}{V_{0}-1} -Lipschitz continuous. Proof of Lemma A.10 : Define G:r\mapsto V_{0}f(r)+\frac{r^{2}}{2} , which is convex by V_{0} -weak convexity. For any \delta\in\mathbb{R} , the function F_{\delta}:r\mapsto f(r)+\frac{(\delta-r)^{2}}{2} can be written as F_{\delta}(r)=F_{0}(r)+\left(-\delta r+\frac{\delta^{2}}{2}\right)\,,\qquad\text{with}\qquad F_{0}(r)=\frac{1}{V_{0}}G(r)+\left(1-\frac{1}{V_{0}}\right)\frac{r^{2}}{2}\,. (185) Since V_{0}>1 , both terms on the right are convex, hence F_{0} is convex, and consequently F_{\delta} is convex. Furthermore, if r_{0}\in\mathbb{R} is such that G is differentiable at r_{0} , we have that, for any r\in\mathbb{R},\>G(r)\geq G(r_{0})+G^{\prime}(r_{0})(r-r_{0}) . Thus, F_{\delta} is coercive in r , and f is prox-coercive. Since it is weakly convex, it also is continuous and hence E_{f}=\mathbb{R} . Since r_{\min}(\delta) minimizes the convex function F_{\delta} , the first-order optimality condition gives 0\in\partial F_{\delta}(r_{\min}(\delta)) . From the expressions above, \partial F_{\delta}(r)=\frac{1}{V_{0}}\partial G(r)+\left(1-\frac{1}{V_{0}}\right)r-\delta. Therefore, at r=r_{\min}(\delta) , V_{0}\delta-(V_{0}-1)r_{\min}(\delta)\in\partial G(r_{\min}(\delta))=[G^{\prime}_{-}(r_{\min}(\delta)),G^{\prime}_{+}(r_{\min}(\delta))]. For \delta<\delta^{\prime} , using that r_{\min} is non-decreasing ( Proposition A.3 ) and G is convex (hence \partial G is monotone), V_{0}\delta-(V_{0}-1)r_{\min}(\delta)\leq G^{\prime}_{+}(r_{\min}(\delta))\leq G^{\prime}_{-}(r_{\min}(\delta^{\prime}))\leq V_{0}\delta^{\prime}-(V_{0}-1)r_{\min}(\delta^{\prime}). Rearranging yields 0\leq r_{\min}(\delta^{\prime})-r_{\min}(\delta)\leq\frac{V_{0}}{V_{0}-1}(\delta^{\prime}-\delta). which is the definition of Lipschitzness that we were looking for. ∎ Before proving the reciprocal, we recall a well known characterization of convex functions over intervals in our specific case. Lemma A.11 . Let F\,:\,\mathbb{R}\rightarrow\mathbb{R} be any function. F\text{ is convex}\iff F\text{ is locally Lipschitz continuous with }F^{\prime}\text{ non-decreasing} (186) Remark A.7 . A Lipschitz continuous function on a compact set is differentiable almost everywhere on this compact set. Thus, in the above equivalence, F^{\prime} non-decreasing must be understood as F^{\prime} is non decreasing over the set where it is defined. Proof of Lemma A.11 : Take a1 and \frac{\frac{L}{L-1}}{\frac{L}{L-1}-1}=L, (197) Lemma A.10 yields that r_{\min}\text{ is $L$-Lipschitz continuous}. (198) Now for the second equivalence, if r_{\min} is 1 -Lipschitz continuous, it is L -Lipschitz continuous for any L>1 . Hence, r\mapsto f(r)+\left(1-\frac{1}{L}\right)\frac{r^{2}}{2}\text{ is convex for any }L>1. (199) This family of convex functions converges pointwise to f as L\rightarrow 1^{+} , which is thus a convex function. Conversely, if f is convex, it is V_{0} -weakly-convex for any V_{0}>1 . Therefore, r_{\min}\text{ is }\frac{V_{0}}{V_{0}-1}\text{-Lipschitz continuous}. (200) Taking the point wise limit V_{0}\rightarrow\infty yields that r_{\min} is 1 -Lipschitz continuous. ∎ Corollary A.13 . Suppose E_{f}=\mathbb{R} and f is strictly 1 -weakly convex. Let r_{\min} be the unique continuous proximal selection of f . For r_{0}\in\mathbb{R} , r_{\min}^{-1}(r_{0})=r_{0}+[f^{\prime}_{-}(r_{0}),f^{\prime}_{+}(r_{0})]. Proof of Corollary A.13 : By Corollary A.9 , r_{\min} is uniquely determined and onto. By Proposition A.4 , r_{\min}^{-1}(r_{0})=\{\delta\in\mathbb{R}:r_{0}\in\mathcal{P}_{f}(\delta)\}=\{\delta\in\mathbb{R}:s_{f}(r_{0})\leq\delta\leq i_{f}(r_{0})\}=[s_{f}(r_{0}),i_{f}(r_{0})]. By Proposition A.5 , s_{f}(r_{0})=r_{0}+f^{\prime}_{-}(r_{0}) and i_{f}(r_{0})=r_{0}+f^{\prime}_{+}(r_{0}) . ∎ We are now ready to state the proof of the main results of this appendix. Proof of Theorem 5.3 : The proof follows by combining the previous results: The first statement follows from Proposition A.2 . The non-decreasing property and almost everywhere differentiability follow from Proposition A.3 . The three main equivalences follow from, Corollary A.9 for the continuity equivalence and Corollary A.12 for both Lipschitz equivalences. The uniqueness statement follows from any of these conditions implying strict 1 -weak convexity (or stronger), which by Corollary A.6 and Proposition A.4 implies \mathcal{P}_{f} is singleton-valued. The characterization of r_{\min}^{-1}(r_{0}) follows from Corollary A.13 . Finally, r_{\min} is increasing if and only if it is injective, which occurs if and only if r_{\min}^{-1}(r_{0}) is a singleton for all r_{0} . This happens if and only if f^{\prime}_{-}(r_{0})=f^{\prime}_{+}(r_{0}) for all r_{0} , i.e., f is differentiable everywhere. ∎ Proof of Corollary 5.4 : The proof of the first statement follows by applying Lemma A.10 to Vf since V_{0}/V>1 . The second statement follows from Theorem 5.3 applied to the function Vf in place of f , with L=\frac{V_{0}}{V_{0}-V}>1 . Under Assumption 2.3 , for the loss \mathscr{L} , the function z\mapsto\mathscr{L}(y,z) is V_{L} -weakly convex. Under Assumption 2.4 , applying Corollary 5.4 with V=\frac{\tau^{\star}}{\kappa^{\star}}\tilde{r}_{L}(\delta)\in\argmin_{r\in\mathbb{R}}\left\{\frac{(\delta-r)^{2}}{2}+\frac{\tau^{\star}}{\kappa^{\star}}\mathscr{L}(y,r)\right\}. If we define \mathcal{P}_{\frac{\tau^{\star}}{\kappa^{\star}}\mathscr{L}(y,\cdot)}:\omega\in\mathbb{R}\mapsto\tilde{r}_{L}(\omega)\in\mathbb{R} satisfying \mathcal{P}_{\frac{\tau^{\star}}{\kappa^{\star}}\mathscr{L}(y,\cdot)}(\omega)\in\mathcal{P}_{\frac{\tau^{\star}}{\kappa^{\star}}\mathscr{L}(y,\cdot)}(\omega) for all (\omega,y)\in\mathbb{R}^{2} . Similarly, for the regularization \mathscr{R} , the function w\mapsto\mathscr{R}(w) is V_{R} -weakly convex. Corollary 5.4 with V=\frac{1}{\eta^{\star}} and L=L_{R} provides a unique L_{R} -Lipschitz continuous selection \mathcal{P}_{\frac{1}{\eta^{\star}}\mathscr{R}(\cdot)}:\mathbb{R}\to\mathbb{R} with \mathcal{P}_{\frac{1}{\eta^{\star}}\mathscr{R}(\cdot)}(w)\in\mathcal{P}_{\frac{1}{\eta^{\star}}\mathscr{R}(\cdot)}(w) for all w\in\mathbb{R} . These Lipschitz-continuous proximal selections define the update functions g^{\star} and f^{\star} in Eq. 14 , recovering the regularity conditions originally stated in the first formulation of our framework. ∎ Appendix B Applications B.1 Examples of Weakly Convex Losses We verify Assumption 2.4 for standard robust losses found in the statistics literature. Example B.1 (Huber Loss) . The Huber loss is defined as \mathscr{L}_{H}^{\xi}(y,z)=\xi^{2}\int_{0}^{|y-z|/\xi}\min(1,x)\,dx. Its second derivative with respect to z is \frac{\partial^{2}\mathscr{L}_{H}^{\xi}}{\partial z^{2}}(y,z)=\begin{cases}1&\text{if }|y-z|\leq\xi\\ 0&\text{if }|y-z|>\xi\end{cases}\geq 0. Thus z\mapsto\mathscr{L}_{H}^{\xi}(y,z) is convex, hence V_{0} -weakly convex for any V_{0}\geq 0 . Example B.2 (Tukey Biweight Loss) . The Tukey biweight loss is defined as \mathscr{L}_{T}^{\xi}(y,z)=\begin{cases}\frac{\xi^{2}}{6}\left[1-\left(1-\frac{(y-z)^{2}}{\xi^{2}}\right)^{3}\right]&\text{if }|y-z|\leq\xi\\ \frac{\xi^{2}}{6}+\varrho|y-z-\xi|^{3}&\text{if }y-z>\xi\\ \frac{\xi^{2}}{6}+\varrho|y-z+\xi|^{3}&\text{if }y-z<-\xi\end{cases} where \varrho>0 is a coercivity parameter. For u:=y-z with |u|\leq\xi , the second derivative is \frac{\partial^{2}\mathscr{L}_{T}^{\xi}}{\partial z^{2}}(y,z)=\left(1-\frac{u^{2}}{\xi^{2}}\right)\left(1-5\frac{u^{2}}{\xi^{2}}\right). This is negative when \frac{u^{2}}{\xi^{2}}\in(\frac{1}{5},1) . To find the minimum, set t=\frac{u^{2}}{\xi^{2}} and minimize (1-t)(1-5t)=1-6t+5t^{2} . Taking the derivative yields -6+10t=0 , giving t=\frac{3}{5} . At this point, the second derivative equals (1-\frac{3}{5})(1-3)=-\frac{4}{5} . For |u|>\xi , we have \frac{\partial^{2}\mathscr{L}_{T}^{\xi}}{\partial z^{2}}=6\varrho|u-\xi|>0 . Taking V_{0}=\frac{5}{4} ensures \frac{\partial^{2}}{\partial z^{2}}\left(V_{0}\mathscr{L}_{T}^{\xi}+\frac{z^{2}}{2}\right)\geq\frac{5}{4}\cdot\left(-\frac{4}{5}\right)+1=0. Thus \mathscr{L}_{T}^{\xi} is \frac{5}{4} -weakly convex. Example B.3 (Cauchy Loss) . The Cauchy loss is defined as \mathscr{L}_{C}^{\xi}(y,z)=\frac{\xi^{2}}{2}\log\left(1+\frac{(y-z)^{2}}{\xi^{2}}\right). Its second derivative with respect to z is \frac{\partial^{2}\mathscr{L}_{C}^{\xi}}{\partial z^{2}}(y,z)=\frac{1-\frac{(y-z)^{2}}{\xi^{2}}}{\left(1+\frac{(y-z)^{2}}{\xi^{2}}\right)^{2}}. Setting t=\frac{(y-z)^{2}}{\xi^{2}} and minimizing h(t)=\frac{1-t}{(1+t)^{2}} gives h^{\prime}(t)=\frac{t-3}{(1+t)^{3}}=0 at t=3 , with minimum value h(3)=\frac{-2}{16}=-\frac{1}{8} . Taking V_{0}=8 ensures \frac{\partial^{2}}{\partial z^{2}}\left(V_{0}\mathscr{L}_{C}^{\xi}+\frac{z^{2}}{2}\right)\geq 8\cdot\left(-\frac{1}{8}\right)+1=0, so \mathscr{L}_{C}^{\xi} is 8 -weakly convex. Example B.4 ( \ell_{2} Regularization) . The \ell_{2} regularization is defined as \mathscr{R}_{\lambda}(w)=\frac{\lambda}{2}w^{2} . Its second derivative is \mathscr{R}_{\lambda}^{\prime\prime}(w)=\lambda\geq 0 for \lambda>0 . This is convex, hence V_{0} -weakly convex for all V_{0}\geq 0 . B.2 Negative Regularization in a Spherical Shell To study the landscape of the problem at hand we slice it in spherical shells of radius squared equal to q . We have that \displaystyle\min_{{\mathbf{w}}\in\mathbb{R}^{d}}\frac{1}{d}\quantity[ \sum_{\dataidx=1}^n \lossfun\qty(y_\dataidx, \frac{\w^\top\x_\dataidx}{\sqrt{d}} ) ]+\frac{\lambda}{2}\frac{\norm{\w}_{2}^{2}}{d} \displaystyle=\min_{q\geq 0}\min_{{\mathbf{w}}\in\mathcal{K}_{q,q}}\frac{1}{d}\quantity[ \sum_{\dataidx=1}^n \lossfun\qty(y_\dataidx, \frac{\w^\top\x_\dataidx}{\sqrt{d}} ) ]+\frac{\lambda}{2}q (201) \displaystyle=:\min_{q\geq 0}h(q)+\frac{\lambda}{2}q (202) where the second minimization can be studied with the help of Theorem 2.1 . We now are left with the study of a function in a single variable h(q) . We consider the specific form of the optimization objective obtained from Corollary 6.5 , where for (m^{\star},q^{\star},\tau^{\star},\kappa^{\star},\nu^{\star},\eta^{\star})\in\mathcal{S}^{\star} we have that h(q)=\alpha\mathbb{E}\quantity[ \lossfun\qty(y, \mathcal{P}_{\frac{\tau^\star}{\kappa^\star}\lossfun(y,\cdot)} \qty(\frac{m^\star}{\sqrt{\rho}} s + \sqrt{q - \frac{(m^\star)^2}{\rho}} h)) ]\,, (203) and where q^{\star}=q since in the problem definition we have that a=b=q . We also note that because of the assumption on \mathscr{L} h(q) is also convex. We study first the derivative of the first term. We notice three facts: first, the value of the derivative in zero is non-positive, secondly it is bounded from above by a constant and third for q\to\infty the derivative reaches zero from above. We thus define the value of \lambda_{c} as \lambda_{c}=\min\quantity{\lambda\in\RR\mid\exists q \geq 0 \quad\partial h(q) = \frac{\lambda}{2} }\,, (204) The presence of a single minimizer for \lambda\geq 0 follows from the convexity of the optimization objective. For \lambda_{c}\leq\lambda<0 follows from the fact that for \lambda\in[\lambda_{c},0] there are two values of q such that \partial h(q)=\frac{\lambda}{2} . If we consider \lambda<\lambda_{c} we have that there is no stationary point for h(q) and thus it is a decreasing function of q and its minimum is attained at q\to\infty . B.3 Performances of Linearized AMP The equations presented in the main text are the ones presented in Corollary 6.4 where the projection on the set \mathcal{K}_{1,1} at each step simplifies the second and third line in Eq. 110 to be m=\frac{\hat{m}}{\hat{q}+\hat{m}^{2}}\,,\quad\tau=\frac{1}{\sqrt{\hat{q}+\hat{m}^{2}}}\,. (205) Appendix C Details on Numerical Experiments To find the minimum of the Eq. 16 we use the fixed point characterization from Corollary 6.4 as they are written in a way amenable to be solved via fixed-point iteration. Starting from a random initialization, we iterate through both the hat and non-hat variable equations until the maximum absolute difference between the order parameters in two successive iterations falls below a tolerance of 10^{-5} . To speed-up convergence we use a damping scheme, updating each order parameter at iteration i , designated as x_{i} , using x_{i}:=x_{i}\mu+x_{i-1}(1-\mu) , with \mu as the damping parameter. Once convergence is achieved for fixed value of hyper-parameters they are optimized using a gradient-free numerical minimization procedure for a one dimensional minimization. For each iteration, we evaluate the proximal operator numerically using SciPy’s Brent’s algorithm for root finding ( scipy.optimize.minimize_scalar ). The numerical integration is handled with SciPy’s quad method ( scipy.integrate.quad ), which provides adaptive quadrature of a given function over a specified interval. These numerical techniques allow us to evaluate the equations and perform the necessary integrations with the desired accuracy. Concerning the setting of each figure shown in the main text we have Figure 1 The left figure is a plot of the different loss functions defined in Section 3.1 with \xi=1.5 . The data model considered in the right figure is P_{\mathrm{out}}\quantity(y \mid z)=\begin{cases}z+\sqrt{\Delta}z_{1}&\text{with prob. }1-\epsilon\\ \sqrt{\Sigma}z_{2}&\text{with prob. }\epsilon\end{cases} (206) with \epsilon=0.1 , \Delta=\Sigma=1 , and z_{1},z_{2}\sim\mathcal{N}(0,1) independent. The error bars are 10 different realizations of the numerical minimization of the ERM problem with d=1000 . Figure 2 The figure on the left shows the minimum value of {\mathcal{A}}^{\star} as a function of the fixed q . The channel chosen is the one in Eq. 206 with \epsilon=0.3 , \Delta=1.0 , \Sigma=5.0 . We use the Huber loss with \xi=1 . The values of the regularization parameter chosen are \lambda\in\quantity{-1.0, 1.0, -2.1, -1.735, 0.0} and \alpha=10 . For the right figure we use again the channel defined in Eq. 206 with \lambda= and the previous parameter as before. The gradient descent iterations are done on a system with d=1000 .