A Model of Double Descent for High-dimensional Binary Linear Classification

Introduction

Modern learning architectures are chosen such that the number of training parameters overly exceeds the size of the training set. Despite their increased complexity, such over-parametrized architectures are known to generalize well in practice. In principle, this contradicts conventional wisdom of the so-called approximation-generalization tradeoff. The latter suggests a U-shaped curve for the generalization error as a function of the number of parameters, over which the error initially decreases, but increases after some point due to overfitting. In contrast, several authors uncover a peculiar W-shaped curve for the generalization error of neural networks as a function of the number of parameters. After the “classical” U-shaped curve, it is seen that a second approximation-generalization tradeoff (hence, a second U-shaped curve) appears for large enough number of parameters. The authors of [BMM18, BHMM18, BHM18] coin this the “double-descent” risk curve. The double-descent phenomenon has been demonstrated experimentally for decision trees, random features and two-layer neural networks (NN) in [BHMM18] and, more recently, for deep NNs (including ResNets, standard CNNs and Transformers) in [NKB+19]; see also [SGd+19, GJS+19] for similar observations.

Recent efforts towards theoretically understanding the phenomenon of double descent focus on linear regression with Gaussian features [HMRT19, MVS19, BHX19, BLLT19]; also [BRT18, XH19, MM19, KLS19] for related efforts. These works investigate how the generalization error of gradient descent (GD) on square-loss depends on the overparameterization ratio $\kappa=p/n$, where $p$ number of features used for training are divided by the size $n$ of the training set. On one hand, when $\kappa<1$, GD iterations converge to the least-squares solution for which the generalization performance is well-known [HMRT19]. On the other hand, in the overparameterized regime $\kappa>1$, GD iterations converge to the min-norm solution for which the generalization performance is sharply characterized in [HMRT19, BHX19, MVS19] using random matrix-theory (RMT). Using these sharp asymptotics, these papers identify regimes (in terms of model parameters such as the signal-to-noise ratio (SNR)) for which a double-descent curves appear.

This paper investigates the dependence of the classification error on the overparameterization ratio in binary linear classification with Gaussian features. In short, we obtain results that parallel previous studies for linear regression [HMRT19, BHX19, MVS19]. In more detail, we study gradient descent on logistic loss for two simple, yet popular, models: logistic model and gaussian mixtures (GM) model. Known results establish that GD iterations converge to either the support-vector machines (SVM) solution or the logistic maximum-likelihood (ML) solution, depending on whether the training data is separable or not. For the proposed learning model, we compute a phase-transition threshold $\kappa_{\star}\in(0,1/2)$ and show that when problem dimensions are large, then data are separable if and only if $\kappa>\kappa_{\star}$. Connecting the two, we redefine our task to that of studying the classification performance of the ML and SVM solutions. In contrast to linear regression, where the corresponding task can be accomplished using RMT, here we employ a machinery based on Guassian process inequalities. In particular, we obtain sharp asymptotics using the framework of the convex Gaussian min-max theorem (CGMT) [Sto13, TOH15, TAH18]. Finally, we corroborate our theoretical findings with numerical simulations and build on the former to identify regimes where double descent occurs. Figure 1 contains a pictorial preview of our findings The y-axis represents excess risk $\mathcal{R}_{\rm excess}:=\mathcal{R}-\mathcal{R}_{\rm best}$ defined as the the difference of the absolute expected risk $\mathcal{R}$ minus the risk of the best linear classifier $\mathcal{R}_{\rm best}$ (see Eqn. (7)). Naturally both $\mathcal{R}$ and $\mathcal{R}_{\rm best}$ are decreasing functions of the SNR parameter $r$. However, $\mathcal{R}_{\rm best}$ is decreasing faster than $\mathcal{R}$. This explains why the value of the excess risk $\mathcal{R}_{\rm excess}$ is smaller for larger values of the signal strength $r$ in Figure 1. In particular, it holds $\mathcal{R}_{\rm best}=$ 0.133, 0.098 and 0.084 for $r=$ 5, 10 and 25, respectively. Contrast this to the values of the absolute risk $\mathcal{R}=$ 0.434, 0.429 and 0.428 at (say) $\kappa=0.05$. .

On a technical level, we provide useful extensions of the CGMT that allow: (a) studying feasibility questions (such as, when is the hard-margin SVM optimization feasible?); (b) raising certain boundedness assumption on the CGMT that were previously circumvented on a case-by-case analysis; (c) establishing almost-sure convergence results (rather than “in probability”). While our motivation comes from the analysis of the hard-margin SVM, we believe that these extensions can be of independent interest offering a principled way for future statistical studies of related optimization-based inference algorithms. We present these extensions of the CGMT as self-contained theorems in Appendix A.2.

1 Related works

Our results on the performance of logistic ML and SVM fit in the rapidly growing recent literature on sharp asymptotics of (possibly non-smooth) convex optimization-based estimators; [DMM11, BM12, Sto13, OTH13, TOH15, DM16, TAH18, EK18] and many references therein. Most of these works study linear regression models, for which the CGMT framework has been shown to be powerful and applicable under several variations; see for example [TAH18, TXH18, CM19, HL19, JSH20]. We also mention a parallel line of work that uses an alternative analysis framework based on the Approximate Message Passing (AMP) (e.g [DMM11, BM12, WWM19, BKRS19, RV18, Ran11]); a detailed comparison between the two frameworks is out of the scope of this paper.

In contrast to the above mentioned studies of linear regression models, our results hold for binary classification. To the best of our knowledge, the first asymptotically sharp analysis of convex-based methods for binary models is due to [TAH15], which computes the squared-error of regularized least-squares under nonlinearities. The simple, yet central idea, which allows for an application of the CGMT in this setting, is a certain “projection trick” inspired by [PV15] (also used in [Gen16]). (A similar idea was also applied in [DTL18] for the analysis of the PhaseMax algorithm for phase-retrieval.) However, [TAH15] is not focused on binary classification.

In this context, the first relevant results are due to [CS18, SC19], who perform a detailed study of logistic regression under the logistic data model using the approximate kinematic formula [ALMT13] and the AMP. Soon after the works of Candes and Sur, [SAH19] and [TPT19, TPT20] have used the CGMT to analyze the statistical properties of regularized logistic regression and of general convex empirical-risk-minimization (ERM), respectively. The paper [KA20], while still using the CGMT, focuses on a discriminative (rather than a generative) data model and studies the hard-margin SVM classifier. While there are a few other recent works on sharp asymptotics of binary linear classification [MLC19b, MLC19a, Hua17], the papers [KA20, TPT20, SAH19, CS18, SC19] are the most closely related to this work.

Compared to these, our contribution differs as follows. First, we examine risk curves for all possible values of the overparameterization ratio, which gives rise to the phase-transition of Proposition 3.1 and the double-descent phenomena investigated in Section 4. Second, we propose and study the misspecified model for classification of Section 2.2. Third, we derive results that treat both the logistic generative model and the GM discriminative model in a unifying way. On a technical level: (i) we properly apply the CGMT to study feasibility of the hard-margin SVM (previous results focus on feasible optimization problems); (ii) we establish convergence results that hold almost surely (the CGMT establishes convergence in probability); (iii) we prove existence and uniqueness to the solution of the equations derived in Propositions 3.2 and 3.3. Importantly, compared to [KA20], which also studies feasibility and almost-sure convergence of hard-margin SVM, we formulate our ideas as stand-alone results and prove them in more general settings such that they can be used beyond the context of our paper.

An early conference version of this paper appears in [DKT20]. After the initial submission and while preparing a long version of the paper we became aware of the parallel work [MRSY19]. Very similar to our setting, [MRSY19] investigates the classification performance of hard-margin SVM for binary linear classification under generative data models. In contrast to [MRSY19], we also analyze the performance of logistic ML. This allows us to generate risk curves for all positive values of the overparametrizatio ratio $\kappa>0$ and explicitly demonstrate and study the presence of double-descent phenomena. We also extend our study to the discriminative Gaussian mixture model. On the other hand, it is worth mentioning that the authors of [MRSY19] further derive asymptotic predictions for correlated (not necessarily iid) Gaussian features. While both papers build their asymptotic analysis on the CGMT, there are several differences when it comes to the technical analysis of the Auxiliary Optimization (AO) problem of the CGMT In this paper, we analyze the formulation of the hard-margin SVM in (9). In contrast, the authors of [MRSY19] consider a re-formulation of the SVM (see [SSBD14, Eqn. 15.1]) that even-though is equivalent, it leads to a different AO problem.. Overall, we believe that both contributions are of independent interest.

Learning model

We study supervised binary classification under two popular data models,

a discriminative model: mixtures of Gaussian.

Logistic model. First, we consider a discriminative approach which models the marginal probability $p(y|\mathbf{x})$ as follows:

Throughout, we assume iid Gaussian feature vectors $\mathbf{x}\sim\mathcal{N}(0,\mathbf{I}_{d}).$ For compactness let ${\rm{Rad}}\left(p\right)$ denote a symmetric Bernoulli distribution with probability $p$ for the value $+1$ and probability $1-p$ for the value $-1$. We summarize the logistic model with Gaussian features:

2 Feature selection model for training data

During training, we assume access to $n$ data points generated according to either (1) or (2). We allow for the possibility that only a subset ${\mathcal{S}}\subset[d]$ of the total number of features is known during training. Concretely, for each feature vector $\mathbf{x}_{i},~{}i\in[n]$, the learner only knowns a sub-vector $\mathbf{w}_{i}:=\mathbf{x}_{i}({\mathcal{S}}):=\{\mathbf{x}_{i}(j),~{}j\in{\mathcal{S}}\},$ for a chosen set ${\mathcal{S}}\subset[d]$. We denote the size of the known feature sub-vector as $p:=|{\mathcal{S}}|$. We will often refer to $p$ as the model size. Onwards, we choose ${\mathcal{S}}=\{1,2,\ldots,p\}$ This assumption is without loss of generality for our asymptotic model specified in Section 3.1., i.e., select the features sequentially in the order in which they appear.

