# Benign Overfitting in Multiclass Classification:
All Roads Lead to Interpolation

Ke Wang111Primary correspondence to<EMAIL_ADDRESS>CT is also affiliated
with the Department of Electrical and Computer Engineering, University of
California, Santa Barbara. Vidya Muthukumar† Christos Thrampoulidis∘

∗Department of Statistics and Applied Probability, University of California
Santa Barbara
†Electrical and Computer Engineering & Industrial and Systems Engineering,
Georgia Institute of Technology
∘Department of Electrical and Computer Engineering, University of British
Columbia

###### Abstract

The literature on “benign overfitting” in overparameterized models has been
mostly restricted to regression or binary classification; however, modern
machine learning operates in the multiclass setting. Motivated by this
discrepancy, we study benign overfitting in multiclass linear classification.
Specifically, we consider the following training algorithms on separable data:
(i) empirical risk minimization (ERM) with cross-entropy loss, which converges
to the multiclass support vector machine (SVM) solution; (ii) ERM with least-
squares loss, which converges to the min-norm interpolating (MNI) solution;
and, (iii) the one-vs-all SVM classifier. First, we provide a simple
sufficient deterministic condition under which _all_ three algorithms lead to
classifiers that interpolate the training data and have equal accuracy. When
the data is generated from Gaussian mixtures or a multinomial logistic model,
this condition holds under high enough effective overparameterization. We also
show that this sufficient condition is satisfied under “neural collapse”, a
phenomenon that is observed in training deep neural networks. Second, we
derive novel bounds on the accuracy of the MNI classifier, thereby showing
that all three training algorithms lead to benign overfitting under sufficient
overparameterization. Ultimately, our analysis shows that good generalization
is possible for SVM solutions beyond the realm in which typical margin-based
bounds apply.

##  1 Introduction

Modern deep neural networks are overparameterized (high-dimensional) with
respect to the amount of training data. Consequently, they achieve zero
training error even on noisy training data, yet generalize well on test data
[ZBH+17]. Recent mathematical analysis has shown that fitting of noise in
regression tasks can in fact be relatively benign for linear models that are
sufficiently high-dimensional [BLLT20, BHX20, HMRT19, MVSS20, KLS20]. These
analyses do not directly extend to classification, which requires separate
treatment. In fact, recent progress on sharp analysis of interpolating binary
classifiers [MNS+21, CL21, WT21, CGB21] revealed high-dimensional regimes in
which binary classification generalizes well, but the corresponding regression
task does _not_ work and/or the success _cannot_ be predicted by classical
margin-based bounds [SFBL98, BM03].

In an important separate development, these same high-dimensional regimes
admit an equivalence of loss functions used for optimization at training time.
The support vector machine (SVM), which arises from minimizing the logistic
loss using gradient descent [SHN+18, JT19], was recently shown to satisfy a
high-probability equivalence to interpolation, which arises from minimizing
the squared loss [MNS+21, HMX21]. This equivalence suggests that interpolation
is ubiquitous in very overparameterized settings, and can arise naturally as a
consequence of the optimization procedure even when this is not explicitly
encoded or intended. Moreover, this equivalence to interpolation and
corresponding analysis implies that the SVM can generalize even in regimes
where classical learning theory bounds are not predictive. In the logistic
model case [MNS+21] and Gaussian binary mixture model case [CL21, WT21,
CGB21], it is shown that good generalization of the SVM is possible beyond the
realm in which classical margin-based bounds apply. These analyses lend
theoretical grounding to the surprising hypothesis that squared loss can be
equivalent to, or possibly even superior, to the cross-entropy loss for
classification tasks. Ryan Rifkin provided empirical support for this
hypothesis on kernel machines [Rif02, RK04]; more recently, corresponding
empirical evidence has been provided for state-of-the-art deep neural networks
[HB20, PL20a].

These perspectives have thus far been limited to regression and binary
classification settings. In contrast, most success stories and surprising new
phenomena of modern machine learning have been recorded in _multiclass_
classification settings, which appear naturally in a host of applications that
demand the ability to automatically distinguish between large numbers of
different classes. For example, the popular ImageNet dataset [RDS+15] contains
on the order of $1000$ classes. Whether a) good generalization beyond
effectively low-dimensional regimes where margin-based bounds are predictive
is possible, and b) equivalence of squared loss and cross-entropy loss holds
in multiclass settings remained open problems.

This paper makes significant progress towards a complete understanding of the
optimization and generalization properties of high-dimensional linear
multiclass classification, both for unconditional Gaussian covariates (where
labels are generated via a multinomial logistic model), and Gaussian mixture
models. Our contributions are listed in more detail below.

###  1.1 Our Contributions

Figure 1: Contributions and organization.

$\bullet$ We establish a _deterministic_ sufficient condition under which the
multiclass SVM solution has a very simple and symmetric structure: it is
identical to the solution of a One-vs-All (OvA) SVM classifier that uses a
_simplex-type_ encoding for the labels (unlike the classical one-hot
encoding). Moreover, the constraints at both solutions are active.
Geometrically, this means that all data points are support vectors, and they
interpolate the simplex-encoding vector representation of the labels. See
Figure 2 for a numerical illustration confirming our finding.
$\bullet$ This implies a surprising equivalence between traditionally
different formulations of multiclass SVM, which in turn are equivalent to the
minimum-norm interpolating (MNI) classifier on the one-hot label vectors.
Thus, we show that the outcomes of training with cross-entropy (CE) loss and
squared loss are identical in terms of classification error.
$\bullet$ Next, for data following a Gaussian-mixtures model (GMM) or a
Multinomial logistic model (MLM), we show that the above sufficient condition
is satisfied with high-probability under sufficient “effective”
overparameterization. Our sufficient conditions are non-asymptotic and are
characterized in terms of the data dimension, the number of classes, and
functionals of the data covariance matrix. Our numerical results show
excellent agreement with our theoretical findings. We also show that the
sufficient condition of equivalence of CE and squared losses is satisfied when
the “neural collapse” phenomenon occurs [PHD20].
$\bullet$ Finally, we provide novel non-asymptotic bounds on the error of the
MNI classifier for data generated either from the GMM or the MLM, and identify
sufficient conditions under which benign overfitting occurs. A direct outcome
of our results is that benign overfitting occurs under these conditions
regardless of whether the cross-entropy loss or squared loss is used during
training.

Figure 1 describes our contributions and their implications through a
flowchart. To the best of our knowledge, these are the first results
characterizing a) equivalence of loss functions, and b) generalization of
interpolating solutions in the multiclass setting. The multiclass setting
poses several challenges over and above the recently studied binary case. When
presenting our results in later sections, we discuss in detail how our
analysis circumvents these challenges.

###  1.2 Related Work

##### Multiclass classification and the impact of training loss functions

There is a classical body of work on algorithms for multiclass classification,
e.g., [WW98, BB99, DB95, CS02, LLW04] and several empirical studies of their
comparative performance [RK04, F0̈2, ASS01] (also see [HYS16, GCOZ17, KS18,
BEH20, DCO20, HB20, PL20a] for recent such studies in the context of deep
nets). Many of these (e.g. [RK04, HB20, BEH20]) have found that least-squares
minimization yields competitive test classification performance to cross-
entropy minimization. Our proof of equivalence of the SVM and MNI solutions
under sufficient overparameterization provides theoretical support for this
line of work. This is a consequence of the implicit bias of gradient descent
run on the CE and squared losses leading to the multiclass SVM [SHN+18, JT19]
and MNI [EHN96] respectively. Numerous classical works investigated
consistency [Zha04, LLW04, TB07, PGS13, PS16] and finite-sample behavior,
e.g., [KP02, CKMY16, LDBK15, Mau16, LDZK19] of multiclass classification
algorithms in the underparameterized regime. In contrast, our central focus is
the highly overparameterized regime, where the typical uniform convergence
techniques cannot apply.

##### Binary classification error analyses in overparameterized regime

The recent wave of analyses of the minimum-$\ell_{2}$-norm interpolator (MNI)
in high-dimensional linear regression (beginning with [BLLT20, BHX20, HMRT19,
MVSS20, KLS20]) prompted researchers to consider to what extent the phenomena
of benign overfitting and double descent [BHMM19, GJS+20] can be proven to
occur in classification tasks. Even the binary classification setting turns
out to be significantly more challenging to study owing to the discontinuity
of the 0-1 test loss function. Sharp asymptotic formulas for the
generalization error of binary classification algorithms in the linear high-
dimensional regime have been derived in several recent works [Hua17, SC19,
MLC19, SAH19, TPT20, TPT21, DKT21, MRSY19, KA21, LS20, SAH20, AKLZ20, Lol20,
DL20]. These formulas are solutions to complicated nonlinear systems of
equations that typically do not admit closed-form expressions. A separate line
of work provides non-asymptotic error bounds for both the MNI classifier and
the SVM classifier [CL21, MNS+21, WT21, CGB21]; in particular, [MNS+21]
analyzed the SVM in a Gaussian covariates model by explicitly connecting its
solution to the MNI solution. Subsequently, [WT21] also took this route to
analyze the SVM and MNI in mixture models, and even more recently, [CGB21]
provided extensions of this result to sub-Gaussian mixtures. While these non-
asymptotic analyses are only sharp in their dependences on the sample size $n$
and the data dimension $p$, they provide closed-form generalization
expressions in terms of easily interpretable summary statistics.
Interestingly, these results imply good generalization of the SVM beyond the
regime in which margin-based bounds are predictive. Specifically, [MNS+21]
identifies a separating regime for Gaussian covariates in which corresponding
regression tasks would not generalize. In the Gaussian mixture model, margin-
based bounds [SFBL98, BM03] (as well as corresponding recently derived mistake
bounds on interpolating classifiers [LR21]) would require the intrinsic
signal-to-noise-ratio (SNR) to scale at least as $\omega(p^{1/2})$ for good
generalization; however, the analyses of [WT21, CGB21] show that good
generalization is possible for significantly lower SNR scaling as
$\omega(p^{1/4})$. The above error analyses are specialized to the binary
case, where closed-form error expressions are easy to derive [MNS+21]. The
only related work applicable to the multiclass case is [TOS20], which also
highlights the numerous challenges of obtaining a sharp error analysis in
multiclass settings. Specifically, [TOS20] derived sharp generalization
formulas for multiclass least-squares in underparameterized settings;
extensions to the overparameterized regime and other losses beyond least-
squares remained open. Finally, [KT21] recently derived sharp phase-transition
thresholds for the feasibility of OvA-SVM on multiclass Gaussian mixture data
in the linear high-dimensional regime. However, this does not address the more
challenging multiclass-SVM that we investigate here.

##### Other SVM analyses

The number of support vectors in the binary SVM has been characterized in low-
dimensional separable and non-separable settings [DOS99, BG01, MO05] and
scenarios have been identified in which there is a vanishing fraction of
support vectors, as this implies good generalization222In this context, the
fact that [MNS+21, WT21, CGB21] provide good generalization bounds in the
regime where support vectors proliferate is particularly surprising. In
conventional wisdom, a proliferation of support vectors was associated with
overfitting but this turns out to not be the case here. via PAC-Bayes sample
compression bounds [Vap13, GHST05, GLL+11]. In the highly overparameterized
regime that we consider, perhaps surprisingly, the opposite behavior occurs:
all training points become support vectors with high probability [DOS99, BG01,
MO05, MNS+21, HMX21]. In particular, [HMX21] provided sharp non-asymptotic
sufficient conditions for this phenomenon for both isotropic and anisotropic
settings. The techniques in [MNS+21, HMX21] are highly specialized to the
binary SVM and its dual, where a simple complementary slackness condition
directly implies the property of interpolation. In contrast, the complementary
slackness condition for the case of multiclass SVM does not directly imply
interpolation; in fact, the operational meaning of “all training points
becoming support vectors” is unclear in the multiclass SVM. Our proof of
deterministic equivalence goes beyond the complementary slackness condition
and uncovers a surprising symmetric structure by showing equivalence of
multiclass SVM to a simplex-type OvA classifier. The simplex equiangular tight
frame structure that we uncover is somewhat reminiscent of the recently
observed neural collapse phenomenon in deep neural networks [PHD20]; indeed,
Section 3.3 shows an explicit connection between our deterministic equivalence
condition and the neural collapse phenomenon. Further, [MNS+21, HMX21] focus
on proving deterministic conditions for equivalence in the case of labels
generated from covariates; the mixture model case (where covariates are
generated from labels) turns out to be significantly more involved.

###  1.3 Organization

The paper is organized as follows. Section 2 describes the problem setting and
sets up notation. Section 3 presents our main results on the equivalence
between the multiclass SVM and MNI solutions for two data models: the Gaussian
mixture model (GMM) and the multinomial logistic model (MLM). In the same
section, we also show the equivalence under the Neural Collapse phenomenon.
Section 4 presents our error analysis of the MNI solution (and, by our proved
equivalence, the multiclass SVM) for the GMM and the MLM, and Section 5
presents consequent conditions for benign overfitting of multiclass
classification. Finally, Section 6 presents proofs of our main results;
auxiliary proofs are deferred to the appendices. Please refer to the table of
contents (before the appendices) for a more detailed decomposition of results
and proofs.

##### Notation

For a vector $\mathbf{v}\in\mathbb{R}^{p}$ , let
$\|{\mathbf{v}}\|_{2}=\sqrt{\sum_{i=1}^{p}v_{i}^{2}}$,
$\|\mathbf{v}\|_{1}={\sum_{i=1}^{p}|v_{i}|}$,
$\|\mathbf{v}\|_{\infty}=\max_{i}\\{|v_{i}|\\}$. $\mathbf{v}>\mathbf{0}$ is
interpreted elementwise. $\mathbf{1}_{m}$ / $\mathbf{0}_{m}$ denote the all-
ones / all-zeros vectors of dimension $m$ and $\mathbf{e}_{i}$ denotes the
$i$-th standard basis vector. For a matrix $\mathbf{M}$, $\|\mathbf{M}\|_{2}$
denotes its $2\to 2$ operator norm and $\|\mathbf{M}\|_{F}$ denotes the
Frobenius norm. $\odot$ denotes the Hadamard product. [$n$] denotes the set
$\\{1,2,...,n\\}$. We also use standard “Big O” notations $\Theta(\cdot)$,
$\omega(\cdot)$, e.g., see [CLRS09, Chapter 3]. Finally, we write
$\mathcal{N}(\boldsymbol{\mu},\boldsymbol{\Sigma})$ for the (multivariate)
Gaussian distribution of mean $\boldsymbol{\mu}$ and covariance matrix
$\boldsymbol{\Sigma}$, and, $Q(x)=\mathbb{P}(Z>x),~{}Z\sim\mathcal{N}(0,1)$
for the Q-function of a standard normal. Throughout, constants refer to
strictly positive numbers that do not depend on the problem dimensions $n$ or
$p$.

##  2 Problem setting

We consider the multiclass classification problem with $k$ classes. Let
$\mathbf{x}\in\mathbb{R}^{p}$ denote the feature vector and $y\in[k]$
represent the class label associated with one of the $k$ classes. We assume
that the training data has $n$ feature$/$label pairs
$\\{\mathbf{x}_{i},y_{i}\\}_{i=1}^{n}$. We focus on the overparameterized
regime, i.e., $p>Cn$, and we will frequently consider $p\gg n$. For
convenience, we express the labels using the one-hot coding vector
$\mathbf{y}_{i}\in\mathbb{R}^{k}$, where only the $y_{i}$-th entry of
$\mathbf{y}_{i}$ is $1$ and all other entries are zero, i.e.,
$\mathbf{y}_{i}=\boldsymbol{e}_{y_{i}}$. With this notation, the feature and
label matrices are given in compact form as follows:
$\mathbf{X}=\begin{bmatrix}\mathbf{x}_{1}&\mathbf{x}_{2}&\cdots&\mathbf{x}_{n}\end{bmatrix}\in\mathbb{R}^{p\times
n}$ and
$\mathbf{Y}=\begin{bmatrix}\mathbf{y}_{1}&\mathbf{y}_{2}&\cdots&\mathbf{y}_{n}\end{bmatrix}=\begin{bmatrix}\mathbf{v}_{1}&\mathbf{v}_{2}&\cdots\mathbf{v}_{k}\end{bmatrix}^{T}\in\mathbb{R}^{k\times
n},$ where we have defined $\mathbf{v}_{c}\in\mathbb{R}^{n},c\in[k]$ to denote
the $c$-th row of the matrix $\mathbf{Y}$.

###  2.1 Data models

We assume that the data pairs $\\{\mathbf{x}_{i},y_{i}\\}_{i=1}^{n}$ are
independently and identically distributed (IID). We will consider two models
for the distribution of $(\mathbf{x},y)$. For both models, we define the mean
vectors $\\{\boldsymbol{\mu}_{j}\\}_{j=1}^{k}\in\mathbb{R}^{p}$, and the mean
matrix is given by
$\mathbf{M}:=\begin{bmatrix}\boldsymbol{\mu}_{1}&\boldsymbol{\mu}_{2}&\cdots&\boldsymbol{\mu}_{k}\end{bmatrix}\in\mathbb{R}^{p\times
k}.$

##### Gaussian Mixture Model (GMM)

In this model, the mean vector $\boldsymbol{\mu}_{i}$ represents the
conditional mean vector for the $i$-th class. Specifically, each observation
$(\mathbf{x}_{i},y_{i})$ belongs to to class $c\in[k]$ with probability
$\pi_{c}$ and conditional on the label $y_{i}$, $\mathbf{x}_{i}$ follows a
multivariate Gaussian distribution. In summary, we have

$\displaystyle\mathbb{P}(y=c)=\pi_{c}~{}~{}\text{and}~{}~{}\mathbf{x}=\boldsymbol{\mu}_{y}+\mathbf{q},~{}\mathbf{q}\sim\mathcal{N}(\boldsymbol{0},\boldsymbol{\Sigma}).$
(1)

In this work, we focus on the isotropic case
$\boldsymbol{\Sigma}=\mathbf{I}_{p}$. Our analysis can likely be extended to
the more general anisotropic case, but we leave this to future work.

##### Multinomial Logit Model (MLM)

In this model, the feature vector $\mathbf{x}\in\mathbb{R}^{p}$ is distributed
as $\mathcal{N}(\boldsymbol{0},\boldsymbol{\Sigma})$, and the conditional
density of the class label $y$ is given by the soft-max function.
Specifically, we have

$\displaystyle\mathbf{x}\sim\mathcal{N}(\boldsymbol{0},\boldsymbol{\Sigma})~{}~{}\text{and}~{}~{}\mathbb{P}(y=c|\mathbf{x})=\frac{\exp(\boldsymbol{\mu}_{c}^{T}\mathbf{x})}{\sum_{j\in[k]}\exp(\boldsymbol{\mu}_{j}^{T}\mathbf{x})}.$
(2)

For this model, we analyze both the isotropic and anisotropic cases.

###  2.2 Data separability

