Fundamental Limits of Ridge-Regularized Empirical Risk Minimization in High Dimensions

Introduction

Empirical Risk Minimization (ERM) includes a wide family of statistical inference algorithms that are popular in estimation and learning tasks encountered in a range of applications in signal processing, communications and machine learning. ERM methods are often efficient in implementation, but first one needs to make certain choices: such as, choose an appropriate loss function and regularization function, and tune the regularization parameter. Classical statistics have complemented the practice of ERM with an elegant theory regarding optimal such choices, as well as, fundamental limits, i.e., tight bounds on their performance, e.g., [Hub11]. These classical theories typically assume that the size $m$ of the set of observations is much larger than the dimension $n$ of the parameter to be estimated, i.e., $m\gg n$. In contrast, modern inference problems are typically high-dimensional, i.e. $m$ and $n$ are of the same order and often $n>m$ [Can14, Mon15, Kar13]. This paper studies the fundamental limits of convex ERM in high-dimensions for generalized linear models.

This paper aims to provide answers to the following questions on fundamental limits of (1): What is the minimum achievable (estimation/prediction) error of $\widehat{\mathbf{x}}_{\mathcal{L},{\lambda}}$? How does this depend on the link function $\varphi$ and how to choose $\mathcal{L}$ and ${\lambda}$ to achieve it? What is the sub-optimality gap of popular choices such as ridge-regularized least-squares (RLS)? How do the answers to these questions depend on the over-parameterization ratio $n/m$? We provide answers to the questions above for the following two popular instances of GLMs.

Linear models: $y_{i}=\mathbf{a}_{i}^{T}\mathbf{x}_{0}+z_{i}$, where z_{i}\mathrel{\overset{\text{\small{iid}}}{\scalebox{1.5}[1.0]{\sim}}}P_{Z},~{}i\in[m]. As is typical, for linear models, we measure performance of $\widehat{\mathbf{x}}_{\mathcal{L},{\lambda}}$ with the squared error: $\|\widehat{\mathbf{x}}_{\mathcal{L},{\lambda}}-\mathbf{x}_{0}\|_{2}^{2}$.

All our results are valid under the following two assumptions.

Throughout the paper, we assume the high-dimensional limit where $m,n\rightarrow\infty$ at a fixed ratio $\delta=m/n>0$.

Overview of Contributions. We are now ready to summarize the paper’s main contributions.

$\bullet$ For linear models, we prove a lower bound on the squared-estimation error of RERM; see Theorem 2.1. We start with a system of two nonlinear equations that is parametrized by the loss $\mathcal{L}$ and the regularizer ${\lambda}$, and determines the high-dimensional limit of the error for the corresponding $\mathcal{L}$ and ${\lambda}$ [Kar13, TAH18]. By identifying an algebraic structure in these equations, we establish a lower bound on their solution that holds for all choices of $\mathcal{L}$ and ${\lambda}$.

$\bullet$ For binary models, we first derive a system a of three nonlinear equations whose unique solution characterizes the statistical performance (correlation or classification error) of RERM under mild assumptions on the loss and link functions $\mathcal{L}$ and $f$; see Theorem 3.1. Previous works have only considered specific loss and link functions or no regularization. Second, we use this system of equations to upper bound the accuracy over this class of $(\mathcal{L},f)$-pairs; see Theorem 3.2.

$\bullet$ Importantly, we present a recipe for optimally tuning $\mathcal{L}$ and ${\lambda}$ in both linear and binary models; see Lemmas 2.1 and 3.1. For specific models, such as linear model with additive exponential noise, binary logistic and signed data, we numerically show that the optimal loss function is convex and we use gradient-descent to optimize it. The numerical simulations perfectly match with the theoretical predictions suggesting that our bounds are tight.

$\bullet$ We derive simple closed-form approximations to the aforementioned bounds; see Corollaries 2.1 (linear) and 3.1 (binary). These simple (yet tight) expressions allow us to precisely quantify the sub-optimality of ridge-regularized least-squares (RLS). For instance, we show that optimally-tuned RLS is (perhaps surprisingly) approximately optimal for logistic data and small signal strength, but the sub-optimality gap grows drastically as signal strength increases. In the Appendix, we also include comparisons to ERM without regularization and to a simple averaging method.

Our results fit in the rapidly growing recent literature on sharp asymptotics of (possibly non-smooth) convex optimization-based estimators, e.g., [DMM11, Sto09, BM12, CRPW12, ALMT13, OH16, Sto13, OTH13, TOH15, Kar13, EK18, DM16, TAH18, OT17, MM18, WWM19, CM19, HL19, BKRS19, HL19, BKRS19]. Most of these works study linear models. Extensions to generalized linear models for the special case of regularized LS were studied in [TAH15], while more recently there has been a surge of interest in RERM methods tailored to binary models (such as logistic regression or SVM) [Hua17, CS18, SC19, MLC19b, MLC19a, KA20, SAH19, TPT20, DKT19, MRSY19, LS20, MKLZ20].

Out of these works relatively few have focused on fundamental limits among families of ERM (rather than specific instances). The papers [BBEKY13, DM16, AG16] derive lower bounds and optimal loss functions for the squared error of (unregularized) ERM for linear models. In a related work, [DM15] studies robustness of these methods to the noise distribution. More recently, [CM19] performed an in-depth analysis of fundamental limits of convex-regularized LS for linear models of structured signals. For binary models, upper bounds on the correlation of un-regularized ERM were only recently derived in [TPT20]. This paper contributes to this line work. For linear models, we build on corresponding sharp error characterizations in [EK18, TAH18] to extend the results of [BBEKY13, DM16, AG16] to ridge-regularized ERM. Specifically, our results hold for all values of $\delta>0$ including the, so called, overparameterized regime $\delta<1$. For binary models, our contribution is twofold: (i) we present sharp asymptotic characterizations for RERM for a wide class of loss and link functions; (ii) we use these to extend the correlation bounds of [TPT20] to the regularized case.

On a technical level, the sharp asymptotics are derived using the convex Gaussian min-max Theorem (CGMT) [Sto13, TOH15]. In particular, we follow the machinery introduced in [TAH15, KA20, SAH19, TPT20, DKT19] that applies the CGMT to binary models and predicts the performance in terms of a system of few nonlinear equations. Our main technical contribution here is proving existence and uniqueness of the solutions to these equations, which is critical as it guarantees that our performance bounds hold for a wide class of loss and link functions.

Linear Models

Consider data $(y_{i},\mathbf{a}_{i})$ from an additive noisy linear model: y_{i}=\mathbf{a}_{i}^{T}\mathbf{x}_{0}+z_{i},~{}z_{i}\mathrel{\overset{\text{\small{iid}}}{\scalebox{1.5}[1.0]{\sim}}}P_{Z},~{}i\in[m].

The noise variables $z_{i}$ are iid distributed as $Z\sim P_{Z}$, $i\in[m]$, for a distribution $P_{Z}$ with zero mean and finite nonzero second moment.

For loss functions that are lower semicontinuous (lsc), proper, and convex we focus on the following version of (1) that is tailored to linear models:

We assume without loss of generality that $\|\mathbf{x}_{0}\|_{2}=1$ Suppose that $\|\mathbf{x}_{0}\|_{2}=r>0$. Then, the optimization problem in (2) can be transformed to the case $\widetilde{\mathbf{x}}_{0}:=\mathbf{x}_{0}/r$ (hence $\|\widetilde{\mathbf{x}}_{0}\|=1$) by setting $\widetilde{\mathcal{L}}(t):=\mathcal{L}(rt)$, $\widetilde{{\lambda}}:=r^{2}{\lambda}$ and $\widetilde{Z}=Z/r$. This implies that the results of Section 2.2 can be reformulated by replacing $Z$ with $\widetilde{Z}$..

