Support vector machines and linear regression coincide with very high-dimensional features

Introduction

The support vector machine (SVM) and ordinary least squares (OLS) are well-weathered approaches to fitting linear models, but they are associated with different learning tasks: classification and regression. In this paper, we study the case in which the models return exactly the same hypothesis for sufficiently high-dimensional data.

Although the optimization problems in (1) and (2) are very different, they have been observed to coincide in very high-dimensional regimes. The study of this support vector proliferation (SVP) phenomenon—in which every training example is a support vector—was recently initiated by Muthukumar et al. and Hsu et al. . Roughly speaking, they show that SVP occurs when $d=\Omega(n\log n)$ for a broad class of sample distributions, and that SVP does not occur when $d=O(n)$ in an idealized isotropic Gaussian case.

SVP is a phenomenon that connects linear classification and linear regression, topics that have received renewed attention due to the break-down of classical analyses of these methods in high-dimensions. For instance, some analyses of SVM that are based on the number of support vectors become vacuous when this number becomes large [e.g., 44, 20, 19]. Similarly, overparameterized linear regression is typically only studied in noisy settings with explicit regularization. It was not until recently that SVM and OLS have been meaningfully analyzed in these regimes (see Section 1.2), and the connection between the two approaches via SVP has played an important analytical role .

In this work, we further examine support vector proliferation with the goal of broadly understanding when and why SVMs and OLS coincide. We pose and study the following questions:

How general is the SVP phenomena? What relationship between $d$ and $n$ determines if the solutions to (1) and (2) coincide?

We close the $\log n$ gap from the prior work of Hsu et al. by showing that $d\gtrsim n\log n$ is necessary for SVP to occur under a model of independent subgaussian features, even with constant probability. Our lower-bounds hold for a broad class of distributions over ${\mathbf{x}}_{i}$, and they match the upper-bounds from . This demonstrates that SVP is extremely unlikely to occur in the much-studied $d=\Theta(n)$ setting.

Is there a sharp threshold separating the occurrence and non-occurrence of this phenomenon? Is this threshold universal across all “reasonable” distributions over each ${\mathbf{x}}_{i}$?

We hypothesize that a sharp phase transition occurs at $d=2n\log n$. We rigorously prove this hypothesis for isotropic Gaussian features and quantitatively bound the width of the transition. We experimentally observe the same transition for a wide range of other distributions.

Section 2 introduces the SVM and OLS approaches in full generality, our $\lambda$-anisotropic subgaussian data model, and prior results about SVP. Several equivalent characterizations of SVP are established (Proposition 1) for use in subsequent sections.

Section 3 characterizes when SVP does not occur for a broad range of distributions (Theorem 3). Our lower-bound on the dimension required for SVP matches the upper-bounds from in the isotropic Gaussian setting, resolving the open question from that work, and also gives new lower-bounds for anisotropic cases. The proof works by tightly controlling the spectrum of the Gram matrix and establishing anti-concentration via the Berry-Esseen Theorem.

Section 4 establishes a sharp threshold of $d=2n{\log{n}}$ for SVP in the case of isotropic Gaussian samples, and also characterize the width of the phase transition (Theorem 4).

Section 5 provides empirical evidence that the sharp threshold observed in Section 4 holds for a wide range of random variables. Rigorous statistical methodology inspired by Donoho and Tanner is used to test our “universality hypothesis” that the probability of SVP does not depend on the underlying sample distribution as $d$ and $n$ become large.

2 Related work

Muthukumar et al. initiate the study of SVP in part to facilitate generalization analysis of the SVM in very high-dimensional settings. Their work, as well as the contemporaneous work of Chatterji and Long , shows that the SVM enjoys low test error in certain regimes where classical learning-theoretic analyses would otherwise yield vacuous error bounds. (In fact, one of the settings in requires polynomially-higher dimension than is typically studied: $d=\Omega(n^{2}\log n)$.) The coincidence between SVM and OLS identified by Muthukumar et al. was also more recently used by Wang and Thrampoulidis and Cao et al. for analyses of linear classification in very high dimensions under different data distributions.

The generalization analysis of Muthukumar et al. concerns a data model inspired by the spiked covariance model of Wang and Fan . They identify a regime of overparameterization where the hard-margin SVM classifier has good generalization (i.e., classification risk going to 0) even when all the training samples are supoort vectors. Our new lower bound can be regarded as establishing a limit on this approach to the analysis of SVM; specifically, if the (effective) dimension is not sufficiently large, the OLS and SVM solutions may not coincide.

Prior analyses of number of support vectors.

Besides its relevance to generalization analysis, the number of support vectors in an SVM model is an interesting quantity to study in its own right. Hsu et al. sharpen and extend the analysis of Muthukumar et al. about SVP in the independent features model that we also adopt. They prove that SVM on $n$ samples with $d$ independent subgaussian components coincides with OLS when $d=\Omega(n\log n)$ with probability tending to $1$. They also give a converse result stating that the coincidence fails with constant probability when $d=O(n)$ in the isotropic Gaussian feature model. (We give these results here as Theorems 1 and 2 respectively.) Our results generalize and tighten the latter bound to tell an asymptotically sharp story about the phase transition for both isotropic and anisotropic random vectors with subgaussian components. Our specific analysis for the isotropic Gaussian case gives the exact point of the phase transition.

The number of support vectors is also studied in the context of variants of SVM , including the soft-margin SVM and the $\nu$-SVM . In these cases, the asymptotic number of support vectors is shown to be related to the noise rate in the problem. The setups we study are linearly separable, which makes it possible to study the hard-margin SVM (without regularization). The hard-margin SVM is also of interest because it captures the implicit bias of gradient descent on the logistic loss objective for linear predictors .

Phase transitions have been studied in the context of linear classification , and SVMs in particular , but most study qualitative changes in behavior other than support vector proliferation. The most relevant is the study of Buhot and Gordon , who employ techniques from statistical physics to show the existence of phase transitions for the generalization error, margin size, and number of support vectors as $n$ and $d=\Theta(n)$ become arbitrarily large. While they characterize the fraction of samples that are support vectors, they do not address our question about when all samples are support vectors, not just a large fraction. Indeed, our results demonstrate that their regime where $d$ grows linearly with $n$ will not exhibit support vector proliferation when $n$ and $d$ in the limit.

Overparameterized linear regression.

There has been a recent flurry of analyses of overparameterized linear regression models [e.g., 5, 4, 21, 34, 32, 33, 47, 29, 35, 48, 24]. Many of these analyses are carried out in the $d=\Theta(n)$ asymptotic regime, whereas our work studies a phase transition that occurs in a much higher-dimensional regime. The notions of effective dimensions we use are present in the analyses of Bartlett et al. and Muthukumar et al. , and the latter work identifies regimes where SVM and OLS coincide and enjoy good performance for both classification and regression.

High-dimensional geometry and universality.

Preliminaries

This section introduces notation, as well as the optimization problems and data models we consider. We also define support vector proliferation and prove the equivalence of different formulations.

2 Optimization problems