We consider linear classifiers parameterized by
$\mathbf{W}=\begin{bmatrix}\mathbf{w}_{1}&\mathbf{w}_{2}&\cdots&\mathbf{w}_{k}\end{bmatrix}^{T}\in\mathbb{R}^{k\times
p}.$ Given input feature vector $\mathbf{x}$, the classifier is a function
that maps $\mathbf{x}$ into an output of $k$ via
$\mathbf{x}\mapsto\mathbf{W}\mathbf{x}\in\mathbb{R}^{k}$ (for simplicity, we
ignore the bias term throughout). We will operate in a regime where the
training data are linearly separable. In multiclass settings, there exist
multiple notions of separability. Here, we focus on (i) multiclass
separability (also called $k$-class separability) (ii) one-vs-all (OvA)
separability, and, recall their definitions below.

######  Definition 1 (multiclass and OvA separability).

The dataset $\\{\mathbf{x}_{i},y_{i}\\}_{i\in[n]}$ is multiclass linearly
separable when

$\displaystyle\exists\mathbf{W}\,:\,(\mathbf{w}_{y_{i}}-\mathbf{w}_{c})^{T}\mathbf{x}_{i}\geq
1,~{}\forall{c\neq y_{i},c\in[k]},\text{ and }\forall i\in[n].$ (3)

The dataset is one-vs-all (OvA) separable when

$\displaystyle\exists\mathbf{W}\,:\,\mathbf{w}_{c}^{T}\mathbf{x}_{i}\begin{cases}\geq
1\text{ if }y_{i}=c\\\ \leq-1\text{ if }y_{i}\neq
c\end{cases},\forall{c\in[k]},\text{ and }\forall i\in[n].$ (4)

Under both data models of the previous section (i.e., GMM and MLM), we have
$\rm{rank}(\mathbf{X})=n$ almost surely in the overparameterized regime $p>n$.
This directly implies OvA separability. It turns out that OvA separability
implies multiclass separability, but not vice versa (see [BM94] for a
counterexample).

###  2.3 Classification error

Consider a linear classifier $\widehat{\mathbf{W}}$ and a fresh sample
$(\mathbf{x},y)$ generated following the same distribution as the training
data. As is standard, we predict $\hat{y}$ by a “winner takes it all
strategy”, i.e.,
$\hat{y}=\arg\max_{j\in[k]}\widehat{\mathbf{w}}_{j}^{T}\mathbf{x}$. Then, the
classification error conditioned on the true label being $c$, which we refer
to as the class-wise classification error, is defined as

$\displaystyle\mathbb{P}_{e|c}:=\mathbb{P}(\hat{y}\neq
y|y=c)=\mathbb{P}(\widehat{\mathbf{w}}_{c}^{T}\mathbf{x}\leq\max_{j\neq
c}\widehat{\mathbf{w}}_{j}^{T}\mathbf{x}).$ (5)

In turn, the total classification error is defined as

$\displaystyle\mathbb{P}_{e}:=\mathbb{P}(\hat{y}\neq
y)=\mathbb{P}(\arg\max_{j\in[k]}\widehat{\mathbf{w}}_{j}^{T}\mathbf{x}\neq
y)=\mathbb{P}(\widehat{\mathbf{w}}_{y}^{T}\mathbf{x}\leq\max_{j\neq
y}\widehat{\mathbf{w}}_{j}^{T}\mathbf{x}).$ (6)

###  2.4 Classification algorithms

Next, we review several different training strategies for which we
characterize the total/class-wise classification error in this paper.

##### Multiclass SVM

Consider training $\mathbf{W}$ by minimizing the cross-entropy (CE) loss

$\displaystyle\mathcal{L}(\mathbf{W}):=-\log\left(\frac{{e^{\mathbf{w}_{y_{i}}^{T}\mathbf{x}_{i}}}}{{\sum_{c\in[k]}e^{\mathbf{w}_{c}^{T}\mathbf{x}_{i}}}}\right)$

with the gradient descent algorithm (with constant step size $\eta$). In the
separable regime, the CE loss $\mathcal{L}(\mathbf{W})$ can be driven to zero.
Moreover, [SHN+18, Thm. 7] showed that the normalized iterates
$\\{\mathbf{W}^{t}\\}_{t\geq 1}$ converge as

$\displaystyle\lim_{t\rightarrow\infty}\big{\|}\frac{\mathbf{W}^{t}}{\log{t}}-\mathbf{W}_{\text{SVM}}\big{\|}_{F}=0,$

where $\mathbf{W}_{\text{SVM}}$ is the solution of the _multiclass SVM_ [WW98]
given by

$\displaystyle\mathbf{W}_{\text{SVM}}:=\arg\min_{\mathbf{W}}\lVert\mathbf{W}\rVert_{F}\quad\text{sub.
to}~{}~{}(\mathbf{w}_{y_{i}}-\mathbf{w}_{c})^{T}\mathbf{x}_{i}\geq
1,~{}\forall i\in[n],c\in[k]\text{ s.t. }c\neq y_{i}.$ (7)

It is important to note that the normalizing factor $\log{t}$ here does not
depend on the class label; hence, in the limit of GD iterations, the solution
$\mathbf{W}^{t}$ decides the same label as multiclass SVM for any test sample.

##### One-vs-all SVM

In contrast to Equation (7), which optimizes the hyperplanes
$\\{\mathbf{w}_{c}\\}_{c\in[k]}$ jointly, the one-vs-all (OvA)-SVM classifier
solves $k$ separable optimization problems that maximize the margin of each
class with respect to all the rest. Concretely, the OvA-SVM solves the
following optimization problem for all $c\in[k]$:

$\displaystyle\mathbf{w}_{{\rm
OvA},c}:=\arg\min_{\mathbf{w}}\|{\mathbf{w}}\|_{2}\quad\text{sub.
to}~{}~{}\mathbf{w}^{T}\mathbf{x}_{i}\begin{cases}\geq
1,&~{}\text{if}~{}\mathbf{y}_{i}=c,\\\
\leq-1,&~{}\text{if}~{}\mathbf{y}_{i}\neq c,\end{cases}~{}~{}\forall i\in[n].$
(8)

In general, the solutions to Equations (7) and (8) are different. While the
OvA-SVM does not have an obvious connection to any training loss function, its
relevance will become clear in Section 3. Perhaps surprisingly, we will prove
that in the highly overparameterized regime the multiclass SVM solution is
identical to a slight variant of (8).

##### Min-norm interpolating (MNI) classifier

An alternative to the CE loss is the square loss
$\mathcal{L}(\mathbf{W}):=\frac{1}{2n}\|\mathbf{Y}-\mathbf{W}\mathbf{X}\|_{2}^{2}=\frac{1}{2n}\sum_{i=1}^{n}\|{\mathbf{W}\mathbf{x}_{i}-\mathbf{y}_{i}}\|_{2}^{2}$.
Since the square loss is tailored to regression, it might appear that the CE
loss is more appropriate for classification. Perhaps surprisingly, one of the
main messages of this paper is that under sufficient effective
overparameterization the two losses actually have equivalent performance. Our
results lend theoretical support to empirical observations of competitive
classification accuracy between the square loss and CE loss in practice
[Rif02, HB20, PL20a].

Towards showing this, we note that when the linear model is overparameterized
(i.e. $p>n$) and assuming $\rm{rank}(\mathbf{X})=n$ (e.g this holds almost
surely under both the GMM and MLM), the data can be linearly interpolated,
i.e. the square-loss can be driven to zero. Then, it is well-known [EHN96]
that gradient descent with sufficiently small step size and appropriate
initialization converges to the minimum-norm -interpolating (MNI) solution,
given by:

$\displaystyle\mathbf{W}_{\text{MNI}}:=\arg\min_{\mathbf{W}}\lVert\mathbf{W}\rVert_{F},~{}~{}\text{sub.
to}~{}~{}\mathbf{X}^{T}\mathbf{w}_{c}=\mathbf{v}_{c},\forall c\in[k].$ (9)

Since $\mathbf{X}^{T}\mathbf{X}$ is invertible, the MNI solution is given in
closed form as
$\mathbf{W}_{\text{MNI}}^{T}=\mathbf{X}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{Y}^{T}$.
From here on, we refer to (9) as the MNI classifier.

##  3 Equivalence of solutions and geometry of support vectors

In this section, we show the equivalence of the solutions of the three
classifiers defined above in certain high-dimensional regimes.

###  3.1 A key deterministic condition

We first establish a key deterministic property of SVM that holds for
_generic_ multiclass datasets $(\mathbf{X},\mathbf{Y})$ (i.e. not necessarily
generated by either the GMM or MLM). Specifically, Theorem 1 below derives a
sufficient condition (cf. (12)) under which the multiclass SVM solution has a
surprisingly simple structure. First, the constraints are _all_ active at the
optima (cf. (13)). Second, and perhaps more interestingly, this happens in a
very specific way; the feature vectors interpolate a simplex representation of
the multiclass labels, as specified below:

$\displaystyle\hat{\mathbf{w}}_{c}^{T}\mathbf{x}_{i}=z_{ci}:=\begin{cases}\frac{k-1}{k}&,~{}c=y_{i}\\\
-\frac{1}{k}&,~{}c\neq y_{i}\end{cases}\,\text{ for all }i\in[n],c\in[k].$
(10)

To interpret this, define an adjusted $k$-dimensional label vector
$\widetilde{\mathbf{y}}_{i}:=[z_{1i},z_{2i},\ldots,z_{ki}]^{T}$ for each
training sample $i\in[n]$. This can be understood as a $k$-dimensional vector
encoding of the original label $y_{i}$ that is different from the classical
one-hot encoding representation $\mathbf{y}_{i}$; in particular, it has
entries either $-1/k$ or $1-1/k$ (rather than $0$ or $1$). We call this new
representation a _simplex representation_ , based on the following
observation. Consider $k$ data points that each belong to a different class
$1,\ldots,k$, and their corresponding vector representations
$\widetilde{\mathbf{y}}_{1},\ldots,\widetilde{\mathbf{y}}_{k}$. Then, it is
easy to verify that the vectors
$\\{\mathbf{0},\widetilde{\mathbf{y}}_{1},\ldots,\widetilde{\mathbf{y}}_{k}\\}$
are affinely independent; hence, they form the vectices of a $k$-simplex.

######  Theorem 1.

For a multiclass separable dataset with feature matrix
$\mathbf{X}=[\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{n}]\in\mathbb{R}^{p\times
n}$ and label matrix
$\mathbf{Y}=[\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{k}]^{T}\in\mathbb{R}^{k\times
n}$, denote by
$\mathbf{W}_{\text{SVM}}=[\hat{\mathbf{w}}_{1},\hat{\mathbf{w}}_{2},\ldots,\hat{\mathbf{w}}_{k}]^{T}$
the multiclass SVM solution of (7). For each class $c\in[k]$ define vectors
$\mathbf{z}_{c}\in\mathbb{R}^{n}$ such that

$\displaystyle\mathbf{z}_{c}=\mathbf{v}_{c}-\frac{1}{k}\mathbf{1}_{n},~{}c\in[k].$
(11)

Let $(\mathbf{X}^{T}\mathbf{X})^{+}$ be the Moore-Penrose generalized
inverse333Most of the regimes that we study are ultra-high-dimensional (i.e.
$p\gg n$), and so $\mathbf{X}^{T}\mathbf{X}$ is invertible with high
probability. Consequently, $(\mathbf{X}^{T}\mathbf{X})^{+}$ can be replaced by
$(\mathbf{X}^{T}\mathbf{X})^{-1}$ in these cases. of the Gram matrix
$\mathbf{X}^{T}\mathbf{X}$ and assume that the following condition holds

$\displaystyle\mathbf{z}_{c}\odot(\mathbf{X}^{T}\mathbf{X})^{+}\mathbf{z}_{c}>\mathbf{0},\quad\forall
c\in[k].$ (12)

Then, the SVM solution $\mathbf{W}_{\text{SVM}}$ is such that all the
constraints in (7) are active. That is,

$\displaystyle(\hat{\mathbf{w}}_{y_{i}}-\hat{\mathbf{w}}_{c})^{T}\mathbf{x}_{i}=1,~{}\forall{c\neq
y_{i},c\in[k]},\text{ and }~{}\forall i\in[n].$ (13)

Moreover, the features interpolate the simplex representation. That is,

$\displaystyle\mathbf{X}^{T}\hat{\mathbf{w}}_{c}=\mathbf{z}_{c},~{}\forall
c\in[k].$ (14)

For $k=2$ classes, it can be easily verified that Equation (12) reduces to the
condition in Equation (22) of [MNS+21] for the binary SVM. Compared to the
binary setting, the conclusion for the multiclass case is richer: provided
that Equation (12) holds, we show that not only are all data points support
vectors, but also, they satisfy a set of simplex OvA-type constraints as
elaborated above. The proof of Equation (14) is particularly subtle and
involved: unlike in the binary case, it does _not_ follow directly from a
complementary slackness condition on the dual of the multiclass SVM. A key
technical contribution that we provide to remedy this issue is a novel
reparameterization of the SVM dual. The complete proof of Theorem 1 and this
reparameterization is provided in Section 6.1.

We make a few additional remarks on the interpretation of Equation (14).

First, our proof shows a somewhat stronger conclusion: when Equation (12)
holds, the multiclass SVM solutions $\hat{\mathbf{w}}_{c},c\in[k]$ are same as
the solutions to the following _simplex OvA-type classifier_ (cf. Equation
(8)):

$\displaystyle\min_{\mathbf{w}_{c}}~{}\frac{1}{2}\|\mathbf{w}_{c}\|_{2}^{2}\qquad\text{sub.
to}~{}~{}~{}\mathbf{x}_{i}^{T}\mathbf{w}_{c}\begin{cases}\geq\frac{k-1}{k}&,y_{i}=c,\\\
\leq-\frac{1}{k}&,y_{i}\neq c,\end{cases}~{}~{}~{}\forall i\in[n],$ (15)

for all $c\in[k]$. We note that the OvA-type classifier above can also be
interpreted as a binary cost-sensitive SVM classifier [IMSV19] that enforces
the margin corresponding to all other classes to be $(k-1)$ times smaller
compared to the margin for the labeled class of the training data point. This
simplex structure is illustrated in Figure 2, which evaluates the solution of
the multiclass SVM on a $4$-class Gaussian mixture model with isotropic noise
covariance. The mean vectors are set to be mutually orthogonal and equal in
norm, with SNR $\|{\boldsymbol{\mu}}\|_{2}=0.2\sqrt{p}$. We also set $n=50$,
$p=1000$ to ensure sufficient effective overparameterization (in a sense that
will be formally defined in subsequent sections). Figure 2 shows the inner
product $\widehat{\mathbf{w}}_{c}^{T}\mathbf{x}$ drawn from 8 samples. These
inner products are consistent with the simplex OvA structure defined in
Equation (14), i.e., $\widehat{\mathbf{w}}_{c}^{T}\mathbf{x}_{i}=3/4$ if
$y_{i}=c$ and $\widehat{\mathbf{w}}_{c}^{T}\mathbf{x}_{i}=-1/4$ if $y_{i}\neq
c$.

Figure 2: Inner products
$\mathbf{W}_{\text{SVM}}\mathbf{x}_{c}\in\mathbb{R}^{4}$ for features
$\mathbf{x}_{i}$ that each belongs to the $c$-th class for $c\in[k]$ and $k=4$
total classes. The red lines correspond to the values $(k-1)/k=3/4$ and
$-1/k=-1/4$ of the simplex encoding described in Theorem 1. Observe that the
inner products $\mathbf{W}_{\text{SVM}}\mathbf{x}_{c}$ match with these
values, that is, Equation (10) holds.

Second, Equation (14) shows that when Equation (12) holds, then the multiclass
SVM solution $\mathbf{W}_{\text{SVM}}$ has the same classification error as
that of the minimum-norm interpolating solution. In other words, we can show
that the minimum-norm classifiers that interpolate the data with respect to
_either_ the one-hot representations $\mathbf{y}_{i}$ or the simplex
representations $\widetilde{\mathbf{y}}_{i}$ of (10) have identical
classification performance. This conclusion, stated as a corollary below,
drives our classification error analysis in Section 4.

######  Corollary 1 (SVM=MNI).

Under the same assumptions as in Theorem 1, and provided that the inequality
in Equation (12) holds, it holds that
$\mathbb{P}_{e|c}(\mathbf{W}_{\text{SVM}})=\mathbb{P}_{e|c}(\mathbf{W}_{\text{MNI}})$
for all $c\in[k]$. Thus, the total classification errors of both solutions are
equal:
$\mathbb{P}_{e}(\mathbf{W}_{\text{SVM}})=\mathbb{P}_{e}(\mathbf{W}_{\text{MNI}})$.

The corollary follows directly by combining Theorem 1 with the following lemma
applied with the choice $\alpha=1,\beta=-1/k$. We include a detailed proof
below for completeness.

######  Lemma 1.

For constants $\alpha>0,\beta$, consider the MNI-solution
${\mathbf{w}}^{\alpha,\beta}_{c}=\mathbf{X}(\mathbf{X}^{\top}\mathbf{X})^{+}(\alpha\mathbf{v}_{c}+\beta\boldsymbol{1}),c\in[k]$
corresponding to a target vector of labels
$\alpha\mathbf{v}_{c}+\beta\mathbf{1}_{n}$. Let
${\mathbb{P}}_{e|c}^{\alpha,\beta},c\in[k]$ be the class-conditional
classification errors of the classifier $\mathbf{w}^{\alpha,\beta}$. Then, for
any different set of constants $\alpha^{\prime}>0,\beta^{\prime}$, it holds
that
${\mathbb{P}}_{e|c}^{\alpha,\beta}={\mathbb{P}}_{e|c}^{\alpha^{\prime},\beta^{\prime}},\forall
c\in[k]$.

###### Proof.

Note that
$\mathbf{w}_{c}^{\alpha=1,\beta=0}=\mathbf{w}_{\text{MNI},c},c\in[k]$ and for
arbitrary $\alpha>0,\beta$, we have:
$\mathbf{w}_{c}^{\alpha,\beta}=\alpha\mathbf{w}_{\text{MNI},c}+\beta\mathbf{X}(\mathbf{X}^{\top}\mathbf{X})^{+}\mathbf{1}$.
Moreover, it is not hard to check that
$\mathbf{w}_{\text{MNI},c}^{\top}\mathbf{x}\leq\max_{j\neq
c}\mathbf{w}_{\text{MNI},j}^{\top}\mathbf{x}$ if and only if
$(\alpha{\mathbf{w}_{\text{MNI}}}_{c}+\mathbf{b})^{\top}\mathbf{x}\leq\max_{j\neq
c}(\alpha\mathbf{w}_{\text{MNI},j}+\mathbf{b})^{\top}\mathbf{x}$, for any
$\mathbf{b}\in\mathbb{R}^{p}$. The claim then follows by choosing
$\mathbf{b}=\beta\mathbf{X}(\mathbf{X}^{\top}\mathbf{X})^{+}\mathbf{1}$ and
noting that $\alpha>0,\beta$ were chosen arbitrarily. ∎