Prior works have investigated the limit of the squared error $\|\widehat{\mathbf{x}}_{{}_{\mathcal{L},{\lambda}}}-\mathbf{x}_{0}\|^{2}$ [Kar13, TAH18]. Specifically, consider the following system of two equations in two unknowns $\alpha$ and $\tau$:

where $G\sim\mathcal{N}(0,1)$ and $Z\sim P_{Z}$ is the noise variable. It has been shown in [Kar13, TAH18] that under appropriate regularity conditions on $\mathcal{L}$ and the noise distribution $P_{Z}$, the system of equations above has a unique solution $(\alpha_{\mathcal{L},{\lambda}}>0,\tau{{}_{\mathcal{L},{\lambda}}}>0)$ and $\alpha_{\mathcal{L},{\lambda}}^{2}$ is the HD limit of the squared-error, i.e.,

Here, we derive tight lower bounds on $\alpha_{\mathcal{L},{\lambda}}^{2}$ over both the choice of $\mathcal{L}$ and ${\lambda}$. Our starting point is the asymptotic characterization in (4), i.e., our results hold for all loss functions and regularizer parameters for which (3) has a unique solution that characterizes the HD limit of the square-error. To formalize this, we define the following collection of loss functions $\mathcal{L}$ and noise distributions $P_{Z}$:

We refer the reader to [Kar13, Thm. 1.1] and [TAH18, Thm. 2] for explicit characterizations of $(\mathcal{L},P_{Z})$ that belong to $\mathcal{C}_{\rm lin}$. We conjecture that some of these regularity conditions (e.g., the differentiability requirement) can in fact be relaxed. While this is beyond the scope of this paper, if this is shown then automatically the results of this paper formally hold for a richer class of loss functions.

2 Fundamental Limits and Optimal Tuning

Our first main result, stated as Theorem 2.1 below, establishes a tight bound on the achievable values of $\alpha_{{\mathcal{L},{\lambda}}}^{2}$ for all regularization parameters ${\lambda}>0$ and all choices of $\mathcal{L}$ such that $(\mathcal{L},P_{Z})\in\mathcal{C}_{\rm lin}$.

For any $\mathcal{L}$ such that $(\mathcal{L},P_{Z})\in\mathcal{C}_{\rm lin}$, ${\lambda}>0$ and $\alpha_{{\mathcal{L},{\lambda}}}^{2}$ denoting the respective high-dimensional limit of the squared-error as in (4), it holds that $\alpha_{{\mathcal{L},{\lambda}}}\geq\alpha_{\star}$.

Let $\alpha_{\star}$ be as in (5) under the assumptions of Theorem 2.1. Assume that $p_{Z}$ is differentiable and takes strictly positive values on the real line. Then, it holds that

Moreover, the equality holds if and only if $Z\sim\mathcal{N}(0,\zeta^{2})$ for $\zeta>0$.

The proof of Corollary presented in Section C.5 shows that the gap between the actual value of $\alpha_{\star}$ and h_{\delta}\big{(}{1}\big{/}{\mathcal{I}(Z)}\big{)} depends solely on the distribution of $Z$. Informally: the more $Z$ resembles a Gaussian, the smaller the gap. The simple approximation of Corollary 2.1 is key for comparing the performance of optimally tuned RERM to optimally-tuned RLS in Section 2.3.

Our next result reinforces the claim that the bound is actually tight for a larger class of noise distributions.

We leave for future work coming up with sufficient conditions on $P_{Z}$ under which $(\mathcal{L}_{\star},P_{Z})\in\mathcal{C}_{\rm lin}$, which would imply that the bound of Theorem 2.1 is achieved by choosing $\mathcal{L}=\mathcal{L}_{\star}$ and ${\lambda}={\lambda}_{\star}$ in (2). In Figures 1(Left) and 2(Top Left), we numerically (by using gradient descent) evaluate the performance of the proposed loss function $\mathcal{L}_{\star}$, in the case of Laplacian noise, suggesting that it achieves the lower bound $\alpha_{\star}$ in Theorem 2.1. See also Figure 3(Left) for an illustration of $\mathcal{L}_{\star}$.

3 The Sub-optimality Gap of RLS in Linear Models

We rely on Theorem 2.1 to investigate the statistical gap between least-squares (i.e. $\mathcal{L}(t)=t^{2}$ in (2)) and the optimal choice of $\mathcal{L}$. As a first step, the lemma below computes the high-dimensional limit of optimally regularized RLS.

The first term in the lower bound in (7) reveals that in the highly over-parameterized regime ($\delta\ll 1$), it holds $\omega_{\delta}\approx 1$. Thus, optimally-regularized LS becomes optimal. More generally, in the overparameterized regime $0<\delta<1$, the squared-error of optimally-tuned LS is no worse than $(1-\delta)^{-1}$ times the optimal performance among all convex ERM.

Binary Models

Consider data $(y_{i},\mathbf{a}_{i}),~{}i\in[m]$ from a binary model: $y_{i}=f(\mathbf{a}_{i}^{T}\mathbf{x}_{0})$ where $f$ is a (possibly random) link function outputting $\{\pm 1\}.$

Under Assumptions 1, 2 and 4 we study the ridge-regularized ERM for binary measurements:

We also assume that $\|\mathbf{x}_{0}\|_{2}=1$ since the signal strength can always be absorbed in the link function, i.e., if $\|\mathbf{x}_{0}\|_{2}=r>0$ then the results continue to hold for a new link function \widetilde{f}(t):=f\big{(}rt\big{)}.

In contrast to linear models where we focused on squared error, for binary models, a more relevant performance measure is normalized correlation ${\rm{corr}}\left(\,{{\widehat{\mathbf{w}}}_{{\mathcal{L},{\lambda}}}}\,,\,{\mathbf{x}_{0}}\,\right)$. Our first result determines the limit of ${\rm{corr}}\left(\,{{\widehat{\mathbf{w}}}_{{\mathcal{L},{\lambda}}}}\,,\,{\mathbf{x}_{0}}\,\right)$. Specifically, we show that for a wide class of loss functions it holds that

where \sigma_{{\mathcal{L},{\lambda}}}^{2}:=\alpha_{{\mathcal{L},{\lambda}}}^{2}\big{/}\mu_{{\mathcal{L},{\lambda}}}^{2} and $(\alpha_{{\mathcal{L},{\lambda}}},\mu_{{\mathcal{L},{\lambda}}})$ are found by solving the following system of three nonlinear equations in three unknowns $(\alpha,\mu,\tau)$, for G,S\mathrel{\overset{\text{\small{iid}}}{\scalebox{1.5}[1.0]{\sim}}}\mathcal{N}(0,1) :

To formalize this, we define the following collection of loss and link functions:

We prove Theorem 3.1 in Section B. Previous works have considered special instances of this: [SC19, SAH19] study unregularized and regularized logistic-loss for the logistic binary model, while [TPT20] studies strictly-convex ERM without regularization. Here, we follow the same approach as in [SAH19, TPT20], who apply the convex Gaussian min-max theorem (CGMT) to relate the performance of RERM to an auxiliary optimization (AO) problem whose first-order optimality conditions lead to the system of equations in (10). Our technical contribution in proving Theorem 3.1 is proving existence and uniqueness of solutions to (10) for a broad class of convex losses. As a final remark, the solution to (10) (specifically, the parameter $\sigma_{{\mathcal{L},{\lambda}}}^{2}$) further determines the high-dimensional limit of the classification error for a fresh feature vector $\mathbf{a}\sim\mathcal{N}(\mathbf{0},\mathbf{I}_{n})$ (see Section D.2) :

