Precise Error Analysis of Regularized M-estimators in High-dimensions

Introduction

Regularized M-estimators. The most widely used approach to obtain an estimate $\hat{\mathbf{x}}$ of the unknown $\mathbf{x}_{0}$ from the vector $\mathbf{y}$ of observations is via solving the convex program

Challenge. A popular way to compare performance among different instances of (1) is by the squared-error $\|\hat{\mathbf{x}}-\mathbf{x}_{0}\|_{2}^{2}$. In the absence of the regularizer function $f$, the family of estimators in (1) corresponds to the “plain-vanilla” regression M-estimators and there is a complete, practical and elegant theory developed in the statistics literature that analyzes its asymptotic performance. This theory includes some of the most popular notions and results in statistics, such as conditions on the optimality of Maximum Likelihood (ML) estimators, the theory of robust statistics [Hub11], etc.. Unfortunately, it only holds under an assumption of many observations (large m) of only a few well-chosen variables to be estimated (small $n$), and thus, it fails to capture the following prevailing features of modern applications: (a) large number of variables to be estimated (large $n$); (b) (often) fewer observations than variables ($m<n$); (c) the unknown signal $\mathbf{x}_{0}$ is structured. Therefore, an extension of the theory to the high-dimensional regime is of interest. In fact, the roots of such a question are quite old and date back to the works of Huber, Kolmogorov, and others (see [Hub11, Ser13] and references therein). Nonetheless, and despite several remarkable recent advances, we still lack a general and clear theory that would resemble that of the traditional regime.

2 Contribution

Error Prediction. In this work, we characterize the (mean) squared-error performance of the generalized M-estimator in (1) under the following setting:

– high-dimensional proportional regime: $m,n\rightarrow\infty$ with $m/n\rightarrow\delta\in(0,\infty)$,

– Gaussian design: $\mathbf{A}$ has entries iid Gaussian,

– Regularity conditions: only minimal and generic conditions are imposed on the loss function, the regularizer, and the noise and signal statistics.

We show that the squared error converges in probability to a nontrivial limit which is given as the unique minimizer to a deterministic convex optimization problem that only involves four scalar optimization variables. The normalized number of measurements $\delta$ and the regularizer parameter ${\lambda}$ appear in the objective function of the optimization explicitly. In contrast, the loss function $\mathcal{L}$ and the noise distribution $p_{\mathbf{z}}$ appear through a summary functional, which we call the Expected Moreau Envelope. The same holds for the regularizer $f$ and the distribution of the signal $p_{\mathbf{x}_{0}}$.

Generality. A key feature of our result is that it holds under very general settings. All existing results in the literature on the performance of specific instances of M-estimators can be seen as special cases of the main theorem of this work (Theorem 3.1). Beyond those, the theorem can be used to derive a wide range of novel results, including instances where the loss function and the regularizer may be non-smooth or non-separable, and where the noise distribution may have unbounded moments.

Opportunities. The precise characterization of the squared error permits an accurate performance comparison between different instances of (1). Hence, the main theorem of this work lays the groundwork towards developing a complete theory of regularized M-estimators in the high-dimensional regime. This involves providing rigorous answers to optimality questions regarding the choice of the involved parameters:

What is the optimal loss function and regularizer, under different settings, e.g. in the presence of outliers, particular structure of $\mathbf{x}_{0}$, etc.?

What is the minimum achievable squared error in each one of those scenarios? Do there exist consistent M-estimators, i.e. instances for which $\|\hat{\mathbf{x}}-\mathbf{x}_{0}\|_{2}\rightarrow 0$?

How to optimally tune the regularizer parameter $\lambda$?

How does the sampling ratio $\delta=m/n$ affect the error?

Given the popularity of M-estimators, the questions above are clearly of both theoretical and practical interest. Only partial answers that apply to special cases and to only few of them are known in the literature, while most remain open and challenging. We envision that the main theorem of this work gets us a step closer to overcoming the challenge and to exploring phenomena that are new when compared to what is known in the classical statistics regime. Although, this goes beyond the scope of the current paper, we have included some preliminary results and discussions to illustrate those potentials.

Convex Gaussian Min-max Theorem. The main ingredient of the proof of our main result is the Convex Gaussian Min-max Theorem (CGMT). The CGMT is a generalization and a strengthened version of a classical Gaussian comparison inequality due to Gordon, which dates back to 1988 [Gor88, Gor85]. While Gordon’s original result only provides lower bounds, the CGMT shows that the results become tight when additional convexity assumptions are imposed. The idea of combining Gordon’s inequality with convexity is attributed to Stojnic, who used it to analyze the high-SNR performance of the constrained LASSO [Sto13a]. The CGMT solidifies and adds upon this initial idea. The final result leads to a transparent and readily applicable framework which is powerful enough to be useful under the general framework of the current paper. In fact, the CGMT in the generality that it appears hereAn early version appears by subset of the authors in [TOH15]., might be of independent interest and may have applications that go beyond the scope of our work. Finally, it should be noted, that the successful application of the CGMT to the analysis of regularized M-estimators involves a number of new ideas that are introduced as part of this work.

3 Related Work

With the advent of Compressed Sensing there is a very large number of theoretical results that have appeared in recent years in place for various types of regularized M-estimators. The vast majority of those results hold under standard incoherence or restricted eigenvalue conditions on the measurement matrix $\mathbf{A}$ Such conditions have been shown to be satisfied by a wide class of randomly designed measurement matrices, (e.g. [FR, EK12, DDEK11] and references therein). A more recent line of works obtains similar order-wise bounds under even weaker assumptions on the randomness properties of $\mathbf{A}$ [LM14, Tro14, SBR15]., but they are order-wise in nature, i.e., they characterize the error performance only up to loose constants. While this line of work includes unifying frameworks for the analysis of general instances of (1), the loose constants involved in the error bounds do not permit any accurate comparisons among the different instances (e.g. [NRWY12, Wai14, BCFS14, LHC15] and references therein); therefore, they cannot be used to answer optimality questions of the nature discussed in Section 1.2.

4 Organization

The rest of the paper is organized as follows. In Section 2, we introduce some basic notions and set-up the problem. The main theorem (Theorem 3.1) is presented next in Section 3, where its features and implications are also discussed. Theorem 3.1 is specialized to instances of M-estimators with separable loss and regularizer functions in Section 4. A number of examples of M-estimators and relevant numerical simulations are included in Section 5 to illustrate the applicability and the premises of the result. In Section 6, we introduce the mechanics that lead to the proof of Theorem 3.1; this includes the statement of the Convex Gaussian Min-max Theorem in Section 6.2. Section 1.4 discusses the relevant literature in some detail. Finally, the paper concludes in Section 8 with a discussion on several promising directions of future research. The proofs of the results of all the sections are deferred to Appendices A-E

Preliminaries

We gather here the basic notation that is used throughout the work.

We reserve the letters $\mathbf{g}$ and $\mathbf{h}$ to denote standard Gaussian vectors (with iid entries $\mathcal{N}(0,1)$) of dimensions $m$ and $n$, respectively. Similarly, $G$ and $H$ are reserved to denote (scalar) standard normal random variables.

2 Setup

Linear Asymptotic Regime: Our study falls into the linear asymptotic regime in which the problem dimensions $m$ and $n$ grow proportionally to infinity with

Information about the structure of $\mathbf{x}_{0}$ is encoded in $p_{\overline{\mathbf{x}}_{0}}$. For instance, to study an $\mathbf{x}_{0}$ which is sparse, it is typical to assume that its entries are i.i.d. $\mathbf{x}_{0,i}\sim(1-\rho)\delta_{0}+\rho q_{\mathbf{X}_{0}}$, where $\rho\in(0,1)$ becomes the normalized sparsity level, $q_{\mathbf{X}_{0}}$ is a scalar p.d.f. and $\delta_{0}$ is the Dirac delta functionSuch models in place for studying structured signals have been widely used in the relevant literature, e.g. [DJ94, DMM11, DJM13]. In fact, the results here continue to hold as long as the marginal distribution of $\mathbf{x}_{0}$ converges to a given distribution (as in [BM12])..

Here, ${\lambda}>0$ is a fixed regularizer parameter.

Estimation error: Solving (2) aims to recovering $\mathbf{x}_{0}$. We assess the quality of the estimator $\hat{\mathbf{x}}$ with the “empirical squared error” (or simply, “squared-error”) defined as: $\frac{1}{n}\|\hat{\mathbf{x}}-\mathbf{x}_{0}\|_{2}^{2}.$ Note, that this is a random quantity owing to the randomness of $\mathbf{A},\mathbf{z}$ and $\mathbf{x}_{0}$. Our main theorem precisely evaluates its high probability limit as $n\rightarrow\infty$.

General Result

As already hinted in the introduction the functions $\mathcal{L}$, $f$ and the distributions $p_{\mathbf{z}}$ and $p_{\mathbf{x}_{0}}$ determine the error performance indirectly through “summary functionals” related to the Moreau-envelope approximations. The assumption below is an in-probability convergence requirement on the sequence of Moreau-envelopes, and defines those summary functionals. It also involves a rather natural growth restriction on the loss function in the presence of noise to handle instances where the noise may have unbounded moments.

Assumption 1 is rather mild: as discussed later in Section 3.4.1, it holds naturally under very generic settings. Yet, it is of key importance since it defines the functionals $L$ and $F$, which are necessary ingredients involved in the error prediction of (2). The main theorem in its most general form will require some extra (continuity and growth) properties on the functionals $L$ and $F$. Those will most often be naturally inherited from corresponding easy-to-verify and in cases well-studied properties of the Moreau envelope functions.

2 Theorem

Assumption 1 provides us with the basic terminology needed for the statement of the main theorem. Technically, a few additional mild constraint qualifications are required. We present those immediately after the statement of the main result (see Assumption 2). The proof of the theorem is deferred to Appendix A. An outline is given earlier in Section 6.

Let $\hat{\mathbf{x}}$ be a minimizer of the Generalized $M$-estimator in (2) for fixed ${\lambda}>0$. Further let Assumptions 1 and 2 hold. If the following convex-concave minimax scalar optimization

has a unique minimizer $\alpha_{*}$, then, it holds in probability that

We will often refer to the optimization problem in (3) as the Scalar Performance Optimization (SPO) problem.

