###### Contents

  1. 1 Introduction
    1. 1.1 Our Contributions
    2. 1.2 Related Work
    3. 1.3 Organization
  2. 2 Problem setting
    1. 2.1 Data models
    2. 2.2 Data separability
    3. 2.3 Classification error
    4. 2.4 Classification algorithms
  3. 3 Equivalence of solutions and geometry of support vectors
    1. 3.1 A key deterministic condition
    2. 3.2 Connection to effective overparameterization
      1. 3.2.1 Gaussian mixture model
      2. 3.2.2 Multinomial logistic model
    3. 3.3 Connection to Neural Collapse
  4. 4 Generalization bounds
    1. 4.1 Gaussian mixture model
    2. 4.2 Multinomial logistic model
  5. 5 Conditions for benign overfitting
  6. 6 Proofs of main results
    1. 6.1 Proof of Theorem 1
    2. 6.2 Proof of Theorem 2
    3. 6.3 Proof of Theorem 5
  7. 7 Conclusion and future work
  8. A Lemmas used in the proof of Theorem 2
    1. A.1 Auxiliary Lemmas
    2. A.2 Proof of Lemma 2
      1. A.2.1 Proof outline
      2. A.2.2 Proofs for 1-st order quadratic forms in Equation (51)
      3. A.2.3 Completing the proof for k-th order quadratic forms
    3. A.3 Proofs of Auxiliary lemmas
      1. A.3.1 Proof of Lemma 6
      2. A.3.2 Proof of Lemma 8
      3. A.3.3 Proof of Lemma 9
  9. B Proof of Theorem 3
  10. C Classification error proofs
    1. C.1 Proof of Theorem 4
      1. C.1.1 Proof strategy and notations
      2. C.1.2 Proof of Equation (67)
      3. C.1.3 Completing the proof
      4. C.1.4 Proof of Equation (66)
      5. C.1.5 Extensions to not-orthogonal means
    2. C.2 Proof of Corollary 3
  11. D Lemmas used in error analysis of MLM
    1. D.1 Proof of Lemma 4
    2. D.2 Proof of Lemma 5
  12. E Recursive formulas for higher-order quadratic forms
    1. E.1 Expressions for 1-st order quadratic forms
  13. F One-vs-all SVM
    1. F.1 Gaussian mixture model
    2. F.2 Multinomial logistic model

##  Appendix A Lemmas used in the proof of Theorem 2

###  A.1 Auxiliary Lemmas

In this section, we state a series of auxiliary lemmas that we use to prove
Lemma 2. The following result shows concentration of the norms of the label
indicators $\mathbf{v}_{c},c\in[k]$ under the equal-priors assumption
(Assumption 1). Intuitively, in this balanced setting there are $\Theta(n/k)$
samples for each class; hence, $\Theta(n/k)$ non-zeros (in fact, 1’s) in each
label indicator vector $\mathbf{v}_{c}$.

######  Lemma 6.

Under the setting of Assumption 1, there exist large constants $C_{1},C_{2}>0$
such that the event

$\displaystyle\mathcal{E}_{v}:=\Big{\\{}\left(1-\frac{1}{C_{1}}\right)\frac{n}{k}\leq\|{\mathbf{v}_{c}}\|_{2}^{2}\leq\left(1+\frac{1}{C_{1}}\right)\frac{n}{k}~{},~{}\forall
c\in[k]\Big{\\}},$ (49)

holds with probability at least $1-2ke^{-\frac{n}{C_{2}k^{2}}}$.

Next, we provide bounds on the “base case” $0$-th order quadratic forms that
involve the Gram matrix $\mathbf{A}_{0}^{-1}$. We do this in three lemmas
presented below. The first Lemma 7 follows by a direct application of [WT21,
Lemma 4 and 5]. The only difference is that we keep track of throughout the
proof is the scaling of $\mathcal{O}(1/k)$ arising from the multiclass case in
the $\mathbf{v}_{j}$’s. For instance, the bound of the term
$h_{mj}^{(0)}:=\mathbf{v}_{m}^{T}\mathbf{A}_{0}^{-1}\mathbf{d}_{j}$ involves a
term $\tilde{\rho}_{n,k}=\min\\{1,\sqrt{\log(2n)/k}\\}$ compared to the binary
case. The other two Lemmas 8 and 9 are proved in Section A.3.

######  Lemma 7 ($0$-th order Quadratic forms, Part I).

Under the event $\mathcal{E}_{v}$, there exist constants $c_{i}$’s and
$C_{i}$’s $>1$ such that the following bounds hold with probability at least
$1-c_{1}ke^{-\frac{n}{c_{2}}}$.

$\displaystyle t_{jj}^{(0)}$
$\displaystyle\leq\frac{C_{1}n\|{\boldsymbol{\mu}}\|_{2}^{2}}{p}~{}~{}\text{for
all}~{}j\in[k],$ $\displaystyle|h_{mj}^{(0)}|$
$\displaystyle\leq\tilde{\rho}_{n,k}\frac{C_{2}n\|{\boldsymbol{\mu}}\|_{2}}{\sqrt{k}p}~{}~{}\text{for
all}~{}m,j\in[k],$ $\displaystyle|t_{mj}^{(0)}|$
$\displaystyle\leq\frac{C_{3}n\|{\boldsymbol{\mu}}\|_{2}^{2}}{p}~{}~{}\text{for
all}~{}m\neq j\in[k],$ $\displaystyle\|{\mathbf{d}_{j}}\|_{2}^{2}$
$\displaystyle\leq C_{4}n\|{\boldsymbol{\mu}}\|_{2}^{2}~{}~{}\text{for
all}~{}j\in[k],$ $\displaystyle\max_{i\in[n]}|f_{ji}^{(0)}|$
$\displaystyle\leq\frac{C_{5}\sqrt{\log(2n)}\|{\boldsymbol{\mu}}\|_{2}}{p}~{}~{}\text{for
all}~{}j\in[k].$

To sharply characterize the forms $s_{ij}^{(0)}$ we need additional work,
particularly for the cross-terms where $i\neq j$. We will make use of
fundamental concentration inequalities on quadratic forms of inverse Wishart
matrices. The following lemma controls these quadratic forms, and shows in
particular that the $s_{ij}^{(0)}$ terms for $i\neq j$ are much smaller than
the corresponding terms $s_{jj}^{(0)}$. This sharp control of the cross-terms
is essential for several subsequent proof steps.

######  Lemma 8 ($0$-th order Quadratic forms, Part II).

Working on the event $\mathcal{E}_{v}$ defined in Equation (49), assume that
$p>Cn\log(kn)+n-1$ for large enough constant $C>1$ and large $n$. There exist
constants $C_{i}$’s $>1$ such that with probability at least
$1-\frac{C_{0}}{n}$, the following bound holds:

$\displaystyle\frac{C_{1}-1}{C_{1}}\cdot\frac{n}{kp}\leq$ $\displaystyle
s_{jj}^{(0)}\leq\frac{C_{1}+1}{C_{1}}\cdot\frac{n}{kp},~{}~{}\text{for}~{}j\in[k],$
$\displaystyle-\frac{C_{2}+1}{C_{2}}\cdot\frac{\sqrt{n}}{kp}\leq$
$\displaystyle
s_{ij}^{(0)}\leq\frac{C_{2}+1}{C_{2}}\cdot\frac{\sqrt{n}}{kp},~{}~{}\text{for}~{}i\neq
j\in[k].$

The proof of Lemma 8 for the cross terms with $i\neq j$ critically uses the
in-built orthogonality of the label indicator vectors
$\\{\mathbf{v}_{c}\\}_{c\in[k]}$. Finally, the following lemma controls the
quadratic forms $g_{ji}^{(0)}$.

######  Lemma 9 ($0$-th order Quadratic forms, Part III).

Working on the event $\mathcal{E}_{v}$ defined in Equation (49), given
$p>Ck^{3}n\log(kn)+n-1$ for a large constant $C$, there exist large enough
constants $C_{1},C_{2}$, such that with probability at least $1-\frac{2}{kn}$,
we have for every $i\in[n]$:

$\displaystyle\left(1-\frac{1}{C_{1}}\right)\frac{1}{p}\leq$ $\displaystyle
g_{(y_{i})i}^{(0)}\leq\left(1+\frac{1}{C_{1}}\right)\frac{1}{p},$
$\displaystyle-\frac{1}{C_{2}}\cdot\frac{1}{k^{2}p}\leq$ $\displaystyle
g_{ji}^{(0)}\leq\frac{1}{C_{2}}\cdot\frac{1}{k^{2}p},~{}~{}\text{for}~{}j\neq
y_{i}.$

###  A.2 Proof of Lemma 2

In this section, we provide the full proof of Lemma 2. We begin with a proof
outline.

####  A.2.1 Proof outline

As explained in Section 6.2, it suffices to consider the case where $j=k$,
since 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.
For concreteness, we will also fix $i\in[n]$, $y_{i}=k$ and define as
shorthand $m:=k-1$. These fixes are without loss of generality. The reason why
we fix $j=k$ and $m=k-1$ is that when we do the proof, we want to add the
$k-1$-th and $k$-th components last. This is for ease of reading and
understanding.

For the case $j=k$, the leave-one-out quadratic forms in Lemma 2 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)}$. We will proceed
recursively starting from the quadratic forms of order $1$ building up all the
way to the quadratic forms of order $k-1$. Specifically, starting from order
$1$, we will work on the event

$\displaystyle\mathcal{E}_{q}:=\\{\text{all the inequalities in
Lemmas~{}\ref{lem:ineqforazero},~{}\ref{lem:ineqforszero}~{}and~{}\ref{lem:ineqforgzero}
hold}\\},$ (50)

Further, we note that Lemma 9 shows that the bound for $g_{y_{i}i}^{(0)}$ is
different from the bound for $g_{ji}^{(0)}$ when $j\neq y_{i}$. We will show
the following set of upper and lower bounds:

$\displaystyle\begin{split}\left(\frac{C_{11}-1}{C_{11}}\right)\frac{n}{kp}&\leq
s_{kk}^{(1)}\leq\left(\frac{C_{11}+1}{C_{11}}\right)\frac{n}{kp},\\\
-\left(\frac{C_{12}+1}{C_{12}}\right)\frac{\sqrt{n}}{kp}&\leq
s_{mk}^{(1)}\leq\left(\frac{C_{12}+1}{C_{12}}\right)\frac{\sqrt{n}}{kp},\\\
t_{kk}^{(1)}&\leq\frac{C_{13}n\|{\boldsymbol{\mu}}\|_{2}^{2}}{p},\\\
|h_{mk}^{(1)}|&\leq\tilde{\rho}_{n,k}\frac{C_{14}n\|{\boldsymbol{\mu}}\|_{2}}{\sqrt{k}p},\\\
|t_{mk}^{(1)}|&\leq\frac{C_{15}n\|{\boldsymbol{\mu}}\|_{2}^{2}}{p},\\\
\|{\mathbf{d}_{k}}\|_{2}^{2}&\leq C_{16}n\|{\boldsymbol{\mu}}\|_{2}^{2},\\\
|f_{ki}^{(1)}|&\leq\frac{C_{17}\sqrt{n}\|{\boldsymbol{\mu}}\|_{2}}{p},\\\
\left(1-\frac{1}{C_{18}}\right)\frac{1}{p}&\leq
g_{(y_{i})i}^{(1)}\leq\left(1+\frac{1}{C_{18}}\right)\frac{1}{p},\text{ and
}\\\ -\frac{1}{C_{19}k^{2}p}&\leq
g_{mi}^{(1)}\leq\frac{1}{C_{19}k^{2}p}\end{split}$ (51)

with probability at least $1-\frac{c}{kn^{2}}$. Comparing the bounds on the
terms of order $1$ in Equation (51) with the terms in Lemmas 7, 8 and 9 of
order $0$, the key observation is that they are all at the same order. This
allows us to repeat the same argument to now bound corresponding terms of
order $2$, and so on until order $k-1$. Note that for each $j\in[k]$, we have
$n$ terms of the form $g_{ji}^{(1)}$, corresponding to each value of
$i\in[n]$. Thus, we will adjust the final probabilities by applying a union
bound over the $n$ training examples.

####  A.2.2 Proofs for 1-st order quadratic forms in Equation (51)

The proof makes repeated use of Lemmas 7, 8 and 9. In fact, we will throughout
condition on the event $\mathcal{E}_{q}$, defined in Equation (50), which
holds with probability at least
$1-\frac{c_{1}}{n}-c_{2}e^{-\frac{n}{c_{0}k^{2}}}$. Specifically, by Lemma 7
we have

$\displaystyle
h_{mj}^{(0)}\leq\tilde{\rho}_{n,k}\frac{C_{1}\epsilon_{n}}{k^{2}\sqrt{n}},\qquad\max_{i\in[n]}|f_{mi}^{(0)}|\leq\frac{C_{2}\epsilon_{n}}{k^{1.5}n},\quad\text{and}\quad\frac{s_{mj}^{(0)}}{s_{kk}^{(0)}}\leq\frac{C}{\sqrt{n}}\text{
for }m,j\neq k,$ (52)

where we recall from Equation (43) the notation
$\epsilon_{n}:=\frac{k^{1.5}n\sqrt{n}\|{\boldsymbol{\mu}}\|_{2}}{p}.$ Also,
recall that we choose $\epsilon_{n}\leq\tau$ for a sufficiently small constant
$\tau$.

In order to make use of Lemmas 7, 8 and 9, we need to relate the quantities of
interest to corresponding quadratic forms involving $\mathbf{A}_{0}$. We do
this recursively and make repeated use of the Woodbury identity. The
recursions are proved in Appendix E.1. We now provide the proofs for the
bounds on the terms in Equation (51) one-by-one.

Bounds on $s_{mk}^{(1)}$. By Equation (77) in Appendix E.1, we have

$\displaystyle s_{mk}^{(1)}$
$\displaystyle=s_{mk}^{(0)}-\frac{1}{\det_{0}}(\star)_{s}^{(0)},$ (53)

where we define

$\displaystyle\begin{split}(\star)_{s}^{(0)}&:=(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)})s_{1k}^{(0)}s_{1m}^{(0)}+s_{1m}^{(0)}h_{k1}^{(0)}h_{11}^{(0)}+s_{1k}^{(0)}h_{m1}^{(0)}h_{11}^{(0)}-s_{11}^{(0)}h_{k1}^{(0)}h_{m1}^{(0)}+s_{1m}^{(0)}h_{k1}^{(0)}+s_{1k}^{(0)}h_{m1}^{(0)}\text{
and }\\\
{\det}_{0}&:=s_{11}^{(0)}(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)})+(1+h_{11}^{(0)})^{2}.\end{split}$
(54)

The essential idea is to show that $|\frac{(\star)_{s}^{(0)}}{\det_{0}}|$ is
sufficiently small compared to $|s_{mk}^{(0)}|$. We first look at the first
term given by
$\Big{(}(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)})s_{1k}^{(0)}s_{1m}^{(0)}\Big{)}/\det_{0}$.
By Lemmas 7, 8 and the definition of $\det_{0}$, we have

$\displaystyle\Big{|}\frac{1}{\det_{0}}\Big{(}(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)})s_{1k}^{(0)}s_{1m}^{(0)}\Big{)}\Big{|}\leq\frac{(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)})|s_{1k}^{(0)}s_{1m}^{(0)}|}{s_{11}^{(0)}(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)})}=\Big{|}\frac{s_{1k}^{(0)}s_{1m}^{(0)}}{s_{11}^{(0)}}\Big{|}\leq\frac{C_{1}}{\sqrt{n}}\cdot\frac{C_{2}+1}{C_{2}}\cdot\frac{\sqrt{n}}{kp},$

where we use $\det_{0}\geq
s_{11}^{(0)}(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)})$ and
$s_{mj}^{(0)}/s_{kk}^{(0)}\leq C/\sqrt{n}\text{ for all }m,j\neq k$. Now, we
upper bound the other two dominant terms $|s_{1m}^{(0)}h_{k1}^{(0)}/\det_{0}|$
and $|{s_{1k}^{(0)}h_{m1}^{(0)}}/\det_{0}|$. Note that the same bound will
apply to the remaining terms in Equation (54) because we trivially have
$|h_{ij}^{(0)}|=\mathcal{O}(1)$ for all $(i,j)\in[k]$. Again, Lemmas 7 and 8
give us

$\displaystyle\Big{|}\frac{s_{1m}^{(0)}h_{k1}^{(0)}}{\det_{0}}\Big{|}\leq\frac{|s_{1m}^{(0)}h_{k1}^{(0)}|}{(1+h_{11}^{(0)})^{2}}\leq\frac{\tilde{\rho}_{n,k}C_{3}\epsilon_{n}}{\left(1-\frac{C_{5}\tilde{\rho}_{n,k}\epsilon_{n}}{k^{2}\sqrt{n}}\right)^{2}k^{2}\sqrt{n}}\cdot\frac{C_{2}+1}{C_{2}}\cdot\frac{\sqrt{n}}{kp}.$

The identical bound holds for $|{s_{1k}^{(0)}h_{m1}^{(0)}}|$. Noting that
$|s_{mk}^{(0)}|\leq\frac{C_{2}+1}{C_{2}}\cdot\frac{\sqrt{n}}{kp}$, we then
have

$\displaystyle|s_{mk}^{(1)}|$
$\displaystyle\leq|s_{mk}^{(0)}|+\Big{|}\frac{(\star)_{s}^{(0)}}{\det_{0}}\Big{|}$
$\displaystyle\leq\left(1+\frac{C_{6}}{\sqrt{n}}+\frac{C_{7}\tilde{\rho}_{n,k}\epsilon_{n}}{\left(1-\frac{C_{5}\tilde{\rho}_{n,k}\epsilon_{n}}{k^{2}\sqrt{n}}\right)^{2}k^{2}\sqrt{n}}\right)\frac{C_{2}+1}{C_{2}}\cdot\frac{\sqrt{n}}{kp}$
$\displaystyle\leq(1+\alpha)\cdot\frac{C_{2}+1}{C_{2}}\cdot\frac{\sqrt{n}}{kp},$
(55)

where in the last inequality, we use that $\epsilon\leq\tau$ for sufficiently
small constant $\tau>0$, and defined

$\alpha:=\frac{C_{6}}{\sqrt{n}}+\frac{C_{7}\tau}{\left(1-\frac{C_{5}\tau}{k^{2}\sqrt{n}}\right)^{2}k^{2}\sqrt{n}}.$

Now, we pick $\tau$ to be sufficiently small and $n$ to be sufficiently large
such that $(1+\alpha)\frac{C_{2}+1}{C_{2}}\leq\frac{C_{8}+1}{C_{8}}$ for some
constant $C_{8}>0$. Then, we conclude with the following upper bound:

$\displaystyle|s_{mk}^{(1)}|\leq\frac{C_{8}+1}{C_{8}}\cdot\frac{\sqrt{n}}{kp}.$

Bounds on $s_{kk}^{(1)}$. Equation (78) in Appendix E.1 gives us

$\displaystyle
s_{kk}^{(1)}=s_{kk}^{(0)}-\frac{1}{\det_{0}}\Big{(}(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)}){s_{1k}^{(0)}}^{2}+2s_{1k}^{(0)}{h_{k1}^{(0)}}h_{11}^{(0)}-s_{11}^{(0)}{h_{k1}^{(0)}}^{2}+2s_{1k}^{(0)}h_{k1}^{(0)}\Big{)}.$

First, we lower bound $s_{kk}^{(1)}$ by upper bounding
$\frac{1}{\det_{0}}\Big{(}(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)}){s_{1k}^{(0)}}^{2}\Big{)}$.
Lemmas 7 and 8 yield

$\displaystyle\frac{1}{\det_{0}}\Big{(}(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)}){s_{1k}^{(0)}}^{2}\Big{)}\leq\frac{(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)}){s_{1k}^{(0)}}^{2}}{s_{11}^{(0)}(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)})+(1+h_{11}^{(0)})^{2}}\leq\frac{(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)}){s_{1k}^{(0)}}^{2}}{s_{11}^{(0)}(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)})}\leq\frac{C_{1}}{n}\cdot\frac{n}{kp}.$

It suffices to upper bound the other dominant term
$|s_{1k}^{(0)}h_{k1}^{(0)}|/\det_{0}$. For this term, we have