Our results in Sections 3–5 concern $p=2$, and we discuss $p=1$ in Section 6. It is worth mentioning that feasibility is not a concern in the settings we consider.When $d\geq n$, we are always able to find a separating hyperplane since the features are linearly independent with high probability. In fact, a theorem of Cover shows that feasibility holds with high probability under mild distributional assumptions even for $d>n/2$. An example $({\mathbf{x}}_{i},y_{i})$ is called a support vector if it lies exactly on the margin defined by separator $w$, or equivalently if $y_{i}w^{\scriptscriptstyle{\mathsf{T}}}{{\mathbf{x}}_{i}}=1$. It is well-known that $w$ can be represented as a non-negative linear combination of all $y_{i}{\mathbf{x}}_{i}$ where ${\mathbf{x}}_{i}$ is a support vector .

Per the convention mentioned in the introduction, the solution of (Interpolation Primal) when $p=2$ is referred to as ordinary least squares. Feasibility is ensured as long as the feature vectors ${\mathbf{x}}_{i}$ are linearly independent.

3 Equivalent formulations of SVP

We study the phenomenon of support vector proliferation (SVP), i.e., the occurrence in which every example ${\mathbf{x}}_{i}$ is a support vector. Because ${\mathbf{x}}_{i}$ is a support vector if $y_{i}w^{\scriptscriptstyle{\mathsf{T}}}{{\mathbf{x}}_{i}}=1$, this occurs if and only if the solution of (SVM Primal) coincides exactly with that of (Interpolation Primal). Here, we analyze those formulations to show equivalent conditions needed for SVP, which we give in Proposition 1. Before presenting the proposition, we introduce the notation needed to use the alternate formulations.

The solutions $w$ to (SVM Primal) and (Interpolation Primal) are identical.

$\Pi_{\mathbf{T}}(\mathbf{0})\in\mathbf{T}^{+}$.

Moreover, if $p=2$, then properties (1)–(4) are also equivalent to the following:

For all $i\in[n]$, $y_{i}y_{\setminus i}^{\scriptscriptstyle{\mathsf{T}}}{\mathbf{K}}_{\setminus i}^{-1}{\mathbf{X}}_{\setminus i}{\mathbf{x}}_{i}=y_{i}\Pi_{\mathbf{T}_{\setminus i}}(\mathbf{0})^{\scriptscriptstyle{\mathsf{T}}}{\mathbf{x}}_{i}/\|\Pi_{\mathbf{T}_{\setminus i}}(\mathbf{0})\|_{2}^{2}<1.$

We prove Proposition 1 in Appendix A. The equivalence between (1) and (5) in the $p=2$ case was proved by Hsu et al. [23, Lemma 1]. Our alternative proof is based on establishing the equivalence of (4) and (5) and draws heavily from our geometric formulation of SVP.

4 Data model

We use the data model of Hsu et al. , where every labeled sample $({\mathbf{x}}_{i},y_{i})$ has ${\mathbf{x}}_{i}$ drawn from an anisotropic subgaussian distribution with independent components and arbitrary fixed labels $y_{i}$.

We only consider fixed labels $y$ that do not depend on ${\mathbf{X}}$. However, we do not consider this to be a major limitation of this work. As discussed before, Cover shows that linear separability is overwhelmingly likely in the high-dimensional regimes we consider. Moreover, our results can be extended to a setting where ${\mathbf{y}}_{i}=\text{sign}\left(v^{\scriptscriptstyle{\mathsf{T}}}{{\mathbf{x}}_{i}}\right)$ for some fixed weight vector $v$.

5 Previous results

We tighten and generalize the characterization of the SVP threshold by Hsu et al. . We give versions of their results that are directly comparable to our results in Sections 3 and 4.

They note the logarithmic separation between Theorems 1 and 2 and the limitations of the data model used in Theorem 2. The authors pose an improvement in generality and asymptotic tightness to their lower-bound as an open problem, which we resolve in the subsequent sections.

SVP threshold for anisotropic subgaussian samples

We closely characterize when support vector proliferation does and does not occur through the following theorem, which serves as a converse to Theorem 1.

Consider a $\lambda$-anisotropic subgaussian sample $({\mathbf{X}},y)$ and any $\delta\in(0,\frac{1}{2})$. For absolute constants $C_{1},C_{2},C_{3},C_{4}$, assume that $\lambda$ and $n$ satisfy

In addition, the result can be generalized to subgaussian ${\mathbf{x}}_{i}$ with general variance proxies $\gamma\geq 1$. We present the current version for the sake of simplicity and note that the generalization is straightforward.

In the case where $({\mathbf{X}},y)$ is an isotropic subgaussian sample, Theorem 3 and Theorem 1 (from ) together establish that the threshold for SVP occurs at $d=\Theta(n\log n)$. Theorem 3 sharpens and generalizes the partial converse of given in Theorem 2.

Theorem 3 does not depend explicitly on the ambient dimension $d$; instead, it only involves the effective dimension proxies $d_{2}$ and $d_{\infty}$, which can be finite even if $d$ is infinite. Thus, the result readily extends to infinite-dimensional Hilbert spaces.

We prove the theorem in Appendix B and briefly summarize the techniques here. By Proposition 1, it suffices to show that with probability $1-\delta$, ${\mathbf{K}}$ is invertible and

where ${\mathbf{K}}_{\setminus i}:={\mathbf{X}}_{\setminus i}{\mathbf{X}}_{\setminus i}^{\scriptscriptstyle{\mathsf{T}}}$. This same equivalence underlies the proof of Theorem 2 in . However, their application of this equivalence is limited because they avoid issues of dependence between random variables by instead lower-bounding the probability that $y_{1}y_{\setminus 1}^{\scriptscriptstyle{\mathsf{T}}}{\mathbf{K}}_{\setminus 1}^{-1}{\mathbf{X}}_{\setminus 1}{\mathbf{x}}_{1}\geq 1$. This forces their bound to hold only when $d=O(n)$. We obtain a tighter bound by separating the first $m$ samples (denoted ${\mathbf{X}}_{[m]}$) for some carefully chosen $m$ and relating the term to the maximum of $m$ independent random variables. To do so, we lower-bound the left-hand side of (4) with the following decomposition:

We prove that this decomposition (and hence, also (4)) is at least 1 with probability $1-\delta$ by lower-bounding the three terms with Lemmas 1, 3, and 4 (given in Appendix B). We bound the first two terms for all $i\in[m]$ by employing standard concentration bounds for subgaussian and subexponential random variables and by tightly controlling the spectrum of ${\mathbf{K}}_{\setminus i}$. To bound the third term, we relate the quantity for each $i\in[m]$ to an independent univariate Gaussian with the Berry-Esseen theorem and apply standard lower-bounds on the maximum of $m$ independent Gaussians.