A few important remarks are in place here (a detailed discussion follows in Section 3.4): (i) The convergence in the theorem is over the randomness of the design matrix $\mathbf{A}$, of the noise vector $\mathbf{z}$ and of the unknown signal $\mathbf{x}_{0}$. (ii) As was discussed in Section 2.2 the result applies to a properly defined sequence of M-Estimators of growing dimensions $m$ and $n$ such that $m/n\rightarrow\delta\in(0,\infty)$. (We have dropped the dependence of $\hat{\mathbf{x}}$ and $\mathbf{x}_{0}$ on $n$ to simplify notation.) (iii) The terms involving division by $\alpha$ and $\beta$ are understood as taking their limiting values when $\alpha=0$ and $\beta=0$, i.e. $\mathcal{D}(0,{\tau_{g}},\beta,{\tau_{h}})=\lim_{\alpha\rightarrow 0^{+}}\mathcal{D}(\alpha,{\tau_{g}},\beta,{\tau_{h}})$ and $\mathcal{D}(\alpha,{\tau_{g}},0,{\tau_{h}})=\lim_{\beta\rightarrow 0^{+}}\mathcal{D}(\alpha,{\tau_{g}},\beta,{\tau_{h}}).$

Before proceeding with a further discussion of the result, let us state Assumption 2 on the functionals $L$ and $F$ as required by Theorem 3.1.

We say that Assumption 2 holds if all the following are true.

$\lim_{\tau\rightarrow 0^{+}}F(\tau,\tau)=0$ and $\lim_{c\rightarrow+\infty}\left\{\frac{c^{2}}{2\tau}-F(c,\tau)\right\}=+\infty$ for all $\tau>0$.

$\lim_{\tau\rightarrow 0^{+}}{L(\alpha,\tau)}<+\infty$, $\lim_{\tau\rightarrow 0^{+}}{L(0,\tau)}=0$, and , $-\infty<L_{2,+}(0,0):=\lim_{\tau\rightarrow 0^{+}}L_{2,-}(0,\tau)\leq 0.$

3 Separable M-estimators

A special yet popular family of M-estimators involves separable loss/regularizer functions and iid noise/signal distributions. We refer to such instances as “separable M-estimators”. To be concrete, consider solving

In order to get a better understanding of those issues before discussing Theorem 3.1 in its most generality, we state below a summary of the main result regarding separable M-estimators. (The formal statement will be given later in Section 4, which includes a detailed treatment of separable M-estimators.)

where $\alpha_{*}$ is the unique minimizer to the (SPO) problem in (3) with

4 Remarks

We have made an effort to identify technical assumptions required for the statement of Theorem 3.1 which are as generic and minimal as possible. Assumption 1 summarizes those technical conditions that are essential for our result to hold in its most general form. In later sections, when we discuss special cases (e.g. separable M-estimators in Section 4), we show that these conditions translate to more primitive sufficient conditions that are often easier to check.

We remark that if Assumption 1 holds, then both the functions $F$ and $L$ defined therein are jointly convex in their arguments. This follows from the facts that (a) the Moureau envelope of a convex function is jointly convex in its arguments (cf. Lemma D.1(ii)), (b) taking limits preserves convexity. In that sense, the continuity requirement of the assumption on $L$ and $F$ is rather mild, since convex functions are continuous on the interior of their domain [Roc97, Thm. 10.1].

Assumption 1(b) is tailored to scenarios in which the noise distribution has unbounded moments (e.g. mean, variance); in this case $\|\mathbf{z}\|_{2}/\sqrt{n}$ is not bounded with high probability. It is not hard to see that condition 1(b) implies $\sup_{\mathbf{v}}\frac{\|\mathcal{L}(\mathbf{v})\|_{2}}{\|\mathbf{v}\|_{2}}<\infty$; such a requirement that $\mathcal{L}$ grows at most linearly at infinity is natural in the context of robust statistics.

4.2 On Assumption 2

Assumption 2(d) is meant to deal with cases of noise with unbounded moments (this will often translate to $L_{0}=+\infty$). In such cases, we require that $L(c,\tau)$ grows sub-linearly in $\tau$. Once more, this property is essentially inherited without any extra effort by corresponding property of the Moreau-envelope.

4.3 On the theorem

In evaluating the objective function $\mathcal{D}$ of the (SPO) at $\alpha=0$ and $\beta=0$, Assumptions 2(a)-(b) turn out to be useful, giving

An important property of the (SPO) is that it is convex: its objective function $\mathcal{D}(\alpha,{\tau_{g}},\beta,{\tau_{h}})$ is (jointly) convex in $\alpha,{\tau_{g}}$ and concave in $\beta,{\tau_{h}}$. As is well known, convexity translates to the ability to efficiently solve the optimization; see also Remark 3.4.10 below.

4.4 Further Discussions

The role of the normalized number of measurement $m/n\rightarrow\delta$ and that of the regularizer parameter ${\lambda}$ are explicit in (3). On the other hand, the structure of $\mathbf{x}_{0}$ and the choice of the regularizer $f$ are implicit through $F$. Similarly, any prior knowledge on the noise vector $\mathbf{z}$ and the effect of the loss function $\mathcal{L}$ are also implicit in (3) through $L$. In the separable case, the role of those summary parameters is played by the Expected Moreau envelope function.

The (SPO) problem in (3) is convex-concave and only involves four scalar variables. Thus, the optimal $\alpha_{*}$ can, in principle, be efficiently numerically computed. Equivalently, $\alpha_{*}$ can be expressed as the solution to the corresponding first-order optimality conditions, which offers an alternative to the current statement of Theorem 3.1. In Section 4.3.1 we explicitly derive the system of stationary equations for the case of separable M-estimators. It is often possible to solve the stationary equations by means of simple iterative schemes (cf. Remark 4.3.3). Furthermore, this alternative formulation might be easier to work with when deriving analytic properties of $\alpha_{*}$. As an example, in Sections 5.1–5.3 for specific instances of M-estimators, we start from the stationary equations, combine them in an appropriate way, and, derive insightful and practically useful properties, such as lower bounds on $\alpha_{*}$, necessary conditions on the problem parameters such that $\alpha_{*}$ (correspondingly, the equated error) be bounded, etc..

The statement of the theorem holds under an asymptotic setup in which the problem dimensions $m$ and $n$ grow to infinity. In Section 5 we examine via simulations the validity of the prediction for finite values of $m$ and $n$. The results indicate that the asymptotic prediction becomes accurate for values of the problem parameters ranging on a few hundreds, and, in cases even on a few tens.

Theorem 3.1 assumes that the entries of the design matrix $\mathbf{A}$ are iid Gaussian. In the proof of the result this assumption is crucial since the proof itself heavily relies on the CGMT, for which the gaussianity assumption is implicit. Yet, a few important remarks apply regarding the potential use of the results and the analysis of this work to cases beyond the gaussian design. Some examples include the cases of Elliptical Distributions [Kar13] and Isotropically Random Orthogonal matrices to which the CGMT framework is still applicable. We discuss those in Section 8.

All existing results in the literature on the performance of specific instances of M-estimators can be seen as special cases of Theorem 3.1. Beyond those, the theorem can be used to derive a wide range of novel results, including instances where the loss function and the regularizer may be non-smooth and non-separable, and where, the noise distribution may have unbounded moments. We discuss several examples in Section 5.

Separable M-estimators

We specialize the general result of Section 3 to the popular case where the loss function $\mathcal{L}$ and the regularizer $f$ are both separable, and, the noise vector and signal $\mathbf{x}_{0}$ both have entries iid. To make things concrete, assumeNote the slight abuse of notation here in using $f$ to denote both the vector-valued and scalar regularizer function.

To apply Theorem 3.1, we first need to verify that Assumptions 1 and 2 hold for both the loss function and the noise distribution, and, for the regularizer and the signal distribution.

where the expectation is over $Z\sim p_{Z}$ and $G\sim\mathcal{N}(0,1)$. This is shown in Lemma 4.1 below.

Apart from (8), we also need to satisfy Assumption 1(b), which here translates to the following requirement:

1.2 Regularizer and Signal Distribution

Not surprisingly, following the results of Section 4.1, the required condition on $f$ and $p_{x}$ becomes

where the expectation is over $X_{0}\sim p_{x}$ and $H\sim\mathcal{N}(0,1)$. Additionally, the following mild assumptions are required:

If $f$ and $p_{x}$ satisfy (11) and (12), then, Assumptions 1(a) and 2(a) hold with

2 The Expected Moreau Envelope

If conditions (8), (10) and (11) are satisfied, then Theorem 3.1 is applicable with $L$ and $F$ given as in (9) and (13), respectively. We call those functions, the Expected Moreau envelopes. The important role they play in determining the error performance of the corresponding M-estimator is apparent from Theorem 3.1. In this section, we discuss two key features that they possess, namely, smoothness and strict convexity.

The strict convexity property of $L$ is critical because it guarantees uniqueness of the minimizer $\alpha_{*}$ of the (SPO) problem in Theorem 3.1. This implication is proved in Lemma C.3 in Appendix C.3.

3 Error Prediction

We are now ready to state the main result of this section which characterizes the squared error of separable M-estimators. This is essentially a corollary of Theorem 3.1.

for all $\alpha,\beta\geq 0,{\tau_{g}},{\tau_{h}}>0$ and $p_{*}=(\alpha_{*},{\tau_{g}}_{*},\beta_{*},{\tau_{h}}_{*})$. A similar remark as the one that follows Theorem 3.1 is in place regarding the values $\alpha=0$ and $\beta=0$. At these, the derivatives above should be interpreted as the corresponding (upper) limits as $\alpha\rightarrow 0^{+}$ and $\beta\rightarrow 0^{+}$. The continuity properties of the Moreau envelope (see Lemma D.1) guarantee that those limits are well-defined

When $\alpha_{*}>0$ and there also exist optimal values $\beta,{\tau_{g}},{\tau_{h}}$, all of them strictly positive, then (14) holds with equalities. In this case, a little bit of algebra, and, an appropriate change of variables from ${\tau_{g}},{\tau_{h}}$ to $\kappa,\nu$, shows that the optimality conditions can be expressed as follows:

3.2 Remarks

Examples and Numerical Simulations

Consider an M-estimator without regularization, i.e.,

where we have performed the (straightforward) optimization over ${\tau_{h}}$: $\inf_{{\tau_{h}}>0}\frac{{\tau_{h}}}{2}+\frac{\beta^{2}}{2{\tau_{h}}}=\beta.$ We may equivalently express $\alpha_{*}$ as the solution to the first-order optimality conditions of (18). In particular, the stationary equations (see (15)) simplify in this case to the following system of two equations in two unknowns:

Starting from (19), some interesting conclusions can be drawn regarding the performance of M-estimators without regularization, which we gather in the following remarks.

It follows from (19) that in the absence of regularization, it is required that the number of measurements $m$ is at least as large as the dimension of the ambient space $n$ ($\delta\geq 1$), in order for the recovery to be stable, i.e. the error be finite. To see this, assume stable recovery, then there exists $(\alpha_{*},\kappa_{*})$ satisfying (19). Starting from the second equation, applying the Cauchy-Schwarz inequality and substituting back the first equation we find:

2 Ridge Regularzation

A popular regularizer in the machine learning and statistics literature is the ridge regularizer (also known as Tikhonov regularizer), i.e.