$\displaystyle\Big{|}\frac{s_{1k}^{(0)}h_{k1}^{(0)}}{\det_{0}}\Big{|}\leq\frac{|s_{1k}^{(0)}h_{k1}^{(0)}|}{(1+h_{11}^{(0)})^{2}}\leq\frac{C_{3}\tilde{\rho}_{n,k}\epsilon_{n}}{\left(1-\frac{C_{4}\tilde{\rho}_{n,k}\epsilon_{n}}{k^{2}\sqrt{n}}\right)^{2}k^{2}\sqrt{n}}\cdot\frac{C_{2}+1}{C_{2}}\cdot\frac{\sqrt{n}}{kp}.$

Thus, we get

$\displaystyle
s_{kk}^{(1)}\geq\left(1-\frac{C_{1}}{{n}}-\frac{C_{5}\tilde{\rho}_{n,k}n\epsilon_{n}}{\left(1-\frac{C_{4}\tilde{\rho}_{n,k}\epsilon_{n}}{k^{2}\sqrt{n}}\right)^{2}k^{2}\sqrt{n}}\right)\frac{C_{6}-1}{C_{6}}\cdot\frac{{n}}{kp}\geq(1-\alpha)\cdot\frac{C_{6}-1}{C_{6}}\cdot\frac{{n}}{kp}.$

Next, we upper bound $s_{kk}^{(1)}$ by a similar argument, and get

$\displaystyle s_{kk}^{(1)}$
$\displaystyle\leq|s_{kk}^{(0)}|+\frac{1}{\det_{0}}\Big{|}2s_{1k}^{(0)}{h_{k1}^{(0)}}h_{11}^{(0)}+s_{11}^{(0)}{h_{k1}^{(0)}}^{2}+2s_{1k}^{(0)}h_{k1}^{(0)}\Big{|}$
$\displaystyle\leq\left(1+\frac{C_{7}\tilde{\rho}_{n,k}\epsilon_{n}}{\left(1-\frac{C_{4}\tilde{\rho}_{n,k}\epsilon_{n}}{k^{2}\sqrt{n}}\right)^{2}k^{2}\sqrt{n}}\right)\frac{C_{8}+1}{C_{8}}\cdot\frac{{n}}{kp}\leq(1+\alpha^{\prime})\frac{C_{8}+1}{C_{8}}\cdot\frac{{n}}{kp},$

where we used
$\frac{1}{\det_{0}}\Big{(}(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)}){s_{1k}^{(0)}}^{2}\Big{)}>0$
in the first step. As above, we can tune $\epsilon$ and $n$ such that
$(1+\alpha^{\prime})\frac{C_{8}+1}{C_{8}}\leq\frac{C_{9}+1}{C_{9}}$ and
$(1-\alpha)\frac{C_{6}-1}{C_{6}}\geq\frac{C_{9}-1}{C_{9}}$ for sufficiently
large constant $C_{9}>0$.

Bounds on $h_{mk}^{(1)}$. Equation (79) in Appendix E.1 gives us

$\displaystyle h_{mk}^{(1)}$
$\displaystyle=h_{mk}^{(0)}-\frac{1}{\det_{0}}(\star)_{h}^{(0)},$

where we define

$(\star)_{h}^{(0)}=(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)})s_{1m}^{(0)}h_{1k}^{(0)}+h_{m1}^{(0)}h_{1k}^{(0)}h_{11}^{(0)}+h_{m1}^{(0)}h_{1k}^{(0)}+s_{1m}^{(0)}t_{k1}^{(0)}+s_{1m}^{(0)}t_{k1}^{(0)}h_{11}^{(0)}-s_{11}^{(0)}t_{k1}^{(0)}h_{m1}^{(0)}.$

We focus on the two dominant terms
$((\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)})s_{1m}^{(0)}h_{1k}^{(0)})/\det_{0}$
and $s_{1m}^{(0)}t_{k1}^{(0)}/\det_{0}$. For the first dominant term
$((\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)})s_{1m}^{(0)}h_{1k}^{(0)})/\det_{0}$,
Lemmas 7 and 8 yield

$\displaystyle\Big{|}\frac{1}{\det_{0}}\Big{(}(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)})s_{1m}^{(0)}h_{1k}^{(0)}\Big{)}\Big{|}\leq\frac{(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)})|s_{1m}^{(0)}h_{1k}^{(0)}|}{s_{11}^{(0)}(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)})}\leq\Big{|}\frac{s_{1m}^{(0)}h_{1k}^{(0)}}{s_{11}^{(0)}}\Big{|}\leq\frac{C_{1}}{\sqrt{n}}|h_{1k}^{(0)}|\leq\frac{C_{2}\tilde{\rho}_{n,k}\epsilon_{n}}{k^{2}\sqrt{n}}.$

For the second dominant term $s_{1m}^{(0)}t_{k1}^{(0)}/\det_{0}$, we have

$\displaystyle\frac{1}{\det_{0}}s_{1m}^{(0)}t_{k1}^{(0)}\leq\frac{|s_{1m}^{(0)}t_{k1}^{(0)}|}{(1+h_{11}^{(0)})^{2}}\leq\frac{C_{3}n\sqrt{n}\|{\boldsymbol{\mu}}\|_{2}^{2}}{\left(1-\frac{C_{4}\tilde{\rho}_{n,k}\epsilon_{n}}{k^{2}\sqrt{n}}\right)^{2}kp^{2}}\leq\frac{C_{5}\epsilon_{n}}{\left(1-\frac{C_{4}\tilde{\rho}_{n,k}\epsilon_{n}}{k^{2}\sqrt{n}}\right)^{2}k^{1.5}\sqrt{n}}\cdot\frac{\tilde{\rho}_{n,k}\epsilon_{n}}{k^{2}\sqrt{n}},$

where we use the fact $1/\sqrt{k}<\tilde{\rho}_{n,k}$ for $k>1$. Thus, we get

$\displaystyle|h_{mk}^{(1)}|$
$\displaystyle\leq|h_{mk}^{(0)}|+\Big{|}\frac{1}{\det_{0}}(\star)_{h}^{(0)}\Big{|}\leq\left(1+\frac{C_{1}}{\sqrt{n}}+\frac{C_{5}\tilde{\rho}_{n,k}\epsilon_{n}}{\left(1-\frac{C_{4}\tilde{\rho}_{n,k}\epsilon_{n}}{k^{2}\sqrt{n}}\right)^{2}k^{1.5}\sqrt{n}}\right)\frac{C_{6}\tilde{\rho}_{n,k}\epsilon_{n}}{k^{2}\sqrt{n}}$
$\displaystyle\leq(1+\alpha)\frac{C_{7}\tilde{\rho}_{n,k}\epsilon_{n}}{k^{2}\sqrt{n}},$

and there exists constant $C_{8}$ such that $(1+\alpha)C_{7}\leq C_{8}$, which
shows the desired upper bound.

Bounds on $t_{kk}^{(1)}$. Equation (81) in Appendix E.1 gives us

$\displaystyle
t_{kk}^{(1)}=t_{kk}^{(0)}-\frac{1}{\det_{0}}\left(\left(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)}\right){h_{1k}^{(0)}}^{2}+2t_{1k}^{(0)}{h_{1k}^{(0)}}h_{11}^{(0)}-s_{11}^{(0)}{t_{1k}^{(0)}}^{2}+2t_{1k}^{(0)}h_{1k}^{(0)}\right).$

We only need an upper bound on $t_{kk}^{(1)}$. The first dominant term
$s_{11}^{(0)}{t_{1k}^{(0)}}^{2}/\det_{0}$ is upper bounded as follows:

$\displaystyle\frac{s_{11}^{(0)}{t_{1k}^{(0)}}^{2}}{\det_{0}}\leq\frac{s_{11}^{(0)}{t_{1k}^{(0)}}^{2}}{(1+h_{11}^{(0)})^{2}}\leq\frac{C_{6}n^{3}\|{\boldsymbol{\mu}}\|_{2}^{4}}{\left(1-\frac{C_{3}\tilde{\rho}_{n,k}\epsilon_{n}}{k^{2}\sqrt{n}}\right)^{2}kp^{3}}\leq\frac{C_{7}\epsilon_{n}^{2}}{\left(1-\frac{C_{3}\tilde{\rho}_{n,k}\epsilon_{n}}{k^{2}\sqrt{n}}\right)^{2}pk^{4}{n}}\cdot\frac{n\|{\boldsymbol{\mu}}\|_{2}^{2}}{p}.$

Next, the second dominant term, $t_{1k}^{(0)}h_{1k}^{(0)}/\det_{0}$, is upper
bounded as

$\displaystyle\frac{t_{1k}^{(0)}h_{1k}^{(0)}}{\det_{0}}\leq\frac{|t_{1k}^{(0)}h_{1k}^{(0)}|}{(1+h_{11}^{(0)})^{2}}\leq\frac{C_{8}\tilde{\rho}_{n,k}\epsilon_{n}}{k^{2}\sqrt{n}\left(1-\frac{C_{3}\tilde{\rho}_{n,k}\epsilon_{n}}{k^{2}\sqrt{n}}\right)^{2}}\cdot\frac{n\|{\boldsymbol{\mu}}\|_{2}^{2}}{p}.$

Combining the results above gives us

$\displaystyle t_{kk}^{(1)}$ $\displaystyle\leq
t_{kk}^{(0)}+\frac{1}{\det_{0}}\Big{|}2t_{1k}^{(0)}{h_{1k}^{(0)}}h_{11}^{(0)}+s_{11}^{(0)}{t_{1k}^{(0)}}^{2}+2t_{1k}^{(0)}h_{1k}^{(0)}\Big{|}$
$\displaystyle\leq\left(1+\frac{C_{9}\tilde{\rho}_{n,k}\epsilon_{n}}{\left(1-\frac{C_{3}\tilde{\rho}_{n,k}\epsilon_{n}}{k^{2}\sqrt{n}}\right)^{2}k^{2}\sqrt{n}}\right)\frac{{n\|{\boldsymbol{\mu}}\|_{2}^{2}}}{p}\leq\frac{{C_{5}n\|{\boldsymbol{\mu}}\|_{2}^{2}}}{p}.$

This shows the desired upper bound.

Bounds on $t_{mk}^{(1)}$. Equation (80) in Appendix E.1 gives us

$\displaystyle t_{mk}^{(1)}$
$\displaystyle=t_{mk}^{(0)}-\frac{1}{\det_{0}}(\star)_{t}^{(0)},$

where we define

$(\star)_{t}^{(0)}=(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)})h_{1m}^{(0)}h_{1k}^{(0)}+t_{m1}^{(0)}h_{1k}^{(0)}h_{11}^{(0)}+t_{k1}^{(0)}h_{1m}^{(0)}h_{11}^{(0)}+t_{1m}^{(0)}h_{1k}^{(0)}+t_{1k}^{(0)}h_{1m}^{(0)}-s_{11}^{(0)}t_{1m}^{(0)}t_{1k}^{(0)}.$

Again, we only need an upper bound on $t_{mk}^{(1)}$. As in the previously
derived bounds, we have

$\displaystyle\frac{1}{\det_{0}}(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)}){h_{1m}^{(0)}}{h_{1k}^{(0)}}\leq\frac{(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)})|{h_{1m}^{(0)}}{h_{1k}^{(0)}}|}{s_{11}^{(0)}(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)})}\leq\frac{C_{1}\tilde{\rho}_{n,k}^{2}n^{2}\|{\boldsymbol{\mu}}\|_{2}^{2}}{kp^{2}}\cdot\frac{kp}{n}\leq\frac{C_{1}n\|{\boldsymbol{\mu}}\|_{2}^{2}}{p}.$

The other dominant term $t_{1m}^{(0)}h_{1m}^{(0)}/\det_{0}$ is upper bounded
as:

$\displaystyle\frac{t_{1m}^{(0)}h_{1m}^{(0)}}{\det_{0}}\leq\frac{|t_{1m}^{(0)}h_{1m}^{(0)}|}{(1+h_{11}^{(0)})^{2}}\leq\frac{C_{2}\tilde{\rho}_{n,k}\epsilon_{n}}{k^{2}\sqrt{n}(\left(1-\frac{C_{3}\tilde{\rho}_{n,k}\epsilon_{n}}{k^{2}\sqrt{n}}\right)^{2}}\cdot\frac{n\|{\boldsymbol{\mu}}\|_{2}^{2}}{p}.$

Combining the results above yields

$\displaystyle|t_{mk}^{(1)}|$
$\displaystyle\leq|t_{mk}^{(0)}|+\frac{1}{\det_{0}}\Big{|}(\star)_{t}^{(0)}\Big{|}$
$\displaystyle\leq\left(C_{1}+\frac{C_{2}\tilde{\rho}_{n,k}\epsilon_{n}}{\left(1-\frac{C_{3}\tilde{\rho}_{n,k}\epsilon_{n}}{k^{2}\sqrt{n}}\right)^{2}k^{2}\sqrt{n}}\right)\frac{{n\|{\boldsymbol{\mu}}\|_{2}^{2}}}{p}\leq\frac{{C_{4}n\|{\boldsymbol{\mu}}\|_{2}^{2}}}{p}.$

Note that both $t_{kk}^{(0)}$ and $t_{mk}^{(0)}$ are much smaller than
$\|{\boldsymbol{\mu}}\|_{2}^{2}$. The above upper bound shows that this
continues to hold for $t_{kk}^{(1)}$ and $t_{mk}^{(1)}$ since $p\gg n$.

Bounds on $f_{ki}^{(1)}$. Consider $i\in[n]$ and fix $y_{i}=k$ without loss of
generality. Equation (82) in Appendix E.1 gives us

$\displaystyle f_{ki}^{(1)}$
$\displaystyle=f_{ki}^{(0)}-\frac{1}{\det_{0}}(\star)_{f}^{(0)},$ (56)

where we define

$\displaystyle(\star)_{f}^{(0)}=(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)})h_{1k}^{(0)}g_{1i}^{(0)}+t_{1k}^{(0)}g_{1i}^{(0)}+t_{1k}^{(0)}h_{11}^{(0)}g_{1i}^{(0)}+h_{1k}^{(0)}f_{1i}^{(0)}+h_{1k}^{(0)}h_{11}^{(0)}f_{1i}^{(0)}-s_{11}^{(0)}t_{1k}^{(0)}f_{1i}^{(0)}.$
(57)

We only need an upper bound on $f_{ki}^{(1)}$. We consider the dominant terms
$(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)})h_{1k}^{(0)}g_{1i}^{(0)}/\det_{0}$,
$t_{1k}^{(0)}g_{1i}^{(0)}/\det_{0}$, $h_{1k}^{(0)}f_{1i}^{(0)}/\det_{0}$ and
$s_{11}^{(0)}t_{1k}^{(0)}f_{1i}^{(0)}/\det_{0}$. Lemmas 7, 8 and 9 give us

$\displaystyle\frac{(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)})h_{1k}^{(0)}g_{1i}^{(0)}}{\det_{0}}\leq\frac{(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)})|h_{1k}^{(0)}g_{1i}^{(0)}|}{(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)})s_{11}^{(0)}}$
$\displaystyle\leq\frac{C_{1}\tilde{\rho}_{n,k}n\|{\boldsymbol{\mu}}\|_{2}}{\sqrt{k}p}\cdot\frac{1}{C_{2}k^{2}p}\cdot\frac{kp}{n}\leq\frac{C_{3}}{k^{1.5}\sqrt{n}}\cdot\frac{\sqrt{n}\|{\boldsymbol{\mu}}\|_{2}}{p},$
$\displaystyle\frac{t_{1k}^{(0)}g_{1i}^{(0)}}{\det_{0}}\leq\frac{|t_{1k}^{(0)}g_{1i}^{(0)}|}{(1+h_{11}^{(0)})^{2}}\leq\frac{C_{4}n\|{\boldsymbol{\mu}}\|_{2}^{2}}{\left(1-\frac{C_{5}\tilde{\rho}_{n,k}\epsilon}{k^{2}\sqrt{n}}\right)^{2}k^{2}p^{2}}\leq\frac{C_{7}\epsilon_{n}}{\left(1-\frac{C_{5}\tilde{\rho}_{n,k}\epsilon_{n}}{k^{2}\sqrt{n}}\right)^{2}k^{3.5}{{n}}}\cdot\frac{\sqrt{n}\|{\boldsymbol{\mu}}\|_{2}}{p},$
$\displaystyle\frac{h_{1k}^{(0)}f_{1i}^{(0)}}{\det_{0}}\leq\frac{|h_{1k}^{(0)}f_{1i}^{(0)}|}{(1+h_{11}^{(0)})^{2}}\leq\frac{C_{6}\tilde{\rho}_{n,k}\epsilon_{n}}{\left(1-\frac{C_{5}\tilde{\rho}_{n,k}\epsilon_{n}}{k^{2}\sqrt{n}}\right)^{2}k^{2}\sqrt{n}}\cdot\frac{\sqrt{n}\|{\boldsymbol{\mu}}\|_{2}}{p},\text{
and }$
$\displaystyle\frac{s_{11}^{(0)}t_{1k}^{(0)}f_{1i}^{(0)}}{\det_{0}}\leq\frac{|s_{11}^{(0)}t_{1k}^{(0)}f_{1i}^{(0)}|}{(1+h_{11}^{(0)})^{2}}\leq\frac{C_{7}\epsilon_{n}^{2}}{k^{4}{n}\left(1-\frac{C_{5}\tilde{\rho}_{n,k}\epsilon_{n}}{k^{2}\sqrt{n}}\right)^{2}}\cdot\frac{\sqrt{n}\|{\boldsymbol{\mu}}\|_{2}}{p},$

where, in the last two steps, we used the upper bound
${C\sqrt{n}\|{\boldsymbol{\mu}}\|_{2}}/{p}$ for $|f_{ji}^{(0)}|$ and
previously derived bounds on $|h_{1k}^{(0)}|$ and
$|s_{11}^{(0)}t_{1k}^{(0)}|$. Thus, we have

$\displaystyle|f_{ki}^{(1)}|$
$\displaystyle\leq|f_{ki}^{(0)}|+\Big{|}\frac{1}{\det_{0}}(\star)_{f}^{(0)}\Big{|}$
$\displaystyle\leq\left(1+\frac{C_{3}}{k^{1.5}\sqrt{n}}+\frac{C_{8}\epsilon_{n}}{\left(1-\frac{C_{5}\tilde{\rho}_{n,k}\epsilon_{n}}{k^{2}\sqrt{n}}\right)^{2}k^{2}\sqrt{n}}\right)\frac{C_{9}\sqrt{n}\|{\boldsymbol{\mu}}\|_{2}}{p}$
$\displaystyle\leq(1+\alpha)\frac{C_{10}\epsilon_{n}}{k^{1.5}{n}},$

and we have $(1+\alpha)C_{10}\leq C_{11}$ for a large enough positive constant
$C_{11}$. This shows the desired upper bound.

Bounds on $g_{ki}^{(1)}$ and $g_{mi}^{(1)}$. Equation (83) in Appendix E.1
gives

$\displaystyle
z_{ci}\mathbf{e}_{i}^{T}\mathbf{A}_{1}^{-1}\mathbf{u}_{k}=|z_{ci}|^{2}\Big{(}\mathbf{e}_{i}^{T}\mathbf{A}_{0}^{-1}\mathbf{v}_{k}-\frac{1}{\det_{0}}(\star)_{gk}^{(0)}\Big{)}=|z_{ci}|^{2}\Big{(}g_{ki}^{(0)}-\frac{1}{\det_{0}}(\star)_{gk}^{(0)}\Big{)},$
(58)

where we define

$(\star)_{gk}^{(0)}=(\|\boldsymbol{\mu}_{1}\|_{2}^{2}-t_{11}^{(0)})s_{1k}^{(0)}g_{1i}^{(0)}+g_{1i}^{(0)}h_{11}^{(0)}h_{k1}^{(0)}+g_{1i}^{(0)}h_{k1}^{(0)}+s_{1k}^{(0)}f_{1i}^{(0)}+s_{1k}^{(0)}h_{11}^{(0)}f_{1i}^{(0)}-s_{11}^{(0)}h_{k1}^{(0)}f_{1i}^{(0)}.$

Lemmas 7, 8 and 9 give us