Clearly, $1\leq p\leq d$. Overall, the training set ${\mathcal{T}}({\mathcal{S}})$ consists of $n$ data pairs:

if the training set ${\mathcal{T}}$ is generated according to (1) or (2), respectively.

3 Classification rule

The estimate $\mathbf{\boldsymbol{\beta}}_{\star}$ is obtained by minimizing the empirical risk:

for step-size $\eta_{k}>0$ and arbitrary $\boldsymbol{\beta}_{(0)}$. We run GD until convergence and set

Classification error. For a new sample $(\mathbf{x},y)$ we measure test error of $\hat{y}$ by the expected risk (or, test error):

Here, $\mathds{1}(\mathcal{E})$ denotes the indicator function of an event $\mathcal{E}$. Also, the expectation here is over the distribution of the new data sample $(\mathbf{x},y)$ generated according to either (1) or (2). In particular, note that $\mathcal{R}(\mathbf{\boldsymbol{\beta}}_{\star})$ is a function of the training set ${\mathcal{T}}$. Along these lines, we also define the excess risk:

Training error. The training error of $\boldsymbol{\beta}_{\star}$ is given by

4 Implicit bias of GD

Recent literature fully characterizes the converging behavior of GD iterations for logistic loss [JT19, SHN+18, Tel13]. There are two regimes of interest:

When data are such that $\widehat{\mathcal{R}}_{\rm emp}(\boldsymbol{\beta})$ is strongly convex, then standard tools show that $\boldsymbol{\beta}_{(k)}$ converges to the unique bounded minimizer of $\widehat{\mathcal{R}}_{\rm emp}(\boldsymbol{\beta})$.

When data are linearly separable, then the normalized iterates $\boldsymbol{\beta}_{(k)}/\|\boldsymbol{\beta}_{(k)}\|_{2}$ converge to the max-margin solution.

These deterministic properties guide our approach towards studying the classification error of the converging point of GD for logistic loss in Section 3. Specifically, instead of studying GD iterations directly, we study the classification performance of the max-margin classifier and of the minimum of the empirical logistic risk. We formalize these ideas next.

The training set is separable if and only if there exists a linear classifier achieving zero training error, i.e., $\exists\boldsymbol{\beta}~{}:~{}y_{i}\mathbf{w}_{i}^{T}\boldsymbol{\beta}\geq 1,~{}\forall i\in[n].$ When data are separable, the normalized iterations of GD for logistic loss converge to the maximum margin classfier [SHN+18, JT19]. Precisely, for $k\rightarrow\infty$ it holds \Big{\|}\frac{\boldsymbol{\beta}_{(k)}}{\|\boldsymbol{\beta}_{(k)}\|_{2}}-\frac{\boldsymbol{\widehat{\beta}}}{\|\boldsymbol{\widehat{\beta}}\|_{2}}\Big{\|}_{2}\rightarrow 0, where $\boldsymbol{\widehat{\beta}}$ is the solution to the hard-margin SVM:

4.2 Non-separable data

When the separability condition does not hold, then $\widehat{\mathcal{R}}_{\rm emp}(\beta)$ is coercive. Thus, its sub-level sets are closed and GD iterations will converge [JT19] to the minimizer $\boldsymbol{\widehat{\beta}}$ of the empirical loss:

Sharp Asymptotics

We present sharp asymptotic formulae for the classification performance of GD iterations for the logistic loss under the learning model of Sections 2.1 and 2.2 and the linear asymptotic setting presented in Section 3.1. Our analysis sharply predicts the limiting behavior of the test error and of the cosine similarity as a function of the model size, i.e., the number of parameters $p$ used for training.

The first key step of our analysis, makes use of the convergence results discussed in Section 2.4 that relate GD for logistic loss to the convex programs (10) and (9) depending on whether the training data ${\mathcal{T}}$ are linearly separable. Specifically, we show in Section 3.2 that, in the linear asymptotic regime with Gaussian features, the convergence behavior of GD as a function of the model size, undergoes a sharp phase-transition for both data models (logistic and Gaussian-mixtures). The boundary of the phase-transition separates the so-called under- and over-parameterized regimes. Thus, for each one of the two corresponding regimes, GD converges to an associated convex program (cf. (10) and (9), respectively). The second key step of our analysis, uses the Convex Gaussian min-max Theorem (CGMT) [TOH15, TAH18] to sharply evaluate the classification performance of these convex programs in Section 3.3. Specifically, we build on a useful extension of the CGMT, which we present in Appendix A.2. The proofs of the results presented in this sections are deferred to the Appendix.

$\bullet$ $d$: dimension of the ambient space, $\bullet$ $n$: size of the training set, $\bullet$ $p$: number of parameters used in training (aka model size).

Our asymptotic results hold in a linear asymptotic regime where $n,d,p\rightarrow+\infty$ such that

Above and throughout the paper, for a sequence of random variables $\mathcal{X}_{n,p,d}$ that converges almost-surely (resp., in probability) to a constant $c$ in the limit of (11), we write $\mathcal{X}_{n,p,d}\xrightarrow[]{a.s.}c$ (resp. $\mathcal{X}_{n,p,d}\stackrel{{\scriptstyle{P}}}{{\rightarrow}}c$).

The parameters $s\in[0,r]$ and $\sigma$ in (12) can be thought of as the useful signal strength and the noise strength, respectively. Our notation specifies that $s(\kappa)$ (hence also, $\sigma(\kappa)$) is a function of $\kappa$. We are interested in functions $s(\kappa)$ that are increasing in $\kappa$ such that the signal strength increases as more features enter into the training model; see Section 4.1 for explicit parameterizations. For each triplet $(n,d,p)$ in the sequence of problems that we consider, the corresponding training set ${\mathcal{T}}={\mathcal{T}}(\{1,2,\ldots,p\})$ follows (3).

2 Regimes of learning: Phase-transition

As discussed in Section 2.4, the behavior of GD changes depending on whether the training data is separable or not. The following proposition establishes a sharp phase-transition characterizing the separability of the training data under the data model of Section 2.

We reserve the following notation for random variables $G,H,Z$ and $Y_{r,s}$

Fix total signal strength $r$ and let $s(\kappa)\in(0,r]$ be an increasing function of $\kappa\in(0,\zeta]$. For a training set ${\mathcal{T}}$ that is generated by either of the two models in (1) or (2) such that (12) is satisfied, consider the event

under which the training data is separable. Recall from (3) that for all $i\in[n]$, \mathbf{w}_{i}=\mathbf{x}_{i}\big{(}\{1,\ldots,p\}\big{)} are the $p$ (out of $d$) features that are used for training. Recall the notation in (13) and define a random variable $V_{r,s(\kappa)}$ depending on the data generation model as follows

Let $\kappa_{\star}\in[0,1/2]$ be the unique solution to the equation $g(\kappa)=\kappa$. Then, the following holds regarding $\mathcal{E}_{\rm{sep}}$:

Put in words: the training data is separable iff $\kappa>\kappa_{\star}$. When this is the case, then the training error $\mathcal{R}_{\rm train}$ can be driven to zero and we are in the interpolating regime. In contrast, the training error is non-vanishing for smaller values of $\kappa$.

In the case of the GM model, the threshold function $g(\kappa)$ takes a simple form as follows. First, assume ${\mathcal{T}}\sim\eqref{eq:yi_GM}$ and substitute the value of $V=G+s$ in (15). Then, using the fact that $G$ and $H$ are independent Gaussians the threshold function simplifies to:

The proposition above is an extension of the phase-transition result by Candes and Sur [CS18] for the noiseless logistic model. Specifically, we extend their result to the noisy setting (to accommodate for the feature selection model in Section 2.2) as well as to the Gaussian mixtures model. Our analysis approach and proof technique are also very different to [CS18]. Both approaches bare intimate connections and are motivated by corresponding results on sharp phase-transitions in compressed sensing [Sto09, CRPW12, ALMT13]. On the one hand, the proof in [CS18] is based on a purely geometric argument and specifically on an appropriate application of the approximate kinematic formula of [ALMT13]. This leads to a non-asymptotic characterization of the phase-transition. On the other hand, in this paper, we follow an approach that is based on Gaussian process inequalities [RV06, Sto09, CRPW12, Sto13, OTH13] and specifically on the Convex Gaussian min-max Theorem (CGMT) [TOH15]. Our idea is exploiting the fact that data is linearly separable iff the solution to hard-margin SVM (9) is bounded. Based on this, we are able to appropriately use the CGMT in order to show that the minimization (9) is bounded almost surely iff $\kappa>\kappa_{\star}$. Previous applications of the CGMT have almost entirely focused on feasible minimization problems. In this work, we formulate Theorem A.1 in Appendix A.2 as a useful corollary of the CGMT to further allow the study of feasibility questions. We anticipate that the theorem proves useful in other settings beyond the specifics considered in this paper. The detailed proof of Proposition 3.1 is given in Appendix C.2.

3 High-dimensional asymptotics

Recall that we use $\xrightarrow[]{a.s.}$ to denote almost sure convergence in the limit of (11). Also, we denote the proximal operator of the logistic loss as follows,

