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

Navid Ardeshir, Clayton Sanford, Daniel Hsu

TL;DR

This paper investigates when Support Vector Machines (SVMs) and linear regression models produce identical solutions, a phenomenon called Support Vector Proliferation (SVP). They establish a sharp threshold for this coincidence in high-dimensional settings, showing it occurs when the number of features is roughly twice the number of samples times the logarithm of the number of samples. This finding is crucial for understanding the behavior of these fundamental machine learning models in regimes where they are often used but poorly understood.

What Problem Does This Paper Address?

Support Vector Machines (SVMs) and ordinary least squares (OLS) linear regression are workhorses in machine learning, but they are typically applied to different tasks: classification and regression, respectively. However, in very high-dimensional settings (where the number of features d is much larger than the number of samples n), it's been observed that these two fundamentally different approaches can yield the exact same linear model. This phenomenon, termed Support Vector Proliferation (SVP), occurs when every training data point becomes a "support vector" in the SVM formulation.

While prior work hinted at this coincidence happening when d is on the order of n log n, it was unclear how general this was, whether there was a sharp "phase transition" in the data dimension where SVP suddenly starts or stops occurring, and if this phenomenon was specific to the standard l2-norm used in SVMs and OLS. This paper aims to precisely characterize the conditions under which SVP occurs, identify the exact threshold, and explore its universality across different data distributions and even for l1-norm variants of these models. Understanding this connection is vital for theoretical analysis and practical application of these models in high-dimensional data.

Methods

The paper leverages a combination of theoretical analysis and empirical validation.

  • Optimization Problem Equivalence: The core of the theoretical work involves translating the SVM and OLS optimization problems into their dual forms. The authors show that SVP occurs if and only if the optimal solution to the dual SVM problem lies within the positive orthant. This geometric formulation is key to their analysis.
  • Concentration of Measure and Random Matrix Theory: To analyze the conditions under which this geometric property holds, the authors employ tools from concentration of measure (like the Berry-Esseen theorem) and random matrix theory. They carefully analyze the eigenvalues of the Gram matrix (XX^T) and its inverse, which are central to the SVM and OLS solutions.
  • Phase Transition Analysis: For Gaussian data, they derive an exact threshold for SVP, showing it occurs when d is approximately 2n log n. They also bound the width of this transition, indicating how sharply the probability of SVP changes around this threshold.
  • Universality Testing: To test if this phenomenon is specific to Gaussian data, they use statistical modeling (Probit regression) to analyze experimental results across various data distributions. This allows them to statistically assess whether the SVP threshold is universal.
  • Geometric Interpretation for l1-SVM: For the l1-norm variant, they use geometric interpretations of random polytopes and linear programs to gain insights into the conditions for SVP.

Datasets

The paper does not introduce new datasets. Instead, it uses synthetic data generated according to specific statistical models:

  • Anisotropic Subgaussian Samples: Data where features are drawn from subgaussian distributions with independent components.
  • Isotropic Gaussian Samples: A special case of subgaussian samples where features are drawn from a standard multivariate Gaussian distribution.
  • Various Distributions for Universality Testing: For experimental validation, they generate data from six different distributions: Uniform, Bernoulli, Rademacher, Laplacian, Gaussian, and Gaussian Biased.

Key Insights and Ideas

  • Sharp Phase Transition: The most striking insight is the existence of a sharp phase transition for SVP. The probability of SVP jumps from near 0 to near 1 as the ratio of features to samples (d / (n log n)) crosses a specific threshold (approximately 2). This is a fundamental property of high-dimensional statistics.
  • Universality of the Threshold: The experimental results strongly suggest that this sharp phase transition at d ≈ 2n log n is not limited to Gaussian data but holds across a wide range of distributions, indicating a fundamental geometric property of high-dimensional spaces.
  • l1-SVMs Require Much Higher Dimensions: The paper conjectures and provides evidence that for l1-norm variants of SVM and regression, SVP requires significantly higher dimensions than for l2-norms, potentially scaling much faster than n log n.
  • Geometric Underpinnings: The connection between SVP and the geometry of random polytopes and convex sets provides a powerful framework for understanding these phenomena, suggesting that geometric properties of high-dimensional spaces dictate the behavior of these learning algorithms.

Key Results

  • Exact Threshold for Gaussian Data: For isotropic Gaussian samples, SVP occurs if d > (2 + εn)n log n and does not occur if d < (2 - εn)n log n, where εn is a sequence that goes to zero slowly. The transition width is bounded by O(n√log n).
  • Lower Bound for Subgaussians: For anisotropic subgaussian features, SVP does not occur if d is too small, specifically d = O(n log n). This complements the upper bound and establishes O(n log n) as the critical dimension.
  • Experimental Universality: Experiments across six different distributions show that the SVP phase transition occurs at the same d ≈ 2n log n threshold and exhibits similar sharpness, supporting the universality hypothesis.
  • l1-SVMs: Empirical evidence suggests that SVP for l1-SVMs requires substantially larger dimensions than for l2-SVMs, with the transition being less sharp.

Limitations and Future Work

  • Fixed Labels: The theoretical analysis for dependent labels (Theorem 5) is presented for a simplified case (y_i = sign(v^T x_i)). Generalizing this to arbitrary dependent labels is a potential future direction.
  • l1-SVM Dimension Bound: The theoretical lower bound for l1-SVP is loose. The authors believe a better understanding of the geometry of random polytopes could tighten this bound and provide a more precise characterization.
  • Transition Width Sharpness: While the transition width is bounded, it's an open problem whether this bound is sharp for all distributions.
  • l1-SVM Transition Rate: The exact rate of the phase transition for l1-SVMs remains an open question, with experiments suggesting it might be significantly higher than n log n.

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 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