The assumptions in (3) are all intuitive and necessary for our arguments. The first assumption ensures that enough samples are drawn for high-probability concentration bounds to exist over collections of $n$ variables. The second assumption guarantees the sub-sample size $m$ is sufficiently large to have predictable statistical properties; this is asymptotically tight with its counterpart in Theorem 1 up to a factor of $\log\frac{1}{\delta}$. The third ensures that the variance of each $y_{i}y_{\setminus i}^{\scriptscriptstyle{\mathsf{T}}}{\mathbf{K}}_{\setminus i}^{-1}{\mathbf{X}}_{\setminus i}{\mathbf{x}}_{i}$ term is sufficiently small. The fourth assumption rules out $\lambda$-anisotropic subgaussian distributions with $\|\lambda\|_{2}^{2}\ll\|\lambda\|_{\infty}^{2}n$, where a single component of each ${\mathbf{x}}_{i}$ is disproportionately large relative to others and causes unfavorable anti-concentration properties.

Exact asymptotic threshold for Gaussian samples

Section 3 shows the existence of a change in model behavior when $d=\Theta(n\log n)$ without identifying a precise threshold where this phase transition appears. Here, we refine that analysis for the isotropic Gaussian case to find such an exact threshold. That is, if $d=2\tau n\log n$, as $n$ becomes large, SVP will occur when $\tau>1$ and will not occur when $\tau<1$. Roughly speaking, this phenomenon stems from the fact that terms in (4) are weakly correlated, which causes (4) to behave similarly to a maximum of independent Gaussians. Furthermore, we characterize the rate at which the phase transition sharpens. The following theorem shows that if the convergence $\tau\to 1$ is slow enough, then the asymptotic probabilities of SVP are degenerate and the width of the transition is bounded.

Let $({\mathbf{X}},y)$ be an isotropic Gaussian sample. Let $(\epsilon_{n})_{n\geq 1}$ be any sequence of positive real numbers such that $\limsup_{n\to\infty}\epsilon_{n}<2-c_{1}$ for some $c_{1}>0$ and $\liminf_{n\to\infty}{\epsilon_{n}\sqrt{\log{n}}}>C_{2}$ for some $C_{2}>0$ depending only on $c_{1}$. Then,

Theorem 4 characterizes the width of the phase transition: the difference $w_{n}$ between the values of $d$ where the probability of SVP is (say) $0.9$ and $0.1$ satisfies $w_{n}=O(n\sqrt{\log{n}})$.

It remains an open problem to determine if this transition width estimate is sharp. Specifically, the bound can be sharpened by exhibiting some sequence $\epsilon_{n}$ for which the asymptotic probability of support-vector proliferation is non-degenerate.

The proof of Theorem 4 is given in Appendix C. In the case where $d=(2-\epsilon_{n})n{\log{n}}$, the proof mirrors that of Theorem 3, but deviates in the final step by using the limiting distribution of the maximum of independent Gaussians. When $d=(2+\epsilon_{n})n{\log{n}}$, we follow the basic argument in the proof of Theorem 1 from , but we sharpen the analysis by taking advantage of Gaussianity to find the limiting probability as $n\to\infty$.

Experimental validation of SVP phase transition and universality

While Theorem 4 identifies the exact SVP phase transition for only isotropic Gaussian samples, we demonstrate experimentally that a similarly sharp cutoff occurs for a broader category of data distributions. These experiments suggest that the phase transition phenomenon extends beyond the distributions with independent subgaussian components considered in Theorem 3, and that it occurs at the same location ($d=2n\log n$), with the transition sharpening as $n\to\infty$.

Figure 1 shows a heat map of $\hat{\mathbf{p}}(n,d;\mathcal{D},M)$ with $M=400$. The striking similarity across the distributions suggests that SVP is a universal phenomenon for a broad class of sample distributions that vary qualitatively in different aspects: biased vs. unbiased, continuous vs. discrete, bounded vs. unbounded, and subgaussian vs. non-subgaussian. Moreover, the boundary at which the sharp transition occurs is visibly indistinguishable across the different sample distributions.

Here, $\Phi(t)$ is the standard normal distribution function, $\tau=d/(2n\log n)$, and the model parameters are $\mu^{(i)}_{0}(\mathcal{D})$ and $\mu^{(i)}_{1}(\mathcal{D})$ for $i\in\{0,1,2\}$ and the six different distributions $\mathcal{D}$ (shown in Table 1 in Appendix D.1). Figure 2 visualizes the fitted Probit function $p$ for fixed $n$ and $\tau$ and demonstrates that the model provides a very accurate approximation of $\hat{\mathbf{p}}$.

The universality hypothesis corresponds to the model in which the parameters $\mu^{(i)}_{0}(\mathcal{D})$ are “tied together” (i.e., forced to be the same) for all distributions $\mathcal{D}$. That is, only the parameters scaled down by a factor of $\sqrt{n}$, $\mu^{(i)}_{1}(\mathcal{D})$, are allowed to vary with $\mathcal{D}$. The scaling ensures that their effect tends to zero as $n\to\infty$. The alternative (non-universality) hypothesis corresponds to the model in which all parameters (both $\mu^{(i)}_{0}(n,\mathcal{D})$ and $\mu^{(i)}_{1}(n,\mathcal{D})$ for each $i$) are allowed to vary with $\mathcal{D}$. We compare the models’ goodness-of-fit using analysis of deviance . Our main finding is that the experimental data are consistent with the universality hypothesis (and also that we can reject a null hypothesis in which all parameters are “tied together” for all $\mathcal{D}$). The details and model diagnostics are given in Appendix D.2.

Finally, in Appendix D.3, we provide empirical support for the generality of Remark 3, namely that the transition width is roughly $n\sqrt{\log n}$ for data models other than Gaussian ensembles.

Conjecture 1 and the other questions raised in this work point to a broader scope of investigations about high-dimensional phenomena and universality concerning optimization problems commonly used in machine learning and statistics. Our results, along with those from prior works, provide new analytic and empirical approaches that may prove useful in tackling these questions.

Acknowledgments and Disclosure of Funding

D. Hsu acknowledges support from NSF grants CCF-1740833 and IIS-1563785, NASA ATP grant 80NSSC18K109, and a Sloan Research Fellowship. C. Sanford acknowledges support from NSF grant CCF-1563155 and a Google Faculty Research Award to D. Hsu. N. Ardeshir acknowledges support from Columbia Statistics Department. This material is based upon work supported by the National Science Foundation under grant numbers listed above. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation. We acknowledge computing resources from Columbia University’s Shared Research Computing Facility project, which is supported by NIH Research Facility Improvement Grant 1G20RR030893-01, and associated funds from the New York State Empire State Development, Division of Science Technology and Innovation (NYSTAR) Contract C090171, both awarded April 15, 2010.

References

Appendix A Proofs for Section 2

The proof henceforth proceeds under the assumption that ${\mathbf{K}}$ is invertible. Since ${\mathbf{K}}$ is symmetric, the invertibility of ${\mathbf{K}}$ implies that all of its principal minors (i.e., the ${\mathbf{K}}_{\setminus i}$’s) are invertible.

This is immediate from the fact that the definition of SVP corresponds exactly to the equality constraints that are present in (Interpolation Primal) and not in (SVM Primal).

