Support vector machines and linear regression coincide with very high-dimensional features
Authors: Navid Ardeshir
Clayton Sanford
Daniel Hsu
Venue: NeurIPS 2021 Poster (2021)
Keywords: support vector machines
high-dimensional statistics
interpolation
least squares regression

Abstract: The support vector machine (SVM) and minimum Euclidean norm least squares regression are two fundamentally different approaches to fitting linear models, but they have recently been connected in models for very high-dimensional data through a phenomenon of support vector proliferation, where every training example used to fit an SVM becomes a support vector. In this paper, we explore the generality of this phenomenon and make the following contributions. First, we prove a super-linear lower bound on the dimension (in terms of sample size) required for support vector proliferation in independent feature models, matching the upper bounds from previous works. We further identify a sharp phase transition in Gaussian feature models, bound the width of this transition, and give experimental support for its universality. Finally, we hypothesize that this phase transition occurs only in much higher-dimensional settings in the $\ell_1$ variant of the SVM, and we present a new geometric characterization of the problem that may elucidate this phenomenon for the general $\ell_p$ case. 

Support vector machines and linear regression coincide with very high-dimensional features
Navid Ardeshir* Dept. of Statistics Columbia University na28448columiia edu
Clayton Sanford*
Daniel Hsu Dept. of Computer Science Columbia University dj djssuucs columbia. edu
Dept. of Computer Science Columbia University
claytonecs www.anoccs.oolmma.......
Abstract
The support vector machine (SVM) and minimum Euclidean norm least squares regression are two fundamentally different approaches to fitting linear models, but they have recently been connected in models for very high-dimensional data through a phenomenon of support vector proliferation, where every training ex- ample used fit an SVM becomes a support vector. this paper, we explore the generality of this phenomenon and make the following contributions. First, we prove a super-linear lower bound on the dimension (in terms of sample size) re- quired for support vector proliferation in independent feature models, matching the upper bounds from previous works. We further identify a sharp phase transition Gaussian feature models, bound the width of this transition, and give experimental support for its universality. Finally, we hypothesize that this phase transition occurs only in much gigeer-dimeniionl settings in the l variant of the SVM, and we present a new geometric characterization of the problem that may elucidate this phenomenon for the general ly case.
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 digeesiiensional data.
The mard-margin SVM is linear classification model that finds the separating hyperplane that maximizes the minimum margin of error for every training sample. If the training data (x1, "1)...., (Xn, Vn) E Rdd {=1} are linearly separable, then the resulting linear classifier is - sign (x' (gVM), where WgVM is the solution to the following optimization problem:
WSVM = arg min ||wll2 such that you x; 2 1, Vi E [n].
(1)
wEB
An example x; is support vector if the corresponding constraint is satisfied with equality, and the optimal solution WSVM linear combination of these support vectors.
Ordinary least squares regression finds the linear function that best fits the training data (x1, v1)...., (Xn, Vn) E Fd x R according to the sum of squared enrors. When the solution is not unique, it natural to take the solution of minimum Fuclidean norm; this is the convention we
adopt. Taking X = [xi]... xx,"" Raxd and y := (y1,-.., Dn), the solution is the hypothesis x + WOLST where WOLS the solution to the following: woLs = arg min,ers [|w]] such that
X X'y. In many nigh-dimensional settings (e.g.. where X has full row rank), the solution may in fact interpolate the training data, i.e.,
WOLS = arg min ||w]|2 such that wT w'x; = Des Vi [n].
wERd
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Although the optimization problems in ① and 2 are very different, they have been observed to coincide in very highddimensional regimes. The study of this support vector proliferation (SVP) phenomenon-iln in which every training example is support vector-was recently initiated by Muthukumar et al. 35 and Hsu al. [23] Roughly speaking, they show that SVP occurs when d = Sn log v.) for a broad class of sample distributions, and that SVP does not occur when d = (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 high-dimensions. For instance, some analyses of SVM that are based on the number of support vectors become vacuous when this number becomes large [c.g.. 19. 20, 44] 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.2h. and the connection between the two approaches via SVP has played an important analytical role 35 46
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:
1. How general is the SVP phenomenu? What relationship between d and n determines if the solutions to ① and coincide?
We close the log n. gap from the prior work of Hsu et al. 23 by showing that Z n log n is necessary for SVP to occur under model of independent subgaussian features, even with constant probability. Our lower-bounds hold for broad class of distributions over X,, and they match the upper-bounds from (23). This demonstrates that SVP is extremely unlikely occur in the much-studied d = ((n) setting.
2. ly there a sharp threshold separating the occurrence and non-occurrence of this phenomenon? Is this threshold universal across all "reasonable" distributions over each x.?
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.
3. Is support vector proliferation specific to the by SVM problem? If [ and (2) are generalized to instead minimize Ep norms, does this still occur at the same rate?
We re-frame this question with a geometric characterization of the dual of the SVM optimization problem for Lp norms. We conjecture that a similar phase transition occurs for L,, but also that it requires much larger dimension d; this is supported by preliminary experiments.
1.1 Outline of our results
2 introduces the SVM and OLS approaches in full generality, our X-anisotropic subgaussian data model, and prior results about SVP. Several equivalent characterizations of SVP are established (Proposition I for use in subsequent sections.
Section
Section characterizes when SVP does not occur for a broad range of distributions (Theorem B) Our lower-bound on the dimension required for SVP matches the upper-bounds from 23 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 = 2nlog n for SVP in the case of isotropic Gaussian samples, and also characterize the width of the phase transition (Theorem 4p.
Section 5 provides empirical evidence that the sharp threshold observed in Section holds for a wide range of random variables. Rigorous statistical methodology inspired by Donoho and Tanner 16 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.
Section Basks the questions about SVP from the preceding sections in the context of M and minimum f--ormm interpolation. Specifically, the SVP threshold for & is conjectured to occur for (n v log Evidence for this conjecture provided simulation study and in geometric arguments about random linear programs.
2

---

1.2 Related work
Prior works connecting SVP and generalization. Muthukumar et al. B51 initiate the study of SVP in part facilitate generalization analysis of the SVM in very high-dimensional settings. Their work, as well as the contemporaneous work of Chatterji and Long [T0], shows that the SVM enjoys low test error in certain regimes where classical Garning-theoretee analyses would otherwise yield vacuous error bounds. (In fact, one of the settings in [[0] requires polynomially-hgghe
dimension than is typically studied: d (2(n² logn).) The coincidence between SVM and OLS identified by Muthukumar et al. was also more recently used by Wang and Thrampoulidis [6] 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 [47]. They identify a regime of overparameteriizttoo where the hard-margin SVM classifier has good generalization (i.e., classification risk going to 0) even when all the training samples 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.
supoort vectors. Our new lower bound can be regarded establishing a limit
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. 23 sharpen and extend the analysis of Muthukumar et al. (35 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 = 22(n log n) with probability tending to 1. They also give converse result stating that the coincidence fails with constant probability when d (n)) in the isotropic Gaussian feature model. (We give these results here as Theorems [ 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 39], including the soft-margin SVM [2] and the D-SVM (37]. 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-margh 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 (25 38)
40 and SVMs in particular 77 [4 28 30), but most study qualitative changes in behavior other than support vector proliferation. The most relevant is the study of Buhot and Gordon [7]. 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 = ((n) become arbitrarily large. While they characterize the fraction of samples that are support vectors, they do not address samples are support vectors, not just large fraction. Indeed, our results demonstrate that their regime where d grows linearly with n will not exhibit support vector proliferation when and d in the limit.
Phase transitions have been studied in the context of linear classification
13
question about when all
Overparameterized linear regression. There has been a recent flurry of analyses of overparame- terized linear regression models [e.g..4 21 24
Many of these analyses are carried out in the d = O(n) asymptotic regime, whereas our work studies a phase transition that occurs in much nigher-dimensional regime. The notions of effective dimensions we use present in the analyses of Bartlett et al. [4] and Muthukumar et al. (35), and the latter work identifies regimes where SVM and OLS coincide and enjoy good performance for both classification and regression.
29
32
35
47
48
High- diggnsiamnnio geometry and universality. Our conjecture about support vector proliferation for & SVMS derives inspiration from studies of nigh-dimensional geometric phase transitions, particularly those by 15 These results consider the geometry of random polytopes. Amelunxen and Bürgisser [I] establish phase transitions on the feasibility and boundedness of the solutions to random linear programs, Amelunxen et al. 2 extend these results to characterize when -norm minimizing solutions to sparse recovery problems are exactly correct, and Donoho and Tanner [[S] bound the number of faces of random polytopes. We also borrow heavily from [66 when designing our experiments in Section 5 to test the universality hypothesis.
3

---

2
Preliminaries
This section introduces notation, well as the optimization problems and data models we consider. We also define support vector proliferation and prove the equivalence of different formulations.
2.1 Notation
For À E [24, we define the l2 and for dimension proxies as d2 = |1 and doo == Let [n] := {l,..., ra). For some vector IR" and matrix A E Raxd we let wy and A; denote the ith element of w and row of A respectively; likewise, we let A., E IR represent the jth column of We abuse notation to let W/ = [W]) W;-1 Wi+1, W.) E R W|m]] = (Wi..... Wm) E RT, Wi, Wi]m = (wm+11.... Wn) E g--m, and Wim]ss = (WIm)) va E R=-1 for E [m] and m E [m]. Analogous notation holds for Aq Alm]- A Amm- and Amm]y 2- We frequently consider the Gram matrix K == XX" E R= for feature matrix X E IR=xd; for these matrices, we let K = XX E and J'mi ( A) represent the largest and smallest eigenvalues of the matrix respectively, and let || be the operator norm of A. For some vector RR, we let diag(y) E IR=x be a diagonal matrix with (diag(y)),, = y/s. Throughout, boldface characters refer to random variables.
(=(=11)((- and analogously define [mn- K [mm] and [m] Let Mmmxx A)
2.2 Optimization problems
We consider the hard-margin support vector machine (SVM) optimization problem and ask under what conditions one may expect all the slackness conditions to be satisfied. We consider training samples (x1, 1/)...................... (Xm, Dn) Rd x {#1} } in high-dimensional regime where d >> n with design matrix X := [xi]...(xx] [x.]" Ruxd and Gram matrix K = XXT Raxn, In full generality, the separating hyperplane corresponding to the SV- problem for some 2 1 is the solution to the following optimization problem:
min ||0||p such that y x, 2 1, Vi E [n]] EER
(SVM Primal)
Our results in Sections 3 concern p = 2, and we discuss p 1 in Section 6 It worth mentioning
that feasibility is not concern in the settings we consider An example (x,, y:) is called a support
vector if it lies exactly on the margin defined by separator well-known that w can be represented as a non-negative linear combination of all y,x; where x, is support vector 43
equivalently if yow x; = 1. It is
We contrast the weights of the classifier returned by SVM Primal with the weights of minimum f--norm that satisfy the normal equations of ordinary least squares (OLS). In the case where the training data can be linearly interpolated, this optimization problem is:
min ||lll such that y, x; = 1, vi [n].
(Interpolation Primal)
weRd
Per the convention mentioned in the introduction, the solution of (Interpolation Primal) when p is referred to as ordinary least squares. Feasibility is ensured as long as the feature vectors x; are linearly independent.
2.3 Equivalent formulations of SVP
We study the phenomenon of support vector proliferation (SVP), i.c., the occurrence in which every example x; a support vector. Because x; is support vector if y x; 1, this occurs if and only 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 Proposition] [] Before presenting the proposition, we introduce the notation needed to use the alternate formulations.
'hhen d 2 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 [13) shows that feasibility holds with high probability under mild distributional assumptions even for d n/2.

---

We translate the relationship between the two primal optimization problems into the dual space. Taking A X E Iaxd the dual of the optimization problem [Ineerpolation Primal
max oER
a2 such that | S 1.
(Interpolation Dual)
The dual of (SVM Primal is Interpolation Dual with an additional constraint that a E R...
Let T = 1Σ
1 0; = 13 denote the affine plane passing through the rows of A, and let T 12 1 a
i [n], let T 1 a,A;
04 14 a; 2 0} be the convex hull of the rows of A. In addition, for c aq Ap: Eez; d2' 1}. We denote (r) as the fg -g-norm projection of
the origin onto T, which is uniquely defined for < < co.
Proposition 1. Let < p < oo and q = (1 - 1/p) -1, and consider any (X, v) E Raxd x {+1}". Suppose K is invertible. Then, the following equivalent:
(1) SVP occurs for f--SVM.
(2) The solutions w to (SVM Primal) and (Interpolation Primal) are identical.
(3) The optimal solution to (Interpolation Dual) lies within the interior of I2..
(4) (0) TT
Moreover, if 2, then properties (1)- are also equivalent to the following:
(5) For all [m], yau K. X x = y. (0)"x))) II (
This dual framework in (3) and (4) gives an alternative geometric structure to consider for this problem. For the fa-case, this formulation draws from the fact that the separating hyperplane obtained from an SVM is represented as a linear combination of support vectors. Although the l case is not technically covered by Proposition] I (due to the non-strict convexity of & norm), our analysis still gives useful insights, and we explore this case specifically in Section
We prove Proposition T in Appendix A The equivalence between (1) and (5) in the 2 case was proved by Hsu et al. 23 Lemma I]. Our alternative proof is based establishing the equivalence of (4) and (5) and draws heavily from our geometric formulation of SVP.
2.4 Data model
We use the data model of Hsu et al. 23 where every labeled sample (x;, has x; drawn from an anisotropic subgaussian distribution with independent components and arbitrary fixed labels yı. Definition. For some À B& we say (X,y) Rx x {=1}" th (as well (X, Z, y) Raxd x Raxd x {=1)") is a X-anisotropic subgaussian sample iff y = (yI...., . Vn) {+1}² are fixed (non-random) labels; Z |z] ... |z,]" Raxd a matrix of independent 1-subgaussian random variables with E[z,,] 0 and E E 1: and X == [x] ...
Z diag ( 1/2 Raxd We say (X, y) is an isotropic subgaussian sample it is a-anisotropic for > (1. ........ ...,. 1). Finally, we say [X, y) is an isotropic Gaussian sample if it is isotropic subgaussian and each x, ~ Io).
|x,'' [x]
We only consider fixed labels y that do not depend on X. However, we do not consider this to be major limitation of this work. As discussed before, Cover [13] shows that linear separability is overwhelmingly likely in the dige-iimensional regimes we consider. Moreover, our results can be extended to a setting where y, sign (v'x,) for some fixed weight vector v.
2.5 Previous results
We tighten and generalize the characterization of the SVP threshold by Hsu al. 23 We give versions of their results that are directly comparable to our results in Sections 3 and 4
Theorem 1 (Thcorem of (23). Consider a X-anisotropic subgaussian sample (X, y) and any
8 E (0, 1). df = lin log(n (n) log( ()), then SVP occurs for SV- with probability at least 1 Theorem 2 (Theorem 3 of (3).. Consider an isotropic Gaussian sample (X, y). For some constant
8 E (0, 1), if d O(n). then SVP occurs for LV-S with probability at most 8.
5

---

They note the logarithmic separation between Theorems] | and and the limitations of the data model used in Theorem 2 The authors pose an improvement in generality and asymptotic tightness their lower-bound as open problem, which we resolve in the subsequent sections.
3 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 I
Theorem 3 (Lower-bound on SVP threshold for anisotropic subgaussians). Consider a X-anisotropic
subgaussian sample (X, v) and any 8 E (0, })) For absolute constants C1, C2 C2, CA, assume that and satisfy
n M C1 log 1 5) 3) ))²
d2 S C2nlogn. do 2 Cyn Csn 8' and de Cjd2n.
(3)
Then, SVP occurs for 22-SVM with probability at most 6. Remark 1. If each x; is drawn from a Gaussian distribution, then we could instead permit x, to have any positive semi-definite covariance matrix E E Rdxd with eigenvalues X1..... Xa due to rotational invariance.
Remark 2. In addition, the result can be generalized to subgaussian X; with general variance proxies y 1. We present the current version for the sake of simplicity and note that the generalization is straightforward.
In the case where (X, y) is an isotropic subgaussian sample. Theorem 3 and Theorem (from (23 together establish that the threshold for SVP occurs at d O (Onnog log n). Theorem sharpens and generalizes the partial converse of [23 given in Theorem 2
Theorem 3 does not depend explicitly the ambient dimension d; instead, it only involves the effective dimension proxies d2 and doc. which can be finite even is infinite. Thus, the result readily extends to ifinite-dimensiona. Hilbert spaces.
We prove the theorem in Appendix and briefly summarize the techniques here. By Proposition I suffices to show that with probability 1 1 5, K is invertible and
max y. K. x 2 1,
where K- X This same equivalence underlies the proof of Theorem 2 in 23 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ıv" " K, their bound to hold only when
1. This forces On)). We obtain tighter bound by separating the first m samples (denoted 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 ( with the following decomposition:
1
max 4E(m)
K
||ll In-
X xx
+
|||| M: M.y X [m]))
+
||a]], 7. [mj] [m)) X5
We prove that this decomposition (and hence, also (4) is at least with probability - 5 by lower- bounding the three terms with Lemmas and (given in Appendix B). We bound the first two terms for all i E [ma] by employing standard concentration bounds for subgaussian and subexponential random variables and by tightly controlling the spectrum of K; To bound the third term, relate independent univariate Gaussian with the Besre-Esseen theorem
the quantity for each E [m] 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-probabilityy concentration bounds to exist over collections of variables. The second assumption guarantees the sub-sample size m is sufficiently large to have predictable statistical properties; this is asymptotically tight with counterpart in Theorem Tup to factor of log J. The third ensures that the variance of each y.u,, K Xxxx term sufficiently small.
The fourth assumption rules out X-anisotropic subgaussian distributions with [IA & || where a single component of each x; is disproportionately large relative to others and causes unfavorable anti-coneentration properties.

---

4 Exact asymptotic threshold for Gaussian samples
Section shows the existence of a change in model behavior when (n log n) without identifying precise threshold where this phase transition appears. Here, we refine that analysis for the isotropic Gaussian ease to find such an exact threshold. That is, if d 2rn log n, as n becomes large, SVP will occur when т > 1 and will not occur when < 1. Roughly speaking, this phenomenon stems from the fact that terms in 44) 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 the convergence т + is slow enough, then the asymptotic probabilitiess of SVP are degenerate and the width of the transition is bounded.
Theorem 4 (Sharp SVP phase transition). Let (X, y) be an isotropic Gaussian sample. Let (Fn) n2 be any sequence of positive real numbers such that lim supn-4co En < 2 - 01 for some 0y > 0 and lim inf, 6n Vlog n > for some C2 > O depending only on C1. Then,
lim P(SVP occurs for f2-SVM { R2+00
[0
if (2 en en)nlon,
ifd = (2 + en nlogn.
Remark 3. Theorem f characterizes the width of the phase transition: the difference w,, between the values of d where the probability of SVP is (say) 0.9 and 0.1 satisfies w,, = O(n/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 en for which the asymptotic probability of support-vector proliferation is non-degenerate.
The proof of Theorem is given in Appendix C In the case where d = (2 c, nnog 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 + en Jnlog n, we follow the basic argument in the proof of Theorem [ from (23), but we sharpen the analysis by taking advantage of Gaussianity to 00.
find the limiting probability
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 CO.
Our simulation procedure is as follows. We generate data sets (X, y) E Rand {=1)"" where y E [+1]" is a fixed vector of labels with exactly n/2 positive labels, and X1, Xn. Miid. Dod where D is one of six sample distributions on R. For each data set, we check for SVP by solving the problem (Interpolation Primal). and checking if its solution additionally satisfies the constraints from (SVM Primal.. Let p := p(n, d; DD .M) denote the observed frequency of SVP in M 400 independent trials when X E Raxd is generated using D. (Full details are given in Appendix D.1
Figure D shows a heat map of p(n, d; D. M) with M = 400. The striking similarity across the distributions suggests that SVP 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.
We also investigate the universality of SVP using statistical methodology inspired by Donoho and Tanner [66. Specifically, we model p using Probit regression to test our universality hypothesis: that the occurrence of SVP for SV on data with independent features matches the behavior under Gaussian features as and d grow large. Our model is M P Binom(y(n, d; D), M), where
p(n, d: D) ② (1t0) (n, D) + (n, x T (x(())))0))))))))))) (1) D) log
(4) (D) + (D)))
(D)
with (n, D) 4D
Vn
7

---

Bernoull
Gaussian
Gaussian lased
1000
750
500
Number of features (d)
250
0.75
Laplacian
Rademacher
Un Uniform
1000
0.25
750
0.00
500
250
40
60
80
100 40
60
80
100
40
60
80
100
Number of amples (n)
Figure 1: The fraction of M 400 trials where support vector proliferation occurs for samples, features, and six different sample distributions D. All distributions demonstrate sharp phase transitions near the theoretical boundary n. 2n log n, illustrated by the red curve.
Here, ((t) is the standard normal distribution function, d/(2n log n), and the model parameters are 14 (D) and 1 (D) for i E {0, 1, 1, and the six different distributions (shown in Table in Appendix D.I. Figure 2 visualizes the fitted Probit function p for fixed and and demonstrates that the model provides a very accurate approximation of p.
The universality hypothesis corresponds to the model in which the parameters Ho (D) are "tied together" (i.e., forced be the same) for all distributions That is, only the parameters scaled down by a factor of /n., 141 (6) (D), are allowed to vary with D. The scaling ensures that their effect tends to co. The alternative (non-unin monn-universality) hypothesis corresponds to the model in which all
parameters (both 10 (n, D) and (1) (n, D) for each i) are allowed to vary with D. We compare the models' goodness-or of-fit using analysis of deviance [22] 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 "tied together" for all 'D). The details and model diagnostics 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 ny/log n for data models other than Gaussian ensembles.
SVP phase transition for S-SSMss?
Because both the SVM and linear regression problems can be formulated for general fn-nomms, can ask similar questions about when their solutions coincide. Here, we examine the & case: the coincidence of SVM with an E éi-penalty and fn-nrrm minimizing interpolation (also called Basis Pursuit (1].. Linear models with l regularization are often motivated by the desire for sparse weight vectors [e.g..
36
Based on experimental evidence and the differences in nigh-dimensional geometry between foo and & balls, we conjecture that SVP for l SVMS only occurs in a much higher- dimeen-odmniiinnll regime.
Conjecture 1. Let (X, y) E Raxd Th an isotropic Gaussian sample. Then, the probability of SVP occurring for & SVM with X and y undergoes phase transition around = (n), for some

---

1.00-
3-
Observed Probabilites (p)
(Observed Probstalitics)
404,551
6
0.75-
606.777
[8...8
[0
50
0
90
70
[1.11]
-1-
[111.12]
0.25
[121133]
-2
(133.14)
0.00
-3-
(1.5.1.)
1.0
1.5
2.0
2.5
40
60
80
100
Number of Samples (n)
(a)
(b)
Figure 2: Visualizations of SVP frequencies for constant slices of and for d 2nn log n. Left panel (a): The points are (T. P) from the Gaussian samples, for fixing n E (50, 70, 90). The black vertical line corresponds correspond to r for which the model's predicted probabilities are between 0.1 and 0.9. Right panel (b): The points show (n, & (p)) from Gaussian distribution, fixing T to lie in one of 12 different intervals. The Probit model's predictions (averaged over all within an interval) are overlaid.
1. The Probit model's predictions overlaid, and shaded regions
L2
1000
1000
750
750-
1.00
Number of features
0.75
500
500
0.50
0.25
250
250
0.00
20
40
60
40
60
80
100
Number of Samples (n)
Figure 3:
The observed probabilities of support vector proliferation for é and f--SVMs for d- dimensional isotropic Gaussian samples of size n.
f(m) = (n Formally, there exist positive constants e. and é' with S d' such that
So <d<<c((n) if e (()).
lim P (SVP occurs for L1-SVM]
1
Conjecture I is consistent with our preliminary experimental findings, summarized in Figure shows larger values of d relative to n are needed to ensure SVP for f-SVMM and that the transition appears be less sharp. Indeed, the experiments indicate that the true phase transition may occur when d is asymptotically much larger than n log n. They do not rule out the possibility that the transition may even require d = exp(S((n)). Further experimental details are given Appendix E.
Answering whether support vector proliferation occurs the & case is equivalent to determining whether the optimal solution a' to (Interpolation Dual) problem lies the positive orthant R. 2 In the & case, we have oc, so solving the problem amounts to characterizing the solutions to the
While Proposition 1 does not imply this equivalence for 4 SVMs for arbitrary data, the results of the proposition are valid for isotropic Gaussian samples, because the corresponding fox projection 1r (0) in those cases is well-defined almost surely.

---

following linear program for data matrix A diag(y) X E Raxd,
max
s.t. - 1 1
(Dual L1)
OER
=
There is line of work that gives high probability guarantees about whether related random linear programs are feasible and where their solutions reside [ 2 Similar analyses of random linear programs may be useful for understanding how large d must be to have a' E R,,, and we carry out preliminary characterization in Appendix
Conjecture [ and the other questions raised in this work point to a broader scope of investigations about nigh-diimensinal 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 109, and a Sloan Research Fellowship. C. Sanford acknowledges support from NSF grant CCF-1563 and a Google Faculty Research Award to 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 's Shared Research Computing Facility project, which is supported by NIH Research Facility Improvement Grant IG20RR030893-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
[1] Dennis Amelunxen and Peter Büirgisser. Intrinsic volumes of symmetric cones. arXiv preprint 1205 1863, 2012.
[2] Dennis Amelunxen, Martin Lotz, Michael B McCoy, and Joel A Tropp. Living on the edge: Phase transitions in convex programs with random data. Information and Inference: Journal of the IMA, 3(3):224-294) 2014.
[3] Peter L Bartlett and Ambuj Tewari. Sparseness vs estimating conditional probabilities: Some asymptotic results. Journal of Machine Learning Research, 8(Apr):775-790, 2007.
[4] Peter L. Bartlett, Philip M. Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(48):30063-300) Apr 2020.
[5] Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. SIAM Journal on Mathematics of Data Science, 167):116 2020.
[6] Andrew C. Berry. The accuracy of the gaussian approximation to the sum of independent variates. Transactions of the American Mathematical Society, 49(1):122-136, 1941.
[7] Arnaud Buhot and Mirta B Gordon. Robust learning and generalization with support vector machines. Journal of Physics A: Mathematical and General, 34(21):4377-4388 may 2001.
[8] Emmanuel J Candès and Pragya Sur. The phase transition for the existence of the maximum likelihood estimate in high-dimensional logistic regression. The Annals of Statistics, 48(1): 27-42, 2020.
[9] Yuan Cao, Quanquan Gu, and Mikhail Belkin. Risk bounds for over-parameterizee maximum margin classification sub- -ab-gaussian mixtures. arXiv preprint arXiv:2104. 2021.
10

---

[10] Niladri S Chatterji and Philip M Long. Finite-sampa sample analysis of interpolating linear classifiers the overparameterized regime. Journal of Machine Learning Research, 22(129): 2021.
[11] Shaobing Chen and David Donoho. Basis pursuit. Proceedings of 1994 28th Asilomar Conference Signals, Systems and Computers, volume 1, pages 41 44. IEEE, 1994.
[12] Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine learning, 20(3): 273-297, 1995.
[13] Thomas M Cover. Geometrical and statistical properties of systems of linear inequalities with applications pattern recognition. IEEE Transactions on Electronic Computers, 14(3):326-334, 1965.
[14] Rainer Dietrich, Manfred Opper, and Haim Sompolinsky. Statistical mechanics of support vector networks. Physical Review Letters, 82(14):9975, 1999.
[15] David Donoho and Jared Tanner. Counting faces of randomly projected polytopes when the projection radically lowers dimension. Journal of the American Mathematical Society, 22(1): 1 1-53, 2009.
[16] David Donoho and Jared Tanner. Observed universality of phase transitions in high-dimensional geometry. with implications for modern data analysis and signal processing. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 367 (1906):4273-429) 2009.
[17] AP Dvoretsky. Some results on convex bodies and banach spaces. Matematika, 8(1):73-102, 1964.
[18] Ronald Aylmer Fisher and Leonard Henry Caleb Tippett. Limiting forms of the frequency distribution of the largest or smallest member of a sample. In Mathematical proceedings of the Cambridge philosophical society, volume 24, pages 180-190. Cambridge University Press, 1928.
[19] Pascal Germain, Alexandre Lacoste, François Laviolette, Mario Marchand, and Sara Shanian. A PAC-Bayes sample-compression approach to kernel methods. In ICML, 2011.
[20] Thore Graepel, Ralf Herbrich, and John Shawe-Taylon PAC-Bayesian compression bounds on the prediction error of learning algorithms for classification. Machine Learning, 59(1-5):55-76.
2005.
[21] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. arXiv preprint
2019.
[22] Trevor J Hastic and Daryl Pregibon. Generalized linear models. In Statistical models in S, pages 195-247. Routledge, 2017.
[23] Daniel Hsu, Vidya Muthukumar, and Xu. On the proliferation of support vectors in high dimensions. In Twenty-Fourts International Conference on Artificial Intelligence and Statistics, 2021.
[24] Ningyuan Huang, David W Hogg, and Soledad Villar. Dimensionality reduction, regularization, and generalization in overparameterized regressions. arXiv preprint arXiv:2011.114777 2020. 2020.
[25] Ziwei Ji and Matus Telgarsky. The implicit bias of gradient descent on nonseparable data. In Conference Leurning Theory, pages 1772-1798. PMLR, 2019.
[26] Michel Ledoux. The concentration of measure phenomenon. Number 89. American Mathemati- cal Soc., 2001.
[27] Tengyuan Liang and Pragya Sur. A precise high-dimensione asymptotic theory for boosting and minimum-Il-non -normm interpolated classifiers. arXiv preprint arXiv:2002.01586, 2020.
[28] Haoyang Liu. Exact high-dimensional asymptotics for support vector machine. arXiv preprint axXiv:190..05125, 2019.

---

[29] Yasaman Mahdaviyeh and Zacharie Naulet. Risk of the least squares minimum norm estimator under the spike covariance model. arXiv preprint arXiv:1912.13421, 2019.
[30] Dörthe Malzahn and Manfred Opper. A statistical physies approach for the analysis of machine learning algorithms on real data. Journal of Statistical Mechanics: Theory and Experiment, 1005(11):P) 1001, 2005.
[31] Jiri Matousek. Lectures on discrete geometry, volume 212. Springer Science & Business Media, 2013.
[32] Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and double descent curve. arXiv preprint arXiv: 05355, 2019.
[33] Partha P Mitra. Understanding overfitting peaks in generalization error: Analytical risk curves for lg and L penalized interpolation. arXiv preprint arXiv:1906.000 19066036666 2019.
[34] Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai. Harmless interpolation of noisy data in regression. IEEE Journal on Selected Areas in Information Theory, 1(1):67-83, 2020.
[35] Vidya Muthukumar, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel Hsu, and Anant Sahai. Classification vs regression in overparameterized regimes: Does the loss function matter? Journal of Machine Learning Research, 22(222):1-69, 2021.
[36] Andrew Y Ng. Feature selection, 1 vs. 2 regularization, and rotational invariance. In Proceedings of the twenty-first international conference on Machine learning, page 78, 2004.
[37] Bernhard Schölkopf, Alex J Smola, Robert C Williamson, and Peter L Bartlett. New support vector algorithms. Neural computation, 12(5):1207-18 1245, 2000.
[38] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. J. Mach. Learn. Res., 19(1):2822-25) 2878, January 2018
[39] Ingo Steinwart. Sparseness of support vector machines. Journal of Machine Learning Research, 107-1110 2003.
[40] Ryan Theisen, Jason Klusowski, and Michael Mahoney. Good classifiers abundant in the interpolating regime. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, 2021.
[41] Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267-288, 1996.
[42] Lieven Vandenberghe. The cvxopt linear and quadratic cone program solvers, 2010. URL https://www. seas. www.uclal.e..... aaccla.edu/"vandaee httah///aaneebee/ppbblaaaassass conepro.. -ddf]
[43] Vladimir Naumovich Vapnik. Estimation of dependences based on empirical data, Springer- Verlag, 1982.
[44] Vladimir Naumovich Vapnik. The Nature of Statistical Learning Theory. Peringer-Verlag 1995.
[45] Roman Vershynin. Estimation in high dimensions: a geometrie perspective. Sampling theory, a renaissance, pages 3-66. Springer, 2015.
[46] Ke Wang and Christos Thrampoulidis. Binary classification of gaussian mixtures: Abundance of support vectors, benign overfitting and regularization. arXiv preprint 1,X9:2001.09948.0 2021.
[47] Weichen Wang and Jianqing Fan. Asymptotics of empirical eigenstructure for high dimensional spiked covariance. Annals of Statistics, 13442 2017.
[48] Xu and Daniel Hsu, On the number of variables to use in principal component regression. In Advances in Neural Information Processing Systems 32, 2019.
12


Reviews:
[{"review_id": "yJA3OP0DMf-", "reviewer": "Reviewer_cFdd", "summary": "This paper explores the generality of support vector proliferation and makes the following three contributions: (1) proving a super-linear lower bound on the dimension (in terms of sample size) required for support vector proliferation in independent feature models. (2) identifying a sharp phase transition in Gaussian feature models. (3) investigating `the phenomenon of support vector proliferation for $\\ell_1$ variant of the SVM.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper focuses on the phenomenon of support vector proliferation, where every training example used to fit an SVM becomes a support vector.  Specially, this paper studies the case in which support vector machine (SVM) and ordinary least squares (OLS) return exactly the same hypothesis for sufficiently high-dimensional data. In real-world applications, linear regression models are often used to solve classification problems. This paper theoretically tells us when linear regression model is equivalent to the classification model SVM. Here, I list some problems and suggestions from my perspective:\n\n1. For SVM, this paper only focuses on the hard-margin SVM, however, soft-margin SVM is more commonly-used in real-world applications.\n\n2. As stated in lines 27-28, \"When the solution is not unique, it is natural to take the solution of minimum Euclidean norm\". In other words, for OLS, this paper only focuses on the case that the number of feature dimension is larger than the number of examples. This conjecture can also be supported by the conclusion obtained in this paper, $d=O(n \\log n)$. However, in many real-world applications, the number of feature dimension is smaller than the number of examples. Maybe authors consider the nonlinear mapping feature space with kernel trick?\n\n3. The assumption for the data distribution is too strong, and the theoretical results are not verified over real-world data sets. It is better to add some experiments over some widely-used publicly available data sets.\n\n4.  What are the differences of $\\Omega(\\cdot)$, $O(\\cdot)$, $\\Theta(\\cdot)$ and $\\omega(\\cdot)$? For example, line 37: $d = \\Omega (n \\log n) $, $d = O(n)$, line 54: $d = \\Theta (n)$, line 82: $d = \\omega (n \\log n)$.\n\n\n#UPDATES AFTER RESPONSE\nI have read the responses of authors and other reviews. Although authors did not address my concerns, I still would like to keep my acceptance recommendation as I think that this paper is interesting and an accepted paper does not have to be perfect. Thanks.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The potential limitations of this paper from my perspective have been listed in the Main Review above, while this paper has minimal near-term applications with social implications.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "18"}, "extra_text": {}}, {"review_id": "qGrwhPzoWqP", "reviewer": "Reviewer_p8z3", "summary": "This manuscript investigates the phenomena of \\emph{Support Vector proliferation} (SVP) [1,2], in which all points in the training set $x_{i}\\in\\mathbb{R}^{d}$, $i=1,\\cdots, n$ become support vectors, i.e. satisfy $y_{i}\\hat{w}^{\\top}x_{i}=1$, where $\\hat{w}\\in\\mathbb{R}^{d}$ is the SVM estimator and $y_{i}\\in\\{-1,1\\}$ are the training labels. SVP implies that the SVM estimator coincides with interpolating least-norm linear regression, a fact which has been used in many recent works to study overparametrisation in generalised linear models. In particular, the authors focus in a data model defined by fixed labels $y_{i}$ and sub-Gaussian features $x_{i}$ with zero mean and diagonal covariance $\\lambda_{k}$, $k=1, \\cdots, d$ (i.e. the labels are independent of the features). The key results are:\n\n- Different equivalent characterisations of SVP for generic $\\ell_{p}$, $1< p< \\infty$ norm SVM (proposition 1). \n\n- Establishing a lower bound showing that one needs at least $d=n\\log{n}$ for SVP to occur in the anisotropic model defined above and $\\ell_{2}$-SVM  (Theorem 3). This result tightens the a previous bound from [2] (Theorem 1).\n\n- Establishing a sharp transition at $d = 2n\\log{n}$ for SVP in the particular case of isotropic Gaussian data $x_{i}\\sim\\mathcal{N}(0,I_{d})$, also for $\\ell_{2}$-SVM (Theorem 4).\n\nThe authors also provide numerical simulations corroborating the theorems, and suggesting that their results apply beyond the theorem's assumptions. Finally, they also provide a conjecture for the equivalent result in the $\\ell_1$-SVM case.\n\n\n[1] Vidya Muthukumar, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel Hsu, and Anant Sahai. *Classification vs regression in overparameterized regimes: Does the loss function matter?*, 2020.\n\n[2]: Daniel Hsu, Vidya Muthukumar, and Ji Xu. *On the proliferation of support vectors in high dimensions*.  In Twenty-Fourth International Conference on Artificial Intelligence and Statistics, 391 2021.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality:** This work is a follow-up of [2]. However, it employs alternative proof techniques to improve over their results, which also give a geometrical picture of SVP.\n\n**Quality:** I am not an expert in the proof techniques employed, and therefore I cannot confidently judge the details of the proof. However, the results are sound and the authors provide numerical evidence beyond the theorems scope. \n\n**Clarity**: The manuscript is well organised and the reading flow is smooth. The definitions and assumptions used are clearly stated, and the authors provide intuition where it fits, as well as the main ideas of the proof technique employed. I have two suggestions that I believe could further improve the readability for a non-specialist reader: \n\n- The authors make an extensive use of the $O, o, \\Omega, \\omega$ notation, without previously defining it. While this is standard, I believe that including a recap of the definition in the notation section could help the reader.\n- It would be good to explicitly state that different from Proposition 1, Theorem 3 \\& 4 are for the $\\ell_{2}$-SVM in the \"Outline of our results\" section.\n\n**Significance**: SVP is an interesting phenomena occurring in overparametrised problems and which has drawn significant attention recently. Therefore, elucidating when and how it occurs in simple statistical models is, in my opinion, of interest to the NeurIPS community. This works gives a step forward in this direction, sharpening previous findings and providing an alternative picture of the mechanism behind SVP.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors are clear about some of the limitations of their results. However, I missed a deeper discussion of two limitations:\n\n- SVP is defined in section 2 for $\\ell_{p}$-SVM, but Theorems 3 \\& 4 focus on the $p=2$ case. Section $6$ addresses the $p=1$ case, but I missed a discussion on the $p>2$ case. Are they qualitatively similar to $p=2$ or significantly different? What are the bottlenecks in the proofs for $p>2$? Did the authors explore these cases numerically (akin to Figs. 1 and 3)?\n- The work mostly focus on a data model where the labels are independent from the features. The authors dismiss this limitation in a one sentence comment (lines 200-201). However, at least \\emph{a priori}, the definition of SVP seems to crucially depends on the interplay between the labels and the features through the definition of the margins $y_{i}\\hat{w}^{\\top}x_{i}$. Have the authors explored this claim (numerically or analytically) in models in which the labels depend on the features, e.g. in a 2-Gaussian mixture? I believe this deserves an extended discussion.\n\nFinally, one question: do the results require $n$ to be large or are valid down to $n=O(1)$?", "review_text": "", "extra_scores": {"ethical_concerns": "There are no ethical issues. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4h"}, "extra_text": {}}, {"review_id": "o8ilbHH7zb4", "reviewer": "Reviewer_AB4x", "summary": "The paper considers the conditions under which the solution to the classic, hard-margin SVM classifier collapses to the solution of the ordinary linear regression problem.  This is known as support vector proliferation and occurs when all training vectors for the SVM are support vectors.  SVP has been observed previously, and an upper bound placed on the dimension (relative to training set size) required to induce it given.  The paper further elaborates on these results, providing improved lower bounds on the dimension for which it occurs.  The transition region in which SVP occurs is characterised and it's width bounded.  Finally, the authors speculate as to the conditions required for SVP in the $\\ell_1$ variant of the SVM, and show experimentally that SVP appears to require much higher dimension for this case.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The results in the paper are technically interesting, if not entirely surprising, and do have some interest in gaining a deeper understanding of the behaviour of the SVM in the limits where current results are not applicable (i.e. when the number of support vectors is large, contradicting the key assumptions of certain results regarding e.g. convergence analysis).  The experimental results that are given back-up the results, at least for small training set sizes.\n\nI do worry that the results are a little on the incremental side, and the hypothesis for the $\\ell_1$-SVM is underwhelming (at least to me), but nevertheless overall I would err on the side of acceptance.\n\nPOST-REBUTTAL: having read the response and the ensuing discussion I have chosen to leave my response unchanged and recommend accepting this paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "CjUl_akBox4", "reviewer": "Reviewer_FQDN", "summary": "This paper proves a super-linear lower bound on the dimension of support vector proliferation (SVP) when features are anisotropic subgaussians. The exact asymptotic threshold of the phase transition in the isotropic Gaussian distribution is also proved. Finally, this paper discussed the case of SVP phase transition for $\\ell_1$-SVMs. The experiments on synthetic data sets are also conducted.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "From my point of view, the coincidence between SVM and OLS is not the essential of the problem. If I understand correctly, the paper just wants to show that when dimension is appropriately high and the features are anisotropic subgaussians, the examples will lie on two parallel hyperplanes. Obviously, this is independent of what learning models are chosen.\n\nFrom the practical perspective, SVP only occurs on a quite idealized condition, thus cannot provide any insight for learning algorithms’ understanding and design. From the theoretical perspective, the techniques used in the proof are just subgaussian concentration bounds as well as some linear algebra. It seems difficult to judge the contributions of the paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors are suggested to elaborate more on in which scenarios the SVP theory can be applied?", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "48"}, "extra_text": {}}, {"review_id": "A47RplgeT_1", "reviewer": "Reviewer_Cct8", "summary": "This paper investigates the phenomenon of support vector proliferation (SVP), that is, when linear classification with minimum-$\\ell_p$-norm hard-margin SVM and minimum-$\\ell_p$-norm interpolation yield the same solution. A previous paper showed for $p=2$ that SVP occurs with high probability for certain distributions with (effective) input dimension $d = \\Omega(n \\log n)$, but not for $d = O(n)$. The authors close this gap by showing that SVP does not occur for $d = o(n \\log n)$. The authors further specify a more precise bound for standard Gaussian inputs and provide empirical evidence showing similar behavior for other distributions. Finally, the authors present some other theoretical and empirical results to illuminate the behavior for different $p$.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: The novel contributions of the paper are clearly stated. The proofs of the main theorems rely on a novel decomposition where, despite taking a maximum over non-independent terms, one part of the decomposition now consists of independent terms where the distribution of the maximum can be bounded more precisely. \n\nQuality: Claims in the paper are supported by proofs and numerical experiments. The theoretical results look reasonable, although I did not read all of the proofs and the parts that I did read were sometimes not very detailed and left a few questions open (see below). \n\nClarity: The submission is clearly written. However, I would suggest writing more about the implications of this work, i.e., how this work is relevant to ML (see below). \n\nSignificance: The authors provide a much tighter characterization of the occurence of SVP for a certain class of distributions than previous work. Although the considered problem is mathematically interesting, I only see limited significance due to several reasons:\n- The improvement is only by a factor $O(\\log n)$\n- It is unclear to me why a practitioner should care whether SVP occurs or not since it does not seem to have direct implications on generalization.\n- The analysis of over-parameterized regime is usually motivated by neural networks, which can behave like linear models sometimes, but usually are not trained using hinge loss. \n- Raw input data in ML rarely has dimension $\\Omega(n)$. The setting considered in this paper is therefore most interesting when applied to data that is generated using a feature map with high-dimensional feature space, or when considering a kernel method with potentially infinite-dimensional feature space. However, the assumption that the data is generated from distributions with independent components excludes realistic feature maps. I understand that treating such cases theoretically is very hard and likely not possible with a similar proof technique. However, I would suggest extending the experimental results with distributions arising from feature maps, which would also make the hypothesized universality of the $d = 2n\\log n$ boundary more convincing. While the formulated results only apply to finite-dimensional data, the formulation with effective dimensions appears to generalize to an infinite-dimensional limit, and although the independent components assumption is not satisfied for typical kernels, it would be interesting to study the effective dimension of a kernel's feature distribution depending on the kernel width or the input dimension, in order to see when SVP might arise in a kernel setting. This could be done by replacing the vector $\\lambda$ with the eigenvalues of the kernel's integral operator with respect to a given input dimension. In certain cases, these eigenvalues can be computed precisely, see e.g. Minh et al. for the Gaussian kernel on the sphere (https://link.springer.com/content/pdf/10.1007/11776420_14.pdf). In order to let the effective dimension grow with $n$, I guess either the kernel width should decrease at a certain rate with $n$ or the input dimension should increase with $n$. Asymptotics of the latter type have also been investigated e.g. by Liang et al. (https://arxiv.org/abs/1808.00387, https://arxiv.org/abs/1908.10292). \n\nPerhaps the significance of the paper could also be improved by establishing a link to the Double Descent literature, as the considered setting is exactly in the regime where the Double Descent literature would suggest bad generalization performance of the considered methods. A distinction between overfitting and interpolating classifiers is also made by Belkin et al. (http://proceedings.mlr.press/v80/belkin18a.html), maybe this could be of interest.\n\nConclusion: The paper contains a clear theoretical contribution to a rather specialized topic of research. Due to concerns about significance, I am currently opting for a weak reject. \n\nMajor comments:\n\nL. 545 f.: The matrix $A^\\top A$ is a $d \\times d$ matrix of rank $\\leq n$. In the regime $d > n$, it cannot be invertible. Maybe the shown argument works with pseudoinverses, but this is not immediately clear. Also, the last step in the proof where the authors go back from A to X and y is unclear - is this some sort of Schur complement / Woodbury identity? Maybe this part of the proof could be simplified if the solution of the dual problem can be expressed in terms of the (explicitly known) solution of the primal problem.\nSince the corresponding part of the proof is only an alternative proof to an already known statement, this problem does not question the validity of the rest of the paper.\n\nEq. after line 562: The first inequality appears to have a term of order n \\log(n/\\delta)^{1/3} and I don't see how this is covered by the third assumption in (3). Maybe it works by inserting the definition of m and using some bound between d_\\infty and d_2. In any case, I would recommend adding more details to these arguments, also regarding some of the inequalities after l. 570 (which seem to be correct, though).\n\nMinor comments: \n\nL. 103: \"primarily relevant for non-separable data\" -> why would that be? Even when using a high-dimensional feature space, regularization might be necessary to avoid overfitting (even if unregularized models are trendy).\n\nL. 137: . missing\n\nL. 138: \"matrix\" -> \"the matrix\", \"a matrix\" or \"\", similar in L. 136\n\nL. 151: \"with high probability as soon as $d = \\Omega(n)$\" -> In fact, this holds almost surely as soon as $d \\geq n$. Proof: The samples are almost surely linearly independent (this holds for all continuous distributions and also for some non-continuous ones, see e.g. Section 5 in https://arxiv.org/abs/2010.01851), hence the interpolation problem is almost surely solvable and hence they are linearly separable. (However, for general $\\lambda$-anisotropic subgaussian distributions as considered later in the paper, which are not necessarily continuous, these properties do not necessarily hold almost surely.)\n\nL. 195: How restrictive is it to assume that a random variable is 1-subgaussian with second moment = 1? While almost every subgaussian random variable can be rescaled to have second moment = 1, the rescaled version need not be 1-subgaussian.\n\nL. 207: probability is not exactly 1-\\delta, I assume? Also, does this mean that the constant in the \\Omega is arbitrary or is it \"given\" by the theorem?\n\nL. 208: meaning of formulation \"with constant probability\" is unclear\n\nL. 216 / L. 196: Since the $\\ell_2$-case is rotationally invariant, it seems that general covariance matrices could be used and not only diagonal ones. Maybe this could be remarked somewhere near Theorem 3.\n\nL. 260: You use both $\\log$ and $\\ln$ for the same thing (maybe also in other places). It would be better to consistently use one of the two.\n\nFig. 1: \"Radamacher\" -> \"Rademacher\". Maybe it would be advantageous to use log-log plots to show more clearly that the relative width of the phase transition gets smaller for larger $n$? (Although this effect is separately demonstrated in the appendix.) Maybe it would be helpful to extend the plots a bit to the left, such that the curvature from the $\\log(n)$ term is better visible.\n\nFig. 2: Repeat $d = \\tau n \\log n$ for the reader? L. 292 says $\\tau = d/(2n\\log n)$, which is different from $d = \\tau n \\log n$ used before. The usage of $\\tau$ should be made consistent. \n\nFig. 2: \"from the Gaussian samples\" -> \"using a Gaussian distribution\"?\n\nL. 291f.: Notation for model parameters is unintuitive, although it makes sense. Maybe it would be more intuitive to put n and \\calD as indices, otherwise \\mu looks like a function.\n\nL. 490f.: The principal minors are not the K_{\\i} matrices. Also, the invertibility of K ist not equivalent to the invertibility of all K_{\\i} as can be seen from the symmetric matrix K = [[1, 1], [1, 1]]. However, it is known here that K ist symmetric and positive semidefinite, and the assumption that K is invertible implies that K is positive definite, which in turn implies that all K_{\\i} are positive definite and hence invertible.\n\nL. 491: \"invertiability\" -> \"invertibility\"\n\nL. 492: \"inveritble\" -> \"invertible\"\n\nThe equation after L. 536 is wrong - $\\alpha^*$ belongs in a different place. However, the following steps already use the correct variant of the equation, so it is not a big problem.\n\nL. 544: \"problem\" can be removed\n\nL. 584 and following: Which matrix norm is used? You might want to add an index to the norm to indicate which norm it is - probably the 2-norm.\n\nEquation after l. 588: The last line should have parentheses after $\\exp$.\n\nL. 610: Would it be more appropriate to use $n-m$ instead of $n$ here?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations of the paper are addressed. Potential societal impact is not addressed since this is a theoretical paper. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper improves existing bounds for the support vector proliferation regime. 
While initially there were some concerns among the reviewers, the authors managed
to convince the more skeptical reviewers during the rebuttal phase. On the negative 
side, the paper deals, as its predecessors, with a rather restricted data model and direct
practical implications remain vague.
Decision: Accept (Poster)