We specialize Theorem 3.1 to that case. For simplicity, we assume a separable loss function, and, $\mathbf{z}_{j}\stackrel{{\scriptstyle\text{iid}}}{{\sim}}p_{Z}$ and $\mathbf{x}_{0,i}\stackrel{{\scriptstyle\text{iid}}}{{\sim}}p_{X}$.

The first-order optimality conditions (see (15)) of this problem simplify after some algebra to the following two equations in two unknowns:

Now, we can solve these to get the following closed form expression for $\alpha^{*}$:

Observe that letting ${\lambda}\rightarrow 0$ (which would correspond to ordinary least-squares) and assuming $\delta>1$, $\kappa$ in (27) approaches ${1}/{(\delta-1)}$ and the optimal $\alpha^{2}$ in (26) becomes ${\sigma_{z}^{2}}/({\delta-1}),$ which agrees with (21), as expected.

First, we use the results of Remark 5.2.2 to calculate the achieved error of the M-estimator optimized over the values of the regularizer parameter:

The optimization over ${\lambda}$ is possible as follows. From (25), we find

Substituting this in (26), and denoting $x=\kappa{\lambda}$, gives

Minimizing $\alpha^{2}$ over ${\lambda}>0$ in (28) is equivalent to minimizing the fraction above over $0<x<1$, since there always exist $\kappa,{\lambda}$ satisfying $x=\kappa{\lambda}$ and (29). Thus, performing the optimization over $0<x<1$ in (30) we find

Next, Wu and Verdu have shown in [WV12, Thm. 8, Eqn. (56)] that the MMSE is given by the expression in the right-hand side above as well. This, completes the proof of the claim.

3 Cone-constrained M-estimators

for some set $\mathbf{x}\in\mathcal{C}$. The role of the regularizer in (2) is played here by the constraint $\mathbf{x}\in\mathcal{C}$. It is common that $\mathcal{C}$ takes the form $\mathcal{C}=\{\mathbf{x}~{}|~{}g(\mathbf{x})\leq g(\mathbf{x}_{0})\}$, i.e. the set of descent directions of some convex function $g$, which is structure inducing for $\mathbf{x}_{0}$ [CRPW12, FM14, OTH13, PV15]. Of course, such a formulation assumes prior knowledge of the value of $g$ at $\mathbf{x}_{0}$. Also, in this case, there exists by Lagrangian duality a value of ${\lambda}$ for which the regularized M-estimator with $f(x)=g(x)$ is equivalent to (32).

3.2 Error Performance

In the last equality above we have used the homogeneity of the cone $\mathcal{K}$. Let $\mathcal{K}^{\circ}$ denote the polar cone of $\mathcal{K}$, and,

This quantity is known as the statistical dimension [ALMT13] of the cone $\mathcal{K}$, or, as the Gaussian distance squared [OTH13]. It can be though of as a measure of the size of the cone, and also, it is very closely related to the gaussian width of $\mathcal{K}$[ALMT13]. We assume that

This translates to an assumption on the degrees of freedom of the structured signal $\mathbf{x}_{0}$ being proportional to its dimension. For example, for a $k$-sparse $\mathbf{x}_{0}$ and $g(\mathbf{x})=\|\mathbf{x}\|_{1}$, (34) is satisfied for $k=\rho n$, $\rho\in(0,1)$.

Compared to (3), we have performed the (straightforward) optimization over ${\tau_{h}}$: $\inf_{{\tau_{h}}>0}\frac{{\tau_{h}}}{2}+\frac{\beta^{2}\overline{D}_{\mathcal{K}}^{2}}{2{\tau_{h}}}=\beta\overline{D}_{\mathcal{K}}.$

3.3 Remarks

Starting from (35) we can conclude on the minimum number of measurements required for stable recovery. We show that the normalized number of measurements $\delta$ need to be at least as large as $\overline{D}_{\mathcal{K}}$, in order for the error to be finite. This is to be compared with the case where no regularization is used that required $\delta\geq 1>\overline{D}_{\mathcal{K}}$ (see Remark 5.1.1). To prove the claim, assume finite error, then the value where it converges is predicted by (35). Standard first-order optimality conditions give The three equations in (36) correspond to differentiation of the objective of (35) with respect to $\tau,\alpha$ and $\beta$, respectively. If any of the variables is zero at the optimal, then, the corresponding equation holding with an inequality is necessary and sufficient. On the other hand, if the optimal is strictly positive, then the equation should hold with equality.

Starting from the second equation, applying the Cauchy-Schwarz inequality and substituting back the first equation we conclude as follows:

It can be easily checked that if $\delta>\overline{D}_{\mathcal{K}}$, then the optimal $\alpha_{*}$ is

It is insightful to compare this with (21), the corresponding error formula for least-suares: the only difference is that $1$ is substituted with the statistical dimension $\overline{D}_{\mathcal{K}}$. Also, verifying the conclusion of the previous remark, we now require $\delta>\overline{D}_{\mathcal{K}}$ instead of $\delta>1$, implying that recovery is in general possible with less measurements than the dimension of the signal.

(Lower Bound) In (36b) apply Stein’s inequality and combine it with (36a) to yield

For Gaussian noise of variance $\sigma^{2}$, we have $1/I(Z)=\sigma^{2}$. In this case the lower bound in (39) coincides with the error formula of the least-squares loss function, which then proves optimality of the latter.

(Consistent Estimators) The lower bound in (39) only holds if the optimal $\alpha_{*}$ in (35) is strictly positive. This is not always the case: under circumstances, it is possible to choose the loss function such that the resulting cone-constrained M-estimator is consistent. Theorem 3.1 is the starting point to identifying such interesting scenarios.

then the first-order optimality conditions in (36) are satisfied for $\alpha\rightarrow 0,{\tau_{g}}\rightarrow 0$ and some $\beta>0$. Thus, when the number of measurements is large enough such that (40) holds, then $\alpha_{*}=0$, and, $\mathbf{x}_{0}$ is perfectly recovered In the context that it appears here, the perfect recovery condition in (40) has been shown previously in [TH14]. The problem is very closely related to the demixing problem in which one aims to extract two (or more) constituents from a mixture of structured vectors [MCD+14]. In that context, recovery conditions like the one in (40) have been generalized to other king of structures beyond sparsity [MT14, MCD+14, FM14]. Our purpose here has been to illustrate how Theorem 3.1 can be used to derive such results. Besides, the generality of the paper’s setup offers the potential of extending such consistency-type results beyond cone-constrained M-estimators and beyond fixed signals $\mathbf{x}_{0}$. This is an interesting direction of future research. .

4 Generalized LASSO

Equivalently, the error is predicted by the solution to the stationary equations in (15) with $e^{\prime}_{\frac{1}{2}(\cdot)^{2}}(\chi;\tau)=\frac{\chi}{1+\tau}.$ The second and third equations in (15) give

Solving these for $\kappa$ and $\nu$, and substituting them in the remaining two equations results in the following system of two nonlinear equations in two unknowns

5 Square-root LASSO

In contrast, to the other examples in this section, the square-root LASSO is an instance of (2) with a non-separable loss function. Observe the normalization of the loss function with a $\sqrt{n}$-factor. This is to satisfy our condition of Section 2.2 that $(\forall c>0)(\exists C>0)~{}\left[\|\mathbf{v}\|_{2}\leq c\sqrt{n}\implies\frac{1}{\sqrt{n}}\sup_{\mathbf{s}\in\partial\mathcal{L}(\mathbf{v})}\|\mathbf{s}\|_{2}\leq C\right]$.

Also, Assumption 1(b) is trivially satisfied, and, Section E.2 shows the same for Assumptions 2(b)-(d). Thus, considering any regularizer that satisfies Assumptions 1(a) and 2(a), Theorem 3.1 applies, and predicts the squared error of (43) as the unique minimizer $\alpha_{*}$ to the following optimization:

To arrive to (45) starting from (3), we have replaced $L$ with (44) and have performed the minimization over ${\tau_{g}}$ as shown below:

The optimization in (46) can be simplified one step further. It is shown in Section E.2 that $-\frac{\alpha\beta^{2}}{2{\tau_{h}}}+{\lambda}F\left(\frac{\alpha\beta}{{\tau_{h}}},\frac{\alpha{\lambda}}{{\tau_{h}}}\right)$ is a non-increasing function of $\beta$ for $\beta>0$. Therefore, the (SPO) becomes equivalent to the following

The fact that the optimization in (47) predicts the squared error of (161), has been recently shown by the authors in [TAH15]. That work only considers the square-root LASSONote however, that [TAH15] considers a more general measurement model than the one of the current paper, one that allows for nonlinearities., while here, we have (re)-derived the result as a corollary of the general Theorem 3.1.

6 Heavy-tails

In this section, we investigate instances where the noise distribution has unbounded moments. In the presence of (say) heavy-tailed noise, it is a common practice to use a loss function that grows to infinity no faster than linearly. This is also suggested by Assumption 1(b) (cf. (10) for the separable case), as has already been discussed.

As a first example, consider the regularized-LAD estimator:

6.2 Huber-loss

The Huber-loss function with parameter $\rho>0$ is defined as

7 Numerical Simulations

We have performed a few numerical simulations on specific instances of M-estimators that were previously discussed in Section 5. The purpose is to illustrate both the validity of the prediction of Theorem 3.1, as well as, that of the remarks that followed as a consequence of it.

When the number of measurements $m$ gets large enough, then, for an appropriate range of values of the regularizer parameter, the estimator is consistent, i.e. the unknown signal $\mathbf{x}_{0}$ is perfectly recovered. This is relevant to Remark 5.3.4 where we proved this to be the case for the closely related cone-constrained LAD estimator. For that, we were able to quantify how large $m$ should be as a function of the sparsities of the noise and of the signal, see (40).

The prediction of Theorem 3.1 remains accurate when the measurement matrix has entries iid Bernoulli ($\{\pm 1\}$). This suggests that the error behavior (at least of this specific instant of M-estimator) undergoes some universality properties. See also the relevant discussion in Section 8.

Proof Highlights

Our goal is to characterize the nontrivial limiting behavior of $\|\hat{\mathbf{x}}-\mathbf{x}_{0}\|_{2}$, where $\hat{\mathbf{x}}$ is any solution to the following minimization,

To get a direct handle on the error term, it is convenient to change the optimization variable to $\mathbf{w}:=\mathbf{x}-\mathbf{x}_{0}$, so then $\hat{\mathbf{w}}:=\hat{\mathbf{x}}-\mathbf{x}_{0}$ is a solution to (recall $\mathbf{y}=\mathbf{A}\mathbf{x}_{0}+\mathbf{z}$)