(2) ⇔iff\iff (3):

By Holder’s inequality, if we take $q$ to be the dual of $p$ (i.e. $\frac{1}{p}+\frac{1}{q}=1$), then $|w^{\scriptscriptstyle{\mathsf{T}}}u|\leq\|w\|_{p}\|u\|_{q}$, with equality when $|u_{i}|^{q}$ is proportional to $|w_{i}|^{p}$. Therefore,

(3) ⇔iff\iff (4):

(4) ⇔iff\iff (5):

By the (Interpolation Projection) formulation, $\Pi_{\mathbf{T}}(\mathbf{0})$ can be alternatively interpreted as the projection of the origin onto the affine space $\mathbf{T}$. Therefore we have,

The following steps show the equivalence:

We find an explicit expression for $\Pi_{\mathbf{T}}(\mathbf{0})$:

An analogous expression for $\Pi_{\mathbf{T}_{\setminus i}}(\mathbf{0})$ can be found for any fixed $i$ by the same method, which gives the desired equivalence by combining with (6).

First Step: Fix some index $i\in[n]$. Since $\Pi_{\mathbf{T}_{\setminus i}}({\mathbf{A}}_{i})$ is on the affine space $\mathbf{T}_{\setminus i}$, which is closed under affine linear combination, one can express $\mathbf{T}$ in the following way:

By the definition of the projection onto $\mathbf{T}$, we represent $\Pi_{\mathbf{T}}(\mathbf{0})=a^{*}\left({\mathbf{A}}_{i}-\Pi_{\mathbf{T}_{\setminus i}}({\mathbf{A}}_{i})\right)+u^{*}$ where,

It is straightforward to see that $a^{*}=a_{i}^{*}$ by comparing this representation with equation (5) alongside with the fact that ${\mathbf{A}}_{i}-\Pi_{\mathbf{T}_{\setminus i}}({\mathbf{A}}_{i})$ is orthogonal to $\mathbf{T}_{\setminus i}$:

To find $a^{*}$, we sequentially optimize over $u$, substitute its optimal value, and then optimize over $a$. It suffices to minimize $\left\|u\right\|_{2}^{2}$ because $u^{\scriptscriptstyle{\mathsf{T}}}({\mathbf{A}}_{i}-\Pi_{\mathbf{T}_{\setminus i}}({\mathbf{A}}_{i}))$ is constant for all $u\in\mathbf{T}_{\setminus i}$ due to orthogonality and the definition of $\mathbf{T}_{\setminus i}$. Hence, $u^{*}=\Pi_{\mathbf{T}_{\setminus i}}(\mathbf{0})$ is optimal. Subsequently, by optimizing over $a$ and setting the derivative to zero,

For the last step, we combine the facts that $\Pi_{\mathbf{T}_{\setminus i}}(\mathbf{0})^{\scriptscriptstyle{\mathsf{T}}}u$ is constant over $\mathbf{T}_{\setminus i}$ and $\Pi_{\mathbf{T}_{\setminus i}}(\mathbf{0})\in\mathbf{T}_{\setminus i}$. Note that the denominator is non-zero because the invertibility of ${\mathbf{K}}$ implies that ${\mathbf{A}}_{i}$ will not lie on the span of the remaining rows ${\mathbf{A}}_{\setminus i}$, and hence will not be in ${\mathbf{T}}_{\setminus i}$. This immediately proves (6).

This problem can be easily understood using a simple Cauchy-Schwarz inequality,

In conclusion, we can express the projection as,

Appendix B Proofs for Section 4

We prove Theorem 3, which we restate below.

As discussed in Section 3, it suffices to prove that ${\mathbf{K}}_{\setminus i}$ is invertible for all $i$ and

with probability $1-\delta$ for some $m\leq n$. We do so by showing that the following three events each hold with probability $1-\frac{\delta}{3}$:

It remains to plug in the results of Lemmas 1, 3, and 4 to show that the three events occur with high probability given the conditions imposed on $n$, $d_{2}$, $d_{\infty}$, and $\delta$ in (3). Let $m:=\lceil\exp(\frac{d_{2}}{2C_{2}n})\rceil$. By (3), $m\leq\sqrt{n}+1\leq\frac{n}{{\log{n}}}\leq\frac{n}{2}$ for sufficiently small constant $C_{1}$.

By Lemma 1 in Appendix B.1 with $\delta:=\frac{\delta}{3m}$, it follows that for any fixed $i\in[m]$, ${\mathbf{K}}_{\setminus i}$ is invertible and

with probability at least $1-\frac{\delta}{3m}$ as long as the following conditions hold:

We show that the inequalities in (8) and (9) are implied by the preconditions of Theorem 3 in (3) by choosing sufficiently large constants $C_{1}$, $C_{3}$, and $C_{4}$. For (8),

which implies the desired inequality. To establish (9):

By applying a union bound to all $m$ events, they all occur with probability at least $1-\frac{\delta}{3}$.

By applying Lemma 3 in Appendix B.2 for all $i\in[m]$ with $\delta$ as before and union-bounding over the corresponding events, with probability $1-\frac{\delta}{3}$,

Both inequalities follow from the third inequality of (3) for sufficiently large $C_{3}$ and by $m\leq\frac{n}{\log n}$.

with probability $1-\frac{\delta}{3}$, if

The inequalities are satisfied as immediate consequences of (3) and the fact that $m=\lceil\exp(\frac{d_{2}}{2C_{2}n})\rceil\leq\frac{n}{2}$ for sufficiently small $C_{2}$. ∎

In the subsequent three sections, we prove Lemmas 1, 3, and 4.

To guarantee that $|y^{\scriptscriptstyle{\mathsf{T}}}({\mathbf{K}}^{-1}-\left\|\lambda\right\|_{1}^{-1}I_{n}){\mathbf{X}}{\mathbf{x}}^{\prime}|\leq\epsilon$ with probability $1-\delta$ for some $\epsilon>0$, it suffices to show that

for universal constants $c_{3}^{\prime}$ and $c_{4}$.

The proof of Lemma 1 relies heavily on a concentration bound on the eigenvalues of the Gram matrix ${\mathbf{K}}$, which draws from a technical lemma of Hsu et al. . We present and prove this result below and then use it to prove Lemma 1.

where $\left\|\cdot\right\|$ denotes the spectral (operator) norm. If additionally $d_{\infty}\geq c_{3}(n+\log\frac{1}{\delta})$ for some universal constant $c_{3}$, then for the same event, ${\mathbf{K}}$ is invertible and

Equation (10) follows from Lemma 8 of Hsu et al. . For some universal constant $c^{\prime}$ and sufficiently large $c$, we have the following:

If equation (11) holds and $c_{3}$ is sufficiently large, then all eigenvalues of ${\mathbf{K}}$ are strictly positive and ${\mathbf{K}}$ is invertible. We now derive equation (11) by bounding the eigenvalues of ${\mathbf{K}}^{-1}$, assuming that the event in equation (10) occurs, and rescaling $c$:

