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

Navid Ardeshir, Clayton Sanford, Daniel J. Hsu

In classical machine learning, the hard-margin Support Vector Machine (SVM) and minimum-norm Ordinary Least Squares (OLS) regression are traditionally distinct algorithms used for different tasks: classification and regression, respectively. However, in the modern "overparameterized" regime—where the number of features ($d$) greatly exceeds the number of samples ($n$)—the boundaries between these methods begin to blur.

In extremely high-dimensional settings, these two algorithms can actually produce the exact same model. This paper characterizes this phenomenon, known as "Support Vector Proliferation" (SVP), proving that a sharp phase transition occurs at a specific dimensionality threshold where every single data point becomes a support vector.

The Phenomenon of Support Vector Proliferation

Support Vector Proliferation occurs when every training example used to fit an SVM becomes a "support vector," meaning every point lies exactly on the decision margin. When this happens, the SVM solution becomes mathematically identical to the minimum-norm OLS solution.

While previous research noted this could happen when $d$ is roughly proportional to $n \log n$, there was no precise "tipping point" identified, nor was it clear if this was a quirk of Gaussian data or a universal rule. The authors set out to find the exact threshold and determine how broadly it applies, successfully closing the "$\log n$" gap in previous lower bounds to prove that $d \gtrsim n \log n$ is strictly necessary.

Methodology

The authors employ a mix of rigorous mathematical proof and statistical simulation to investigate SVP:

  • Geometric Dual Framework: They analyze the dual optimization problems of both SVM and OLS. By looking at the problem through a geometric lens—specifically the $\ell_q$-norm projection of the origin onto an affine plane—they established equivalent conditions for SVP.
  • Probabilistic Analysis: For the theoretical proofs, they used a $\lambda$-anisotropic subgaussian data model, utilizing the Berry-Esseen Theorem and concentration inequalities to control the behavior of the Gram matrix.
  • Universality Testing: To see if their Gaussian findings held for other distributions, they used Probit regression methodology to statistically test if the phase transition boundary shifted across different types of random variables.

The theoretical proofs primarily rely on synthetic datasets of Isotropic and Anisotropic Gaussians. To evaluate the "Universality Hypothesis"—the idea that the specific distribution doesn't matter as much as the dimensionality—they also tested five non-Gaussian distributions: Bernoulli, Rademacher, Uniform, Laplacian, and Biased Gaussian.

Key Findings

The study yields several critical insights into the behavior of linear models in high dimensions.

The $2n \log n$ Threshold: For isotropic Gaussian features, the transition is not just a vague range; it is a sharp line. The authors formally prove that the probability of SVP jumps from 0 to 1 as $d$ crosses the $2n \log n$ threshold. Furthermore, they characterized the "width" of this transition, showing it sharpens as $n$ increases, specifically behaving like $O(n \sqrt{\log n})$.

Universality Across Distributions: The most striking finding is that this $2n \log n$ boundary appears to be universal. Whether the data is binary (Bernoulli) or heavy-tailed (Laplacian), the merger of SVM and OLS happens at the same relative dimensionality.

Empirical probability of support vector proliferation across six different data distributions. The red line indicates the theoretical $2n \log n$ threshold.

$\ell_1$ vs. $\ell_2$ Geometry: The authors highlight that this proliferation is specific to the geometry of the $\ell_2$ norm. When they tested $\ell_1$-SVMs (which encourage sparsity), the proliferation happened much later, requiring a significantly higher dimension ($d$) relative to $n$.

Limitations and Future Work

While the empirical evidence for universality is strong, the authors only rigorously proved the sharp $2n \log n$ threshold for the isotropic Gaussian case. Formal proofs for other distributions remain an open challenge.

Additionally, the paper conjectures that for $\ell_1$-SVMs, the threshold for proliferation is much higher (possibly exponential in $n$), but they provide only simulation evidence and geometric intuition rather than a formal proof. Finally, the study focuses on the hard-margin SVM; how proliferation manifests in soft-margin SVMs used in real-world "noisy" scenarios is a subject for future study.

Summary updated

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.
BibTeX
@inproceedings{ardeshir2021support,
  author = {Navid Ardeshir and Clayton Sanford and Daniel J. Hsu},
  title = {{Support vector machines and linear regression coincide with very high-dimensional features}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=8AwM7F2GzQ},
}

Loading related content...

Figure