There is a simple but standard argument that is in the heart of most analyses of such minimization estimators, and comes as follows. Suppose we knew that the error $\|\hat{\mathbf{w}}\|_{2}$ converges eventually to some deterministic value, call it $\alpha_{*}$. This is equivalent to $\hat{\mathbf{w}}$ belonging in the following set

with probability one (w.p.1) for all $\epsilon>0$. Letting ${\mathcal{S}}_{\epsilon}^{c}$ denote the complement of that set, observe, that if w.p. 1,

then $\hat{\mathbf{w}}$ must lie in ${\mathcal{S}}_{\epsilon}$. Note that with this standard trick we have translated a question on the optimal solution of the minimization problem in (50) to one regarding its optimal cost. One possible approach in comparing the two random processes in (52) would be to first identify the converging limits of both. If say

which is just a comparison between two deterministic quantities.

This is exactly the approach we want to take here: show (53) and (54). Unfortunately, directly working with the objective function $M$ and proving (53) turns out to be rather challenging. Instead, we prove the desired indirectly, via working with an auxiliary objective function which is simpler to analyze. What justifies this idea is the Convex Gaussian min-max Theorem (CGMT), which we present next.

2 The CGMT

The Convex Gaussian Min-max Theorem associates with a primary optimization (PO) problem a simplified auxiliary optimization (AO) problem from which we can tightly infer properties of the original (PO), such as the optimal cost, the optimal solution, etc..

Specifically, the (PO) and (AO) optimizations are given as follows:

In (55), let ${\mathcal{S}}_{\mathbf{w}},{\mathcal{S}}_{\mathbf{u}}$ be compact sets, $\psi$ be continuous on ${\mathcal{S}}_{\mathbf{w}}\times{\mathcal{S}}_{\mathbf{u}}$, and, $\mathbf{G},\mathbf{g}$ and $\mathbf{h}$ all have entries iid standard normal. The following statements are true:

Let ${\mathcal{S}}$ be an arbitrary open subset of ${\mathcal{S}}_{\mathbf{w}}$ and ${{\mathcal{S}}^{c}}={\mathcal{S}}_{\mathbf{w}}/{\mathcal{S}}$ . Denote $\Phi_{{\mathcal{S}}^{c}}(\mathbf{G})$ and $\phi_{{\mathcal{S}}^{c}}(\mathbf{g},\mathbf{h})$ the optimal costs of the optimizations in (55a) and (55b), respectively, when the minimization over $\mathbf{w}$ is now constrained over $\mathbf{w}\in{{\mathcal{S}}^{c}}$. If there exist constants $\overline{\phi},~{}\overline{\phi}_{{\mathcal{S}}^{c}}$ and $\eta>0$ such that

$\overline{\phi}_{{\mathcal{S}}^{c}}\geq\overline{\phi}+3\eta$,

$\phi(\mathbf{g},\mathbf{h})<\overline{\phi}+\eta$ with probability at least $1-p$,

$\phi_{{\mathcal{S}}^{c}}(\mathbf{g},\mathbf{h})>\overline{\phi}_{{{\mathcal{S}}^{c}}}-\eta$ with probability at least $1-p$,

The CGMT is an extension of a Gaussian comparison inequality proved by Gordon in 1988 [Gor88, Gor85]. Starting with the works of Rudelson and Vershynin[RV06] and of Stojnic [Sto09b], Gordon’s original theorem has played a key role in the analysis of (underdetermined) noiseless linear inverse problems (also, [OH10, CRPW12]). We refer the interested reader to [TOH15] (also, Remark 3.4.14) for more details and a discussion on the relation of the CGMT to the result by Gordon.

The first two statements of Theorem 6.1 are identical to [TOH15, Thm. 3], and, a proof is included therein. Statement (iii) as it appears here is novel. In particular, when compared to its counterpart in [TOH15, Thm. 3], it holds for all problem dimensions $m,n$, and also, it holds for more general sets ${\mathcal{S}}$. We present a proof of the last statement of the theorem in Appendix B.

Using the same notation as in Theorem 6.1, suppose there exists constants $\overline{\phi}<\overline{\phi}_{{\mathcal{S}}^{c}}$ such that $\phi(\mathbf{g},\mathbf{h})\xrightarrow{P}\overline{\phi}$ and $\phi_{{\mathcal{S}}^{c}}(\mathbf{g},\mathbf{h})\xrightarrow{P}\overline{\phi}_{{{\mathcal{S}}^{c}}}$. Then,

Observe that the conditions of the corollary are the same as those in (53)-(54) only this time they hold for the objective function of the (AO). From that, we already know that $\mathbf{w}_{\phi}(\mathbf{g},\mathbf{h})\in{\mathcal{S}}$ with probability approaching 1. The statement of the corollary is stronger in that it concludes the same for $\mathbf{w}_{\Phi}(\mathbf{G})$, which is the solution to a seemingly different optimization problem.

The CGMT might be of individual interest and may have applications that go beyond the topic of this paper. With this in mind, we have chosen to present it above in its most general version. In the upcoming sections we specialize the result to the study of the error performance of M-estimators.

3 Applying the CGMT

Back to the problem of analyzing (50) and our goal of proving (53). As already hinted, the CGMT will be handy towards this direction. The M-estimator optimization in (50) will play the role of the (PO), and, we need to identify the corresponding (AO). To do so, we first need to birng (50) in the form of (55a) as required by the CGMT.

The idea here is to use dualityA preliminary version of this idea first appeared in [TPH15], in which the authors analyzed the error performance of the Generalized-LASSO. We have extended the idea here to apply to any convex loss function $\mathcal{L}$.. Specifically, we can equivalently view the minimization in (50) as follows:

Then, associating a dual variable $\mathbf{u}$ with the equality constraint above, we have

Clearly, this is now in the desired format: we can identify the bilinear form $\mathbf{u}^{T}\mathbf{A}\mathbf{w}$ and a function $\psi(\mathbf{w},\mathbf{v},\mathbf{u})$ which is convex in $(\mathbf{w},\mathbf{v})$ and concave in $\mathbf{u}$. Thus, immediately, the corresponding (AO) problem becomesWhen compared to (55b) it is more convenient in (57) to write the two terms $\|\mathbf{w}\|\mathbf{g}^{T}\mathbf{u}$ and $\|\mathbf{u}\|\mathbf{h}^{T}\mathbf{w}$ with a minus sign instead. We can do this, since $\mathbf{g}$ and $\mathbf{h}$ are Gaussian vectors; thus, their distribution is sign independent.:

Now that we have identified the (AO) problem, we wish to apply Corollary 6.1 for the set ${\mathcal{S}}_{\epsilon}$ of (51). Applying the corollary amounts to analyzing the convergence of the (AO) problem (and that of its “restricted” counterpart). This will be performed in two stages. The first involves a deterministic analysis, in which the optimization in (57) is simplified and reduced to one which only involves scalar random variables. In the second stage, we analyze the convergence properties of this scalar optimization.

Before proceeding with those, in all the above, we have been silent regarding any compactness requirements of Theorem 6.1. These technicalities are carefully handled in Appendix A. (In particular, this is where Assumption 1(b) becomes useful.)

4 Analysis of the Auxiliary Optimization

A key idea that facilitates the analysis of the (AO) in (57) is to reduce the optimization into one that only involves scalar optimization variables. The objective function of the (AO) is tailored towards this direction, and the only modification required is to express $f(\mathbf{x}_{0}+\mathbf{w})$ via its variational form as $\sup_{\mathbf{s}}\mathbf{s}^{T}(\mathbf{x}_{0}+\mathbf{w})-f^{*}(\mathbf{s})$, where $f^{*}$ is the Fenchel conjugate function.

This way, the variables $\mathbf{u}$ and $\mathbf{w}$ appear in the objective only through either linear terms or through their magnitudes. This observation suggests that one can easily optimize over their directions while fixing the magnitudes. To illustrate this, fixing the magnitude of $\mathbf{u}$ as $\|\mathbf{u}\|_{2}=\beta\geq 0$, we can optimize over its direction by aligning it with $-\|\mathbf{w}\|_{2}\mathbf{g}-\mathbf{z}+\mathbf{v}$. Then (57) simplifies to the following,

Suppose we could switch the order of min-max above. Then, it would be possible to do the same trick with $\mathbf{w}$, i.e. fix $\|\mathbf{w}\|_{2}=\alpha\geq 0$ and minimize over its direction to get

Justifying that flipping in the order of min-max is not straightforward, since the objective function in (58) is not convex-concave; thus, what would otherwise be the arguments to be called upon, namely the Minimax Theorems (e.g. [S+58]), are not directly applicable here. Yet, in Appendix A, we show that such a minimax property holds asymptotically in the problem dimensions; thus, (59) is (for our purposes) equivalent to (58). We leave the details aside for the moment, and, proceed with the simplification of (59).

In (59), we have reduced the optimization over $\mathbf{w}$ and $\mathbf{u}$ to scalars $\alpha$ and $\beta$. Next, we wish to simplify the optimization over $\mathbf{s}$ and $\mathbf{v}$. However, the same trick as the one we applied for the former two variables won’t work. The new idea that we need here is to write the terms $\|\|\mathbf{w}\|_{2}\mathbf{g}+\mathbf{z}+\mathbf{v}\|_{2}$ and $\|\beta\mathbf{h}-{\lambda}\mathbf{s}\|_{2}$ using

What we achieve with this is that the corresponding terms become now separable over the entries of the vectors $\mathbf{v}$ and $\mathbf{s}$, which makes the optimization over them easier. The only price we have to pay is introducing just two more scalar optimization variables. That is (59) becomes

It can be readily seen that the minimization over $\mathbf{v}$ gives rise to the Moreau envelope function of $\mathcal{L}$ evaluated at $\mathbf{z}+\alpha\mathbf{g}$ with index ${\tau_{g}}/\beta$. A rather straightforward completion of squares arguments and a call upon the relation between the Moreau envelopes of conjugate pairs, leads to a similar conclusion regarding the minimization over $\mathbf{s}$, as well. Deferring the details to the appendix, we have reached the following scalar optimization

4.2 Convergence

Once we have simplified the (AO), it is now possible to analyze the convergence of its optimal cost. We start with the objective function of (60), which we shall denote $\mathcal{R}_{n}(\alpha,{\tau_{g}},\beta,{\tau_{h}})$ for convenience. FixTo be precise, an appropriate rescaling is required here. See Section A. $\alpha,{\tau_{g}},\beta,{\tau_{h}}$, then,

where we have assumed that $L$ and $F$ above are such that

Our next step is to use the point-wise convergence of (61) in order to prove the following result:

This statement is of course much stronger than the one in (61). The proof requires two main ingredients: (i) translating the point-wise convergence into a uniform one over compact sets, (ii) proving that $\mathcal{D}$ is level-bounded with respect to its arguments, thus, the sets of optimizers in (62) are bounded. For the first point, convexity turns out to be critical, while the latter can be shown if Assumption 2 holds.