###  3.2 Connection to effective overparameterization

Theorem 1 establishes a deterministic condition that applies to any multiclass
separable dataset as long as the data matrix $\mathbf{X}$ is full-rank. In
this subsection, we show that the inequality in Equation (12) occurs with
high-probability under both the GMM and MLM data models provided that there is
sufficient effective overparameterization.

####  3.2.1 Gaussian mixture model

We assume an equal-energy, equal-prior setting as detailed below.

######  Assumption 1 (Equal energy/prior).

The mean vectors have equal energy and the priors are equal, i.e. we have
$\|{\boldsymbol{\mu}}\|_{2}:=\|{\boldsymbol{\mu}_{c}}\|_{2}$ and
$\pi_{c}=\pi=1/k$, for all $c\in[k]$.

######  Theorem 2.

Assume that the training set follows a multiclass GMM with
$\boldsymbol{\Sigma}=\mathbf{I}_{p}$, Assumption 1 holds, and the number of
training samples $n$ is large enough. There exist constants
$c_{1},c_{2},c_{3}>1$ and $C_{1},C_{2}>1$ such that Equation (12) holds with
probability at least $1-\frac{c_{1}}{n}-c_{2}ke^{-\frac{n}{c_{3}k^{2}}}$,
provided that

$\displaystyle p>C_{1}k^{3}n\log(kn)+n-1\quad\text{ and }\quad
p>C_{2}k^{1.5}n\sqrt{n}\|{\boldsymbol{\mu}}\|_{2}.$ (16)

Theorem 2 establishes a set of two conditions under which Equation (12) and
the conclusions of Theorem 1 hold, i.e.
$\mathbf{W}_{\text{SVM}}=\mathbf{W}_{\text{MNI}}$. The first condition
requires sufficient overparameterization $p=\Omega(k^{3}n\log(kn)),$ while the
second one requires that the signal strength is not too large. Intuitively, we
can understand these conditions as follows. Note that Equation (12) is
satisfied provided that the inverse Gram matrix
$(\mathbf{X}^{T}\mathbf{X})^{-1}$ is “close” to identity, or any other
positive-definite diagonal matrix. Recall from Equation (1) that
$\mathbf{X}=\mathbf{M}\mathbf{Y}+\mathbf{Q}=\sum_{j=1}^{k}\boldsymbol{\mu}_{j}\mathbf{v}_{j}^{T}+\mathbf{Q}$
where $\mathbf{Q}$ is a $p\times n$ standard Gaussian matrix. The first
inequality in Equation (16) (i.e. a lower bound on the data dimension $p$) is
sufficient for $(\mathbf{Q}^{T}\mathbf{Q})^{-1}$ to have the desired property;
the major technical challenge is that $(\mathbf{X}^{T}\mathbf{X})^{-1}$
involves additional terms that intricately depend on the label matrix
$\mathbf{Y}$ itself. Our key technical contribution is showing that these
extra terms do _not_ drastically change the desired behavior, provided that
the norms of the mean vectors (i.e. signal strength) are sufficiently small.
At a high-level we accomplish this with a recursive argument as follows.
Denote $\mathbf{X}_{0}=\mathbf{Q}$ and
$\mathbf{X}_{i}=\sum_{j=1}^{i}\boldsymbol{\mu}_{j}\mathbf{v}_{j}^{T}+\mathbf{Q}$
for $i\in[k]$. Then, at each stage $i$ of the recursion, we show how to bound
quadratic forms involving
$\big{(}\mathbf{X}_{i}^{T}\mathbf{X}_{i}\big{)}^{-1}$ using bounds established
previously at stage $i-1$ on quadratic forms involving
$\big{(}\mathbf{X}_{i-1}^{T}\mathbf{X}_{i-1}\big{)}^{-1}$. A critical property
for the success of our proof strategy is the observation that the rows of
$\mathbf{Y}$ are always orthogonal, that is,
$\mathbf{v}_{i}^{T}\mathbf{v}_{j}=0$, for $i\neq j$. The complete proof of the
theorem is given in Section 6.2.

We first present numerical results that support the conclusions of Theorem 2.
(In all our figures, we show averages over $100$ Monte-Carlo realizations, and
the error bars show the standard deviation at each point.) Figure 3(a) plots
the fraction of support vectors satisfying Equation (14) as a function of
training size $n$. We fix dimension $p=1000$ and class priors
$\pi=\frac{1}{k}$. To study how the outcome depends on the number of classes
$k$ and signal strength $\|{\boldsymbol{\mu}}\|_{2}$, we consider $k=4,7$ and
three equal-energy scenarios where $\forall
c\in[k]:\|{\boldsymbol{\mu}_{c}}\|_{2}=\|{\boldsymbol{\mu}}\|_{2}=\mu\sqrt{p}$
with $\mu=0.2,0.3,0.4$. Observe that smaller $\mu$ results in larger
proportion of support vectors for the same value of $n$. To verify our
theorem’s second condition (on the signal strength) in Equation (16), Figure
3(a) also plots the same set of curves over a re-scaled axis
$k^{1.5}n^{1.5}\|{\boldsymbol{\mu}}\|_{2}/p$. The six curves corresponding to
different settings nearly overlap in this new scaling, showing that the
condition is order-wise tight. In Figure 3(b), we repeat the experiment in
Figure 3(a) for different values of $k=3$ and $k=6$. Again, these curves
nearly overlap when the x-axis is scaled according to the second condition on
signal strength in Equation (16). We conjecture that our second condition on
the signal strength is tight up to an extra $\sqrt{n}$ factor, which we
believe is an artifact of the analysis444Support for this belief comes from
the fact that [WT21] shows that $p>C_{2}\|\boldsymbol{\mu}\|_{2}n$ is
sufficient for the SVM = interpolation phenomenon to occur in the case of GMM
and _binary_ classification.. We also believe that the $k^{3}$ factor in the
first condition can be relaxed slightly to $k^{2}$ (as in the MLM case
depicted in Figure 4, which considers a rescaled $x$-axis and shows exact
overlap of the curves for all values of $k$). Sharpening these dependences on
both $k$ and $n$ is an interesting direction for future work.

(a) $k=4$ and $7$

(b) $k=3$ and $6$

Figure 3: Fraction of training examples satisfying Equation (14) (also called
“support vectors”) in the GMM case. The error bars show the standard
deviation. Figure (a) considers $k=4$ and $7$, and Figure (b) considers $k=3$
and $6$. On the legend, “(4) 0.3” corresponds to $k=4$ and
$\|{\boldsymbol{\mu}}\|_{2}/\sqrt{p}=0.2$. Observe that the curves nearly
overlap when plotted versus $k^{1.5}n^{1.5}\|{\boldsymbol{\mu}}\|_{2}/p$ as
predicted by the second condition in Equation (16) of Theorem 2.

####  3.2.2 Multinomial logistic model

We now consider the MLM data model and anisotropic data covariance.
Explicitly, the eigendecomposition of the covariance matrix is given by
$\boldsymbol{\Sigma}=\sum_{i=1}^{p}\lambda_{i}\mathbf{u}_{i}\mathbf{u}_{i}^{T}$,
where $\boldsymbol{\lambda}=[\lambda_{1},\cdots,\lambda_{p}]$. We also define
the effective dimensions
$d_{2}:={\|\boldsymbol{\lambda}\|_{1}^{2}}/{\|\boldsymbol{\lambda}\|_{2}^{2}}$
and
$d_{\infty}:={\|\boldsymbol{\lambda}\|_{1}}/{\|\boldsymbol{\lambda}\|_{\infty}}$.
The following result contains sufficient conditions for the SVM and MNI
solutions to coincide.

######  Theorem 3.

Assume $n$ training samples following the MLM defined in (2). There exist
constants $c$ and $C_{1},C_{2}>1$ such that Equation (12) holds with
probability at least $(1-\frac{c}{n})$ provided that

$\displaystyle d_{\infty}>C_{1}k^{2}n\log(kn)\text{ and
}d_{2}>C_{2}(\log(kn)+n).$ (17)

In fact, the only conditions we require on the generated labels is conditional
independence.

For the isotropic case $\boldsymbol{\Sigma}=\mathbf{I}_{p}$, this implies that
Equation (12) holds with probability at least $(1-\frac{c}{n})$ provided that

$\displaystyle p>C_{1}k^{2}n\log({k}n).$ (18)

The sufficient conditions in Theorem 3 require that the spectral structure in
the covariance matrix $\boldsymbol{\Sigma}$ has sufficiently slowly decaying
eigenvalues (corresponding to sufficiently large $d_{2}$), and that it is not
too “spiky” (corresponding to sufficiently large $d_{\infty}$). When
$\boldsymbol{\Sigma}=\mathbf{I}_{p}$, the conditions reduce to sufficient
overparameterization. For the special case of $k=2$ classes, our conditions
reduce to those in [HMX21] for binary classification. The dominant dependence
on $k$, given by $k^{2}$, is a byproduct of the “unequal” margin in Equation
(10). Figure 4 empirically verifies the sharpness of this factor.

The proof of Theorem 3 is provided in Appendix B. We now numerically validate
our results in Theorem 3 in Figure 4, focusing on the isotropic case. We fix
$p=1000$, vary $n$ from $10$ to $100$ and the numbers of classes from $k=3$ to
$k=6$. We choose orthogonal mean vectors for each class with equal energy
$\|{\boldsymbol{\mu}}\|_{2}^{2}=p$. The left-most plot in Figure 4 shows the
fraction of support vectors satisfying Equation (14) as a function of $n$.
Clearly, smaller number of classes $k$ results in higher proportion of support
vectors with the desired property for the same number of measurements $n$. To
verify the condition in Equation (18), the middle plot in Figure 4 plots the
same curves over a re-scaled axis $k^{2}n\log(kn)/p$ (as suggested by Equation
(18)). We additionally draw the same curves over $kn\log(kn)/p$ in the right-
most plot of Figure 3. Note the overlap of the curves in the middle plot. We
now numerically validate our results in Theorem 3 in Figure 4, focusing on the
isotropic case. We fix $p=1000$, vary $n$ from $10$ to $100$ and the numbers
of classes from $k=3$ to $k=6$. We choose orthogonal mean vectors for each
class with equal energy $\|{\boldsymbol{\mu}}\|_{2}^{2}=p$. The left-most plot
in Figure 4 shows the fraction of support vectors satisfying Equation (14) as
a function of $n$. Clearly, smaller number of classes $k$ results in higher
proportion of support vectors with the desired property for the same number of
measurements $n$. To verify the condition in Equation (18), the middle plot in
Figure 4 plots the same curves over a re-scaled axis $k^{2}n\log({k}n)/p$ (as
suggested by Equation (18)). We additionally draw the same curves over
$kn\log({k}n)/p$ in the right-most plot of Figure 3. Note the overlap of the
curves in the middle plot.

Figure 4: Fraction of training examples satisfying equality in the simplex
label representation in Equation (14) in the MLM case with
$\boldsymbol{\Sigma}=\mathbf{I}_{p}$. The middle plot shows that the curves
overlap when plotted versus $k^{2}n\log({k}n)/p$ as predicted by Equation
(18).

###  3.3 Connection to Neural Collapse

In this section, we provide a distinct set of sufficient conditions on the
feature vectors that guarantee Equation (12), and hence the conclusions of
Theorem 1 hold. Interestingly, these sufficient conditions relate to the
recently discovered, so called _neural-collapse_ phenomenon that is
empirically observed in the training process of overparameterized deep nets
[PHD20] (see also e.g. [ZDZ+21, MPP20, HPD21, LS22, FHLS21a, FHLS21b, PL20b,
GHNK21] for several recent follow-ups).

######  Corollary 2.

Recall the notation in Theorem 1. Assume exactly balanced data, that is
$|\\{i:y_{i}=c\\}|=n/k$ for all $c\in[k]$. Also, assume that the following two
conditions hold:

  * •

Feature collapse (NC1): For each $c\in[k]$ and all $i\in[n]:y_{i}=c$, it holds
that $\mathbf{x}_{i}=\boldsymbol{\mu}_{c}$, where
$\boldsymbol{\mu}_{c}\triangleq\frac{k}{n}\sum_{i:y_{i}=c}\mathbf{x}_{i}$ is
the “mean” vector of the corresponding class.

  * •

Simplex ETF structure (NC2): The matrix of mean vectors
$\mathbf{M}:=[\boldsymbol{\mu}_{1},\ldots,\boldsymbol{\mu}_{k}]_{p\times k}$
is the matrix of a simplex Equiangular Tight Frame (ETF), i.e., for some
orthogonal matrix $\mathbf{U}_{p\times k}$ (with
$\mathbf{U}^{T}\mathbf{U}=\mathbf{I}_{k}$) and $\alpha\in\mathbb{R}$, it holds
that

$\displaystyle\mathbf{M}=\alpha\sqrt{\frac{k}{n}}\mathbf{U}\left(\mathbf{I}_{k}-\frac{1}{k}\mathbf{1}\mathbf{1}^{T}\right).$
(19)

Then, the sufficient condition (12) of Theorem 1 holds for the Gram matrix
$\mathbf{X}^{T}\mathbf{X}$.

###### Proof.

For simplicity, denote the sample size of each class as $m:=n/k$. Without loss
of generality under the corollary’s assumptions, let the columns of the
feature matrix $\mathbf{X}$ be ordered such that
$\mathbf{X}=[\mathbf{M},\mathbf{M},\ldots,\mathbf{M}]=\mathbf{M}\otimes\mathbf{1}_{m}^{T}$.
Accordingly, we have
$\mathbf{z}_{c}=\left(\mathbf{e}_{c}\otimes\mathbf{1}_{m}\right)-\frac{1}{k}\left(\mathbf{1}_{k}\otimes\mathbf{1}_{m}\right)$
where $\mathbf{e}_{c}$ is the $c$-th basis vector in $\mathbb{R}^{k}$. Then,
the feature Gram matrix is computed as

$\mathbf{X}^{T}\mathbf{X}=\left(\mathbf{M}^{T}\mathbf{M}\right)\otimes\left(\mathbf{1}_{m}\mathbf{1}_{m}^{T}\right)=\frac{{\alpha^{2}}}{m}\left(\mathbf{I}_{k}-\frac{1}{k}\mathbf{1}_{k}\mathbf{1}_{k}^{T}\right)\otimes\left(\mathbf{1}_{m}\mathbf{1}_{m}^{T}\right).$
(20)

Observe here that we can write
$\left(\mathbf{I}_{k}-\frac{1}{k}\mathbf{1}_{k}\mathbf{1}_{k}^{T}\right)=\mathbf{V}\mathbf{V}^{T}$
for $\mathbf{V}\in\mathbb{R}^{k\times(k-1)}$ having orthogonal columns (i.e.
$\mathbf{V}^{T}\mathbf{V}=\mathbf{I}_{k-1}$) and
$\mathbf{V}^{T}\mathbf{1}_{k}=\mathbf{0}_{k}$. Using this and the fact that
$(\mathbf{V}\mathbf{V}^{T})^{+}=(\mathbf{V}\mathbf{V}^{T})$, it can be checked
from (20) that

$(\mathbf{X}^{T}\mathbf{X})^{+}=\frac{1}{\alpha^{2}m}\left(\mathbf{I}_{k}-\frac{1}{k}\mathbf{1}_{k}\mathbf{1}_{k}^{T}\right)\otimes\left(\mathbf{1}_{m}\mathbf{1}_{m}^{T}\right).$
(21)

Putting things together, we get, for any $c\in[k]$, that

$\displaystyle(\mathbf{X}^{T}\mathbf{X})^{+}\mathbf{z}_{c}=\frac{1}{\alpha^{2}m}\left(\big{(}\mathbf{I}_{k}-\frac{1}{k}\mathbf{1}_{k}\mathbf{1}_{k}^{T}\big{)}\otimes\left(\mathbf{1}_{m}\mathbf{1}_{m}^{T}\right)\right)\left(\mathbf{e}_{c}\otimes\mathbf{1}_{m}\right)=\frac{1}{\alpha^{2}}\left(\mathbf{e}_{c}-\frac{1}{k}\mathbf{1}_{k}\right)\otimes\mathbf{1}_{m}=\frac{1}{\alpha^{2}}\mathbf{z}_{c}.$

Therefore, it follows immediately that

$\mathbf{z}_{c}\odot\mathbf{M}^{+}\mathbf{z}_{c}=\frac{1}{\alpha^{2}}\mathbf{z}_{c}\odot\mathbf{z}_{c}>\mathbf{0},$

as desired. This completes the proof. ∎

It might initially appear that the structure of the feature vectors imposed by
the properties NC1 and NC2 is too specific to be relevant in practice. To the
contrary, [PHD20] showed via a principled experimental study that these
properties occur at the last layer of overparameterized deep nets across
several different data sets and DNN architectures. Specifically, the
experiments conducted in [PHD20] suggest that training overparameterized deep
nets on classification tasks with CE loss in the absence of weight decay
(i.e., without explicit regularization) results in learned feature
representations in the final layer that converge555Here, “convergence” is with
respect to an increasing number of training epochs. Since the architecture is
overparameterized, it can perfectly separate the data. Hence, the training 0-1
error can be driven to zero. Nevertheless, training continues despite having
achieved zero 0-1 training error, since the CE loss continues to drop. [PHD20]
refers to this regime as the terminal phase of training (TPT). In sum, [PHD20]
show that neural collapse is observed in TPT. to the ETF structure described
by NC1 and NC2. Furthermore, it was recently shown in [GHNK21] that the neural
collapse phenomenon continues to occur when the last-layer features of a deep
net are trained with the recently proposed _supervised contrastive loss_ (SCL)
function [KTW+20] and a linear model is independently trained on these learned
last-layer features. (In fact, [GHNK21, KTW+20] showed that this self-
supervised procedure can yield superior generalization performance compared to
CE loss.)

To interpret Corollary 2 in view of these findings, consider the following
two-stage classification training process:

  * •

First, train (without weight-decay and continuing training beyond the
interpolation regime) the last-layer feature representations of an
overparameterized deep-net with either CE or SCL losses.

  * •

Second, taking as inputs those learned feature representations of the first
stage, train a linear multiclass classifier (often called the “head” of the
deep-net) with CE loss.

Then, from Corollary 2, the resulting classifier from this two-stage process
interpolates the simplex label representation, and the classification accuracy
is the same as if we had used the square loss in the second stage of the above
training process. Thus, our results lend strong theoretical justification to
the empirical observation that _square-loss and CE loss yield near-identical
performance in large-scale classification tasks[Rif02, RK04, HB20, PL20a]_.

##  4 Generalization bounds

In this section, we derive non-asymptotic bounds on the error of the MNI
classifier for data generated from both GMM and MLM.

###  4.1 Gaussian mixture model

We present classification error bounds under the additional assumption of
orthogonal means for ease of exposition — this can be relaxed with some
additional work as described in Appendix C.1.5.