2 Fundamental Limits and Optimal Tuning

Thus far, we have shown in (9) and (12) that $\sigma_{{\mathcal{L},{\lambda}}}$ predicts the high-dimensional limit of the correlation and classification-error of the RERM solution ${\widehat{\mathbf{w}}}_{{\mathcal{L},{\lambda}}}$. In fact, smaller values for $\sigma_{{\mathcal{L},{\lambda}}}$ result in better performance, i.e. higher correlation and classification accuracy (see Section D.2). In this section we derive a lower bound on $\sigma_{{\mathcal{L},{\lambda}}}$ characterizing the statistical limits of RERM for binary models.

For any $(\mathcal{L},f)\in\mathcal{C}_{\rm bin}$, ${\lambda}>0$ and $\sigma_{{\mathcal{L},{\lambda}}}^{2}$ the respective high-dimensional limit of the error as in (9), it holds that $\sigma_{{\mathcal{L},{\lambda}}}\geq\sigma_{\star}$.

We prove Theorem 3.2 in Section D.3, where we also show that the minimization in (13) is always feasible. In view of (9) and (12) the theorem’s lower bound translates to an upper bound on correlation and test accuracy. Note that $\sigma_{\star}$ depends on the link function only through the Fisher information of the random variable $s\,G+S\,f(S)$. This parallels the lower bound of Theorem 2.1 on linear models with the random variable $S\,f(S)$ effectively playing the role of the noise variable $Z$.

Let $\sigma_{\star}$ be as in (13). Fix any $\delta>0$ and assume that $f(\cdot)$ is such that the random variable $Sf(S)$ has a differentiable and strictly positive probability density on the real line. Then,

Corollary 3.1 can be viewed as an extension of Corollary 2.1 to binary models. The proof of the corollary presented in Section D.6 further reveals that the more the distribution of $Sf(S)$ resembles a Gaussian distribution, the tighter the gap is, with equality being achieved if and only if $Sf(S)$ is Gaussian.

Our next result strengthens the lower bound of Theorem 3.2 by showing existence of a loss function and regularizer parameter for which the system of equations (10) has a solution leading to $\sigma_{\star}$.

where $\eta:=1-\mathcal{I}(W_{{\star}})\cdot(\sigma_{\star}^{2}-\sigma_{\star}^{2}{\lambda}_{\star}\delta-{\lambda}_{\star}\delta)-{\lambda}_{\star}\delta$ and $Q(w):=w^{2}/2.$ Then for $\mathcal{L}_{\star}$ and ${\lambda}_{\star}$, the equations (10) satisfy $(\alpha,\mu,\tau)=(\sigma_{\star},1,1)$.

Lemma 3.1 suggests that if $\mathcal{L}_{\star}$ satisfies the assumptions of Theorem 3.1, then $\sigma_{\mathcal{L}_{\star},{\lambda}_{\star}}=\sigma_{\star}$. In Figures 1 and 2 and for the special cases of Signed and Logistic models, we verify numerically that performance of candidates $\mathcal{L}_{\star}$ and ${\lambda}_{\star}$ reaches the optimal errors . This suggests that for these models, Lemma 3.1 yields the optimal choices for $\mathcal{L}$ and ${\lambda}$. See also Figure 3(Right) for an illustration of $\mathcal{L}_{\star}$.

3 The Sub-optimality Gap of RLS in Binary Models

We use the optimality results of the previous section to precisely quantify the sub-optimality gap of RLS. First, the following lemma characterizes the performance of RLS.

Numerical Experiments

In the next two figures, we present results for binary models. Figure 1(Middle) plots the effective error parameter $\sigma$ for the Signed model and Figure 1(Right) plots the classification error ‘$\mathcal{E}$’ for the Logistic model with $\|\mathbf{x}_{0}\|_{2}=10$. The red squares correspond to the numerical evaluations of ERM with $\mathcal{L}=\mathcal{L}_{\star}$ and ${\lambda}={\lambda}_{\star}$ (as in Lemma 3.1) derived by running GD on the proposed optimal loss and regularization parameter. See Figure 3(Right) for an illustration of the optimal loss in this case. The solution ${\widehat{\mathbf{w}}}_{{\mathcal{L}_{\star},{\lambda}_{\star}}}$ of GD is used to calculate $\sigma_{{\mathcal{L}_{\star},{\lambda}_{\star}}}$ and $\mathcal{E}_{{\mathcal{L}_{\star},{\lambda}_{\star}}}$ in accordance with (9) and (12), respectively. Again, note the close match between theoretical and numerical evaluations (also see the third and fourth rows of Table 1).

Finally, for all three models studied in Figure 1, we also include the theoretical predictions for the error of the following: (i) RLS with small and large regularization (as derived in Equations (59) and (16)); (ii) optimally tuned RLS (as predicted by Lemmas 2.2 and 3.2); (iii) optimally-tuned unregularized ERM (marked as $\alpha_{\rm ureg},\sigma_{\rm ureg},\mathcal{E}_{\rm ureg}$). The curves for the latter are obtained from [BBEKY13] and [TPT20] for linear and binary models, respectively. We refer the reader to Sections F.1 and F.2 for a precise study of the benefits of regularization in view of Theorems 2.1 and 3.2, for both linear and binary models.

Conclusion and Future work

This paper derives fundamental lower bounds on the statistical accuracy of ridge-regularized ERM (RERM) for linear and binary models in high-dimensions. It then derives simple closed-form approximations that allow precisely quantifying the sub-optimality gap of RLS. In Section F in the supplementary material, these bounds are further used to study the benefits of regularization by comparing (RERM) to un-regularized ERM.

Among several interesting directions of future work, we highlight the following. First, our lower bounds make it possible to compare RERM to the optimal Bayes risk [BKM+19, RP19]. Second, it is interesting to extend the analysis to GLMs for arbitrary link functions beyond linear and binary studied here. A third exciting direction is investigating the fundamental limits of RERM in the presence of correlated (Gaussian) features.

Acknowledgment

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

References

Appendix A Useful facts

In Proposition A.1, some of the differential properties of Moreau-envelope functions, used throughout the paper are summarized (cf. [RW09]):

Let $\mathcal{L}$ be a lower semi-continuous and proper function. Then

(b) The first order derivatives of the Moreau-envelope of a function $\mathcal{L}$ are derived as follows:

Also if $\mathcal{L}$ is differentiable then

(c) Additionally, based on the relations above, if $\mathcal{L}$ is twice differentiable then the following is derived for its second order derivatives :

The following proposition gives the recipe for inverting Moreau-envelpe of a convex function:

[AG16, Result. 23] For $\tau>0$ and $f$ a convex, lower semi-continuous function such that $g(\cdot)=\mathcal{M}_{{f}}\left({\cdot};{\tau}\right)$, the Moreau envelope can be inverted so that $f(\cdot)=-\mathcal{M}_{{-g}}\left({\cdot};{\tau}\right).$

A.2 On Fisher Information

In Proposition A.3 we collect some useful properties of the Fisher Information for location. For the proofs and more details, we refer the interested reader to [Bla65].