Conditioned on ${\mathbf{X}}$, $y^{\scriptscriptstyle{\mathsf{T}}}({\mathbf{K}}^{-1}-\|\lambda\|_{1}^{-1}I_{n}){\mathbf{X}}{\mathbf{x}}^{\prime}$ is a univariate subgaussian random variable with mean 0 and variance proxy at most $\|y^{\scriptscriptstyle{\mathsf{T}}}({\mathbf{K}}^{-1}-\|\lambda\|_{1}^{-1}I_{n}){\mathbf{X}}\|^{2}\|\lambda\|_{\infty}$, as long as ${\mathbf{K}}$ is invertible. We bound the variance proxy and show that ${\mathbf{K}}$ is invertible with high probability by applying Lemma 2 for some universal $c^{\prime}$ with probability $1-\frac{\delta}{2}$:

We observe that the bound holds for a proper choice of $c$ for a standard concentration bound for a subgaussian random variable. ∎

B.2 Concentration of leave-one-out terms

To ensure that $\left\|\lambda\right\|_{1}^{-1}|y^{\scriptscriptstyle{\mathsf{T}}}{\mathbf{X}}{\mathbf{x}}^{\prime}|\leq\epsilon$ with probability $1-\delta$ for some $\epsilon>0$, it suffices to show that

We have the claim by dividing by $\|\lambda\|_{1}$. ∎

B.3 Anti-concentration for independent leave-one-out terms

and all ${\mathbf{q}}_{j}$ and ${\mathbf{z}}_{i,j}^{\prime}$ are independent and that ${\mathbf{q}}_{j}$ is subgaussian with variance proxy $n/\|\lambda\|_{1}^{2}$. The proof of the claim is powered by the Berry-Esseen theorem and comes in two parts:

We first show that ${\mathbf{X}}$ is well-behaved with high probability; we say that ${\mathbf{X}}$ is good if the following hold:

We prove that \mathbf{P}[\text{{\mathbf{X}}is good}]\geq 1-\frac{2\delta}{3}.

Then, we use the Berry-Esseen Theorem to show that, for each $i\in[m]$,

Because $\left\|\lambda\right\|_{1}^{-1}y_{i}^{\prime}y^{\scriptscriptstyle{\mathsf{T}}}{\mathbf{X}}{\mathbf{x}}_{i}^{\prime}$ for $i\in[m]$ are conditionally independent given ${\mathbf{X}}$, we obtain the desired statement:

The claim follows from the Hanson-Wright inequality , the lower-bound on $n$ with respect to $\delta$, the assumption $d_{\infty}^{2}\geq c_{4}d_{2}n$, and the fact $\left\|\lambda\right\|_{4}^{4}\leq\left\|\lambda\right\|_{2}^{2}\left\|\lambda\right\|_{\infty}^{2}$.

for sufficiently large absolute constant $c_{4}$.

𝐗𝐗{\mathbf{X}} satisfies (13) with high probability.

We introduce a different sequence of random variables ${\mathbf{r}}_{1},\dots,{\mathbf{r}}_{n}$ to eliminate any dependence on $d$. Set $0=k_{0}<k_{1}<\dots<k_{n}=d$ such that for all $i\in[n]$,

Such a partition is possible because we can require that $\|\lambda\|_{\infty}^{2}\leq\|\lambda\|_{2}^{2}/n$ by assuming $c_{4}$ is large enough. Let

Note that all ${\mathbf{r}}_{i}$ are independent and that

Because $\mathbf{E}[{\mathbf{q}}_{j}]=0$ and $\mathbf{E}[{\mathbf{q}}_{j}^{2}]=n/\|\lambda\|_{1}^{2}$, we can bound $\mathbf{E}[{\mathbf{r}}_{i}]$:

We upper-bound $\max_{j}|\lambda_{j}{\mathbf{q}}_{j}|$ by noting that $\max_{j}|\lambda_{j}{\mathbf{q}}_{j}|\leq\max_{i}\sqrt{{\mathbf{r}}_{i}}$. By the Hanson-Wright inequality, the subgaussianity of ${\mathbf{q}}_{i}$, and the lower-bound on $n$ with respect to $\delta$,

for some absolute constants $c^{\prime}$ and for a sufficiently large setting of $c_{1}$. Thus, (13) is satisfied with probability $1-\frac{\delta}{3}$ by a union bound.

Bound on term given good 𝐗𝐗{\mathbf{X}}.

We use the Berry-Esseen theorem to relate the maximization over $\|\lambda\|_{1}^{-1}y^{\scriptscriptstyle{\mathsf{T}}}{\mathbf{X}}{\mathbf{x}}_{1}^{\prime}$ to a maximization over standard Gaussians. Consider some fixed good ${\mathbf{X}}$ (and hence, fixed ${\mathbf{q}}_{j}$ for all $j\in[d]$). Then, for some absolute constant $c$ and for univariate standard Gaussian ${\mathbf{g}}$,

Because each ${\mathbf{z}}_{i,j}$ is subgaussian, $\mathbf{E}[{\mathbf{z}}_{i,j}^{3}]\leq\rho=O(1)$ for some $\rho$. We simplify the expression by plugging in the second and third moments of ${\mathbf{z}}_{i,j}^{\prime}$ and rescaling $t$:

Because we assume that ${\mathbf{X}}$ is good, we plug in our upper-bound on $\max_{j}|\lambda_{j}{\mathbf{q}}_{j}|$ and lower-bound on $\sum_{j=1}^{d}\lambda_{j}^{2}{\mathbf{q}}_{j}^{2}$.

We now bound the first term by invoking the Mills ratio bound for the Gaussian distribution function (Fact 1) with the assumption that $c_{2}\leq\frac{1}{8}$. The remainder of the inequalities follow by enforcing that $c_{1}$ and $c_{2}$ be sufficiently large and small respectively:

which above holds when $m\geq(\log\frac{3}{\delta})^{2}$ and is ensured by a sufficiently large choice of $c_{3}$. ∎

The following well-known fact is the Mills ratio bound.

Let $\Phi$ denote the standard Gaussian distribution function. Then for any $t\geq 0$,

B.4 Modification of Theorem 3 to support dependent labels

While an apparent weakness of Theorem 3 is the fixed labels $y$, this can be surmounted. Here, we outline how the proof can be easily modified to include labels ${\mathbf{y}}_{i}=\text{sign}\left(v^{\scriptscriptstyle{\mathsf{T}}}{\mathbf{x}}_{i}\right)$ for some unit vector $v$ for the isotropic Gaussian case; we believe this can be further generalized, but we present this version for the sake of simplicity.

We can prove this fact for the simple Gaussian setting by taking advantage of the fact that orthogonal components of a spherical Gaussian are independent. For all $i$, we write ${\mathbf{x}}_{i}=(v^{\scriptscriptstyle{\mathsf{T}}}{\mathbf{x}}_{i})v+{\mathbf{x}}_{i}^{\prime}$ where $v^{\scriptscriptstyle{\mathsf{T}}}{\mathbf{x}}_{i}^{\prime}=0$. Then