######  Assumption 2 (Orthogonal means).

In addition to Assumption 1, we assume that the means are orthogonal, that is
$\boldsymbol{\mu}_{c}^{T}\boldsymbol{\mu}_{j}=0$, for all $c\neq j\in[k]$.

######  Theorem 4.

Let Assumption 2 and the condition in Equation (16) hold. Further assume
constants $C_{1},C_{2},C_{3}>1$ such that
$\big{(}1-\frac{C_{1}}{\sqrt{n}}-\frac{C_{2}n}{p}\big{)}\|{\boldsymbol{\mu}}\|_{2}>C_{3}\min\\{\sqrt{k},\sqrt{\log(2n)}\\}.$
Then, there exist additional constants $c_{1},c_{2},c_{3}$ and $C_{4}>1$ such
that both the MNI solution $\mathbf{W}_{\text{MNI}}$ and the multiclass SVM
solution $\mathbf{W}_{\text{SVM}}$ satisfy

$\displaystyle\mathbb{P}_{e|c}\leq(k-1)\exp{\left(-\|{\boldsymbol{\mu}}\|_{2}^{2}\frac{\left(\left(1-\frac{C_{1}}{\sqrt{n}}-\frac{C_{2}n}{p}\right)\|{\boldsymbol{\mu}}\|_{2}-C_{3}\min\\{\sqrt{k},\sqrt{\log(2n)}\\}\right)^{2}}{C_{4}\left(1+\frac{kp}{n\|{\boldsymbol{\mu}}\|_{2}^{2}}\right)}\right)}$
(22)

with probability at least $1-\frac{c_{1}}{n}-c_{2}ke^{-\frac{n}{c_{3}k^{2}}}$,
for every $c\in[k]$. Moreover, the same bound holds for the total
classification error $\mathbb{P}_{e}$.

For large enough $n$, Theorem 4 reduces to the results in [WT21] when $k=2$
(with slightly different constants). There are two major challenges in the
proof of Theorem 4, which is presented in Appendix C.1. First, in contrast to
the binary case the classification error does _not_ simply reduce to bounding
correlations between vector means $\boldsymbol{\mu}_{c}$ and their estimators
$\hat{\mathbf{w}}_{c}$. Second, just as in the proof of Theorem 2, technical
complications arise from the multiple mean components in the training data
matrix $\mathbf{X}$. We use a variant of the recursion-based argument
described in Section 6.2 to obtain our final bound.

###  4.2 Multinomial logistic model

In this section, we present our error analysis of the MNI classifier when data
is generated by the MLM. Importantly, for this case we consider more general
anisotropic structure in the covariance matrix
$\boldsymbol{\Sigma}:=\boldsymbol{U}\boldsymbol{\Lambda}\boldsymbol{U}^{\top}$.
We begin by carrying over the assumptions made from the binary-case analysis
in [MNS+21], beginning with a natural assumption of $s$-sparsity.

######  Assumption 3 ($s$-sparse class means).

We assume that all of the class means $\boldsymbol{\mu}_{c},c\in[k]$ are
$s$-sparse in the basis given by the eigenvectors of $\boldsymbol{\Sigma}$. In
other words, we have

$\displaystyle\boldsymbol{U}^{-1}\boldsymbol{\mu}_{c,j}=0\text{ if }j>s.$

This $s$-sparse assumption is also made in corresponding works on regression
(e.g. for the results for the anisotropic case in [HMRT19]) and shown to be
necessary in an approximate sense for consistency of MSE of the
minimum-$\ell_{2}$-norm interpolation arising from bias [TB20]. Next, we make
a special assumption of bi-level structure in the covariance matrix.

######  Assumption 4 (Bi-level ensemble).

We assume that the eigenvalues of the covariance matrix, given by
$\boldsymbol{\lambda}$, have a bilevel structure. In particular, our bi-level
ensemble is parameterized by $(n,m,q,r)$ where $m>1$, $0\leq r<1$ and
$0<q<{(m-r)}$.We set parameters $p=n^{m}$, $s=n^{r}$ and $a=n^{-q}$. Then, the
eigenvalues of the covariance matrix are given by

$\displaystyle\lambda_{j}=\begin{cases}\lambda_{H}:=\frac{ap}{s},\;1\leq j\leq
s\\\ \lambda_{L}:=\frac{(1-a)p}{p-s},\;\text{ otherwise.}\end{cases}$

We will fix $(m,q,r)$ and study the classification error as a function of $n$.
While the bi-level ensemble structure is not in principle needed for complete
statements of results, it admits particularly clean characterizations of
classification error rates as well as easily interpretable conditions for
consistency666See [MNS+21] for additional context on the bi-level ensemble and
examples of its manifestation in high-dimensional machine learning models..

Assumption 4 splits the covariance spectrum in a small set of large
eigenvalues ${\lambda}_{H}$ and the remaining large set of small eigenvalues
${\lambda}_{L}$. The bi-level ensemble is friendly to consistency of the MNI
solution for three reasons: a) the number of small eigenvalues is much larger
than the sample size, b) the ratio between the large-valued and small-valued
eigenvalues grows with the sample size $n$, and c) the number of large-valued
eigenvalues is exponentially small relative to the sample size $n$. Note that
condition a) facilitates benign overfitting of noise (as first pointed out in
the more general anisotropic case by [BLLT20]), while conditions b) and c)
facilitate signal recovery. To verify these conditions more quantitatively,
note that: a) the number of small eigenvalues is on the order of $p\gg n$, b)
the ratio between the large-valued and small-valued eigenvalues can be
verified to be on the order of $n^{m-q-r}$ which grows with $n$, and c) the
number of large-valued eigenvalues is equal to $s=n^{r}$, which is
exponentially smaller than $n$.

Finally, we imbue the above assumptions with an equal energy and orthogonality
assumption, as in the GMM case. These assumptions are specific to the
multiclass task, and effective subsume Assumption 3.

######  Assumption 5 (Equal energy and orthogonality).

We assume that the class means are equal energy, i.e.
$\|{\boldsymbol{\mu}}\|_{2}=1/\sqrt{\lambda_{H}}$ for all $c\in[k]$, and are
orthogonal, i.e. $\boldsymbol{\mu}_{i}^{\top}\boldsymbol{\mu}_{j}=0$ for all
$i\neq j\in[k]$. Together with Assumptions 3 and 4, a simple coordinate
transformation gives us

$\displaystyle\boldsymbol{\mu}_{c}$
$\displaystyle=\frac{1}{\sqrt{\lambda_{H}}}\boldsymbol{e}_{j_{c}}\;\text{ for
some $j_{c}\in[s]$, $j_{c}\neq j_{c^{\prime}}$ for all $c\neq
c^{\prime}\in[k]$, and }$ $\displaystyle\boldsymbol{\Sigma}$
$\displaystyle=\boldsymbol{\Lambda}$

without loss of generality. The normalization by the factor
$\frac{1}{\sqrt{\lambda_{H}}}$ is done to ensure that the signal strength is
equal to $1$, i.e. $\mathbb{E}[(\mathbf{x}^{\top}\boldsymbol{\mu}_{c})^{2}]=1$
for all $c\in[k]$.

Under these assumptions, we state our main result for the total classification
error of MLM. Our error bounds will be on the excess risk over and above the
Bayes error rate incurred by the optimal classifier
$\\{\widehat{\mathbf{w}}_{c}=\boldsymbol{\mu}_{c}\\}_{c\in[k]}$, which we
denote by $\mathbb{P}_{e,\mathsf{Bayes}}$.

######  Theorem 5.

Under Assumptions 4 and 5, there are universal constants $U,L_{1},L_{2}$ (that
may depend on $k$, but not $n$ or $p$) such that the total excess
classification error of $\mathbf{W}_{\text{MNI}}$ and
$\mathbf{W}_{\text{SVM}}$ under the MLM model is given by

$\displaystyle\mathbb{P}_{e}-\mathbb{P}_{e,\mathsf{Bayes}}$ $\displaystyle\leq
k^{2}\left(\frac{1}{2}-\frac{1}{\pi}\mathsf{tan}^{-1}(\mathsf{SNR}(n))\right),\;\text{
where }$ (23) $\displaystyle\mathsf{SNR}(n)$ $\displaystyle\geq
L_{1}\sqrt{\log n}\cdot n^{\frac{\min\\{(m-1),(1-r)\\}}{2}},\;0<q<(1-r)$
$\displaystyle\mathsf{SNR}(n)$ $\displaystyle\geq L_{2}\sqrt{\log n}\cdot
n^{\frac{\min\\{(m-1),(2q+r-1)\\}}{2}+(1-r)-q},\;q>(1-r).$

Keeping $k$ constant with respect to $n$, the scalings provided in Theorem 5
are identical to those for the binary case. These scalings also match the
lower bound provided by [MNS+21] in their dependence on $n$; therefore,
Theorem 5 is sharp in the regime where we keep $k$ constant with respect to
$n$. The proof of Theorem 5 is presented in Section 6.3.

##  5 Conditions for benign overfitting

Thus far, we have studied the classification error of the MNI classifier under
the GMM data model (Theorem 4), and shown equivalence of the multiclass SVM
and MNI solutions (Theorems 1, 2 and Corollary 1). Combining these results, we
now provide sufficient conditions under which the classification error of the
multiclass SVM solution (also of the MNI) approaches $0$ as the number of
parameters $p$ increases. First, we state our sufficient conditions for
harmless interpolation under the GMM model — these arise as a consequence of
Theorem 4, and the proof is provided in Appendix C.2.

######  Corollary 3.

Let the same assumptions as in Theorem 4 hold. Then, for finite number of
classes $k$ and sufficiently large sample size $n$, there exist positive
constants $c_{i}$’s and $C_{i}$’s $>1$, such that the multiclass SVM
classifier $\mathbf{W}_{\text{SVM}}$ in (7) satisfies the simplex
interpolation constraint in (14) and its total classification error approaches
$0$ as $\left(\frac{p}{n}\right)\to\infty$ with probability at least
$1-\frac{c_{1}}{n}-c_{2}ke^{-\frac{n}{c_{3}k^{2}}}$, provided that the
following conditions hold:

(1). When $\|{\boldsymbol{\mu}}\|_{2}^{2}>\frac{kp}{n}$,

$\displaystyle\frac{n}{C_{1}k}\|{\boldsymbol{\mu}}\|_{2}^{2}>p>\max\\{C_{2}k^{3}n\log(kn)+n-1,C_{3}k^{1.5}n^{1.5}\|{\boldsymbol{\mu}}\|_{2}\\}.$

(2). When $\|{\boldsymbol{\mu}}\|_{2}^{2}\leq\frac{kp}{n}$,

$\displaystyle
p>\max\\{C_{2}k^{3}n\log(kn)+n-1,C_{3}k^{1.5}n^{1.5}\|{\boldsymbol{\mu}}\|_{2},\frac{n\|{\boldsymbol{\mu}}\|_{2}^{2}}{k}\\},$
and $\displaystyle\|{\boldsymbol{\mu}}\|_{2}^{4}\geq
C_{4}\left(\frac{p}{n}\right)^{\alpha},\ \ \text{for}\ \alpha>1.$

When $n$ is fixed, the conditions for benign overfitting for
$\mathbf{W}_{\text{SVM}}$ become
$\|{\boldsymbol{\mu}}\|_{2}=\Theta(p^{\beta})\text{ for }\beta\in(1/4,1).$

Note that the upper bound on $\|{\boldsymbol{\mu}}\|_{2}$ comes from the
conditions that make SVM=MNI in Theorem 2; indeed, a distinct corollary of
Theorem 4 is that $\mathbf{W}_{\text{MNI}}$ overfits benignly with sufficient
signal strength $\|{\boldsymbol{\mu}}\|_{2}=\Omega(p^{1/4})$. We can compare
our result with the binary case [WT21]. When $k$ and $n$ are both finite, the
condition $\|{\boldsymbol{\mu}}\|_{2}=\Theta(p^{\beta})\text{ for
}\beta\in(1/4,1)$ is the same as the binary result.

Next, we state our sufficient and necessary conditions for harmless
interpolation under the MLM model — these arise directly from Equation (23) of
Theorem 5.

######  Corollary 4.

Let the same assumptions as in Theorem 5 hold. Then, for finite number of
classes $k$, the following parameters of the bilevel ensemble (Assumption 4)
ensure that the total classification error of $\mathbf{W}$ approaches $0$ as
$n\to\infty$:

$\displaystyle p>1\text{ and }q<(1-r)+\frac{(m-1)}{2}.$ (24)

Further, when $q>(1-r)$, the same conclusion holds for
$\mathbf{W}_{\text{MNI}}$.

We can again compare our result with the binary case [MNS+21]: when $k$ is
finite, the conditions in Equation (24) are identical to those for the binary
case. We also note that while Theorem 5 only provides an upper bound on MLM
classification error, [MNS+21] provides matching lower bounds for the binary
case that automatically apply to the MLM for the special case $k=2$.
Therefore, Equation (24) encapsulates sufficient and necessary conditions for
consistency when $k$ is constant with respect to $n$. Moreover, as [MNS+21]
show, the condition $q\leq(1-r)$ would be requirement for a corresponding
_regression_ task to generalize; consequently, Corollary 4 shows that
_multiclass classification can generalize even when regression does not._

We particularly note that, like in the binary case, Corollaries 3 and 4 imply
benign overfitting in regimes that cannot be explained by classical training-
data-dependent bounds based on the margin [SFBL98]. While the shortcomings of
such margin-based bounds in the highly overparameterized regime are well-
documented, e.g. [DR17], we provide a brief description here for completeness.
For the MLM, [MNS+21, Section 6] shows (for the binary case) that margin-based
bounds could only predict harmless interpolation if we had the significantly
stronger condition $q\leq(1-r)$ (also required for consistency of the
corresponding regression task). For the GMM, we verify here that the margin-
based bounds could only predict benign overfitting if we had the significantly
stronger condition $\beta\in(1/2,1)$ (see also [WT21, Section 9.1]): in the
regime where SVM = MNI, the margin is exactly equal to $1$. The margin-based
bounds (as given in, e.g. [BM03]), can be verified to scale as
$\mathcal{O}\left(\sqrt{\frac{\text{trace}(\boldsymbol{\Sigma}_{\text{un}})}{n||\boldsymbol{\Sigma}_{\text{un}}||_{2}}}\right)$
with high probability, where
$\boldsymbol{\Sigma}_{\text{un}}:=\mathbb{E}\left[\mathbf{x}\mathbf{x}^{\top}\right]$
denotes the unconditional covariance matrix under the GMM. In the case of the
binary GMM and isotropic noise covariance, an elementary calculation shows
that the spectrum of $\boldsymbol{\Sigma}_{\text{un}}$ is given by
$\begin{bmatrix}\|{\boldsymbol{\mu}}\|_{2}^{2}+1&1&\ldots&1\end{bmatrix}$;
plugging this into the above bound requires
$\|{\boldsymbol{\mu}}\|_{2}^{2}\gg\frac{p}{n}$ for the margin-based upper
bound to scale as $o(1)$. This clearly does not explain benign overfitting
when SVM = MNI, which we showed requires
$\|{\boldsymbol{\mu}}\|_{2}^{2}\leq\frac{p}{n}$.

(a) $k=4$

(b) $k=6$

Figure 5: Evolution of total classification error and fraction of support
vectors as a function of $p$ in the GMM case. Figure (a) considers $k=4$ and
Figure (b) considers $k=6$. We consider the energy of all class means to be
$\|{\boldsymbol{\mu}}\|_{2}=\mu\sqrt{p}$, where $\mu=0.2,0.3$ and $0.4$.
Observe that the total classification error approaches $0$ and the fraction of
support vectors approaches $1$ as $p$ gets larger.

Finally, we present numerical illustrations validating our benign overfitting
results in Corollary 3. In Figure 5(a), we set the number of classes $k=4$. To
guarantee sufficient overparameterization, we fix $n=40$ and vary $p$ from
$50$ to $1200$. We simulate $3$ different settings for the mean matrices: each
has orthogonal and equal-norm mean vectors
$\|{\boldsymbol{\mu}}\|_{2}=\mu\sqrt{p}$, with $\mu=0.2,0.3$ and $0.4$. Figure
5 plots the classification error as a function of $p$ for both MNI estimates
(solid lines) and multiclass SVM solutions (dashed lines). Different colors
correspond to different mean norms. The solid and dashed curves almost overlap
as predicted from our results in Section 3. We verify that as $p$ increases,
the classification error decreases towards zero. Observe that the fraction of
support vectors approaches $1$ as $p$ gets larger. Further, the classification
error goes to zero very fast when $\mu$ is large, but then the proportion of
support vectors increases at a slow rate. In contrast, when $\mu$ is small,
the proportion of support vectors increases fast, but the classification error
decreases slowly. Figure 5(b) uses the same setting as in Figure 5(a) except
for setting $k=6$ and $n=30$. Observe that the classification error continues
to go to zero and the proportion of support vectors continues to increase, but
both become slower as the number of classes is now greater.

##  6 Proofs of main results

In this section, we provide the proofs of Theorems 1, 2 and 5. The proof
techniques we developed for these results convey novel technical ideas that
also form the core of the rest of the proofs, which we defer to the Appendix.

###  6.1 Proof of Theorem 1

Argument sketch. We split the proof of the theorem in three steps. To better
convey the main ideas, we first outline the three steps in this paragraph
before discussing their details in the remaining of this section.

Step 1: The first key step to prove Theorem 1 is constructing a new
parameterization of the dual of the multiclass SVM, which we show takes the
following form:

$\displaystyle\max_{\boldsymbol{\beta}_{c}\in\mathbb{R}^{n},c\in[k]}~{}~{}~{}~{}\sum_{c\in[k]}{\boldsymbol{\beta}_{c}^{T}\mathbf{z}_{c}-\frac{1}{2}\|\mathbf{X}\boldsymbol{\beta}_{c}\|_{2}^{2}}$
(25) $\displaystyle~{}~{}~{}~{}~{}\text{sub.
to}~{}~{}~{}~{}~{}~{}~{}~{}\beta_{y_{i},i}=-\sum_{c\neq
y_{i}}\beta_{c,i},~{}\forall
i\in[n]\quad\text{and}\quad\boldsymbol{\beta}_{c}\odot\mathbf{z}_{c}\geq\mathbf{0},\forall
c\in[k].$

Here, for each $c\in[k]$ we let
$\boldsymbol{\beta}_{c}=[\beta_{c,1},\beta_{c,2},\ldots,\beta_{c,n}]\in\mathbb{R}^{n}.$
We also show by complementary slackness the following implication for any
_optimal_ $\beta^{*}_{c,i}$ in (25):

$\displaystyle
z_{c,i}\beta_{c,i}^{*}>0~{}\implies~{}(\hat{\mathbf{w}}_{y_{i}}-\hat{\mathbf{w}}_{c})^{T}\mathbf{x}_{i}=1.$
(26)