$\displaystyle\frac{(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)})|s_{1k}^{(0)}g_{1i}^{(0)}|}{\det_{0}}\leq\frac{(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)})|s_{1k}^{(0)}g_{1i}^{(0)}|}{(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)})s_{11}^{(0)}}\leq\frac{C_{1}}{\sqrt{n}}\cdot\frac{1}{C_{2}k^{2}p},$
$\displaystyle\frac{|h_{k1}^{(0)}g_{1i}^{(0)}|}{\det_{0}}\leq\frac{|h_{k1}^{(0)}g_{1i}^{(0)}|}{(1+h_{11}^{(0)})^{2}}\leq\frac{C_{3}\tilde{\rho}_{n,k}\epsilon_{n}}{\left(1-\frac{C_{4}\tilde{\rho}_{n,k}\epsilon_{n}}{k^{2}\sqrt{n}}\right)^{2}k^{2}\sqrt{n}}\cdot\frac{1}{C_{2}k^{2}p},\text{
and }$
$\displaystyle\frac{|s_{1k}^{(0)}f_{1i}^{(0)}|}{\det_{0}}\leq\frac{|s_{1k}^{(0)}f_{1i}^{(0)}|}{(1+h_{11}^{(0)})^{2}}\leq\frac{C_{5}\epsilon_{n}}{\left(1-\frac{C_{4}\tilde{\rho}_{n,k}\epsilon_{n}}{k^{2}\sqrt{n}}\right)^{2}\sqrt{k}\sqrt{n}}\cdot\frac{1}{C_{2}k^{2}p}.$

We then have

$\displaystyle g_{ki}^{(1)}$ $\displaystyle\geq
g_{ki}^{(0)}-\frac{1}{\det_{0}}|(\star)_{gk}^{(0)}|\geq\left(1-\frac{1}{C}\right)\left(1-\frac{C_{1}}{k^{2}\sqrt{n}}-\frac{C_{6}\epsilon_{n}}{\left(1-\frac{C_{4}\tilde{\rho}_{n,k}\epsilon_{n}}{k^{2}\sqrt{n}}\right)^{2}k^{2.5}\sqrt{n}}\right)\frac{1}{p}\geq\left(1-\frac{1}{C}\right)\frac{1-\alpha}{p}$
$\displaystyle g_{ki}^{(1)}$ $\displaystyle\leq
g_{ki}^{(0)}+\frac{1}{\det_{0}}|(\star)_{gk}^{(0)}|\leq\left(1+\frac{1}{C}\right)\left(1+\frac{C_{1}}{k^{2}\sqrt{n}}+\frac{C_{7}\epsilon_{n}}{\left(1-\frac{C_{4}\tilde{\rho}_{n,k}\epsilon_{n}}{k^{2}\sqrt{n}}\right)^{2}k^{2.5}\sqrt{n}}\right)\frac{1}{p}\leq\left(1+\frac{1}{C}\right)\frac{1+\alpha}{p},$

where for large enough $n$ and positive constant $C_{9}$, we have
$(1+\alpha)\frac{C+1}{C}\leq\frac{C_{9}+1}{C_{9}}$ and
$(1-\alpha)\frac{C-1}{C}\geq\frac{C_{9}-1}{C_{9}}$. Similarly, for the case
$m\neq k$, we have

$\displaystyle
z_{ci}\mathbf{e}_{i}^{T}\mathbf{A}_{1}^{-1}\mathbf{u}_{m}=|z_{ci}|^{2}\left(\mathbf{e}_{i}^{T}\mathbf{A}_{0}^{-1}\mathbf{v}_{m}-\frac{1}{\det_{0}}(\star)_{gm}^{(0)}\right)=|z_{ci}|^{2}\Big{(}g_{mi}^{(0)}-\frac{1}{\det_{0}}(\star)_{gm}^{(0)}\Big{)},$
(59)

where we define

$(\star)_{gm}^{(0)}=(\|\boldsymbol{\mu}\|_{2}^{2}-t_{11}^{(0)})s_{1m}^{(0)}g_{1i}^{(0)}+g_{1i}^{(0)}h_{11}^{(0)}h_{m1}^{(0)}+g_{1i}^{(0)}h_{m1}^{(0)}+s_{1m}^{(0)}f_{1i}^{(0)}+s_{1m}^{(0)}h_{11}^{(0)}f_{1i}^{(0)}-s_{11}^{(0)}h_{m1}^{(0)}f_{1i}^{(0)}.$

As a consequence of our equal energy and priors assumption (Assumption 1), we
can directly use the bounds of the terms in $(\star)_{gk}^{(0)}$ to bound
terms in $(\star)_{gm}^{(0)}$. We get

$\displaystyle|g_{mi}^{(1)}|\leq\frac{1}{C}\left(1+\frac{C_{1}}{\sqrt{n}}+\frac{C_{8}\epsilon_{n}}{(1-(\frac{C_{4}\tilde{\rho}_{n,k}\epsilon_{n}}{k^{2}\sqrt{n}}))^{2}\sqrt{k}\sqrt{n}}\right)\frac{1}{k^{2}p}\leq\frac{1}{C}\cdot\frac{1+\alpha}{k^{2}p}.$

Finally, there exists a sufficiently large constant $C_{10}$ such that
$(1+\alpha)/C\leq 1/C_{10}$. This shows the desired bounds.

####  A.2.3 Completing the proof for k-th order quadratic forms

Notice from the above analysis that the $1$-st order quadratic forms exhibit
the same order-wise dependence on $n,k$ and $p$ as the $0$-th order quadratic
forms, e.g. both $s_{mk}^{(0)}$ and $s_{mk}^{(1)}$ are of order
$\Theta(\frac{\sqrt{n}}{kp})$. Thus, the higher-order quadratic forms that
arise by including more mean components will not change too much777There are
several low-level reasons for this. One critical reason is the aforementioned
orthogonality of the label indicator vectors $\\{\mathbf{v}_{c}\\}_{c\in[k]}$,
which ensures by Lemma 8 that the cross-terms $|s_{mk}^{(j)}|$ are always
dominated by the larger terms $|s_{kk}^{(j)}|$. Another reason is that
$h_{mk}^{(0)}$, which can be seen as the “noise” term in our analysis, is
small and thus does not affect other terms. . By Equation (38), we can see
that we can bound the $2$-nd order quadratic forms by bounding quadratic forms
with order $1$. We consider $s_{mk}^{(2)}$ as an example:

$\displaystyle s_{mk}^{(2)}$
$\displaystyle=s_{mk}^{(1)}-\frac{1}{\det_{1}}(\star)_{s}^{(1)},$

where

$\displaystyle(\star)_{s}^{(1)}$
$\displaystyle:=(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{22}^{(1)})s_{2k}^{(1)}s_{2m}^{(1)}+s_{2m}^{(1)}h_{k2}^{(1)}h_{22}^{(1)}+s_{2k}^{(1)}h_{m2}^{(1)}h_{22}^{(1)}-s_{22}^{(1)}h_{k2}^{(1)}h_{m2}^{(1)}+s_{2m}^{(1)}h_{k2}^{(1)}+s_{2k}^{(1)}h_{m2}^{(1)},$
$\displaystyle{\det}_{1}$
$\displaystyle:=s_{22}^{(1)}(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{22}^{(1)})+(1+h_{22}^{(1)})^{2}.$

We additionally show how $f_{ki}^{(2)}$ relates to the $1$-st order quadratic
forms:

$\displaystyle f_{ki}^{(2)}$
$\displaystyle=f_{ki}^{(1)}-\frac{1}{\det_{1}}(\star)_{f}^{(1)},$

where we define

$(\star)_{f}^{(1)}=(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{22}^{(1)})h_{2k}^{(1)}g_{2i}^{(1)}+t_{2k}^{(1)}g_{2i}^{(1)}+t_{2k}^{(1)}h_{22}^{(1)}g_{2i}^{(1)}+h_{2k}^{(1)}f_{2i}^{(1)}+h_{2k}^{(1)}h_{22}^{(1)}f_{2i}^{(1)}-s_{22}^{(1)}t_{2k}^{(1)}f_{2i}^{(1)}.$

Observe that the equations above are very similar to Equations (53) and (54)
(for $s$), and Equations (56) and (57) (for $f$), except that the quadratic
forms are in terms of Gram matrix $\mathbf{A}_{1}$. We have shown that the
quadratic forms with order $1$ will not be drastically different different
from the quadratic forms with order $0$. Hence, we repeat the above procedures
of bounding these quadratic forms $k-1$ times to obtain the desired bounds in
Lemma 2. The only quantity that will change in each iteration is $\alpha$,
which nevertheless remains negligible888To see this, recall that in the first
iteration we had
$\alpha_{1}:=\alpha=\frac{C_{1}}{\sqrt{n}}+\frac{C_{2}\tau}{(1-(C_{5}\tau/(k^{2}\sqrt{n})))^{2}k^{2}\sqrt{n}}$
for the first-order terms. Thus, even if we repeat the procedure $k-1$ times,
then we have $\alpha_{k}\leq Ck\alpha_{1}$, which remains small since we
consider $n\gg k$..

Our analysis so far is conditioned on event $\mathcal{E}_{q}$. We define the
unconditional event $\mathcal{E}_{u}:=$ $\\{$all the inequalities in Lemma 2
hold$\\}$. Then, we have

$\displaystyle\mathbb{P}(\mathcal{E}_{u}^{c})$
$\displaystyle\leq\mathbb{P}(\mathcal{E}_{u}^{c}|\mathcal{E}_{q})+\mathbb{P}(\mathcal{E}_{q}^{c})\leq\mathbb{P}(\mathcal{E}_{u}^{c}|\mathcal{E}_{q})+\mathbb{P}(\mathcal{E}_{q}^{c}|\mathcal{E}_{v})+\mathbb{P}(\mathcal{E}_{v}^{c})$
$\displaystyle\leq\frac{c_{1}}{kn}+\frac{c_{2}}{n}+c_{3}k(e^{-\frac{n}{c_{4}}}+e^{-\frac{n}{c_{5}k^{2}}})$
$\displaystyle\leq\frac{c_{6}}{n}+c_{7}ke^{-\frac{n}{c_{5}k^{2}}},$

for constants $c_{i}$’s $>1$. This completes the proof.

###  A.3 Proofs of Auxiliary lemmas

We complete this section by proving the auxiliary Lemmas 6, 8 and 9, which
were used in the proof of Lemma 2.

####  A.3.1 Proof of Lemma 6

Our goal is to upper and lower bound $\|{\mathbf{v}_{c}}\|_{2}^{2}$, for
$c\in[k]$. Note that every entry of $\mathbf{v}_{c}$ is either $1$ or $0$,
hence these entries are independent sub-Gaussian random variables with sub-
Gaussian parameter $1$ [Wai19, Chapter 2]. Under the equal-prior Assumption 1,
we have $\mathbb{E}[\|{\mathbf{v}_{c}}\|_{2}^{2}]=n/k$ when we assume equal
priors. Thus, a straightforward application of Hoeffding’s concentration
inequality on bounded random variables [Wai19, Chapter 2] gives us

$\displaystyle\mathbb{P}\left(\left|\|{\mathbf{v}_{c}}\|_{2}^{2}-\frac{n}{k}\right|\geq
t\right)\leq 2\exp\left(-\frac{t^{2}}{2n}\right).$

We complete the proof by setting $t=\frac{n}{C_{1}k}$ for a large enough
constant $C_{1}$ and applying the union bound over all $c\in[k]$.

####  A.3.2 Proof of Lemma 8

We use the following lemma adapted from [MNS+21, Lemma 2] to bound quadratic
forms of inverse Wishart matrices.

######  Lemma 10.

Define $p^{\prime}(n):=(p-n+1)$, and consider matrix
$\mathbf{M}\sim\text{Wishart}(p,\mathbf{I}_{n})$. For any unit Euclidean norm
vector $\mathbf{v}$ and any $t>0$, we have

$\displaystyle\mathbb{P}\Big{(}\frac{1}{\mathbf{v}^{T}\mathbf{M}^{-1}\mathbf{v}}>p^{\prime}(n)+\sqrt{2tp^{\prime}(n)}+2t\Big{)}\leq
e^{-t}\quad\text{and}\quad\mathbb{P}\Big{(}\frac{1}{\mathbf{v}^{T}\mathbf{M}^{-1}\mathbf{v}}<p^{\prime}(n)-\sqrt{2tp^{\prime}(n)}\Big{)}\leq
e^{-t},$

provided that $p^{\prime}(n)>2\max\\{t,1\\}$.

We first upper and lower bound $s_{cc}^{(0)}$ for a fixed $c\in[k]$. Recall
that we assume $p>Cn\log(kn)+n-1$ for sufficiently large constant $C>1$ and
this can be obtained by assuming $p^{\prime}(n)>Cn\log(kn)$. Let
$t=2\log(kn)$. Working on the event $\mathcal{E}_{v}$ defined in (49), Lemma
10 gives us

$\displaystyle
s_{cc}^{(0)}\leq\frac{\|{\mathbf{v}_{c}}\|_{2}^{2}}{p^{\prime}(n)-\sqrt{4\log(kn)p^{\prime}(n)}}\leq\frac{C_{1}+1}{C_{1}}\cdot\frac{n/k}{p^{\prime}(n)\left(1-\frac{2}{\sqrt{Cn}}\right)}\leq\frac{C_{2}+1}{C_{2}}\cdot\frac{n}{kp}$

with probability at least $1-\frac{2}{k^{2}n^{2}}$. Here, the last inequality
comes from the fact that $p$ is sufficiently large compared to $n$ and $C$ is
large enough. Similarly, for the lower bound, we have

$\displaystyle
s_{cc}^{(0)}\geq\frac{\|{\mathbf{v}_{c}}\|_{2}^{2}}{p^{\prime}(n)+\sqrt{4\log(kn)p^{\prime}(n)}+2\log(kn)}\geq\frac{C_{1}-1}{C_{1}}\cdot\frac{n/k}{p^{\prime}(n)\left(1+\frac{4}{\sqrt{Cn}}\right)}\geq\frac{C_{2}-1}{C_{2}}\cdot\frac{n}{kp}$

with probability $1-\frac{2}{k^{2}n^{2}}$.

Now we upper and lower bound $s_{cj}^{(0)}$ for a fixed choice $j\neq
c\in[k]$. We use the parallelogram law to get

$\displaystyle\mathbf{v}_{c}^{T}\mathbf{A}_{0}^{-1}\mathbf{v}_{j}=\frac{1}{4}\Big{(}(\mathbf{v}_{c}+\mathbf{v}_{j})^{T}\mathbf{A}_{0}^{-1}(\mathbf{v}_{c}+\mathbf{v}_{j})-(\mathbf{v}_{c}-\mathbf{v}_{j})^{T}\mathbf{A}_{0}^{-1}(\mathbf{v}_{c}-\mathbf{v}_{j})\Big{)}.$

Because of the orthogonality of the label indicator vectors
($\mathbf{v}_{c}^{T}\mathbf{v}_{j}=0$ for any $j\neq c$), we have
$\|{\mathbf{v}_{c}+\mathbf{v}_{j}}\|_{2}^{2}=\|{\mathbf{v}_{c}-\mathbf{v}_{j}}\|_{2}^{2}$,
which we denote by $\tilde{n}$ as shorthand. Then, we have

$\displaystyle\mathbf{v}_{c}^{T}\mathbf{A}_{0}^{-1}\mathbf{v}_{j}$
$\displaystyle\leq\frac{1}{4}\left(\frac{\tilde{n}}{p^{\prime}(n)-\sqrt{4\log({k}n)p^{\prime}(n)}}-\frac{\tilde{n}}{p^{\prime}(n)+\sqrt{4\log({k}n)p^{\prime}(n)}+4\log({k}n)}\right)$
$\displaystyle\leq\frac{1}{4}\cdot\frac{2\tilde{n}\sqrt{4\log({k}n)p^{\prime}(n)}+4\tilde{n}\log(kn)}{(p^{\prime}(n)-\sqrt{4\log({k}n)p^{\prime}(n)})(p^{\prime}(n)+\sqrt{4\log({k}n)p^{\prime}(n)})}$
$\displaystyle\leq\frac{C_{1}+1}{2C_{1}k}\cdot\frac{2{n}\sqrt{4\log({k}n)p^{\prime}(n)}+4{n}\log(kn)}{(p^{\prime}(n)-\sqrt{4\log({k}n)p^{\prime}(n)})(p^{\prime}(n)+\sqrt{4\log({k}n)p^{\prime}(n)})}$

with probability at least $1-\frac{2}{k^{2}n^{2}}$ Here, the last inequality
follows because we have
$\tilde{n}\leq\frac{2(C_{1}+1)}{C_{1}}\cdot\frac{n}{k}$ on $\mathcal{E}_{v}$.
Because $p^{\prime}(n)>Cn\log(kn)$, we have

$\displaystyle\mathbf{v}_{c}^{T}\mathbf{A}_{0}^{-1}\mathbf{v}_{j}$
$\displaystyle\leq\frac{C_{1}+1}{2C_{1}k}\cdot\frac{2\sqrt{n}p^{\prime}(n)\cdot\sqrt{4/C}+4/C\cdot
p^{\prime}(n)}{\left(1-\sqrt{4/(Cn)}\right)p^{\prime}(n)^{2}}$
$\displaystyle\leq\frac{C_{1}+1}{2C_{1}}\cdot\frac{\sqrt{n}}{{k}}\cdot\frac{2\sqrt{4/C}+\sqrt{4/(Cn)}}{p^{\prime}(n)(1-\sqrt{4/(Cn)})}$
$\displaystyle\leq\frac{C_{2}+1}{C_{2}}\cdot\frac{\sqrt{n}}{kp},$

where in the last step we use the fact that $C>1$ is large enough. To lower
bound $s_{cj}^{(0)}$, we get

$\displaystyle\mathbf{v}_{c}^{T}\mathbf{A}_{0}^{-1}\mathbf{v}_{j}$
$\displaystyle\geq\frac{1}{4}\left(\frac{\tilde{n}}{(p^{\prime}(n)+\sqrt{4\log({k}n)p^{\prime}(n)}+4\log({k}n))}-\frac{\tilde{n}}{(p^{\prime}(n)-\sqrt{4\log({k}n)p^{\prime}(n)})}\right)$
$\displaystyle\geq\frac{1}{4}\cdot\frac{-2\tilde{n}\sqrt{4\log({k}n)p^{\prime}(n)}-4\tilde{n}\log(kn)}{(p^{\prime}(n)-\sqrt{4\log({k}n)p^{\prime}(n)})(p^{\prime}(n)+\sqrt{4\log({k}n)p^{\prime}(n)})}$
$\displaystyle\geq-\frac{C_{1}+1}{2C_{1}k}\cdot\frac{2{n}\sqrt{4\log({k}n)p^{\prime}(n)}+4{n}\log(kn)}{(p^{\prime}(n)-\sqrt{4\log({k}n)p^{\prime}(n)})(p^{\prime}(n)+\sqrt{4\log({k}n)p^{\prime}(n)})}$

with probability at least $1-\frac{2}{k^{2}n^{2}}$. Then following similar
steps to the upper bound of
$\mathbf{v}_{c}^{T}\mathbf{A}_{0}^{-1}\mathbf{v}_{j}$ gives us

$\displaystyle\mathbf{v}_{c}^{T}\mathbf{A}_{0}^{-1}\mathbf{v}_{j}$
$\displaystyle\geq-\frac{C_{1}+1}{2C_{1}k}\cdot\frac{2\sqrt{n}p^{\prime}(n)\sqrt{4/C}+(4/C)p^{\prime}(n)}{(p^{\prime}(n)-\sqrt{4/(Cn)}p^{\prime}(n))p^{\prime}(n)}$
$\displaystyle\geq-\frac{C_{1}+1}{2C_{1}}\cdot\frac{\sqrt{n}}{{k}}\cdot\frac{2\sqrt{4/C}+(4/C\sqrt{n})}{p^{\prime}(n)(1-\sqrt{4/(Cn)})}$
$\displaystyle\geq-\frac{C_{2}+1}{C_{2}}\cdot\frac{\sqrt{n}}{kp}.$

We finally apply the union bound on all pairs of $c,j\in[k]$ and complete the
proof.

####  A.3.3 Proof of Lemma 9

We first lower and upper bound $g_{(y_{i})i}^{(0)}$. Recall that we assumed
$y_{i}=k$ without loss of generality. With a little abuse of notation, we
define $\|{\mathbf{v}_{k}}\|_{2}^{2}=\tilde{n}$ and
$\mathbf{u}:=\sqrt{\tilde{n}}\mathbf{e}_{i}$. We use the parallelogram law to
get

$\displaystyle\mathbf{e}_{i}^{T}\mathbf{A}_{0}^{-1}\mathbf{v}_{k}=\frac{1}{4\sqrt{\tilde{n}}}\left((\mathbf{u}+\mathbf{v}_{k})^{T}\mathbf{A}_{0}^{-1}(\mathbf{u}+\mathbf{v}_{k})-(\mathbf{u}-\mathbf{v}_{k})^{T}\mathbf{A}_{0}^{-1}(\mathbf{u}-\mathbf{v}_{k})\right).$