Fix total signal strength $r$ and overparameterization ratio $\kappa<\kappa_{\star}$. Denote $s=s(\kappa)\in(0,r]$. With these, consider a training set ${\mathcal{T}}$ that is generated by either of the two models in (1) or (2). Let $\boldsymbol{\widehat{\beta}}$ be given as in (10). Recall the notation in (13) and define a random variable $V=V_{r,s}$ depending on the data generation model as in (14). Let $(\mu,\alpha>0,{\lambda}>0)$ be the unique solution to the following system of three nonlinear equations in three unknowns,

When data is generated according to (2), then $V=G+s$. Using this and Gaussian integration by parts, the system of three equations in (17) simplifies to the following:

The performance of logistic loss under the logistic model was recently studied in [SC19, SAH19, TPT19]. Compared to this prior work: (i) our result extends to the mismatch model of Section 2; (ii) we obtain a prediction for the classification error; (iii) we prove convergence in an almost-sure sense (rather than with probability 1 as in previous works). Also, to the best of our knowledge, this work is the first to formally prove uniqueness and existence of solutions to (17) under non-separable data. Our proof is based on an extension of the CGMT presented as Corollary A.1 in Appendix A.2. The proof of Proposition 3.2 is given in Appendix F.

3.2 Separable data

Here, we characterize the asymptotic generalization performance of hard-margin SVM under both models (1) and (2).

Fix total signal strength $r$ and overparameterization ratio $\kappa<\kappa_{\star}$. Denote $s=s(\kappa)\in(0,r]$. With these, consider a training set ${\mathcal{T}}$ that is generated by either of the two models in (1) or (2). Let $\boldsymbol{\widehat{\beta}}$ be given as in (9). Recall the notation in (13) and define a random variable $V=V_{r,s}$ depending on the data model as in (14). With these, define

Let $q^{\star}$ be the unique solution of the equation

Further let $\rho^{\star}$ be the unique minimum of $\eta(q^{\star},\rho)$ for $\rho\in$. Then,

In addition to the stated results in Proposition 3.3, our proof further shows that the optimal cost of the hard-margin SVM (9) converges almost surely to $q^{\star}$. In other words, the margin $1/\|\boldsymbol{\widehat{\beta}}\|_{2}$ of the classifier converges in probability to $1/q^{\star}$. The dertailed proof of Proposition 3.3 is given in Appendix C.3.

We note that under the GM model, the function $\eta$ in Proposition 3.3 simplifies to:

where the expectation is over a single Gaussian random variable $G\sim\mathcal{N}(0,1)$. Moreover, the formula predicting the risk simplifies to

Numerical results and discussion

Recall that the number of features known at training is determined by $\kappa$. Specifically, $\kappa$ enters the formulae predicting the classification performance via the signal strength $s=s(\kappa)$. In this section, we specify two explicit models for feature selection and their corresponding functions $s(\kappa)$. Similar models are considered in [BF83, HMRT19, BHX19], albeit in a linear regression setting.

Linear model. We start with a uniform feature selection model characterized by the following parametrization:

for fixed $r^{2}$ and $\zeta>1$. This models a setting where all coefficients of the regressor $\boldsymbol{\eta}_{0}$ have equal contribution. Hence, the signal strength $s^{2}=\|\boldsymbol{\beta}_{0}\|_{2}^{2}$ increases linearly with the number $p$ of features considered in training.

Polynomial model. In the linear model, adding more features during training results in a linear increase of the signal strength. In contrast, our second model assumes diminishing returns:

for some $\gamma\geq 1$. As $\kappa$ increases, so does the signal strength $s$, but the increase is less significant for larger values of $\kappa$ at a rate specified by $\gamma$.

2 Risk curves

Figure 1 assumes the logistic data model (1) and polynomial feature model (22) for $\gamma=2$ and three values of total signal strength $r$. The crosses (‘$\times$’) are simulation results obtained by running GD on synthetic data generated according to (1) and (22). Specifically, the depicted values are averages calculated over $500$ Monte Carlo realizations for $p=150$. For each realization, we ran GD on logistic loss (see Sec. 2.3) with a fixed step size until convergence and recored the resulting risk. Similarly, the squares (‘$\square$’) are simulation results obtained by solving SVM (9) over the same number of different realizations and averaging over the recorded performance. As expected by [JT19] (also Sec. 2.4), the performance of GD matches that of SVM when data are separable. Also, as predicted by Proposition 3.1, the data is separable with high-probability when $\kappa>\kappa_{\star}$ (the threshold value $\kappa_{\star}$ is depicted with dashed vertical lines). This is verified by noticing the dotted (‘$\bullet$’) scatter points, which record (averages of) the training error. Recall from Section 2.3 that the training error is zero if and only if the data are separable. Finally, the solid lines depict the theoretical predictions of Proposition 3.2 ($\kappa<\kappa_{\star}$) and Proposition 3.3 ($\kappa>\kappa_{\star}$). The results of Figure 1 validate the accuracy of our predictions: our asymptotic formulae predict the classification performance of GD on logistic loss for all values of $\kappa$. Note that the curves correspond to excess risk defined in (7); see also related Footnote 1. Corresponding results for the cosine similarity are presented in Figure 8 in Appendix H.

Under the logistic model (1), Figures 2 and 3 depict the cosine similarity and excess risk curves of GD as a function of $\kappa$ for the linear and the polynomial model, respectively. Compared to Figure 1, we only show the theoretical predictions. Note that the linear model is determined by parameters $(\zeta,r)$ and the polynomial model by $(\gamma,r)$. Once these values are fixed, we compute the threshold value $\kappa_{\star}$. Then, we numerically evaluate the formulae of Proposition 3.2 ($\kappa<\kappa_{\star}$) and Proposition 3.3 ($\kappa>\kappa_{\star}$).

Finally, Figures 4 and 5 show risk and cosine-similarity curves for the Gaussian mixture data model (2) with linear and polynomial feature selection rules, respectively. The figures compare simulation results to theoretical predictions similar in nature to Figure 1, thus validating the accuracy of the latter for the GM model. For the simulations, we generate data according to (2) with $\pi_{+1}=1/2$, $n=200$ and $d=600$. The results are averages over $500$ Monte Carlo realizations.

3 Discussion on double descent

The double-descent behavior of the test error (resp. double-ascent behavior of the cosine similarity) as a function of the model complexity can be clearly observed in all the plots described above.

First, focus on the underparameterized regime $\kappa<\kappa_{\star}$ (cf. area on the left of the vertical dashed lines). Here, the number $n$ of training examples is large compared to the size $p$ of the unknown weight vector $\boldsymbol{\beta}_{0}$, which favors learning $\boldsymbol{\beta}_{0}$ with better accuracy. However, since only a (small) fraction $p/d$ of the total number $d$ of features are used for training, the observations are rather noisy. This tradeoff manifests itself with a “U-shaped curve” for $\kappa<\kappa_{\star}$.

Next, as the size overparameterization ratio $\kappa$ increases beyond $\kappa_{\star}$ (cf. area on the right of the vertical dashed lines) the training data become linearly separable. The implicit bias of GD on logistic loss leads to convergence to the max-margin classifier. In all Figures 1–5, it is clearly seen that the risk curves experience a second descent just after the interpolation threshold $\kappa_{\star}$. This observation analytically reaffirms similar empirical observations in more complicated learning tasks, architectures and datasets [NKB+19]. Intuitively, the second descent can be attributed to: (a) the implicit bias of GD and (b) the fact that larger $\kappa$ implies smaller degree of model mismatch in the model of Section 2.2. In fact, it can be seen that depending on the feature selection model the curve in the overparameterized regime can either be monotonically decreasing (e.g., Figure 2) or having a U-shape (e.g. Figure 3). In particular, the polynomial feature selection model (22) favors the later behavior and the “U-shape” is more pronounced for larger values of the parameter $\gamma$ in (22). At this point, it is worth noting that the potential U-shape in the overparameterized regime is not predicted by classical bounds on the test error of margin-classifiers in terms of the normalized max-margin {\sqrt{\kappa}}\big{/}{\|\hat{\boldsymbol{\beta}}\|_{2}} [SSBD14, Thm. 26.13]. This is demonstrated in Figure 3 (right), which shows that the asymptotic limit $\sqrt{\kappa}q^{\star}$ of the normalized max-margin (cf. Proposition 3.3) is monotonic in $\kappa$ rather than following a “U-shape”.

Owing to the double-descent behavior, the risk curves have are two local minima corresponding to the two regimes of learning. This observation is valid for all different data models depicted in Figures 1–5. On the other hand, whether the global minimum of the curves appears in the overparameterized regime or not, this depends on the nature of the training data. For example, for both the logistic and GM models under the linear feature model in Figures 2 and 4 the global minimum occurs at $\kappa_{\rm opt}>\kappa_{\star}$ in the interpolating regime for all SNR values. The value of $\kappa_{\rm opt}$ determines the optimal number of features that need to be selected during training to minimize the classification error. Note that for $\kappa_{\rm opt}$ the training error is zero, yet the classification performance is best. However, for the polynomial model depending on the value of $\gamma$ it can happen that $\kappa_{\rm opt}<\kappa_{\star}$ (cf. Figures 3 and 5 for $\gamma=5$.).

The previous discussion related to Figures 1–5 makes clear that important features of double-descent curves, such as the global minimum and the location of cusp of the curves critically depend on the data. The recent paper [KT20] has extended the present analysis to GD on square-loss. When combined, [KT20] and our paper demonstrate analytically that double descent behaviors can occur even in simple linear classification models. Moreover, they show analytically that the features of the curves depend both on the data (e.g., logistic vs GM) as well as on the learning algorithm (e.g., square vs logistic loss). These conclusions resemble, and thus might offer insights, to corresponding empirical findings in the literature [NKB+19, BHMM18, SGd+19]. We refer the interested reader to [KT20] for further details on how the choice of loss in (5) impacts the double descent.