Thus, to prove Equation (13), it will suffice showing that
$z_{c,i}\beta_{c,i}^{*}>0,\forall i\in[n],c\in[k]$ provided that Equation (12)
holds.

Step 2: To do this, we prove that the _unconstrained_ maximizer in (25), that
is
$\hat{\boldsymbol{\beta}}_{c}=(\mathbf{X}^{T}\mathbf{X})^{+}\mathbf{z}_{c},~{}\forall
c\in[k]$ is feasible, and therefore optimal, in (25). Now, note that Equation
(12) is equivalent to $\mathbf{z}_{c}\odot\hat{\boldsymbol{\beta}}_{c}>0$;
thus, we have found that $\hat{\boldsymbol{\beta}}_{c},c\in[k]$ further
satisfies the $n$ strict inequality constraints in (26) which completes the
proof of the first part of the theorem (Equation (13)).

Step 3: Next, we outline the proof of Equation (14). We consider the simplex-
type OvA-classifier in (15). The proof has two steps. First, using similar
arguments to what was done above, we show that when Equation (12) holds, then
all the inequality constraints in (15) are active at the optimal. That is, the
minimizers $\mathbf{w}_{\text{OvA},c}$ of (15) satisfy Equation (14). Second,
to prove that Equation (14) is satisfied by the minimizers
$\hat{\mathbf{w}}_{c}$ of the multiclass SVM in (7), we need to show that
$\mathbf{w}_{\text{OvA},c}=\hat{\mathbf{w}}_{c}$ for all $c\in[k]$. We do this
by showing that, under Equation (12), the duals of (7) and (15) are
equivalent. By strong duality, the optimal costs of the primal problems are
also the same. Then, because a) the objective is the same for the two primals,
b) $\mathbf{w}_{\text{OvA},c}$ is feasible in (15) and c) (7) is strongly
convex, we can conclude with the desired.

Step 1: Key alternative parameterization of the dual. We start by writing the
dual of the multiclass SVM, repeated here for convenience:

$\displaystyle\min_{\mathbf{W}}\frac{1}{2}\lVert\mathbf{W}\rVert_{F}^{2}\quad\text{sub.
to}~{}~{}(\mathbf{w}_{y_{i}}-\mathbf{w}_{c})^{\top}\mathbf{x}_{i}\geq
1,~{}\forall i\in[n],c\in[k]:c\neq y_{i}.$ (27)

We have dual variables $\\{{\lambda}_{c,i}\\}$ for every
$i\in[n],c\in[k]:c\neq y_{i}$ corresponding to the constraints on the primal
form above. Then, the dual of the multiclass SVM takes the form

$\displaystyle\max_{{\lambda}_{c,i}\geq
0}~{}\sum_{i\in[n]}\Big{(}\sum_{\begin{subarray}{c}c\in[k]\\\ c\neq
y_{i}\end{subarray}}{\lambda}_{c,i}\Big{)}-\frac{1}{2}\sum_{c\in[k]}\Big{\|}{\sum_{i\in[n]:y_{i}=c}\Big{(}\sum_{\begin{subarray}{c}c^{\prime}\in[k]\\\
c^{\prime}\neq
y_{i}\end{subarray}}{\lambda}_{c^{\prime},i}\Big{)}\mathbf{x}_{i}-\sum_{i\in[n]:y_{i}\neq
c}{\lambda}_{c,i}\mathbf{x}_{i}}\Big{\|}_{2}^{2}.$ (28)

Let $\hat{\lambda}_{c,i},i\in[n],c\in[k]:c\neq y_{i}$ be maximizers in
Equation (28). By complementary slackness, we have

$\displaystyle\hat{\lambda}_{c,i}>0~{}\implies~{}(\hat{\mathbf{w}}_{y_{i}}-\hat{\mathbf{w}}_{c})^{\top}\mathbf{x}_{i}=1.$
(29)

Thus, it will suffice to prove that $\hat{\lambda}_{c,i}>0,\forall
i\in[n],c\in[k]:c\neq y_{i}$ provided that (12) holds.

It is challenging to work directly with Equation (28) because the variables
${\lambda}_{c,i}$ are coupled in the objective function. Our main idea is to
re-parameterize the dual objective in terms of new variables
$\\{\beta_{c,i}\\}$, which we define as follows for all $c\in[k]$ and
$i\in[n]$:

$\displaystyle\beta_{c,i}=\begin{cases}\sum_{c^{\prime}\neq
y_{i}}{\lambda}_{c^{\prime},i}&,y_{i}=c,\\\ -{\lambda}_{c,i}&,y_{i}\neq
c.\end{cases}$ (30)

For each $c\in[k]$, we denote
$\boldsymbol{\beta}_{c}=[\beta_{c,1},\beta_{c,2},\ldots,\beta_{c,n}]\in\mathbb{R}^{n}.$
With these, we show that the dual objective becomes

$\displaystyle\sum_{c\in[k]}\boldsymbol{\beta}_{c}^{\top}\mathbf{z}_{c}-\frac{1}{2}\sum_{c\in[k]}\Big{\|}\sum_{i\in[n]}\beta_{c,i}\mathbf{x}_{i}\Big{\|}_{2}^{2}=\sum_{c\in[k]}{\boldsymbol{\beta}_{c}^{\top}\mathbf{z}_{c}-\frac{1}{2}\|\mathbf{X}\boldsymbol{\beta}_{c}\|_{2}^{2}}.$
(31)

The equivalence of the quadratic term in $\boldsymbol{\beta}$ is
straightforward. To show the equivalence of the linear term in
$\boldsymbol{\beta}$, we denote
$A:=\sum_{i\in[n]}\Big{(}\sum_{\begin{subarray}{c}c\in[k],c\neq
y_{i}\end{subarray}}{\lambda}_{c,i}\Big{)}$, and simultaneously get

$\displaystyle A=\sum_{i\in[n]}\beta_{y_{i},i}\qquad\text{and}\qquad
A=\sum_{i\in[n]}\sum_{c\neq y_{i}}(-\beta_{c,i}),$

by the definition of variables $\\{\beta_{c,i}\\}$ in Equation (30). Then, we
have

$\displaystyle A=\frac{k-1}{k}\cdot A+\frac{1}{k}\cdot A$
$\displaystyle=\frac{k-1}{k}\sum_{i\in[n]}\beta_{y_{i},i}+\frac{1}{k}\sum_{i\in[n]}\sum_{c\neq
y_{i}}(-\beta_{c,i})$
$\displaystyle\stackrel{{\scriptstyle\mathsf{(i)}}}{{=}}\sum_{i\in[n]}\mathbf{z}_{y_{i},i}\beta_{y_{i},i}+\sum_{i\in[n]}\sum_{c\neq
y_{i}}\mathbf{z}_{c,i}\beta_{c,i}$
$\displaystyle=\sum_{i\in[n]}\sum_{c\in[k]}\mathbf{z}_{c,i}\beta_{c,i}=\sum_{c\in[k]}\boldsymbol{\beta}_{c}^{\top}\mathbf{z}_{c}.$

Above, inequality $(\mathsf{i})$ follows from the definition of
$\mathbf{z}_{c}$ in Equation (11), rewritten coordinate-wise as:

$\displaystyle z_{c,i}=\begin{cases}\frac{k-1}{k},&y_{i}=c,\\\
-\frac{1}{k},&y_{i}\neq c.\end{cases}$

Thus, we have shown that the objective of the dual can be rewritten in terms
of variables $\\{\beta_{c,i}\\}$. After rewriting the constraints in terms of
$\\{\beta_{c,i}\\}$, we have shown that the dual of the SVM (Equation (7)) can
be equivalently written as in Equation (25). Note that the first constraint in
(25) ensures consistency with the definition of $\boldsymbol{\beta}_{c}$ in
Equation (30). The second constraint guarantees the non-negativity constraint
of the original dual variables in (28), because we have

$\displaystyle\beta_{c,i}z_{c,i}=\frac{\lambda_{c,i}}{k}\text{ for all
}i\in[n],c\in[k]:c\neq y_{i}.$

Consequently, we have

$\displaystyle\beta_{c,i}z_{c,i}\geq
0~{}~{}\Longleftrightarrow~{}~{}\lambda_{c,i}\geq 0$ (32)

for all $c\in[k]$ and $i\in[n]:y_{i}\neq c$. In fact, the equivalence above
also holds with the inequalities replaced by strict inequalities. Also note
that the second constraint for $c=y_{i}$ yields
$\frac{k-1}{k}\sum_{c^{\prime}\neq y_{i}}\lambda_{c^{\prime},i}\geq 0$, which
is automatically satisfied when Equation (32) is satisfied. Thus, these
constraints are redundant.

Step 2: Proof of Equation (13). Define

$\hat{\boldsymbol{\beta}}_{c}:=(\mathbf{X}^{\top}\mathbf{X})^{+}\mathbf{z}_{c},~{}\forall
c\in[k].$

This specifies an _unconstrained_ maximizer in (25). We will show that this
unconstrained maximizer $\hat{\boldsymbol{\beta}}_{c},c\in[k]$ is feasible in
the constrained program in (25). Thus, it is in fact an optimal solution in
(25).

To prove this, we will first prove that $\hat{\boldsymbol{\beta}}_{c},c\in[k]$
satisfies the $n$ equality constraints in (25). For convenience, let
$\mathbf{g}_{i}\in\mathbb{R}^{n},i\in[n]$ denote the $i$-th row of
$(\mathbf{X}^{\top}\mathbf{X})^{+}$. Then, for the $i$-th element
$\hat{\beta}_{c,i}$ of $\hat{\boldsymbol{\beta}}_{c}$, it holds that
$\hat{\beta}_{c,i}=\mathbf{g}_{i}^{\top}\mathbf{z}_{c}$. Thus, for all
$i\in[n]$, we have

$\displaystyle\hat{\beta}_{y_{i},i}+\sum_{c\neq
y_{i}}\hat{\beta}_{c,i}=\mathbf{g}_{i}^{\top}\Big{(}\mathbf{z}_{y_{i}}+\sum_{c\neq
y_{i}}\mathbf{z}_{c}\Big{)}=\mathbf{g}_{i}^{\top}\Big{(}\sum_{c\in[k]}\mathbf{z}_{c}\Big{)}=0,$

where in the last equality we used the definition of $\mathbf{z}_{c}$ in (11)
and the fact that $\sum_{c\in[k]}\mathbf{v}_{c}=\mathbf{1}_{n}$, since each
column of the label matrix $\mathbf{Y}$ has exactly one non-zero element equal
to $1$. Second, since Equation (12) holds,
$\hat{\boldsymbol{\beta}}_{c},c\in[k]$ further satisfies the $n$ strict
inequality constraints in (25).

We have shown that the unconstrained maximizer is feasible in the constrained
program (25). Thus, we can conclude that it is also a global solution to the
latter. By Equation (32), we note that the original dual variables
$\\{\lambda_{c,i}\\}$ are all strictly positive. This completes the proof of
the first part of the theorem, i.e. the proof of Equation (13).

Step 3: Proof of Equation (14). To prove Equation (14), consider the following
OvA-type classifier: for all $c\in[k]$,

$\displaystyle\min_{\mathbf{w}_{c}}~{}\frac{1}{2}\|\mathbf{w}_{c}\|_{2}^{2}\qquad\text{sub.
to}~{}~{}~{}\mathbf{x}_{i}^{\top}\mathbf{w}_{c}\begin{cases}\geq\frac{k-1}{k},&y_{i}=c,\\\
\leq-\frac{1}{k},&y_{i}\neq c,\end{cases}~{}~{}~{}\forall i\in[n].$ (33)

To see the connection with Equation (14), note the condition for the
constraints in (33) to be active is exactly Equation (14). Thus, it suffices
to prove that the constraints of (33) are active under the theorem’s
assumptions. We work again with the dual of (33):

$\displaystyle\max_{\boldsymbol{\nu}_{c}\in\mathbb{R}^{k}}~{}~{}-\frac{1}{2}\|\mathbf{X}\boldsymbol{\nu}_{c}\|_{2}^{2}+\mathbf{z}_{c}^{\top}\boldsymbol{\nu}_{c}\qquad\text{sub.
to}~{}~{}~{}\mathbf{z}_{c}\odot\boldsymbol{\nu}_{c}\geq\mathbf{0}.$ (34)

Again by complementary slackness, the desired Equation (14) holds provided
that all dual constraints in (34) are strict at the optimal.

We now observe two critical similarities between (34) and (25): (i) the two
dual problems have the same objectives (indeed the objective in (25) is
separable over $c\in[k]$); (ii) they share the constraint
$\mathbf{z}_{c}\odot\boldsymbol{\nu}_{c}\geq\mathbf{0}$ /
$\mathbf{z}_{c}\odot\boldsymbol{\beta}_{c}\geq\mathbf{0}$. From this
observation, we can use the same argument as for (25) to show that when
Equation (12) holds, $\hat{\boldsymbol{\beta}}_{c}$ is optimal in (34).

Now, let $\rm{OPT}_{\eqref{eq:k-svm-square}}$ and
$\rm{OPT}^{c}_{\eqref{eq:sym-cs-svm}}$ be the optimal costs of the multiclass
SVM in (27) and of the simplex-type OvA-SVM in (33) parameterized by
$c\in[k]$. Also, denote $\rm{OPT}_{\eqref{eq:k-svm-dual-beta-sketch}}$ and
$\rm{OPT}^{c}_{\eqref{eq:sym-cs-svm-dual}},c\in[k]$ the optimal costs of their
respective duals in (25) and (34), respectively. We proved above that

$\displaystyle\rm{OPT}_{\eqref{eq:k-svm-dual-beta-
sketch}}=\sum_{c\in[k]}\rm{OPT}^{c}_{\eqref{eq:sym-cs-svm-dual}}.$ (35)

Further let
$\mathbf{W}_{\text{OvA}}=[\mathbf{w}_{\text{OvA},1},\ldots,\mathbf{w}_{\text{OvA},k}]$
be the optimal solution in the simplex-type OvA-SVM in (34). We have proved
that under Equation (12) $\mathbf{w}_{\text{OvA},c}$ satisfies the constraints
in (33) with equality, that is
$\mathbf{X}^{\top}\mathbf{w}_{\text{OvA},c}=\mathbf{z}_{c},~{}\forall
c\in[k]$. Thus, it suffices to prove that
$\mathbf{W}_{\text{OvA}}=\mathbf{W}_{\text{SVM}}$. By strong duality (which
holds trivially for (33) by Slater’s conditions), we get

$\displaystyle\rm{OPT}^{c}_{\eqref{eq:sym-cs-
svm}}=\rm{OPT}^{c}_{\eqref{eq:sym-cs-svm-dual}},~{}c\in[k]$
$\displaystyle\implies\sum_{c\in[k]}\rm{OPT}^{c}_{\eqref{eq:sym-cs-
svm}}=\sum_{c\in[k]}\rm{OPT}^{c}_{\eqref{eq:sym-cs-svm-dual}}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:duals_equality}}}{{\implies}}\sum_{c\in[k]}\rm{OPT}^{c}_{\eqref{eq:sym-
cs-svm}}=\rm{OPT}_{\eqref{eq:k-svm-dual-beta-sketch}}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:sym-cs-
svm}}}{{\implies}}\sum_{c\in[k]}\frac{1}{2}\|\mathbf{w}_{\text{OvA},c}\|_{2}^{2}=\rm{OPT}_{\eqref{eq:k-svm-
dual-beta-sketch}}.$ (36)

Again, by strong duality we get $\rm{OPT}_{\eqref{eq:k-svm-dual-beta-
sketch}}=\rm{OPT}_{\eqref{eq:k-svm-square}}.$ Thus, we have

$\sum_{c\in[k]}\frac{1}{2}\|\mathbf{w}_{\text{OvA},c}\|_{2}^{2}=\rm{OPT}_{\eqref{eq:k-svm-
square}}.$

Note also that $\mathbf{W}_{\text{OvA}}$ is feasible in (27) since

$\mathbf{X}^{\top}\mathbf{w}_{\text{OvA},c}=\mathbf{z}_{c},~{}\forall
c\in[k]\implies(\mathbf{w}_{\text{OvA},y_{i}}-\mathbf{w}_{\text{OvA},c})^{\top}\mathbf{x}_{i}=1,~{}\forall{c\neq
y_{i},c\in[k]},\text{ and }\forall i\in[n].$

Therefore, $\mathbf{W}_{\text{OvA}}$ is optimal in (27). Finally, note that
the optimization objective in (27) is strongly convex. Thus, it has a unique
minimum and therefore $\mathbf{W}_{\text{SVM}}=\mathbf{W}_{\text{OvA}}$ as
desired.

###  6.2 Proof of Theorem 2

In this section, we provide the proof of Theorem 2. First, we remind the
reader of the prescribed approach outlined in Section 3.2.1 and introduce some
necessary notation. Second, we present the key Lemma 2, which forms the
backbone of our proof. The proof of the lemma is rather technical and is
deferred to Appendix A.1 along with a series of auxiliary lemmas. Finally, we
end this section by showing how to prove Theorem 2 using Lemma 2.

Argument sketch and notation. We begin by presenting high-level ideas and
defining notation that is specific to this proof. For $c\in[k]$, we define

$\mathbf{A}_{c}:=(\mathbf{Q}+\sum_{j=1}^{c}\boldsymbol{\mu}_{j}\mathbf{v}_{j}^{T})^{T}(\mathbf{Q}+\sum_{j=1}^{c}\boldsymbol{\mu}_{j}\mathbf{v}_{j}^{T}).$

Recall that in the above, $\boldsymbol{\mu}_{j}$ denotes the $j^{th}$ class
mean of dimension $p$, and $\mathbf{v}_{j}$ denotes the $n$-dimensional
indicator that each training example is labeled as class $j$. Since we have
made an equal-energy assumption on the class means (Assumption 2), we will
denote $\|{\boldsymbol{\mu}}\|_{2}:=\|{\boldsymbol{\mu}_{c}}\|_{2}$ throughout
this proof as shorthand. Further, recall from Equation (1) that the feature
matrix can be expressed as $\mathbf{X}=\mathbf{M}\mathbf{Y}+\mathbf{Q}$, where
$\mathbf{Q}\in\mathbb{R}^{p\times n}$ is a standard Gaussian matrix. Thus, we
have

$\displaystyle\mathbf{X}^{T}\mathbf{X}=\mathbf{A}_{k}\qquad\text{and}\qquad\mathbf{Q}^{T}\mathbf{Q}=\mathbf{A}_{0}.$

As discussed in Section 3.2.1, our goal is to show that the inverse Gram
matrix $\mathbf{A}_{k}^{-1}$ is “close” to a positive definite diagonal
matrix. Indeed, in our new notation, the desired inequality in Equation (12)
becomes

$\displaystyle z_{ci}\mathbf{e}_{i}^{T}\mathbf{A}_{k}^{-1}\mathbf{z}_{c}>0,\ \
\text{for \ all}\ \ c\in[k]~{}~{}\text{and}~{}i\in[n].$ (37)