By independence and symmetry, each term in the last sum is distributed identically to ${v^{\scriptscriptstyle{\mathsf{T}}}{\mathbf{x}}_{j}v^{\scriptscriptstyle{\mathsf{T}}}{\mathbf{x}}_{i}}+{\mathbf{x}}_{j}^{\prime{\scriptscriptstyle{\mathsf{T}}}}{\mathbf{x}}_{i}^{\prime}={\mathbf{x}}_{j}^{\scriptscriptstyle{\mathsf{T}}}{\mathbf{x}}_{i}$. This gives the claim.

Appendix C Proofs for Section 4

In this section, we give the proof of Theorem 4.

We divide the proof into two cases, which we each prove in the two following subsections.

We first consider the case where the dimension is below the threshold, specifically $d=(2-\epsilon_{n})n\log n$.

Our proof follows the same strategy as that of Theorem 3. Let $m:=n/\log n$ and assume $n$ is sufficiently large so that $m\leq n/2$. Using the equivalence from Proposition 1, it suffices to show that the following event has probability tending to $1$:

For any $C_{0}>0$ and $c_{1}\in(0,2)$, there exists $C_{2}>0$ and $n_{0}>0$ such that the following statements hold for all $n\geq n_{0}$, and all $\epsilon_{n}$ satisfying $2-c_{1}\geq\epsilon_{n}\geq C_{2}/\sqrt{\log n}$ for all $n\geq n_{0}$, with $d=(2-\epsilon_{n})n\log n$:

$\displaystyle\mathbf{P}\left[{\mathbf{K}}_{\setminus i}\text{ is invertible,}\ \max_{i\in[m]}\left|y_{i}y_{\setminus i}^{\scriptscriptstyle{\mathsf{T}}}\left({\mathbf{K}}_{\setminus i}^{-1}-\frac{1}{d}I_{n-1}\right){\mathbf{X}}_{\setminus i}{\mathbf{x}}_{i}\right|\leq\frac{\epsilon_{n}}{2C_{0}}\right]\geq 1-\frac{1}{n}$.

$\displaystyle\mathbf{P}\left[\max_{i\in[m]}\left|\frac{1}{d}y_{i}y_{[m]\setminus i}^{\scriptscriptstyle{\mathsf{T}}}{\mathbf{X}}_{[m]\setminus i}{\mathbf{x}}_{i}\right|\leq\frac{\epsilon_{n}}{2C_{0}}\right]\geq 1-\frac{1}{n}$.

We start with the first claim. By Lemma 1 and a union bound, we have with probability at least $1-1/n$, ${\mathbf{K}}_{\setminus i}$ is invertible and

For sufficiently large $n$, we have $d\geq c_{1}n\log n$ and

The second term on the right-hand side is at most $C_{2}/(4C_{0}\sqrt{\log n})$ for sufficiently large $n$, and hence at most $\epsilon_{n}/(4C_{0})$. The first term on the right-hand side is also at most $\epsilon_{n}/(4C_{0})$ provided that

(since we already assume $\epsilon_{n}\leq 2-c_{1}$ for sufficiently large $n$). This is satisfied provided that $C_{2}\geq 12C_{0}C$. This proves the first claim.

For the second claim, we have by Lemma 3 (with $n$ in the statement of Lemma 3 set to $m-1$) and a union bound, we have with probability at least $1-1/n$:

where the second inequality uses $m=n/\log n\leq n/2$ and holds for sufficiently large $n$, with $C^{\prime}>0$ an absolute constant. The second term on the right-hand side is at most $C_{2}/(4C_{0}\sqrt{\log n})$ for sufficiently large $n$, and hence also at most $\epsilon_{n}/(4C_{0})$. The first term on the right-hand side is also at most $\epsilon_{n}/(4C_{0})$ provided that

Since $\epsilon_{n}\leq 2-c_{1}$, the above condition holds as long as $C_{2}\geq 4\sqrt{C_{0}C^{\prime}/c_{1}}$. This proves the second claim. ∎

For any $C_{0}>4$ and $c_{1}\in(0,2)$, there exists $C_{2}>0$ such that the following holds for all sequences $(\epsilon_{n})$ satisfying $2-c_{1}\geq\epsilon_{n}\geq C_{2}/\sqrt{\log n}$ for all large enough $n$, with $d=(2-\epsilon_{n})n\log n$:

Observe that conditioned on ${\mathbf{X}}_{\setminus[m]}$, the $m$ random variables

are distributed as independent mean-zero Gaussian random variables with variance

where $\sigma^{2}$ is as defined above, and ${\mathbf{g}}_{1},\dotsc,{\mathbf{g}}_{m}$ are i.i.d. standard Gaussian random variables, independent of $\sigma^{2}$.

where the second inequality follows from standard approximations of the Gamma function, and the final inequality holds assuming $C_{2}\geq 1$.

Let $\mathsf{E}$ be the event in which (15) holds. Then

We claim that the probability on the right-hand side tends to $1$ with $n\to\infty$ as well.

The distribution of the random variable $\max_{i\in[m]}{\mathbf{g}}_{i}$ obeys a limiting Gumbel distribution; specifically, for all $x>0$,

where $C>0$ is an absolute constant . Therefore, it suffices to show that for all $x>0$, we have

for all sufficiently large $n$. Dividing through by $\sqrt{2\log n}$ and using $m=n/\log n$, the above inequality is implied by

Since $0\leq\epsilon_{n}\leq 2-c_{1}$, we have

by a Taylor series argument. So, (16) is implied by

Since $\epsilon_{n}\geq C_{2}/\sqrt{\log n}$ and $T(n)=o(1/\sqrt{\log n})$, we can choose $C_{2}$ large enough so that (16) holds for all sufficiently large $n$. ∎

We conclude as in the proof of Theorem 3. The event in which all of the following hold has probability approaching $1$ as $n\to\infty$ by combining Lemma 5 and Lemma 6 and a union bound:

$\max_{i\in[m]}\left|y_{i}y_{\setminus i}^{\scriptscriptstyle{\mathsf{T}}}\left({\mathbf{K}}_{\setminus i}^{-1}-\frac{1}{d}I_{n-1}\right){\mathbf{X}}_{\setminus i}{\mathbf{x}}_{i}\right|\leq\frac{\epsilon_{n}}{2C_{0}}$;

$\max_{i\in[m]}\left|\frac{1}{d}y_{i}y_{[m]\setminus i}^{\scriptscriptstyle{\mathsf{T}}}{\mathbf{X}}_{[m]\setminus i}{\mathbf{x}}_{i}\right|\leq\frac{\epsilon_{n}}{2C_{0}}$;

$\max_{i\in[m]}\frac{1}{d}y_{i}y_{\setminus[m]}^{\scriptscriptstyle{\mathsf{T}}}{\mathbf{X}}_{\setminus[m]}{\mathbf{x}}_{i}\geq 1+\frac{\epsilon_{n}}{C_{0}}$.

In this event, there exists $i\in[m]$ such that

C.2 Above the threshold

