1.1 Motivation

Classical estimation theory studies problems in which the number of unknown parameters n is small compared to the number of observations m. In contrast, modern inference problems are typically high-dimensional, that is n can be of the same order as m. Examples are abundant in a wide range of signal processing and machine learning applications such as medical imaging, wireless communications, recommendation systems and so on. Classical tools and theories are not applicable in these modern inference problems. As such, over the last two decades or so, the study of high-dimensional estimation problems has received significant attention.

Perhaps the most well-studied setting is that of noisy linear observations (aka, linear regression). The literature on the topic is vast with remarkable contributions from the statistics, signal processing and machine learning communities. Several recent works focus on the linear asymptotic regime and derive sharp results on the inference performance of appropriate convex optimization methods, e.g., [Don06, Sto09, CRPW12, DMM11, Tro14, OT17, BM12, Sto13, OTH13, Kar13, BBEKY13, TOH15, DM16, TAH18, AG16, WMZTXH18, MM18, BKRS19, XMRH19, CM19]. These works show that, albeit challenging, sharp results are advantageous over loose order-wise bounds. Not only do they allow for accurate comparisons between different choices of the optimization parameters, but they also form the basis for establishing optimal such choices as well as fundamental performance limitations.

This paper takes this recent line of work a step further by demonstrating that results of this nature can be achieved in binary observation models. While we depart from the previously studied linear regression model, we remain faithful to the requirement and promise of sharp results. Binary models are popularly applicable in a wide range of signal-processing (e.g., highly quantized measurements) and machine learning (e.g., binary classification) problems. We derive sharp asymptotics for a rich class of convex optimization estimators, which includes least-squares, logistic regression and hinge-loss as special cases. Perhaps more interestingly, we use these results to derive fundamental performance limitations and design optimal loss functions that provably outperform existing choices.

In Section 1.2 we formally introduce the problem setup. The paper’s main contributions and organization are presented in Section 1.3. A detailed discussion of prior art follows in Section 1.4.

Notation. The symbols denote probability, expectation and variance. We use boldface notation for vectors. denotes the Euclidean norm of a vector v. We write for i = 1, 2, . . . , m. When writing we let the operator arg min return any one of the possible minimizers of f. For all is the cumulative distribution function of standard normal and Gaussian Q-function at x is defined as

1.2 Problem statement

Consider the problem of recovering from observations is a (possibly random) binary function. We study the performance of empirical-risk minimization (ERM) estimators that solve the following optimization problem for some convex loss function

Model. The binary observations are determined by a label function as follows:

where ’s are known measurement vectors with i.i.d. Gaussian entries; and is an unknown vector of coefficients. Some popular examples for the label function f include the following:

• (Noisy) Signed:

• Logistic:

• Probit:

Loss function. We study the recovery performance of estimates that are obtained by solving (1) for proper convex loss functions . Different choices for lead to popular specific estimators including the following:

Performance measure. We measure performance of the estimator by the value of its correlation to

Obviously, we seek estimates that maximize correlation. While correlation is the measure of primal interest, our results extend rather naturally to other parameter estimation metrics, such as square error, as well as prediction metrics, such as classification error.

Model assumptions. All our results are valid under the assumption that the measurement vectors have i.i.d. Gaussian entries.

Assumption 1 (Gaussian feature vectors). The vectors have entries i.i.d. standard normal.

Figure 1: Left: Comparison between analytical (solid lines) and empirical (markers) performance for least-squares (LS) and least-absolute deviations (LAD), along with optimal performance (dashed line) as predicted by the upper bound of Theorem 3.1 for the Signed model(). The red markers depict the empirical performance of the optimal loss function that attains the upper bound. Right: Illustrations of optimal loss functions for the Signed model for different values of according to Theorem 3.2.

Table 1: Analytical predictions and empirical performance of the optimal loss function for Signed model. Empirical results are averaged over 20 independent experiments for n = 128.

We further assume that . This assumption is without loss of generality since the norm of can always be absorbed in the link function. Indeed, letting , we can always write the measurements as . We make no further assumptions on the distribution of the true vector

1.3 Contributions and organization

This paper’s main contributions are summarized below.

• Sharp asymptotics: We show that the absolute value of correlation of to the true vector is sharply predicted bywhere the "effective noise" parameter can be explicitly computed by solving a system of three non-linear equations in three unknowns. We find that the system of equations (and thus, the value of ) depends on the loss function through its Moreau envelope function. Our prediction holds in the linear asymptotic regime in which . See Section 2.

• Fundamental limits: We establish fundamental limits on the performance of convex optimization-based estimators by computing an upper bound on the best possible correlation performance among all convex loss functions. We compute the upper bound by solving a certain nonlinear equation and we show that such a solution exists for all . See Section 3.1.

• Optimal performance: For certain models including Signed and Logistic, we find the loss functions that achieve the optimal performance, i.e., they attain the previously derived upper bound. See Section 3.2.

• Optimality of LS: For binary logistic and sigmoid models, we prove that the correlation performance of least-squares (LS) is at least as good as 0.9972 and 0.9804 times the optimal performance. See Section 4.1. • Numerical simulations: We specialize our results on general models and loss functions to popular instances, for which we provide simulation results that demonstrate the accuracy of the theoretical predictions. See Section 5.

Figure 1 contains a pictorial preview of our results described above for the special case of Signed measurements. First, Figure 1a depicts the correlation performance of LS and LAD estimators as a function of the aspect ratio . Both theoretical predictions and numerical results are shown; note the close match for even small dimensions. Second, the dashed line on the same figure shows the upper bound derived in this paper – there is no convex loss function that results in correlation exceeding this line. Third, we show that the upper bound can be achieved by the loss functions depicted in Figure 1b for several values of (1) for this choice of loss functions using gradient descent and numerically evaluate the achieved correlation performance. The recorded values are compared in Table 1 to the corresponding values of the upper bound; again, note the close agreement between the values as predicted by the findings of this paper. We present corresponding results for the Logistic and Probit models in Section 5 and for the Noisy-signed model in Appendix E.

1.4 Related work

Over the past two decades there has been a long list of works that derive statistical guarantees for high-dimensional estimation problems. Many of these are concerned with convex optimization-based inference methods. Our work is most closely related to the following three lines of research.

(a) Sharp asymptotics for linear measurements. Most of the results in the literature of high-dimensional statistics are order-wise in nature. Sharp asymptotic predictions have only more recently appeared in the literature for the case of noisy linear measurements with Gaussian measurement vectors. There are by now three different approaches that have been used towards asymptotic analysis of convex regularized estimators: i) the one that is based on the approximate message passing (AMP) algorithm and its state-evolution analysis, e.g., [DMM09, DMM11, BM11, BM12, DM16, BKRS19, MMBii) the one that is based on Gaussian process (GP) inequalities, specifically the convex Gaussian min-max Theorem (CGMT) e.g., [Sto13, OTH13, TOH15, TAH18, TXH18, MM18]. iii) the “leave-one-out" approach [Kar13, EK15]. The three approaches are quite different to each other and each comes with its unique distinguishing features and disadvantages. A detailed comparison is beyond our scope.

Our results in Theorems 3.1 and 3.2 for achieving the best performance across all loss functions is complementary to [BBEKY13, Theorem 1] and [AG16] in which the authors also proposed a method for deriving optimal loss function and measuring its performance, albeit for linear models. Instead, we study binary models. The optimality of regularization for linear measurements, is recently studied in [CM19].

In terms of analysis, we follow the GP approach and build upon the CGMT. Since the previous works are concerned with linear measurements, they consider estimators that solve minimization problems of the form

Specifically, the loss function penalizes the residual. In this paper, we show that the CGMT is applicable to optimization problems in the form of (1). For our case of binary observations, (1) is more general than (4). To see this, note that for and popular symmetric loss functions , e.g. least-squares (LS), (1) results in (4) by choosing in the former. Moreover, (1) includes several other popular loss functions such as the logistic loss and the hinge-loss which cannot be expressed by (4).