The major challenge in showing inequality (37) is that
$\mathbf{A}_{k}=(\mathbf{Q}+\sum_{j=1}^{k}\boldsymbol{\mu}_{j}\mathbf{v}_{j}^{T})^{T}(\mathbf{Q}+\sum_{j=1}^{k}\boldsymbol{\mu}_{j}\mathbf{v}_{j}^{T})$
involves multiple mean components through the sum
$\sum_{j=1}^{c}\boldsymbol{\mu}_{j}\mathbf{v}_{j}^{T}$. This makes it
challenging to bound quadratic forms involving the Gram matrix
$\mathbf{A}_{k}^{-1}$ directly. Instead, our idea is to work recursively
starting from bounding quadratic forms involving $\mathbf{A}_{0}^{-1}$.
Specifically, we denote
$\mathbf{P}_{1}=\mathbf{Q}+\boldsymbol{\mu}_{1}\mathbf{v}_{1}^{T}$ and derive
the following recursion on the
$\mathbf{A}_{0},\mathbf{A}_{1},\ldots,\mathbf{A}_{k}$ matrices:

$\displaystyle\mathbf{A}_{1}$
$\displaystyle=\mathbf{P}_{1}^{T}\mathbf{P}_{1}=\mathbf{A}_{0}+\begin{bmatrix}\|{\boldsymbol{\mu}}\|_{2}\mathbf{v}_{1}&\mathbf{Q}^{T}\boldsymbol{\mu}_{1}&\mathbf{v}_{1}\end{bmatrix}\begin{bmatrix}\|{\boldsymbol{\mu}}\|_{2}\mathbf{v}_{1}^{T}\\\
\mathbf{v}_{1}^{T}\\\ \boldsymbol{\mu}_{1}^{T}\mathbf{Q}\end{bmatrix},$
$\displaystyle\mathbf{A}_{2}$
$\displaystyle=(\mathbf{P}_{1}+\boldsymbol{\mu}_{2}\mathbf{v}_{2}^{T})^{T}(\mathbf{P}_{1}+\boldsymbol{\mu}_{2}\mathbf{v}_{2}^{T})=\mathbf{A}_{1}+\begin{bmatrix}\|{\boldsymbol{\mu}}\|_{2}\mathbf{v}_{2}&\mathbf{P}_{1}^{T}\boldsymbol{\mu}_{2}&\mathbf{v}_{2}\end{bmatrix}\begin{bmatrix}\|{\boldsymbol{\mu}}\|_{2}\mathbf{v}_{2}^{T}\\\
\mathbf{v}_{2}^{T}\\\ \boldsymbol{\mu}_{2}^{T}\mathbf{P}_{1}\end{bmatrix},$
(38)

and so on, until $\mathbf{A}_{k}$ (see Appendix E.1 for the complete
expressions for the recursion). Using this trick, we can exploit bounds on
quadratic forms involving $\mathbf{A}_{0}^{-1}$ to obtain bounds for quadratic
forms involving $\mathbf{A}_{1}^{-1}$, and so on until $\mathbf{A}_{k}^{-1}$.

There are two key ideas behind this approach. First, we will show how to use a
leave-one-out argument and the Matrix Inversion Lemma to express (recursively)
the quadratic form $\mathbf{e}_{i}^{T}\mathbf{A}_{k}^{-1}\mathbf{z}_{c}$ in
(37) in terms of simpler quadratic forms, which are more accessible to bound
directly. For later reference, we define these auxiliary forms here. Let
$\mathbf{d}_{c}:=\mathbf{Q}^{T}\boldsymbol{\mu}_{c}$, for $c\in[k]$ and define
the following quadratic forms involving $\mathbf{A}_{c}^{-1}$ for
$c,j,m\in[k]$ and $i\in[n]$:

$\displaystyle s_{mj}^{(c)}$
$\displaystyle:=\mathbf{v}_{m}^{T}\mathbf{A}_{c}^{-1}\mathbf{v}_{j},$
$\displaystyle t_{mj}^{(c)}$
$\displaystyle:=\mathbf{d}_{m}^{T}\mathbf{A}_{c}^{-1}\mathbf{d}_{j},$
$\displaystyle h_{mj}^{(c)}$
$\displaystyle:=\mathbf{v}_{m}^{T}\mathbf{A}_{c}^{-1}\mathbf{d}_{j},$ (39)
$\displaystyle g_{ji}^{(c)}$
$\displaystyle:=\mathbf{v}_{j}^{T}\mathbf{A}_{c}^{-1}\mathbf{e}_{i},$
$\displaystyle f_{ji}^{(c)}$
$\displaystyle:=\mathbf{d}_{j}^{T}\mathbf{A}_{c}^{-1}\mathbf{e}_{i}.$

For convenience, we refer to terms above as _quadratic forms of order $c$_ or
_the $c$-th order quadratic forms_, where $c$ indicates the corresponding
superscript. A complementary useful observation facilitating our approach is
the observation that the class label indicators are orthogonal by definition,
i.e. $\mathbf{v}_{i}^{T}\mathbf{v}_{j}=0$, for $i,j\in[k]$. (This is a
consequence of the fact that any training data point has a unique label and we
are using here one-hot encoding.) Thus, the newly added mean component
$\boldsymbol{\mu}_{c+1}\mathbf{v}_{c+1}^{T}$ is orthogonal to the already
existing mean components included in the matrix $\mathbf{A}_{c}$ (see Equation
(38)). Consequently, we will see that adding new mean components will only
slightly change the magnitude of these these quadratic forms as $c$ ranges
from $0$ to $k$.

Identifying and bounding quadratic forms of high orders. Recall the desired
inequality (37). We can equivalently write the definition of $\mathbf{z}_{c}$
in Equation (11) as

$\displaystyle\mathbf{z}_{c}=\frac{k-1}{k}\mathbf{v}_{c}+\sum_{j\neq
c}\left(-\frac{1}{k}\right)\mathbf{v}_{j}=\tilde{z}_{c(c)}\mathbf{v}_{c}+\sum_{j\neq
c}\tilde{z}_{j(c)}\mathbf{v}_{j},$ (40)

where we denote

$\displaystyle\tilde{z}_{j(c)}=\begin{cases}-\frac{1}{k},~{}~{}\text{if}~{}~{}j\neq
c\\\ \frac{k-1}{k},~{}~{}\text{if}~{}~{}j=c\end{cases}.$

Note that by this definition, we have $\tilde{z}_{y_{i}(c)}:=z_{ci}$. This
gives us

$\displaystyle z_{ci}\mathbf{e}_{i}^{T}\mathbf{A}_{k}^{-1}\mathbf{z}_{c}$
$\displaystyle=z_{ci}^{2}\mathbf{e}_{i}^{T}\mathbf{A}_{k}^{-1}\mathbf{v}_{y_{i}}+\sum_{j\neq
y_{i}}z_{ci}\tilde{z}_{j(c)}\mathbf{e}_{i}^{T}\mathbf{A}_{k}^{-1}\mathbf{v}_{j},$
$\displaystyle=z_{ci}^{2}g_{y_{i}i}^{(k)}+\sum_{j\neq
y_{i}}z_{ci}\tilde{z}_{j(c)}g_{ji}^{(k)}.$ (41)

Note that this expression (Equation (41)) involves the $k$-th order quadratic
forms $g_{ji}^{(k)}=\mathbf{e}_{i}^{T}\mathbf{A}_{k}^{-1}\mathbf{v}_{j}$. For
each such form, we use the matrix inversion lemma to leave the $j$-th mean
component in $\mathbf{A}_{k}$ out and express it in terms of the leave-one-out
versions of quadratic forms that we defined in (39), as below (see Appendix
E.1 for a detailed derivation):

$\displaystyle
g_{ji}^{(k)}=\mathbf{e}_{i}^{T}\mathbf{A}_{k}^{-1}\mathbf{v}_{j}=\frac{(1+h_{jj}^{(-j)})g_{ji}^{(-j)}-s_{jj}^{(-j)}f_{ji}^{(-j)}}{s_{jj}^{(-j)}(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{jj}^{(-j)})+(1+h_{jj}^{(-j)})^{2}}\,.$
(42)

Specifically, above we defined
$s_{jj}^{(-j)}:=\mathbf{v}_{j}^{T}\mathbf{A}^{-1}_{-j}\mathbf{v}_{j}$, where
$\mathbf{A}_{-j}$ denotes the version of the Gram matrix $\mathbf{A}_{k}$ with
the $j$-th mean component left out. The quadratic forms $h_{jj}^{(-j)}$,
$f_{ji}^{(-j)}$, $g_{ji}^{(-j)}$ and $t_{jj}^{(-j)}$ are defined similarly in
view of Equation (39).

Specifically, to see how these “leave-one-out” quadratic forms relate directly
to the forms in Equation (39), note that it suffices in (42) to consider the
case where $j=k$. Indeed, observe that when $j\neq k$ we can simply change the
order of adding mean components, described in Equation (38), so that the
$j$-th mean component is added last. On the other hand, when $j=k$ the leave-
one-out quadratic terms in (42) involve the Gram matrix $\mathbf{A}_{k-1}$.
Thus, they are equal to the quadratic forms of order $k-1$, given by
$s_{kk}^{(k-1)},t_{kk}^{(k-1)}$, $h_{kk}^{(k-1)}$, $g_{ki}^{(k-1)}$ and
$f_{ki}^{(k-1)}$.

The following technical lemma bounds all of these quantities and its use is
essential in the proof of Theorem 2. Its proof, which is deferred to Appendix
A, relies on the recursive argument outlined above: We start from the
quadratic forms of order $0$ building up all the way to the quadratic forms of
order $k-1$.

######  Lemma 2 (Quadratic forms of high orders).

Let Assumption 1 hold and further assume that $p>Ck^{3}n\log(kn)+n-1$ for
large enough constant $C>1$ and large $n$. There exist constants $c_{i}$’s and
$C_{i}$’s $>1$ such that the following bounds hold for every $i\in[n]$ and
$j\in[k]$ with probability at least
$1-\frac{c_{1}}{n}-c_{2}ke^{-\frac{n}{c_{3}k^{2}}}$,

$\displaystyle\frac{C_{1}-1}{C_{1}}\cdot\frac{n}{kp}\leq$ $\displaystyle
s_{jj}^{(-j)}\leq\frac{C_{1}+1}{C_{1}}\cdot\frac{n}{kp},$ $\displaystyle
t_{jj}^{(-j)}\leq$
$\displaystyle\frac{C_{2}n\|{\boldsymbol{\mu}}\|_{2}^{2}}{p},$
$\displaystyle-\tilde{\rho}_{n,k}\frac{C_{3}n\|{\boldsymbol{\mu}}\|_{2}}{\sqrt{k}p}\leq$
$\displaystyle
h_{jj}^{(-j)}\leq\tilde{\rho}_{n,k}\frac{C_{3}n\|{\boldsymbol{\mu}}\|_{2}}{\sqrt{k}p},$
$\displaystyle|f_{ji}^{(-j)}|\leq$
$\displaystyle\frac{C_{4}\sqrt{n}\|{\boldsymbol{\mu}}\|_{2}}{p},$
$\displaystyle g_{ji}^{(-j)}\geq$
$\displaystyle\left(1-\frac{1}{C_{5}}\right)\frac{1}{p},~{}~{}\text{for}~{}j=y_{i},$
$\displaystyle|g_{ji}^{(-j)}|\leq$
$\displaystyle\frac{1}{C_{6}k^{2}p},~{}~{}\text{for}~{}j\neq y_{i},$

where $\tilde{\rho}_{n,k}=\min\\{1,\sqrt{{\log(2n)}/{k}}\\}.$ Observe that the
bounds stated in the lemma hold for any $j\in[k]$ and the bounds themselves
are independent of $j$.

Completing the proof of Theorem 2. We now show how to use Lemma 2 to complete
the proof of the theorem. Following the second condition in the statement of
Theorem 2, we define

$\displaystyle\epsilon_{n}:=\frac{k^{1.5}n\sqrt{n}\|{\boldsymbol{\mu}}\|_{2}}{p}\leq\tau,$
(43)

where $\tau$ is a sufficiently small positive constant, the value of which
will be specified later in the proof. First, we will show that the denominator
of Equation (42) is strictly positive on the event where Lemma 2 holds. We
define

${\det}_{-j}:=s_{jj}^{(-j)}(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{jj}^{(-j)})+(1+h_{jj}^{(-j)})^{2}.$

By Lemma 2, the quadratic forms $s_{jj}^{(-j)}$ are of the same order
$\Theta\left(\frac{n}{kp}\right)$ for every $j\in[k]$. Similarly, we have
$t_{jj}^{(-j)}=\mathcal{O}\left(\frac{n}{p}\|{\boldsymbol{\mu}}\|_{2}^{2}\right)$
and
$|h_{jj}^{(-j)}|=\tilde{\rho}_{n,k}\mathcal{O}\left(\frac{\epsilon_{n}}{k^{2}\sqrt{n}}\right)$
for $j\in[k]$. Thus, we have

$\displaystyle\frac{n\|{\boldsymbol{\mu}}\|_{2}^{2}}{C_{1}kp}\left(1-\frac{C_{2}n}{p}\right)+\left(1-\frac{C_{3}\epsilon_{n}}{k^{2}\sqrt{n}}\right)^{2}\leq\text{det}_{-j}\leq\frac{C_{1}n\|{\boldsymbol{\mu}}\|_{2}^{2}}{kp}+\left(1+\frac{C_{3}\epsilon_{n}}{k^{2}\sqrt{n}}\right)^{2},$
(44)

with probability at least $1-\frac{c_{1}}{n}-c_{2}ke^{-\frac{n}{c_{3}k^{2}}}$,
for every $j\in[k]$. Here, we use the fact that $t_{jj}^{-j}\geq 0$ by the
positive semidefinite property of the leave-one-out Gram matrix
$\mathbf{A}_{-j}^{-1}$. Next, we choose $\tau$ in Equation (43) to be
sufficiently small so that $C_{3}\tau\leq 1/2$. Provided that $p$ is
sufficiently large compared to $n$, there then exist constants
$C_{1}^{\prime},C_{2}^{\prime}>0$ such that we have

$\displaystyle C_{1}^{\prime}\leq\frac{\det_{-m}}{\det_{-j}}\leq
C_{2}^{\prime},~{}~{}\text{for all}~{}j,m\in[k],$

with probability at least $1-\frac{c_{1}}{n}-c_{2}ke^{-\frac{n}{c_{3}k^{2}}}$.
Now, assume without loss of generality that $y_{i}=k$. Equation (44) shows
that there exists constant $c>0$ such that $\det_{-j}>c$ for all $j\in[k]$
with high probability provided that $p/n$ is large enough (guaranteed by the
first condition of the theorem). Hence, to make the right-hand-side of
Equation (41) positive, it suffices to show that the numerator will be
positive. Accordingly, we will show that

$\displaystyle
z_{ci}^{2}\big{(}(1+h_{kk}^{(-k)})g_{ki}^{(-k)}-s_{kk}^{(-k)}f_{ki}^{(-k)}\big{)}+Cz_{ci}\sum_{j\neq
k}\tilde{z}_{j}\big{(}(1+h_{jj}^{(-j)})g_{ji}^{(-j)}-s_{jj}^{(-j)}f_{ji}^{(-j)}\big{)}>0,$
(45)

for some $C>1$.

We can show by simple algebra that it suffices to consider the worst case of
$z_{ci}=-1/k$. To see why this is true, we consider the simpler term
$z_{ci}^{2}g_{y_{i}i}^{(-y_{i})}-|\sum_{j\neq
y_{i}}z_{ci}\tilde{z}_{j(c)}g_{ji}^{(-j)}|$. Clearly, Equation (45) is
positive only if the above quantity is also positive. Lemma 2 shows that when
$z_{ci}=-1/k$, then
$z_{ci}^{2}g_{y_{i}i}^{(-y_{i})}\geq\left(1-\frac{1}{C_{1}}\right)\frac{1}{k^{2}p}$
and $|z_{ci}\tilde{z}_{j(c)}g_{ji}^{(-j)}|\leq\frac{1}{C_{2}k^{3}p}$, for
$j\neq y_{i}$. Hence

$z_{ci}^{2}g_{y_{i}i}^{(-y_{i})}-|\sum_{j\neq
y_{i}}z_{ci}\tilde{z}_{j(c)}g_{ji}^{(-j)}|\geq\left(1-\frac{1}{C_{3}}\right)\frac{1}{k^{2}p}.$

Here, $z_{ci}=-1/k$ minimizes the lower bound
$z_{ci}^{2}g_{y_{i}i}^{(-y_{i})}-|\sum_{j\neq
y_{i}}z_{ci}\tilde{z}_{j(c)}g_{ji}^{(-j)}|$. To see this, we first drop the
positive common factor $|z_{ci}|$ in the equation above and get
$|z_{ci}|g_{y_{i}i}^{(-y_{i})}-|\sum_{j\neq
y_{i}}\tilde{z}_{j(c)}g_{ji}^{(-j)}|$. If we had $z_{ci}=-1/k$, then
$|\tilde{z}_{j(c)}|$ is either $(k-1)/k$ or $1/k$. In contrast, if we consider
$z_{ci}=(k-1)/k$, then we have $|\tilde{z}_{j(c)}|=1/k$ for all $j\neq y_{i}$
and so the term $|z_{ci}|g_{y_{i}i}^{(-y_{i})}-|\sum_{j\neq
y_{i}}\tilde{z}_{j(c)}g_{ji}^{(-j)}|$ is strictly larger.

Using this worst case, i.e. $z_{ci}=-1/k$, and the trivial inequality
$|\tilde{z}_{j(c)}|<1$ for $j\neq y_{i}$ together with the bounds for the
terms $s_{jj}^{(-j)},t_{jj}^{(-j)},h_{jj}^{(-j)}$ and $f_{ji}^{(-j)}$ derived
in Lemma 2 gives us

$\displaystyle~{}\eqref{eq:numeratorsum}$
$\displaystyle\geq\frac{1}{k^{2}}\left(\left(1-\frac{C_{1}\epsilon_{n}}{k^{2}\sqrt{n}}\right)\left(1-\frac{1}{C_{2}}\right)\frac{1}{p}-\frac{C_{3}\epsilon_{n}}{k^{1.5}n}\cdot\frac{n}{kp}\right)-k\cdot\frac{1}{C_{4}k}\left(\left(1+\frac{C_{5}\epsilon_{n}}{k^{2}\sqrt{n}}\right)\frac{1}{k^{2}p}-\frac{C_{6}\epsilon_{n}}{{k}^{1.5}n}\frac{n}{kp}\right)$
$\displaystyle\geq\frac{1}{k^{2}}\left(1-{\frac{1}{C_{9}}}-\frac{C_{10}\epsilon_{n}}{k^{2}\sqrt{n}}-\frac{C_{11}\epsilon_{n}}{k^{2}}-C_{12}\epsilon_{n}\right)\frac{1}{p}$
$\displaystyle\geq\frac{1}{k^{2}p}\left(1-\frac{1}{C_{9}}-C_{10}\tau\right),$
(46)