5 Concluding

The analysis of the (AO) problem led us to (62). The same arguments also show that

Recall from Section 6.4.1 that the variable $\alpha$ plays the role of the magnitude of $\mathbf{w}$, hence the random optimization in the LHS of (63) corresponds to the restricted (AO) problem $\phi_{{\mathcal{S}}^{c}_{\epsilon}}(\mathbf{g},\mathbf{h})$ of Corollary 6.1. What remains for the corollary to apply is showing that $\overline{\phi}_{{\mathcal{S}}^{c}_{\epsilon}}>\overline{\phi}$. This follows by assumption of the theorem that the minimizer over $\alpha$ in the RHS of (62) is unique. Applying the corollary, shows the desired and concludes the proof.

Prior Literature

In Section 1.4 we gave a brief overview of the results most closely aligned with our work. Here, we expand on this discussion.

Phase transitions. The work on phase transitions of non-smooth convex optimization used to recover structured signals from noiseless linear measurements is an essential precursor for the follow-up work on the error behavior of regularized M-estimators. Hence, we discuss it here in some detail. This line of work attempts to characterize the minimum number of measurements, say $m_{*}$, as a function of the structural complexity of $\mathbf{x}_{0}$ and of the choice of $f$, such that $\mathbf{x}_{0}$ is the unique solution of the optimization $\min_{\mathbf{A}\mathbf{x}=\mathbf{A}\mathbf{x}_{0}}f(\mathbf{x})$ with probability approacihing 1 if and only if $m>m_{*}$.

Precise reconstruction error. As mentioned in Section 1.4, there is a very long list of early results on the error performance of regularized M-estimators which derive “order-wise” bounds that involve unknown scaling constants (e.g. [CT07, BCW11, BRT09, NRWY12, Wai14, Ver14, BCFS14, LHC15] and references therein). Nevertheless, in this discussion we focus entirely on more recent results that derive precise characterizations rather than loose bounds. Unless otherwise stated, the literature that we describe below takes the random measurement matrix $\mathbf{A}$ to have independent Gaussian entries (but, see Remark 7.0.1). Also, it studies the high-dimensional asymptotic regime where $m$ and $n$ grow to infinity at a proportional rate.

Finally, a third approach to analyze the mean-squared error performance of high-dimensional M-estimators has been undertaken by El Karoui in [Kar13, EK15]. El Karoui uses leave-one-out and martingale ideas from statistics and ideas from random matrix theory to accurately predict the squared error of ridge-regularized (a.k.a. $f(\mathbf{x})=\|\mathbf{x}\|_{2}^{2}$) M-estimators. The analysis can handle noise distributions with unbounded moments, but it requires a smooth and separable loss function. In our work, we drop both these assumptions and extend the results to general convex regularizers. In comparing the two works, we note that El Karoui’s proof technique can deal with more general assumptions on the design matrix $\mathbf{A}$. (Nevertheless, please see Remark 7.0.1). Beyond matrices with iid entries, El Karoui [EK15] further considers elliptical models. Even though we do not explicitely consider such an extension in the current paper, our proof technique is readily applicable to this more general scenario. Please also refer to the short discussion at the end of Section 8.

Since the works [Sto09b, CRPW12, ALMT13] we now have a very clear understanding of the phase transitions of non-smooth convex signal recovery methods with iid Gaussian measurements. Under the same measurement model, the current paper extends this clear picture to the noisy setting by precisely characterizing the reconstruction error. Here, we briefly discuss relevant results that prove the universal behavior of iid Gaussian measurements over a wider class of distributions.

From this discussion we have excluded random measurement models beyond ones with iid entries. An important example includes design matrices with orthogonal rows, e.g. Isotropically Random Orthogonal (IRO) matrices, randomly subsampled Fourier and Hadamard matrices, etc.. While the universality of phase transition appears to extend to such designs, this is not the case for the reconstruction error. Thrampoulidis & Hassibi [TH15] have proved that the error behavior of the LASSO is different for IRO and for Gaussian matrices. The same is true for the elliptical model considered by El Karoui in [EK15].

In parallel to the works referenced above, there have been a number of works that studied the same questions mixing heuristic-based arguments and extended simulations. For example, [GBS09, KWT10, RGF09, VKC14] use the replica method from statistical physics, which provides a powerful tool for tackling hard analytical problems, but still lacks mathematical rigor in some parts. Closer to the setting of our work, the high-dimensional error performance of regularized M-estimators has been previously considered via heuristic arguments and simulations in [EKBB+13, BBEKY13]. In particular, Bean et. al. [BBEKY13] shows that maximum likelihood estimators are in general inefficient in high-dimension and initiate the study of optimal loss functions. It is worth revisiting and extending those results in connection to the mathematically rigorous approach of the current paper.

Conclusions and Future work

Theorem 3.1 predicts the squared error performance of general regularized M-estimators in the presence of noisy linear Gaussian measurements. The analysis is performed in the high-dimensional regime where both the number of measurements and the dimension of the signal grow large at a proportional rate. The theorem identifies the precise dependence of the error performance on the problem parameters, namely, the loss function $\mathcal{L}$, the regularizer $f$, the noise and signal distributions $p_{\mathbf{z}}$ and $p_{\mathbf{x}_{0}}$, the value of the regularizer parameter $\delta$ and the normalized number of measurement $\delta$.

We envision several interesting directions in which the results of this paper can operate as a starting point for future work, which we shall discuss next.

Optimal tuning. Regularized M-estimators have been widely used in practice and a remaining challenging issue is that of optimally tuning the regularizer parameter ${\lambda}$. Theorem 3.1 establishes the precise dependence of the error performance on ${\lambda}$. Hence, in principle, it can be used to provide valuable insights and guidelines regarding its optimal choice. In Section 5.7 and Figure 2 we saw an example that highlights the importance of being able to choose ${\lambda}$ in the correct range of values, otherwise the performance can be significantly deteriorated.

Comparing performances. Theorem 3.1 can be used to evaluate the performance of general M-estimators under different settings. Figure 2 serves as a preliminary numerical illustration: under the specific setting, LAD outperforms the LASSO for appropriate choices of ${\lambda}$. The error expressions of Theorem 3.1 will allow quantifying such comparisons and yield analytic such conclusions.

Optimal loss/regularizer functions. One of the most exciting (at the same time challenging) potential applications of the results of this paper is identifying optimal choices for the loss and regularizer functions under different settings. Since the error characterization differs from the corresponding results of classical statistics (where the signal dimension is fixed), we expect new phenomena to arise and the answers to differ in general. When it comes to the regularizer, the optimality question has been partially considered in the literature. When the structured signal $\mathbf{x}_{0}$ is considered fixed, then a good choice for the regularizer $f$ is one that minimizes the statistical dimension of the tangent cone of $f$ at $\mathbf{x}_{0}$ (cf. Section 5.3) [CRPW12, ALMT13, OTH13]Based on this, Chandrasekaran et. al. have suggested the notion of “atomic-norms” as a principled way for constructing appropriate convex regularizer functions for different kind of structures [CRPW12].. The results of [CRPW12] and [ALMT13] combined prove that this is indeed the optimal choice in the noiseless case. The same is true in the high-SNR regime when a least-squares loss function is used as shown in [OTH13, TPH15]. The more general setting of the current paper, will allow revisiting this question and extending the results to capture instances where $\mathbf{x}_{0}$ is associated with a prior distribution $p_{\mathbf{x}_{0}}$, the loss function differs from a least-squares one, and, the noise variance is not necessarily tending to zero. Theorem 3.1 suggests that the quantity that will be involved in the optimization is the Expected Moreau envelope, which is in fact a generalization of the statistical dimension (cf. Section 5.3). When it comes to the optimal choice of the loss function with respect to the noise distribution $p_{\mathbf{z}}$, less is known. Again, the expected Moreau envelope will be central in the optimization, but is yet to be understood how this will translate into practical recipes for the design of optimal loss functions.

Consistency. Another important question that is also related to the optimal choice of loss/regularizer functions, asks for conditions under which the squared error is zero, if at all this is possible. In Remark 5.3.4, we discussed an example of a an M-estimator that under specific noise and signal distributions, becomes consistent provided that the normalized number of measurements is large enough and that the regularizer parameter is chosen on the correct range (also, see Figure 2). Answering questions regarding consistency, amounts to identifying conditions under which $\alpha_{*}=0$ can be the optimal solution to the (SPO) of Theorem 3.1.

Beyond Gaussian Designs. Theorem 3.1 assumes that the entries of the design matrix $\mathbf{A}$ are iid Gaussian. Yet, there are potentials of extending the results to other classes of distributions as discussed next.

Matrices with iid entries. Preliminary numerical results (Figure 1 is an example) suggest a universality property of the prediction of Theorem 3.1 to design matrices with entries iid drawn from a wider class of probability distributions, e.g. sub-gaussians. Besides simulation results, it is worth mentioning that El Karoui proves this to be the case for M-estimators with ridge-regulararization and a twice differentiable loss function [EK15].

Isotropically Random Orthogonal (IRO) Matrices. An IRO matrix $\mathbf{A}$ is sampled uniformly at random from the manifold of row-orthogonal matrices satisfying $\mathbf{A}\mathbf{A}^{T}=\mathbf{I}_{m}$. Studying the error performance of M-estimators under such designs is of practical interest Certain classes of orthogonal matrices such as discrete-cosine and Hadamard allow for fast multiplication and reduced complexity. Numerical simulations in [TH15] suggest that the error prediction for IRO matrices is valid for random DCT and Hadamard matrices. . In [TH15], we were able to extend the CGMT framework to accurately predict the error performance of the LASSO when $\mathbf{A}$ is IRO and $\mathbf{z}$ is iid gaussian. Extending those ideas to general M-estimators in a flavor similar to the setting of this paper is a possible direction for future research.

Acknowledgement

The authors would like to thank George Moustakides, Joel Tropp, P. P. Vaidyanathan and Panagiotis Vergados for helpful conversations and suggestions. Christos Thrampoulidis would also like to thank Ashkan Panahi and Linqi (Daniel) Guo; some of the ideas that led to this work were born in collaboration with them, cf. [TPH15, TPGH15].

References

Appendix A Proof of Theorem 3.1

Here, we prove Theorem 3.1. The proof consists of several steps and intermediate results, that are stated as Lemmas. The proofs of the latter are all deferred to Appendix B.

Recall that $\mathbf{y}=\mathbf{A}\mathbf{x}_{0}+\mathbf{z}$. Our goal is to characterize the nontrivial limiting behavior of $\|\hat{\mathbf{x}}-\mathbf{x}_{0}\|_{2}/\sqrt{n}$. We start with a simple change of variables $\mathbf{w}:=(\mathbf{x}-\mathbf{x}_{0})/\sqrt{n}$, to directly get a handle on the error vector $\mathbf{w}$. Also, we normalize the objective by dividing with ${n}$ so that the optimal cost is of constant order. Then,