(b) One-bit compressed sensing. Our work naturally relates to the literature on one-bit compressed sensing (CS) [BB08]. The vast majority of performance guarantees for one-bit CS are order-wise in nature, e.g., [JLBB13, PV13, PV12, PV16, Gen17, XJ18]. To the best of our knowledge, the only existing sharp results are presented in [TAH15] for Gaussian measurement vectors, which studies the asymptotic performance of regularized LS. Our work can be seen as a direct extension of [TAH15] to loss functions beyond least-squares; see Section 4.1 for details.

Similar to the generality of our paper, [Gen17] also studies the high-dimensional performance of general loss functions. However, in contrast to our results, their performance bounds are loose (order-wise); as such, they are not informative about the question of optimal performance which we also address here.

(c) Classification in high-dimensions. In [CS18, SC19] the authors study the high-dimensional performance of maximum-likelihood (ML) estimation for the logistic model. The ML estimator is a special case of (1) and we consider general binary models. Also, their analysis is based on the AMP. The asymptotics of logistic loss under different classification models has also been recently studied in [MLC19]. In yet another closely related recent work [SAH19], the authors extend the results of [SC19] to regularized ML by using the CGMT. Instead, we present results for general loss functions and for general measurement models. Importantly, we also study performance bounds and optimal loss functions.

Finally, we remark on the following closely related parallel works. While this paper was being under review, the CGMT has been applied by [MRSY19] and [DKT19] to determine the generalization performance of max-margin linear classifiers in a binary classification setting. In essence, these results are complementary to the results of our paper in the following sense. Consider a binary classification setting under the logistic model and Gaussian regressors. As discussed in Section 4.2, the optimal set of (1) is bounded with probability approaching one if and only if , for appropriate threshold determined for first time in [CS18] (see also Figure 2a). Our results hold in this regime. In contrast, the papers [DKT19] and [MRSY19] study the regime . Also a preliminary version of the results of this paper was published in [TPT19].

2.1 Definitions

Moreau envelopes. Before stating the first result we need a definition. We write

for the Moreau envelope function of the loss with parameter . The minimizer (which is unique by strong convexity) is known as the with parameter and we denote it as . A useful property of the Moreau envelope function is that it is continuously differentiable with respect to both ]. We denote these derivatives as follows

A system of equations. As we show shortly, the asymptotic performance of the optimization in (1) is tightly connected to the solution of a certain system of nonlinear equations, which we introduce here. Specifically, define random variables G, S and Y as follows:

and consider the following system of non-linear equations in three unknowns

The expectations are with respect to the randomness of the random variables G, S and Y . We remark that the equations are well defined even if the loss function is not differentiable. In Section A we summarize some well-known properties of the Moreau Envelope function and use them to simplify (6) for differentiable loss functions.

2.2 Asymptotic prediction

We are now ready to state our first main result.

Theorem 2.1 (Sharp asymptotics). Let Assumption 1 hold and assume such that the set of minimizers in (1) is bounded and the system of equations (6) has a unique solution , such that . Let . Then, in the limit of , it holds with probability one that

Moreover,

Theorem 2.1 holds for general loss functions. In Section 4 we specialize the result to specific popular choices and also present numerical simulations that confirm the validity of the predictions (see Figures. 1a–3a and 7a–7b). Before that, we include a few remarks on the conditions, interpretation and implications of the theorem. The proof is deferred to Appendix B and uses the convex Gaussian min-max theorem (CGMT) [TOH15, TAH18].