We conclude this section, with an investigation of the dependence of the double-descent curves on the size of the training set. Specifically, we fix $d$ (the dimension of the ambient space) and study double descent for three distinct values of the training-set size, namely $n=\frac{1}{3}d,\frac{2}{3}d,$ and $d$. For these three cases, we plot the test error vs the model size $p=\frac{\kappa}{\zeta}d$ in Figure 6 for the linear (Left) and polynomial (Right) feature-selection model. First, observe that as the training size grows larger (i.e., $\zeta$ decreases), the interpolation threshold shifts to the right (thus, it also increases) under both models. Second, for the linear model, larger $n$ improves the performance for all model sizes. On the other hand, for the polynomial model, larger $n$ does not necessarily imply that the global minima of the corresponding curve corresponds to better test error. Moreover, the curves cross each other. This implies that more training examples do not necessarily help, and could potentially hurt the classification performance, whether at the underparameterized or the overparameterized regimes. For example, for model size $p\approx 0.4d$, the test error is lowest for $n=\frac{1}{3}d$ and largest for $n=d$. The effect of the size of the training set on the DD curve was recently studied empirically in [NKB+19]; see also [Nak19] for an analytical treatment in a linear regression setting. Our investigation is motivated by and theoretically corroborates the observations reported therein. Also please refer to [KT20] for corresponding results on square-loss.

Future work

We studied the classification performance of GD on logistic loss under the logistic and GM models with isotropic Gaussian features. We further used these results to demonstrate double-descent curves in binary linear classification under such simple models. Specifically, the proposed setting is simple enough that it allows a principled analytic study of several important features of double-descent (DD) curves, such as the dependence of the curve’s transition threshold and global minimum on: (i) the learning model and SNR, (ii) the size of the training set and (iii) the loss function (in combination with the results of [KT20]).

References

Appendix A Main Analysis Tool

In Section A.2 we present our main analysis tools: Theorems A.1 and A.2, which are extensions of the CGMT and can potentially be used beyond the scope of this paper. For the reader’s convenience, we first recall the CGMT in Section A.1.

The CGMT is an extension of Gordon’s Gaussian min-max inequality (GMT) [Gor88]. In the context of high-dimensional inference problems, Gordon’s inequality was first successfully used in the study oh sharp phase-transitions in noiseless Compressed Sensing [Sto09, CRPW12, ALMT13, Sto09, OT17]. More recently, [Sto13] (see also [ALMT13, Sec. 10.3]) discovered that Gordon’s inequality is essentially tight for certain convex problems. A concrete and general formulation of this idea was given by [TOH15] and was called the CGMT.

In order to summarize the essential ideas, consider the following two Gaussian processes:

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.