Instead of the optimization problem above, we will analyze a simpler Auxiliary Optimization (AO) that is tightly related to the Primary Optimization (PO) in (64) via the CGMT.

A.2 The CGMT for M-estimators

In this section, we show how the CGMT Theorem 6.1 can be applied to predict the limiting behavior of the solution $\|\hat{\mathbf{w}}\|_{2}$ to the minimization in (64). The main challenge here is to express (64) as a (convex-concave) minimax optimization in which the involved random matrix (here $\mathbf{A}$) appears in a bilinear form, exactly as in (55a). Also, some side technical details need to be taken care of. For example, in (55a) the optimization constraints are required by Theorem 6.1 to be bounded, which is not the case with (64). We start with addressing this immediately next.

The constraint set over which $\mathbf{w}$ is optimized in (55a) is unbounded. We will introduce “artificial” boundedness constraints that allow applying Theorem 6.1, while they do not affect the optimization itself. For this purpose, recall our goal of proving that $\|\hat{\mathbf{w}}\|_{2}$ converges to some (finite) $\alpha_{*}$ defined in Theorem 3.1. Define the set ${\mathcal{S}}_{\mathbf{w}}=\{\mathbf{w}~{}|~{}\|\mathbf{w}\|_{2}\leq K_{\alpha}\}$, where

for a constant $\zeta>0$, and, consider the “bounded” version of (64):

We expect that the additional constraint $\mathbf{w}\in{\mathcal{S}}_{\mathbf{w}}$ in (66) will not affect the optimization with high probability when $n$ is large enough. The idea here is that the minimizer of the original unconstrained problem in (64) satisfies $\|\hat{\mathbf{w}}\|_{2}\approx\alpha_{*}<K_{\alpha}$ w.h.p.. Of course, this latter statement is yet to be proven! Once this is done, we can return and confirm that our initial expectation is met. Lemma A.1 below shows that if $\|\hat{\mathbf{w}}^{B}\|\xrightarrow{P}\alpha_{*}<K_{\alpha}$, then, the same is true for the optimal of (64).

For the two optimizations in (64) and (66), let $\hat{\mathbf{w}}$ and $\hat{\mathbf{w}}^{B}$ be optimal solutions. Also, recall the definition of $K_{\alpha}$ in (65). If $\|\hat{\mathbf{w}}^{B}\|\xrightarrow{P}\alpha_{*}$, then $\|\hat{\mathbf{w}}\|\xrightarrow{P}\alpha_{*}$.

Owing to the result of the lemma, henceforth, we work with the bounded optimization in (66). Using some abuse of notation, we will refer to optimal solution of (66) as $\hat{\mathbf{w}}$, rather than $\hat{\mathbf{w}}^{B}$.

A.2.2 Identifying the (PO)

Here, we bring the minimization in (66) it in the form of the (PO) in (55a). For this purpose, we will use Lagrange duality. Note that the former can be equivalently expressed as

Associating a dual variable $\mathbf{u}$ to the equality constraint above, we write it as

It takes no much effort to check that the objective function above is in the desired format of (55a): the random matrix $\mathbf{A}$ appears in a bilinear term $\mathbf{u}^{T}\mathbf{A}\mathbf{w}$, and, the rest of the terms form a convex-concave function in $\mathbf{u},\mathbf{w}$. Furthermore, we can use Assumption 1(b) to show that the optimal $\mathbf{u}_{*}$ is bounded, which is a requirement of Theorem 6.1. In the same lines as in Section A.2.1, we henceforth work with the “bounded” version of (67), namely,

for ${\mathcal{S}}_{\mathbf{u}}:=\{\mathbf{u}~{}|~{}\|\mathbf{u}\|_{2}\leq K_{\beta}\}$ and $K_{\beta}>0$ a sufficiently large constant.

If Assumption 1(b) holds, then there exists sufficiently large constant $K_{\beta}$, such that the optimization problem in (68) is equivalent to that in (66), with probability approaching 1 in the limit of $n\rightarrow\infty$.

As a last step, before writing down the corresponding (AO) problem, it will be useful for the analysis of the latter, to express $f$ in a variational form through its Fenchel conjugate, which gives,

A.2.3 The (AO)

Having identified (69) as the (PO) in our application, it is straightforward to write the corresponding (AO) problem following (55b):

Once we have identified the (AO) problem, Corollary 6.1 suggests analyzing that one instead of the (PO). Our goal is showing that $\|\hat{\mathbf{w}}\|_{2}\xrightarrow{P}\alpha_{*}$. For this, we wish to apply the corollary to the following set

A.2.4 Asymptotic min-max property of the (AO)

It turns out that verifying the conditions of the corollary for the (AO) as it appears in (70) is not directly easy. In short, what makes the analysis cumbersome is the fact that the optimization in (70) is not convex (e.g. if $\mathbf{g}^{T}\mathbf{u}$ is negative, then $\|\mathbf{w}\|_{2}\mathbf{g}^{T}\mathbf{u}$ is not convex). Thus, flipping the order of min-max operations that would simplify the analysis is not directly justified.

At this point, recall that the (PO) in (69) is itself convex. In fact, for it, all conditions of Sion’s min-max Theorem [S+58] are met, thus, the order of min-max operations can be flipped. According to the CGMT, the (PO) and the (AO) are tightly related in an asymptotic setting. We use this, to translate the convexity properties of the (PO) to the (AO). In essence, we show that when dimensions grow, the order of min-max operations in the (AO) can be flipped. Thus, we will instead consider the following problem as the (AO):

Observe that the objective function remains the same; it is only the order of min-max operations that is slightly modified compared to (70). Since the objective function is not necessarily convex-concave in its arguments, there is no immediate guarantee that the two problems in (70) and (A.2.4) are equivalent for any realizations of $\mathbf{g}$ and $\mathbf{h}$. However, the lemma below essentially shows that such a strong duality holds with high probability over $\mathbf{g}$ and $\mathbf{h}$ in high dimensions. Hence, the problem in (A.2.4) can be as well used, instead of the one in (70), in order to analyze the (PO). For this reason, henceforth, we refer to (A.2.4) as the (AO) problem.

Let $\hat{\mathbf{w}}(\mathbf{A})$ denote an optimal solution of (64). Consider the (AO) problem in (A.2.4). Let $\alpha_{*}$ be as defined in Theorem 3.1. For any $\epsilon>0$ define the set ${\mathcal{S}}:=\{\mathbf{w}~{}|~{}|\|\mathbf{w}\|_{2}-\alpha_{*}|<\epsilon\}$, and, $\phi_{{\mathcal{S}}^{c}}(\mathbf{g},\mathbf{h})$ be the optimal cost of the same optimization as in (A.2.4), only this time the minimization over $\mathbf{w}$ is further constrained such that $\mathbf{w}\notin{\mathcal{S}}$. Assume that for any $K_{\alpha}>\alpha_{*}$ and for any sufficiently large $K_{\beta}$, there exist constants $\overline{\phi}<\overline{\phi}_{{\mathcal{S}}^{c}}$ such that for all $\eta>0$, with probability approaching one in the limit of $n\rightarrow\infty$ the following hold:

$\phi(\mathbf{g},\mathbf{h})<\overline{\phi}+\eta$,

$\phi_{{\mathcal{S}}^{c}}(\mathbf{g},\mathbf{h})>\overline{\phi}_{{{\mathcal{S}}^{c}}}-\eta$.

After Lemma A.3, what remains in order to prove Theorem 6.1 is satisfying the conditions of the lemma. This involves a thorough analysis of the (AO) problem in (A.2.4), which is the subject of the next few sections.

A.3 Scalarization

Observe that the optimization in (A.2.4) is over vectors. The purpose of this section is to simplify the (AO) into an optimization involving only scalar variables. Of course, one of this has to play the role of the norm of $\mathbf{w}$, which is the quantity of interest. The main idea behind the “scalarization” step of the (AO) is to perform the optimization over only the direction of the vector variables while keeping their magnitude constant. This is already hinted by the rearrangement of the order of min-max operations going from (70) to (A.2.4). Also, this process is facilitated by the following two:

The bilinear term $\mathbf{u}^{T}\mathbf{A}\mathbf{w}$ that appears in the (PO) conveniently “splits” into the two terms $\|\mathbf{w}\|_{2}\mathbf{g}^{T}\mathbf{u}$ and $\|\mathbf{u}\|_{2}\mathbf{h}^{T}\mathbf{w}$ in the (AO),

The term involving the regularizer, i.e. $f(\mathbf{x}_{0}+\mathbf{w})$ has been expressed in a variational form as $\sup_{\mathbf{s}}\mathbf{s}^{T}\mathbf{x}_{0}+\mathbf{s}^{T}\mathbf{w}-f^{*}(\mathbf{s})$.

The details of the reduction step are all summarized in Lemma A.4 below which shows that the (AO) reduces to the following convex minimax problem on four scalar optimization variables:

The following statements are true regarding the two minimax optimization problems in (A.2.4) and (72):

The objective function in (72) is continuous on its domain, (jointly) convex in $(\alpha,{\tau_{g}})$ and (jointly) concave in $(\beta,{\tau_{h}})$.

The order of inf-sup in (72) can be flipped without changing the optimization.

A.4 Convergence Analysis

The goal of this section is to show that the (AO) satisfies the conditions of Lemma A.3. This requires a convergence analysis of its optimal cost. We work with the scalarized version of the (AO) that was derived in the previous section:

Here, when compared to (72), we have subtracted from the objective the terms $\mathcal{L}(\mathbf{z})$ and $f(\mathbf{x}_{0})$, which of course does not affect the optimization. The optimization is of course random over the realizations of $\mathbf{g},\mathbf{h},\mathbf{z}$ and $\mathbf{x}_{0}$, and, by the WLLN, it is easy to identify the converging value of the objective function $\mathcal{R}_{n}$ for fixed parameter values $\alpha,{\tau_{g}},\beta,{\tau_{h}}$. Indeed, it converges to the objective function of the (SPO) problem in (3). For our goals, we need to show that minimax of the converging sequence of objectives converges to the minimax of the objective of the (SOP). Convexity of $\mathcal{R}_{n}$ plays a crucial role here since is being use to conclude local uniform convergence from the pointwise convergence. Uniform convergence is a requirement to conclude the desired.We remark that the tools used for this part of the proof are similar to those classically used for the study of consistency of $M$-estimators in the classical regime where $n$ is fixed and $m$ goes to infinity, cf. Arg-min theorems e.g. [LM08, Thm. 7.70], [NM94, Thm. 2.7] .

