On the Equivalence of SVM and MNI in Overparametrized RegimeIn traditional ML, the hard-margin support vector machine (SVM) and the minimum-norm interpolator (MNI) are usually introduced as two very different objects: the former is the canonical maximum-margin classifier, while the latter is the least-squares solution that a regression analysis would produce. A remarkable phenomenon in high-dimensional statistics is that, once the model is sufficiently overparametrized, these two solutions become exactly identical. This post explains why this happens, when it happens, and why it is useful. Setup: Two Interpolating SolutionsConsider a binary classification task with a dataset \(\{(\mathbf{x}_i, y_i)\}_{i=1}^n\) with \(\mathbf{x}_i \in \mathbb{R}^d\) and \(y_i \in \{\pm 1\}\), in the overparametrized (i.e., underdetermined) regime \(d > n\) where the data matrix \(\mathbf{X} \in \mathbb{R}^{n \times d}\) has full row rank. We compare two estimators. The hard-margin SVM can be written as \[ \hat{\mathbf{w}}_{\text{SVM}} = \arg\min_{\mathbf{w}} \|\mathbf{w}\|_2^2 \quad \text{s.t.} \quad y_i \, \mathbf{w}^\top \mathbf{x}_i \geq 1 \;\; \forall i, \] while the minimum-norm interpolator (equivalently, the minimum-\(\ell_2\)-norm solution of least squares on the labels) can be written as \[ \hat{\mathbf{w}}_{\text{MNI}} = \arg\min_{\mathbf{w}} \|\mathbf{w}\|_2^2 \quad \text{s.t.} \quad \mathbf{w}^\top \mathbf{x}_i = y_i \;\; \forall i, \] which admits the closed form \(\hat{\mathbf{w}}_{\text{MNI}} = \mathbf{X}^\top (\mathbf{X}\mathbf{X}^\top)^{-1} \mathbf{y}\). Here, it is worth remarking that SVMs appear quite often in deep learning theory and the implicit bias literature: For example, when the model is a linear predictor (e.g., linear or deep linear nets) and the loss function is exponentially tailed (e.g., logistic, exponential, etc.), the (normalized) asymptotic solution of GD converges to the direction of the hard-margin SVM. That is, analyzing the SVM is equivalent to analyzing the neural net in a classification task (in a minimalist setup). However, analyzing the properties of SVMs is quite hard due to the randomness of the support vectors, which depends entirely on the sampling process of the training set (or the population distribution). Then, what can we do about this? Thankfully, researchers have found that under a suitable condition of “overparametrization,” the two solutions become equivalent. We now take a deeper look. Support Vector ProliferationRecall that the KKT conditions of the SVM state that the solution takes the form \(\hat{\mathbf{w}}_{\text{SVM}} = \sum_i \alpha_i y_i \mathbf{x}_i\) with dual variables \(\alpha_i \geq 0\), where \(\alpha_i > 0\) is allowed only if the corresponding margin constraint is active, i.e., \(y_i \, \hat{\mathbf{w}}_{\text{SVM}}^\top \mathbf{x}_i = 1\); points with active constraints are the support vectors. The overparametrization condition under which the two solutions coincide is the following: once \(d \gtrsim n \log n\), every training point becomes a support vector – a phenomenon called support vector proliferation (SVP). Theorem (from [1, 2]). Let \(\mathbf{x}_i \overset{\text{i.i.d.}}{\sim} \mathcal{N}(\mathbf{0}, \mathbf{I}_d)\), and let the labels \(y_i \in \{\pm 1\}\) be arbitrary (possibly depending on \(\mathbf{x}_i\)). There exists a universal constant \(C > 0\) such that if \(d \geq C n \log n\), then with probability \(1 - o(1)\), every training point is a support vector, and consequently \(\hat{\mathbf{w}}_{\text{SVM}} = \hat{\mathbf{w}}_{\text{MNI}}\). ProofLet \(\boldsymbol{\beta} = (\mathbf{X}\mathbf{X}^\top)^{-1}\mathbf{y}\), so that the MNI can be written in the span of the training points as \[ \hat{\mathbf{w}}_{\text{MNI}} = \mathbf{X}^\top \boldsymbol{\beta} = \sum_i \beta_i \mathbf{x}_i = \sum_i (y_i \beta_i) \, y_i \mathbf{x}_i. \] Suppose \(y_i \beta_i \geq 0\) for all \(i\), and set \(\alpha_i := y_i \beta_i\). Then \((\hat{\mathbf{w}}_{\text{MNI}}, \boldsymbol{\alpha})\) satisfies the KKT conditions of the SVM: (stationarity) \(\hat{\mathbf{w}}_{\text{MNI}} = \sum_i \alpha_i y_i \mathbf{x}_i\) by the display above; (primal feasibility) \(y_i \, \hat{\mathbf{w}}_{\text{MNI}}^\top \mathbf{x}_i = 1 \geq 1\) since the MNI interpolates; (dual feasibility) \(\alpha_i \geq 0\) by assumption; (complementary slackness) trivially, since every constraint is active. As the SVM is a convex program, the KKT conditions are sufficient for optimality, so \(\hat{\mathbf{w}}_{\text{SVM}} = \hat{\mathbf{w}}_{\text{MNI}}\) and every training point is a support vector. It therefore suffices to show that, with high probability, \(y_i \beta_i > 0\) for all \(i\). A leave-one-out formula. Fix a point \(i\), let \(\mathbf{X}_{-i}\) and \(\mathbf{y}_{-i}\) denote the data with point \(i\) removed, and let \(\mathbf{A}_{-i} = \mathbf{X}_{-i}\mathbf{X}_{-i}^\top\). Permuting point \(i\) to the last position and applying the block (Schur complement) inversion formula to \(\boldsymbol{\beta} = (\mathbf{X}\mathbf{X}^\top)^{-1}\mathbf{y}\) gives \[ \beta_i = \frac{y_i - \mathbf{x}_i^\top \hat{\mathbf{v}}_{-i}}{\|\mathbf{x}_i\|_2^2 - \mathbf{x}_i^\top \mathbf{X}_{-i}^\top \mathbf{A}_{-i}^{-1} \mathbf{X}_{-i} \mathbf{x}_i}, \qquad \text{where} \quad \hat{\mathbf{v}}_{-i} := \mathbf{X}_{-i}^\top \mathbf{A}_{-i}^{-1} \mathbf{y}_{-i} \] is the leave-one-out MNI, trained on all points except \(i\). The denominator equals \(\|(\mathbf{I} - \mathbf{P}_{-i})\mathbf{x}_i\|_2^2 > 0\), where \(\mathbf{P}_{-i}\) is the orthogonal projection onto the span of the other points, so the sign of \(\beta_i\) is the sign of the numerator, and multiplying by \(y_i\) (using \(y_i^2 = 1\)) yields the criterion \[ y_i \beta_i > 0 \quad \Longleftrightarrow \quad y_i \, \mathbf{x}_i^\top \hat{\mathbf{v}}_{-i} < 1. \] Concentration. It remains to show that the leave-one-out predictions \(g_i := \mathbf{x}_i^\top \hat{\mathbf{v}}_{-i}\) are uniformly smaller than \(1\). Since the samples are i.i.d., \(\mathbf{x}_i\) is independent of \((\mathbf{X}_{-i}, \mathbf{y}_{-i})\), and hence of \(\hat{\mathbf{v}}_{-i}\). Conditioning on the latter, \[ g_i \mid (\mathbf{X}_{-i}, \mathbf{y}_{-i}) \;\sim\; \mathcal{N}\big(0, \|\hat{\mathbf{v}}_{-i}\|_2^2\big), \qquad \|\hat{\mathbf{v}}_{-i}\|_2^2 = \mathbf{y}_{-i}^\top \mathbf{A}_{-i}^{-1} \mathbf{y}_{-i} \leq \frac{n-1}{\lambda_{\min}(\mathbf{A}_{-i})}. \] Standard bounds on the extreme singular values of Gaussian matrices give \(\lambda_{\min}(\mathbf{X}\mathbf{X}^\top) \geq (\sqrt{d} - c\sqrt{n})^2 \geq d/2\) with probability at least \(1 - e^{-c'd}\) once \(d \gtrsim n\); by Cauchy's interlacing theorem, the same lower bound holds simultaneously for every principal submatrix \(\mathbf{A}_{-i}\). On this event, \(\|\hat{\mathbf{v}}_{-i}\|_2^2 \leq 2n/d\) for all \(i\), and the Gaussian tail bound gives, for each \(i\), \[ \mathbb{P}\big( y_i g_i \geq 1 \big) \;\leq\; \mathbb{P}\big( |g_i| \geq 1 \big) \;\leq\; 2\exp\!\Big( -\frac{1}{2\|\hat{\mathbf{v}}_{-i}\|_2^2} \Big) \;\leq\; 2\exp\!\Big( -\frac{d}{4n} \Big), \] where taking the absolute value sidesteps the dependence between \(y_i\) and \(\mathbf{x}_i\). Finally, taking a union bound over the \(n\) points, we get \[ \mathbb{P}\big( \exists i: \; y_i \beta_i \leq 0 \big) \;\leq\; 2n \exp\!\Big( -\frac{d}{4n} \Big) + e^{-c'd} \;=\; 2\exp\!\Big( \log n -\frac{d}{4n} \Big) + e^{-c'd}, \] which vanishes as soon as \(d \geq 5 n \log n\). \(\square\) Note
References[1] Muthukumar et al., Classification vs. regression in overparameterized regimes: Does the loss function matter? JMLR, 2021. |