Note that
$\|{\mathbf{u}+\mathbf{v}_{k}}\|_{2}^{2}=2(\tilde{n}+\sqrt{\tilde{n}})$ and
$\|{\mathbf{u}-\mathbf{v}_{k}}\|_{2}^{2}=2(\tilde{n}-\sqrt{\tilde{n}})$. As
before, we apply Lemma 10 with $t=2\log(kn)$ to get with probability at least
$1-\frac{2}{k^{2}n^{2}}$,

$\displaystyle\mathbf{e}_{i}^{T}\mathbf{A}_{0}^{-1}\mathbf{v}_{k}$
$\displaystyle\geq\frac{1}{4\sqrt{\tilde{n}}}\left(\frac{2(\tilde{n}+\sqrt{\tilde{n}})}{(p^{\prime}(n)+\sqrt{4\log({k}n)p^{\prime}(n)}+4\log({k}n))}-\frac{2(\tilde{n}-\sqrt{\tilde{n}})}{(p^{\prime}(n)-\sqrt{4\log({k}n)p^{\prime}(n)})}\right)$
$\displaystyle\geq\frac{1}{4\sqrt{\tilde{n}}}\cdot\frac{4\sqrt{\tilde{n}}p^{\prime}(n)-4\tilde{n}\sqrt{4\log({k}n)p^{\prime}(n)}-8\tilde{n}\log(kn)}{(p^{\prime}(n)+\sqrt{4\log({k}n)p^{\prime}(n)}+4\log(kn))p^{\prime}(n)}$
$\displaystyle\geq\frac{p^{\prime}(n)-\sqrt{\tilde{n}}\sqrt{4\log({k}n)p^{\prime}(n)}-2\sqrt{\tilde{n}}\log(kn)}{(p^{\prime}(n)+\sqrt{4\log({k}n)p^{\prime}(n)}+4\log(kn))p^{\prime}(n)},$
$\displaystyle\geq\frac{p^{\prime}(n)-\sqrt{(1+1/C_{1})n/k}\sqrt{4\log({k}n)p^{\prime}(n)}-2\sqrt{(1+1/C_{1})n/k}\log(kn)}{(p^{\prime}(n)+\sqrt{4\log({k}n)p^{\prime}(n)}+4\log(kn))p^{\prime}(n)}.$

The last inequality works on event $\mathcal{E}_{v}$, by which we have
$\tilde{n}\leq\frac{2(C_{1}+1)n}{C_{1}k}$. Then,
$p^{\prime}(n)>Ck^{3}n\log(kn)$ gives us

$\displaystyle\mathbf{e}_{i}^{T}\mathbf{A}_{0}^{-1}\mathbf{v}_{k}$
$\displaystyle\geq\frac{p^{\prime}(n)-\sqrt{(1+1/C_{1})n/k}\sqrt{4/(Ck^{3}n)}p^{\prime}(n)-\sqrt{(1+1/C_{1})n/k}(2/Ck^{3}n)p^{\prime}(n)}{(p^{\prime}(n)+\sqrt{4\log({k}n)p^{\prime}(n)}+4\log(kn))p^{\prime}(n)}$
$\displaystyle\geq\frac{1-(1/(C_{2}\sqrt{k^{4}}))-(1/(C_{3}k^{3.5}\sqrt{n}))}{p^{\prime}(n)(1+2\sqrt{4/(Ck^{3}n)})}$
$\displaystyle\geq\frac{C_{4}-1}{C_{4}}\cdot\frac{1}{p},$

where in the last step we use the fact that $C,C_{2},C_{3}>1$ are large
enough. To upper bound $g_{(y_{i})i}^{(0)}$, we have with probability at least
$1-\frac{2}{k^{2}n^{2}}$,

$\displaystyle\mathbf{e}_{i}^{T}\mathbf{A}_{0}^{-1}\mathbf{v}_{k}$
$\displaystyle\leq\frac{1}{4\sqrt{\tilde{n}}}\left(\frac{2(\tilde{n}+\sqrt{\tilde{n}})}{(p^{\prime}(n)-\sqrt{4\log({k}n)p^{\prime}(n)})}-\frac{2(\tilde{n}-\sqrt{\tilde{n}})}{(p^{\prime}(n)+\sqrt{4\log({k}n)p^{\prime}(n)}+4\log({k}n))}\right)$
$\displaystyle\leq\frac{1}{4\sqrt{\tilde{n}}}\cdot\frac{4\sqrt{\tilde{n}}p^{\prime}(n)+4\tilde{n}\sqrt{4\log({k}n)p^{\prime}(n)}+8\tilde{n}\log(kn)}{(p^{\prime}(n)-\sqrt{4\log({k}n)p^{\prime}(n)})p^{\prime}(n)}$
$\displaystyle\leq\frac{p^{\prime}(n)+\sqrt{\tilde{n}}\sqrt{4\log({k}n)p^{\prime}(n)}+2\sqrt{\tilde{n}}\log(kn)}{(p^{\prime}(n)-\sqrt{4\log({k}n)p^{\prime}(n)})p^{\prime}(n)},$
$\displaystyle\leq\frac{p^{\prime}(n)+\sqrt{(1+1/C_{1})n/k}\sqrt{4\log({k}n)p^{\prime}(n)}+2\sqrt{(1+1/C_{1})n/k}\log(kn)}{(p^{\prime}(n)-\sqrt{4\log({k}n)p^{\prime}(n)})p^{\prime}(n)}.$

Then $p^{\prime}(n)>Ck^{3}n\log(kn)$ gives us

$\displaystyle\mathbf{e}_{i}^{T}\mathbf{A}_{0}^{-1}\mathbf{v}_{k}$
$\displaystyle\leq\frac{p^{\prime}(n)+\sqrt{(1+1/C_{1})n/k}\sqrt{4/(Ck^{3}n)}p^{\prime}(n)+2\sqrt{(1+1/C_{1})n/k}(4/Ck^{3}n)p^{\prime}(n)}{(p^{\prime}(n)-\sqrt{4\log({k}n)p^{\prime}(n)})p^{\prime}(n)}$
$\displaystyle\leq\frac{1+(1/(C_{2}\sqrt{k^{4}}))+(1/(C_{3}k^{3.5}\sqrt{n}))}{p^{\prime}(n)(1-2\sqrt{4/(Ck^{3}n)})}$
$\displaystyle\leq\frac{C_{4}+1}{C_{4}}\cdot\frac{1}{p}.$

We now upper and lower bound $g_{ji}^{(0)}$ for a fixed $j\neq y_{i}$. As
before, we have

$\displaystyle\mathbf{e}_{i}^{T}\mathbf{A}_{0}^{-1}\mathbf{v}_{j}=\frac{1}{4\sqrt{\tilde{n}}}\left((\mathbf{u}+\mathbf{v}_{j})^{T}\mathbf{A}_{0}^{-1}(\mathbf{u}+\mathbf{v}_{j})-(\mathbf{u}-\mathbf{v}_{j})^{T}\mathbf{A}_{0}^{-1}(\mathbf{u}-\mathbf{v}_{j})\right).$

Since $\mathbf{e}_{i}^{T}\mathbf{v}_{j}=0$, we now have
$\|{\mathbf{u}+\mathbf{v}_{j}}\|_{2}^{2}=\|{\mathbf{u}-\mathbf{v}_{j}}\|_{2}^{2}=2\tilde{n}$.
We apply Lemma 10 with $t=2\log(kn)$ to get, with probability at least
$1-\frac{2}{k^{2}n^{2}}$,

$\displaystyle\mathbf{e}_{i}^{T}\mathbf{A}_{0}^{-1}\mathbf{v}_{j}$
$\displaystyle\leq\frac{1}{4\sqrt{\tilde{n}}}\left(\frac{2\tilde{n}}{(p^{\prime}(n)-\sqrt{4\log({k}n)p^{\prime}(n)})}-\frac{2\tilde{n}}{(p^{\prime}(n)+\sqrt{4\log({k}n)p^{\prime}(n)}+4\log({k}n))}\right)$
$\displaystyle\leq\frac{1}{4\sqrt{\tilde{n}}}\cdot\frac{4\tilde{n}\sqrt{4\log({k}n)p^{\prime}(n)}+8\tilde{n}\log(kn)}{(p^{\prime}(n)-\sqrt{4\log({k}n)p^{\prime}(n)})p^{\prime}(n)}$
$\displaystyle\leq\frac{\sqrt{\tilde{n}}\sqrt{4\log({k}n)p^{\prime}(n)}+2\sqrt{\tilde{n}}\log(kn)}{(p^{\prime}(n)-\sqrt{4\log({k}n)p^{\prime}(n)})p^{\prime}(n)},$
$\displaystyle\leq\frac{\sqrt{(1+1/C_{1})n/k}\sqrt{4\log({k}n)p^{\prime}(n)}+2\sqrt{(1+1/C_{1})n/k}\log(kn)}{(p^{\prime}(n)-\sqrt{4\log({k}n)p^{\prime}(n)})p^{\prime}(n)}.$

The last inequality works on event $\mathcal{E}_{v}$, by which we have
$\tilde{n}\leq\frac{2(C_{1}+1)n}{C_{1}k}$. Then,
$p^{\prime}(n)>Ck^{3}n\log(kn)$ gives us

$\displaystyle\mathbf{e}_{i}^{T}\mathbf{A}_{0}^{-1}\mathbf{v}_{j}$
$\displaystyle\leq\frac{\sqrt{(1+1/C_{1})n/k}\sqrt{4/(Ck^{3}n)}p^{\prime}(n)+\sqrt{(1+1/C_{1})n/k}(2/Ck^{3}n)p^{\prime}(n)}{(p^{\prime}(n)-\sqrt{4\log({k}n)p^{\prime}(n)})p^{\prime}(n)}$
$\displaystyle\leq\frac{(1/(C_{2}\sqrt{k^{4}}))+(1/(C_{3}k^{3.5}\sqrt{n}))}{p^{\prime}(n)(1-\sqrt{4/(Ck^{3}n)})}$
$\displaystyle\leq\frac{C_{4}+1}{C_{4}}\cdot\frac{1}{k^{2}p},$

where in the last step we use the fact that $C,C_{2},C_{3}>1$ are large
enough. To lower bound $g_{ij}^{(0)}$, we have with probability at least
$1-\frac{2}{k^{2}n^{2}}$,

$\displaystyle\mathbf{e}_{i}^{T}\mathbf{A}_{0}^{-1}\mathbf{v}_{j}$
$\displaystyle\geq\frac{1}{4\sqrt{\tilde{n}}}\left(\frac{2\tilde{n}}{(p^{\prime}(n)+\sqrt{4\log({k}n)p^{\prime}(n)}+4\log(kn))}-\frac{2\tilde{n}}{(p^{\prime}(n)-\sqrt{4\log({k}n)p^{\prime}(n)})}\right)$
$\displaystyle\geq\frac{1}{4\sqrt{\tilde{n}}}\cdot\frac{-4\tilde{n}\sqrt{4\log({k}n)p^{\prime}(n)}-8\tilde{n}\log(kn)}{(p^{\prime}(n)-\sqrt{4\log({k}n)p^{\prime}(n)})p^{\prime}(n)}$
$\displaystyle\geq-\frac{\sqrt{\tilde{n}}\sqrt{4\log({k}n)p^{\prime}(n)}+2\sqrt{\tilde{n}}\log(kn)}{(p^{\prime}(n)-\sqrt{4\log({k}n)p^{\prime}(n)})p^{\prime}(n)},$
$\displaystyle\geq-\frac{\sqrt{(1+1/C_{1})n/k}\sqrt{4\log({k}n)p^{\prime}(n)}+2\sqrt{(1+1/C_{1})n/k}\log(kn)}{(p^{\prime}(n)-\sqrt{4\log({k}n)p^{\prime}(n)})p^{\prime}(n)}.$

Because $p^{\prime}(n)>Ck^{3}n\log(kn)$, we get

$\displaystyle\mathbf{e}_{i}^{T}\mathbf{A}_{0}^{-1}\mathbf{v}_{j}$
$\displaystyle\geq-\frac{\sqrt{(1+1/C_{1})n/k}\sqrt{4/(Ck^{3}n)}p^{\prime}(n)+\sqrt{(1+1/C_{1})n/k}(2/Ck^{3}n)p^{\prime}(n)}{(p^{\prime}(n)-\sqrt{4\log({k}n)p^{\prime}(n)})p^{\prime}(n)}$
$\displaystyle\geq-\frac{(1/(C_{2}\sqrt{k^{4}}))+(1/(C_{3}k^{3.5}\sqrt{n}))}{p^{\prime}(n)(1-\sqrt{4/(Ck^{3}n)})}$
$\displaystyle\geq-\frac{C_{4}+1}{C_{4}}\cdot\frac{1}{k^{2}p},$

where in the last step we use the fact that $C,C_{2},C_{3}>1$ are large
enough. We complete the proof by applying a union bounds over all $k$ classes
and $n$ training examples.

##  Appendix B Proof of Theorem 3

In this section, we provide the proof of Theorem 3, which was discussed in
Section 3.2.2. After having derived the interpolation condition in Equation
(12) for multiclass SVM, the proofs is in fact a rather simple extension of
the arguments provided in [MNS+21, HMX21] to the multiclass case. This is
unlike the GMM case that we considered in Section 6.2, which required
substantial additional effort over and above the binary case [WT21].

For this section, we define $\mathbf{A}=\mathbf{X}^{T}\mathbf{X}$ as shorthand
(we denoted the same quantity as $\mathbf{A}_{k}$ in Section 6.2). Recall that
the eigendecomposition of the covariance matrix is given by
$\boldsymbol{\Sigma}=\sum_{i=1}^{p}\lambda_{i}\mathbf{v}_{i}\mathbf{v}_{i}^{T}=\boldsymbol{V}\boldsymbol{\Lambda}\boldsymbol{V}^{T}$.
By rotation invariance of the standard normal variable, we can write
$\mathbf{A}=\mathbf{Q}^{T}\boldsymbol{\Lambda}\mathbf{Q}$, where the entries
of $\mathbf{Q}\in\mathbb{R}^{p\times n}$ are IID $\mathcal{N}(0,1)$ random
variables. Finally, recall that we denoted
$\boldsymbol{\lambda}=\begin{bmatrix}\lambda_{1}&\cdots&\lambda_{p}\end{bmatrix}$
and defined the effective dimensions
$d_{2}=\frac{\|\boldsymbol{\lambda}\|_{1}^{2}}{\|\boldsymbol{\lambda}\|_{2}^{2}}$
and
$d_{\infty}=\frac{\|\boldsymbol{\lambda}\|_{1}}{\|\boldsymbol{\lambda}\|_{\infty}}$.
Observe that Equation (12) in Theorem 1 is equivalent to the condition

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

We fix $c\in[k]$ and drop the subscript $c$, using $\overline{\mathbf{z}}$ to
denote the vector $\mathbf{z}_{c}$. We first provide a deterministic
equivalence to Equation (12) that resembles the condition provided in [HMX21,
Lemma 1]. Our proof is slightly modified compared to [HMX21, Lemma 1] and
relies on elementary use of block matrix inversion identity.

######  Lemma 11.

Let $\mathbf{Q}\in\mathbb{R}^{p\times
n}=[\mathbf{q}_{1},\cdots,\mathbf{q}_{n}]$. In our notation, Equation (12)
holds for a fixed $c$ if and only if:

$\displaystyle\frac{1}{z_{i}}\overline{\mathbf{z}}_{\setminus
i}^{T}\Big{(}\mathbf{Q}_{\setminus
i}^{T}\boldsymbol{\Lambda}\mathbf{Q}_{\setminus
i}\Big{)}^{-1}\mathbf{Q}_{\setminus
i}^{T}\boldsymbol{\Lambda}\mathbf{q}_{i}<1,~{}~{}\text{for
all}~{}~{}i=1,\cdots,n.$ (61)

Above, $\overline{\mathbf{z}}_{\setminus i}\in\mathbb{R}^{(n-1)\times 1}$ is
obtained by removing the $i$-th entry from vector $\overline{\mathbf{z}}$ and
$\mathbf{Q}_{\setminus i}\in\mathbb{R}^{d\times(n-1)}$ is obtained by removing
the $i$-th column from $\mathbf{Q}$.

###### Proof.

By symmetry, it suffices to consider the case $i=1$. We first write

$\displaystyle\mathbf{A}=\begin{bmatrix}\mathbf{q}_{1}^{T}\mathbf{\Lambda}\mathbf{q}_{1}&\mathbf{q}_{1}^{T}\mathbf{\Lambda}\mathbf{Q}_{\setminus
1}\\\ \mathbf{Q}_{\setminus
1}^{T}\mathbf{\Lambda}\mathbf{q}_{1}&\mathbf{Q}_{\setminus
1}^{T}\mathbf{\Lambda}\mathbf{Q}_{\setminus
1}\end{bmatrix}\triangleq\begin{bmatrix}\alpha&\mathbf{b}^{T}\\\
\mathbf{b}&\mathbf{D}\end{bmatrix}.$

By Schur complement [Ber09], we have

$\mathbf{A}\succ\mathbf{0}~{}\textit{iff}~{}\text{either}~{}\left\\{\alpha>0~{}\text{and}~{}\mathbf{D}-\frac{\mathbf{b}\mathbf{b}^{T}}{\alpha}\succ\mathbf{0}\right\\}~{}\text{or}~{}\left\\{\mathbf{D}\succ\mathbf{0}~{}\text{and}~{}\alpha-\mathbf{b}^{T}\mathbf{D}^{-1}\mathbf{b}>0\right\\}.$

Since the entries of $\mathbf{Q}$ are drawn from a continuous distribution
(IID standard Gaussian), both $\mathbf{A}$ and
$\mathbf{D}=\mathbf{Q}_{\setminus 1}^{T}\mathbf{\Lambda}\mathbf{Q}_{\setminus
1}$ are positive definite almost surely. Therefore,
$\alpha-\mathbf{b}^{T}\mathbf{D}^{-1}\mathbf{b}>0$ almost surely.

Thus, by block matrix inversion identity [Ber09], we have

$\displaystyle\mathbf{A}^{-1}=\begin{bmatrix}(\alpha-\mathbf{b}^{T}\mathbf{D}^{-1}\mathbf{b})^{-1}&-(\alpha-\mathbf{b}^{T}\mathbf{D}^{-1}\mathbf{b})^{-1}\mathbf{b}^{T}\mathbf{D}^{-1}\\\
-\mathbf{D}^{-1}\mathbf{b}(\alpha-\mathbf{b}^{T}\mathbf{D}^{-1}\mathbf{b})^{-1}&\mathbf{D}^{-1}+\mathbf{D}^{-1}\mathbf{b}(\alpha-\mathbf{b}^{T}\mathbf{D}^{-1}\mathbf{b})^{-1}\mathbf{b}^{T}\mathbf{D}^{-1}\end{bmatrix}.$

Therefore,$\mathbf{e}_{1}^{T}\mathbf{A}^{-1}=(\alpha-\mathbf{b}^{T}\mathbf{D}^{-1}\mathbf{b})^{-1}\begin{bmatrix}1&-\mathbf{b}^{T}\mathbf{D}^{-1}\end{bmatrix}.$
Hence we have

$\displaystyle
z_{1}\mathbf{e}_{1}^{T}\mathbf{A}^{-1}\overline{\mathbf{z}}=(\alpha-\mathbf{b}^{T}\mathbf{D}^{-1}\mathbf{b})^{-1}(z_{1}^{2}-\mathbf{b}^{T}\mathbf{D}^{-1}(z_{1}\overline{\mathbf{z}}_{\setminus
1})),$

where we use the fact that $\overline{\mathbf{z}}_{1}=z_{1}$. Since
$\alpha-\mathbf{b}^{T}\mathbf{D}^{-1}\mathbf{b}>0$ almost surely, we have

$\displaystyle z_{1}\mathbf{e}_{1}^{T}\mathbf{A}^{-1}\overline{\mathbf{z}}>0$
$\displaystyle\iff(\alpha-\mathbf{b}^{T}\mathbf{D}^{-1}\mathbf{b})^{-1}(z_{1}^{2}-\mathbf{b}^{T}\mathbf{D}^{-1}(z_{1}\overline{\mathbf{z}}_{\setminus
1}))>0$
$\displaystyle\iff\frac{1}{z_{1}}\mathbf{b}^{T}\mathbf{D}^{-1}\overline{\mathbf{z}}_{\setminus
1}<1.$