Let $\mathcal{R}_{n}(\alpha,{\tau_{g}},\beta,{\tau_{h}}):=\mathcal{R}_{n}(\alpha,{\tau_{g}},\beta,{\tau_{h}};\mathbf{g},\mathbf{h},\mathbf{z},\mathbf{x}_{0})$ be defined as in (73), and,

for $\mathcal{A}\subseteq[0,\infty)$. Further consider the following deterministic convex program

where $L$ and $F$ as in Theorem 3.1. If Assumption 1(a) and 2 hold, then,

$\mathcal{R}_{n}(\alpha,{\tau_{g}},\beta,{\tau_{h}})\xrightarrow{P}\mathcal{D}(\alpha,{\tau_{g}},\beta,{\tau_{h}})$, for all $(\alpha,{\tau_{g}},\beta,{\tau_{h}})$, and, $\mathcal{D}(\alpha,{\tau_{g}},\beta,{\tau_{h}})$ is convex in $(\alpha,{\tau_{g}})$ and concave in $(\beta,{\tau_{h}})$.

Assume $\alpha_{*}$ is the unique minimizer in (75) with $\mathcal{A}:=[0,\infty)$. For any $\epsilon>0$, define ${\mathcal{S}}_{\epsilon}:=\{\alpha~{}|~{}|\alpha-\alpha_{*}|<\epsilon\}$. Then, for any sufficiently large constants $K_{\alpha}>\alpha_{*}$ and $K_{\beta}>0$, and for all $\eta>0$, it holds with probability approaching 1 as $n\rightarrow\infty$:

$\phi_{[0,K_{\alpha}]}<\overline{\phi}_{[0,\infty)}+\eta$,

$\phi_{[0,K_{\alpha}]\setminus{\mathcal{S}}_{\epsilon}}\geq\overline{\phi}_{[0,\infty)\setminus{\mathcal{S}}_{\epsilon}}-\eta$,

$\overline{\phi}_{[0,\infty)\setminus{\mathcal{S}}_{\epsilon}}>\overline{\phi}_{[0,\infty)}$.

A.5 Putting all the Pieces Together

We are now ready to conclude the proof of Theorem 3.1.

Fix any $\epsilon>0$. Consider the set ${\mathcal{S}}_{\epsilon}=\{\mathbf{w}~{}|~{}|\|\mathbf{w}\|_{2}-\alpha_{*}\|_{2}<\epsilon$ as in Lemma A.3. We use the same notation as in the lemma. Let $K_{\alpha}>\alpha_{*}$ and arbitrarily large (but finite) $K_{\beta}>0$. From Lemma A.4(i) $\phi(\mathbf{g},\mathbf{h})$ is equal to the optimal cost of the optimization in (72). But, from Lemma A.5(b)(i), the latter converges in probability to some constant $\overline{\phi}$ (see Lemma A.5 for the exact value constant). The same line of arguments applies to $\phi_{{\mathcal{S}}_{\epsilon}^{c}}(\mathbf{g},\mathbf{h})$, showing that it converges to another constant $\overline{\phi}_{{\mathcal{S}}_{\epsilon}^{c}}$. Again from Lemma A.5(iii): $\overline{\phi}_{{\mathcal{S}}_{\epsilon}^{c}}>\overline{\phi}$. Thus, the conditions of Lemma A.3 are satisfied, and, it implies that the magnitude of any optimal minimizer (say) $\hat{\mathbf{w}}^{(PO)}$ of the (PO) problem in (69) satisfies $\hat{\mathbf{w}}^{(PO)}\in{\mathcal{S}}$ in probability, in the limit of $n\rightarrow\infty$. ∎

Appendix B Proofs for Section A

In this event, it is not hard to check using assumption (a) that $\Phi_{{\mathcal{S}}^{c}}>\Phi$, or equivalently $\mathbf{w}_{\Phi}\in{\mathcal{S}}$. Thus, it suffices to show that $\mathcal{E}$ occurs with probability at least $1-4p$.

Indeed, from statement (i) of the theorem and assumption (c),

Also, from statement (ii) of the theorem and assumption (b),

Combining the above displays the claim follows from a union bound.

B.2 Proof of Corollary 6.1

Call $\eta:=(\overline{\phi}_{{\mathcal{S}}^{c}}-\overline{\phi})/3>0$. By assumption, for any $p>0$ there exists $N:=N(\eta,p)$ such that the events $\{\phi<\overline{\phi}+\eta\}$ and $\{\phi_{{\mathcal{S}}^{c}}>\overline{\phi}_{{\mathcal{S}}^{c}}-\eta\}$ occur with probability at least $1-p$ each, for all $n>N$. Then, for all $n>N$, we can apply Theorem 6.1(iii) to conclude that $\mathbf{w}_{\Phi}(\mathbf{G})\in{\mathcal{S}}$ with probably at least $1-4p$. Since this holds for all $p>0$, the proof is complete.

B.3 Proof of Lemma A.1

For convenience, denote with $M(\mathbf{w})$ the objective function in (64). For some $\epsilon>0$ such that $\alpha+\epsilon<K_{\alpha}$ (e.g. $\epsilon=\zeta/2$ in (65)), denote $\mathcal{D}:=\{\mathbf{w}~{}|~{}\alpha-\epsilon\leq\|\mathbf{w}\|_{2}\leq\alpha+\epsilon\}$. By assumption, with probability approaching 1 (w.p.a. 1).

For the shake of a contradiction, assume that there exists optimal solution $\hat{\mathbf{w}}$ of (64) such that $\hat{\mathbf{w}}\not\in\mathcal{D}$ w.p.a. 1. Clearly,

Suppose $\hat{\mathbf{w}}\in{\mathcal{S}}_{\mathbf{w}}$, then $\hat{\mathbf{w}}$ is optimal for (66) and satisfies (76), which contradicts our assumption. Thus, $\hat{\mathbf{w}}\not\in{\mathcal{S}}_{\mathbf{w}}$. Next, let $\mathbf{w}_{\theta}:=\theta\hat{\mathbf{w}}+(1-\theta)\hat{\mathbf{w}}^{B}$ for $\theta\in(0,1)$ such that $\mathbf{w}_{\theta}\not\in\mathcal{D}$ and $\mathbf{w}_{\theta}\in{\mathcal{S}}_{w}$ (always possible, by definition of $\mathcal{D}$). By the convexity of $F$ and (77), it follows that $M(\hat{\mathbf{w}}_{\theta})\leq M(\hat{\mathbf{w}}^{B})$. Hence, $\hat{\mathbf{w}}_{\theta}$ is optimal for (66) and satisfies (76), which, again, is a contradiction. This completes the proof.

B.4 Proof of Lemma A.2

It suffices to prove the equivalence of the optimization (67) and (68). Let $\mathbf{w}_{*},\mathbf{v}_{*},\mathbf{u}_{*}$ be optimal in (67). To prove the claim, we show that $\mathbf{u}_{*}\in{\mathcal{S}}_{\mathbf{u}}\left(\Leftrightarrow\|\mathbf{u}_{*}\|_{2}\leq K_{\beta}\right)$ w.p.a. 1. From the first order optimality conditions in (67), we find that

B.5 Proof of Lemma A.3

Let $\mathbf{w}_{*}$ denote an optimal solution of the “bounded” optimization in (69). It will suffice to prove that $\mathbf{w}_{*}\in{\mathcal{S}}$ in probability. To see this, recall from Lemma A.2 that (69) is asymptotically equivalent to (66). Then, Lemma A.1 and the assumption $\alpha_{*}<K_{\alpha}$ guarantee that $\hat{\mathbf{w}}(\mathbf{A})\in{\mathcal{S}}$ in probability, as desired.

Denote $\Phi:=\Phi(\mathbf{A})$ the optimal cost of the minimization in (69) and $\Phi_{{\mathcal{S}}^{c}}:=\Phi_{{\mathcal{S}}^{c}}(\mathbf{A})$ the optimal cost of the same problem when the minimization is further restricted to be over the set $\mathbf{w}\in{\mathcal{S}}^{c}$. Note that $\mathbf{w}_{*}\in{\mathcal{S}}$ iff $\Phi_{{\mathcal{S}}^{c}}(\mathbf{A})>\Phi(\mathbf{A})$; hence, it will suffice to prove that the latter event occurs in probability.

We do so by relating the (PO) in (69) to the Auxiliary Optimization (AO) in (A.2.4) using Theorem 6.1. For concreteness, denote the objective function in (A.2.4) with $A(\mathbf{w},\mathbf{v},\mathbf{u},\mathbf{s})$, and, recall ${\mathcal{S}}_{\mathbf{w}}:=\{\mathbf{w}~{}|~{}\|\mathbf{w}\|_{2}\leq K_{\alpha}\}$, ${\mathcal{S}}_{\mathbf{u}}:=\{\mathbf{u}~{}|~{}\|\mathbf{u}\|_{2}\leq K_{\beta}\}$. With these, define

Observe here that the order of min-max in $\phi^{P}$ is exactly as in the original formulation of the CGMT, cf. (55b); $\phi^{D}$ is the dual of it, and $\phi$ in (A.2.4) involves yet another change in the order of the optimizations. The reason we prefer to work with the later problem, is that this particular order allows for a number of simplifications performed in Section A.3.

As done before, denote with ${\phi^{P}}_{{\mathcal{S}}^{c}},{\phi^{D}}_{{\mathcal{S}}^{c}}$ the optimal cost of the optimizations in (80) under the additional constraint $\mathbf{w}\in{\mathcal{S}}^{c}$. The two problems in (80) are related to the one in (A.2.4) as follows:

where the inequality follows from the min-max inequality [Roc97, Lem. 36.1]. Similarly,

Also, from Theorem 6.1(ii)more precisely, please refer to equation (32) in [TOH15].:

The remaining of the proof is in the same lines as the proof of 6.1(iii), but is included for clarity. Let $\eta:=(\phi_{{{\mathcal{S}}^{c}}}-\phi)/3>0$. We may apply (83) for $c=\overline{\phi}_{{\mathcal{S}}^{c}}-\eta$ and combine with (81) to find that

From assumption (b) the last term above tends to zero as $n\rightarrow\infty$. In a similar way, combining (84), (82) and assumption (a), we find that

goes to zero with $n\rightarrow\infty$. Denote the event $\mathcal{E}=\{{\Phi}_{{\mathcal{S}}^{c}}\geq\overline{\phi}_{{\mathcal{S}}^{c}}-\eta\text{~{}and~{}}{\Phi}\leq\overline{\phi}+\eta$}. From (85) and (86) the event occurs with probability approaching 1. Furthermore, in this event, after using assumption (a), we have ${\Phi^{b}}_{{\mathcal{S}}^{c}}\geq\overline{\phi}_{{\mathcal{S}}^{c}}-\eta>\overline{\phi}+\eta\geq{\Phi^{b}}$; equivalently, the optimal minimizer satisfies $\mathbf{w}_{*}\in{\mathcal{S}}$, which completes the proof.

B.6 Proof of Lemma A.4

(i) We start by showing how the vector optimization in (A.2.4) can be reduced to the scalar one that appears in (72). This requires the following steps.

Optimizing over the direction of $\mathbf{u}$: Performing the inner maximization is easy. In particular, using the fact that $\max_{\|\mathbf{u}\|_{2}=\beta}\mathbf{u}^{T}\mathbf{t}=\beta\|\mathbf{t}\|_{2}$ for all $\beta\geq 0$ the problem simplifies to a max-min one:

Optimizing over the direction of $\mathbf{w}$: Next, we fix $\|\mathbf{w}\|_{2}=\alpha$, and, similar to what was done above, minimize over its direction:

Changing the orders of min-max: Denote with $M(\alpha,\beta,\mathbf{v},\mathbf{s})$ the objective function above. It can be checked that $M$ is jointly convex in $(\alpha,\mathbf{v})$ and jointly concave in $(\beta,\mathbf{s})$ (cf. Lemma B.4). Thus, $\min_{\mathbf{v}}M$ is convex in $\alpha$ and jointly concave in $(\beta,\mathbf{s})$. Furthermore, the constraint sets are all convex and the one over which minimization over $\alpha$ occurs is bounded. Hence, as in [S+58, Cor. 3.3] we can flip the order of $\max_{\beta,\mathbf{s}}\min_{\alpha}$, to conclude with

Also, observe that the order of optimization among $\mathbf{v}$ and $\mathbf{s}$ does not affect the outcome.

The square-root trick: We apply the fact that $\sqrt{\chi}=\inf_{\tau>0}\{\frac{\tau}{2}+\frac{\chi}{2\tau}\}$ to both the terms $\frac{1}{\sqrt{n}}\|\alpha\mathbf{g}+\mathbf{z}-\mathbf{v}\|_{2}$ and $\frac{1}{\sqrt{n}}\|\beta\mathbf{h}-{\lambda}\mathbf{s}\|_{2}$:

Identifying the Moreau envelope: Arguing as before, we can change the order of optimization between $\beta$ and ${\tau_{g}}$. Also, it takes only a few algebra steps and using basic properties of Moreau envelope functions (in particular, Lemma B.5(ii)) in order to rewrite the last summand in (88) as below. If $\alpha>0$, then,

Otherwise, if $\alpha=0$, then the same term equals $-{\lambda}f(\mathbf{x}_{0})$ since $\max_{\mathbf{s}}\mathbf{s}^{T}\mathbf{x}_{0}-f^{*}(\mathbf{s})=f(\mathbf{x}_{0})$.

(ii) The continuity of the objective function in (72) follows directly from the continuity of the Moreau envelope functions, cf. [RW09, Lem. 1.25, 2.26]. In particular, regarding the two branches of the objective: it can be checked, using the continuity of the Moreau envelope, that the limit of the RHS in (90) as $\alpha\rightarrow 0$ evaluates to $-{\lambda}f(\mathbf{x}_{0})$. (In fact, this is the unique extension of the upper branch to a continuous finite convex function on the whole $\alpha\geq 0,\tau>0$, as per [Roc97, Thm. 10.3]).

Convexity of (72) can be checked from (88). By applying Lemma B.4, after minimization over $\mathbf{v}$ the Moreau Envelope remains jointly convex with respect to $\alpha$ and ${\tau_{g}}$ and concave in $\beta$. The same argument (and similar lemma) holds for the last term of (88) in which after minimization over $\mathbf{s}$ it remains jointly convex in $\beta$ and ${\tau_{h}}$ and concave in $\alpha$. Then the negative sign before this term makes it jointly concave in $\beta$ and ${\tau_{h}}$ and convex over $\alpha$.

B.7 Proof of Lemma A.5

(a) By Assumption 1(a) the normalized Moreau envelope functions in (73) converge in probability to $L$ and $F$, respectively. Also, $\|\mathbf{h}\|_{2}^{2}/n\xrightarrow{P}1$ by the WLLN. This proves the convergence part.

Lemma A.4(i) showed $\mathcal{R}_{n}$ to be convex-concave. Then, the same holds for $\mathcal{D}$ by point-wise convergence and the fact that convexity is preserved by point wise limits.

The bulk of the proof consists of showing that the following two statements hold

Before proceeding with the proof of those, let us show how the conclusion of the lemma is reached once (92) and (93) are established.

Using (92) and (93) to prove the lemma : Fix $K_{\alpha}>\alpha_{*}$, any $\delta>0$ such that $\mathcal{A}:=[\alpha_{*}-2\delta,\alpha_{*}+2\delta]\subset(0,K_{\alpha}]$ and $K_{\beta}>0$ large enough such that (92) and (93) both hold. Then, for all $\epsilon>0$, w.p.a.1:

For the last inequality above: if $\alpha_{*}=0$, it follows from (93), or otherwise from (92).

Next, consider the compact set $\mathcal{A}_{l}=\{\alpha>0~{}|~{}\alpha\in[\alpha_{*}-2\delta,\alpha-\delta]~{}\}$ and $\mathcal{A}_{r}=\{\alpha>0~{}|~{}\alpha\in[\alpha_{*}+\delta,\alpha+2\delta]~{}\}$. (Note that if $\alpha_{*}=0$, then $\mathcal{A}_{l}$ is empty.) From (92), we know that for all $\epsilon>0$, w.p.a.1

Let $\mathcal{A}_{lu}=\mathcal{A}_{l}\cup\mathcal{A}_{u}$ and combine the above to find

By assumption on uniqueness of $\alpha_{*}$ and on convexity of $M$, we have

and $M(\alpha_{*})=\min_{\alpha\in\mathcal{A}}M(\alpha)$. Thus, Applying (94) and (95) for $\epsilon=(\min_{\alpha\in\mathcal{A}_{lu}}M(\alpha)-M(\alpha_{*}))/3$ yields w.p.a.1 :

In this event, for any $\alpha\not\in\mathcal{A}$, there is a convex combination $\alpha_{\theta}:=\theta\hat{\alpha}_{n}+(1-\theta)\alpha$, ($\theta<1$) that equals either $\alpha_{*}-2\delta$ or $\alpha_{*}+2\delta$. By convexity,

Also, from (97), $M_{n}(\hat{\alpha}_{n})<M_{n}(\alpha_{\theta})$. Combining those, we find $M_{n}(\hat{\alpha}_{n})<M_{n}(\alpha)$, implying that $\hat{\alpha}_{n}$ is the minimizer of $M_{n}$ over the entire $[0,K_{\alpha}]$ w.p.a.1. In other words, for all $\epsilon$ w.p.a. 1,

To establish a connection with the three statements (i)-(iii) of the lemma, observe that $\overline{\phi}_{[0,\infty)}=M(\alpha_{*})$. Also, $\overline{\phi}_{[0,\infty)\setminus{\mathcal{S}}_{\delta}}=\min_{\alpha\in\mathcal{A}_{lu}}M(\alpha)$ (by convexity). With these, (i) corresponds directly to (94), (ii) to (98), and, (iii) to (96).

Proof of (92) and (93) : From the first statement of the lemma, the objective function $\mathcal{R}_{n}$ of the (AO) converges point-wise to $\mathcal{D}$. We will use this to show that the minimax value of $\mathcal{R}_{n}$ converges to the corresponding minimax of $\mathcal{D}$. The proof is based on a repeated use of Lemma B.1 below, about convergence of the infimum of a sequence of convex converging stochastic processes. This fact is essentially a consequence of what is known in the literature as convexity lemma, according to which point wise convergence of convex functions implies uniform convergence in compact subsets. Please refer to Section B.8 for the proof.

$M_{n}(x)\xrightarrow{P}M(x)$, for all $x>0$,

there exists $z>0$ such that $M(x)>\inf_{x>0}M(x)$ for all $x\geq z$.

Then, $\inf_{x>0}M_{n}(x)\xrightarrow{P}\inf_{x>0}F(x).$

1) Fix $\alpha\geq 0,\beta>0$, and, ${\tau_{h}}>0$. Consider