Remark 1 (The role of According to (7), the prediction for the limiting behavior of the correlation value is given in terms of an effective noise parameter are unique solutions of (6). While the correlation value is fully determined by the ratio of , their individual role is clarified in (8). Specifically, according to (8), a biased estimate of the true represents exactly that bias term. In other words, solving (1) returns an estimator that is close to a –scaled version of are scaled appropriately, the of their difference converges to

Remark 2 (Why The theorem requires that (equivalently, m > n). Here, we show that this condition is necessary for the equations (6) to have a bounded solution. To see this, take squares in both sides of (6c) and divide by (6b), to find that

The inequality follows by applying Cauchy-Schwarz and using the fact that

Remark 3 (On the existence of a solution to (6)). While is a necessary condition for the equations in (6) to have a solution, it is not sufficient in general. This depends on the specific choice of the loss function. For example, in Section 4.1, we show that for the squared loss , the equations have a unique solution iff . On the other hand, for logistic-loss and hinge-loss, it is argued in Section 4.2 that there exists a threshold value such that the set of minimizers in (1) is unbounded if . In this case, Theorem 2.1 does not hold. We conjecture that for these choices of loss, the equations (6) are solvable iff . Justifying this conjecture and further studying more general sufficient and necessary conditions under which the equations (6) admit a solution is left to future work. However, in what follows, given such a solution, we prove that it is unique for a wide class of convex-loss functions of interest.

Remark 4 (On the uniqueness of solution to (6)). We show that if the system of equations in (6) has a solution, then it is unique provided that is strictly convex, continuously differentiable and its derivative satisfies . For instance, this class includes the square, the logistic and the exponential losses. However, it excludes non-differentiable functions such as the LAD and hinge-loss. We believe that the differentiability assumption can be relaxed without major modification in our proof, but we leave this for future work. Our result is summarized in Proposition 2.1 below.

Proposition 2.1. Assume that the loss function has the following properties: (i) it is proper strictly convex; (ii) it is continuously differentiable and its derivative is such that . Further assume that the (possibly random) link function f is such that has strictly positive density on the real line. The following statement is true. For any , if the system of equations in (6) has a bounded solution, then it is unique.

The detailed proof of Proposition 2.1 is deferred to Appendix B.5. Here, we highlight some key ideas. The CGMT relates –in a rather natural way– the original ERM optimization (1) to the following deterministic min-max optimization on four variables

In Appendix B.4, we show that the optimization above is convex-concave for any lower semi-continuous, proper, convex function . Moreover, it is shown that one arrives at the system of equations in (6) by simplifying the first-order optimality conditions of the min-max optimization in (9). This connection is key to the proof of Proposition 2.1. Indeed, we prove uniqueness of solution (if such a solution exists) to (6), by proving instead that the function above is (jointly) strictly convex in and strictly concave in , provided that satisfies the conditions of the proposition. Next, let us briefly discuss how strict convex-concavity of (9) can be shown. For concreteness, we only discuss strict convexity here; the ideas are similar for strict concavity. At the heart of the proof of strict convexity of F is understanding the properties of the defined as follows:

Specifically, we prove in Proposition A.7 in Appendix A.6 that if is strictly convex, differentiable and does not attain its minimum at is strictly convex in and strictly concave in . It is worth noting that the Moreau envelope function for fixed g, s and y = f(s) is not necessarily strictly convex. Interestingly, we show that the expected Moreau envelope has this desired feature. We refer the reader to Appendices A.6 and B.5 for more details.

3.1 Fundamental limitations

In this section, we establish fundamental limits on the performance of (1) by deriving an upper bound on the absolute value of correlation that holds for all choices of loss functions satisfying Theorem 2.1. The result builds on the prediction of Theorem 2.1. In view of (7) upper bounding correlation is equivalent to lower bounding the effective noise parameter below derives such a lower bound.

function . Then, the Fisher information of H is defined as follows (e.g. [Bar84, Sec. 2]):

Theorem 3.1 (Best achievable performance). Let the assumptions and notation of Theorem 2.1 hold and recall the definition of random variables G, S and Y in (5). For , define a new random variable and the function as follows,

Further define as follows,

Then, for it holds that

The theorem above establishes an upper bound on the best possible correlation performance among all convex loss functions. In Section 3.2, we show that this bound is often tight, i.e. there exists a loss function that achieves the specified best possible performance.

Remark 5. Theorem 3.1 complements the results of [BBEKY13], [DM16, Lem. 3.4] and [TAH18, Rem. 5.3.3] in which they consider only linear measurements. In particular, Theorem 3.1 shows that it is possible to achieve results of this nature for the more challenging setting of binary observations considered here.

Proof of Theorem 3.1. Fix a loss function and let be a solution to (6), which by assumptions of Theorem 2.1 is unique. The first important observation is that the error of a loss function is unique up to a multiplicative constant. To see this, consider an arbitrary loss function and let be a minimizer in (1). Now consider (1) with the following loss function instead, for some arbitrary constants

It is not hard to see that is the minimizer for has the same correlation value with as , showing that the two loss functions perform the same. With this observation in mind, consider the function . Then, notice that

Using this relation in (6) and setting , the system of equations in (6) can be equivalently rewritten in the following convenient form,

Next, we show how to use (12) to derive an equivalent system of equations based on . Starting with (12c) we have

where in the last step we used

Therefore we have by (14) that

This combined with (12c) gives Second, multiplying (12c) with and adding it to (12a) yields that,

Putting these together we conclude with the following system of equations which is equivalent to (12),

Note that for exists everywhere. This is because for all and is continuously differentiable. Combining (17a) and (17c) we derive the following equation which holds for

By Cauchy-Schwartz inequality we have that

Using the fact that (by integration by parts), and (17b), the right hand side of (18) is equal to

Therefore, we have concluded with the following inequality for

which holds for all . In particular, (19) holds for the following choice of values for

(The choice above is motivated by the result of Section 3.2; see Theorem 3.2). Rewriting (19) with the chosen values of yields the following inequality,

where in the right-hand side above, we recognize the function defined in the theorem.

Next, we use (20) to show that yields a lower bound on the achievable value of the sake of contradiction, assume that . By the above, . Moreover, by the definition of we must have that Since and is a continuous function we conclude that for some it holds that . Therefore for we have , which contradicts the definition of . This proves that , as desired.

In order to complete the proof, it remains to show that the equation admits a solution for all . For this purpose, we use the continuous mapping theorem and the fact that fisher information is a continuous function [Cos85]. Recall that for two independent and non-constant random variables it holds that I(X + Y ) < I(X) [Bar84, Eq. 2.18]. Since G and SY are independent random variables we find that which implies that takes finite values for all values of . Therefore,

Note that , which further yields that for all . Finally since is a continuous function, we deduce that range of is [0, 1), implying the existence of a solution to (10) for all

A useful closed-form bound on the best achievable performance: In general, determining requires computing the Fisher information of the random variable for . If the probability distribution of SY is continuously differentiable (e.g., logistic model; see Section C.2), then we obtain the following simplified bound.

Corollary 3.1 (Closed-form lower bound on Let be the probability distribution of SY . If is differentiable for all

The proof of the corollary reveals that (21) holds with equality when SY is Gaussian. In Section C.2, we compute for the Logistic and the Probit models and numerically show that it is close to the density of a Gaussian random variable. Consequently, the lower bound of Corollary 3.1 is almost exact when measurements are obtained according to the Logistic and Probit models; see Figure 5 in the appendix.

Proof of Corollary 3.1. Based on Theorem 3.1, the following equation holds for

or equivalently, by rewriting the right-hand side,

Define the following function

The function h is increasing in the region According to Stam’s inequality [Bla65], for two independent random variables X and Y with continuously differentiable it holds that

where equality is achieved if and only if X and Y are independent Gaussian random variables. Therefore since by assumption is differentiable on the real line, Stam’s inequality yields

Next we prove that for all , both sides of (23) are in the region . First, we prove that By Cramer-Rao bound (e.g. see [Bar84, Eq. 2.15]) for Fisher information of a random variable X, we have that . Also for the random variable , we know that Var

Using the relation , one can check that the following inequality holds :

Therefore from (24) and (25) we derive that . Furthermore by the inequality in (23) and the definition of it directly follows that for all

Finally noting that is increasing in , combined with (23) we have

which after using the relation and further simplification yields the inequality in the statement of the corollary.

3.2 On the optimal loss function

It is natural to ask whether there exists a loss function that attains the bound of Theorem 3.1. If such a loss function exists, then we say it is optimal in the sense that it maximizes the correlation performance among all convex loss functions in (1).

Our next theorem derives a candidate for the optimal loss function, which we denote . Before stating the result, we provide some intuition about the proof which builds on Theorem 3.1. The critical observation in the proof of Theorem 3.1 is that the effective noise of is minimized (i.e., it attains the value ) if the Cauchy-Schwartz inequality in (18) holds with equality. Hence, we seek so that for some

By choosing , integrating and ignoring constants irrelevant to the minimization of the loss function, the previous condition is equivalent to the following It turns out that this condition can be “inverted" to yield the following explicit formula for (see Proposition D.1) Of course, one has to properly choose and to make sure that this function satisfies the system of equations in (17) with . The correct choice is specified in the theorem below.

Theorem 3.2 (Optimal loss function). Recall the definition of in (10). Define the random variable denote its density. Consider the following loss function

where

If defined as in (27) is convex and the equation has a unique solution, then

In general, there is no guarantee that the function as defined in (27) is convex. However, if this is the case, the theorem above guarantees that it is optimal condition for to be convex, is provided in Section D.2. Importantly, in Section D.2.1 we show that this condition holds for observations following the Signed model. Thus, for this case the resulting function is convex. Although we do not prove the convexity of optimal loss function for the Logistic and Probit models, our numerical results (e.g., see Figure 2b) suggest that this is the case. Concretely, we conjecture that the loss function is convex for Logistic and Probit models, and therefore by Theorem 3.2 its performance is optimal.

Proof of Theorem 3.2. We will show that the triplet is a solution to the equations (6) for chosen as in (27). Using Proposition A.2 in the appendix we rewrite using the Fenchel-Legendre conjugate as follows :

where , and for a function f, its Fenchel-Legendre conjugate is defined as:

Next we use the fact that for any proper, closed and convex function f it holds that, [Roc70, theorem 12.2]. Therefore noting that is a convex function (see the proof of Lemma D.1 in the appendix), combined with (29) yields that

Additionally using Proposition A.2 we find that to :

Thus, by differentiation, we find that satisfies (26) with

Next, we establish the desired by directly substituting (31) into the system of equations in (17). First, using the values of and in (28), as well as, the fact that , we have the following chain of equations:

This shows (6b). Second, using again the specified values of , a similar calculation yields

Recall from (15) that E

with (33) yields (6c). Finally, we use again (31) and the specified values of to find that

But, using (15) it holds that

This combined with (35) and (33) shows that E

completes the proof of the theorem.

4.1 Least-Squares

By choosing , we obtain the standard least-squares estimate. To see this, note that since , it holds for all is minimizing the sum of squares of the residuals:

For this choice of a loss function, we can solve the equations in (6) in closed form. Furthermore, the equations have a (unique, bounded) solution for any provided that E[SY ] > 0. The final result is summarized in the corollary below. See Section F.1 for the proof.

Corollary 4.1 (Least-squares). Let Assumption 1 hold and . For the label function assume that E[SY ] > 0 in the notation of (5). Let be as in (36). Then, in the limit of , Equations (7) and (8) hold with probability one with given as follows:

Corollary 4.1 appears in [TAH15] (see also [Bri82, PV16, Gen17] and Section F for an interpretation of the result). However, these previous works obtain results that are limited to least-squares loss. In contrast, our results are general and LS prediction is obtained as a simple corollary of our general Theorem 2.1. Moreover, our study of fundamental limits allows us to quantify the sub-optimality gap of least-square (LS) as follows.

On the optimality of LS. On the one hand, Corollary 4.1 derives an explicit formula for the effective noise variance of LS in terms of E[Y S] and . On the other hand, Corollary 3.1 provides an explicit lower bound on the optimal value in terms of . Combining the two, we conclude that

In terms of correlation,

where the first inequality follows from the fact that

Another interesting consequence of combining Corollary 4.1 with Corollary 3.1 is that LS would be optimal if SY were a a Gaussian random variable. To see this, recall from Corollary 3.1 that if SY is Gaussian then:

But, for SY Gaussian, we can explicitly compute I(SY ) = 1/Var[SY ], which leads to

The right hand side is exactly . Therefore the optimal performance is achieved by the square-loss function if SY is a Gaussian random variable. In particular, the result described above applies to the following binary Gaussian-mixtures model:

For this model, using the method introduced above (with appropriate modifications), we prove in [TPT20] that LS is optimal for among all choices of convex loss functions yielding a unique solution to the equations.

4.2 Logistic & Hinge loss

Theorem 2.1 only holds in regimes for which the set of minimizers of (1) is bounded. As we show here, this is not always the case. Specifically, consider non-negative loss functions with the property . For example, the hinge, exponential and logistic loss functions all satisfy this property. Now, we show that for such loss functions the set of minimizers is unbounded if for some appropriate . First, note that the set of minimizers is unbounded if the following condition holds:

Indeed, if (39) holds then , attains zero cost in (1); thus, it is optimal and the set of minimizers is unbounded. To proceed, we rely on a recent result by Candes and Sur [CS18] who prove that (39) holds iff

where G, S and Y are random variables as in (5) and . We highlight that Logistic and Hinge losses give unbounded solutions in the Noisy-Signed model with , since the condition (39) holds for . However their performances are comparable to the optimal performance in both Logistic and Probit models (see Figures 2a and 3a).

In this section, we present numerical simulations that validate the predictions of Theorems 2.1, 3.1 and 3.2. We use the following three popular models as our case study: Signed, Logistic and Probit. We generate random measurements according to (2) and Assumption 1. Without loss of generality (due to rotational invariance of the Gaussian measure) we set . We then obtain estimates of by numerically solving (1) and measure performance by the correlation value . Throughout the experiments, we set

Figure 2: Left: Comparison between analytical and empirical results for the performance of LS, Logistic loss, Hinge-loss and optimal loss function for Logistic model. The vertical dashed line represents , as evaluated by (40). Right: Illustrations of optimal loss functions for different values of , derived according to Theorem 3.2 for Logistic model. In order to signify the similarity of optimal loss function to the LS loss, the optimal loss functions (hardly visible) are scaled such that

n = 128 and the recorded values of correlation are averages over 25 independent realizations. For each label function we first provide plots that compare results of Monte Carlo simulations to the asymptotic predictions for loss functions discussed in Section 4, as well as, to the optimal performance of Theorem 3.1. We next present numerical results on optimal loss functions. In order to empirically derive the correlation of optimal loss function, we run gradient descent-based optimization with 1000 iterations. As a general comment, we note that despite being asymptotic, our predictions appear accurate even for relatively small problem dimensions. For the analytical predictions we apply Theorem 2.1. In particular for solving the system of non-linear equations in (1), we empirically observe (see also [TAH18, SAH19] for similar observation) that if a solution exists, then it can be efficiently found by the following fixed-point iteration method. Let be such that (1) is equivalent to v = F(v). With this notation, we initialize and for repeat the iterations until convergence.

Logistic model. For the logistic model, comparison between the predicted values and the numerical results is illustrated in Figure 2a. Results are shown for LS, logistic and hinge loss functions. Note that minimizing the logistic loss corresponds to the maximum-likelihood estimator (MLE) for logistic model. An interesting observation in Figure 2a is that in the high-dimensional setting (finite ) LS has comparable (if not slightly better) performance to MLE. Additionally we observe that in this model, performance of LS is almost the same as the best possible performance derived according to Theorem 3.1. This confirms the analytical conclusion of Section 4.1. The comparison between the optimal loss function as in Theorem 3.2 and other loss functions is illustrated in Figure 2b. We note the obvious similarity between the shapes of optimal loss functions and LS which further explains the similarity between their performance.

Probit model. Theoretical predictions for the performance of hinge and LS loss functions are compared with the empirical results and optimal performance of Theorem 3.1 in Figure 3a. Similar to the Logistic model, in this model LS also outperforms hinge-loss and its performance resembles the performance of optimal loss function derived according to Theorem 3.2. Figure 3b illustrates the shapes of LS, hinge-loss and the optimal loss functions for the Probit model. The obvious similarity between the shape of LS and optimal loss functions for all values of explains the close similarity of their performance.

Additionally by comparing the LS performance for the three models in Figures 1a, 2a and 3a, it is clear that higher (resp., lower) correlation values are achieved for signed (resp., logistic) measurements. This behavior is indeed predicted by Corollary 4.1: correlation performance is higher for higher values of be shown that for the signed, probit and logistic models we have , respectively.

Figure 3: Left: Comparison between analytical and empirical results for the performance of LS, Hinge-loss and optimal loss function for Probit model. The vertical dashed line represents , as evaluated by (40). Right: Illustrations of optimal loss functions for different values of derived according to Theorem 3.2 for Probit model. In order to signify the similarity of optimal loss function to the LS loss, the optimal loss functions (hardly visible) are scaled such that

Optimal loss function. By putting together Theorems 3.1 and 3.2, we obtain a method on deriving the

optimal loss function. This requires the following steps.

by solving (10).

2. Compute the density of according to (27).

Note that computing needs the density function of the random variable . In principle can be calculated as the convolution of the Gaussian density with the pdf . Moreover, it follows from the recipe above that the optimal loss function depends on in general. This is because itself depends on

This paper derives sharp asymptotic performance guarantees for a wide class of convex optimization based estimators for recovering a signal from binary observation models. We further provide a theoretical upper bound on the best achievable performance among all convex loss functions. Using this, we develop a procedure for computing the optimal loss function. Finally, we provide numerical studies that show tight agreement with our theoretical results. Interesting future directions include studying the generalized linear measurement model beyond binary observations and characterizing the optimal loss function for such general models.

This work was supported by NSF Grants CCF-1755808 and CCF-1909320 and an Academic Senate Research Grant from UCSB.

[AG16] Madhu Advani and Surya Ganguli. Statistical mechanics of optimal convex inference in high dimensions. Physical Review X, 6(3):031034, 2016.

[Bar84] Andrew R Barron. Monotonic central limit theorem for densities. Department of Statistics, Stanford University, California, Tech. Rep, 50, 1984.

[BB08] Petros T Boufounos and Richard G Baraniuk. 1-bit compressive sensing. In 2008 42nd Annual Conference on Information Sciences and Systems (CISS), pages 16–21. IEEE, 2008.

[BBEKY13] Derek Bean, Peter J Bickel, Noureddine El Karoui, and Bin Yu. Optimal m-estimation in high-dimensional regression. Proceedings of the National Academy of Sciences, 110(36):14563–14568, 2013.

[BKRS19] Zhiqi Bu, Jason Klusowski, Cynthia Rush, and Weijie Su. Algorithmic analysis and statistical estimation of slope via approximate message passing. In Advances in Neural Information Processing Systems, pages 9361–9371, 2019.

[Bla65] N. Blachman. The convolution inequality for entropy powers. IEEE Transactions on Information Theory, 11(2):267–271, 1965.

[BM11] Mohsen Bayati and Andrea Montanari. The dynamics of message passing on dense graphs, with applications to compressed sensing. Information Theory, IEEE Transactions on, 57(2):764–785, 2011.

[BM12] Mohsen Bayati and Andrea Montanari. The lasso risk for gaussian matrices. Information Theory, IEEE Transactions on, 58(4):1997–2017, 2012.

[Bri82] David R Brillinger. A generalized linear model with" gaussian" regressor variables. A Festschrift For Erich L. Lehmann, page 97, 1982.

[BV09] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2009.

[CM19] Michael Celentano and Andrea Montanari. Fundamental barriers to high-dimensional regression with convex penalties. arXiv preprint arXiv:1903.10603, 2019.

[Cos85] Max H. M. Costa. A new entropy power inequality. IEEE Trans. Information Theory, 31:751–760, 1985.

[CRPW12] Venkat Chandrasekaran, Benjamin Recht, Pablo A Parrilo, and Alan S Willsky. The convex geometry of linear inverse problems. Foundations of Computational Mathematics, 12(6):805–849, 2012.

[CS18] Emmanuel J Candès and Pragya Sur. The phase transition for the existence of the maximum likelihood estimate in high-dimensional logistic regression. arXiv preprint arXiv:1804.09753, 2018.

[DKT19] Zeyu Deng, Abla Kammoun, and Christos Thrampoulidis. A model of double descent for high-dimensional binary linear classification. arXiv preprint arXiv:1911.05822, 2019.

[DM16] David Donoho and Andrea Montanari. High dimensional robust m-estimation: Asymptotic variance via approximate message passing. Probability Theory and Related Fields, 166(3-4):935– 969, 2016.

[DMM09] David L Donoho, Arian Maleki, and Andrea Montanari. Message-passing algorithms for compressed sensing. Proceedings of the National Academy of Sciences, 106(45):18914–18919, 2009.

[DMM11] David L Donoho, Arian Maleki, and Andrea Montanari. The noise-sensitivity phase transition in compressed sensing. Information Theory, IEEE Transactions on, 57(10):6920–6941, 2011.

[Don06] David L Donoho. Compressed sensing. Information Theory, IEEE Transactions on, 52(4):1289– 1306, 2006.

[DTL18] Oussama Dhifallah, Christos Thrampoulidis, and Yue M Lu. Phase retrieval via polytope optimization: Geometry, phase transitions, and new algorithms. arXiv preprint arXiv:1805.09555, 2018.

[EK15] Noureddine El Karoui. On the impact of predictor geometry on the performance on high-dimensional ridge-regularized generalized robust regression estimators. 2015.

[Gen17] Martin Genzel. High-dimensional estimation of structured signals from non-linear observations with general convex loss functions. IEEE Transactions on Information Theory, 63(3):1601–1619, 2017.

[GJ17] Martin Genzel and Peter Jung. Recovering structured data from superimposed non-linear measurements. arXiv preprint arXiv:1708.07451, 2017.

[GMW18] Larry Goldstein, Stanislav Minsker, and Xiaohan Wei. Structured signal recovery from non-linear and heavy-tailed measurements. IEEE Transactions on Information Theory, 64(8):5513–5530, 2018.

[Gor88] Yehoram Gordon. On Milman’s inequality and random subspaces which escape through a mesh in . Springer, 1988.

[JLBB13] Laurent Jacques, Jason N Laska, Petros T Boufounos, and Richard G Baraniuk. Robust 1-bit compressive sensing via binary stable embeddings of sparse vectors. IEEE Transactions on Information Theory, 59(4):2082–2102, 2013.

[Kar13] Noureddine El Karoui. Asymptotic behavior of unregularized and ridge-regularized high-dimensional robust regression estimators: rigorous results. arXiv preprint arXiv:1311.2445, 2013.

[MLC19] Xiaoyi Mai, Zhenyu Liao, and Romain Couillet. A large scale analysis of logistic regression: Asymptotic performance and new insights. In ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3357–3361. IEEE, 2019.

[MM18] Léo Miolane and Andrea Montanari. The distribution of the lasso: Uniform control over sparse balls and adaptive parameter tuning. arXiv preprint arXiv:1811.01212, 2018.

[MMBAli Mousavi, Arian Maleki, Richard G Baraniuk, et al. Consistent parameter estimation for lasso and approximate message passing. The Annals of Statistics, 46(1):119–148, 2018.

[MRSY19] Andrea Montanari, Feng Ruan, Youngtak Sohn, and Jun Yan. The generalization error of max-margin linear classifiers: High-dimensional asymptotics in the overparametrized regime. arXiv preprint arXiv:1911.01544, 2019.

[OT17] Samet Oymak and Joel A Tropp. Universality laws for randomized dimension reduction, with applications. Information and Inference: A Journal of the IMA, 7(3):337–446, 2017.

[OTH13] Samet Oymak, Christos Thrampoulidis, and Babak Hassibi. The squared-error of generalized lasso: A precise analysis. arXiv preprint arXiv:1311.0830, 2013.

[PV12] Yaniv Plan and Roman Vershynin. Robust 1-bit compressed sensing and sparse logistic regression: A convex programming approach. IEEE Transactions on Information Theory, 59(1):482–494, 2012.

[PV13] Yaniv Plan and Roman Vershynin. One-bit compressed sensing by linear programming. Communications on Pure and Applied Mathematics, 66(8):1275–1297, 2013.

[PV16] Yaniv Plan and Roman Vershynin. The generalized lasso with non-linear observations. IEEE Transactions on information theory, 62(3):1528–1537, 2016.

[Roc70] R Tyrrell Rockafellar. Convex analysis princeton university press. Princeton, NJ, 1970.

[RW09] R Tyrrell Rockafellar and Roger J-B Wets. Variational analysis, volume 317. Springer Science & Business Media, 2009.

[SAH19] Fariborz Salehi, Ehsan Abbasi, and Babak Hassibi. The impact of regularization on high-dimensional logistic regression. arXiv preprint arXiv:1906.03761, 2019.

[SC19] Pragya Sur and Emmanuel J Candès. A modern maximum-likelihood theory for high-dimensional logistic regression. Proceedings of the National Academy of Sciences, page 201810420, 2019.

[Sto09] Mihailo Stojnic. Various thresholds for -optimization in compressed sensing. arXiv preprint arXiv:0907.3666, 2009.

[Sto13] Mihailo Stojnic. A framework to characterize performance of lasso algorithms. arXiv preprint arXiv:1303.7291, 2013.

[TAH15] Christos Thrampoulidis, Ehsan Abbasi, and Babak Hassibi. Lasso with non-linear measurements is equivalent to one with linear measurements. In Advances in Neural Information Processing Systems, pages 3420–3428, 2015.

[TAH18] Christos Thrampoulidis, Ehsan Abbasi, and Babak Hassibi. Precise error analysis of regularized m-estimators in high dimensions. IEEE Transactions on Information Theory, 64(8):5592–5628, 2018.

[TOH15] Christos Thrampoulidis, Samet Oymak, and Babak Hassibi. Regularized linear regression: A precise analysis of the estimation error. In Proceedings of The 28th Conference on Learning Theory, pages 1683–1709, 2015.

[TPT19] Hossein Taheri, Ramtin Pedarsani, and Christos Thrampoulidis. Sharp guarantees for solving random equations with one-bit information. In 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 765–772. IEEE, 2019.

[TPT20] Hossein Taheri, Ramtin Pedarsani, and Christos Thrampoulidis. Optimality of least-squares for classification in gaussian-mixture models. Submitted to IEEE International Symposium on Information Theory (ISIT), 2020.

[TR18] Christos Thrampoulidis and Ankit Singh Rawat. The generalized lasso for sub-gaussian measurements with dithered quantization. arXiv preprint arXiv:1807.06976, 2018.

[Tro14] Joel A Tropp. Convex recovery of a structured signal from independent random linear measurements. arXiv preprint arXiv:1405.1102, 2014.

[TXH18] Christos Thrampoulidis, Weiyu Xu, and Babak Hassibi. Symbol error rate performance of boxrelaxation decoders in massive mimo. IEEE Transactions on Signal Processing, 66(13):3377–3392, 2018.

[WMZHaolei Weng, Arian Maleki, Le Zheng, et al. Overcoming the limitations of phase transition by higher order analysis of regularization techniques. The Annals of Statistics, 46(6A):3099–3129, 2018.

[XJ18] Chunlei Xu and Laurent Jacques. Quantized compressive sensing with rip matrices: The benefit of dithering. arXiv preprint arXiv:1801.05870, 2018.

[XMRH19] Ji Xu, Arian Maleki, Kamiar Rahnama Rad, and Daniel Hsu. Consistent risk estimation in high-dimensional linear regression. arXiv preprint arXiv:1902.01753, 2019.

A.1 Derivatives

Recall the definition of the Moreau envelope and proximal operator of a function

Proposition A.1 (Basic properties of be lower semi-continuous (lsc), proper and convex. The following statements hold for any

(a) The proximal operator is unique and continuous. In fact,

(b) The value is finite and depends continuously on , with for all x as

(c) The Moreau envelope function is differentiable with respect to both arguments. Specifically, for all the following properties are true:

If in addition is differentiable and denotes its derivative, then

Replacing the above relations for derivative of , we can write the equations in terms of the proximal operator. If is differentiable then the Equations (6) can be equivalently written as follows:

Finally, if is two times differentiable then applying integration by parts in Equation (12c) results in the following reformulation of (6c):

A.3 Examples of proximal operators

the proximal operator admits a simple expression, as follows:

where

is the standard soft-thresholding function.

Hinge-Loss. When , the proximal operator can be expressed in terms of the soft-thresholding function as follows:

A.4 Fenchel-Legendre conjugate representation

For a function , its Fenchel-Legendre conjugate, is defined as :

The following proposition relates Moreau Envelope of a function to its Fenchel-Legendre conjugate.

and a function h, we have:

Proof.

A.5 Convexity of the Moreau envelope

Lemma A.1. The function defined as follows

is jointly convex in its arguments.

Proof. Note that the function is jointly convex in (x, v). Thus its perspective function

is jointly convex in , Sec. 2.3.3], which completes the proof.

Proposition A.3. (a) [Prop. 2.22[RW09]] Let f(x, y) be jointly convex in its arguments. Then, the function is convex.

(b) [Sec. 3.2.3[BV09]] Suppose is a set of concave functions, with an index set. Then the function is concave.

be a lsc, proper, convex function. Then,

Proof. Recall that

where for compactness, we let denote the triplet and . With this notation, we may write

For the first equality above we recalled the definition of in (50) and the inequality right after follows from Lemma A.1 and convexity of . Thus, the function G is jointly convex in its arguments. Using this fact, as well as (51), and applying Proposition A.3(a) completes the proof.

A.6 The expected Moreau-envelope (EME) function and its properties

The performance of the ERM estimator (1) is governed by the system of equations (6) in which the Moreau envelope function of the loss function plays a central role. More precisely, as already hinted by (6) and will become clear in Appendix B, what governs the behavior is the function

which we call the expected Moreau envelope (EME). Recall here that Y = f(S). Hence, the EME is the key summary parameter that captures the role of both the loss function and of the link function on the statistical performance of (1).

In this section, we study several favorable properties of the EME. In (52) the expectation is over

. We first study the EME under more general distribution assumptions in Sections A.6.1–A.6.3 and we then specialize our results to Gaussian random variables G and S in Section A.6.4.

A.6.1 Derivatives

Proposition A.4. Let be a lsc, proper and convex function. Further let X, Z be independent random variables with bounded second moments . Then the expected Moreau envelope function , is differentiable with respect to both c and and the derivatives are given as follows:

Proof. The proof is an application of the Dominated Convergence Theorem (DCT). First, by Proposition A.1(b), for every and any the function takes a finite value. Second, by Proposition A.1(c) is continuously differentiable with respect to both

From this, note that Cauchy-Schwarz inequality gives

Therefore, the remaining condition to check so that DCT can be applied is that the term above is integrable. To begin with, we can easily bound A as: Next, by non-expansiveness (Lipschitz property) of the proximal operator [RW09, Prop. 12.19] we have that Putting together, we find that

We consider two cases. First, for fixed and any compact interval I, we have that

Similarly, for fixed c and any compact interval J on the positive real line, we have that

where we also used boundedness of the proximal operator (cf. Proposition A.1(a)). This completes the proof.

A.6.2 Strict convexity

We study convexity properties of the

for a lsc, proper, convex function and independent random variables X and Z with positive densities. Here and onwards, we let denote a triplet and the expectation is over the randomness of X and Z. From Lemma A.2, it is easy to see that is convex. In this section, we prove a stronger claim:

This is summarized in Proposition A.5 below.

Proposition A.5 (Strict convexity). Let be a function with the following properties: (i) it is proper strictly convex; (ii) it is continuously differentiable and its derivative is such that let X, Z be independent random variables with strictly positive densities. Then, the function in (55) is jointly strictly convex in its arguments.

Proof. Let and . Further assume that and define the proximal operators

for i = 1, 2. Finally, denote . With this notation,

The first inequality above follows by the definition of the Moreau envelope in (41). The equality in the second line uses the definition of the function . Finally, the last inequality follows from convexity

This already proves convexity of (55). In what follows, we will argue that the inequality in (57) is in fact strict under the assumption of the lemma. Specifically, in Lemma A.3, we prove that under the assumptions of the proposition, for

Using this in (56) completes the proof of the proposition. The idea behind the proof of Lemma A.3 is as follows. First, we use the fact that to argue that there exists a non-zero measure set of . Then, the desired claim follows by strict convexity of

Lemma A.3. Let be a proper strictly convex function that is continuously differentiable with . Further assume independent continuous random variables X, Z with strictly positive densities. Fix arbitrary triplets . Further denote

Then, there exists a ball of nonzero measure, i.e. , such that , for all . Consequently, for any , the following strict inequality holds,

Proof. Note that (59) holds trivially with “replaced by “due to the convexity of . To prove that the inequality is strict, it suffices, by strict convexity of , that there exists subset that satisfies the following two properties:

1. p

2.

Consider the following function

By lemma A.4, there exists

Moreover, by continuity of the proximal operator (cf. Proposition A.1(a)), it follows that f is continuous. From this and (61), we conclude that for sufficiently small there exists a -ball S centered at , such that property 1 holds. Property 2 is also guaranteed to hold for S, since both X, Z have strictly positive densities and are independent.

Lemma A.4. Let be a proper, convex function. Further assume that is continuously differentiable and . Then, the following statement is true

Proof. We prove the claim by contradiction, but first, let us set up some useful notation. Let triplets and further define

By Proposition A.1, the following is true:

For the sake of contradiction, assume that the claim of the lemma is false. Then,

From this, it also holds that

Recalling (63) and applying (64), we derive the following from (65):

We consider the following two cases separately.

Case 1: , it holds that

However, from (66) we have that for all . This contradicts (67) and completes the proof for this case.

Case 2: : Continuing from (66) we can compute that for all

By replacing ) we derive that:

where

By replacing x = z = 0 in (69) we find that . This contradicts the assumption of the lemma and completes the proof.

A.6.3 Strict concavity

In this section, we study the following variant of the expected Moreau envelope:

for a lower semi-continuous, proper, convex function and continuous random variable X. The expectation above is over the randomness of X. In Section B.4 we show that the function is concave in . Here, we prove the following statement regarding strict-concavity of

This is summarized in Proposition A.6 below.

Proposition A.6 (Strict concavity). Let be a convex, continuously differentiable function for which . Further let X be a continuous random variable in R with strictly positive density in the real line. Then, the function concave in

Proof. Before everything, we introduce the following convenient notation:

Note from Proposition A.1 that is differentiable with derivative

We proceed in two steps as follows. First, for fixed we prove in Lemma A.5 below that

This shows that for all

Second, we use Lemma A.3 to argue that the inequality is in fact strict for all where and . To be concrete, apply Lemma A.3 for . Notice that all the assumptions of the lemma are satisfied, hence there exists interval

Hence, from (72) it follows that

From this, and (71) we conclude that

Thus from (73) and (74), as well as the facts that , we conclude that is strictly concave in

Lemma A.5. Let be a convex, continuously differentiable function. Fix and denote . Then, for any , it holds that

Moreover, for , the following statement is true :

Proof. First, we prove (75). Then, we use it to prove (76).

Proof of (75): Consider function defined as follows . By assumption, g is

differentiable with derivative . Moreover, -strongly convex. Finally, by optimality of the proximal operator (cf. Proposition A.1), it holds that these, it can be computed that

In the following inequalities, we combine all the aforementioned properties of the function g to find that

This leads to the desired statement and completes the proof of (75).

Proof of (76): We fix and apply (75) two times as follows. First, applying (75) for

and using the fact that we find that

Second, applying (75) for and using again the fact that we find that

Adding (77) and (78), we have shown the desired property as follows:

Proposition A.7. Let be a lsc, proper, convex function. Let and function such that the random variable Y S = f(S)S has a continuous strictly positive density on the real line. Then the following properties are true for the expected Moreau envelope function

For the statements below, further assume that is strictly convex and continuously differentiable with

Proof. The statements (a),(b) and (d) follow directly by Propositions A.4, A.5 and A.6. It remains to prove statements (c) and (e). Let . Then, there exist independent copies . Hence, we have the following chain of inequalities:

where the inequality follows from Jensen and convexity of with respect to (see Statement (b) of the Proposition). This proves Statement (c). For Statement (e), note that the inequality is strict provided that is strictly convex (see Statement (d) of the Proposition).

In this section we provide a proof sketch of Theorem 2.1. The main technical tool that facilitates our analysis is the convex Gaussian min-max theorem (CGMT), which is an extension of Gordon’s Gaussian min-max inequality (GMT). We introduce the necessary background on the CGMT in B.1.

The CGMT has been mostly applied to linear measurements [Sto13, OTH13, TOH15, TAH18, MM18]. The simple, yet central idea, which allows for this extension, is a certain projection trick inspired by [PV16]. Here, we apply a similar trick, but in our setting, we recognize that it suffices to simply rotate to align with the first basis vector. The simple rotation decouples the measurements from the last coordinates of the measurement vectors (see Section B.2). While this is sufficient for LS in [TAH15], in order to study more general loss functions, we further need to combine this with a duality argument similar to that in [TOH15]. Second, while the steps that bring the ERM minimization to the form of a PO (see (88)) bear the aforementioned similarities to [TAH15, TOH15], the resulting AO is different from the one studied in previous works. Hence, the mathematical derivations in Sections B.3 and B.4 are different. This also leads to a different system of equations characterizing the statistical behavior of ERM. Finally, in Section B.5, we prove uniqueness of the solution of this system of equations using the properties of the expected Moreau envelope function studied in Section A.6.

B.1 Technical tool: CGMT

B.1.1 Gordon’s Min-Max Theorem (GMT)

The Gordon’s Gaussian comparison inequality [Gor88] compares the min-max value of two doubly indexed Gaussian processes based on how their autocorrelation functions compare. The inequality is quite general (see [Gor88]), but for our purposes we only need its application to the following two Gaussian processes:

where: , they all have entries iid Gaussian; the sets and are compact; and, . For these two processes, define the following (random) min-max optimization programs, which we refer to as the primary optimization (PO) problem and the auxiliary optimization (AO).

According to Gordon’s comparison inequality, for any , it holds:

In other words, a high-probability lower bound on the AO is a high-probability lower bound on the PO. The premise is that it is often much simpler to lower bound the AO rather than the PO. To be precise, (82) is a slight reformulation of Gordon’s original result proved in [TOH15].

B.1.2 Convex Gaussian Min-Max Theorem (CGMT)

The proof of Theorem 2.1 builds on the CGMT [TOH15]. For ease of reference we summarize here the essential ideas of the framework following the presentation in [TAH18]; please see [TAH18, Section 6] for the formal statement of the theorem and further details. The CGMT is an extension of the GMT and it asserts that the AO in (81b) can be used to tightly infer properties of the original (PO) in (81a), including the optimal cost and the optimal solution. According to the CGMT [TAH18, Theorem 6.1], if the sets and are convex and is continuous , then, for any

In words, concentration of the optimal cost of the AO problem around implies concentration of the optimal cost of the corresponding PO problem around the same value . Moreover, starting from (83) and under strict convexity conditions, the CGMT shows that concentration of the optimal solution of the AO problem implies concentration of the optimal solution of the PO to the same value. For example, if minimizers of (81b) satisfy for some , then, the same holds true for the minimizers of (81a): [TAH18, Theorem 6.1(iii)]. Thus, one can analyze the AO to infer corresponding properties of the PO, the premise being of course that the former is simpler to handle than the latter.

B.2 Applying the CGMT to ERM for binary classification

In this section, we show how to apply the CGMT to (1). For convenience, we drop the subscript from and simply write

where the measurements follow (2). By rotational invariance of the Gaussian distribution of the measurement vectors , we assume without loss of generality that . Denoting ) is equivalent to the following min-max optimization:

such that are the first entries of , respectively. Note that in this new notation (2) becomes:

and

where we have decomposed ) is written as

or, in matrix form:

where is a diagonal matrix with on the diagonal, matrix with rows

In (88) we recognize that the first term has the bilinear form required by the GMT in (81a). The rest of the terms form the function in (81a): they are independent of and convex-concave as desired by the CGMT. Therefore, we have expressed (84) in the desired form of a PO and for the rest of the proof we will analyze the probabilistically equivalent AO problem. In view of (81b), this is given as follows,

where as in (81b)

B.3 Analysis of the Auxiliary Optimization

Here, we show how to analyze the AO in (89). To begin with, note that , therefore and . Also, let us denote the first entry

From [TAH18, Lem. A.3], instead of the AO in (89), it suffices to analyze the following version

Note that the “” problem in (89) is equivalent to a “” problem. Compared to that, the order of min-max in (90) is now flipped; see the discussion in [TAH18, Sec. A.6]. Now it is now possible to optimize over the direction of , which leads to the following:

Next, let and optimize over the direction of

To continue, we utilize the fact that for all

With this trick, the optimization over u becomes separable over its coordinates . By inserting this in (92) we have

Now, we show that the objective function above is convex-concave. Clearly, the function is linear (thus, concave in ). Moreover, from Lemma A.1, the function is jointly convex in The rest of the terms are clearly convex and this completes the argument. Hence, with a permissible change in the order of min-max, we arrive at the following convenient form:

where recall the definition of the Moreau envelope in (41). As to now, we have reduced the AO into a random min-max optimization over only four scalar variables in (93). For fixed , direct application of the weak law of large numbers, shows that the objective function of (93) converges in probability to the following as

where (in view of (86)). Based on that, it can be shown (similar arguments are developed in [TAH18, DTL18]) that the random optimizers converge to the deterministic optimizers of the following (deterministic) optimization problem (whenever these are bounded as the statement of the theorem requires):

At this point, recall that represents the norm of the value of . Thus, in view of (i) (87), (ii) the equivalence between the PO and the AO, and, (iii) our derivations thus far we have that with probability approaching 1,

where are the minimizers in (94). The three equations in (6) are derived by the first-order optimality conditions of the optimization in (94). We show this next.

B.4 Convex-Concavity and First-order Optimality Conditions

First, we prove that the objective function in (94) is convex-concave. For convenience define the function as follows

Based on Lemma A.2, it immediately follows that if is convex, F is jointly convex in . To prove concavity of it suffices to show that is concave in . To show this we note that

which is the point-wise minimum of linear functions of . Thus, using Proposition A.3(b), we conclude that is concave in . This completes the proof of convex-concavity of the function convex. By direct differentiation and applying Proposition A.7(a), the first order optimality conditions of the min-max optimization in (94) are as follows:

Next, we show how these equations simplify to the following system of equations (same as (6):

Let is immediate from equation (96a). Second, substituting , which together with (96b) leads to (97c). Finally, (97b) can be obtained by substituting ) and using the fact that (see Proposition A.1):

B.5 On the uniqueness of solutions to (97): Proof of Proposition 2.1

Here we prove the claim of Proposition 2.1 through the following lemmas. As we discussed in Remark 4, the main part of the proof is showing strict convex-concavity of F in (9). Lemma B.1 proves that this is the case, and Lemmas B.2 and B.3 show that this is sufficient for the uniqueness of solutions to (97). When put together, these complete the proof of Proposition 2.1.

Lemma B.1 (Strict convex-concavity of (95))be proper and strictly convex function. Further assume that is continuously differentiable with . Also assume that SY has positive density in the real line. Then, the function is strictly convex in and strictly concave in

Proof. The claim follows directly from the strict convexity-concavity properties of the expected Moreauenvelope proved in Proposition A.5 and A.6. Specifically, we apply Proposition A.7.

Lemma B.2. If the objective function in (95) is strictly convex in and strictly concave in , then (96) has a unique solution

be two different saddle points of (95). For convenience, let for i = 1, 2. By strict-concavity in , for fixed values of , the value of maximizing is unique. Thus, if then it must hold that , which is a contraction to our assumption of . Similarly, we can use strict-convexity to derive that . Then based on the definition of the saddle point, and strict convexity-concavity, the following two relations hold for i = 1, 2:

We choose

From the above, it follows that and , which is a contradiction. This completes the proof.

Lemma B.3. If (96) has a unique solution has a unique solution

Proof. First, following the same approach of deriving the equations (97) from (96) in Section B.4, it is easy to see that existence of solution implies existence of solution Now, for the sake of contradiction to the statement of the lemma, assume that there are two different triplets

Figure 4: The value of as in Theorem 3.1 for various measurement models. Since is a monotonic function of solution to determines the minimum possible value of

and satisfying (97). Then, we can show that both such that:

satisfy the system of equations in (96). However since , it must be that . This contradicts the assumption of uniqueness of solutions to (96) and completes the proof.

C.1 On the uniqueness of solutions to the Equation

The existence of a solution to the equation was proved in the previous Section. However it is not clear if the solution to this equation is unique i.e., for any there exists only one such that If this is the case then the Equation (10) in Theorem 3.1 can be equivantly written as

Although we do not prove this claim, our numerical experiments in Figure 4 show that is a monotonic function for Noisy-signed (see Section E for the definition), Logistic and Probit measurements, implying the uniqueness of solution to the equation

C.2 Distribution of SY in special cases

We derive the following densities for SY for the special cases :

• Signed:

• Logistic:

• Probit:

Figure 5: Probability distribution function of SY for the Logistic and Probit models compared with the probability distribution function of the Gaussian random variable (dashed lines) with the same mean and variance i.e., N(E[SY ], Var[SY ]).

In particular we numerically observe that for Logistic and Probit models, the resulting densities are similar to the density of a gaussian distribution derived according to N(E[SY ], Var[SY ]). Figure 5 illustrates this similarity for these two models. As it was discussed in Corollary 3.1 this similarity results in the tightness of the lower bound achieved for in Equation (21).

D.1 Completing the proof

The following proposition gives a recipe to invert Moreau envelope functions and was used in the proof of Theorem 3.2.

Proposition D.1 (Inverse of the Moreau envelope). [AG16, Result 23 in the appendix] For convex, lower semi-continuous function such that , the Moreau envelope can be inverted so that

D.2 On the convexity of optimal loss function

Here we provide a sufficient condition for to be convex.

Lemma D.1. The optimal loss function as defined in Theorem 3.2 is convex if

Proof. Using (49) optimal loss function is written in the following form

Next we prove that is a convex function. We first show that both and are positive numbers for all values of . We first note that since G and SY are independent random variables . Therefore

Additionally following Cramer-Rao bound [Bar84] for fisher information, it yields that :

Using this inequality for we derive that

where c is a constant independent of w. By differentiating twice we see that

is a convex function of w. Therefore for proving that is a convex function it is sufficient to prove that is a convex function or equivalently . By replacing values of and recalling the equation for it yields that

which implies the convexity of . For obtaining the derivative of , we use the result in [Roc70, Cor. 23.5.1] which states that for a convex function f

By differentiating again and using the properties of inverse function it yields that

Note that denominator of (102) is nonnegative since it is second derivative of a convex function. Therefore it is evident from (102) that a sufficient condition for the convexity of

This condition is satisfied if the statement of the lemma holds for

where we used (100) in the last inequality. This concludes the proof.

Figure 6: . For Logistic and Hinge-loss, the set of minimizers in (1) is bounded (as required by Theorem 2.1) iff

D.2.1 Optimal loss function for Signed model

In the case of Signed model, it can be proved that the conditions of Lemma D.1 is satisfied. Since , we derive the probability density of as follows :

Direct calculation shows that f is a log-concave function for all . Therefore

This proves the convexity of optimal loss function derived according to Theorem 3.2 when measurements follow the Signed model.

Consider a noisy-signed label function as follows:

where . In the case of signed measurements i.e., it can be observed that for all possible values of , the condition (39) in Section 4.2 holds for . This implies the separability of data and therefore the solution to the optimization problem (1) is unbounded for all . However in the case of noisy signed label function, boundedness or unboundedness of solutions to (1) depends on . As it was discussed in Section 4.2, the minimum value of for bounded solutions is derived from the following:

Figure 7: Comparisons between analytical and empirical results for the least-squares (LS), least-absolute deviations and Hinge loss functions along with the upper bound on performance and the empirical performance of optimal loss function as in Theorem 3.2, for Noisy-signed measurement model with (left) and (right). The vertical dashed lines are evaluated by (103) and represent , respectively.

where . It can be checked analytically that is a decreasing function of with and

In Figure 6, we have numerically evaluated the threshold value as a function of the probability of error For , the set of minimizers of the (1) with logistic or hinge loss is unbounded.

The performances of LS, LAD and Hinge loss functions for Noisy-signed measurement model with and are demonstrated in Figures 7a and 7b, respectively. Comparing performances of Least-Squares and Hinge-loss functions suggest that hinge-loss is robust to measurement corruptions, as for moderate to large values of it outperforms the LS estimator. Theorem 2.1 opens the way to analytically confirm such conclusions, which is an interesting future direction.

F.1 Proof of Corollary 4.1

In order to get the values of as in the statement of the corollary, we show how to simplify Equations (6) for . In this case, the proximal operator admits a simple expression:

Also, . Substituting these in (12a) gives the formula for as follows:

where we have also used from (5) that and G is independent of S. Also, since , direct application of (47) gives

Finally, substituting the value of ) we obtain the desired value for as follows :

F.2 Discussion

Linear vs binary. On the one hand, Corollary 4.1 shows that least-squares performance for binary measurements satisfies

where is as in (37) and . On the other hand, it is well-known (e.g., see references in [TAH18, Sec. 5.1]) that least-squares for (scaled) linear measurements with additive Gaussian noise (i.e. ) leads to an estimator that satisfies

Direct comparison of (104) to (105) suggests that least-squares with binary measurements performs the same as if measurements were linear with scaling factor and noise variance worth-mentioning conclusion is not new as it was proved in [Bri82, PV16, TAH15, GJ17]. We include a short discussion on the relation to this prior work in the following paragraph. We highlight that all these existing results are limited to a least-squares loss unlike our general analysis.

Prior work. There is a lot of recent work on the use of least-squares-type estimators for recovering signals from nonlinear measurements of the form with Gaussian vectors . The original work that suggests least-squares as a reasonable estimator in this setting is due to Brillinger [Bri82]. In his 1982 paper, Brillinger studied the problem in the classical statistics regime (aka n is fixed not scaling with ) and he proved for the least-squares solution satisfies

where

and the expectations are with respect to S and possible randomness of f. Evaluating (106) for leads to the same values for . In other works, (104) for indeed recovers Brillinger’s result. The extension of Brillinger’s original work to the high-dimensional setting (both m, n large) was first studied by Plan and Vershynin [PV16], who derived (non-sharp) non-asymptotic upper bounds on the performance of constrained least-squares (such as the Lasso). Shortly after, [TAH15] extended this result to sharp asymtpotic predictions and to regularized least-squares. In particular, Corollary 4.1 is a special case of the main theorem in [TAH15]. Several other interesting extensions of the result by Plan and Vershynin have recently appeared in the literature, e.g., [Gen17, GMW18, GJ17, TR18]. However, [TAH15] is the only one to give results that are sharp in the flavor of this paper. Our work, extends the result of [TAH15] to general loss functions beyond least-squares. The techniques of [TAH15] that have guided the use of the CGMT in our context have also been recently applied in [DTL18] in the context of phase-retrieval.