summaries: 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. 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. 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$. 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. 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:  - Different equivalent characterisations of SVP for generic $\ell_{p}$, $1< p< \infty$ norm SVM (proposition 1).   - 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).  - 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).  The 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.   [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.  [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.
abstractText: 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 l1 variant of the SVM, and we present a new geometric characterization of the problem that may elucidate this phenomenon for the general lp case.
authors.name: Navid Ardeshir
authors.name: Daniel Hsu
references.authors: Dennis Amelunxen Peter Bürgisser
references.title: Intrinsic volumes of symmetric cones
references.venue: arXiv preprint arXiv:1205.1863,
references.authors: Dennis Amelunxen Martin Lotz Michael B McCoy Joel A Tropp
references.title: Living on the edge: Phase transitions in convex programs with random data
references.venue: Information and Inference: A Journal of the IMA,
references.authors: Peter L Bartlett Ambuj Tewari
references.title: Sparseness vs estimating conditional probabilities: Some asymptotic results
references.venue: Journal of Machine Learning Research,
references.authors: Peter L. Bartlett Philip M. Long Gábor Lugosi Alexander Tsigler
references.title: Benign overfitting in linear regression
references.venue: Proceedings of the National Academy of Sciences,
references.authors: Mikhail Belkin Daniel Hsu Ji Xu
references.title: Two models of double descent for weak features
references.venue: SIAM Journal on Mathematics of Data Science,
references.authors: Andrew C. Berry
references.title: The accuracy of the gaussian approximation to the sum of independent variates
references.venue: Transactions of the American Mathematical Society,
references.authors: Arnaud Buhot Mirta B Gordon
references.title: Robust learning and generalization with support vector machines
references.venue: Journal of Physics A: Mathematical and General,
references.authors: Emmanuel J Candès Pragya Sur
references.title: The phase transition for the existence of the maximum likelihood estimate in high-dimensional logistic regression
references.venue: The Annals of Statistics,
references.authors: Yuan Cao Quanquan Gu Mikhail Belkin
references.title: Risk bounds for over-parameterized maximum margin classification on sub-gaussian mixtures
references.venue: arXiv preprint arXiv:2104.13628,
references.authors: Niladri S Chatterji Philip M Long
references.title: Finite-sample analysis of interpolating linear classifiers in the overparameterized regime
references.venue: Journal of Machine Learning Research,
references.authors: Shaobing Chen David Donoho
references.title: Basis pursuit
references.venue: In Proceedings of 1994 28th Asilomar Conference on Signals, Systems and Computers,
references.authors: Thomas M Cover
references.title: Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition
references.venue: IEEE Transactions on Electronic Computers,
references.authors: Rainer Dietrich Manfred Opper Haim Sompolinsky
references.title: Statistical mechanics of support vector networks
references.venue: Physical Review Letters,
references.authors: David Donoho Jared Tanner
references.title: Counting faces of randomly projected polytopes when the projection radically lowers dimension
references.venue: Journal of the American Mathematical Society,
references.authors: David Donoho Jared Tanner
references.title: Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing
references.venue: Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences,
references.authors: AP Dvoretsky
references.title: Some results on convex bodies and banach spaces
references.venue: Matematika, 8(1):73–102
references.authors: Ronald Aylmer Fisher Leonard Henry Caleb Tippett
references.title: Limiting forms of the frequency distribution of the largest or smallest member of a sample
references.venue: In Mathematical proceedings of the Cambridge philosophical society,
references.authors: Pascal Germain Alexandre Lacoste François Laviolette Mario Marchand Sara Shanian
references.title: A PAC-Bayes sample-compression approach to kernel methods
references.venue: In ICML,
references.authors: Thore Graepel Ralf Herbrich John Shawe-Taylor
references.title: PAC-Bayesian compression bounds on the prediction error of learning algorithms for classification
references.venue: Machine Learning,
references.authors: Trevor Hastie Andrea Montanari Saharon Rosset Ryan J Tibshirani
references.title: Surprises in highdimensional ridgeless least squares interpolation
references.venue: arXiv preprint arXiv:1903.08560,
references.authors: Trevor J Hastie Daryl Pregibon
references.title: Generalized linear models. In Statistical models in S, pages 195–247
references.authors: Daniel Hsu Vidya Muthukumar Ji Xu
references.title: On the proliferation of support vectors in high dimensions
references.venue: In Twenty-Fourth International Conference on Artificial Intelligence and Statistics,
references.authors: Ningyuan Huang David W Hogg Soledad Villar
references.title: Dimensionality reduction, regularization, and generalization in overparameterized regressions
references.venue: arXiv preprint arXiv:2011.11477,
references.authors: Ziwei Ji Matus Telgarsky
references.title: The implicit bias of gradient descent on nonseparable data
references.venue: In Conference on Learning Theory,
references.authors: Michel Ledoux
references.title: The concentration of measure phenomenon
references.venue: Number 89. American Mathematical Soc.,
references.authors: Tengyuan Liang Pragya Sur
references.title: A precise high-dimensional asymptotic theory for boosting and minimum-l1-norm interpolated classifiers
references.venue: arXiv preprint arXiv:2002.01586,
references.authors: Haoyang Liu
references.title: Exact high-dimensional asymptotics for support vector machine
references.venue: arXiv preprint arXiv:1905.05125,
references.authors: Yasaman Mahdaviyeh Zacharie Naulet
references.title: Risk of the least squares minimum norm estimator under the spike covariance model
references.authors: Dörthe Malzahn Manfred Opper
references.title: A statistical physics approach for the analysis of machine learning algorithms on real data
references.venue: Journal of Statistical Mechanics: Theory and Experiment,
references.authors: Jiri Matousek
references.title: Lectures on discrete geometry, volume 212
references.venue: Springer Science & Business Media,
references.authors: Song Mei Andrea Montanari
references.title: The generalization error of random features regression: Precise asymptotics and double descent curve
references.authors: Partha P Mitra
references.title: Understanding overfitting peaks in generalization error: Analytical risk curves for l2 and l1 penalized interpolation
references.authors: Vidya Muthukumar Kailas Vodrahalli Vignesh Subramanian Anant Sahai
references.title: Harmless interpolation of noisy data in regression
references.venue: IEEE Journal on Selected Areas in Information Theory,
references.authors: Vidya Muthukumar Adhyyan Narang Vignesh Subramanian Mikhail Belkin Daniel Hsu Anant Sahai
references.title: Classification vs regression in overparameterized regimes: Does the loss function matter
references.venue: Journal of Machine Learning Research,
references.authors: Andrew Y Ng
references.title: Feature selection, l 1 vs. l 2 regularization, and rotational invariance
references.venue: In Proceedings of the twenty-first international conference on Machine learning,
references.authors: Bernhard Schölkopf Alex J Smola Robert C Williamson Peter L Bartlett
references.title: New support vector algorithms
references.venue: Neural computation,
references.authors: Daniel Soudry Elad Hoffer Mor Shpigel Nacson Suriya Gunasekar Nathan Srebro
references.title: The implicit bias of gradient descent on separable data
references.venue: J. Mach. Learn. Res.,
references.authors: Ingo Steinwart
references.title: Sparseness of support vector machines
references.venue: Journal of Machine Learning Research,
references.authors: Ryan Theisen Jason Klusowski Michael Mahoney
references.title: Good classifiers are abundant in the interpolating regime
references.venue: In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics,
references.authors: Robert Tibshirani
references.title: Regression shrinkage and selection via the lasso
references.venue: Journal of the Royal Statistical Society: Series B (Methodological),
references.authors: Lieven Vandenberghe
references.title: The cvxopt linear and quadratic cone program solvers, 2010. URL https://www.seas.ucla.edu/~vandenbe/publications/coneprog.pdf
references.authors: Vladimir Naumovich Vapnik
references.title: Estimation of dependences based on empirical data
references.authors: Roman Vershynin
references.title: Estimation in high dimensions: a geometric perspective
references.venue: In Sampling theory, a renaissance,
references.authors: Ke Wang Christos Thrampoulidis
references.title: Binary classification of gaussian mixtures: Abundance of support vectors, benign overfitting and regularization
references.venue: arXiv preprint arXiv:2011.09148v4,
references.authors: Weichen Wang Jianqing Fan
references.title: Asymptotics of empirical eigenstructure for high dimensional spiked covariance
references.venue: Annals of Statistics,
references.authors: Ji Xu Daniel Hsu
references.title: On the number of variables to use in principal component regression
references.venue: In Advances in Neural Information Processing Systems
sections.heading: 1 Introduction
sections.text: 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.
  The hard-margin SVM is a linear classification model that finds the separating hyperplane that maximizes the minimum margin of error for every training sample. If the training data (x1, y1), . . . , (xn, yn) ∈ Rd × {±1} are linearly separable, then the resulting linear classifier is x 7→ sign (xTwSVM), where wSVM is the solution to the following optimization problem:
  wSVM = argmin w∈Rd ∥w∥2 such that yiw Txi ≥ 1, ∀i ∈ [n]. (1)
  An example xi is a support vector if the corresponding constraint is satisfied with equality, and the optimal solution wSVM is a linear combination of these support vectors.
  Ordinary least squares regression finds the linear function that best fits the training data (x1, y1), . . . , (xn, yn) ∈ Rd × R according to the sum of squared errors. When the solution is not unique, it is natural to take the solution of minimum Euclidean norm; this is the convention we adopt. Taking X := [x1| . . . |xn]T ∈ Rn×d and y := (y1, . . . , yn), the solution is the hypothesis x 7→ wTOLSx where wOLS is the solution to the following: wOLS = argminw∈Rd ∥w∥2 such that XTXw = XTy. In many high-dimensional settings (e.g., where X has full row rank), the solution may in fact interpolate the training data, i.e.,
  wOLS = argmin w∈Rd ∥w∥2 such that w Txi = yi, ∀i ∈ [n]. (2)
  35th Conference on Neural Information Processing Systems (NeurIPS 2021).
  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. [35] and Hsu et al. [23]. Roughly speaking, they show that SVP occurs when d = Ω(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., 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.2), and the connection between the two approaches via SVP has played an important analytical role [9, 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 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. [23] by showing that d ≳ 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 xi, and they match the upper-bounds from [23]. This demonstrates that SVP is extremely unlikely to occur in the much-studied d = Θ(n) setting.
  2. Is there a sharp threshold separating the occurrence and non-occurrence of this phenomenon? Is this threshold universal across all “reasonable” distributions over each xi?
  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 ℓ2 SVM problem? If (1) and (2) are generalized to instead minimize ℓp 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 ℓp norms. We conjecture that a similar phase transition occurs for ℓ1, but also that it requires much larger dimension d; this is supported by preliminary experiments.
sections.heading: 1.1 Outline of our results
sections.text: Section 2 introduces the SVM and OLS approaches in full generality, our λ-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 [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 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 [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 6 asks the questions about SVP from the preceding sections in the context of ℓ1-SVM and minimum ℓ1-norm interpolation. Specifically, the SVP threshold for ℓ1 is conjectured to occur for d = ω(n log n). Evidence for this conjecture is provided in a simulation study and in geometric arguments about random linear programs.
sections.heading: 1.2 Related work
sections.text: Prior works connecting SVP and generalization. Muthukumar et al. [35] 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 [10], 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 [10] requires polynomially-higher dimension than is typically studied: d = Ω(n2 log n).) The coincidence between SVM and OLS identified by Muthukumar et al. was also more recently used by Wang and Thrampoulidis [46] and Cao et al. [9] 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 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. [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 = Ω(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 [3, 39], including the soft-margin SVM [12] and the ν-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-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 [25, 38].
  Phase transitions have been studied in the context of linear classification [8, 13, 27, 40], and SVMs in particular [7, 14, 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 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., 4, 5, 21, 24, 29, 32–35, 47, 48]. Many of these analyses are carried out in the d = Θ(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. [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.
  High-dimensional geometry and universality. Our conjecture about support vector proliferation for ℓ1-SVMs derives inspiration from studies of high-dimensional geometric phase transitions, particularly those by [1, 2, 15]. These results consider the geometry of random polytopes. Amelunxen and Bürgisser [1] 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 ℓ1-norm minimizing solutions to sparse recovery problems are exactly correct, and Donoho and Tanner [15] bound the number of faces of random polytopes. We also borrow heavily from [16] when designing our experiments in Section 5 to test the universality hypothesis.
sections.heading: 2 Preliminaries
sections.text: 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.
sections.heading: 2.1 Notation
sections.text: For λ ∈ Rd+, we define the ℓ2 and ℓ∞ dimension proxies as d2 := ∥λ∥21/∥λ∥22 and d∞ := ∥λ∥1/∥λ∥∞ Let [n] := {1, . . . , n}. For some vector w ∈ Rn and matrix A ∈ Rn×d, we let wi and Ai denote the ith element of w and row of A respectively; likewise, we let A·,j ∈ Rn represent the jth column of A. We abuse notation to let w\i = (w1, . . . , wi−1, wi+1, . . . , wn) ∈ Rn−1, w[m] = (w1, . . . , wm) ∈ Rm, w\[m] = (wm+1, . . . , wn) ∈ Rn−m, and w[m]\i = (w[m])\i ∈ Rm−1 for i ∈ [m] and m ∈ [n]. Analogous notation holds for A\i, A[m], A\[m], and A[m]\i. We frequently consider the Gram matrix K := XXT ∈ Rn×n for feature matrix X ∈ Rn×d; for these matrices, we let K\i = X\iXT\i ∈ R
  (n−1)×(n−1) and analogously define K[m], K\[m], and K[m]\i. Let µmax(A) and µmin(A) represent the largest and smallest eigenvalues of the matrix A respectively, and let ∥A∥ be the operator norm of A. For some vector y ∈ Rn, we let diag(y) ∈ Rn×n be a diagonal matrix with (diag(y))i,i = yi. Throughout, boldface characters refer to random variables.
sections.heading: 2.2 Optimization problems
sections.text: 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, y1), . . . , (xn, yn) ∈ Rd×{±1} in a high-dimensional regime where d ≫ n with design matrix X := [x1| . . . |xn]T ∈ Rn×d and Gram matrix K = XXT ∈ Rn×n. In full generality, the separating hyperplane corresponding to the ℓp-SVM problem for some p ≥ 1 is the solution to the following optimization problem:
  min w∈Rd ∥w∥p such that yiw Txi ≥ 1, ∀i ∈ [n]. (SVM Primal)
  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.1 An example (xi, yi) is called a support vector if it lies exactly on the margin defined by separator w, or equivalently if yiwTxi = 1. It is well-known that w can be represented as a non-negative linear combination of all yixi where xi is a support vector [43].
  We contrast the weights of the classifier returned by SVM Primal with the weights of minimum ℓp-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 w∈Rd ∥w∥p such that yiw Txi = 1, ∀i ∈ [n]. (Interpolation Primal)
  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 xi are linearly independent.
sections.heading: 2.3 Equivalent formulations of SVP
sections.text: We study the phenomenon of support vector proliferation (SVP), i.e., the occurrence in which every example xi is a support vector. Because xi is a support vector if yiwTxi = 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.
  1When d ≥ 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 = diag(y)X ∈ Rn×d, the dual of the optimization problem (Interpolation Primal) is:
  max α∈Rn n∑ i=1 αi such that ∥ATα∥q ≤ 1. (Interpolation Dual)
  The dual of (SVM Primal) is (Interpolation Dual) with an additional constraint that α ∈ Rn+. Let T = { ∑n i=1 aiAi : ∑n
  i=1 ai = 1} denote the affine plane passing through the rows of A, and let T+ = { ∑n i=1 aiAi : ∑n i=1 ai = 1, ai ≥ 0} be the convex hull of the rows of A. In addition, for
  i ∈ [n], let T\i = { ∑ i′ ̸=i ai′Ai′ : ∑
  i′ ̸=i ai′ = 1}. We denote ΠT(0) as the ℓq-norm projection of the origin onto T, which is uniquely defined for 1 < q < ∞. Proposition 1. Let 1 < p < ∞ and q = (1− 1/p)−1, and consider any (X, y) ∈ Rn×d × {±1}n. Suppose K is invertible. Then, the following are equivalent:
  (1) SVP occurs for ℓp-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 Rd+. (4) ΠT(0) ∈ T+.
  Moreover, if p = 2, then properties (1)–(4) are also equivalent to the following:
  (5) For all i ∈ [n], yiyT\iK −1 \i X\ixi = yiΠT\i(0) Txi/∥ΠT\i(0)∥22 < 1.
  This dual framework in (3) and (4) gives an alternative geometric structure to consider for this problem. For the ℓ2-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 ℓ1 case is not technically covered by Proposition 1 (due to the non-strict convexity of ℓ1 norm), our analysis still gives useful insights, and we explore this case specifically in Section 6.
  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.
sections.heading: 2.4 Data model
sections.text: We use the data model of Hsu et al. [23], where every labeled sample (xi, yi) has xi drawn from an anisotropic subgaussian distribution with independent components and arbitrary fixed labels yi. Definition. For some λ ∈ Rd≥0, we say (X, y) ∈ Rn×d × {±1}n (as well as (X,Z, y) ∈ Rn×d × Rn×d × {±1}n) is a λ-anisotropic subgaussian sample if: y = (y1, . . . , yn) ∈ {±1}n are fixed (non-random) labels; Z := [z1| . . . |zn]T ∈ Rn×d is a matrix of independent 1-subgaussian random variables with E[zi,j ] = 0 and E[z2i,j ] = 1; and X := [x1| . . . |xn]T = Z diag(λ)1/2 ∈ Rn×d. We say (X, y) is an isotropic subgaussian sample if it is λ-anisotropic for λ = (1, . . . , 1). Finally, we say (X, y) is an isotropic Gaussian sample if it is isotropic subgaussian and each xi ∼ N (0, Id).
  We only consider fixed labels y that do not depend on X. However, we do not consider this to be a major limitation of this work. As discussed before, Cover [13] shows that linear separability is overwhelmingly likely in the high-dimensional regimes we consider. Moreover, our results can be extended to a setting where yi = sign (vTxi) for some fixed weight vector v.
sections.heading: 2.5 Previous results
sections.text: We tighten and generalize the characterization of the SVP threshold by Hsu et al. [23]. We give versions of their results that are directly comparable to our results in Sections 3 and 4. Theorem 1 (Theorem 1 of [23]). Consider a λ-anisotropic subgaussian sample (X, y) and any δ ∈ (0, 1). If d∞ = Ω(n log(n) log( 1δ )), then SVP occurs for ℓ2-SVM with probability at least 1− δ. Theorem 2 (Theorem 3 of [23]). Consider an isotropic Gaussian sample (X, y). For some constant δ ∈ (0, 1), if d = O(n), then SVP occurs for ℓ2-SVM with probability at most δ.
  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.
sections.heading: 3 SVP threshold for anisotropic subgaussian samples
sections.text: We closely characterize when support vector proliferation does and does not occur through the following theorem, which serves as a converse to Theorem 1. Theorem 3 (Lower-bound on SVP threshold for anisotropic subgaussians). Consider a λ-anisotropic subgaussian sample (X, y) and any δ ∈ (0, 12 ). For absolute constants C1, C2, C3, C4, assume that λ and n satisfy
  n ≥ C1 ( log 1
  δ
  )2 , d2 ≤ C2n log n, d∞ ≥ C3n log 1
  δ , and d2∞ ≥ C4d2n. (3)
  Then, SVP occurs for ℓ2-SVM with probability at most δ. Remark 1. If each xi is drawn from a Gaussian distribution, then we could instead permit xi to have any positive semi-definite covariance matrix Σ ∈ Rd×d with eigenvalues λ1, . . . , λd due to rotational invariance. Remark 2. In addition, the result can be generalized to subgaussian xi with general variance proxies γ ≥ 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 1 (from [23]) together establish that the threshold for SVP occurs at d = Θ(n log n). Theorem 3 sharpens and generalizes the partial converse of [23] given in Theorem 2.
  Theorem 3 does not depend explicitly on the ambient dimension d; instead, it only involves the effective dimension proxies d2 and d∞, 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− δ, K is invertible and
  max i∈[n]
  yiy T \iK −1 \i X\ixi ≥ 1, (4)
  where K\i := X\iXT\i. 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 y1yT\1K −1 \1 X\1x1 ≥ 1. This forces their bound to hold only when d = O(n). We obtain a 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 (4) with the following decomposition:
  max i∈[m]
  [ yiy T
  \i ( K−1\i − 1
  ∥λ∥1 In−1
  ) X\ixi + 1
  ∥λ∥1 yiy
  T [m]\iX[m]\ixi + 1
  ∥λ∥1 yiy
  T \[m]X\[m]xi
  ] .
  We prove that this decomposition (and hence, also (4)) is at least 1 with probability 1− δ by lowerbounding the three terms with Lemmas 1, 3, and 4 (given in Appendix B). We bound the first two terms for all i ∈ [m] by employing standard concentration bounds for subgaussian and subexponential random variables and by tightly controlling the spectrum of K\i. To bound the third term, we relate the quantity for each i ∈ [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 1δ . The third ensures that the variance of each yiy T \iK −1 \i X\ixi term is sufficiently small. The fourth assumption rules out λ-anisotropic subgaussian distributions with ∥λ∥22 ≪ ∥λ∥2∞n, where a single component of each xi is disproportionately large relative to others and causes unfavorable anti-concentration properties.
sections.heading: 4 Exact asymptotic threshold for Gaussian samples
sections.text: Section 3 shows the existence of a change in model behavior when d = Θ(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τn 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 (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 τ → 1 is slow enough, then the asymptotic probabilities 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 (ϵn)n≥1 be any sequence of positive real numbers such that lim supn→∞ ϵn < 2− c1 for some c1 > 0 and lim infn→∞ ϵn √ log n > C2 for some C2 > 0 depending only on c1. Then,
  lim n→∞ P[SVP occurs for ℓ2-SVM] = { 0 if d = (2− ϵn)nlog n, 1 if d = (2 + ϵn)nlog n.
  Remark 3. Theorem 4 characterizes the width of the phase transition: the difference wn between the values of d where the probability of SVP is (say) 0.9 and 0.1 satisfies wn = 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 ϵ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− ϵn)nlog 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 + ϵn)nlog n, we follow the basic argument in the proof of Theorem 1 from [23], but we sharpen the analysis by taking advantage of Gaussianity to find the limiting probability as n → ∞.
sections.heading: 5 Experimental validation of SVP phase transition and universality
sections.text: 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 → ∞. Our simulation procedure is as follows. We generate data sets (X, y) ∈ Rn×d × {±1}n, where y ∈ {±1}n is a fixed vector of labels with exactly n/2 positive labels, and x1, . . . ,xn ∼i.i.d. D⊗d where D is one of six sample distributions on R. For each data set, we check for SVP by solving the problem in (Interpolation Primal), and checking if its solution additionally satisfies the constraints from (SVM Primal). Let p̂ := p̂(n, d;D,M) denote the observed frequency of SVP in M = 400 independent trials when X ∈ Rn×d is generated using D. (Full details are given in Appendix D.1.) Figure 1 shows a heat map of p̂(n, d;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.
  We also investigate the universality of SVP using statistical methodology inspired by Donoho and Tanner [16]. Specifically, we model p̂ using Probit regression to test our universality hypothesis: that the occurrence of SVP for ℓ2-SVM on data with independent features matches the behavior under Gaussian features as n and d grow large. Our model is M · p̂ ∼ Binom(p(n, d;D),M), where
  p(n, d;D) = Φ ( µ(0)(n,D) + µ(1)(n,D)× τ + µ(2)(n,D)× log τ ) with µ(i)(n,D) = µ(i)0 (D) + µ (i) 1 (D)√
  n .
  Here, Φ(t) is the standard normal distribution function, τ = d/(2n log n), and the model parameters are µ(i)0 (D) and µ (i) 1 (D) for i ∈ {0, 1, 2} and the six different distributions D (shown in Table 1 in Appendix D.1). Figure 2 visualizes the fitted Probit function p for fixed n and τ and demonstrates that the model provides a very accurate approximation of p̂.
  The universality hypothesis corresponds to the model in which the parameters µ(i)0 (D) are “tied together” (i.e., forced to be the same) for all distributions D. That is, only the parameters scaled down by a factor of √ n, µ(i)1 (D), are allowed to vary with D. The scaling ensures that their effect tends to zero as n → ∞. The alternative (non-universality) hypothesis corresponds to the model in which all parameters (both µ(i)0 (n,D) and µ (i) 1 (n,D) for each i) are allowed to vary with D. We compare the models’ goodness-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 are “tied together” for all 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 √ log n for data models other than Gaussian ensembles.
sections.heading: 6 SVP phase transition for ℓ1-SVMs?
sections.text: Because both the SVM and linear regression problems can be formulated for general ℓp-norms, we can ask similar questions about when their solutions coincide. Here, we examine the ℓ1 case: the coincidence of SVM with an ℓ1-penalty and ℓ1-norm minimizing interpolation (also called Basis Pursuit [11]). Linear models with ℓ1 regularization are often motivated by the desire for sparse weight vectors [e.g., 11, 34, 36, 41].
  Based on experimental evidence and the differences in high-dimensional geometry between ℓ∞ and ℓ2 balls, we conjecture that SVP for ℓ1-SVMs only occurs in a much higher-dimensional regime.
  Conjecture 1. Let (X, y) ∈ Rn×d × Rn be an isotropic Gaussian sample. Then, the probability of SVP occurring for an ℓ1-SVM with X and y undergoes a phase transition around d = f(n), for some
  f(n) = ω(n log n). Formally, there exist positive constants c and c′ with c ≤ c′ such that
  lim n→∞ P [SVP occurs for ℓ1-SVM] = { 0 if d < cf(n), 1 if d > c′f(n).
  Conjecture 1 is consistent with our preliminary experimental findings, summarized in Figure 3. It shows larger values of d relative to n are needed to ensure SVP for ℓ1-SVMs and that the transition appears to 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(Ω(n)). Further experimental details are given in Appendix E.1.
  Answering whether support vector proliferation occurs in the ℓ1 case is equivalent to determining whether the optimal solution α∗ to (Interpolation Dual) problem lies in the positive orthant Rn+.2 In the ℓ1 case, we have q = ∞, so solving the problem amounts to characterizing the solutions to the
  2While Proposition 1 does not imply this equivalence for ℓ1-SVMs for arbitrary data, the results of the proposition are valid for isotropic Gaussian samples, because the corresponding ℓ∞ projection ΠT(0) in those cases is well-defined almost surely.
  following linear program for data matrix A = diag(y)X ∈ Rn×d:
  max α∈Rn n∑ i=1 αi s.t. − 1 ≤ ATα ≤ 1. (Dual L1)
  There is a line of work that gives high probability guarantees about whether related random linear programs are feasible and where their solutions reside [1, 2]. Similar analyses of random linear programs may be useful for understanding how large d must be to have α∗ ∈ Rn+, and we carry out a preliminary characterization in Appendix E.
  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.
title: Support vector machines and linear regression coincide with very high-dimensional features