In words, concentration of the optimal cost of the AO problem around $q^{\ast}$ implies concentration of the optimal cost of the corresponding PO problem around the same value $q^{\ast}$. Asymptotically, if we can show that $\phi(\mathbf{g},\mathbf{h})\stackrel{{\scriptstyle{P}}}{{\rightarrow}}q^{\ast}$, then we can conclude that $\Phi(\mathbf{G})\stackrel{{\scriptstyle{P}}}{{\rightarrow}}q^{\ast}$. Moreover, starting from (26) and under appropriate 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 around the same value. For example, if minimizers of (24b) satisfy $\lVert\mathbf{w}_{\phi}(\mathbf{g},\mathbf{h})\rVert_{2}\stackrel{{\scriptstyle{P}}}{{\rightarrow}}\alpha^{\ast}$ for some $\alpha^{\ast}>0$, then, the same holds true for the minimizers of (24a): $\lVert\mathbf{w}_{\Phi}(\mathbf{G})\rVert_{2}\stackrel{{\scriptstyle{P}}}{{\rightarrow}}\alpha^{\ast}$ [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. In [TAH18], the authors introduce a principled machinery that allows to (a) express general convex empirical-risk minimization (ERM) problems for noisy linear regression in the form of the PO and (b) simplify the AO from a (random) optimization over vector variables to an easier optimization over only few scalar variables, termed the “scalarized AO”.

A.2 Novel extensions of the CGMT

As mentioned in the previous section, the CGMT applies to optimization problems in which the optimization sets are convex and compact sets. While convexity is frequently met in practice, the compactness condition is not always satisfied (this is specifically true for compactness of the “dual” variable $\mathbf{u}$ in (24a)). Some existing ideas allowing to circumvent this problem are developed in [TAH18] but, they are essentially suitable to high-dimensional linear regression problems and cannot be directly extended to handle any optimization problem. The difficulty becomes even more pronounced in problems like the hard-margin SVM that are not always feasible.

In this work, we extend the CGMT in two directions. First, we show that the behavior of any convex optimization problem in the form of the CGMT can be characterized through that of a sequence of AO problems. Particularly, we illustrate in Theorem A.1 how these sequences can help identify whether the underlying optimization problem is feasible or not. When feasibility conditions are met, we show in Theorem A.2 that the precise characterization of the PO boils down to an analysis of the optimal costs of the sequence of AO problems. While our motivation stems from the analysis of the hard-margin SVM, we believe that the generalization of the CGMT presented here can be of independent interest offering a principled way for future statistical performance studies of related optimization-based inference algorithms.

The proofs of Theorems A.1 and A.2 are presented in Appendix B.

Before stating our main results, let us first introduce some necessary notation and some useful facts. As previously (cf. (24a)), let $\Phi({\bf G})$ be the primary optimization problem:

Since the function $\max_{\begin{subarray}{c}{\bf u}\in\mathcal{S}_{\bf u}\\ \|{\bf u}\|\leq\Gamma\end{subarray}}X_{{\bf w},{\bf u}}$ is convex in ${\bf w}$ and concave in $\Gamma$, the order of min-sup in (29) can be flipped [S+58] leading to the following connection between the PO and its $(R,\Gamma)$-bounded version:

We associate with $\Phi_{R,\Gamma}({\bf G})$ the following AO problem:

Note in the definitions of $\Phi_{R,\Gamma}(\mathbf{G})$ and $\phi_{R,\Gamma}(\mathbf{g},\mathbf{h})$ in (28) and (31) that the involved optimization problems are over bounded convex sets. Thus, the CGMT directly establishes a link between the two. Nevertheless, what is of interest to us is the PO problem $\Phi(\mathbf{G})$ in (27) that optimizes over (possibly) unbounded sets.

Theorems A.1 and A.2 below establish a connection between $\Phi(\mathbf{G})$ and a sequence (over $R$ and $\Gamma$) of the AO problems $\phi_{R,\Gamma}(\mathbf{g},\mathbf{h})$. In order to show this, it is convenient to further define $\phi_{R}({\bf g},{\bf h})$ as follows:

Using the fact that $\Gamma\mapsto\phi_{R,\Gamma}(\mathbf{g},\mathbf{h})$ is increasing it can be further shown that (see Section B.1):

Finally, starting from (32) and applying the min-max inequality [Roc97, Lem. 36.1] we see that

Note that equality does not necessarily hold in (34) since $Y_{\mathbf{w},\mathbf{u}}$ is not necessarily convex-concave.

As a last remark, we note that $\Phi(\mathbf{G}),\Phi_{R,\Gamma}(\mathbf{G})$ and $\phi_{R,\Gamma}(\mathbf{G})$ are all indexed by the dimensions $n$ and $d$. We have not explicitly accounted for this dependence in our notation for simplicity.

First, Theorem A.1 shows how studying feasibility of the sequence of “$(R,\Gamma)$-bounded” AO problems in (31) can determine the feasibility of the original PO problem (in which the constraint sets are potentially unbounded).

Recall the definitions of $\Phi(\mathbf{G}),\phi_{R,\Gamma}(\mathbf{g},\mathbf{h})$ and $\phi_{R}(\mathbf{g},\mathbf{h})$ in (27), (31) and (33), respectively. Assume that $(\mathbf{w},\mathbf{u})\mapsto X_{\mathbf{w},\mathbf{u}}$ in (23) is convex-concave and that the constraint sets ${\mathcal{S}}_{\mathbf{w}},{\mathcal{S}}_{\mathbf{u}}$ are convex (but not necessarily bounded). The following two statements hold true.

Then, with probability $1$, for $n$ sufficiently large, $\Phi({\bf G})=\infty$.

This observation can be useful as it is often the case that the “unbounded” optimization over $\mathbf{u}$ is easy to perform.

Theorem A.2 below shows that if the sequence of AO problems are all feasible, then their limiting cost determines the optimal cost of the original PO problem. Compared to the CGMT, note that it is not required that ${\mathcal{S}}_{\mathbf{w}}$ and ${\mathcal{S}}_{\mathbf{u}}$ are compact and also the convergence results hold in almost-sure sense.

Furthermore, letting $\mathbf{w}_{\Phi}$ denote a minimizer of the PO in (27), it also holds that

While the constraint set ${\mathcal{S}}_{\mathbf{u}}$ is often unbounded, it is common that the constraint set ${\mathcal{S}}_{\mathbf{w}}$ can be assumed to be bounded. When this is the case, the conditions of Theorem A.2 can be simplified as shown in the corollary below, which is an immediate consequence of Theorem A.2.

Furthermore, letting $\mathbf{w}_{\Phi}$ denote a minimizer in (27), it also holds that

Similar to Remark 2, it suffices for (41b) to hold that the following (often easier to check) condition is true:

Further as noted in Remark 2 this formulation can be useful as it is often the case that the “unbounded” optimization over $\mathbf{u}$ in (44) is easy to perform. What allows us to replace with (44) is the min-max inequality in (34). If equality were true when ${\bf w}$ is constrained to either ${\mathcal{S}}_{w}$ or the (possibly) non-convex set $\mathcal{S}^{c}:=\mathcal{S}_{\bf w}\backslash\mathcal{S}$, then, (41a) and (41c) would be equivalent to the following:

Similar to (44), this formulation is often preferred in practice as it relates to the “easier” unbounded AO. It turns out that a sufficient condition for the equivalence described above is that the objective function $Y_{\mathbf{w},\mathbf{u}}$ of the AO is convex in $\mathbf{w}$. To see this, note that under this convexity condition,

provided that $Y_{\mathbf{w},\mathbf{u}}$ is convex. Unfortunately, the form of the AO in (23b) is not convex in $\mathbf{w}$ as is. Nevertheless, the analysis of the AO (as prescribed in [TAH18]) often leads to an equivalent “scalarized version” (aka optimization over only a few scalar variables) which possesses the desired convexity property. From the discussion above, one may then use (45) towards applying Corollary A.1 to the convex scalarized AO.

In practice Corollary A.1 can be used in conjunction with Lemma G.3 in Appendix G to handle the unboundedness of the set $\mathcal{S}_{{\bf w}}$. At a high level, the recipe is as follows. Start with the following “single-bounded version” of the PO

which allows the use of Corollary A.1. Next, suppose that applying the corollary allows to show that any minimizer $\hat{\bf w}_{R}$ of (46) satisfies $\|{\bf w}_{R}\|\xrightarrow[]{a.s.}\theta^{\star}$ for some $\theta^{\star}<R$ (and independent of $R$). Then, by Lemma G.3, it follows that any solution $\hat{\bf w}_{\Phi}$ of (27) must also satisfy $\|\hat{\bf w}_{\Phi}\|\xrightarrow[]{a.s.}\theta^{\star}$. Hence, this validates the equivalence of (46) for sufficiently large $R$ (e.g., any $R\geq 2\theta^{\star}$) to the unbounded PO in (27). We apply this recipe in Appendix F, which studies the statistical properties of logistic-loss minimization in the underparameterized regime $\kappa<\kappa_{\star}$.

Appendix B Proofs for Appendix A.2

Letting $\Gamma\to\infty$ in the left and right-hand sides of the above inequality, we obtain:

For the rest of the proofs, it is also convenient to note that, due to the convex-concave property of the objective in the PO, the single-bounded version of the PO introduced in (46) writes also as follows:

Similar to what was shown above, we can equivalently write:

B.2 Proof of Theorem A.1

In a similar way, $\Phi_{k,m}({\bf G})\geq\Phi_{k,m-1}({\bf G})$, hence the sequence of events:

Consider now the event $\mathcal{E}$ defined as follows:

B.2.2 Proof of statement (ii)

Recall that $\Phi_{k_{0}}({\bf G})=\lim_{m\to\infty}\Phi_{k_{0},m}({\bf G})=\sup_{m\to\infty}\Phi_{k_{0},m}({\bf G}),$ and so, $\Phi({\bf G})\leq\Phi_{k_{0}}({\bf G})$. Therefore, for any $1>\epsilon>0$ we have:

B.3 Proof of Theorem A.2

The proof consists in showing that each one of (38a), (38b) and (38c) imply one of the following three statements respectively:

where $\widetilde{\Phi}({\bf G})$ is the optimal cost of the optimization in (27) where the minimization over ${\bf w}$ is constrained over ${\bf w}\in\mathcal{S}^{c}$. Clearly the combination of (52a) and (52b) yields (39). To prove how (40) follows from (52c), consider the event:

Proof of (52b): We start by noticing that

Also, recall that $\Phi_{k_{0}}({\bf G})=\lim_{m\to\infty}\Phi_{k_{0},m}({\bf G}).$ With this at hand, we obtain

Proof of (52c): The proof of (52c) is identical to the proof of (52a); thus, it is omitted for brevity.

Appendix C Hard-margin SVM

In this section we analyze the statistical properties of hard-margin SVM. The analysis is based on the two theorems of Section A.2. First, in Section C.1 we show how to bring the SVM minimization in the form of a PO, we write the equivalent AO and we simplify it to a scalar optimization problem. Next, in Section C.2 we apply Theorem A.1 to study the feasibility of SVM. As mentioned, the SVM problem is feasible iff the data are linearly separable. Hence, this section proves Proposition 3.1. In the regime $\kappa>\kappa_{\star}$ where the problem is feasible, we apply Theorem A.2 to prove Proposition 3.3 in Section C.3. Throughout, we focus on the logistic data model (1). Treatment for the GM model (2) is almost identical (if not simpler). To avoid repetitions, we only sketch the main part where the two models need different treatment, which is the formulation of the PO and of the equivalent AO. We present this in Section C.4.

Identifying the PO. The max-margin solution is obtained by solving the following problem:

and is feasible only when the training data is separable. The minimization in (56) is equivalent to solving:

Based on the rotational invariance of the Gaussian measure, we may assume without loss of generality that $\boldsymbol{\beta}_{0}=[s,0,\ldots,0]^{T},$ where only the first coordinate is nonzero. For convenience, we also write

In this new notation, the response variables are expressed as follows:

leads to the following optimization problem

which has the same form of a primary optimization (PO) problem as required by the CGMT (cf. (24a)), with the single exception that the feasibility sets are not compact. To solve this issue, we pursue the approach presented in Section A.2.

Forming the AO. In view of (31), we associate the PO in (61) with the following “$(R,\Gamma)$’–bounded” auxiliary optimization problems:

where $\mathbf{g}\sim\mathcal{N}(0,{\bf I}_{n})$ and $\mathbf{h}\sim\mathcal{N}(0,{\bf I}_{p-1})$. Having identified the AO problem, the next step is to simplify them so as to reduce them to problems involving optimization only over a few number of scalar variables. This will facilitate in the next step of inferring their asymptotic behavior.

It is important to note that the new formulation of the AO problem is obtained from a deterministic analysis that did not involve any asymptotic approximation.

Asymptotic behavior of the AO. In view of (86), let us consider the sequence of functions

for $\alpha\geq 0$ and $\alpha^{2}+\mu^{2}\leq R^{2}$. It is easy to see that $L_{n}$ is jointly convex in its arguments $(\alpha,\mu)$ and converges almost surely in the limit of (11) to:

The convergence above holds point-wise in $(\alpha,\mu)$. But, convergence of convex functions is uniform over compact sets [AG82, Cor. II.1]. Therefore, for an arbitrary fixed compact set $\mathcal{C}$ and any $\varepsilon>0$, for $n$ sufficiently large it holds that

C.2 Proof of Proposition 3.1

Organization of the proof. We organize the proof of Proposition 3.1 in three parts. In the first two parts, which are both presented in this section, we prove the following two statements in the order in which they appear:

In the third part, we prove that the function $g(\kappa)$ is decreasing. Hence, the equation $\kappa=g(\kappa)$ admits a unique solution $\kappa_{*}$ and one of the following two statements holds true for any $\kappa$: $\kappa>\kappa_{*}\Rightarrow\kappa>g(\kappa)$ or $\kappa<\kappa_{*}\Rightarrow\kappa<g(\kappa)$. This third part of the proof is deferred to Appendix D.

holds, then, $\Phi^{(n)}=\infty$, for large enough $n$. Equivalently, when (69) holds, then, the hard-margin SVM program (56) is infeasible with probability one. To prove the desired we will apply Theorem A.1(i). Specifically, in view of (35), it suffices to prove that under (69), for any fixed $R,\Gamma$, there exists constant $C>0$ (independent of $\Gamma$ and $R$) such that for sufficiently large $n$ (that can be taken independently of $R$ and $\Gamma$):

In the remaining of the proof, we show that (70) holds. Recall from (64) that,

The function $(\alpha,\mu)\mapsto{L}_{n}(\alpha,\mu)$ is jointly convex in the variables $(\alpha,\mu)$ and converges pointwise to $(\alpha,\mu)\mapsto\overline{L}(\alpha,\mu)$. Thus, for any $\alpha>0$, $\mu\mapsto L_{n}(\alpha,\mu)$ is convex and converges to $\mu\mapsto\overline{L}(\alpha,\mu)$. Moreover, it is easy to see that $\lim_{\mu\to\pm\infty}\overline{L}(\alpha,\mu)\to\infty$. Hence, using [TAH18, Lemma 10], $\min_{\mu}L_{n}(\alpha,\mu)$ converges to $\min_{\mu}\overline{L}(\alpha,\mu)$. Similarly, $\alpha\mapsto\min_{\mu}{L}_{n}(\alpha,\mu)$ is convex and converges pointwise to $\alpha\mapsto\min_{\mu}\overline{L}(\alpha,\mu)$. Moreover,

because of (69). Hence, we can use again [TAH18, Lemma 10], to find that

Thus, in view of (71), for any $\epsilon>0$, it holds for $n$ sufficiently large (independent of $R$ and $\Gamma$) that

Thus, the desired inequality (70) holds provided that there exists $C$ such that

To see this, note that in this case we can choose $\epsilon$ sufficiently small (say, smaller than $\inf_{\mu,\alpha\geq 0}0.5\overline{L}(\alpha,\mu)$) in (73).

Hence, it suffices to prove that (73) holds under (69). To show the desired, we first prove that the optimization over $\mu$ in (73) when $\alpha$ is constrained to be in the vicinity of can be assumed over a compact set. This can be seen as follows. For any $0\leq\alpha\leq 1$, it holds

Since $\alpha\mapsto\min_{\mu\in\mathcal{A}}\overline{L}(\alpha,\mu)$ is continuous and thus uniformly continuous over compacts, there exists $1>\eta>0$, such that

Note that the right-hand side above is strictly positive because of (69).

Thus, combining (75) and (76), we conclude with the desired, i.e. if (69) holds, then (74) and consequently (70) hold.

C.2.2 Part II: Proof of (68)

then, the PO in (56) is feasible (eqv. $\Phi^{(n)}$ is bounded) with probability 1. To prove this, we will apply Theorem A.1(ii). Specifically, in view of (36) it will suffice to show that under (77) the AO is feasible with probability 1, for sufficiently large $n$.

First, we will show that for any $\delta>0$ the following set is non-empty:

To see this, let $t^{\star}$ be such that:

This and continuity of $\overline{L}(\alpha,\mu)$ prove (78).

Next, we prove (36) by showing that the AO problem is upper bounded by $C_{\delta}^{2}$ with probability 1. Specifically, we work with the sufficient condition (37). Towards that end, choose $k_{0}$ be an integer strictly greater than $C_{\delta}$ and letRecall from (32) that $\phi_{k_{0}}^{(n)}$ is defined as $\phi_{k_{0}}^{(n)}=\displaystyle{\sup_{m>0}}~{}\displaystyle{\min_{(\alpha,\mu)\in\mathcal{C}_{k}}\max_{0\leq\theta\leq m}\theta\,L_{n}(\alpha,\mu)+\alpha^{2}+\mu^{2}}$. Thus, inequality “$\leq$” holds in (80) by the min-max theorem; moreover inequality suffices here for our purposes as explained in Remark 2. Nevertheless, since the objective function of the scalarized AO in (80) is convex-concave, equality holds in (80) by applying the Sion’s min-max theorem [S+58].

Moreover, by uniform convergence of the AO in (66) we know that for all sufficiently large $n$: $L_{n}(\alpha,\mu)\leq\overline{L}(\alpha,\mu)+\delta$, uniformly for all $(\alpha,\mu)\in\mathcal{C}_{k_{0}}$. Hence, recalling (78), it holds that

And so, continuing from (81), we have shown that for sufficiently large $n$:

where the last inequality follows by definition of $C_{\delta}$ in (79). This shows (37) and the proof is complete by applying Theorem A.1(ii).

C.3 Proof of Proposition 3.3

Throughout this section we assume that (77) holds. We will prove Proposition 3.3 by applying Theorem A.2. Specifically, let

where $q^{\star}$ is as defined in Proposition 3.3. In view of Theorem A.2, we need to prove the following

where $\phi_{k}^{(n)}$ is (see (80) and Remark 3) given by:

Recall the definition of $\overline{L}(\alpha,\mu)$ in (65) and let $q^{\star}$ be defined as in Proposition 3.3. Further assume the separability condition (77). The following statement is true, for all $k\geq k_{0}=\sqrt{\lceil(q^{\star})^{2}\rceil+1}$,

In addition to (83), we need to consider an appropriate “perturbed” AO as suggested by (38c). For this reason, fix $\widetilde{\xi}>0$ and define the “perturbed” version of the AO problem (cf. (64)) as follows:

and $\rho^{\star}$ is defined in Proposition 3.3. In order to apply Theorem A.2, we will prove in addition to (83) that

Thus, if we show (83a), (83b) and (88), then Theorem A.2 will imply that the solution $\boldsymbol{\widehat{\beta}}$ of the PO $\Phi^{(n)}$ in (56) satisfies $\boldsymbol{\widehat{\beta}}\in\mathbf{{\mathcal{S}}}^{(n)}$ with probability one. To see why this leads to the asymptotic formulae of the proposition argue as follows. For small enough $\widetilde{\xi}$ it follows by definition (89) that

Therefore, for $\boldsymbol{\beta}\in\mathbf{{\mathcal{S}}}^{(n)}$ (and small enough $\widetilde{\xi}$):

where as always $G,H,Z$ and $Y$ follow our notation in (13) and the second to last line follows since $HY\sim\mathcal{N}(0,1)$.

Hence, it remains to prove (83a), (83b) and (88).

C.3.2 Proof of Lemma C.1

First, recalling the definition of $\overline{L}(\alpha,\mu)$ in (65) note the following implications

where, in the second line we have used the fact that $(0,0)\not\in\{(\alpha,\mu)~{}|~{}\overline{L}(\alpha,\mu)\leq 0\}$. To proceed, define new variables

With this new notation, note that the expression in (92) can be written as

where we recall the definition of the mapping $\eta(q,\rho)$ in (19). With this note and using (92), we have that:

In Lemma E.1, it is shown that $q\mapsto\min_{\rho\in}\eta(q,\rho)$ is strictly decreasing. Recall the definition of $q^{\star}$ in Proposition 3.3 as the unique minimum of the equation $\min_{\rho\in}\eta(q,\rho)=0$; see Appendix E for a proof that such a unique minimum exists under the separability assumption (77) of the lemma. Combining the above, we conclude that

Using this and the assumption $k^{2}>(q^{\star})^{2}$ proves that the RHS in (94) is equal to $(q^{\star})^{2}$, which concludes the proof.

C.3.3 Proof of (83a)

Fix any $\varepsilon>0$, and $k\geq k_{0}=\sqrt{\lceil(q^{\star})^{2}\rceil+1}$. Recall the notation in (84).

We start by proving that the following statement holds almost surely

Before that we argue that the minimization in the RHS above is feasible. The argument is identical to what was done in Section C.2.2. Specifically, by uniform convergence of $L_{n}(\alpha,\mu)$ to $\overline{L}(\alpha,\mu)$ (cf. (66)), for any $\delta>0$ and sufficiently large $n$:

Using assumption (77), we have shown in (78) that the set on the LHS above is non-empty. This implies non-emptyness of the feasibility set in (96).

Next, continuing from (96), we will use uniform convergence of $L_{n}(\alpha,\mu)$ to $\overline{L}(\alpha,\mu)$ (cf. (66)) to show that for sufficiently large $n$:

Before proving (97), let us see how it leads to the desired (83a). When put together with (96), (97) shows that for sufficiently large $n$ (independent of $k$):

From this and (85) of Lemma C.1 we conclude that for sufficiently large $n$:

Since this holds for sufficiently large $n$ independent of $k\geq k_{0}$, we arrive at (83a), as desired.

Proof of (97). From (66), the function $(\alpha,\mu)\mapsto L_{n}(\alpha,\mu)$ converges to $\overline{L}(\alpha,\mu)$ defined in (65) uniformly over the compact set $\mathcal{C}_{k_{0}}$. Concretely, for any $\delta$, for all sufficiently large $n$: $L_{n}(\alpha,\mu)\geq\overline{L}(\alpha,\mu)-\delta,\forall(\alpha,\mu)\in\mathcal{C}_{k_{0}}.$ Thus,

We may now conclude (97) from (100), by first applying Lemma G.2 to see that

and then invoking the $\epsilon$-definition of supremum.

C.3.4 Proof of (83b)

Fix any $\varepsilon>0$. It suffices to prove that for all sufficiently large $n$:

To see why this is sufficient for (83b) to hold, recall from (85) of Lemma C.1 that the RHS above is equal to $(q^{\star})^{2}+\varepsilon$.

Proof of (99). From (66), the function $(\alpha,\mu)\mapsto L_{n}(\alpha,\mu)$ converges to $\overline{L}(\alpha,\mu)$ defined in (65) uniformly over the compact set $\mathcal{C}_{k_{0}}$. Concretely, for any $\delta>0$, for all sufficiently large $n$: $L_{n}(\alpha,\mu)\leq\overline{L}(\alpha,\mu)+\delta,~{}\forall(\alpha,\mu)\in\mathcal{C}_{k_{0}}.$ Thus,

We may now deduce (99) from (100), by first applying Lemma G.2 to see that

and then invoking the $\epsilon$-definition of infimum.

C.3.5 Proof of (88)

In the first part, we show that for any $\zeta>0$ and for sufficiently large $n$ (independent of $k$) it holds that:

where recall the definition of the set ${\mathcal{S}}$ in (87). Recall from Section C.3.1 that

Note that the objective function above is convex in $(\alpha,\mu)$. Hence, we proceed as argued in Remark 3 to show that

We may now prove (101) starting from (102) by using uniform convergence (66). The proof of this step is identical to the proof of (96) and (97) and is omitted for brevity.

In the second part of the proof, we show that there exists $\zeta>0$ such that

This will complete the proof of (88). Indeed, starting from (101) and using $\zeta$ such that (103) holds, we find that for sufficiently large $n$:

It remains to prove (103). First, following the same re-parametrization as in (93) (see Section C.3.2 for identical derivations) we can express $\widetilde{q}^{2}$ as follows:

where ${\mathcal{S}}_{\rho}:=\{\rho~{}|~{}|\rho-\rho^{\star}|<\xi\}$, ${\mathcal{S}}_{q}:=\{q~{}|~{}|q-q^{\star}|<\xi\}$, and $\xi>0$ is small enough constant chosen such that $(\alpha,\mu)\in{\mathcal{S}}\,\Rightarrow\,(q,\rho)\in{\mathcal{S}}_{q}\times{\mathcal{S}}_{\rho}.$ To proceed, we consider two cases as follows.

Case 1: $\rho\in$. First, consider the case in which $\widetilde{q}$ is as follows:

We will use the following facts for the function $\widetilde{\eta}(q):=\min_{\rho\in}\eta(q,\rho)$: (i) it is decreasing; (ii) it has a unique zero $q^{\star}$. See Lemma E.1 in Appendix E for a proof of these claims. From these and the constraint $|q-q^{\star}|\geq\xi$, it is clear that ${\widetilde{q}}=q^{\star}+\xi$. Hence, ${\widetilde{q}}^{2}>(q^{\star})^{2}+\xi^{2},$ and (103) holds after choosing $\zeta=\xi^{2}/2>0$.

Case 2: $|\rho-\rho^{\star}|>\xi$. Second, consider the case in which $\widetilde{q}$ is as follows:

For the sake of contradiction to (103), assume that ${\widetilde{q}}\leq q^{\star}$. By Lemma E.1 in Appendix E the function $q\mapsto\min_{\begin{subarray}{c}\rho\in\\ |\rho-\rho^{\star}|>\xi\end{subarray}}\eta(q,\rho)$ is strictly decreasing. From this and definition of $\widetilde{q}$, it follows that $\min_{\begin{subarray}{c}\rho\in\\ |\rho-\rho^{\star}|>\xi\end{subarray}}\eta(q^{\star},\rho)\leq 0=\eta(q^{\star},\rho^{\star})$. But, again from Appendix E $\rho\mapsto\eta(q^{\star},\rho)$ has a unique minimizer $\rho^{\star}$ in $$. Hence, the above is a contradiction.

C.4 Proof sketch for GM model

For brevity, we only show how to formulate the PO and the corresponding AO under the GM model. The rest of the proof follows mutandis-mutatis the content of Sections C.2 and C.3.

Recall that under the GM model, the feature vectors ${\bf x}_{i}$ are given by: ${\bf x}_{i}=y_{i}\boldsymbol{\eta}_{0}+{\bf z}_{i}$ where ${\bf z}_{i}\sim\mathcal{N}({\bf 0},{\bf I}_{d})$ and ${y}_{i}=\pm 1$. Thus,

where recall that $\mathbf{w}_{i}:=\mathbf{x}_{i}(1:p)$, $\mathbf{v}_{i}:=\mathbf{z}_{i}(1:p)$ and $\boldsymbol{\beta}_{0}=\boldsymbol{\eta}_{0}(1:p)$. Replacing ${\bf w}_{i}=y_{i}\boldsymbol{\beta}_{0}+{\bf v}_{i}$ in (57), the SVM problem is equivalent to

In this, we clearly recognize a PO problem with which we associate the following AO problem:

Next, we sketch how to simplify this vector optimization to a scalar one. First decompose $\boldsymbol{\beta}$ as: $\boldsymbol{\beta}=\alpha_{1}\boldsymbol{\beta}_{0}+\alpha_{2}\boldsymbol{\beta}_{\perp},$ where $\alpha_{2}\geq 0$ and $\boldsymbol{\beta}_{\perp}$ is orthogonal to $\boldsymbol{\beta}_{0}$ and $\|\boldsymbol{\beta}_{\perp}\|=1$. Similarly, let $\mathbf{h}=(\mathbf{h}^{T}\boldsymbol{\beta}_{0})\frac{\boldsymbol{\beta}_{0}}{\|\boldsymbol{\beta}_{0}\|_{2}}+P_{\perp}\mathbf{h}$, where $P_{\perp}$ is the projection operator to a subspace orthogonal to $\boldsymbol{\beta}_{0}$. Optimizing over $\boldsymbol{\beta}_{\perp}$ is straightforward: $\boldsymbol{\beta}_{\perp}=\frac{P_{\perp}\mathbf{h}}{\|P_{\perp}\mathbf{h}\|}$ and further using Lemma G.1 the AO becomes:

Next, let $\theta={\|{\bf u}\|_{2}}$ and set $q^{2}=\alpha_{1}^{2}\|\boldsymbol{\beta}_{0}\|_{2}^{2}+\alpha_{2}^{2}$. Optimizing over the direction of ${\bf u}$, the problem further simplifies to the following:

Further defining $\rho=\frac{\alpha_{1}\|\boldsymbol{\beta}_{0}\|_{2}}{q}$ gives:

At this point, recognize that the optimization above is very similar to the corresponding optimization for the logistic model in (64) (under the mapping $\sqrt{\mu^{2}+\alpha^{2}}\leftrightarrow q$ and $\mu\leftrightarrow\rho\,q$ and using that $\frac{\mathbf{h}^{T}\boldsymbol{\beta}_{0}}{\sqrt{n}}$). Concretely, in a similar manner to Section C.1, consider the sequence of functions in the bracket above

for $q\geq 0$ and $|\rho|\leq 1$. It can be easily seen that $L_{n}$ is converges (pointwise) almost surely to:

where $G\sim\mathcal{N}(0,1)$ and we used the facts that $\frac{\mathbf{h}^{T}\boldsymbol{\beta}_{0}}{\sqrt{n}}\xrightarrow[]{a.s.}0$, $\frac{\|P_{\perp}\mathbf{h}\|_{2}}{\sqrt{n}}\xrightarrow[]{a.s.}\sqrt{\kappa}$ and $\|\boldsymbol{\beta}_{0}\|_{2}\xrightarrow[]{a.s.}s$. Using convexity and level-boundedness arguments similar to what was done for the logistic model, it can be further shown that the optimal cost of the optimization in (105) converges almost surely to the optimal cost of the same optimization but with $\overline{L}_{n}^{\dagger}(q,\rho)$ substituted by $\overline{L}^{\dagger}(q,\rho)$. In (106) recognize the resemblance to the function $\eta$ defined in Proposition 3.3 (cf. (20)). From this point on, the proof repeats the arguments of Sections C.2 and C.3 and we omit the details. Just for an illustration, argue as follows to see how the phase-transition threshold of Proposition 3.1 appears naturally. The AO of the hard-margin SVM in (105) is infeasible if $L^{\dagger}_{n}(q,\rho)$ is positive for all values of $q\geq 0$ and $\rho\in$. In the asymptotic limit, this happens if $\kappa$ is such that:

In the above line recognize the function $g(\kappa)$ defined in (16).

Appendix D On the solutions to the equation g​(κ)=κ𝑔𝜅𝜅g(\kappa)=\kappa in Proposition 3.1

is strictly decreasing. Therefore, the equation $\kappa=g(\kappa)$ admits a unique solution $\kappa_{*}\in(0,1/2)$ and one of the following two statements holds true for any $\kappa$:

where the expectation is over $G,H,Z\stackrel{{\scriptstyle\text{iid}}}{{\sim}}\mathcal{N}(0,1)$. Note that

Lemma D.2 below, shows that $\overline{g}(\varepsilon)$ is strictly decreasing in $\varepsilon$ and $\overline{g}(0)=1/2$ (see also Figure 7 for a numerical illustration). Here, we use these facts to prove the desired.

Towards this end, let $\kappa_{1}<\kappa_{2}$. Since $s(\cdot)$ is increasing, $s_{1}:=s(\kappa_{1})<s(\kappa_{2})=:s_{2}$. Thus, by (111) and Lemma D.2:

Thus, the function $g$ is strictly decreasing. Consider now the equation $g(\kappa)=\kappa$ for $\kappa\in[0,\zeta).$ Clearly, since $g$ is decreasing, if a solution $\kappa_{\star}$ exists, then it is unique. We now show that such a solution exists in the interval $[0,1/2]$. From Lemma D.2 the function $g$ is continuous and $g(\kappa)\leq 1/2$ for all $\kappa\geq 0$. For the shake of contradiction assume that there is no $\kappa\in[0,1/2]$ such that $g(\kappa)=\kappa$. Then, it must be that $g(\kappa)>\kappa$ for all $\kappa\in[0,1/2]$. In particular, $g(1/2)>1/2$, which contradicts the decreasing nature of $g$ and $g(0)\leq\overline{g}(0)=1/2$.

It remains to prove (108) and (109). We only prove the first one here, as the second one follows from the exact same argument. By decreasing nature of $g$ and definition of $\kappa_{\star}$ we have the following implications:

Decreasing nature of $g(\kappa)$. First, we introduce some handy notation. For a (random) variable $X$ we use the following shorthand:

where the random variable $Q$ is defined as $Q=\varepsilon G+\sqrt{1-\varepsilon^{2}}Z$. Then, $\overline{g}(0)=1/2$ and $\overline{g}$ is decreasing in $$.

First, we rewrite $\overline{g}(\varepsilon)$ in a more convenient form. Note that

Here, we have used the fact that $Y_{r\,Q}\in\{\pm 1\}$ and $Q$ is independent of $H$. By further decomposing $T_{1}$ on its projection on $Q$, i.e.,

From this, it is easy to see that the function $\overline{g}(\varepsilon)$ is continuous and that $\overline{g}(0)=1/2$.

where the inequality follows from Lemma D.3 below and the fact that $\delta<1$. The desired claim follows by minimizing both sides of the inequality in (114) with respect to $t$ and invoking (113). ∎

where the second equality follows by Gaussian integration by parts. ∎

Appendix E Properties of the function η​(q,ρ)𝜂𝑞𝜌\eta(q,\rho) of Proposition 3.3

(i). The function $q\mapsto\eta(q,\rho)$ is strictly decreasing for all $\rho\in$.

(ii). The function $\overline{\eta}$ is strictly decreasing.

We prove each one of the two statements separately.

(i). This holds because $x\mapsto(x)_{-}^{2}$ is strictly decreasing for $x<0$ and the measure of the random variable $\rho GY+\sqrt{1-\rho^{2}}H$ is strictly positive on the real line.

(ii). Fix $q_{2}>q_{1}>0$. Let $\rho_{1}\in$ be such that $\eta(q_{1},\rho_{1})=\overline{\eta}(q_{1})$. It holds,

where the second inequality follows from the first statement of the lemma.

defined in (19) admits a unique zero $q^{\star}$ provided that . Recall that $\kappa>\kappa_{\star}$ implies $\kappa>g(\kappa)$ (see Lemma D.1).

First, we show that such a zero exists. From the maximum Theorem [Sun96, Theorem 9.7], the function $\overline{\eta}(q)$ is continuous. Moreover, we will show that

These combined prove existence of a solution to $\overline{\eta}(q)=0$; thus it remains to prove (115) and (116). For the former, we argue as follows:

where in the last inequality we have used the facts that $x\mapsto(x)_{-}^{2}$ is decreasing and that the event $\{\rho GS+H\sqrt{1-\rho^{2}}\leq 0\}$ has nonzero measure for all $\rho\in$. On the other hand, for (116) we follow the following chain of inequalities

where the second inequality in the first line follows by continuity of $\overline{\eta}(q)$ and the last (strict) inequality follows from $\kappa>g(\kappa)$.

Next, we prove that such a zero must be unique. For that we assume that there exists $q_{1}^{\star}$ and $q_{2}^{\star}$ such that:

Denote by $\rho_{1}$ and $\rho_{2}$ the real values in the interval $$such that$\eta(q_{1}^{\star},\rho_{1})=\min_{-1\leq\rho\leq 1}\eta(q_{1}^{\star},\rho)=0$, and$\eta(q_{2}^{\star},\rho_{2})=\min_{-1\leq\rho\leq 1}\eta(\rho,q_{2}^{\star})=0$. Then, by optimality of$\rho_{1}$,

Since $0=\eta(q_{2}^{\star},\rho_{2})$ and $q\mapsto\eta(q,\rho_{2})$ is decreasing (see Lemma E.1), $q_{1}^{\star}\geq q_{2}^{\star}$. Similarly, we can use the same reasoning to prove that $q_{2}^{\star}\geq q_{1}^{\star}$. We thus necessarily have $q_{1}^{\star}=q_{2}^{\star}$, which proves the uniqueness of $q^{\star}$.

Unique minimizer of $\rho\mapsto\eta(\rho,q^{\star})$: Let $\rho_{1}$ and $\rho_{2}$ be two minimizers of $\rho\mapsto\eta(\rho,q^{\star})$ . Define $\mu_{1}=q^{\star}\rho_{1}$, $\alpha_{1}=q^{\star}\sqrt{1-\rho_{1}^{2}}$, $\mu_{2}=q^{\star}\rho_{2}$ and $\alpha_{2}=q^{\star}\sqrt{1-\rho_{2}^{2}}$, where $q^{\star}$ is the unique minimizer of $\overline{\eta}$. Then, in view of (94), $(\alpha_{1},\mu_{1})$ and $(\alpha_{2},\mu_{2})$ are two different minimizers of the following minimization problem:

As $(\alpha,\mu)\mapsto\alpha^{2}+\mu^{2}$ is jointly strictly convex in its variables and $(\alpha,\mu)\mapsto\overline{L}(\alpha,\mu)$ is convex, we have necessarily $\alpha_{1}=\alpha_{2}$ and $\mu_{1}=\mu_{2}$. Hence, $\rho_{1}=\rho_{2}$.

Appendix F Logistic regression

We only present the proof for the logistic model (1) as there is nothing fundamentally changing for the GM model (2). Specifically, the PO can be identified following the exact same procedure as in Section C.4 and the analysis of the AO uses the same arguments as what is presented below.

Identifying the PO. The logistic-loss minimization in (10) is equivalent to:

where, recall from (59), that the responses $y_{i}$ depend on the feature vectors $\mathbf{w}_{i}$ used for training as follows: $y_{i}\sim{\rm{Rad}}\left(f(\boldsymbol{\beta}_{0}^{T}\,\mathbf{w}_{i}+\sigma z_{i})\right),~{}z_{i}\sim\mathcal{N}(0,1).$ By rotational invariance of the Gaussian distribution of the feature vectors, we assume without loss of generality that $\boldsymbol{\beta}_{0}=[s,0,...,0]^{T}$. Further let us define

such that $w_{i}$ and $\mu$ are the first entries of $\mathbf{w}_{i}$ and $\boldsymbol{\beta}$, respectively. In this new notation

and the minimization of the logistic loss in (118) becomes

For ${\mathcal{B}}>0$ large enough constant (to be specified later), consider the set

and the “bounded version” of (164) given by:

Forming the AO. In view of (31), we associate the PO with a sequence of bounded AO problems as follows:

where ${\bf g}\sim\mathcal{N}({\bf 0},{\bf I}_{n})$ and ${\bf h}\sim\mathcal{N}({\bf 0},{\bf I}_{p-1})$. Having identified the sequence of AO problems, we proceed by simplifying them to problems involving only a few number of scalar variables. As will be seen later, this will facilitate inferring their asymptotic behavior as required by the conditions of Corollary A.1.

where in the second line we have denoted the Moreau envelope of the logistic loss function as:

The optimization above is jointly convex in $(\alpha,\mu)$ and concave in $\lambda$. Thus, we may flip the order of the min-max, which yields:

Asymptotic behavior of ${\phi}_{\mathcal{L,B}}^{(n)}$. Define,

For any $\lambda>0$, the function $(\alpha,\mu)\mapsto\mathcal{R}_{n}(\alpha,\mu,\lambda)$ is jointly convex in $(\alpha,\mu)$ (e.g., [TPT20, Lem. A2]) and converges to $(\alpha,\mu)\mapsto\mathcal{R}(\alpha,\mu,\lambda)$. But, convergence of convex functions is uniform over compact sets [AG82, Cor. II.1]. It thus converges uniformly over the set $\left\{(\alpha,\mu)\ |\ \alpha\geq 0,\ \alpha^{2}+\mu^{2}\leq\mathcal{B}^{2}\ \right\}$. Hence, for any $\lambda>0$, the function

Next, we argue that the convergence above is essentially uniform. To see this note that the functions in (129) and (130) are concave (as the pointwise minimum of concave functions). Moreover, the function is level-bounded, which can be shown as follows. For $\mathcal{B}\geq\sqrt{2}$, it can be checked that

and hence, the function (130) is level-bounded. We may now use [TAH18, Lem. 10] to conclude that

Note that we can flip the order of the min-max in $\overline{\phi}_{\mathcal{L,B}}$ since $\mathcal{R}$ is convex in $(\alpha,\mu)$ and concave in $\lambda$. We thus also have:

Checking the conditions of Corollary A.1. Let $\overline{\phi}_{\mathcal{L}}$ be given by:

Assume that $\overline{\phi}_{\mathcal{L}}$ has a unique minimizer $(\alpha^{\star},\mu^{\star})$, which will be proven later. Then, for $\mathcal{B}$ sufficiently large (e.g., any ${\mathcal{B}}>2((\alpha^{\star})^{2}+(\mu^{\star})^{2})$),

Based on this and on the previous analysis, we have thus far shown that $\overline{\phi}_{\mathcal{L,B}}$ converges almost surely to $\overline{\phi}_{\mathcal{L}}$, i.e.,

Using a “deviation argument” and uniqueness of solutions of $\overline{\phi}_{\mathcal{L}}$, which will be shown next, it can be further shown that

The deviations argument is similar to the proof of SVM in Section C.3 and we omit the details.

This proves the desired formulae for the cosine similarity and the risk similar to (91) in Section C.3.1.

Uniqueness of the minimizer of $\overline{\phi}_{\mathcal{L}}$. Our goal here is to prove that if $\kappa<\kappa_{\star}$, then $\overline{\phi}_{\mathcal{L}}$ given by

admits a unique minimizer $\alpha^{\star}$ and $\mu^{\star}$. We proceed with the following change of variable $\Upsilon:=\frac{\mu}{\alpha}$ and write $\overline{\phi}_{\mathcal{L}}$ as:

We start by proving that for any $\alpha$ and $\Upsilon$, the optimum for $\lambda$ cannot be achieved as $\lambda\to 0^{+}$.

Using this observation, the derivative of $\mathcal{D}$ with respect to $\lambda$ can be lower-bounded as follows:

Continuing from (141), as $\lambda\to 0$, the event $1_{\{|H|+\Upsilon|G|\leq\frac{1}{2\lambda}\}}$ occurs with probability one. Hence,

where in (142) we first recall the definition of $g(\kappa)$ in (15) and further apply Lemma D.1, i.e., $\kappa<\kappa_{\star}\implies\kappa<g(\kappa)$. This proves that the supremum is not attained in the limit $\lambda\to 0$.

Next, we prove that there exists a unique $\alpha^{\star}$ minimizing $\alpha\mapsto\alpha\min_{\Upsilon}\sup_{\lambda\geq 0}\mathcal{D}(\frac{1}{\alpha},\Upsilon,\lambda)$. For this, it will suffice to prove the following two statements:

Proof of (143): It will suffice to prove that the function

is (jointly) strictly convex in the variables $(\alpha,\Upsilon)$. Indeed, this would imply that $\alpha\mapsto\inf_{\Upsilon}\sup_{\lambda\geq 0}\mathcal{{D}}(\alpha,\Upsilon,\lambda)$ is strictly convex. In its turn, this would mean that its perspective function $\alpha\mapsto\alpha\min_{\Upsilon}\sup_{\lambda\geq 0}\mathcal{{D}}(\frac{1}{\alpha},\Upsilon,\lambda)$ is also strictly convex. Thus, in what follows, we prove that (145) is strictly convex. Fix any ${\lambda}>0$ (it suffices to consider strictly positive ${\lambda}$ since we have already shown that the supremum in (145) is not attained at ${\lambda}\rightarrow 0^{+}$). Let us define