The functions $\{M_{n}\}$ are convex. Furthermore, $M_{n}^{\alpha,\beta,{\tau_{h}}}({\tau_{g}})\xrightarrow{P}M^{\alpha,\beta,{\tau_{h}}}({\tau_{g}})$ point wise in ${\tau_{g}}$. Next, we show that $M^{\alpha,\beta,{\tau_{h}}}$ is level-bounded, i.e. it satisfies condition (b) of Lemma B.1. In view of Lemma B.2, it suffices to show that $\lim_{{\tau_{g}}\rightarrow\infty}M^{\alpha,\beta,{\tau_{h}}}({\tau_{g}})=+\infty,$ or $\lim_{{\tau_{g}}\rightarrow\infty}\left(\frac{\beta}{2}+\delta\cdot\frac{L(\alpha,{\tau_{g}}/\beta)}{{\tau_{g}}}\right)>0.$ By assumption 2(c), $\lim_{{\tau_{g}}\rightarrow\infty}L(\alpha,{\tau_{g}}/\beta)=-L_{0}$. There is two cases to be considered. Either $L_{0}<\infty$, or else, Assumption 2(d) holds. Either way, $\lim_{{\tau_{g}}\rightarrow\infty}L(\alpha,{\tau_{g}}/\beta)/{\tau_{g}}=0$ and we are done. Now, we can apply Lemma B.1 to conclude that

2) Next, again for fixed $\alpha\geq 0,{\tau_{h}}>0$, consider (we use some abuse of notation here, with the purpose of not overloading notation)

The functions $\{M_{n}^{\alpha,{\tau_{h}}}\}$ are concave in $\beta$, as the point wise minima of concave functions. Furthermore, $M_{n}^{\alpha,{\tau_{h}}}(\beta)\xrightarrow{P}M^{\alpha,{\tau_{h}}}(\beta)$ point wise in $\beta>0$, by (101).

$\alpha>0$: For now and until further notice, restrict attention to the case $\alpha>0$. Also, consider first $\beta>0$. We show that $M^{\alpha,{\tau_{h}}}$ is level-bounded, i.e. it satisfies condition (b) of Lemma B.1. In view of Lemma B.2, it suffices to show that $\lim_{\beta\rightarrow+\infty}M^{\alpha,{\tau_{h}}}(\beta)=-\infty,$ or $\lim_{\beta\rightarrow+\infty}\inf_{{\tau_{g}}>0}M^{\alpha,\beta,{\tau_{h}}}({\tau_{g}})=-\infty.$ This condition is equivalent to the following

This follows by Assumption 2(a) when applied for $c=\alpha\beta/{\tau_{h}}$ and $\tau=\alpha{\lambda}/{\tau_{h}}$ (recall here that $\alpha>0$).