Recall that
$\mathbf{b}^{T}=\mathbf{q}_{1}^{T}\mathbf{\Lambda}\mathbf{Q}_{\setminus 1}$
and $\mathbf{D}=\mathbf{Q}_{\setminus
1}^{T}\mathbf{\Lambda}\mathbf{Q}_{\setminus 1}$. This completes the proof. ∎

Next, we define the following events:

  1. 1.

For $i\in[n]$,
$\mathcal{B}_{i}:=\Big{\\{}\frac{1}{z_{i}}\overline{\mathbf{z}}_{\setminus
i}^{T}\mathbf{A}_{\setminus i}^{-1}\mathbf{Q}_{\setminus
i}^{T}\boldsymbol{\Lambda}\mathbf{q}_{i}\geq 1\Big{\\}}$.

  2. 2.

For $i\in[n]$, given $t>0$,
$\mathcal{E}_{i}(t):=\Big{\\{}\|(\overline{\mathbf{z}}_{\setminus
i}^{T}\mathbf{A}_{\setminus i}^{-1}\mathbf{Q}_{\setminus
i}^{T}\boldsymbol{\Lambda})^{T}\|_{2}^{2}\geq\frac{1}{t}\Big{\\}}$.

  3. 3.

$\mathcal{B}:=\cup_{i=1}^{n}\mathcal{B}_{i}$.

We know all the data points are support vectors i.e., Equation (60) holds, if
none of the events $\mathcal{B}_{i}$ happens; hence, $\mathcal{B}$ is the
undesired event. We want to upper bound the probability of event
$\mathcal{B}$. As in the argument provided in [HMX21], we have

$\displaystyle\mathbb{P}(\mathcal{B})\leq\sum_{i=1}^{n}\Big{(}\mathbb{P}(\mathcal{B}_{i}|\mathcal{E}_{i}(t)^{c})+\mathbb{P}(\mathcal{E}_{i}(t))\Big{)}.$
(62)

The lemma below gives an upper bound on
$\mathbb{P}(\mathcal{B}_{i}|\mathcal{E}_{i}(t)^{c})$.

######  Lemma 12.

For any $t>0$, $\mathbb{P}(\mathcal{B}_{i}|\mathcal{E}_{i}(t)^{c})\leq
2\exp\left(-\frac{t}{2ck^{2}}\right)$.

###### Proof.

On the event $\mathcal{E}_{i}(t)^{c}$, we have
$\|(\overline{\mathbf{z}}_{\setminus i}^{T}\mathbf{A}_{\setminus
i}^{-1}\mathbf{Q}_{\setminus
i}^{T}\boldsymbol{\Lambda})^{T}\|_{2}^{2}\leq\frac{1}{t}$. Since, by its
definition, $|\frac{1}{z_{i}}|\leq k$, we have
$\frac{1}{z_{i}}\overline{\mathbf{z}}_{\setminus i}^{T}\mathbf{A}_{\setminus
i}^{-1}\mathbf{Q}_{\setminus i}^{T}\boldsymbol{\Lambda}\mathbf{q}_{i}$ is
conditionally sub-Gaussian [Wai19, Chapter 2] with parameter at most
$ck^{2}\|(\overline{\mathbf{z}}_{\setminus i}^{T}\mathbf{A}_{\setminus
i}^{-1}\mathbf{Q}_{\setminus i}^{T}\boldsymbol{\Lambda})^{T}\|_{2}^{2}\leq
ck^{2}/t$. Then the sub-Gaussian tail bound gives

$\displaystyle\mathbb{P}(\mathcal{B}_{i}|\mathcal{E}_{i}(t)^{c})\leq
2\exp\left(-\frac{t}{2ck^{2}}\right),$ (63)

which completes the prof. ∎

Next we upper bound $\mathbb{P}(\mathcal{E}_{i}(t))$ with $t=d_{\infty}/(2n)$.
Since $\|\mathbf{z}_{\setminus i}\|_{2}\leq\|\mathbf{y}_{\setminus i}\|_{2}$,
we can directly use [HMX21, Lemma 4].

######  Lemma 13 (Lemma 4, [HMX21]).

$\mathbb{P}\left(\mathcal{E}_{i}\left(\frac{d_{\infty}}{2n}\right)\right)\leq
2\cdot
9^{n-1}\cdot\exp\left(-c_{1}\min\left\\{\frac{d_{2}}{4c^{2}},\frac{d_{\infty}}{c}\right\\}\right)$.

The results above are proved for fixed choices of $i\in[n]$ and $c\in[k]$. We
combine Lemmas 12 and 13 with a union bound over all $n$ training examples and
$k$ classes to upper bound the probability of the undesirable event
$\mathcal{B}$ over all $k$ classes by:

$\displaystyle
kn9^{n-1}\cdot\exp\left(-c_{1}\min\left\\{\frac{d_{2}}{4c^{2}},\frac{d_{\infty}}{c}\right\\}\right)$
$\displaystyle\leq\exp\left(-c_{1}\min\left\\{\frac{d_{2}}{4c^{2}},\frac{d_{\infty}}{c}\right\\}+C_{1}\log(kn)+C_{2}n\right)$
$\displaystyle\text{and}~{}2kn\cdot\exp\left(-\frac{d_{\infty}}{2ck^{2}n}\right)$
$\displaystyle\leq\exp\left(-\frac{c_{2}d_{\infty}}{ck^{2}n}+C_{3}\log(kn)\right).$

Thus, the probability that every data point is a support vector is at least

$\displaystyle
1-\exp\left(-c_{1}\min\left\\{\frac{d_{2}}{4c^{2}},\frac{d_{\infty}}{c}\right\\}+C_{1}\log(kn)+C_{2}n\right)-\exp\left(-\frac{c_{2}d_{\infty}}{ck^{2}n}+C_{3}\log(kn)\right).$

To ensure that
$\exp\left(-c_{1}\min\left\\{\frac{d_{2}}{4c^{2}},\frac{d_{\infty}}{c}\right\\}+C_{1}\log(kn)+C_{2}n\right)+\exp\left(-\frac{c_{2}d_{\infty}}{ck^{2}n}+C_{3}\log(kn)\right)\leq\frac{c_{4}}{n}$,
we consider the conditions
$c_{1}\min\left\\{\frac{d_{2}}{4c^{2}},\frac{d_{\infty}}{c}\right\\}-C_{1}\log(kn)-C_{2}n\geq\log(n)$
and $\frac{c_{2}d_{\infty}}{ck^{2}n}-C_{3}\log(kn)\geq\log(n)$ to be
satisfied. These are equivalent to the conditions provided in Equation (17).
This completes the proof. Note that throughout the proof, we did not use any
generative model assumptions on the labels given the covariates, so in fact
our proof applies to scenarios beyond the MLM. ∎

##  Appendix C Classification error proofs

In this section, we provide the proofs of classification error of the MNI
under both GMM and MLM models. We begin with the proof for the GMM case
(Theorem 4).

###  C.1 Proof of Theorem 4

####  C.1.1 Proof strategy and notations

The notation and main arguments of this proof follow closely the content of
Section 6.2.

Our starting point here is the lemma below (adapted from [TOS20, D.10]) that
provides a simpler upper bound on the class-wise error $\mathbb{P}_{e|c}$.

######  Lemma 14.

Under GMM, $\mathbb{P}_{e|c}\leq\sum_{j\neq
c}Q\left(\frac{(\widehat{\mathbf{w}}_{c}-\widehat{\mathbf{w}}_{j})^{T}\boldsymbol{\mu}_{c}}{\|{\widehat{\mathbf{w}}_{c}-\widehat{\mathbf{w}}_{j}}\|_{2}}\right)$.
In particular, if
$(\widehat{\mathbf{w}}_{c}-\widehat{\mathbf{w}}_{j})^{T}\boldsymbol{\mu}_{c}>0$,
then $\mathbb{P}_{e|c}\leq\sum_{j\neq
c}\exp\left(-\frac{((\widehat{\mathbf{w}}_{c}-\widehat{\mathbf{w}}_{j})^{T}\boldsymbol{\mu}_{c})^{2}}{4(\widehat{\mathbf{w}}_{c}^{T}\widehat{\mathbf{w}}_{c}+\widehat{\mathbf{w}}_{j}^{T}\widehat{\mathbf{w}}_{j})}\right)$.

###### Proof.

[TOS20, D.10] shows $\mathbb{P}_{e|c}$ is upper bounded by $\sum_{j\neq
c}Q\left(\frac{(\widehat{\mathbf{w}}_{c}-\widehat{\mathbf{w}}_{j})^{T}\boldsymbol{\mu}_{c}}{\|{\widehat{\mathbf{w}}_{c}-\widehat{\mathbf{w}}_{j}}\|_{2}}\right)$.
Then if
$(\widehat{\mathbf{w}}_{c}-\widehat{\mathbf{w}}_{j})^{T}\boldsymbol{\mu}_{c}>0$,
the Chernoff bound [Wai19, Ch. 2] gives

$\displaystyle\mathbb{P}_{e|c}\leq\sum_{j\neq
c}\exp\left(-\frac{((\widehat{\mathbf{w}}_{c}-\widehat{\mathbf{w}}_{j})^{T}\boldsymbol{\mu}_{c})^{2}}{2\|{\widehat{\mathbf{w}}_{c}-\widehat{\mathbf{w}}_{j}}\|_{2}^{2}}\right)\leq\sum_{j\neq
c}\exp\left(-\frac{((\widehat{\mathbf{w}}_{c}-\widehat{\mathbf{w}}_{j})^{T}\boldsymbol{\mu}_{c})^{2}}{4(\widehat{\mathbf{w}}_{c}^{T}\widehat{\mathbf{w}}_{c}+\widehat{\mathbf{w}}_{j}^{T}\widehat{\mathbf{w}}_{j})}\right),$

where the last inequality uses the identity $\mathbf{a}^{T}\mathbf{b}\leq
2(\mathbf{a}^{T}\mathbf{a}+\mathbf{b}^{T}\mathbf{b})$. ∎

Thanks to Lemma 14, we can upper bound $P_{e|c}$ by lower bounding the terms

$\displaystyle\frac{((\widehat{\mathbf{w}}_{c}-\widehat{\mathbf{w}}_{j})^{T}\boldsymbol{\mu}_{c})^{2}}{(\widehat{\mathbf{w}}_{c}^{T}\widehat{\mathbf{w}}_{c}+\widehat{\mathbf{w}}_{j}^{T}\widehat{\mathbf{w}}_{j})},~{}~{}\text{for~{}all}~{}~{}c\neq
j\in[k].$ (64)

Our key observation is that this can be accomplished without the need to
control the more intricate cross-correlation terms
$\widehat{\mathbf{w}}_{c}^{T}\widehat{\mathbf{w}}_{j}$ for $c\neq j\in[k].$

Without loss of generality, we assume onwards that $c=k$ and $j=k-1$ (as in
Section 6.2). Similar to Section 6.2, the quadratic forms introduced in
Equation (39) play key role here, as well. For convenience, we recall the
definitions of the _$c$ -th order quadratic forms_ 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},$
$\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}.$

Further, recall that
$\widehat{\mathbf{w}}_{c}=\mathbf{X}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{v}_{c}$
and
$\mathbf{X}=\sum_{j=1}^{k}\boldsymbol{\mu}_{j}\mathbf{v}_{j}^{T}+\mathbf{Q}$.
Also, from orthogonality of the class mean vectors (Assumption 2), we have
$\boldsymbol{\mu}_{c}^{T}\mathbf{X}=\|{\boldsymbol{\mu}}\|_{2}^{2}\mathbf{v}_{c}^{T}+\mathbf{d}_{c}^{T}$.
Thus,

$\displaystyle\widehat{\mathbf{w}}_{c}^{T}\boldsymbol{\mu}_{c}-\widehat{\mathbf{w}}_{j}^{T}\boldsymbol{\mu}_{c}=\|{\boldsymbol{\mu}}\|_{2}^{2}\mathbf{v}_{c}^{T}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{v}_{c}+\mathbf{v}_{c}^{T}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{d}_{c}-\|{\boldsymbol{\mu}}\|_{2}^{2}\mathbf{v}_{c}^{T}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{v}_{j}-\mathbf{v}_{j}^{T}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{d}_{c}.$
(65)

Additionally,

$\displaystyle\widehat{\mathbf{w}}_{c}^{T}\widehat{\mathbf{w}}_{c}=\mathbf{v}_{c}^{T}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{v}_{c},~{}~{}\text{and}~{}~{}\widehat{\mathbf{w}}_{j}^{T}\widehat{\mathbf{w}}_{j}=\mathbf{v}_{j}^{T}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{v}_{j}.$

Using the leave-one-out trick in Section 6.2 and the matrix-inversion lemma,
we show in Appendix C.1.5 that

$\displaystyle~{}\eqref{eq:pfinnerratio}=\left(\frac{\|{\boldsymbol{\mu}}\|_{2}^{2}s_{cc}^{(j)}-s_{cc}^{(j)}t_{cc}^{(j)}+{h_{cc}^{(j)}}^{2}+h_{cc}^{(j)}-\|{\boldsymbol{\mu}}\|_{2}^{2}s_{jc}^{(j)}-h_{jc}^{(j)}-h_{jc}^{(j)}h_{cc}^{(j)}+s_{jc}^{(j)}t_{cc}^{(j)}}{\det_{j}}\right)^{2}\Big{/}\left(\frac{s_{cc}^{(j)}}{\det_{j}}+\frac{s_{jj}^{(-j)}}{\det_{-j}}\right),$
(66)

where
$\det_{j}=(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{cc}^{(j)})s_{cc}^{(j)}+({h_{cc}^{(j)}}+1)^{2}$.
Note that $\det_{j}=\det_{-c}$ when $c=k$ and $j=k-1$.

Next, we will prove that

$\displaystyle\eqref{eq:lowerquadratio}\geq\|{\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_{6}\left(\|{\boldsymbol{\mu}}\|_{2}^{2}+\frac{kp}{n}\right)}\,.$
(67)

####  C.1.2 Proof of Equation (67)

We will lower bound the numerator and upper bound the denominator of Equation
(66). We will work on the high-probability event $\mathcal{E}_{v}$ defined in
Equation (49) in Appendix A.1. For quadratic forms such as
$s_{cc}^{(j)},t_{cc}^{(j)}$ and $h_{cc}^{(j)}$, the Gram matrix
$\mathbf{A}_{j}^{-1}$ does not “include” the $c$-th mean component because we
have fixed $c=k,j=k-1$. Thus, we can directly apply Lemma 2 to get