with probability at least $1-\frac{c_{1}}{n}-c_{2}ke^{-\frac{n}{c_{3}k^{2}}}$
for some constants $C_{i}$’s $>1$. Above, we recalled the definition of
$\epsilon_{n}$ and used from Lemma 2 that
$h_{jj}^{(-j)}\leq\tilde{\rho}_{n,k}\frac{C_{11}\epsilon_{n}}{k^{2}\sqrt{n}}$
and $|f_{ji}^{(-j)}|\leq\frac{C_{12}\epsilon_{n}}{k^{1.5}n}$ with high
probability. To complete the proof, we choose $\tau$ to be a small enough
constant to guarantee $C_{10}\tau<1-1/C_{9}$, and substitute this in Equation
(46) to get the desired condition of Equation (45).

###  6.3 Proof of Theorem 5

Challenges and notation. We begin by highlighting the two main non-
trivialities introduced in the analysis of the multiclass setting. We compare
them to the binary-error analysis in [MNS+21] and we sketch our approach to
each one of them:

  * •

_The multitude of signal vectors:_ The generative model for the MLM involves
$k$ distinct (high-dimensional) signal vectors
$\boldsymbol{\mu}_{1},\ldots,\boldsymbol{\mu}_{k}$, and the classification
error is a complicated functional of all $k$ _recovered_ signal vectors
(denoted by $\widehat{\mathbf{w}}_{1},\ldots,\widehat{\mathbf{w}}_{k}$
respectively). This functional has to be dealt with carefully compared to the
binary case, where there is only one signal vector. In particular, direct
plug-ins of the _survival signal_ and _contamination factor_ for each
recovered signal vector (here, we follow the terminology in [MVSS20]) do not
provide sufficiently sharp expressions of the multiclass classification error
to predict separation between classification-consistency and regression-
consistency. We circumvent this issue by directly analyzing survival and
contamination factors of the pairwise _difference signal_ between two classes,
and showing that they scale very similarly to the single-signal case.

  * •

_Covariate-dependent label noise in the MLM:_ The error analysis provided in
[MNS+21] critically leverages that the cross-correlation between the logit and
the binary label of a training example is lower bounded by a universal
positive constant. This is relatively straightforward to show when the
relationship between the logit and the label is one of _constant-label-noise_
where the event of label error is independent of the covariate. On the other
hand, the MLM involves label errors that are highly depend on the covariate,
and these cross-correlation terms need to be handled much more carefully. We
provide an elegant argument based on Stein’s lemma to handle the more complex
MLM-induced label noise.

Before proceeding we set up some notation for important quantities in the
analysis. Note that Assumption 5 directly implies that $\mu_{c,j_{c}}=1$ for
all $c\in[k]$. For any two classes $c_{1}\neq c_{2}$, we define the true
_difference signal vector_ as

$\displaystyle\boldsymbol{\Delta}_{c_{1},c_{2}}:=\boldsymbol{\mu}_{c_{1}}-\boldsymbol{\mu}_{c_{2}}=\mu_{c_{1},j_{c_{1}}}\boldsymbol{{e}}_{j_{c_{1}}}-\mu_{c_{2},j_{c_{2}}}\boldsymbol{{e}}_{j_{c_{2}}},$

where the last step follows from Assumption 5. Correspondingly, the recovered
difference signal vector is defined as
$\widehat{\boldsymbol{\Delta}}_{c_{1},c_{2}}:=\widehat{\mathbf{w}}_{c_{1}}-\widehat{\mathbf{w}}_{c_{2}}$.

Identifying the survival and contamination terms. We state and prove our main
lemma that characterizes the classification error in MLM as a function of
effective survival and contamination terms.

######  Lemma 3.

The excess classification risk is bounded by

$\displaystyle\mathbb{P}_{e}-\mathbb{P}_{e,\mathsf{Bayes}}\leq\sum_{c_{1}<c_{2}}\left(\frac{1}{2}-\frac{1}{\pi}\mathsf{tan}^{-1}\left(\frac{\mathsf{SU}(\widehat{\boldsymbol{\Delta}}_{c_{1},c_{2}},\boldsymbol{\Delta}_{c_{1},c_{2}})}{\mathsf{CN}(\widehat{\boldsymbol{\Delta}}_{c_{1},c_{2}},\boldsymbol{\Delta}_{c_{1},c_{2}})}\right)\right),$
(47)

where we define for any two classes $c_{1}\neq c_{2}\in[k]$:

$\displaystyle\mathsf{SU}(\widehat{\boldsymbol{\Delta}}_{c_{1},c_{2}},\boldsymbol{\Delta}_{c_{1},c_{2}})$
$\displaystyle:=\frac{\widehat{\boldsymbol{\Delta}}^{\top}{{}_{c_{1},c_{2}}}\boldsymbol{\Sigma}\boldsymbol{\Delta}{{}_{c_{1},c_{2}}}}{\|{\boldsymbol{\Sigma}^{1/2}\boldsymbol{\Delta}{{}_{c_{1},c_{2}}}}\|_{2}}\text{
and}$
$\displaystyle\mathsf{CN}(\widehat{\boldsymbol{\Delta}}_{c_{1},c_{2}},\boldsymbol{\Delta}_{c_{1},c_{2}})$
$\displaystyle:=\sqrt{\left(\widehat{\boldsymbol{\Delta}}{{}_{c_{1},c_{2}}}-\frac{\widehat{\boldsymbol{\Delta}}_{c_{1},c_{2}}^{\top}\boldsymbol{\Sigma}\boldsymbol{\Delta}_{c_{1},c_{2}}}{\|{\boldsymbol{\Sigma}^{1/2}\boldsymbol{\Delta}_{c_{1},c_{2}}}\|_{2}^{2}}\boldsymbol{\Delta}_{c_{1},c_{2}}\right)^{\top}\boldsymbol{\Sigma}\left(\widehat{\boldsymbol{\Delta}}_{c_{1},c_{2}}-\frac{\widehat{\boldsymbol{\Delta}}_{c_{1},c_{2}}^{\top}\boldsymbol{\Sigma}\boldsymbol{\Delta}_{c_{1},c_{2}}}{\|{\boldsymbol{\Sigma}^{1/2}\boldsymbol{\Delta}_{c_{1},c_{2}}}\|_{2}^{2}}\boldsymbol{\Delta}_{c_{1},c_{2}}\right)}.$

###### Proof.

We consider a fixed $\mathbf{x}$, and (following the notation in [TOS20]) the
$k$-dimensional vectors

$\displaystyle\mathbf{g}$
$\displaystyle:=\begin{bmatrix}\mathbf{x}^{\top}\widehat{\mathbf{w}}_{1}&\mathbf{x}^{\top}\widehat{\mathbf{w}}_{2}&\ldots&\mathbf{x}^{\top}\widehat{\mathbf{w}}_{k}\end{bmatrix}$
$\displaystyle\mathbf{h}$
$\displaystyle:=\begin{bmatrix}\mathbf{x}^{\top}\boldsymbol{\mu}_{1}&\mathbf{x}^{\top}\boldsymbol{\mu}_{2}&\ldots&\mathbf{x}^{\top}\boldsymbol{\mu}_{k}\end{bmatrix}$

Further, we define the multinomial logit variable $Y(\mathbf{h})$ such that

$\displaystyle\mathbb{P}\left[Y(\mathbf{h})=j\right]$
$\displaystyle=\frac{\exp\\{h_{j}\\}}{\sum_{m=1}^{k}\exp\\{h_{m}\\}}.$

Recall that $\mathbb{P}_{e}=\mathbb{P}\left({\arg\max}(\mathbf{g})\neq
Y(\mathbf{h})\right)$, where the probability is taken both over the fresh test
sample $\mathbf{x}$ and the randomness in the multinomial logit variable. We
note that for there to be a classification error conditioned on $\mathbf{x}$,
at least one of the following two events needs to hold: a)
${\arg\max}(\mathbf{g})\neq{\arg\max}(\mathbf{h})$, or b)
$Y(\mathbf{h})\neq{\arg\max}(\mathbf{h})$. To see this, note that if neither
a) nor b) held, we would have ${\arg\max}(\mathbf{g})=Y(\mathbf{h})$ and we
would not have a classification error conditional on the covariate being
$\mathbf{x}$. Thus, applying a union bound gives us

$\displaystyle\mathbb{P}_{e}$
$\displaystyle\leq\mathbb{P}_{e,0}+\mathbb{P}_{e,\mathsf{Bayes}}\text{ where
}$ $\displaystyle\mathbb{P}_{e,0}$
$\displaystyle:=\mathbb{P}\left({\arg\max}(\mathbf{g})\neq{\arg\max}(\mathbf{h})\right)\text{
and }$ $\displaystyle\mathbb{P}_{e,\mathsf{Bayes}}$
$\displaystyle:=\mathbb{P}\left({\arg\max}(\mathbf{h})\neq
Y(\mathbf{h})\right).$

Thus, it suffices to provide an upper bound on $\mathbb{P}_{e,0}$ as defined.
We note that for there to be an error of the form
${\arg\max}(\mathbf{g})\neq{\arg\max}(\mathbf{h})$, there needs to exist
indices $c_{1},c_{2}\in[k]$ (whose choice can depend on $\mathbf{x}$) such
that
$\mathbf{x}^{\top}\boldsymbol{\mu}_{c_{1}}\geq\mathbf{x}^{\top}\boldsymbol{\mu}_{c_{2}}$
but
$\mathbf{x}^{\top}\widehat{\mathbf{w}}_{c_{1}}<\mathbf{x}^{\top}\widehat{\mathbf{w}}_{c_{2}}$.
In other words, we have

$\displaystyle\mathbb{P}_{e,0}$
$\displaystyle\leq\mathbb{P}\left(\mathbf{x}^{\top}\boldsymbol{\mu}_{c_{1}}\geq\mathbf{x}^{\top}\boldsymbol{\mu}_{c_{2}}\text{
and
}\mathbf{x}^{\top}\widehat{\mathbf{w}}_{c_{1}}<\mathbf{x}^{\top}\widehat{\mathbf{w}}_{c_{2}}\text{
for some }c_{1}\neq c_{2}\right)$ $\displaystyle\leq\sum_{c_{1}\neq
c_{2}}\mathbb{P}\left(\mathbf{x}^{\top}\boldsymbol{\mu}_{c_{1}}\geq\mathbf{x}^{\top}\boldsymbol{\mu}_{c_{2}}\text{
and
}\mathbf{x}^{\top}\widehat{\mathbf{w}}_{c_{1}}<\mathbf{x}^{\top}\widehat{\mathbf{w}}_{c_{2}}\right)$
$\displaystyle=\sum_{c_{1}<c_{2}}\mathbb{P}\left(\mathbf{x}^{\top}\boldsymbol{\Delta}_{c_{1},c_{2}}\cdot\mathbf{x}^{\top}\widehat{\boldsymbol{\Delta}}_{c_{1},c_{2}}<0\right).$

Now, we consider whitened versions of the difference signal vectors:
$\boldsymbol{E}_{c_{1},c_{2}}:=\boldsymbol{\Sigma}^{1/2}\boldsymbol{\Delta}_{c_{1},c_{2}}$,
$\widehat{\boldsymbol{E}}_{c_{1},c_{2}}:=\boldsymbol{\Sigma}^{1/2}\widehat{\boldsymbol{\Delta}}_{c_{1},c_{2}}$.
We also define the generalized survival and contamination terms of the
difference signal vector as

$\displaystyle\mathsf{SU}(\widehat{\boldsymbol{\Delta}}_{c_{1},c_{2}},\boldsymbol{\Delta}_{c_{1},c_{2}})$
$\displaystyle:=\frac{\widehat{\boldsymbol{E}}_{c_{1},c_{2}}^{T}\boldsymbol{E}_{c_{1},c_{2}}}{\|\boldsymbol{E}_{c_{1},c_{2}}\|_{2}}$
$\displaystyle\mathsf{CN}(\widehat{\boldsymbol{\Delta}}_{c_{1},c_{2}},\boldsymbol{\Delta}_{c_{1},c_{2}})$
$\displaystyle:=\sqrt{\|\widehat{\boldsymbol{E}}_{c_{1},c_{2}}\|_{2}^{2}-\frac{\left(\widehat{\boldsymbol{E}}_{c_{1},c_{2}}^{T}\boldsymbol{E}_{c_{1},c_{2}}\right)^{2}}{\|\boldsymbol{E}_{c_{1},c_{2}}\|_{2}^{2}}}$

Recall that $\mathbf{x}\sim\mathcal{N}(\boldsymbol{0},\boldsymbol{\Sigma})$.
Then, the rotational invariance property of the Gaussian distribution and
Gaussian decomposition yields:

$\displaystyle\mathbb{P}\left(\mathbf{x}^{\top}\boldsymbol{\Delta}_{c_{1},c_{2}}\cdot\mathbf{x}^{\top}\widehat{\boldsymbol{\Delta}}_{c_{1},c_{2}}<0\right)$
$\displaystyle=\mathbb{P}_{\mathbf{G}\sim\mathcal{N}(\boldsymbol{0},\mathbf{I})}\left(\mathbf{G}^{\top}\boldsymbol{E}_{c_{1},c_{2}}\cdot\mathbf{G}^{\top}\widehat{\boldsymbol{E}}_{c_{1},c_{2}}<0\right)$
$\displaystyle=\mathbb{P}_{\begin{subarray}{c}G\sim\mathcal{N}(0,1)\\\
H\sim\mathcal{N}(0,1)\end{subarray}}\left(\|\boldsymbol{E}_{c_{1},c_{2}}\|_{2}G\cdot\left(\mathsf{SU}(\widehat{\boldsymbol{\Delta}}_{c_{1},c_{2}},\boldsymbol{\Delta}_{c_{1},c_{2}})G+\mathsf{CN}(\widehat{\boldsymbol{\Delta}}_{c_{1},c_{2}},\boldsymbol{\Delta}_{c_{1},c_{2}})H\right)<0\right)$
$\displaystyle=\mathbb{P}_{\begin{subarray}{c}G\sim\mathcal{N}(0,1)\\\
H\sim\mathcal{N}(0,1)\end{subarray}}\left(\left(\mathsf{SU}(\widehat{\boldsymbol{\Delta}}_{c_{1},c_{2}},\boldsymbol{\Delta}_{c_{1},c_{2}})\,G^{2}+\mathsf{CN}(\widehat{\boldsymbol{\Delta}}_{c_{1},c_{2}},\boldsymbol{\Delta}_{c_{1},c_{2}})\,H\,G\right)<0\right)$
$\displaystyle=\frac{1}{2}-\frac{1}{\pi}\mathsf{tan}^{-1}\left(\frac{\mathsf{SU}(\widehat{\boldsymbol{\Delta}}_{c_{1},c_{2}},\boldsymbol{\Delta}_{c_{1},c_{2}})}{\mathsf{CN}(\widehat{\boldsymbol{\Delta}}_{c_{1},c_{2}},\boldsymbol{\Delta}_{c_{1},c_{2}})}\right).$
(48)

For the last equality in Equation (48), we used the fact that the ratio $H/G$
of two independent standard normals follows the standard Cauchy distribution.
This completes the proof. ∎

Bounding the survival and contamination terms. Next, we provide
characterizations of
$\mathsf{SU}(\widehat{\boldsymbol{\Delta}}_{c_{1},c_{2}},\boldsymbol{\Delta}_{c_{1},c_{2}})$
and
$\mathsf{CN}(\widehat{\boldsymbol{\Delta}}_{c_{1},c_{2}},\boldsymbol{\Delta}_{c_{1},c_{2}})$.
We abbreviate these by $\mathsf{SU}_{c_{1},c_{2}}$ and
$\mathsf{CN}_{c_{1},c_{2}}$ respectively for brevity. These characterizations
address two new aspects of the MLM: the multiclass setting, and label noise
generated by the logistic model. We start with the characterization of
survival.

######  Lemma 4 (Survival terms).

There exist positive universal constants $L_{1},L_{2},U_{1},U_{2}$ such that

$\displaystyle\mathsf{SU}^{L}(n)$
$\displaystyle\leq\mathsf{SU}_{c_{1},c_{2}}(n)\leq\mathsf{SU}^{U}(n),\;\text{
where }$ $\displaystyle\mathsf{SU}^{L}(n)$
$\displaystyle:=\begin{cases}c(k)(1+L_{1}n^{q-(1-r)})^{-1},\;0<q<1-r\\\
c(k)L_{2}n^{(1-r)-q},\;q>1-r.\end{cases}$ $\displaystyle\mathsf{SU}^{U}(n)$
$\displaystyle:=\begin{cases}c(k)(1+U_{1}n^{q-(1-r)})^{-1},\;0<q<1-r\\\
c(k)U_{2}n^{(1-r)-q},\;q>1-r.\end{cases}$

Above, $c(k)>0$ is a fixed strictly positive constant that depends on $k$ but
not on $n$.

Lemma 4 constitutes a nontrivial extension of Lemma 11 of [MNS+21] to deal
with intricacies in the new pairwise-difference signal vector and the
covariate-dependent label noise induced by the MLM. Its proof is provided in
Appendix D.1.

Next, we provide an upper-bound characterization of contamination.

######  Lemma 5 (Contamination terms).

There exist universal positive constants $U_{3},U_{4}$ such that

$\displaystyle\mathsf{CN}_{c_{1},c_{2}}(n)\leq\mathsf{CN}^{U}(n):=\begin{cases}U_{3}\sqrt{\log
n}\cdot n^{-\frac{\min\\{m-1,1-r\\}}{2}},\;0<q<1-r\\\ U_{4}\sqrt{\log n}\cdot
n^{-\frac{\min\\{m-1,2q+r-q\\}}{2}},\;q>1-r.\end{cases}$

Lemma 5 is a relatively straightforward extension of Lemma 13 of [MNS+21], and
its proof is provided in Appendix D.2.

Plugging Lemmas 4 and 5 into Lemma 3 directly gives us the desired statement
of Theorem 5. ∎

##  7 Conclusion and future work

Our work provides, to the best of our knowledge, the first results
characterizing a) equivalence of loss functions, and b) generalization of
interpolating solutions in multiclass settings. Our fine-grained techniques
are tailored to high-dimensional linear models with Gaussian or independent
sub-Gaussian features. We believe the results will extend to kernel machines
and other nonlinear settings; formally showing these extensions is of
substantial interest. It is also interesting to investigate corresponding
lower bounds for our results — for example, studying the sharpness of our
conditions for equivalence of SVM to MNI in Section 3.2, analogous to [ASH21]
for the binary case. Also, we have limited attention to balanced datasets
throughout, i.e. we assumed that each class contains equal number of training
samples. We would like to investigate the effect of data imbalances on our
results extending our analysis to CE modifications tailored to imbalanced data
recently proposed in [CWG+19, MJR+20, KPOT21]. Finally, we have established a
tight connection of our findings regarding the geometry of support vectors
under overparameterization with the neural collapse phenomenon. Nevertheless,
many questions remain open towards better explaining what leads the learnt
feature representations of overparameterized to have the observed ETF
structure. It is a fascinating research direction further exploring the
geometry of learnt features and of support vectors in nonlinear settings.