Now we consider the case where the dimension is above the threshold, specifically $d=(2+\epsilon_{n})n\log n$.

By Proposition 1, it suffices to show that

This is implied by the following lemma combined with a union bound over all $i\in[n]$.

There exists $C_{2}>0$ and $n_{0}>0$ such that the following statement holds for all $n\geq n_{0}$, and all $\epsilon_{n}$ satisfying $\epsilon_{n}\geq C_{2}/\sqrt{\log n}$ for all $n\geq n_{0}$, with $d=(2+\epsilon_{n})n\log n$:

Conditional on ${\mathbf{X}}_{\setminus i}$ (and the probability $1$ event that ${\mathbf{X}}_{\setminus i}$ has rank $n-1$), the distribution of

By Lemma 2, we have for some absolute constant $C>0$ and sufficiently large $n$, with probability at least $1-1/n^{2}$,

where $C^{\prime}>0$ is a constant depending only on $C$. Let $\mathsf{E}$ be the aforementioned event. Then

where the final inequality follows by the Mills ratio bound (Fact 1). By letting $C_{2}\geq 2C^{\prime}$, we have

(since we assume $\epsilon_{n}\geq C_{2}/\sqrt{\log n}$), upon which bound in (17) is at most

Appendix D Supplementary material for Section 5

As described in Section 5, we show the significance of this universality by providing a parametric model that complies with the given universality hypothesis and fits well to the observed rates of SVP. That is, this model permits slight difference for different sample distributions, as long as this difference decays to zero with $n$. Furthermore, we show that the model becomes statistically insignificant if we incorporate extra parameters to allow non-decaying dependence on sample distributions to conclude universality.

Alongside these universality results, we experimentally support the universality of the bounds on transition width, which are proved for the isotropic Gaussian sample case in Section 4.

These analyses are implemented in Python and R. Our code-base can be found on Github at https://github.com/scO0rpion/SVM-Proliferation-NIPS2021.

We conduct a Monte Carlo simulation in order to validate our theoretical results and grasp their generality to distributions with different tail distributions. For the range $(n,d)\in\{40,42,\dots,100\}\times\{100,110,\dots,1000\}$ we study our problem in the following way:

We used the quadratic program solver from CVXOPT CVXOPT is distributed at https://cvxopt.org/ under a GPLv3 license. to solve (Interpolation Dual) with $p=q=2$ to tolerance level $10^{-7}$.

We report the fraction $\hat{\mathbf{p}}$ of $M$ trials that exhibit SVP. Based on Figure 4, we choose the simulation size value $M=400$ as an appropriate choice for having small enough variance for our range of $(n,d)$. Throughout this section, we run $M=400$ simulations unless stated otherwise.

D.2 Observed universality

Let $\hat{\mathbf{p}}\coloneqq\hat{\mathbf{p}}(n,d;\mathcal{D},M)\sim\text{Binom}(p(n,d;\mathcal{D}),M)$ be the observed SVP rate corresponding to a sample distribution $\mathcal{D}$ with independent components and with simulation size $M$. Due to the log-linear dependence of the dimension $d$ of SVP threshold occurs on $n$ from Theorem 4, we parameterize the probability of SVP as a function of $n$ and $\tau\coloneqq d/\left(2n\log n\right)$ instead. The objective here is to provide a reasonable parametric model for $\hat{\mathbf{p}}(n,d;\mathcal{D})$ as an inferential tool to test the universality hypothesis. To do so, we translate our universality hypothesis in the language of our parametric model and ensure that necessary statistical assumptions hold to make inferential claims.

We use Probit regression (a generalized linear model with Probit link function) to explain the transition behavior and allow the coefficients to depend explicitly on the distribution $\mathcal{D}$ under which sample components are drawn from. We justify this specific choice of link function at the end of this subsection. We propose the following parametric model; we motivate the terms in the model at the end of the subsection as well.

is the Probit link function (i.e., the standard normal distribution function).

The universality hypothesis can be translated to a testing framework under the model described (18) by prohibiting $\mu^{(i)}_{0}(\mathcal{D})$ from depending on the underlying distribution $\mathcal{D}$.

Universality Hypothesis: $\mu^{(1)}_{0}(\mathcal{D})$ are identical for each distribution $\mathcal{D}$, and $\mu^{(1)}_{0}(\mathcal{D})=\mu^{(2)}_{0}(\mathcal{D})=0$.

Alternative Hypothesis: $\mu^{(i)}_{0}(\mathcal{D})$ depends on the underlying distribution $\mathcal{D}$ for some $i\in\{0,1,2\}$.

The Universality Hypothesis permits differences from the ground mean (which must decay to zero as $n$ grows large), but requires that other terms be identical. The Alternative Hypothesis instead permits non-decaying difference among distributions. We show that our model does not reject the Universality Hypothesis.

Inference:

We perform Probit regressions on observed SVP rates $\hat{{\mathbf{p}}}$ sequentially on three different models, each of which is a sub-model of its successor. The second and third models correspond to the Universality Hypothesis and the Alternative Hypothesis respectively. We compare their goodness-of-fit using analysis of deviance (ANOVA) to assess whether each subsequent model restriction meaningfully improves on its predecessor’s ability to fit the data .

Model 1: Does not allow any deviations for different distributions; i.e., $\mu^{(i)}(n,\mathcal{D})$ does not depend on $\mathcal{D}$ for $i\in\{0,1,2\}$.

Model 2: Allows deviations in bias that decay to zero; i.e., only $\mu^{(i)}_{1}(n,\mathcal{D})$ may vary with $\mathcal{D}$.

Model 3: Full model described in Equation (18).

Based on this sequential test given in Table 2, we find that Model 1 should be rejected, because Model 2 substantially improves on it in a statistically significant manner. Furthermore, no statistical significance were detected for rejecting Model 2, and nearly all the excessive parameters (for Model 3) were statistically insignificant. Therefore, we accept Model 2, which complies with the Universality Hypothesis.

Assuming that the Probit model is well-specified (e.g., the residuals satisfy the usual assumptions), we conclude that Model 2 is significant. The remainder of the section argues that the Probit model is the most appropriate for this setting. A full analysis of all three fitted models, including the fitted model parameters and p-values for these parameters, can be found in the code repository.

Motivating the model:

The proposed model (18) is supported by a series of empirical observations about the SVP rate $\hat{{\mathbf{p}}}$:

$\hat{{\mathbf{p}}}$ increases as $\tau$ increases and is mostly unaffected as $n$ changes (left panel (a) of Figure 2). Therefore, the dependence on $n$ should be negligible.

$\hat{{\mathbf{p}}}$ is asymmetric around the theoretical boundary $\tau=1$ (left panel (a) of Figure 2). This behavior motivates the non-linear term in our proposed model and likely originates from the asymmetry of the limiting Gumbel distribution in Section 4.

As $\tau$ varies, the slope of $n\mapsto p(n,\tau;\mathcal{D})$ changes, which motivates including terms that manage the interaction between $n$ and $\tau$ (right panel (b) in Figure 2).