$\displaystyle\frac{C_{1}-1}{C_{1}}\cdot\frac{n}{kp}\leq$ $\displaystyle
s_{cc}^{(j)}\leq\frac{C_{1}+1}{C_{1}}\cdot\frac{n}{kp},$ $\displaystyle
t_{cc}^{(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_{cc}^{(j)}\leq\tilde{\rho}_{n,k}\frac{C_{3}n\|{\boldsymbol{\mu}}\|_{2}}{\sqrt{k}p},$

on the event $\mathcal{E}_{v}$. We need some additional work to bound
$s_{jc}^{(j)}=\mathbf{v}_{j}\mathbf{A}_{j}^{-1}\mathbf{v}_{c}$ and
$h_{jc}^{(j)}=\mathbf{v}_{j}\mathbf{A}_{j}^{-1}\mathbf{d}_{c}$, since the Gram
matrix $\mathbf{A}_{j}^{-1}$ “includes” $\mathbf{v}_{j}$. The proof here
follows the machinery introduced in Appendix A.2 for proving Lemma 2. We
provide the core argument and refer the reader therein for additional
justifications. By Equation (77) in Appendix E.1 (with the index $j-1$
replacing the index $0$), we first have

$\displaystyle s_{jc}^{(j)}$
$\displaystyle=s_{jc}^{(j-1)}-\frac{1}{\det_{j-1}}(\star)_{s}^{(j-1)},$

where we define

$(\star)_{s}^{(j-1)}=(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{jj}^{(j-1)})s_{jj}^{(j-1)}s_{jc}^{(j-1)}+s_{jc}^{(j-1)}{h_{jj}^{(j-1)}}^{2}+s_{jc}^{(j-1)}h_{jj}^{(j-1)}+s_{jj}^{(j-1)}h_{jc}^{(j-1)},$

and
$\det_{j-1}=(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{jj}^{(j-1)})s_{jj}^{(j-1)}+({h_{jj}^{(j-1)}}+1)^{2}$.
Further, we have

$\displaystyle|s_{jc}^{(j)}|$
$\displaystyle=\left|\left(1-\frac{(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{jj}^{(j-1)})s_{jj}^{(j-1)}+{h_{jj}^{(j-1)}}^{2}}{\det_{j-1}}\right)s_{jc}^{(j-1)}-\frac{1}{\det_{j-1}}(s_{jc}^{(j-1)}h_{jj}^{(j-1)}+s_{jj}^{(j-1)}h_{jc}^{(j-1)})\right|$
$\displaystyle\leq\frac{1}{C}|s_{jc}^{(j-1)}|+\frac{1}{\det_{j-1}}|(s_{jc}^{(j-1)}h_{jj}^{(j-1)}+s_{jj}^{(j-1)}h_{jc}^{(j-1)})|.$

We focus on the dominant term $|s_{jj}^{(j-1)}h_{jc}^{(j-1)}|$. Using a
similar argument to that provided in Appendix A.2, we get

$\displaystyle\frac{|s_{jj}^{(j-1)}h_{jc}^{(j-1)}|}{\det_{j-1}}$
$\displaystyle\leq\frac{|s_{jj}^{(j-1)}h_{jc}^{(j-1)}|}{(1+{h_{jj}^{(j-1)}})^{2}}\leq\frac{C_{1}}{\left(1-\frac{C_{2}\tilde{\rho}_{n,k}\epsilon_{n}}{k^{2}\sqrt{n}}\right)^{2}}\cdot\frac{n}{kp}\cdot\frac{\tilde{\rho}_{n,k}\epsilon_{n}}{k^{2}\sqrt{n}}$
$\displaystyle\leq\frac{C_{3}\tilde{\rho}_{n,k}\epsilon_{n}}{\left(1-\frac{C_{2}\tilde{\rho}_{n,k}\epsilon_{n}}{k^{2}\sqrt{n}}\right)^{2}k^{2}}\cdot\frac{\sqrt{n}}{kp}.$

Thus, we have

$\displaystyle|s_{jc}^{(j-1)}|\leq\frac{C_{4}+1}{C_{4}}\cdot\frac{\sqrt{n}}{kp}.$

Similarly, we bound the remaining term $h_{jc}^{(j)}$. Specifically, by
Equation (79) in Section E.1, we have

$\displaystyle h_{jc}^{(j)}$
$\displaystyle=h_{jc}^{(j-1)}-\frac{1}{\det_{j-1}}(\star)_{h}^{(j-1)},$

where we define

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

Furthermore,

$\displaystyle|h_{jc}^{(j)}|$
$\displaystyle=\left|\left(1-\frac{(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{jj}^{(j-1)})s_{jj}^{(j-1)}+{h_{jj}^{(j-1)}}^{2}}{\det_{j-1}}\right)h_{jc}^{(j-1)}-\frac{1}{\det_{j-1}}(h_{jc}^{(j-1)}h_{jj}^{(j-1)}+s_{jj}^{(j-1)}t_{jc}^{(j-1)})\right|$
$\displaystyle\leq\frac{1}{C}|h_{jc}^{(j-1)}|+\frac{1}{\det_{j-1}}|(h_{jc}^{(j-1)}h_{jj}^{(j-1)}+s_{jj}^{(j-1)}t_{jc}^{(j-1)})|.$

We again consider the dominant term
$|s_{jj}^{(j-1)}t_{jc}^{(j-1)}|/\det_{j-1}$ and get

$\displaystyle\frac{|s_{jj}^{(j-1)}t_{jc}^{(j-1)}|}{\det_{j-1}}$
$\displaystyle\leq\frac{|s_{jj}^{(j-1)}t_{jc}^{(j-1)}|}{(1+{h_{jj}^{(j-1)}})^{2}}\leq\frac{C_{1}}{\left(1-\frac{C_{2}\tilde{\rho}_{n,k}\epsilon_{n}}{k^{2}\sqrt{n}}\right)^{2}}\cdot\frac{n}{kp}\cdot\frac{n\|{\boldsymbol{\mu}}\|_{2}^{2}}{p}$
$\displaystyle\leq\frac{C_{3}\epsilon_{n}}{\left(1-\frac{C_{2}\tilde{\rho}_{n,k}\epsilon_{n}}{k^{1.5}\sqrt{n}}\right)^{2}k^{2}\sqrt{n}}\cdot\frac{\tilde{\rho}_{n,k}n\|{\boldsymbol{\mu}}\|_{2}}{\sqrt{k}p}.$

Thus, we find that

$\displaystyle|h_{jc}^{(j-1)}|\leq\tilde{\rho}_{n,k}\frac{C_{4}n\|{\boldsymbol{\mu}}\|_{2}}{\sqrt{k}p}.$

We are now ready to lower bound the RHS in Equation (66) by lower bounding its
numerator and upper bounding its denominator.

First, for the numerator we have the following sequence of inequalities:

$\displaystyle\|{\boldsymbol{\mu}}\|_{2}^{2}s_{cc}^{(j)}-s_{cc}^{(j)}t_{cc}^{(j)}+{h_{cc}^{(j)}}^{2}+h_{cc}^{(j)}-\|{\boldsymbol{\mu}}\|_{2}^{2}s_{jc}^{(j)}-h_{jc}^{(j)}-h_{jc}^{(j)}h_{cc}^{(j)}+s_{jc}^{(j)}t_{cc}^{(j)}$
$\displaystyle\geq$
$\displaystyle\|{\boldsymbol{\mu}}\|_{2}^{2}s_{cc}^{(j)}-\|{\boldsymbol{\mu}}\|_{2}^{2}s_{jc}^{(j)}-s_{cc}^{(j)}t_{cc}^{(j)}+s_{jc}^{(j)}t_{cc}^{(j)}+h_{cc}^{(j)}-h_{jc}^{(j)}-h_{jc}^{(j)}h_{cc}^{(j)}$
$\displaystyle\geq$
$\displaystyle\frac{C_{1}-1}{C_{1}}\cdot\frac{\|{\boldsymbol{\mu}}\|_{2}^{2}n}{kp}-\frac{C_{2}+1}{C_{2}}\cdot\frac{\|{\boldsymbol{\mu}}\|_{2}^{2}\sqrt{n}}{kp}-\frac{C_{3}n}{p}\cdot\frac{\|{\boldsymbol{\mu}}\|_{2}^{2}n}{kp}-\frac{C_{4}n}{p}\cdot\frac{\|{\boldsymbol{\mu}}\|_{2}^{2}\sqrt{n}}{kp}-\frac{C_{5}\tilde{\rho}_{n,k}n\|{\boldsymbol{\mu}}\|_{2}}{\sqrt{k}p}.$

Above, we use the fact that the terms $|h_{cc}^{(j)}|,|h_{jc}^{(j)}|\leq
C\epsilon/(k^{2}\sqrt{n})$ are sufficiently small compared to $1$.
Consequently, the numerator is lower bounded by

$\displaystyle\left(\frac{C_{1}-1}{C_{1}}\cdot\frac{\|{\boldsymbol{\mu}}\|_{2}^{2}n}{kp}-\frac{C_{2}+1}{C_{2}}\cdot\frac{\|{\boldsymbol{\mu}}\|_{2}^{2}\sqrt{n}}{kp}-\frac{C_{3}n}{p}\cdot\frac{\|{\boldsymbol{\mu}}\|_{2}^{2}n}{kp}-\frac{C_{4}n}{p}\cdot\frac{\|{\boldsymbol{\mu}}\|_{2}^{2}\sqrt{n}}{kp}-\frac{C_{5}\tilde{\rho}_{n,k}n\|{\boldsymbol{\mu}}\|_{2}}{\sqrt{k}p}\right)^{2}\Big{/}\text{det}_{j}^{2}.$
(68)

Second, we upper bound the denominator. For this, note that under the
assumption of equal energy and equal priors on class means (Assumption 1),
there exist constants $C_{1},C_{2}>0$ such that
$C_{1}\leq\det_{j}/\det_{-j}\leq C_{2}$. (In fact, a very similar statement
was proved in Equation (44) and used in the proof of Theorem 2). Moreover,
Lemma 2 shows that the terms $s_{cc}^{(j)}$ and $s_{jj}^{(-j)}$ are of the
same order, so it suffices to upper bound $\frac{s_{cc}^{(j)}}{\det_{j}}$.
Again applying Lemma 2, we have

$\displaystyle\frac{s_{cc}^{(j)}}{\det_{j}}\leq\frac{C_{6}}{\det_{j}}\cdot\frac{n}{kp}\,$
(69)

on the event $\mathcal{E}_{v}$. Then, combining Equations (68) and (69) gives
us

$\displaystyle~{}\eqref{eq:lowerquadratio}$
$\displaystyle\geq\frac{n}{C_{0}kp}\cdot\frac{1}{\det_{j}}\left((1-\frac{C_{1}}{\sqrt{n}}-\frac{C_{2}n}{p})\|{\boldsymbol{\mu}}\|_{2}^{2}-C_{3}\min\\{\sqrt{k},\sqrt{\log(2n)}\\}\|{\boldsymbol{\mu}}\|_{2}\right)^{2}$
$\displaystyle\geq\frac{n}{C_{0}kp}\cdot\frac{1}{\frac{C_{4}\|{\boldsymbol{\mu}}\|_{2}^{2}n}{kp}+2+\frac{C_{5}n^{2}\|{\boldsymbol{\mu}}\|_{2}^{2}}{kp^{2}}}\left(\left(1-\frac{C_{1}}{\sqrt{n}}-\frac{C_{2}n}{p}\right)\|{\boldsymbol{\mu}}\|_{2}^{2}-C_{3}\min\\{\sqrt{k},\sqrt{\log(2n)}\\}\|{\boldsymbol{\mu}}\|_{2}\right)^{2}$
$\displaystyle\geq\|{\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_{6}\left(\|{\boldsymbol{\mu}}\|_{2}^{2}+\frac{kp}{n}\right)},$
(70)

where the second inequality follows from the following upper bound on
$\det_{j}$ on the event $\mathcal{E}_{v}$:

$\displaystyle\text{det}_{j}=(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{cc}^{(j)})s_{cc}^{(j)}+({h_{cc}^{(j)}}+1)^{2}\leq\|{\boldsymbol{\mu}}\|_{2}^{2}s_{cc}^{(j)}+2({h_{cc}^{(j)}}^{2}+1)\leq\frac{C_{4}\|{\boldsymbol{\mu}}\|_{2}^{2}n}{kp}+2+\frac{C_{5}n^{2}\|{\boldsymbol{\mu}}\|_{2}^{2}}{kp^{2}}.$

####  C.1.3 Completing the proof

Because of our assumption of equal energy on class means and equal priors, the
analysis above can be applied to bound
$\frac{((\widehat{\mathbf{w}}_{c}-\widehat{\mathbf{w}}_{j})^{T}\boldsymbol{\mu}_{c})^{2}}{(\widehat{\mathbf{w}}_{c}^{T}\widehat{\mathbf{w}}_{c}+\widehat{\mathbf{w}}_{j}^{T}\widehat{\mathbf{w}}_{j})}$,
for every $j\neq c$ and $c\in[k]$. We define the unconditional event

$\mathcal{E}_{u2}:=\left\\{\frac{((\widehat{\mathbf{w}}_{c}-\widehat{\mathbf{w}}_{j})^{T}\boldsymbol{\mu}_{c})^{2}}{(\widehat{\mathbf{w}}_{c}^{T}\widehat{\mathbf{w}}_{c}+\widehat{\mathbf{w}}_{j}^{T}\widehat{\mathbf{w}}_{j})}\text{
is lower bounded by}~{}\eqref{eq:lowerquadratio02}~{}\text{for every}~{}j\neq
c\right\\}.$

We have

$\displaystyle\mathbb{P}(\mathcal{E}_{u2}^{c})$
$\displaystyle\leq\mathbb{P}(\mathcal{E}_{u2}^{c}|\mathcal{E}_{v})+\mathbb{P}(\mathcal{E}_{v}^{c})$
$\displaystyle\leq\frac{c_{4}}{n}+c_{5}k(e^{-\frac{n}{c_{6}}}+e^{-\frac{n}{c_{7}k^{2}}})\leq\frac{c_{4}}{n}+c_{8}ke^{-\frac{n}{c_{7}k^{2}}}$

for constants $c_{i}$’s $>1$. Thus, the class-wise error $\mathbb{P}_{e|c}$ is
upper bounded by

$\displaystyle(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(\|{\boldsymbol{\mu}}\|_{2}^{2}+\frac{kp}{n}\right)}\right)}$

with probability at least $1-\frac{c_{4}}{n}-c_{8}ke^{-\frac{n}{c_{7}k^{2}}}$.
This completes the proof. ∎

####  C.1.4 Proof of Equation (66)

Here, using the results of Section E.1, we show how to obtain Equation (66)
from Equation (64). First, by [WT21, Appendix C.2] (with $\mathbf{y}$ replaced
by $\mathbf{v}_{m}$), we have

$\displaystyle\mathbf{v}_{m}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{v}_{m}=\frac{s_{mm}^{(-m)}}{\det_{-m}},~{}~{}\text{for~{}all}~{}~{}m\in[k],$

where
$\det_{-m}=(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{mm}^{(-m)})s_{mm}^{(-m)}+({h_{mm}^{(-m)}}+1)^{2}$.
Then [WT21, Equation (44)] gives

$\displaystyle\|{\boldsymbol{\mu}_{c}}\|_{2}^{2}\cdot\mathbf{v}_{c}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{v}_{c}+\mathbf{v}_{c}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{d}_{c}=\frac{\|{\boldsymbol{\mu}_{c}}\|_{2}^{2}s_{cc}^{(j)}-s_{cc}^{(j)}t_{cc}^{(j)}+{h_{cc}^{(j)}}^{2}+h_{cc}^{(j)}}{\det_{j}},$

where
$\det_{j}=(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{cc}^{(j)})s_{cc}^{(j)}+({h_{cc}^{(j)}}+1)^{2}$.
Note that $\det_{j}=\det_{-c}$ when $c=k$ and $j=k-1$.

For $\mathbf{v}_{c}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{v}_{j}$ and
$\mathbf{v}_{j}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{d}_{c}$, we can again
express the $k$-th order quadratic forms in terms of $j$-th order quadratic
forms as follows:

$\displaystyle\mathbf{v}_{c}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{v}_{j}$
$\displaystyle=\frac{s_{cj}^{(j)}+s_{cj}^{(j)}h_{cc}^{(j)}-s_{cc}^{(j)}h_{jc}^{(j)}}{\det_{j}},$
$\displaystyle\mathbf{v}_{j}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{d}_{c}$
$\displaystyle=\frac{\|{\boldsymbol{\mu}}\|_{2}^{2}s_{cc}^{(j)}h_{jc}^{(j)}-\|{\boldsymbol{\mu}}\|_{2}^{2}s_{cj}^{(j)}h_{cc}^{(j)}+h_{cc}^{(j)}h_{jc}^{(j)}+h_{jc}^{(j)}-s_{cj}^{(j)}t_{cc}^{(j)}}{\det_{j}}.$

Thus, we have

$\displaystyle\|{\boldsymbol{\mu}}\|_{2}^{2}\mathbf{v}_{c}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{v}_{j}+\mathbf{v}_{j}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{d}_{c}=\frac{\|{\boldsymbol{\mu}_{c}}\|_{2}^{2}s_{jc}^{(j)}+h_{jc}^{(j)}+h_{jc}^{(j)}h_{cc}^{(j)}-s_{jc}^{(j)}t_{cc}^{(j)}}{\det_{j}}.$

This completes the proof. ∎

####  C.1.5 Extensions to not-orthogonal means

While we made the orthogonality assumption on class means (Assumption 2) for
simplicity, our error analysis can conceivably be extended to the more general
unorthogonal setting. We provide a brief discussion of this extension here. To
upper bound the class-wise error $\mathbb{P}_{e|c}$, recall that we need to
lower bound the quantity in Equation (64). As with the orthogonal case, we
consider $c=k,j=k-1$ without loss of generality. Recall that
$\widehat{\mathbf{w}}_{c}=\mathbf{X}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{v}_{c}$
and
$\mathbf{X}=\sum_{j=1}^{k}\boldsymbol{\mu}_{j}\mathbf{v}_{j}^{T}+\mathbf{Q}$.
Thus

$\displaystyle\widehat{\mathbf{w}}_{c}^{T}\boldsymbol{\mu}_{c}$
$\displaystyle=\|{\boldsymbol{\mu}}\|_{2}^{2}\mathbf{v}_{c}^{T}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{v}_{c}+\sum_{m\neq
c}\boldsymbol{\mu}_{m}^{T}\boldsymbol{\mu}_{c}\mathbf{v}_{m}^{T}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{v}_{c}+\mathbf{v}_{c}^{T}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{d}_{c}\text{
and }$ $\displaystyle\widehat{\mathbf{w}}_{j}^{T}\boldsymbol{\mu}_{c}$
$\displaystyle=\|{\boldsymbol{\mu}}\|_{2}^{2}\mathbf{v}_{j}^{T}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{v}_{c}+\boldsymbol{\mu}_{j}^{T}\boldsymbol{\mu}_{c}\mathbf{v}_{j}^{T}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{v}_{j}+\sum_{m\neq
c,j}\boldsymbol{\mu}_{m}^{T}\boldsymbol{\mu}_{c}\mathbf{v}_{m}^{T}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{v}_{j}+\mathbf{v}_{j}^{T}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{d}_{c}.$

We have already obtained the bounds for
$\|{\boldsymbol{\mu}}\|_{2}^{2}\mathbf{v}_{c}^{T}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{v}_{c}+\mathbf{v}_{c}^{T}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{d}_{c}-\|{\boldsymbol{\mu}}\|_{2}^{2}\mathbf{v}_{c}^{T}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{v}_{j}-\mathbf{v}_{j}^{T}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{d}_{c}$
in Appendix C.1. Moreover, under the equal energy and priors assumption, the
$\mathbf{v}_{j}^{T}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{v}_{j}$ terms have
the same bound for every $j\in[k]$. Similarly, the
$\mathbf{v}_{j}^{T}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{v}_{m}$ terms also
have the same bound for all $j\neq m\in[k]$. An upper bound on classification
error can then be derived in terms of the inner products between the mean
vectors. We leave the detailed derivation to the reader. Expressions are
naturally more complicated.

###  C.2 Proof of Corollary 3

We now prove the condition for benign overfitting provided in Corollary 3.
Note that following Theorem 2, we assume that

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

We begin with the setting where
$\|{\boldsymbol{\mu}}\|_{2}^{2}>C\frac{kp}{n},\ \ \text{for some}\ \ C>1.$ In
this case, we get that Equation (70) is lower bounded by
$\frac{1}{c}{\left(\left(1-\frac{C_{3}}{\sqrt{n}}-\frac{C_{4}n}{p}\right)\|{\boldsymbol{\mu}}\|_{2}-C_{5}\sqrt{k}\right)^{2}},$
and we have

$\displaystyle{\left(\left(1-\frac{C_{3}}{\sqrt{n}}-\frac{C_{4}n}{p}\right)\|{\boldsymbol{\mu}}\|_{2}-C_{5}\sqrt{k}\right)^{2}}$
$\displaystyle>\|{\boldsymbol{\mu}}\|_{2}^{2}-2\|{\boldsymbol{\mu}}\|_{2}^{2}\frac{C_{3}}{\sqrt{n}}-2\|{\boldsymbol{\mu}}\|_{2}^{2}\frac{C_{4}n}{p}-2C_{5}\sqrt{k}\|{\boldsymbol{\mu}}\|_{2}$
$\displaystyle>\left(1-\frac{2C_{3}}{\sqrt{n}}\right)\frac{kp}{n}-2\|{\boldsymbol{\mu}}\|_{2}^{2}\frac{C_{4}n}{p}-2C_{5}\sqrt{k}\|{\boldsymbol{\mu}}\|_{2}.$
(72)

Then Equation (71) gives

$\displaystyle\eqref{eq:pfhighsnr02}$
$\displaystyle>\left(1-\frac{2C_{3}}{\sqrt{n}}\right)\frac{kp}{n}-\left(\frac{p}{k^{1.5}n^{1.5}}\right)^{2}\frac{C_{6}n}{p}-\frac{C_{7}\sqrt{k}p}{k^{1.5}n^{1.5}}$
$\displaystyle=\frac{kp}{n}\left(1-\frac{2C_{3}}{\sqrt{n}}-\frac{C_{6}}{k^{4}n}-\frac{C_{7}}{k^{2}\sqrt{n}}\right),$
(73)

which goes to $+\infty$ as $\left(\frac{p}{n}\right)\to\infty$.

Next, we consider the case $\|{\boldsymbol{\mu}}\|_{2}^{2}\leq\frac{kp}{n}$.
Moreover, we assume that
$\|{\boldsymbol{\mu}}\|_{2}^{4}=C_{2}\left(\frac{p}{n}\right)^{\alpha},$ for
$\alpha>1$. Then, Equation (70) is lower bounded by
$\frac{n}{ckp}\|{\boldsymbol{\mu}}\|_{2}^{4}\left(\left(1-\frac{C_{3}}{\sqrt{n}}-\frac{C_{4}n}{p}\right)-\frac{C_{5}\sqrt{k}}{\|{\boldsymbol{\mu}}\|_{2}}\right)^{2}$,
and we get

$\displaystyle\frac{n}{kp}\|{\boldsymbol{\mu}}\|_{2}^{4}\left(\left(1-\frac{C_{3}}{\sqrt{n}}-\frac{C_{4}n}{p}\right)-\frac{C_{5}\sqrt{k}}{\|{\boldsymbol{\mu}}\|_{2}}\right)^{2}$
$\displaystyle>\left(1-\frac{2C_{3}}{\sqrt{n}}\right)\frac{n}{kp}\|{\boldsymbol{\mu}}\|_{2}^{4}-\frac{C_{6}n^{2}}{kp^{2}}\|{\boldsymbol{\mu}}\|_{2}^{4}-\frac{C_{7}n}{\sqrt{k}p}\|{\boldsymbol{\mu}}\|_{2}^{3}$
$\displaystyle\geq\left(1-\frac{2C_{3}}{\sqrt{n}}\right)\frac{1}{k}\left(\frac{p}{n}\right)^{\alpha-1}-\frac{C_{6}}{k}\left(\frac{p}{n}\right)^{\alpha-2}-\frac{C_{7}}{\sqrt{k}}\left(\frac{p}{n}\right)^{0.75\alpha-1},$
(74)

where the last inequality uses Equations (71) and condition
$\|{\boldsymbol{\mu}}\|_{2}^{2}\leq\frac{kp}{n}$. Consequently, the RHS of
Equation (74) will go to $+\infty$ as $\left(\frac{p}{n}\right)\to\infty$,
provided that $\alpha>1$. Overall, it suffices to have

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

All of these inequalities hold provided that
$\|{\boldsymbol{\mu}}\|_{2}=\Theta(p^{\beta})$ for $\beta\in(1/4,1/2]$ for
finite $k$ and $n$. This completes the proof. ∎

##  Appendix D Lemmas used in error analysis of MLM

In this section, we collect the proofs of technical lemmas that are used in
the error analysis of MLM (proof of Theorem 5, provided in Section 6.3).
Before providing the proofs, we introduce notation that is specific to these
proofs. For a diagonal covariance matrix $\boldsymbol{\Sigma}$, we define the
leave-one-out covariance matrix $\boldsymbol{\Sigma}_{-1}$ as
$\boldsymbol{\Sigma}$ with the first row and column removed. Finally, for an
arbitrary PSD matrix $\boldsymbol{M}\in\mathbb{R}^{d\times d}$ with
eigenvalues ${\lambda}_{1},\ldots,{\lambda}_{d}$ and any index
$k\in\\{0,\ldots,d-1\\}$, the effective rank of the first kind (in the sense
of [BLLT20]) is defined as

$\displaystyle
r_{k}(\boldsymbol{M}):=\frac{1}{\lambda_{k+1}}\cdot\sum_{\ell=k+1}^{d}\lambda_{\ell}.$
(75)

###  D.1 Proof of Lemma 4

The proof of Lemma 4 follows similarly to the proof of Theorem 4 in Appendix
D.3 and Lemma 11 in Appendix E of [MNS+21], with the two important and
nontrivial extensions mentioned above: one, to the multiclass case involving
$k$ signal vectors, and two, considering the logistic model for label noise.
Without loss of generality999The reason this is without loss of generality is
because we can carry out the same analysis otherwise with the appropriate
permutation of the index labels., we assume for simplicity that $j_{c}=c$ for
all $c\in[k]$, and consider classes $c_{1}=1,c_{2}=2$ for the argument. First,
we consider the following adjusted orthonormal basis

