Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

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

POST-REBUTTAL: having read the response and the ensuing discussion I have chosen to leave my response unchanged and recommend accepting this paper.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
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.

From 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.
limitations_and_societal_impact: The authors are suggested to elaborate more on in which scenarios the SVP theory can be applied?
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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$.
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. 

Quality: 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). 

Clarity: 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). 

Significance: 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:
- The improvement is only by a factor $O(\log 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.
- 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. 
- 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). 

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

Conclusion: 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. 

Major comments:

L. 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.
Since 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.

Eq. 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).

Minor comments: 

L. 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).

L. 137: . missing

L. 138: "matrix" -> "the matrix", "a matrix" or "", similar in L. 136

L. 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.)

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

L. 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?

L. 208: meaning of formulation "with constant probability" is unclear

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

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

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

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

Fig. 2: "from the Gaussian samples" -> "using a Gaussian distribution"?

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

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

L. 491: "invertiability" -> "invertibility"

L. 492: "inveritble" -> "invertible"

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

L. 544: "problem" can be removed

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

Equation after l. 588: The last line should have parentheses after $\exp$.

L. 610: Would it be more appropriate to use $n-m$ instead of $n$ here?
limitations_and_societal_impact: Limitations of the paper are addressed. Potential societal impact is not addressed since this is a theoretical paper.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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:

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

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

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

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

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

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:

- 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)?
- 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.

Finally, one question: do the results require $n$ to be large or are valid down to $n=O(1)$?
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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:

1. For SVM, this paper only focuses on the hard-margin SVM, however, soft-margin SVM is more commonly-used in real-world applications.

2. 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?

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

4.  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)$.


#UPDATES AFTER RESPONSE
I 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.
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_title: null

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)