Let $X$ be a zero-men random variable with probability density $p_{X}$ satisfying the following conditions: (i) $p_{X}(x)>0,-\infty<x<\infty$; (ii) $p_{X}^{\prime}(x)$ exists; and (iii) The following integral exists:

The Fisher information for location $\mathcal{I}(X)$ defined above satisfies the following properties.

For two independent random variables $X_{1},X_{2}$ satisfying the three conditions above and any $\theta\in$, it holds that $\mathcal{I}(X_{1}+X_{2})\leq\theta^{2}\mathcal{I}(X_{1})+(1-\theta)^{2}\mathcal{I}(X_{2})$.

(Stam’s inequality) For two independent random variables $X_{1},X_{2}$ satisfying the three conditions above, it holds that

Moreover equality holds if and only if $X_{1}$ and $X_{2}$ are independent Gaussian random variables.

$\lim_{a\rightarrow 0}a^{2}\mathcal{I}(V_{a})=0.$

$\lim_{a\rightarrow+\infty}a^{2}\mathcal{I}(V_{a})=1.$

To show part $(a)$, we use Proposition A.3(e) with $\theta=0$ to derive that

where the second step follows by the fact that $\mathcal{I}(Z)$ is finite for any $Z$ satisfying the assumption of the lemma. In order to prove part $(b)$, we apply Proposition A.3(c) to deduce that :

A.3 On Min-max Duality

Let $X$ be a compact convex subset of a linear topological space and $Y$ a convex subset of a linear topological space. If $f$ is a real-valued function on $X\times Y$ with $f(x,\cdot)$ upper semicontinuous and quasi-concave on $Y,\forall x\in X,$ and $f(\cdot,y)$ lower semicontinuous and quasi-convex on $X,\forall y\in Y$ then,

Appendix B Asymptotics for Binary RERM: Proof of Theorem 3.1

In this section, we prove that under the assumptions of Theorem 3.1, the system of equations in (10) has a unique and bounded solution.

As mentioned in Section 3, the proof of Theorem 3.1 has essentially two parts. The first part of the proof uses the CGMT [TOH15] and the machinery developed in [TAH18, TAH15, SAH19, TPT19] to relate the properties of the RERM solution to an Auxiliary Optimization (AO). The detailed steps follow mutatis-mutandis analogous derivations in recent works [TAH18, TAH15, SAH19, TPT19, KA20] and are omitted here for brevity. Instead, we summarize the finding of this analysis in the following proposition.

Consider the optimization problem in (8). If the min-max optimization in (28) has a unique and bounded solution $(\alpha^{\star}>0,\mu^{\star},\upsilon^{\star}>0,\gamma^{\star}>0)$, then the values of $\alpha_{\mathcal{L},{\lambda}}$ and $\mu_{\mathcal{L},{\lambda}}$ corresponding to $\mathcal{L}$ and ${\lambda}$ defined in (65)-(66) are derived by setting $\alpha_{\mathcal{L},{\lambda}}=\alpha_{\star}$ and $\mu_{\mathcal{L},{\lambda}}=\mu_{\star}$, where

and G,S\mathrel{\overset{\text{\small{iid}}}{\scalebox{1.5}[1.0]{\sim}}}\mathcal{N}(0,1).

The system of equations in (10) is derived by the first-order optimality conditions of the function $\Theta$ based on its arguments $(\alpha,\mu,\upsilon,\gamma)$, i.e., by imposing $\nabla\Theta=\mathbf{0}$. In fact, similar to [TPT20], it only takes a few algebraic steps to simplify the four equations in $\nabla\Theta=\mathbf{0}$ to the three equations in (10).

For the rest of this section, we focus on the second part of the proof of Theorem 3.1 regarding existence/uniqueness of solutions to (10), which has not been previously studied in our setting.

B.2 Properties of ΘΘ\Theta : Strict Convexity-Strict Concavity and Boundedness of Saddle Points

We will show in Lemma B.2 that for proving uniqueness and boundedness of the solutions to (10), it suffices to prove uniqueness and boundedness of the saddle point $(\alpha^{\star},\mu^{\star},\upsilon^{\star},\gamma^{\star})$ of $\Theta$. In fact, a sufficient condition for uniqueness of solutions in (28) is that $\Theta$ is (jointly) strictly convex in $(\alpha,\mu,\upsilon)$ and strictly-concave in $\gamma$ (e.g., see [TPT20, Lemma B.2.]). Lemma B.1, which is key to the proof of Theorem 3.1, derives sufficient conditions on $\mathcal{L}$ guaranteeing strict convexity-strict concavity of $\Theta$ as well as conditions on $\mathcal{L}$ ensuring boundedness of $(\alpha^{\star},\mu^{\star},\upsilon^{\star},\gamma^{\star}).$

If $\mathcal{L}$ is bounded from below, then for all solutions $(\alpha^{\star},\mu^{\star},\upsilon^{\star},\gamma^{\star})$ there exists a constant $C>0$ such that $\alpha^{\star}\in[0,C],\mu^{\star}\in[-C,C]$ and $\upsilon^{\star}\in[0,C]$.

In addition to the assumptions of parts (a) and (b) assume that $\mathcal{L}^{\prime}(0)\neq 0$, then $\gamma^{\star}>0,\alpha^{\star}>0$ and $\upsilon^{\star}>0$.

If $\mathcal{L}$ is twice differentiable and non-linear, then $\Theta$ is jointly strictly-convex in $(\alpha,\mu,\upsilon)$.

If $\mathcal{L}$ satisfies the assumptions of part (c) then $\Theta$ is strictly-concave in $\gamma$.

Based on (30) that holds for all feasible $(\alpha,\mu,\upsilon)$ and using the fact that ${\lambda}>0$ it can be readily shown that

Statement (b). Under the assumptions of the lemma, we know from part $(a)$ that the set of solutions to $(\alpha^{\star},\mu^{\star},\upsilon^{\star})$ in (28) is bounded. Thus we can apply the Min-Max Theorem A.1 and flip the order of minimum and maximum to write:

Without loss of generality, we assume $C$ large enough such that $C>\max\{1,1/\sqrt{\delta}\}$. Then, by choosing $\alpha=1,\mu=0$ and $\upsilon=1/\sqrt{\delta}$, we find that for all $\gamma>0$:

This implies boundedness of the set of maximizers $\gamma^{\star}$, which completes the proof.

Statement (c). First, we show that $\gamma^{\star}>0$. On the contrary, assume that $\gamma^{\star}=0$. Then based on (28) and Proposition A.1(a),

which based on the decreasing nature of RHS in terms of $\gamma$, implies that either $\gamma^{\star}=0$ or $\alpha^{\star}=0$. However, we proved that both $\gamma^{\star}$ and $\alpha^{\star}$ are positive. This proves the desired result $\upsilon^{\star}\neq 0$ and completes the proof of this part.

It is straightforward to see that if $\alpha>0$, then $\alpha G+\mu Sf(S)$ has positive density in the real line. Thus from (37) we find that :

Recalling (18), we see that the condition in (38) is satisfied if and only if :

Using inverse properties of Moreau-envelope in Proposition A.2, we derive that the loss function $\mathcal{L}(\cdot)$ satisfying (39) takes the following shape,

Case \@slowromancapii@ : $(\alpha_{1},\mu_{1})\neq(\alpha_{2},\mu_{2})$ In this case we use definition of strict-convexity to prove the claim. First, for compactness we define :