As suggested by Donoho and Tanner , including a dependence on $1/\sqrt{n}$ is motivated by the theory of Edgeworth expansions, which states that the non-asymptotic behaviour of a random Gaussian problem decays to its asymptotic behavior by some power of the “problem size.”

Model diagnostics:

While our proposed model yields formal evidence of universality, it remains to show that the model is correct, particularly because even wrong models are often statistically significant. To avoid this pitfall, we validate the underlying assumptions required to make inferential claims in our logistic regression model. Figure 6 demonstrates that Model 2 accurately approximates the observed probabilities $\hat{{\mathbf{p}}}$ when the probabilities are not too close to one or zero. These extreme cases are not concerning because we are primarily interested in values of $d$ and $n$ where the asymptotic probabilities are non-degenerate. The significance of Model 2 continues to hold, even if we restricted attention to a smaller region with non-degenerate SVP rates $\hat{{\mathbf{p}}}$, such as $\tau\in[0.4,1.6]$. The figure further shows that the residuals approximately follow a standard normal distribution and do not seem to correlate with the fitted values. Therefore, the residuals corresponding to this model satisfy the usual assumptions necessary for regression.

Justification for the link function and log:

We test three link functions for Model 2 to choose an appropriate one for our parametric model (18):

We justify the use of $\log{\tau}$ as a non-linear term in (18) by substituting the logarithmic term with the Cox-Box transform of $\tau$, i.e., $\left(\tau^{\gamma}-1\right)/\gamma$ and cross-fitting various link functions with different exponents $\gamma=0.2,0.4,0.5,1$. The diagnostic plots in Figure 7 indicate that the Probit link function fits best. Moreover, smaller values of $\gamma$ fit observed probabilities better by comparing the deviance r-squares in Table 3 as a measure of goodness of fit. Hence, we use the $\log\tau$, which is the limit of the Cox-Box transform when $\gamma\to 0$.

D.3 Width of transition

To estimate the width of the phase transaction, we adopt a non-parametric approach. For $q<1/2$ and fixed $n$ we define the $q$-transition zone to be the range $[\tau_{q},\tau_{1-q}]$, where $\tau_{q}$ and $\tau_{1-q}$ correspond to the ratio $d/\left(2n{\log{n}}\right)$ for smallest and largest value of $d$ where support vector proliferation occurs with probability $q$ and $1-q$ respectively. In other words, within this range, the corresponding probabilities are inside $[q,1-q]$ interval.

Formally, we define scaled $q$-transition width estimate as,

where $\operatorname{\Phi}$ is the Probit link function introduced in (18) and $\hat{\tau}_{q}$ and $\hat{\tau}_{1-q}$ are plug-in estimates of $\tau_{q}$ and $\tau_{1-q}$. We plot $\hat{w}_{q}(n,d)$ with $n$ in Figure 8.

Appendix E Supplementary material for Section 6

By the Fundamental Theorem of Linear Programming, the optimal solution(s) to (Dual L1) lie on corner points of the polytope

in the dual space. The following lemma provides an alternate characterization the optimal solution $\alpha^{*}$ to the linear program by relating the corner points of $\mathcal{C}^{*}$ to the faces of its dual polytope, $\mathcal{C}$.

Figure 9 for a Gaussian Ensemble with $n=2$ and $d=1500$ and illustrates the relationships between $\mathcal{C}$, $\mathcal{C}^{*}$, $\alpha^{*}$, and ${\mathbf{A}}_{.,i}$. The geometric intuition conveyed in the figure is limited by its low value of $n$; we expect qualitatively different behavior to arise when $n$ is large, particularly when considering the geometry of the facets of $\mathcal{C}$. For instance, when $n=2$, very few samples correspond to corners of the convex hull, and the vast majority lie in the interior. When $n$ is larger, almost all of the samples will be corners of the convex hull, unless $d$ grows exponentially with $n$.

To prove Lemma 8, we make use of several useful facts about the geometric properties of dual polytopes, which are immediate consequences of Farkas’ Lemma [see 31].

The origin $\mathbf{0}$ is in the interior of $\mathcal{C}$ and $\mathcal{C}^{*}$.

Corner points of $\mathcal{C}^{*}$ are perpendicular to facets (boundary hyperplanes) of $\mathcal{C}$.

If $\alpha^{*}$ is an optimal solution, then zero must be a subgradient of the objective at $\alpha^{*}$. Since the set of subgradients of $\alpha\mapsto\max_{i\in[2d]}{\mathbf{B}}_{i}^{\scriptscriptstyle{\mathsf{T}}}\alpha$ at $\alpha$ is $\operatorname{Conv}\{{\mathbf{B}}_{i}:i\in I_{\alpha}\}$, where $I_{\alpha}=\{i\in[2d]:\langle{\mathbf{B}}_{i},\alpha\rangle=\max_{i^{\prime}\in[2d]}{\langle{\mathbf{B}}_{i^{\prime}},\alpha\rangle})\}$ denotes the set of active constraints at $\alpha$, an optimal solution $\alpha^{*}$ must satisfy

This convex hull is a face of $\mathcal{C}$ since $\langle{\mathbf{B}}_{j},\alpha^{*}\rangle<\langle{\mathbf{B}}_{i},\alpha^{*}\rangle=1$ for any $j\notin I_{\alpha^{*}}$ and $i\in I_{\alpha^{*}}$. Moreover, since $\alpha^{*}$ is also a corner point of $\mathcal{C}^{*}$ we have $|I_{\alpha^{*}}|=n$. Combining with Fact 2, we conclude that $\alpha^{*}$ must be perpendicular to the facet of $\mathcal{C}$ that intersects with the ray passing through $\mathbf{1}$. Existence of such a facet is ensured by the fact that origin is in the interior of $\mathcal{C}$. ∎

Based on the previous relationship between support vector proliferation and the faces of a random convex polytope, we can prove a very loose bound on the minimum dimension $d$ needed for support vector proliferation to occur by bounding the number of faces of the polytope. When $d=O\left(n\right)$, the polytope will have far fewer than $2^{n}$ facets, which makes it impossible for most orthants to to be covered by projections from $\mathbf{0}$ onto facets. This (along with rotational invariance of the standard Gaussian distribution) allows us to show that support vector proliferation occurs with a negligibly small probability in this regime.

A key geometric insight for the proof is supplied by . Let $k^{*}$ be the maximum integer $k$ such that every $k$ points from among $\{\pm{\mathbf{A}}_{\cdot,i}:i\in[d]\}$ spans a $k$-dimensional face of $\mathcal{C}$ (i.e., their convex hull is a $k$-dimensional face of $\mathcal{C}$). Then $k^{*}=\Omega_{\mathbf{P}}(\frac{n}{\log(d/n)})$ for large enough values of $n$ and $d$. Hence, it is plausible to expect that every selection of $n$ points spans a facet of $\mathcal{C}$.

The right-hand side converges to zero as $n\to\infty$ provided that $d<Cn$ for some absolute constant $C\approx 1.29$. ∎