$\displaystyle\boldsymbol{\widetilde{e}}_{1}$
$\displaystyle=\frac{(\boldsymbol{\mu}_{1}-\boldsymbol{\mu}_{2})}{\|\boldsymbol{\mu}_{1}-\boldsymbol{\mu}_{2}\|_{2}}$
$\displaystyle\boldsymbol{\widetilde{e}}_{2}$
$\displaystyle=\frac{(\boldsymbol{\mu}_{1}+\boldsymbol{\mu}_{2})}{\|\boldsymbol{\mu}_{1}+\boldsymbol{\mu}_{2}\|_{2}}$
$\displaystyle\boldsymbol{\widetilde{e}}_{j}$
$\displaystyle=\boldsymbol{{e}}_{j}\text{ for all }j\geq 3.$

This orthonormal basis together with the bilevel ensemble structure in
Definition 4 then gives us

$\displaystyle\mathsf{SU}_{c_{1},c_{2}}$
$\displaystyle=\frac{\sqrt{\lambda_{H}}}{\|\boldsymbol{\mu}_{1}-\boldsymbol{\mu}_{2}\|_{2}}\cdot(\boldsymbol{\mu}_{1}-\boldsymbol{\mu}_{2})^{\top}(\widehat{\mathbf{w}}_{1}-\widehat{\mathbf{w}}_{2})$
$\displaystyle=\sqrt{\lambda_{H}}\cdot\boldsymbol{\widetilde{e}}_{1}^{\top}\mathbf{X}(\mathbf{X}^{\top}\mathbf{X})^{-1}(\mathbf{v}_{1}-\mathbf{v}_{2}),$

where the last step follows via the closed-form expression of the MNI. Next,
we define $\mathbf{A}:=\mathbf{X}^{\top}\mathbf{X}$ and define
$\widetilde{\mathbf{u}}_{j}:=\frac{1}{\sqrt{\lambda_{j}}}\mathbf{X}^{\top}\boldsymbol{\widetilde{e}}_{j}$
for all $j=1,\ldots,p$. Clearly, we can write
$\mathbf{A}=\sum_{j=1}^{p}\lambda_{j}\mathbf{z}_{j}\mathbf{z}_{j}^{\top}$;
moreover, we can verify that $\widetilde{\mathbf{u}}_{j}\text{ i.i.d
}\sim\mathcal{N}(0,I_{n})$. (This uses again the rotational invariance of
Gaussianity and the bilevel ensemble structure, again.) Finally, we denote the
“leave-one-out” matrix _corresponding to the changed basis_ by
$\mathbf{A}_{-1}:=\sum_{j=2}^{p}\lambda_{j}\widetilde{\mathbf{u}}_{j}\widetilde{\mathbf{u}}_{j}^{\top}$,
and denote $\mathbf{y}_{1}:=\mathbf{v}_{1}-\mathbf{v}_{2}$ as shorthand.

Using the above notation, we can then write
$\mathsf{SU}_{c_{1},c_{2}}=\lambda_{H}\cdot\widetilde{\mathbf{u}}_{1}^{\top}\mathbf{A}^{-1}\mathbf{y}_{1}$.
Consequently, an identical leave-one-out analysis to the one provided in
[MNS+21, Theorem 4] gives us

$\displaystyle\mathsf{SU}_{c_{1},c_{2}}=\frac{\lambda_{H}\cdot\widetilde{\mathbf{u}}_{1}^{\top}\mathbf{A}_{-1}^{-1}\mathbf{y}_{1}}{1+\lambda_{H}\cdot\widetilde{\mathbf{u}}_{1}^{\top}\mathbf{A}_{-1}^{-1}\mathbf{y}_{1}}.$

As with the proof of Theorem 4 in [MNS+21], we can bound the quadratic forms
around their expectations by using the Hanson-Wright inequality [RV+13],
thereby getting

$\displaystyle\mathsf{SU}_{c_{1},c_{2}}$ $\displaystyle\geq
c(k)\cdot\frac{\lambda_{H}\left(\frac{(n-s)}{c\lambda_{L}r_{s}(\boldsymbol{\Sigma}_{-1})}-\frac{c_{3}n^{3/4}}{\lambda_{L}r_{s}(\boldsymbol{\Sigma})}\right)}{1+\lambda_{H}\left(\frac{cn}{\lambda_{L}r_{s}(\boldsymbol{\Sigma}_{-1})}+\frac{c_{4}n^{3/4}}{\lambda_{L}r_{s}(\boldsymbol{\Sigma})}\right)}\text{
and }$ $\displaystyle\mathsf{SU}_{c_{1},c_{2}}$ $\displaystyle\leq
c(k)\cdot\frac{\lambda_{H}\left(\frac{cn}{\lambda_{L}r_{s}(\boldsymbol{\Sigma}_{-1})}+\frac{c_{3}n^{3/4}}{\lambda_{L}r_{s}(\boldsymbol{\Sigma})}\right)}{1+\lambda_{H}\left(\frac{(n-s)}{c\lambda_{L}r_{s}(\boldsymbol{\Sigma}_{-1})}-\frac{c_{4}n^{3/4}}{\lambda_{L}r_{s}(\boldsymbol{\Sigma})}\right)},$

Above, we define $c(k):=\mathbb{E}[\tilde{u}_{1,i}y_{1,i}]$ and
$\tilde{u}_{1,i},y_{1,i}$ denote the $i$-th entries of
$\widetilde{\mathbf{u}}_{1},\mathbf{y}_{1}$ respectively. Also recall the
definitions of the effective rank $r_{k}(\boldsymbol{\Sigma})$ and the leave-
one-out matrix $\boldsymbol{\Sigma}_{-1}$. Plugging this into an identical
argument as in the proof of Lemma 11 in Appendix E of [MNS+21] gives us the
statement of Lemma 4.

It remains to show that the constant $c(k)$ is strictly positive, and does not
depend on $n$ or $p$ (but will, in general, depend on the number of classes
$k$). To do this, we critically utilize the orthogonality and equal-weight
Assumption 5 as well as the details of the MLM. We denote
$\mathbf{u}_{j}:=\mathbf{X}^{\top}\boldsymbol{{e}}_{j}$, and it can be
verified that $\widetilde{\mathbf{u}}_{j}=\mathbf{u}_{j}$ for all $j\geq 3$,
and
$\widetilde{\mathbf{u}}_{1}=\frac{1}{\sqrt{2}}(\mathbf{u}_{1}-\mathbf{u}_{2})$
and
$\widetilde{\mathbf{u}}_{2}=\frac{1}{\sqrt{2}}(\mathbf{u}_{1}+\mathbf{u}_{2})$.
We now use the simplex-ETF-type structure of $\mathbf{v}_{1},\mathbf{v}_{2}$
together with the structure in the MLM model to get

$\displaystyle\mathbb{P}\left(y_{1,i}=1\Big{|}\\{u_{1,i},u_{2,i},\ldots,u_{k,i}\\}\right)$
$\displaystyle=\frac{\exp(u_{1,i})}{\sum_{c^{\prime}\in[k]}\exp(u_{c^{\prime},i})}\text{
and }$
$\displaystyle\mathbb{P}\left(y_{1,i}=-1\Big{|}\\{u_{1,i},u_{2,i},\ldots,u_{k,i}\right)$
$\displaystyle=\frac{\exp(u_{2,i})}{\sum_{c^{\prime}\in[k]}\exp(u_{c^{\prime},i})},$

and $y_{1,i}=0$ otherwise. Note here that $\\{u_{c,i}\\}_{c\in[k]}$ are IID
standard Gaussian. Thus, we get

$\displaystyle c(k):=\mathbb{E}[\tilde{u}_{1,i}y_{1,i}]$
$\displaystyle=\frac{1}{\sqrt{2}}\cdot\mathbb{E}\left[(u_{1,i}-u_{2,i})\cdot\frac{\exp(u_{1,i})}{\sum_{c^{\prime}\in[k]}\exp(u_{c^{\prime},i})}-(u_{1,i}-u_{2,i})\cdot\frac{\exp(u_{2,i})}{\sum_{c^{\prime}\in[k]}\exp(u_{j_{c^{\prime},i}})}\right]$
$\displaystyle=\frac{1}{\sqrt{2}}\cdot\mathbb{E}\left[(U_{1}-U_{2})\cdot\frac{(e^{U_{1}}-e^{U_{2}})}{\sum_{c=1}^{k}e^{U_{c}}}\right]$
$\displaystyle=\sqrt{2}\cdot\mathbb{E}\left[U_{1}\cdot\frac{(e^{U_{1}}-e^{U_{2}})}{\sum_{c=1}^{k}e^{U_{c}}}\right],$

where the last step follows by symmetry. Note that we have overloaded notation
and written $U_{c}:=u_{c,i}$ for each $c\in[k]$. We also write
$\mathbf{U}:=\begin{bmatrix}U_{1}&\ldots&U_{k}\end{bmatrix}$ as shorthand.
Note that $U_{c}\text{ i.i.d. }\sim\mathcal{N}(0,1)$. This gives us
$c(k)=\mathbb{E}\left[U_{1}\cdot g(\mathbf{U})\right]$ where we write
$g(\mathbf{U}):=\frac{e^{U_{1}}-e^{U_{2}}}{\sum_{c=1}^{k}e^{U_{c}}}$. Then,
applying Stein’s lemma, we get

$\displaystyle\mathbb{E}\left[U_{1}\cdot g(\mathbf{U})\right]$
$\displaystyle=\sum_{i=1}^{n}\mathbb{E}[U_{1}U_{i}]\cdot\mathbb{E}\left[\frac{\partial
g}{\partial U_{i}}\right]$ $\displaystyle=\mathbb{E}\left[\frac{\partial
g}{\partial U_{1}}\right]$ $\displaystyle=\mathbb{E}\left[\frac{\sum_{i\geq
3}e^{U_{1}+U_{i}}+2e^{U_{1}+U_{2}}}{(\sum_{i=1}^{k}e^{U_{i}})^{2}}\right]>0.$

The last step follows because the argument inside the expectation can never
take value $0$ and is always non-negative. This completes the proof. ∎

###  D.2 Proof of Lemma 5

This proof is a simple extension of the argument in [MNS+21, Theorem 5] using
the same change-of-basis argument that we used to characterize the survival.
As with the proof of Lemma 4, we assume without loss of generality that
$c_{1}=1,c_{2}=2$. First, we recall that

$\displaystyle\widehat{\boldsymbol{\Delta}}_{c_{1},c_{2}}:=\mathbf{X}(\mathbf{X}^{T}\mathbf{X})^{-1}(\mathbf{v}_{1}-\mathbf{v}_{2})=\mathbf{X}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{y}_{1}.$

As a direct consequence (following the proof of [MNS+21, Lemma 6]), we get

$\displaystyle\mathsf{CN}_{c_{1},c_{2}}$
$\displaystyle=\sqrt{\mathbf{y}_{1}^{\top}\mathbf{C}\mathbf{y}_{1}},\text{
where }$ $\displaystyle\mathbf{C}$
$\displaystyle:=(\mathbf{X}^{T}\mathbf{X})^{-1}\left(\sum_{j=1,j\neq
1}^{d}\lambda_{j}^{2}\widetilde{\mathbf{u}}_{j}\widetilde{\mathbf{u}}_{j}^{\top}\right)(\mathbf{X}^{T}\mathbf{X})^{-1}$

and recall that $\\{\widetilde{\mathbf{u}}_{j}\\}_{j=1}^{p}$ is as defined in
the proof of Lemma 4. Recall that we also defined
$\mathbf{A}:=\mathbf{X}^{T}\mathbf{X}$ for shorthand, and
$\mathbf{A}_{-1}:=\sum_{j=1,j\neq
j_{c}}^{d}\lambda_{j}\widetilde{\mathbf{u}}_{j}\widetilde{\mathbf{u}}_{j}^{\top}$
as the “leave-one-out” matrix101010Note that these matrices are functionals of
the training data covariates, and so are common across all classes.. Further,
again following the proof of [MNS+21, Lemma 6], we get

$\displaystyle\mathsf{CN}_{c_{1},c_{2}}$
$\displaystyle=\sqrt{\widetilde{\mathbf{z}}_{1}^{\top}\widetilde{\mathbf{C}}\widetilde{\mathbf{z}}_{1}},\text{
where }$ $\displaystyle\widetilde{\mathbf{z}}_{1}$
$\displaystyle:=\mathbf{y}_{1}-\mathsf{SU}_{c_{1},c_{2}}\widetilde{\mathbf{u}}_{1}\text{
and }$ $\displaystyle\widetilde{\mathbf{C}}$
$\displaystyle:=(\mathbf{A}_{-1})^{-1}\left(\sum_{j=1,j\neq
1}^{d}\lambda_{j}^{2}\widetilde{\mathbf{u}}_{j}\widetilde{\mathbf{u}}_{j}^{\top}\right)(\mathbf{A}_{-1})^{-1}$

Now, an identical argument to the proof of [MNS+21, Lemma 29] gives us

$\displaystyle\widetilde{\mathbf{z}}_{1}^{\top}\widetilde{\mathbf{C}}\widetilde{\mathbf{z}}_{1}$
$\displaystyle\leq
2\mathbf{y}_{1}^{\top}\widetilde{\mathbf{C}}\mathbf{y}_{1}+2\mathsf{SU}_{c_{1},c_{2}}^{2}\cdot\widetilde{\mathbf{u}}_{1}^{\top}\widetilde{\mathbf{C}}\widetilde{\mathbf{u}}_{1}$
$\displaystyle\leq
4\text{Tr}(\widetilde{\mathbf{C}})\left(1+\frac{1}{c}\right)\cdot\log n,$

where $c$ is some universal positive constant. The last inequality follows as
a critical consequence of three facts:

  1. 1.

We have $\mathsf{SU}_{c_{1},c_{2}}\leq 1$ almost surely.

  2. 2.

Noting that $\widetilde{\mathbf{u}}_{1}$ is isotropic Gaussian, we have
$\widetilde{\mathbf{u}}_{1}^{\top}\widetilde{\mathbf{C}}\widetilde{\mathbf{u}}_{1}\leq
2\text{Tr}(\widetilde{\mathbf{C}})\left(1+\frac{1}{c}\right)\cdot\log n$ with
high probability from an application of the Hanson-Wright inequality [RV+13].

  3. 3.

Noting that the Hanson-Wright inequality also applies to sub-Gaussian random
vectors with uncorrelated components [RV+13], we similarly apply it to
$\mathbf{y}_{1}$ by noting that $y_{1,i}^{2}\leq 1$ and
$\mathbb{E}[y_{1,i}y_{1,i^{\prime}}]=0$ for all $i\neq i^{\prime}$). The
latter equality is a consequence of the independence of the training examples
(therefore,
$\mathbb{E}[y_{1,i}y_{1,i^{\prime}}]=\mathbb{E}[y_{1,i}]\cdot\mathbb{E}[y_{1,i^{\prime}}]$)
and the fact that the covariates $\mathbf{x}$ are zero-mean, which leads to
$\mathbb{E}[y_{1,i}]=0$ for any $i\in[n]$.

After this, an analysis identical to that of the binary case (contained in
Appendices D.4.2 and Lemma 13 of [MNS+21]) completes the proof of the result.
∎

##  Appendix E Recursive formulas for higher-order quadratic forms

We first show how quadratic forms involving the $j$-th order Gram matrix
$\mathbf{A}_{j}^{-1}$ can be expressed using quadratic forms involving the
$(j-1)$-th order Gram matrix $\mathbf{A}_{j-1}^{-1}$. For concreteness, we
consider $j=1$; identical expressions hold for any $j>1$ with the only change
being in the superscripts. Recall from Section 6.2 that we can write

$\displaystyle\mathbf{A}_{1}$
$\displaystyle=\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}=\mathbf{Q}^{T}\mathbf{Q}+\begin{bmatrix}\|{\boldsymbol{\mu}}\|_{2}\mathbf{v}_{1}&\mathbf{d}_{1}&\mathbf{v}_{1}\end{bmatrix}\begin{bmatrix}\|{\boldsymbol{\mu}}\|_{2}\mathbf{v}_{1}^{T}\\\
\mathbf{v}_{1}^{T}\\\ \mathbf{d}_{1}^{T}\end{bmatrix}.$

The first step is to derive an expression for $\mathbf{A}_{1}^{-1}$. By the
Woodbury identity [HJ12], we get

$\mathbf{A}_{1}^{-1}=\mathbf{A}_{0}^{-1}-\mathbf{A}_{0}^{-1}\begin{bmatrix}\|{\boldsymbol{\mu}}\|_{2}\mathbf{v}_{1}&\mathbf{d}_{1}&\mathbf{v}_{1}\end{bmatrix}\begin{bmatrix}\mathbf{I}+\begin{bmatrix}\|{\boldsymbol{\mu}}\|_{2}\mathbf{v}_{1}^{T}\\\
\mathbf{v}_{1}^{T}\\\
\mathbf{d}_{1}^{T}\end{bmatrix}\mathbf{A}_{0}^{-1}\begin{bmatrix}\|{\boldsymbol{\mu}}\|_{2}\mathbf{v}_{1}&\mathbf{d}_{1}&\mathbf{v}_{1}\end{bmatrix}\end{bmatrix}^{-1}\begin{bmatrix}\|{\boldsymbol{\mu}}\|_{2}\mathbf{v}_{1}^{T}\\\
\mathbf{v}_{1}^{T}\\\ \mathbf{d}_{1}^{T}\end{bmatrix}\mathbf{A}_{0}^{-1}.$
(76)

We first compute the inverse of the $3\times 3$ matrix
$\mathbf{B}:=\begin{bmatrix}\mathbf{I}+\begin{bmatrix}\|{\boldsymbol{\mu}}\|_{2}\mathbf{v}_{1}^{T}\\\
\mathbf{v}_{1}^{T}\\\
\mathbf{d}_{1}^{T}\end{bmatrix}\mathbf{A}_{0}^{-1}\begin{bmatrix}\|{\boldsymbol{\mu}}\|_{2}\mathbf{v}_{1}&\mathbf{d}_{1}&\mathbf{v}_{1}\end{bmatrix}\end{bmatrix}$.
Recalling our definitions of the terms $s_{mj}^{(c)},h_{mj}^{(c)}$ and
$t_{mj}^{(c)}$ in Equation (39) in Section 6.2, we have:

$\displaystyle\mathbf{B}=\begin{bmatrix}1+\|{\boldsymbol{\mu}}\|_{2}^{2}s_{11}^{(0)}&\|{\boldsymbol{\mu}}\|_{2}h_{11}^{(0)}&\|{\boldsymbol{\mu}}\|_{2}s_{11}^{(0)}\\\
\|{\boldsymbol{\mu}}\|_{2}s_{11}^{(0)}&1+h_{11}^{(0)}&s_{11}^{(0)}\\\
\|{\boldsymbol{\mu}}\|_{2}h_{11}^{(0)}&t_{11}^{(0)}&1+h_{11}^{(0)}\end{bmatrix}.$

Recalling $\mathbf{B}^{-1}=\frac{1}{\det_{0}}\text{adj}(\mathbf{B})$, where
$\det_{0}$ is the determinant of $\mathbf{B}$ and $\text{adj}(\mathbf{B})$ is
the adjoint of $\mathbf{B}$, simple algebra gives us

$\displaystyle\text{det}_{0}=s_{11}^{(0)}(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)})+(h_{11}^{(0)}+1)^{2},$

and

$\displaystyle\text{adj}(\mathbf{B})=\begin{bmatrix}(h_{11}^{(0)}+1)^{2}-s_{11}^{(0)}t_{11}^{(0)}&\|{\boldsymbol{\mu}}\|_{2}(s_{11}^{(0)}t_{11}^{(0)}-h_{11}^{(0)}-{h_{11}^{(0)}}^{2})&-\|{\boldsymbol{\mu}}\|_{2}s_{11}^{(0)}\\\
-\|{\boldsymbol{\mu}}\|_{2}s_{11}^{(0)}&h_{11}^{(0)}+1+\|{\boldsymbol{\mu}}\|_{2}^{2}s_{11}^{(0)}&-s_{11}^{(0)}\\\
\|{\boldsymbol{\mu}}\|_{2}(s_{11}^{(0)}t_{11}^{(0)}-h_{11}^{(0)}-{h_{11}^{(0)}}^{2})&\|{\boldsymbol{\mu}}\|_{2}^{2}{h_{11}^{(0)}}^{2}-t_{11}^{(0)}(1+\|{\boldsymbol{\mu}}\|_{2}^{2}s_{11}^{(0)})&h_{11}^{(0)}+1+\|{\boldsymbol{\mu}}\|_{2}^{2}s_{11}^{(0)}\end{bmatrix}.$