## Acknowledgments

This work is partially supported by the NSF under Grant Number CCF-2009030, by
an NSERC Discovery Grant and by a grant from KAUST. Part of this work was done
when VM was visiting the Simons Institute for the Theory of Computing.

## References

  * [AKLZ20] Benjamin Aubin, Florent Krzakala, Yue Lu, and Lenka Zdeborová.  Generalization error in high-dimensional perceptrons: Approaching Bayes error with convex optimization.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 12199–12210. Curran Associates, Inc., 2020.
  * [ASH21] Navid Ardeshir, Clayton Sanford, and Daniel J Hsu.  Support vector machines and linear regression coincide with very high-dimensional features.  Advances in Neural Information Processing Systems, 34, 2021.
  * [ASS01] Erin L. Allwein, Robert E. Schapire, and Yoram Singer.  Reducing multiclass to binary: A unifying approach for margin classifiers.  Journal of Machine Learning Research, 1:113–141, September 2001\.
  * [BB99] Erin J Bredensteiner and Kristin P Bennett.  Multicategory classification by support vector machines.  In Computational Optimization, pages 53–79. Springer, 1999.
  * [BEH20] Anna Sergeevna Bosman, Andries Engelbrecht, and Mardé Helbig.  Visualising basins of attraction for the cross-entropy and the squared error neural network loss functions.  Neurocomputing, 400:113–136, 2020.
  * [Ber09] Dennis S Bernstein.  Matrix mathematics: theory, facts, and formulas.  Princeton university press, 2009.
  * [BG01] Arnaud Buhot and Mirta B Gordon.  Robust learning and generalization with support vector machines.  Journal of Physics A: Mathematical and General, 34(21):4377–4388, May 2001.
  * [BHMM19] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal.  Reconciling modern machine-learning practice and the classical bias–variance trade-off.  Proceedings of the National Academy of Sciences, 116(32):15849–15854, 2019.
  * [BHX20] Mikhail Belkin, Daniel Hsu, and Ji Xu.  Two models of double descent for weak features.  SIAM Journal on Mathematics of Data Science, 2(4):1167–1180, 2020\.
  * [BLLT20] Peter L. Bartlett, Philip M. Long, Gábor Lugosi, and Alexander Tsigler.  Benign overfitting in linear regression.  Proceedings of the National Academy of Sciences, 117(48):30063–30070, 2020.
  * [BM94] Kristin P. Bennett and O.L. Mangasarian.  Multicategory discrimination via linear programming.  Optimization Methods and Software, 3(1-3):27–39, 1994.
  * [BM03] Peter L. Bartlett and Shahar Mendelson.  Rademacher and Gaussian complexities: Risk bounds and structural results.  Journal of Machine Learning Research, 3:463–482, March 2003.
  * [CGB21] Yuan Cao, Quanquan Gu, and Mikhail Belkin.  Risk bounds for over-parameterized maximum margin classification on sub-Gaussian mixtures.  arXiv preprint arXiv:2104.13628, 2021.
  * [CKMY16] Corinna Cortes, Vitaly Kuznetsov, Mehryar Mohri, and Scott Yang.  Structured prediction theory based on factor graph complexity.  In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
  * [CL21] Niladri S Chatterji and Philip M Long.  Finite-sample analysis of interpolating linear classifiers in the overparameterized regime.  Journal of Machine Learning Research, 22(129):1–30, 2021.
  * [CLRS09] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.  Introduction to Algorithms, Third Edition.  The MIT Press, 3rd edition, 2009.
  * [CS02] Koby Crammer and Yoram Singer.  On the algorithmic implementation of multiclass kernel-based vector machines.  Journal of Machine Learning Research, 2:265–292, March 2002.
  * [CWG+19] Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma.  Learning imbalanced datasets with label-distribution-aware margin loss.  In Advances in Neural Information Processing Systems, pages 1567–1578, 2019.
  * [DB95] Thomas G. Dietterich and Ghulum Bakiri.  Solving multiclass learning problems via error-correcting output codes.  Journal of Artificial Intelligence Research, 2(1):263–286, January 1995.
  * [DCO20] Ahmet Demirkaya, Jiasi Chen, and Samet Oymak.  Exploring the role of loss functions in multiclass classification.  In 2020 54th Annual Conference on Information Sciences and Systems (CISS), pages 1–5, 2020.
  * [DKT21] Zeyu Deng, Abla Kammoun, and Christos Thrampoulidis.  A model of double descent for high-dimensional binary linear classification.  Information and Inference: A Journal of the IMA, April 2021.
  * [DL20] Oussama Dhifallah and Yue M Lu.  A precise performance analysis of learning with random features.  arXiv preprint arXiv:2008.11904, 2020.
  * [DOS99] Rainer Dietrich, Manfred Opper, and Haim Sompolinsky.  Statistical mechanics of support vector networks.  Physical Review Letters, 82:2975–2978, Apr 1999.
  * [DR17] Gintare Karolina Dziugaite and Daniel M Roy.  Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data.  arXiv preprint arXiv:1703.11008, 2017.
  * [EHN96] Heinz Werner Engl, Martin Hanke, and Andreas Neubauer.  Regularization of inverse problems, volume 375.  Springer Science & Business Media, 1996.
  * [F0̈2] Johannes Fürnkranz.  Round robin classification.  Journal of Machine Learning Research, 2:721–747, March 2002.
  * [FHLS21a] Cong Fang, Hangfeng He, Qi Long, and Weijie J Su.  Exploring deep neural networks via layer-peeled model: Minority collapse in imbalanced training.  Proceedings of the National Academy of Sciences, 118(43), 2021.
  * [FHLS21b] Cong Fang, Hangfeng He, Qi Long, and Weijie J Su.  Exploring deep neural networks via layer-peeled model: Minority collapse in imbalanced training.  Proceedings of the National Academy of Sciences, 118(43), 2021.
  * [GCOZ17] Krzysztof Gajowniczek, Leszek J. Chmielewski, Arkadiusz Orłowski, and Tomasz Ząbkowski.  Generalized entropy cost function in neural networks.  In Alessandra Lintas, Stefano Rovetta, Paul F.M.J. Verschure, and Alessandro E.P. Villa, editors, Artificial Neural Networks and Machine Learning – ICANN 2017, pages 128–136, Cham, 2017. Springer International Publishing.
  * [GHNK21] Florian Graf, Christoph Hofer, Marc Niethammer, and Roland Kwitt.  Dissecting supervised constrastive learning.  In International Conference on Machine Learning, pages 3821–3830. PMLR, 2021.
  * [GHST05] Thore Graepel, Ralf Herbrich, and John Shawe-Taylor.  Pac-bayesian compression bounds on the prediction error of learning algorithms for classification.  Machine Learning, 59(1-2):55–76, 2005.
  * [GJS+20] Mario Geiger, Arthur Jacot, Stefano Spigler, Franck Gabriel, Levent Sagun, Stéphane d’Ascoli, Giulio Biroli, Clément Hongler, and Matthieu Wyart.  Scaling description of generalization with number of parameters in deep learning.  Journal of Statistical Mechanics: Theory and Experiment, 2020(2):023401, February 2020.
  * [GLL+11] Pascal Germain, Alexandre Lacoste, François Laviolette, Mario Marchand, and Sara Shanian.  A pac-bayes sample-compression approach to kernel methods.  In ICML, 2011.
  * [HB20] Like Hui and Mikhail Belkin.  Evaluation of neural architectures trained with square loss vs cross-entropy in classification tasks.  arXiv preprint arXiv:2006.07322, 2020.
  * [HJ12] Roger A. Horn and Charles R. Johnson.  Matrix Analysis.  Cambridge University Press, USA, 2nd edition, 2012.
  * [HMRT19] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani.  Surprises in high-dimensional ridgeless least squares interpolation.  arXiv preprint arXiv:1903.08560, 2019.
  * [HMX21] Daniel Hsu, Vidya Muthukumar, and Ji Xu.  On the proliferation of support vectors in high dimensions.  In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 91–99. PMLR, 13–15 Apr 2021.
  * [HPD21] XY Han, Vardan Papyan, and David L Donoho.  Neural collapse under mse loss: Proximity to and dynamics on the central path.  arXiv preprint arXiv:2106.02073, 2021.
  * [Hua17] Hanwen Huang.  Asymptotic behavior of support vector machine for spiked population model.  Journal of Machine Learning Research, 18(45):1–21, 2017.
  * [HYS16] Le Hou, Chen-Ping Yu, and Dimitris Samaras.  Squared earth mover’s distance-based loss for training deep neural networks.  arXiv preprint arXiv:1611.05916, 2016.
  * [IMSV19] Arya Iranmehr, Hamed Masnadi-Shirazi, and Nuno Vasconcelos.  Cost-sensitive support vector machines.  Neurocomputing, 343:50–64, 2019.
  * [JT19] Ziwei Ji and Matus Telgarsky.  The implicit bias of gradient descent on nonseparable data.  In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 1772–1798, Phoenix, USA, 25–28 Jun 2019\. PMLR.
  * [KA21] Abla Kammoun and Mohamed-Slim Alouini.  On the precise error analysis of support vector machines.  IEEE Open Journal of Signal Processing, 2:99–118, 2021.
  * [KLS20] Dmitry Kobak, Jonathan Lomond, and Benoit Sanchez.  The optimal ridge penalty for real-world high-dimensional data can be zero or negative due to the implicit ridge regularization.  Journal of Machine Learning Research, 21(169):1–16, 2020.
  * [KP02] V. Koltchinskii and D. Panchenko.  Empirical Margin Distributions and Bounding the Generalization Error of Combined Classifiers.  The Annals of Statistics, 30(1):1 – 50, 2002.
  * [KPOT21] Ganesh Ramachandra Kini, Orestis Paraskevas, Samet Oymak, and Christos Thrampoulidis.  Label-imbalanced and group-sensitive classification under overparameterization.  Advances in Neural Information Processing Systems, 34, 2021.
  * [KS18] Himanshu Kumar and P. S. Sastry.  Robust loss functions for learning multi-class classifiers.  In 2018 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pages 687–692, 2018.
  * [KT21] Ganesh Ramachandra Kini and Christos Thrampoulidis.  Phase transitions for one-vs-one and one-vs-all linear separability in multiclass gaussian mixtures.  In ICASSP 2021 - 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 4020–4024, 2021.
  * [KTW+20] Prannay Khosla, Piotr Teterwak, Chen Wang, Aaron Sarna, Yonglong Tian, Phillip Isola, Aaron Maschinot, Ce Liu, and Dilip Krishnan.  Supervised contrastive learning.  Advances in Neural Information Processing Systems, 33:18661–18673, 2020.
  * [LDBK15] Yunwen Lei, Urun Dogan, Alexander Binder, and Marius Kloft.  Multi-class svms: From tighter data-dependent generalization bounds to novel algorithms.  In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
  * [LDZK19] Yunwen Lei, Ürün Dogan, Ding-Xuan Zhou, and Marius Kloft.  Data-dependent generalization bounds for multi-class classification.  IEEE Transactions on Information Theory, 65(5):2995–3021, 2019\.
  * [LLW04] Yoonkyung Lee, Yi Lin, and Grace Wahba.  Multicategory support vector machines.  Journal of the American Statistical Association, 99(465):67–81, 2004.
  * [Lol20] Panagiotis Lolas.  Regularization in high-dimensional regression and classification via random matrix theory.  arXiv preprint arXiv:2003.13723, 2020.
  * [LR21] Tengyuan Liang and Benjamin Recht.  Interpolating classifiers make few mistakes.  arXiv preprint arXiv:2101.11815, 2021.
  * [LS20] Tengyuan Liang and Pragya Sur.  A precise high-dimensional asymptotic theory for boosting and min-l1-norm interpolated classifiers.  arXiv preprint arXiv:2002.01586, 2020.
  * [LS22] Jianfeng Lu and Stefan Steinerberger.  Neural collapse under cross-entropy loss.  Applied and Computational Harmonic Analysis, 2022.
  * [Mau16] Andreas Maurer.  A vector-contraction inequality for rademacher complexities.  In Ronald Ortner, Hans Ulrich Simon, and Sandra Zilles, editors, Algorithmic Learning Theory, pages 3–17, Cham, 2016. Springer International Publishing.
  * [MJR+20] Aditya Krishna Menon, Sadeep Jayasumana, Ankit Singh Rawat, Himanshu Jain, Andreas Veit, and Sanjiv Kumar.  Long-tail learning via logit adjustment.  In International Conference on Learning Representations, 2020.
  * [MLC19] Xiaoyi Mai, Zhenyu Liao, and Romain Couillet.  A large scale analysis of logistic regression: Asymptotic performance and new insights.  In ICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3357–3361, 2019.
  * [MNS+21] Vidya Muthukumar, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel Hsu, and Anant Sahai.  Classification vs regression in overparameterized regimes: Does the loss function matter?  Journal of Machine Learning Research, 22(222):1–69, 2021.
  * [MO05] Dörthe Malzahn and Manfred Opper.  A statistical physics approach for the analysis of machine learning algorithms on real data.  Journal of Statistical Mechanics: Theory and Experiment, 2005(11):P11001–P11001, nov 2005.
  * [MPP20] Dustin G Mixon, Hans Parshall, and Jianzong Pi.  Neural collapse with unconstrained features.  arXiv preprint arXiv:2011.11619, 2020.
  * [MRSY19] Andrea Montanari, Feng Ruan, Youngtak Sohn, and Jun Yan.  The generalization error of max-margin linear classifiers: High-dimensional asymptotics in the overparametrized regime.  arXiv preprint arXiv:1911.01544, 2019.
  * [MVSS20] Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai.  Harmless interpolation of noisy data in regression.  IEEE Journal on Selected Areas in Information Theory, 2020.
  * [PGS13] Bernardo Ávila Pires, Mohammad Ghavamzadeh, and Csaba Szepesvári.  Cost-sensitive multiclass classification risk bounds.  In Proceedings of the 30th International Conference on International Conference on Machine Learning - Volume 28, ICML’13, page III–1391–III–1399. JMLR.org, 2013.
  * [PHD20] Vardan Papyan, X. Y. Han, and David L. Donoho.  Prevalence of neural collapse during the terminal phase of deep learning training.  Proceedings of the National Academy of Sciences, 117(40):24652–24663, 2020.
  * [PL20a] Tomaso Poggio and Qianli Liao.  Explicit regularization and implicit bias in deep network classifiers trained with the square loss.  arXiv preprint arXiv:2101.00072, 2020.
  * [PL20b] Tomaso Poggio and Qianli Liao.  Explicit regularization and implicit bias in deep network classifiers trained with the square loss.  arXiv preprint arXiv:2101.00072, 2020.
  * [PS16] Bernardo Ávila Pires and Csaba Szepesvári.  Multiclass classification calibration functions.  arXiv preprint arXiv:1609.06385, 2016.
  * [RDS+15] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al.  Imagenet large scale visual recognition challenge.  International journal of computer vision, 115(3):211–252, 2015\.
  * [Rif02] Ryan Michael Rifkin.  Everything old is new again: a fresh look at historical approaches in machine learning.  PhD thesis, MaSSachuSettS InStitute of Technology, 2002.
  * [RK04] Ryan Rifkin and Aldebaro Klautau.  In defense of one-vs-all classification.  Journal of Machine Learning Research, 5:101–141, 2004.
  * [RV+13] Mark Rudelson, Roman Vershynin, et al.  Hanson-wright inequality and sub-gaussian concentration.  Electronic Communications in Probability, 18, 2013.
  * [SAH19] Fariborz Salehi, Ehsan Abbasi, and Babak Hassibi.  The impact of regularization on high-dimensional logistic regression.  In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
  * [SAH20] Fariborz Salehi, Ehsan Abbasi, and Babak Hassibi.  The performance analysis of generalized margin maximizers on separable data.  In International Conference on Machine Learning, pages 8417–8426. PMLR, 2020.
  * [SC19] Pragya Sur and Emmanuel J Candès.  A modern maximum-likelihood theory for high-dimensional logistic regression.  Proceedings of the National Academy of Sciences, 116(29):14516–14525, 2019.
  * [SFBL98] Robert E Schapire, Yoav Freund, Peter Bartlett, and Wee Sun Lee.  Boosting the margin: A new explanation for the effectiveness of voting methods.  The Annals of Statistics, 26(5):1651–1686, 1998.
  * [SHN+18] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro.  The implicit bias of gradient descent on separable data.  Journal of Machine Learning Research, 19(1):2822–2878, 2018.
  * [TB07] Ambuj Tewari and Peter L Bartlett.  On the consistency of multiclass classification methods.  Journal of Machine Learning Research, 8(36):1007–1025, 2007.
  * [TB20] Alexander Tsigler and Peter L Bartlett.  Benign overfitting in ridge regression.  arXiv preprint arXiv:2009.14286, 2020.
  * [TOS20] Christos Thrampoulidis, Samet Oymak, and Mahdi Soltanolkotabi.  Theoretical insights into multiclass classification: A high-dimensional asymptotic view.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 8907–8920. Curran Associates, Inc., 2020.
  * [TPT20] Hossein Taheri, Ramtin Pedarsani, and Christos Thrampoulidis.  Sharp asymptotics and optimal performance for inference in binary models.  In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 3739–3749. PMLR, 26–28 Aug 2020.
  * [TPT21] Hossein Taheri, Ramtin Pedarsani, and Christos Thrampoulidis.  Fundamental limits of ridge-regularized empirical risk minimization in high dimensions.  In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 2773–2781. PMLR, 13–15 Apr 2021.
  * [Vap13] Vladimir Vapnik.  The nature of statistical learning theory.  Springer science & business media, 2013.
  * [Wai19] Martin J Wainwright.  High-dimensional statistics: A non-asymptotic viewpoint, volume 48.  Cambridge University Press, 2019.
  * [WT21] Ke Wang and Christos Thrampoulidis.  Binary classification of gaussian mixtures: Abundance of support vectors, benign overfitting and regularization.  arXiv preprint arXiv:2011.09148, 2021.
  * [WW98] Jason Weston and Chris Watkins.  Multi-class support vector machines.  Technical report, Citeseer, 1998.
  * [ZBH+17] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals.  Understanding deep learning requires rethinking generalization.  In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
  * [ZDZ+21] Zhihui Zhu, Tianyu Ding, Jinxin Zhou, Xiao Li, Chong You, Jeremias Sulam, and Qing Qu.  A geometric analysis of neural collapse with unconstrained features.  Advances in Neural Information Processing Systems, 34, 2021.
  * [Zha04] Tong Zhang.  Statistical behavior and consistency of classification methods based on convex risk minimization.  The Annals of Statistics, 32(1):56–85, 2004.