for $i=1,2$. Based on the way we defined the functions $\Theta$ and $\Omega$, one can see that in order to show strict-convexity of $\Theta$ in $(\alpha,\mu,\upsilon)$ it suffices to prove strict-convexity of $\Omega$ in $(\alpha,\mu,\tau)$. Let $\theta\in(0,1)$, and denote $\tau_{\theta}:=\theta\tau_{1}+\overline{\theta}\tau_{2},\alpha_{\theta}:=\theta\alpha_{1}+\overline{\theta}\alpha_{2}$ and $\mu_{\theta}:=\theta\mu_{1}+\overline{\theta}\mu_{2}$. With this notation,

Additionally since ${\lambda}>0$ and $(\alpha_{1},\mu_{1})\neq(\alpha_{2},\mu_{2})$, we find that :

Thus proceeding from (42) we conclude strict-convexity of the function $\Omega$ :

Statement (e). Based on the proof of part $(c)$ and under the assumptions of the lemma we have $\alpha^{\star}\neq 0$. Thus we see that the random variable $\alpha G+\mu Sf(S)$ has a positive probability density everywhere in the desired domain of the optimization problem in (28). Next, we use the result in [TPT20, Proposition A.6], which states that if the random variable $X$ has a positive density everywhere and $\mathcal{L}$ is continuously differentiable with $\mathcal{L}^{\prime}(0)\neq 0$ then

is strictly concave in $\gamma$. Based on this, $\Theta$ is strictly-concave in $\gamma$. This completes the proof of the lemma.

B.3 From (28) to (10)

The following lemma connects the min-max optimization (28) to the system of equations in (10)

Assume that the optimization problem in (28) yields a unique and bounded solution $(\alpha>0,\mu,\upsilon>0,\gamma>0)$. Then the equations (10) have a unique and bounded solution $(\alpha>0,\mu,\tau>0)$ where $\tau=\upsilon/\gamma.$

By direct differentiation with respect to the variables $(\mu,\alpha,\upsilon,\gamma)$, the first order optimality conditions of the min-max optimization in (28) are as follows:

Assumptions of the lemma imply that the saddle point of the optimization problem in (28) is unique and bounded, therefore (43) yields a unique bounded solution $(\alpha>0,\mu,\upsilon>0,\gamma>0)$. By denoting $\tau=\upsilon/\gamma$ and using the fact that $\mathcal{M}^{\prime}_{{\mathcal{L}},2}\left({x};{\tau}\right)=-\frac{1}{2}(\mathcal{M}^{\prime}_{{\mathcal{L}},1}\left({x};{\tau}\right))^{2}$ (as implied by (18)-(19)) we reach the Equations (10) i.e.,

The uniqueness of $(\alpha>0,\mu,\tau>0)$ as the solution to (44) follows from the uniqueness of the solution $(\alpha>0,\mu,\upsilon>0,\gamma>0)$ to (43). In particular if there are two distinct solutions $(\alpha_{1},\mu_{1},\tau_{1})$ and $(\alpha_{2},\mu_{2},\tau_{2})$ to the Equations (44), then we reach contradiction by noting that $(\alpha_{1},\mu_{1},\upsilon_{1}:=\alpha_{1}/\sqrt{\delta},\gamma_{1}:=\alpha_{1}/(\tau_{1}\sqrt{\delta}))$ and $(\alpha_{2},\mu_{2},\upsilon_{2}:=\alpha_{2}/\sqrt{\delta},\gamma_{2}:=\alpha_{2}/(\tau_{2}\sqrt{\delta}))$ are two distinct points satisfying the Equations (43). This completes the proof of the lemma. ∎

B.4 Completing the proof of Theorem 3.1

We are now ready to complete the proof of Theorem 3.1. Based on Lemma B.2, for the system of equations in (10) to have a unique and bounded solution, it suffices that $(\alpha^{\star}>0,\mu^{\star},\upsilon^{\star}>0,\gamma^{\star}>0)$ as the solution of (28) is unique and bounded. Since $\Theta$ is convex-concave and the optimality sets are bounded from Lemma B.1(a)-(e), a saddle point of $\Theta$ exists [Roc97, Cor. 37.3.2]. Additionally, based on the assumptions of the theorem and in view of Lemma B.1(d),(e), $\Theta$ is jointly strictly-convex in $(\alpha,\mu,\upsilon)$ and strictly-concave in $\gamma$ which implies the uniqueness of $(\alpha^{\star}>0,\mu^{\star},\upsilon^{\star}>0,\gamma^{\star}>0)$ as a solution to (28). This completes the proof of the theorem.

As mentioned in the main body of the paper, we conjecture that some of the technical conditions of Theorem 3.1, albeit mild in their current form, can be relaxed even further. Refining these conditions can be an interesting topic of future work, but is out of the scope of this paper. We mention in passing that the conclusions of Theorem 3.1 also hold true if we replace the two-times differentiability condition by an assumption that the loss is one-time differentiable and strictly convex.

Appendix C Fundamental Limits for Linear Models: Proofs for Section 2

Let $\mathcal{L}(\cdot)$ be a non-linear, convex and twice differentiable function, ${\lambda}>0$ and $\delta>0$ and the pair $(\alpha,\tau)$ be a solution to (3) where $\alpha>0$. Then, $0<\tau<\frac{1}{{\lambda}\delta}.$

Using Stein’s lemma (aka Gaussian integration by parts) we find that

Therefore the equation in the LHS in (3) is equivalent to

In particular, we see that equality is achieved in (46) is achieved if and only if

Finally, using Proposition A.2 to “invert" the Moreau envelope function, we find that the loss function $\mathcal{L}(\cdot)$ satisfying (47) is such that

C.2 Proof of Theorem 2.1

Fix a convex loss function $\mathcal{L}$ and regularization parameter ${\lambda}\geq 0$. Let $(\alpha>0,\tau>0)$ be the unique solution to

Then, $\alpha_{\star}>0$ as in (5) is equivalently expressed as

We are now ready to prove the main claim of the theorem, i.e.,

Denote by $\phi_{\alpha}$ the density of the Gaussian random variable $\alpha G$. We start with the following calculation:

where we have also used the fact that $\tau>0$. To continue, we use (53) to rewrite the LHS above and deduce that:

By simplifying the resulting expressions we have proved that $(\alpha,\tau)$ satisfy the following inequality:

In the remaining, we use (55) to prove (51). For the sake of contradiction to (51), assume that there exists a valid triplet $(\alpha,{\lambda},\tau)$ such that $\alpha<\alpha_{\star}$. Recall by inequality (55) that $\alpha$ satisfies:

We show first that (56) holds with strict inequality. To see this, suppose that $\Psi({\alpha},{\lambda}\,\tau)=1/\delta$. From Lemma C.1, it also holds that ${\lambda}\,\tau\in(0,1/\delta)$. Hence, the pair $(\alpha,{\lambda}\,\tau)$ is a feasible point in the minimization in (50). Combining this with optimality of $\alpha_{\star}$ lead to the conclusion that $\alpha_{\star}\geq\alpha$, which contradicts our assumption $\alpha<\alpha_{\star}$. Therefore we consider only the case where (56) holds with strict inequality i.e., $\Psi({\alpha},\,{\lambda}\tau)>1/\delta$.

To proceed, note that $\Psi(0,x)\leq 0$ for all $x\in[0,1).$ Thus, by continuity of the function $a\mapsto\Psi(a,x)$ for fixed $x\in[0,1/\delta)$:

By recalling our assumption that ${\alpha}<\alpha_{\star}$, we can deduce that (57) in fact holds for $\widetilde{\alpha}<\alpha_{\star}$. However, this is in contradiction with the optimality of $\alpha_{\star}$ defined in (50). This shows that for all achievable $\alpha$ it must hold that $\alpha\geq\alpha_{\star}$. This proves the claim in (51) and completes the proof of the theorem.

C.3 Proof of Lemma 2.1

To prove the claim of the lemma, it suffices to show that the proposed loss function and regularization parameter, satisfy the system of equations in (48) with $\alpha=\alpha_{\star}$. For this purpose we show that $(\mathcal{L},{\lambda},\alpha,\tau)=(\mathcal{L}_{\star},{\lambda}_{\star},\alpha_{\star},1)$ satisfy (48).

Thus by replacing the proposed parameters in (48a) we have :

where for the last line we used the definitions of $\alpha_{\star}$ and ${\lambda}_{\star}$ in the statement of the lemma. This proves the claim for (48a). To show that Equation (48b) is satisfied we use its equivalent expression in (53) and also replace (58) in (53). Specifically, this shows that

from which we conclude that Equation (48b) is satisfied. This completes the proof of the lemma.

C.4 Proof of Lemma 2.2

C.5 Proof of Corollary 2.1

As mentioned in the main body of the paper, the difficulty in deriving a closed-form expression for $\alpha_{\star}$ in (5) is due to the fact that in general $\mathcal{I}(V_{a})=\mathcal{I}(aG+Z)$ may not be expressible in closed-form with respect to $a$. The core idea behind this corollary is using Stam’s inequality (see Proposition A.3) to bound $\mathcal{I}(V_{a})$ in terms of $\mathcal{I}(aG)=a^{-2}$ and $\mathcal{I}(Z)$. Specifically, applying (25) to the random variables $a\,G$ and $Z$ we find that:

Substituting the RHS above in place of $\mathcal{I}(V_{a})$ in the definition of $\alpha_{\star}$ in (5), let us define $\widehat{\alpha}$ as follows:

The remaining of proof has two main steps. First, we show that

Second, we solve the minimization in (61) to yield a closed-form expression for $\widehat{\alpha}$.

Towards proving (62), note from the definition of $\alpha_{\star}$ and inequality (60) that there exists $x_{\star}\in[0,1/\delta)$ such that

Thus, the pair $(\alpha_{\star},x_{\star})$ is feasible in (61). This and optimality of $\widehat{\alpha}$ in (61) lead to (62), as desired.

The next step is finding a closed-form expression for $\widehat{\alpha}$. Based on (61) and few algebraic simplifications we have :

The last equality above is true because the fraction in the constraint in the second line is independent of $a$. Next, by minimizing with respect to the variable $x$ in (63), we reach $\widehat{\alpha}^{2}=h_{\delta}(1/\mathcal{I}(Z))$.

Finally, we know from Proposition A.3(f) that equality in (60) is achieved if and only if the noise is Gaussian i.e. $Z\sim\mathcal{N}(0,\zeta^{2})$ for some $\zeta>0$. Thus, if this is indeed the case, then $\alpha_{\star}=\widehat{\alpha}$ and the lower bound is achieved with replacing the Fisher information of $Z$ i.e, $\mathcal{I}(Z)=\zeta^{-2}$. This completes the proof of the corollary.

C.6 Proof of Equation (7)

Next, we prove the lower bound $\omega_{\delta}\geq 1-\delta$. Fix any $\delta>0$. First, it is straightforward to compute that $h_{\delta}(0)=\max\{1-\delta,0\}\geq 1-\delta.$ Also, simple algebra shows that $h_{\delta}(x)\leq 1,x\geq 0$. From these two and the increasing nature of $h_{\delta}(x)$ we conclude that $1-\delta\leq h_{\delta}(x)\leq 1$, for all $x\geq 0$. The desired lower bound follows immediately by applying these bounds to the definition of $\omega_{\delta}$.

Appendix D Fundametal Limits for Binary Models: Proofs for Section 3

D.2 Discussion on the Classification Error (12)

For the estimator ${\widehat{\mathbf{w}}}_{{\mathcal{L},{\lambda}}}$ obtained from (8), and $\mathbf{x}_{0}$ denoting the true vector with unit norm, the parameters $\mu_{{\mathcal{L},{\lambda}}}$ and $\alpha_{{\mathcal{L},{\lambda}}}$ denote the high-dimensional terms of bias and variance,

Using these, we derive the following for the classification error :

Recalling Assumption 2 we have $\mathbf{a}\sim\mathcal{N}\left(\mathbf{0},\,\mathbf{I}\right)$. Thus by denoting S,G\mathrel{\overset{\text{\small{iid}}}{\scalebox{1.5}[1.0]{\sim}}}\mathcal{N}(0,1) and assuming without loss of generality that $\mu_{\mathcal{L},{\lambda}}>0$, we derive (12).

This shows the desired. Importantly, we remark that in view of (64), this condition on the density of $Sf(S)$ is satisfied for many well-known binary models including Logistic, Probit and Signed.

D.3 Proof of Theorem 3.2

We need the following auxiliary result, which we prove first.

Fix $\delta>0$ and ${\lambda}>0$ and let $\mathcal{L}$ be a convex, twice differentiable and non-linear function. Then all solutions $\tau$ of the system of equations in (44) satisfy $0<\tau<\frac{1}{{\lambda}\delta}$.

The proof follows directly from the proof of Lemma C.1 by replacing $Z$ with $\mu\,Sf(S)$. Note that the Equation (44c) can be obtained by replacing $Z$ with $\mu Sf(S)$ in Equation (48b). ∎

Then, $\sigma_{\star}$ as in (13) is equivalently expressed as:

But, by Lemma A.2, $\lim_{s\rightarrow 0}\;\;s^{2}\,\mathcal{I}(W_{s})=0$ and $\lim_{s\rightarrow+\infty}s^{2}\,\mathcal{I}(W_{s})=1$. Using these, we can show that $\lim_{s\rightarrow 0}\;\;\Phi_{0}(s)=+\infty$ and $\lim_{s\rightarrow+\infty}\;\;\ \Phi_{0}(s)=0$. Combined with (69), we find that $\lim_{s\rightarrow 0}\;\;\Phi_{0}(s)=+\infty$ and $\lim_{s\rightarrow+\infty}\;\;s^{2}\,\mathcal{I}(W_{s})=0$. This concludes the proof of feasibility of the minimization in (67).

We are now ready to prove the main claim of the theorem. Fix convex loss function $\mathcal{L}$ and regularization parameter ${\lambda}\geq$. Let $(\alpha>0,\mu,\tau>0)$ be the unique solution to (44) and denote $\sigma=\alpha/\mu$. We will prove that

The first step in the proof will be to transform the equations (44) in a more appropriate form. In order to motivate the transformation, note that the performance of the optimization problem in (8) is unique up to rescaling. In particular consider the following variant of the optimization problem in (8) :

It is straightforward to see that, regardless of the values of $c_{{}_{1}}$ and $c_{{}_{2}}$, ${\rm{corr}}\left(\,{{\widehat{\mathbf{w}}}_{{\mathcal{L},{\lambda}}}}\,,\,{\mathbf{x}_{0}}\,\right)={\rm{corr}}\left(\,{\widehat{\mathbf{v}}_{{\mathcal{L},{\lambda}}}}\,,\,{\mathbf{x}_{0}}\,\right)$, where recall that $\widehat{\mathbf{w}}_{{\mathcal{L},{\lambda}}}$ solves (8). Thus in view of (9), we see that the error $\sigma$ resulting from $\widehat{\mathbf{w}}_{{\mathcal{L},{\lambda}}}$ and $\widehat{\mathbf{v}}_{{\mathcal{L},{\lambda}}}$ are the same. Motivated by this observation, we consider the following rescaling for the loss function and regularization parameter:

From standard properties of Moreau-envelope functions it can be shown that

Using these transformations, we can rewrite the system of equations (44) in terms of $\sigma$, $\widetilde{\mathcal{L}}$ and $\widetilde{{\lambda}}$ as follows:

where we denote $W_{\sigma}:=\sigma G+Sf(S).$

Next, we further simplify (72) as follows. Similar to the procedure leading to (52), here also we may deduce that,

Additionally, we linearly combine (72a) and (72c) (with coefficient $\sigma$) to yield :

Putting together (72b), (73) and (74), we have shown that $\sigma$ satisfies the following system of equations:

Applying Cauchy-Schwarz inequality to the LHS of (76) gives :

Now, we choose the coefficients $\beta_{{}_{1}}$ and $\beta_{{}_{2}}$ as follows: $\beta_{{}_{1}}=1-\widetilde{{\lambda}}\delta-(\sigma^{2}-\sigma^{2}\widetilde{{\lambda}}\delta-\widetilde{{\lambda}}\delta)\,\mathcal{I}(W_{\sigma})$ and $\beta_{{}_{2}}=1$. (We show later in Theorem 3.1, that this choice lead to an achievable lower bound). Substituting these values in (78) and simplifying the resulting expressions yield the following inequality for $\sigma$:

We will now finish the proof of the theorem by using (79) to prove (70). For the sake of contradiction to (70), assume that $\sigma<\sigma_{\star}$. From (79) and the notation introduced in (67), we have shown that $\Phi\,(\sigma,\widetilde{{\lambda}})\leq 1$. Recall from (71) that $\widetilde{{\lambda}}={\lambda}\tau$. But, from Lemma D.1 it holds that $\widetilde{{\lambda}}={\lambda}\tau<\frac{1}{\delta}$. Therefore, the pair $(\sigma,\widetilde{{\lambda}})$ is feasible in the minimization problem in (68). By this, optimality of $\sigma_{\star}$ and our assumption that $\sigma<\sigma_{\star}$ in (68) it must hold that $\Phi\,({\sigma},\widetilde{{\lambda}})<1.$ But then, since $\lim_{s\rightarrow 0}\Phi\,(s,\widetilde{{\lambda}})=+\infty$ and by continuity of the function $\Phi(\cdot,x)$ for all fixed $x\in[0,1/\delta)$, we have:

Therefore $\Phi(\sigma_{1},\widetilde{{\lambda}})=1$ for $\sigma_{1}<\sigma_{\star}$, which contradicts the optimality of $\sigma_{\star}$ in (68) and completes the proof.

D.4 Proof of Lemma 3.1

To prove the claim of the lemma we show that the proposed candidate-optimal loss and regularization parameter pair $(\mathcal{L}_{\star},{\lambda}_{\star})$ satisfies the system of equations in (44) with $(\alpha,\mu,\tau)=(\sigma_{\star},1,1)$. In line with the proof of Theorem 3.2 and the equivalent representation of (75) for the equations in (44), we show that $(\mathcal{L}_{\star},{\lambda}_{\star})$ satisfy all three equations in (75) with $(\sigma,\mu,\tau)=(\sigma_{\star},1,1).$ We emphasize that since $\mu=\tau=1$, based on (71) the $\mathcal{L}_{\star}$ and ${\lambda}_{\star}$ remain the same under these changes of parameters thus $(\widetilde{\mathcal{L}}_{\star}(\cdot),\widetilde{{\lambda}}_{\star})=(\mathcal{L}_{\star},{\lambda}_{\star})$.

Note that we need $\mathcal{M}_{\mathcal{L}}(\cdot)$ to be able to assess the equations in (75). For this purpose we use inverse properties of Moreau-envelope functions in Proposition A.2 to derive the following from the definition of $\mathcal{L}_{\star}$ in (15) :

where for the last step, we replaced $\eta$ according to the statement of the lemma.

Similarly, for the second equation (75b), we begin with replacing the expression for $\mathcal{M}^{\prime}_{{\mathcal{L}_{\star}},1}\left({W_{\star}};{1}\right)$ to see that

After replacing $\eta$, we can simplify (81) to reach the following

where the last two steps follow from the definition of $\sigma_{\star}$ in (13) and $\Phi(\cdot,\cdot)$ in (67).

For the third Equation (75c) we deduce in a similar way that

confirming the RHS of Equation (75c). This completes the proof.

D.5 Proof of Lemma 3.2

D.6 Proof of Corollary 3.1

The proof is analogous to the proof of Corollary 2.1. Here again we use Stam’s inequality in Proposition A.3 to provide a bound for $\mathcal{I}(W_{\sigma})=\mathcal{I}(\sigma G+Sf(S))$ based on $\mathcal{I}(\sigma G)=\sigma^{-2}$ and $\mathcal{I}(Sf(S))$. First we define

Next we use Stam’s inequality to deduce that :

We can use this inequality in the constraint condition of $\sigma_{\star}$ in (13) to deduce that:

Thus we find that $(\sigma,x)=(\sigma_{\star},{\lambda}_{\star})$ is a feasible solution of the constraint in (82), resulting in :

To complete the proof of the theorem, we need to find the closed-form $\widehat{\sigma}$. Proceeding from (82) we derive the following

The first line follows by algebraic simplifications in (82). The second line is true since by Cramer-Rao bound (see Proposition A.3 (d)) $\mathcal{I}(Sf(S))\geq(Var[Sf(S)])^{-1}$; thus $\mathcal{I}(Sf(S))\geq 1$. Noting that the right hand-side of the inequality is independent of $\sigma$ and can take positive values for some $x\geq 0$ we conclude the last line. Optimizing with respect to the non-negative variable $x$ in the last line completes the proof and yields the desired result in the statement of the corollary.

Appendix E Comparison to a Simple Averaging Estimator

In this section, we compare the performance of optimally ridge-regularized ERM to the following simple averaging estimator

Moreover, it is not hard to check that the correlation performance of ${\widehat{\mathbf{w}}}_{\rm ave}$ is the same as that of the solution of RLS with regularization ${\lambda}$ approaching infinity.

It is in fact possible to exploit these relations of the estimator to the RERM family in order to evaluate its asymptotic performance using the machinery of this paper (i.e., by using the Equations (10)). However, a more direct evaluation that uses the closed form expression in (85) is preferable here. In fact, it can be easily checked that the following limit is true in the high-dimensional asymptotic regime:

A favorable feature of ${\widehat{\mathbf{w}}}_{\rm ave}$ is its computational efficiency. In what follows, we use our lower bounds on the performance of general RERM estimators, to evaluate its suboptimality gap compared to more complicated alternatives. To begin, in view of (86) and (9) let us define the corresponding “effective error parameter"

First, we compare this value with the error of regularized LS. Let ${\widehat{\mathbf{w}}}_{\rm LS}$ be the solution to unregularized LS for $n>m$. It can be checked (e.g., [TAH15]) that

Directly comparing this to (87), we find that \frac{\sigma^{2}_{\rm LS}}{\sigma^{2}_{\rm ave}}=\Big{(}\frac{1}{1-1/\delta}\Big{)}\,\big{(}1-\nu_{f}^{2}\big{)}, for all $\delta>1$. In other words,