We will now use these expressions to derive expressions for the $1$-order
quadratic forms that are used in Appendix A.2.

###  E.1 Expressions for 1-st order quadratic forms

We now show how quadratic forms of order $1$ can be expressed as a function of
quadratic forms of order $0$. All of the expressions are derived as a
consequence of plugging in the expression for $\mathbf{B}^{-1}$ together with
elementary matrix algebra.

First, we have

$\displaystyle
s_{mk}^{(1)}=\mathbf{v}_{m}^{T}\mathbf{A}_{1}^{-1}\mathbf{v}_{k}$
$\displaystyle=\mathbf{v}_{m}^{T}\mathbf{A}_{0}^{-1}\mathbf{v}_{k}-\begin{bmatrix}\|{\boldsymbol{\mu}}\|_{2}s_{m1}^{(0)}&h_{m1}^{(0)}&s_{m1}^{(0)}\end{bmatrix}\frac{\text{adj}(\mathbf{B})}{\det_{0}}\begin{bmatrix}\|{\boldsymbol{\mu}}\|_{2}s_{k1}^{(0)}\\\
s_{k1}^{(0)}\\\ h_{k1}^{(0)}\end{bmatrix}$
$\displaystyle=s_{mk}^{(0)}-\frac{1}{\det_{0}}(\star)_{s}^{(0)},$ (77)

where we define

$\displaystyle(\star)_{s}^{(0)}$
$\displaystyle:=(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)})s_{1k}^{(0)}s_{1m}^{(0)}+s_{1m}^{(0)}h_{k1}^{(0)}h_{11}^{(0)}+s_{1k}^{(0)}h_{m1}^{(0)}h_{11}^{(0)}-s_{11}^{(0)}h_{k1}^{(0)}h_{m1}^{(0)}+s_{1m}^{(0)}h_{k1}^{(0)}+s_{1k}^{(0)}h_{m1}^{(0)}.$

Thus, for the case $m=k$ we have

$\displaystyle
s_{kk}^{(1)}=\mathbf{v}_{k}^{T}\mathbf{A}_{1}^{-1}\mathbf{v}_{k}$
$\displaystyle=\mathbf{v}_{k}^{T}\mathbf{A}_{0}^{-1}\mathbf{v}_{k}-\begin{bmatrix}\|{\boldsymbol{\mu}}\|_{2}s_{k1}^{(0)}&h_{k1}^{(0)}&s_{k1}^{(0)}\end{bmatrix}\frac{\text{adj}(\mathbf{B})}{\det_{0}}\begin{bmatrix}\|{\boldsymbol{\mu}}\|_{2}s_{k1}^{(0)}\\\
s_{k1}^{(0)}\\\ h_{k1}^{(0)}\end{bmatrix}$
$\displaystyle=s_{kk}^{(0)}-\frac{1}{\det_{0}}\Big{(}(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)}){s_{1k}^{(0)}}^{2}+2s_{1k}^{(0)}{h_{k1}^{(0)}}h_{11}^{(0)}-s_{11}^{(0)}{h_{k1}^{(0)}}^{2}+2s_{1k}^{(0)}h_{k1}^{(0)}\Big{)}.$
(78)

Next, we have

$\displaystyle
h_{mk}^{(1)}=\mathbf{v}_{m}^{T}\mathbf{A}_{1}^{-1}\mathbf{d}_{k}$
$\displaystyle=\mathbf{v}_{m}^{T}\mathbf{A}_{0}^{-1}\mathbf{d}_{k}-\begin{bmatrix}\|{\boldsymbol{\mu}}\|_{2}s_{m1}^{(0)}&h_{m1}^{(0)}&s_{m1}^{(0)}\end{bmatrix}\frac{\text{adj}(\mathbf{B})}{\det_{0}}\begin{bmatrix}\|{\boldsymbol{\mu}}\|_{2}h_{1k}^{(0)}\\\
h_{1k}^{(0)}\\\ t_{1k}^{(0)}\end{bmatrix}$
$\displaystyle=h_{mk}^{(0)}-\frac{1}{\det_{0}}(\star)_{h}^{(0)},$ (79)

where we define

$(\star)_{h}^{(0)}=(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)})s_{1m}^{(0)}h_{1k}^{(0)}+h_{m1}^{(0)}h_{1k}^{(0)}h_{11}^{(0)}+h_{m1}^{(0)}h_{1k}^{(0)}+s_{1m}^{(0)}t_{k1}^{(0)}+s_{1m}^{(0)}t_{k1}^{(0)}h_{11}^{(0)}-s_{11}^{(0)}t_{k1}^{(0)}h_{m1}^{(0)}.$

Next, we have

$\displaystyle
t_{km}^{(1)}=\mathbf{d}_{k}^{T}\mathbf{A}_{1}^{-1}\mathbf{d}_{m}$
$\displaystyle=\mathbf{d}_{k}^{T}\mathbf{A}_{0}^{-1}\mathbf{d}_{m}-\begin{bmatrix}\|{\boldsymbol{\mu}}\|_{2}h_{1k}^{(0)}&t_{1k}^{(0)}&h_{1k}^{(0)}\end{bmatrix}\frac{\text{adj}(\mathbf{B})}{\det_{0}}\begin{bmatrix}\|{\boldsymbol{\mu}}\|_{2}h_{1m}^{(0)}\\\
h_{1m}^{(0)}\\\ t_{1m}^{(0)}\end{bmatrix}$
$\displaystyle=t_{km}^{(0)}-\frac{1}{\det_{0}}(\star)_{t}^{(0)},$ (80)

where we define

$(\star)_{t}^{(0)}=(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)})h_{1m}^{(0)}h_{1k}^{(0)}+t_{m1}^{(0)}h_{1k}^{(0)}h_{11}^{(0)}+t_{k1}^{(0)}h_{1m}^{(0)}h_{11}^{(0)}+t_{1m}^{(0)}h_{1k}^{(0)}+t_{1k}^{(0)}h_{1m}^{(0)}-s_{11}^{(0)}t_{1m}^{(0)}t_{1k}^{(0)}.$

Thus, for the case $m=k$ we have

$\displaystyle
t_{kk}^{(1)}=\mathbf{d}_{k}^{T}\mathbf{A}_{1}^{-1}\mathbf{d}_{k}$
$\displaystyle=\mathbf{d}_{k}^{T}\mathbf{A}_{0}^{-1}\mathbf{d}_{k}-\begin{bmatrix}\|{\boldsymbol{\mu}}\|_{2}h_{1k}^{(0)}&t_{1k}^{(0)}&h_{1k}^{(0)}\end{bmatrix}\frac{\text{adj}(\mathbf{B})}{\det_{0}}\begin{bmatrix}\|{\boldsymbol{\mu}}\|_{2}h_{1k}^{(0)}\\\
h_{1k}^{(0)}\\\ t_{1k}^{(0)}\end{bmatrix}$
$\displaystyle=t_{kk}^{(0)}-\frac{1}{\det_{0}}\Big{(}(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)}){h_{1k}^{(0)}}^{2}+2t_{1k}^{(0)}{h_{1k}^{(0)}}h_{11}^{(0)}-s_{11}^{(0)}{t_{1k}^{(0)}}^{2}+2t_{1k}^{(0)}h_{1k}^{(0)}\Big{)}.$
(81)

Next, we have

$\displaystyle
f_{ki}^{(1)}=\mathbf{d}_{k}^{T}\mathbf{A}_{1}^{-1}\mathbf{e}_{i}$
$\displaystyle=\mathbf{d}_{k}^{T}\mathbf{A}_{0}^{-1}\mathbf{e}_{i}-\begin{bmatrix}\|{\boldsymbol{\mu}}\|_{2}h_{1k}^{(0)}&t_{1k}^{(0)}&h_{1k}^{(0)}\end{bmatrix}\frac{\text{adj}(\mathbf{B})}{\det_{0}}\begin{bmatrix}\|{\boldsymbol{\mu}}\|_{2}g_{1i}^{(0)}\\\
g_{1i}^{(0)}\\\ f_{1i}^{(0)}\end{bmatrix}$
$\displaystyle=f_{ki}^{(0)}-\frac{1}{\det_{0}}(\star)_{f}^{(0)},$ (82)

where we define

$(\star)_{f}^{(0)}=(\|{\boldsymbol{\mu}}\|_{2}^{2}-t_{11}^{(0)})h_{1k}^{(0)}g_{1i}^{(0)}+t_{1k}^{(0)}g_{1i}^{(0)}+t_{1k}^{(0)}h_{11}^{(0)}g_{1i}^{(0)}+h_{1k}^{(0)}f_{1i}^{(0)}+h_{1k}^{(0)}h_{11}^{(0)}f_{1i}^{(0)}-s_{11}^{(0)}t_{1k}^{(0)}f_{1i}^{(0)}.$

Finally, we have

$\displaystyle
g_{ji}^{(1)}=\mathbf{v}_{j}^{T}\mathbf{A}_{1}^{-1}\mathbf{e}_{i}$
$\displaystyle=\mathbf{v}_{j}^{T}\mathbf{A}_{0}^{-1}\mathbf{e}_{i}-\begin{bmatrix}\|{\boldsymbol{\mu}}\|_{2}s_{j1}^{(0)}&h_{j1}^{(0)}&s_{j1}^{(0)}\end{bmatrix}\frac{\text{adj}(\mathbf{B})}{\det_{0}}\begin{bmatrix}\|{\boldsymbol{\mu}}\|_{2}g_{1i}^{(0)}\\\
g_{1i}^{(0)}\\\ f_{1i}^{(0)}\end{bmatrix}$
$\displaystyle=g_{ji}^{(0)}-\frac{1}{\det_{0}}(\star)_{gj}^{(0)},$ (83)

where we define

$(\star)_{gj}^{(0)}=(\|\boldsymbol{\mu}\|_{2}^{2}-t_{11}^{(0)})s_{1j}^{(0)}g_{1i}^{(0)}+g_{1i}^{(0)}h_{11}^{(0)}h_{j1}^{(0)}+g_{1i}^{(0)}h_{j1}^{(0)}+s_{1j}^{(0)}f_{1i}^{(0)}+s_{1j}^{(0)}h_{11}^{(0)}f_{1i}^{(0)}-s_{11}^{(0)}h_{j1}^{(0)}f_{1i}^{(0)}.$

∎

##  Appendix F One-vs-all SVM

In this section, we derive conditions under which the OvA solutions
$\mathbf{w}_{{\rm OvA},c}$ interpolate, i.e, all data points are support
vectors in Equation (8).

###  F.1 Gaussian mixture model

As in the case of the multiclass SVM, we assume equal priors on the class
means and equal energy (Assumption 1).

######  Theorem 6.

Assume that the training set follows a multiclass GMM with noise covariance
$\boldsymbol{\Sigma}=\mathbf{I}_{p}$ and Assumption 1 holds. Then, there exist
constants $c_{1},c_{2},c_{3}>1$ and $C_{1},C_{2}>1$ such that the solutions of
the OvA-SVM and MNI are identical with probability at least
$1-\frac{c_{1}}{n}-c_{2}ke^{-\frac{n}{c_{3}k^{2}}}$ provided that

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

We can compare Equation (84) with the corresponding condition for multiclass
SVM in Theorem 2 (Equation (16)). Observe that the right-hand-side of Equation
(84) above does not scale with $k$, while the right-hand-side of Equation (16)
scales with $k$ as $k^{3}$. Otherwise, the scalings with $n$ and energy of
class means $\|\boldsymbol{\mu}\|_{2}$ are identical. This discrepancy with
respect to $k$-dependence arises because the multiclass SVM is equivalent to
the OvA-SVM in Equation (33) with unequal margins $1/k$ and $(k-1)/k$ (as we
showed in Theorem 1).

###### Proof sketch..

Recall from Section 6.2 that we derived conditions under which the multiclass
SVM interpolates the training data by studying the related symmetric OvA-type
classifier defined in Equation (15). Thus, this proof is similar to the proof
of Theorem 2 provided in Section 6.2. The only difference is that the margins
for the OvA-SVM are not $1/k$ and $(k-1)/k$, but $1$ for all classes. Owing to
the similarity between the arguments, we restrict ourselves to a proof sketch
here.

Following Section 6.2 and Equation (45), we consider $y_{i}=k$. We will derive
conditions under which the condition

$\displaystyle\big{(}(1+h_{kk}^{(-k)})g_{ki}^{(-k)}-s_{kk}^{(-k)}f_{ki}^{(-k)}\big{)}+C\sum_{j\neq
k}\big{(}(1+h_{jj}^{(-j)})g_{ji}^{(-j)}-s_{jj}^{(-j)}f_{ji}^{(-j)}\big{)}>0,$
(85)

holds with high probability for some $C>1$. We define

$\displaystyle\epsilon:=\frac{n^{1.5}\|{\boldsymbol{\mu}}\|_{2}}{p}\leq\tau,$

where $\tau$ is chosen to be a sufficiently small constant. Applying the same
trick as in Lemma 2 (with the newly defined parameters $\epsilon$ and $\tau$)
gives us with probability at least
$1-\frac{c_{1}}{n}-c_{2}ke^{-\frac{n}{c_{3}k^{2}}}$:

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

for some constants $C_{i}$’s $>1$. We used the fact that
$|g_{ji}^{(0)}|\leq(1/C)(1/(kp))$ for $j\neq y_{i}$ with probability at least
$1-\frac{c_{1}}{n}-c_{2}ke^{-\frac{n}{c_{3}k^{2}}}$ provided that
$p>C_{1}kn\log(kn)+n-1$, which is the first sufficient condition in the
theorem statement. ∎

###  F.2 Multinomial logistic model

Recall that we defined the data covariance matrix
$\boldsymbol{\Sigma}=\sum_{i=1}^{p}\lambda_{i}\mathbf{v}_{i}\mathbf{v}_{i}^{T}=\boldsymbol{V}\boldsymbol{\Lambda}\boldsymbol{V}^{T}$
and its spectrum
$\boldsymbol{\lambda}=\begin{bmatrix}\lambda_{1}&\cdots&\lambda_{p}\end{bmatrix}$.
We also defined the effective dimensions
$d_{2}:=\frac{\|\boldsymbol{\lambda}\|_{1}^{2}}{\|\boldsymbol{\lambda}\|_{2}^{2}}$
and
$d_{\infty}:=\frac{\|\boldsymbol{\lambda}\|_{1}}{\|\boldsymbol{\lambda}\|_{\infty}}$.

The following result provides sufficient conditions under which the OvA SVM
and MNI classifier have the same solution with high probability under the MLM.

######  Theorem 7.

Assume that the training set follows a multiclass MLM. There exist constants
$c$ and $C_{1},C_{2}>1$ such that, if the following conditions hold:

$\displaystyle
d_{\infty}>C_{1}n\log(kn)~{}~{}\text{and}~{}~{}d_{2}>C_{2}(\log(kn)+n),$ (87)

the solutions of the OvA-SVM and MNI are identical with probability at least
$(1-\frac{c}{n})$. In the special case of isotropic covariance, the same
result holds provided that

$\displaystyle p>10n\log(\sqrt{k}n)+n-1,$ (88)

Comparing this result to the corresponding results in Theorems 3, we observe
that $k$ now only appears in the $\log$ function (as a result of $k$ union
bounds). Thus, the unequal $1/k$ and $(k-1)/k$ margins that appear in the
multiclass-SVM make interpolation harder than with the OvA-SVM, just as in the
GMM case.

###### Proof sketch..

For the OvA SVM classifier, we need to solve $k$ binary max-margin
classification problems, hence the proof follows directly from [MNS+21,
Theorem 1] and [HMX21, Theorem 1] by applying $k$ union bounds. We omit the
details for brevity. ∎

## One-vs-one SVM

In this section, we first derive conditions under which the OvO solutions
interpolate, i.e, all data points are support vectors. We then provide an
upper bound on the classification error of the OvO solution.

In OvO classification, we solve $k(k-1)/2$ binary classification problems,
e.g., for classes pair $(c,j)$, we solve

$\displaystyle\mathbf{w}_{{\rm
OvO},(c,j)}:=\arg\min_{\mathbf{w}}\|{\mathbf{w}}\|_{2}\quad\text{sub.
to}~{}~{}\mathbf{w}^{T}\mathbf{x}_{i}\geq
1,~{}\text{if}~{}\mathbf{y}_{i}=c;~{}~{}\mathbf{w}^{T}\mathbf{x}_{i}\leq-1~{}\text{if}~{}\mathbf{y}_{i}=j,~{}\forall
i\in[n].$ (89)

Then we apply these $k(k-1)/2$ classifiers to a fresh sample and the class
that got the highest $+1$ voting gets predicted.

We now present conditions under which every data point becomes a support
vector over these $k(k-1)/2$ problems. We again assume equal priors on the
class means and equal energy (Assumption 1).

######  Theorem 8.

Assume that the training set follows a multiclass GMM with noise covariance
$\boldsymbol{\Sigma}=\mathbf{I}_{p}$ and Assumption 1 holds. Then, there exist
constants $c_{1},c_{2},c_{3}>1$ and $C_{1},C_{2}>1$ such that the solutions of
the OvA-SVM and MNI are identical with probability at least
$1-\frac{c_{1}}{n}-c_{2}ke^{-\frac{n}{c_{3}k^{2}}}$ provided that

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

###### Proof sketch.

Note that the margins of OvO SVM are $1$ and $-1$, hence the proof is similar
to the proof of Theorem 6. Recall that in OvO SVM, we solve $k(k-1)/2$ binary
problems and each problems has sample size $2n/k$ with high probability.
Therefore, compared to OvA SVM which solves $k$ problems each with sample size
$n$, OvO SVM needs less overparameterization to achieve interpolation. Thus
the first condition in Equation (84) reduces to $p>C_{1}n\log(kn)+(2n/k)-1$. ∎

We now derive the classification risk for OvO SVM classifiers. Recall that OvO
classification solves $k(k-1)/2$ binary subproblems. Specifically, for each
pair of classes, say $(i,j)\in[k]\times[k]$, we train a classifier
$\mathbf{w}_{ij}\in\mathbb{R}^{p}$ and the corresponding decision rule for a
fresh sample $\mathbf{x}\in\mathbb{R}^{p}$ is
$\hat{y}_{ij}=\text{sign}(\mathbf{x}^{T}\hat{\mathbf{w}}_{ij})$. Overall, each
class $i\in[k]$ gets a voting score $s_{i}=\sum_{j\neq
i}\mathbf{1}_{\hat{y}_{ij}=+1}$. Thus, the final decision is given by majority
rule that _decides the class with the highest score_ , i.e.,
$\arg\max_{i\in[k]}s_{i}$. Having described the classification process, the
total classification error $\mathbb{P}_{e}$ for balanced classes is given by
the conditional error $\mathbb{P}_{e|c}$ given the fresh sample belongs to
class $c$. Without loss of generality, we assume $c=1$. Formally,
$\mathbb{P}_{e}=\mathbb{P}_{e|1}=\mathbb{P}_{e|1}(s_{1}<s_{2}~{}\text{or}~{}s_{1}<s_{3}~{}\text{or}\cdots\text{or}~{}s_{1}<s_{k})$.
Under the equal prior and energy assumption, by symmetry and union bound, the
conditional classification risk given that true class is $1$ can be upper
bounded as:

$\displaystyle\mathbb{P}_{e|1}(s_{1}<s_{2}~{}\text{or}~{}s_{1}<s_{3}~{}\text{or}\cdots\text{or}~{}s_{1}<s_{k})\leq\mathbb{P}_{e|1}(s_{1}<k-1)=\mathbb{P}_{e|1}(\exists
j~{}s.t.~{}\hat{y}_{1j}\neq 1)\leq(k-1)\mathbb{P}_{e|1}(\hat{y}_{12}\neq 1).$

Therefore, it suffices to bound $\mathbb{P}_{e|1}(y_{12}\neq 1)$. We can
directly apply Theorem 4 with changing $k$ to $2$ and $n$ to $2n/k$.

######  Theorem 9.

Let Assumption 2 and the condition in Equation (90) hold. Further assume
constants $C_{1},C_{2},C_{3}>1$ such that
$\big{(}1-C_{1}\sqrt{\frac{k}{n}}-\frac{C_{2}n}{kp}\big{)}\|{\boldsymbol{\mu}}\|_{2}>C_{3}.$
Then, there exist additional constants $c_{1},c_{2},c_{3}$ and $C_{4}>1$ such
that the OvO SVM solutions satisfies:

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

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