Next, we study the performance gap of the averaging estimator from the optimal RERM. For this, we use Corollary 3.1 to compare $\sigma^{2}_{\rm ave}$ to the lower bound $\sigma_{\star}$. We find that for any $\delta>0$ and any link function $f$ satisfying the assumptions of Corollary 3.1:

We complement these bounds with numerical simulations in Section G.

Appendix F Gains of Regularization

In this section, we study the impact of the regularization parameter on the best achievable performance. For this purpose, we compare $\alpha_{\star}$, the best achievable performance of ridge-regularized case, to the best achievable performance among non-regularized empirical risk minimization with convex losses denoted by $\alpha_{\rm ureg}$. By definition of $\alpha_{\rm ureg}$, for all convex losses $\mathcal{L}$, in the regime of $\delta>1$ it holds that, $\alpha_{\rm ureg}\;\leq\;\alpha_{{\mathcal{L},\,0}}.$ In [BBEKY13], the authors compute a tight lower bound on $\alpha_{\rm ureg}$ and show that it is attained provided that $p_{Z}$ is log-concave. Our next result bounds the ratio $\alpha_{\star}^{2}\,/\,\alpha_{{}_{\rm ureg}}^{2}$, illustrating the impact of regularization for a wide range of choices of $Z\sim\mathcal{D}$ and any $\delta>1$.

Let the assumptions of Corollary 2.1 hold and $\delta>1$. Then it holds that:

In order to obtain an upper bound for $\alpha_{\star}^{2}/\alpha_{\rm ureg}^{2}$ first we find a lower bound for $\alpha_{\rm ureg}^{2}$. We have

thus we may apply the Stam’s inequality (as stated in Proposition A.3(f)) for $\mathcal{I}(V_{\alpha_{{}_{\rm ureg}}})$ to derive the following lower bound :

This combined with the result of Corollary 2.1 derives the lower bound in the statement of the corollary and completes the proof. ∎

Importantly, based on (91) we find that as $\delta\rightarrow 1$ the ratio $\alpha_{\star}^{2}\,/\,\alpha_{{\,\rm ureg}}^{2}$ reaches zero, implying the large gap between $\alpha^{\star}$ and $\alpha_{{\,\rm ureg}}$ in this regime. In the highly under-parameterized regime where $\delta\rightarrow\infty$, by computing the limit in the lower bound our bound gives

F.2 Binary models

In order to demonstrate the impact of regularization on the performance of ERM based inference, we compare $\sigma_{\star}$ with the optimal error of the non-regularized ERM for $\delta>1$ which we denote by $\sigma_{\rm ureg}$. Thus $\sigma_{\rm ureg}$ satisfies for all convex losses that $\sigma_{\rm ureg}\leq\sigma_{\mathcal{L},0}$. The general approach for determining $\sigma_{{\rm ureg}}$ is discussed in [TPT20] in which the authors also show the achievability of $\sigma_{{\rm ureg}}$ for well-known models such as the Signed and Logistic models.

Our next result quantifies the gap between $\sigma_{{\rm ureg}}$ and $\sigma_{\star}$ in terms of the label functions $f$ and $\delta>1$.

To provide the bounds of the ratio $\sigma_{\star}^{2}/\sigma_{{}_{\rm ureg}}^{2}$, we follow a similar argument stated in the proof of Corollary F.1. First, we use the result in [TPT20] which states that for $\sigma_{\rm ureg}^{2}$ and all $\delta>1$ it holds that

Additionally since it trivially holds that $\sigma_{\star}^{2}\leq\sigma_{\rm ureg}^{2}$ we conclude the upper bound in the statement of the corollary. We proceed with proving the lower bound in the statement of the corollary. For this purpose, first we derive an upper bound for $\sigma_{\rm ureg}^{2}$. Using the fact that $\sigma_{{}_{\rm ureg}}^{2}$ satisfies :

as well as the Cramer-Rao lower bound (Proposition A.3(d)) for $\mathcal{I}(W_{\rm ureg})$ we may deduce that :

This combined with the lower bound on $\sigma_{\star}^{2}$ as stated in Corollary 3.1 proves the lower bound in the statement of the corollary and completes the proof. ∎

Importantly, as shown by (94), in the case of $\delta$ being close to 1, one can see that both of the bounds in (94) vanish. This shows the large gap between $\sigma_{{\rm ureg}}$ and $\sigma_{\star}$ and further implies the benefit of regularization in this regime. When $\delta\rightarrow\infty$ i.e. in the highly under-parameterized regime, by deriving the limits as well as using Proposition A.3 (d), we see that (94) yields:

Thus in this case both the values of $\sigma_{\star}$ and $\sigma_{\rm ureg}$ are approaching zero with the ratio depending on the properties of $Sf(S)$. For models such as Logistic with small signal strength (i.e. small $\|\mathbf{x}_{0}\|$) where $\mathcal{I}(Sf(S))\approx 1/(1-\nu_{f}^{2})$, one can derive that based on (99) the ratio reaches 1, which confirms the intuition that for large values of $\delta$ the impact of regularization is almost negligible.

Appendix G Additional Experiments

In this section, we present additional numerical results comparing the bounds of Theorems 2.1 and 3.2 to the performance of the following: (i) Ridge-regularized Least-Squares (RLS); (ii) optimal unregularized ERM (Section F); (iii) a simple averaging estimator (see Section E). Figure 2(Top Left) plots the asymptotic squared error $\alpha^{2}$ of these estimators for linear measurements with $Z\sim\texttt{Laplace}(0,2)$. Similarly, Figure 2(Top Right) and Figure 2(Bottom) plot the effective error term $\sigma$ for Logistic data with $\|\mathbf{x}_{0}\|_{2}=1$, and the limiting value $\rho$ of the correlation measure for Logistic data with $\|\mathbf{x}_{0}\|_{2}=10$, respectively. The red squares represent the performance of optimally tuned ERM (as per Lemmas 2.1 and 3.1) derived numerically by running GD, as previously described in the context of Figure 1.

The numerical findings in Figures 1 and 2 validate the theoretical findings of Sections 2.3 and 3.3, regarding sub-optimality of RLS for Laplace noise and Logistic binary model (with large $\|\mathbf{x}_{0}\|$) and optimality of ${\lambda}$-tuned RLS for Logistic model with small $\|\mathbf{x}_{0}\|$. Furthermore, by comparing the optimal performance of unregularized ERM to the optimal errors of RERM in both Figures 1 and 2, we confirm the the theoretical guarantees of Section F regarding the impact of regularization in the regime of small $\delta$ for both linear and binary models.

Figure 3 depicts the candidate for optimal loss function derived in Lemmas 2.1 and 3.1, for specific linear and binary models discussed in this paper. To allow for a direct comparison with the least-squares loss function, the optimal losses for the linear models are shifted such that $\mathcal{L}_{\star}\geq 0$ and rescaled such that $\mathcal{L}_{\star}(1)=1$. Similarly, for the Logistic model with $\|\mathbf{x}_{0}\|=1$, the optimal loss is rescaled such that $\mathcal{L}_{\star}(1)=0$ and $\mathcal{L}_{\star}(2)=1$. Interestingly, for this model, $\mathcal{L}_{\star}$, when rescaled (which results in no change in performance by appropriately rescaling ${\lambda}_{\star}$) is similar to the least-squares loss. This confirms the (approximate) optimality of optimally-tuned RLS for this model and further verifies the numerical observations in Figure 2 (Top Right) and the theoretical guarantees of Section 3.3 for this model.