conditional errors of the two classes. But, how to best choose $\delta$ to
achieve that? That is, how to find
$\arg\min_{\delta}\mathcal{R}_{+}(\delta)+\mathcal{R}_{-}(\delta)$ where
$\mathcal{R}_{\pm}(\delta):=\mathcal{R}_{\pm}\big{(}(\hat{\mathbf{w}}_{\delta},\hat{b}_{\delta})\big{)}$?
Thanks to Theorem 2, we can substitute this hard, data-dependent parameter
optimization problem with an analytic form that only depends on the problem
parameters $\pi,\gamma$ and $\mathbf{M}$. Specifically, we seek to solve the
following optimization problem

$\displaystyle\arg\min_{\delta>0}~{}Q(\mathbf{e}_{1}^{T}\mathbf{V}\mathbf{S}\bm{\rho}_{\delta}+b_{\delta}/q_{\delta})+Q(-\mathbf{e}_{2}^{T}\mathbf{V}\mathbf{S}\bm{\rho}_{\delta}-b_{\delta}/q_{\delta})$
sub. to $(q_{\delta},\bm{\rho}_{\delta},b_{\delta})$ defined as (42). (31)

Compared to the original data-dependent problem, the optimization above has
the advantage that it is explicit in terms of the problem parameters. However,
as written, the optimization is still cumbersome as even a grid search over
possible values of $\delta$ requires solving the non-linear equation (42) for
each candidate value of $\delta$. Instead, we can exploit a structural
property of CS-SVM (see Lemma 2 in Section E.2) to rewrite (31) in a more
convenient form. Specifically, we will show in Section E.3 that (31) is
equivalent to the following _explicit minimization_ :

$\displaystyle\arg\min_{\delta>0}~{}Q\Big{(}\ell_{+}+\big{(}\frac{\delta-1}{\delta+1}\big{)}{q_{1}^{-1}}\Big{)}+Q\Big{(}\ell_{-}-\big{(}\frac{\delta-1}{\delta+1}\big{)}{q_{1}^{-1}}\Big{)},$
(32)

where we defined
$\ell_{+}:=\mathbf{e}_{1}^{T}\mathbf{V}\mathbf{S}\bm{\rho}_{1}+b_{1}/q_{1},~{}\ell_{-}:=-\mathbf{e}_{2}^{T}\mathbf{V}\mathbf{S}\bm{\rho}_{1}-b_{1}/q_{1}$,
and, $(q_{1},\bm{\rho}_{1},b_{1})$ are as defined in Theorem 2 for $\delta=1$.
In other words, $(q_{1},\bm{\rho}_{1},b_{1})$ are the parameters related to
the standard hard-margin SVM, for which the balanced error is then given by
$\left(Q(\ell_{+})+Q(\ell_{-})\right)\big{/}2$. To summarize, we have shown
that one can optimally tune $\delta$ to minimize the _asymptotic_ balanced
error by minimizing the objective in (32) that only depends on the parameters
$(q_{1},\bm{\rho}_{1},b_{1})$ characterizing the asymptotic performance of
SVM. In fact, we obtain explicit formulas for the optimal value
$\delta_{\star}$ in (32) as follows

$\displaystyle\delta_{\star}:=({\ell_{-}-\ell_{+}+2q_{1}^{-1}})\big{/}{\left(\ell_{+}-\ell_{-}+2q_{1}^{-1}\right)_{+}},$
(33)

where it is understood that when the denominator is zero (i.e.
$\ell_{+}-\ell_{-}+2q_{1}^{-1}\leq 0$) then $\delta_{\star}\rightarrow\infty$.
When $\ell_{+}-\ell_{-}+2q_{1}^{-1}>0$, setting $\delta=\delta_{\star}$ in (4)
not only achieves minimum balanced error among all other choices of $\delta$,
but also it achieves perfect balancing between the conditional errors of the
two classes, i.e.
$\mathcal{R}_{+}=\mathcal{R}_{-}=Q(\frac{\ell_{-}+\ell_{+}}{2}).$

Formally, we have the following result.

######  Theorem 6 (Optimal tuning of CS-SVM).

Fix $\gamma>\gamma_{\star}$. Let $\overline{\mathcal{R}}_{\text{bal}}(\delta)$
denote the asymptotic balanced error of the CS-SVM with margin-ratio parameter
$\delta>0$ as specified in Theorem 2. Further let
$(q_{1},\bm{\rho}_{1},b_{1})$ the solution to (42) for $\delta=1$. Finally,
define

$\ell_{+}:=\mathbf{e}_{1}^{T}\mathbf{V}\mathbf{S}\bm{\rho}_{1}+b_{1}/q_{1},\quad\ell_{-}:=-\mathbf{e}_{2}^{T}\mathbf{V}\mathbf{S}\bm{\rho}_{1}-b_{1}/q_{1},$

Then, for all $\delta>0$ it holds that

$\overline{\mathcal{R}}_{\text{bal}}(\delta)\geq\overline{\mathcal{R}}_{\text{bal}}(\delta_{\star})$

where $\delta_{\star}$ is defined as

$\displaystyle\delta_{\star}=\begin{cases}\frac{\ell_{-}-\ell_{+}+2q_{1}^{-1}}{\ell_{+}-\ell_{-}+2q_{1}^{-1}}&\text{if
}\ell_{+}+\ell_{-}\geq 0\text{ and }\ell_{+}-\ell_{-}+2q_{1}^{-1}>0,\\\
\rightarrow\infty&\text{if }\ell_{+}+\ell_{-}\geq 0\text{ and
}\ell_{+}-\ell_{-}+2q_{1}^{-1}\leq 0,\\\ \rightarrow 0&\text{if
}\ell_{+}+\ell_{-}<0.\end{cases}$ (34)

Specifically, if $\ell_{+}+\ell_{-}\geq 0$ and
$\ell_{+}-\ell_{-}+2q_{1}^{-1}>0$ hold, then the following two hold: (i)
$\overline{\mathcal{R}}_{\text{bal}}(\delta_{\star})=Q\left(\left({\ell_{-}+\ell_{+}}\right)\big{/}{2}\right)$,
and, (ii) the asymptotic conditional errors are equal, i.e.
$\mathcal{R}_{+}(\delta_{\star})=\mathcal{R}_{-}(\delta_{\star}).$

See Figures 15(c) and 16 for numerical illustrations of the formula in Theorem
6, specifically how $\delta_{\star}$ depends on $\pi$ and $\gamma$.

####  E.1.1 Data-dependent heuristic to estimate $\delta_{\star}$

It is natural to ask if formula (34) can be used for tuning in practice. To
answer this, observe that evaluating the formula requires knowledge of the
true means, which are typically unknown. In this section, we propose a _data-
dependent heuristic_ to estimate $\delta_{\star}$. More generally, tuning
$\delta$ (or $\Delta_{y}$ in VS-loss) requires a train-validation split by
creating a balanced validation set from the original training data which would
help assess balanced risk. Since there is only a single hyperparameter we
expect this approach to work well with fairly small validation data (without
hurting the minority class sample size).

Recall from Equation (33) that
$\delta_{\star}:=({\ell_{-}-\ell_{+}+2q_{1}^{-1}})\big{/}{\left(\ell_{+}-\ell_{-}+2q_{1}^{-1}\right)_{+}},$
where
$\ell_{+}:=\mathbf{e}_{1}^{T}\mathbf{V}\mathbf{S}\bm{\rho}_{1}+b_{1}/q_{1}$
and
$\ell_{-}:=-\mathbf{e}_{2}^{T}\mathbf{V}\mathbf{S}\bm{\rho}_{1}-b_{1}/q_{1}$.
Also, according to Theorem 2 and for $\delta=1$ it holds that

$\displaystyle(\|\hat{\mathbf{w}}_{1}\|_{2},{\hat{\mathbf{w}}_{1}^{T}\bm{\mu}_{+}}/{\|\hat{\mathbf{w}}_{1}\|_{2}},{\hat{\mathbf{w}}_{1}^{T}\bm{\mu}_{-}}/{\|\hat{\mathbf{w}}_{1}\|_{2}},\hat{b}_{1})\stackrel{{\scriptstyle{P}}}{{\longrightarrow}}(q_{1},\mathbf{e}_{1}^{T}\mathbf{V}\mathbf{S}\bm{\rho}_{1},\mathbf{e}_{2}^{T}\mathbf{V}\mathbf{S}\bm{\rho}_{1},b_{1}).$
(35)

The first key observation here is that $\hat{\mathbf{w}}_{1},\hat{b}_{1}$ are
the solutions to SVM, thus they are data-dependent quantities to which we have
access to. Hence, we can simply run SVM and estimate $q_{1}$ and $b_{1}$ using
Equation (35). Unfortunately, to further estimate $\bm{\rho}_{1}$ we need
knowledge of the data means. When this is not available, we propose
approximating the data means by a simple average of the features, essentially
pretending that the data follow a GMM.

Concretely, our recipe for approximating the optimal $\delta$ is as follows.
First, using the training set we calculate the empirical means for the two
classes, $\tilde{\bm{\mu}}_{+}$ and $\tilde{\bm{\mu}}_{-}$. (Ideally, this can
be done on a balanced validation set.) Then, we train standard SVM on the same
set of data and keep track of the coefficients $\hat{\mathbf{w}}_{1}$ and the
intercept $\hat{b}_{1}$. Then, we can reasonably approximate the optimal
$\delta$ as:

$\displaystyle\tilde{\delta}_{\star}:=\frac{\tilde{\ell_{-}}-\tilde{\ell}_{+}+2\|\hat{\mathbf{w}}_{1}\|_{2}^{-1}}{\left(\tilde{\ell_{+}}-\tilde{\ell_{-}}+2\|\hat{\mathbf{w}}_{1}\|_{2}^{-1}\right)_{+}},\text{
with
}\tilde{\ell_{+}}:=\frac{\hat{\mathbf{w}}_{1}^{T}\tilde{\bm{\mu}}_{+}+\hat{b}_{1}}{\|\hat{\mathbf{w}}_{1}\|_{2}},\quad\tilde{\ell_{-}}:=-\frac{\hat{\mathbf{w}}_{1}^{T}\tilde{\bm{\mu}}_{-}+\hat{b}_{1}}{\|\hat{\mathbf{w}}_{1}\|_{2}}.$
(36)

We expect this data-dependent theory-driven heuristic to perform reasonably
well on data that resemble the GMM. For example, this is confirmed by our
experiments in Figures 5 and 12. More generally, we propose tuning $\delta$
with a train-validation split by creating a balanced validation set from the
original training data which would help assess balanced risk. Since there is
only a single hyperparameter we expect this approach to work well with a
fairly small validation data (without hurting the minority class sample size).

(a) $\pi=0.1$

(b) $\pi=0.0025$

(c) $\pi=0.0001$

Figure 15: Graphical illustration of the result of Theorem 6: Balanced errors
of CS-SVM against the margin-ratio parameter $\delta$ for a GMM of antipodal
means with $\|\mu_{+}\|=\|\mu_{-}\|=4$ and different minority class
probabilities $\pi$. The balanced error is computed using the formulae of
Theorem 2. For each case, we studied three different values of $\gamma$. The
value $\delta_{\star}$ at which the curves attain (or approach) their minimum
are predicted by Theorem 6. Specifically, note the following for the three
different priors. (a) For all values of $\gamma$, the minimum is attained (cf.
first branch of (34)). (b) For $\gamma=2,5$ the minimum is approached in the
limit $\delta\rightarrow\infty$ (cf. second branch of (34)), but it is
attained for $\gamma=0.5$ (c) The minimum is always approached as
$\delta_{\star}\rightarrow\infty$.  Figure 16: An example showing the
dependence of $\delta_{\star}$ on the data geometry. The above figure is
similar to Fig 15 but with a smaller $\|\mu_{+}\|=\|\mu_{-}\|=1$, and for
$\pi=0.1$. While in Fig 15, the value of $\delta_{\star}$, whenever finite,
can be seen to increase with increase in $\gamma$, for the current setting, it
is observed to decrease. Note also that $\delta_{\star}\rightarrow\infty$ for
$\gamma=0.5$, but finite for $\gamma=2,5$.

###  E.2 CS-SVM as post-hoc weight normalization

We need the lemma below to prove Theorem 6. But the results is interesting on
its own right as it allows us to view CS-SVM as an appropriate “post-hoc
weight normalization"-approach.

######  Lemma 2.

Let $(\hat{\mathbf{w}}_{1},\hat{b}_{1})$ be the hard-margin SVM solution. Fix
any $\delta>0$ in (4) and define:
$\hat{\mathbf{w}}_{\delta}:=\big{(}\frac{\delta+1}{2}\big{)}\,{\hat{\mathbf{w}}_{1}}$
and
$\hat{b}_{\delta}:=\big{(}\frac{\delta+1}{2}\big{)}\,\hat{b}_{1}+\big{(}\frac{\delta-1}{2}\big{)}.$
Then, $(\hat{\mathbf{w}}_{\delta},\hat{b}_{\delta})$ is optimal in (4).

Thus, classification using (4) is equivalent to the following. First learn
$(\hat{\mathbf{w}}_{1},\hat{b}_{1})$ via standard hard-margin SVM, and then
simply predict: $\hat{y}={\rm
sign}\big{(}(\hat{\mathbf{w}}_{1}^{T}\mathbf{x}+\hat{b}_{1})+\frac{\delta-1}{\delta+1}\big{)}.$
The term $\frac{\delta-1}{\delta+1}$ can be seen as an additive form of post-
hoc weight normalization to account for class imbalances. In the literature
this post-hoc adjustment of the threshold $b$ of standard SVM is often
referred to as boundary-movement SVM (BM-SVM) [STK99, WC03]. Here, we have
shown the equivalence of CS-SVM to BM-SVM for a specific choice of the
boundary shift. The proof of Lemma 2 presented in Appendix E.2 shows the
desired using the KKT conditions of (4).

###### Proof.

From optimality of $(\hat{\mathbf{w}}_{1},\hat{b}_{1})$, convexity of (4) and
the KKT-conditions, there exist dual variables $\beta_{i},i\in[n]$ such that:

$\displaystyle\hat{\mathbf{w}}_{1}=\sum_{i\in[n]}y_{i}\beta_{i}\mathbf{x}_{i},\quad\sum_{i\in[n]}y_{i}\beta_{i}=0,$
(37) $\displaystyle\forall
i\in[n]~{}:~{}\beta_{i}\big{(}\mathbf{x}_{i}^{T}\hat{\mathbf{w}}_{1}+\hat{b}_{1}\big{)}=\beta_{i}y_{i},\quad\beta_{i}\geq
0.$

Let $(\hat{\mathbf{w}}_{\delta},\hat{b}_{\delta})$ defined as in the statement
of the lemma and further define
$\epsilon_{i}:=\big{(}\frac{\delta+1}{2}\big{)}\beta_{i},~{}i\in[n]$. Then, it
only takes a few algebra steps using (37) to check that the following
conditions hold:

$\displaystyle\hat{\mathbf{w}}_{\delta}=\sum_{i\in[n]}y_{i}\epsilon_{i}\mathbf{x}_{i},\quad\sum_{i\in[n]}y_{i}\epsilon_{i}=0,$
(38) $\displaystyle\forall
i\in[n]~{}:~{}\epsilon_{i}\big{(}\mathbf{x}_{i}^{T}\hat{\mathbf{w}}_{\delta}+\hat{b}_{\delta}\big{)}=\epsilon_{i}\cdot\begin{cases}\delta&,\text{if
}y_{i}=+1\\\ -1&,\text{if }y_{i}=-1\end{cases},\quad\epsilon_{i}\geq 0.$

It can also be verified that (38) are the KKT conditions of the CS-SVM with
parameter $\delta$. This proves that
$(\hat{\mathbf{w}}_{\delta},\hat{b}_{\delta})$ is optimal in (4) as desired. ∎

###  E.3 Proof of Theorem 6

As discussed in the section above the proof proceeds in two steps:

(i) First, starting from (31), we prove (32).

(ii) Second, we analytically solve (32) to derive the explicit expression for
$\delta_{\star}$ in (34).

Proof of (32). Fix any $\delta>0.$ From Lemma 2,

$\displaystyle\hat{\mathbf{w}}_{\delta}=\big{(}\frac{\delta+1}{2}\big{)}{\hat{\mathbf{w}}_{1}}\quad\text{and}\quad\hat{b}_{\delta}=\big{(}\frac{\delta+1}{2}\big{)}\hat{b}_{1}+\big{(}\frac{\delta-1}{2}\big{)}.$
(39)

Recall from Theorem 2 that
$\|\hat{\mathbf{w}}_{\delta}\|_{2}\stackrel{{\scriptstyle{P}}}{{\longrightarrow}}q_{\delta}$,
$\|\hat{\mathbf{w}}_{1}\|_{2}\stackrel{{\scriptstyle{P}}}{{\longrightarrow}}q_{1}$,
$\hat{b}_{\delta}\stackrel{{\scriptstyle{P}}}{{\longrightarrow}}b_{\delta}$,
$\hat{b}_{1}\stackrel{{\scriptstyle{P}}}{{\longrightarrow}}b_{1}$, and, for
$i=1,2$:
$\frac{\hat{\mathbf{w}}_{\delta}^{T}\bm{\mu}_{i}}{\|\hat{\mathbf{w}}_{\delta}\|_{2}}\stackrel{{\scriptstyle{P}}}{{\longrightarrow}}\mathbf{e}_{i}^{T}\mathbf{V}\mathbf{S}\bm{\rho}_{\delta}$
and
$\frac{\hat{\mathbf{w}}_{1}^{T}\bm{\mu}_{i}}{\|\hat{\mathbf{w}}_{1}\|_{2}}\stackrel{{\scriptstyle{P}}}{{\longrightarrow}}\mathbf{e}_{i}^{T}\mathbf{V}\mathbf{S}\bm{\rho}_{1}$.
Here, $q_{\delta},\rho_{\delta},b_{\delta}$ and $q_{1},\rho_{1},b_{1}$ are as
defined in Theorem 2. Thus, from (39) we find that

$\displaystyle\bm{\rho}_{\delta}=\bm{\rho}_{1},\qquad
q_{\delta}=\big{(}\frac{\delta+1}{2}\big{)}q_{1}\qquad\text{and}\qquad
b_{\delta}=\big{(}\frac{\delta+1}{2}\big{)}b_{1}+\big{(}\frac{\delta-1}{2}\big{)}.$
(40)

Hence, it holds:

$Q\left(\mathbf{e}_{1}^{T}\mathbf{V}\mathbf{S}\bm{\rho}_{\delta}+b_{\delta}/q_{\delta}\right)=Q\Big{(}\underbrace{\mathbf{e}_{1}^{T}\mathbf{V}\mathbf{S}\bm{\rho}_{\delta}+b_{1}/q_{1}}_{=\ell_{+}}+\frac{\delta-1}{\delta+1}q_{1}^{-1}\Big{)}.$

A similar expression can be written for the conditional error of class $-1$.
Putting these together shows (32), as desired.

Proof of (34). Recall from (32) that we now need to solve the following
constrained minimization where for convenience we call $a=\ell_{+}$,
$b=\ell_{-}$ and $c=q_{1}^{-1}$:

$\min_{\delta>0}~{}Q\left(a+\frac{\delta-1}{\delta+1}c\right)+Q\left(b-\frac{\delta-1}{\delta+1}c\right).$

We define a new variable $x=\frac{\delta-1}{\delta+1}c$. The constraint
$\delta>0$ then writes $x\leq c$. This is because the function
$\delta\in(0,\infty)\mapsto\frac{\delta-1}{\delta+1}$ is onto the interval
$(-1,1).$

Thus, we equivalently need to solve

$\min_{-c<x<c}~{}f(x):=Q(a+x)+Q(b-x).$

Define function $f(x)=Q(a+x)+Q(b-x)$ for some $a,b\in\mathbb{R}$. Direct
differentiation gives $\frac{{\rm d}f}{{\rm
d}x}=\frac{1}{\sqrt{2\pi}}\left(e^{-(b-x)^{2}/2}-e^{-(a+x)^{2}/2}\right).$
Furthermore, note that $\lim_{x\rightarrow\pm\infty}f(x)=1$. With thes and
some algebra it can be checked that $f(\cdot)$ behaves as follows depending on
the sign of $a+b.$ Denote $x_{\star}=(b-a)/2$.

  * •

If $a+b\geq 0$, then $1>f(x)\geq f(x_{\star})$ and $x_{\star}$ is the unique
minimum.

  * •

If $a+b<0$, then $1<f(x)\leq f(x_{\star})$ and $x_{\star}$ is the unique
maximum.

Thus, we conclude with the following:

$\displaystyle\arg\inf_{-c<x<c}~{}f(x)=\begin{cases}x_{\star}&\text{if
}a+b\geq 0\text{ and }b-a<2c,\\\ c&\text{if }a+b\geq 0\text{ and }b-a\geq
2c,\\\ -c&\text{if }a+b<0.\end{cases}$

Equivalently,

$\displaystyle\arg\inf_{\delta>-1}~{}Q\left(\ell_{+}+\frac{\delta-1}{\delta+1}q_{1}^{-1}\right)+Q\left(\ell_{-}-\frac{\delta-1}{\delta+1}q_{1}^{-1}\right)=\begin{cases}\frac{\ell_{-}-\ell_{+}+2q_{1}^{-1}}{\ell_{+}-\ell_{-}+2q_{1}^{-1}}&\text{if
}\ell_{+}+\ell_{-}\geq 0\text{ and }\ell_{+}-\ell_{-}+2q_{1}^{-1}>0,\\\
\infty&\text{if }\ell_{+}+\ell_{-}\geq 0\text{ and
}\ell_{+}-\ell_{-}+2q_{1}^{-1}\leq 0,\\\ 0&\text{if
}\ell_{+}+\ell_{-}<0.\end{cases}$

This shows (34). The remaining statement of the theorem is easy to prove
requiring simple algebra manipulations.

##  Appendix F Asymptotic analysis of CS-SVM

###  F.1 Preliminaries

The main goal of this appendix is proving Theorem 2. For fixed $\delta>0$, let
$(\hat{\mathbf{w}},\hat{b})$ be the solution to the CS-SVM in (4). (See also
(48) below.) In the following sections, we will prove the following
convergence properties for the solution of the CS-SVM:

$\displaystyle(\|\hat{\mathbf{w}}\|_{2},\frac{\hat{\mathbf{w}}^{T}\bm{\mu}_{+}}{\|\hat{\mathbf{w}}\|_{2}},\frac{\hat{\mathbf{w}}^{T}\bm{\mu}_{-}}{\|\hat{\mathbf{w}}\|_{2}},\hat{b})\stackrel{{\scriptstyle{P}}}{{\longrightarrow}}(q_{\delta},\mathbf{e}_{1}^{T}\mathbf{V}\mathbf{S}\bm{\rho}_{\delta},\mathbf{e}_{2}^{T}\mathbf{V}\mathbf{S}\bm{\rho}_{\delta},b_{\delta}).$
(41)

where the triplet $(q_{\delta},\bm{\rho}_{\delta},b_{\delta})$ is as defined
in the theorem’s statement, that is, the unique triplet satisfying

$\displaystyle\eta_{\delta}(q_{\delta},\bm{\rho}_{\delta},b_{\delta})=0\quad\text{and}\quad(\bm{\rho}_{\delta},b_{\delta}):=\arg\min_{\begin{subarray}{c}\|\bm{\rho}\|_{2}\leq
1,b\in\mathbb{R}\end{subarray}}\eta_{\delta}(q_{\delta},\bm{\rho},b).$ (42)

In this section, we show how to use (41) to derive the asymptotic limit of the
conditional class probabilities.

Consider the class conditional
$\mathcal{R}_{+}=\mathbb{P}\left\\{(\mathbf{x}^{T}\hat{\mathbf{w}}+b)<0\,|\,y=+1\right\\}$.
Recall that conditioned on $y=+1$, we have
$\mathbf{x}=\bm{\mu}_{+}+\mathbf{z}$ for
$\mathbf{z}\sim\mathcal{N}(\mathbf{0},\mathbf{I}).$ Thus, the class
conditional can be expressed explicitly in terms of the three summary
quantities on the left hand side of (41) as follows:

$\displaystyle\mathcal{R}_{+}$
$\displaystyle=\mathbb{P}\left\\{(\mathbf{x}^{T}\hat{\mathbf{w}}+\hat{b})<0\,|\,y=+1\right\\}=\mathbb{P}\left\\{\mathbf{z}^{T}\hat{\mathbf{w}}+\bm{\mu}_{+}^{T}\hat{\mathbf{w}}+\hat{b}<0\,|\,y=+1\right\\}$
$\displaystyle=\mathbb{P}\left\\{\mathbf{z}^{T}\hat{\mathbf{w}}>\bm{\mu}_{+}^{T}\hat{\mathbf{w}}+\hat{b}\right\\}$
$\displaystyle=\mathbb{P}_{G\sim\mathcal{N}(0,1)}\left\\{G\|\hat{\mathbf{w}}\|_{2}>\bm{\mu}_{+}^{T}\hat{\mathbf{w}}+\hat{b}\right\\}=\mathbb{P}_{G\sim\mathcal{N}(0,1)}\left\\{G>\frac{\bm{\mu}_{+}^{T}\hat{\mathbf{w}}}{\|\hat{\mathbf{w}}\|_{2}}+\frac{\hat{b}}{\|\hat{\mathbf{w}}\|_{2}}\right\\}$
$\displaystyle=Q\left(\frac{\bm{\mu}_{+}^{T}\hat{\mathbf{w}}}{\|\hat{\mathbf{w}}\|_{2}}+\frac{\hat{b}}{\|\hat{\mathbf{w}}\|_{2}}\right).$

Then, the theorem’s statement follows directly by applying (41) in the
expression above.

In order to prove the key convergence result in (41) we rely on the convex
Gaussian min-max theorem (CGMT) framework. We give some necessary background
before we proceed with the proof.

###  F.2 Background and related literature

Related works: Our asymptotic analysis of the CS-SVM fits in the growing
recent literature on sharp statistical performance asymptotics of convex-based
estimators, e.g. [BBEKY13, DM16, TAH18, TXH18] and references therin. The
origins of these works trace back to the study of sharp phase transitions in
compressed sensing, e.g. see [TAH18] for historical remarks and performance
analysis of the LASSO estimator for sparse signal recovery. That line of work
led to the development of two analysis frameworks: (a) the approximate
message-passing (AMP) framework [BM11, DMM09], and, (b) the convex Gaussian
min-max theorem (CGMT) framework [Sto13, TOH15]. More recently, these powerful
tools have proved very useful for the analysis of linear classifiers [SAH19,
MRSY19, DKT19, KT20, MKL+20, LS20a, TPT20b, CS+20, AKLZ20, TPT20a]. Theorems 2
and 7 rely on the CGMT and contribute to this line of work. Specifically, our
results are most closely related to [DKT19] who first studied max-margin type
classifiers together with [MRSY19].

CGMT framework: Specifically, we rely on the CGMT framework. Here, we only
summarize the framework’s essential ideas and refer the reader to [TOH15,
TAH18] for more details and precise statements. Consider the following two
Gaussian processes:

$\displaystyle X_{\mathbf{w},\mathbf{u}}$
$\displaystyle:=\mathbf{u}^{T}\mathbf{A}\mathbf{w}+\psi(\mathbf{w},\mathbf{u}),$
(43a) $\displaystyle Y_{\mathbf{w},\mathbf{u}}$
$\displaystyle:=\lVert\mathbf{w}\rVert_{2}\mathbf{h}_{n}^{T}\mathbf{u}+\lVert\mathbf{u}\rVert_{2}\mathbf{h}_{d}^{T}\mathbf{w}+\psi(\mathbf{w},\mathbf{u}),$
(43b)

where: $\mathbf{A}\in\mathbb{R}^{n\times d}$,
$\mathbf{h}_{n}\in\mathbb{R}^{n}$, $\mathbf{h}_{d}\in\mathbb{R}^{d}$, they all
have entries iid Gaussian; the sets
$\mathcal{S}_{\mathbf{w}}\subset\mathbb{R}^{d}$ and
$\mathcal{S}_{\mathbf{u}}\subset\mathbb{R}^{n}$ are compact; and,
$\psi:\mathbb{R}^{d}\times\mathbb{R}^{n}\to\mathbb{R}$. For these two
processes, define the following (random) min-max optimization programs, which
are refered to as the _primary optimization_ (PO) and the _auxiliary
optimization_ (AO) problems:

$\displaystyle\Phi(\mathbf{A})$
$\displaystyle=\min\limits_{\mathbf{w}\in\mathcal{S}_{\mathbf{w}}}\max\limits_{\mathbf{u}\in\mathcal{S}_{\mathbf{u}}}X_{\mathbf{w},\mathbf{u}},$
(44a) $\displaystyle\phi(\mathbf{h}_{n},\mathbf{h}_{d})$
$\displaystyle=\min\limits_{\mathbf{w}\in\mathcal{S}_{\mathbf{w}}}\max\limits_{\mathbf{u}\in\mathcal{S}_{\mathbf{u}}}Y_{\mathbf{w},\mathbf{u}}.$
(44b)

According to the first statement of the CGMT Theorem 3 in [TOH15] (this is
only a slight reformulation of Gordon’s original comparison inequality
[Gor85]), for any $c\in\mathbb{R}$, it holds:

$\mathbb{P}\left\\{\Phi(\mathbf{A})<c\right\\}\leq
2\,\mathbb{P}\left\\{\phi(\mathbf{h}_{n},\mathbf{h}_{d})<c\right\\}.$ (45)

In other words, a high-probability lower bound on the AO is a high-probability
lower bound on the PO. The premise is that it is often much simpler to lower
bound the AO rather than the PO. However, the real power of the CGMT comes in
its second statement, which asserts that if the PO is _convex_ then the AO in
can be used to tightly infer properties of the original PO, including the
optimal cost and the optimal solution. More precisely, if the sets
$\mathcal{S}_{\mathbf{w}}$ and $\mathcal{S}_{\mathbf{u}}$ are convex and
_bounded_ , and $\psi$ is continuous _convex-concave_ on
$\mathcal{S}_{\mathbf{w}}\times\mathcal{S}_{\mathbf{u}}$, then, for any
$\nu\in\mathbb{R}$ and $t>0$, it holds [TOH15]:

$\mathbb{P}\left\\{\lvert\Phi(\mathbf{A})-\nu\rvert>t\right\\}\leq
2\,\mathbb{P}\left\\{\lvert\phi(\mathbf{h}_{n},\mathbf{h}_{d})-\nu\rvert>t\right\\}.$
(46)

In words, concentration of the optimal cost of the AO problem around
$q^{\ast}$ implies concentration of the optimal cost of the corresponding PO
problem around the same value $q^{\ast}$. Asymptotically, if we can show that
$\phi(\mathbf{h}_{n},\mathbf{h}_{d})\stackrel{{\scriptstyle{P}}}{{\longrightarrow}}q^{\ast}$,
then we can conclude that
$\Phi(\mathbf{A})\stackrel{{\scriptstyle{P}}}{{\longrightarrow}}q^{\ast}$.

In the next section, we will show that we can indeed express the CS-SVM in (4)
as a PO in the form of (44a). Thus, the argument above will directly allow us
to determine the asymptotic limit of the optimal cost of the CS-SVM. In our
case, the optimal cost equals $\|\hat{\mathbf{w}}\|_{2}$; thus, this shows the
first part of (41). For the other parts, we will employ the following
“deviation argument" of the CGMT framework [TOH15]. For arbitrary
$\epsilon>0$, consider the desired set

$\displaystyle{\mathcal{S}}:=\left\\{(\mathbf{v},c)~{}\Big{|}~{}\max\Big{\\{}\lvert\|\mathbf{v}\|_{2}-q_{\delta}\rvert\,,\,\Big{|}\frac{\mathbf{v}^{T}\bm{\mu}_{+}}{\|\mathbf{v}\|_{2}}-\mathbf{e}_{1}^{T}\mathbf{V}\mathbf{S}\bm{\rho}_{\delta}\Big{|},,\,\Big{|}\frac{\mathbf{v}^{T}\bm{\mu}_{-}}{\|\mathbf{v}\|_{2}}-\mathbf{e}_{2}^{T}\mathbf{V}\mathbf{S}\bm{\rho}_{\delta}\Big{|}\,,\,|c-b_{\delta}|\Big{\\}}\leq\epsilon\,\right\\}.$
(47)

Our goal towards (41) is to show that with overwhelming probability
$(\mathbf{w},b)\in{\mathcal{S}}$. For this, consider the following constrained
CS-SVM that further constraints the feasible set to the complement
${\mathcal{S}}^{c}$ of ${\mathcal{S}}$:

$\displaystyle\Phi_{{\mathcal{S}}^{c}}(\mathbf{A}):=\min_{(\mathbf{w},b)\in{\mathcal{S}}^{c}}~{}\|\mathbf{w}\|_{2}~{}\text{sub.
to}\begin{cases}\mathbf{w}^{T}\mathbf{x}_{i}+b\geq\delta&,y_{i}=+1\\\
\mathbf{w}^{T}\mathbf{x}_{i}+b\leq-1&,y_{i}=-1\end{cases},i\in[n],$ (48)

As per Theorem 6.1(iii) in [TAH18] it will suffice to find costants
$\bar{\phi},\bar{\phi}_{S}$ and $\eta>0$ such that the following three
conditions hold:

$\displaystyle\begin{cases}\text{(i)~{}~{}\,\,
$\bar{\phi}_{S}\geq\bar{\phi}+3\eta$}\\\ \text{(ii)~{}~{}
\,$\phi(\mathbf{h}_{n},\mathbf{h}_{d})\leq\bar{\phi}+\eta$~{}~{} with
overwhelming probability}\\\ \text{(iii)~{}~{}
$\phi_{{\mathcal{S}}^{c}}(\mathbf{h}_{n},\mathbf{h}_{d})\geq\bar{\phi}_{S}-\eta$~{}~{}
with overwhelming probability,}\end{cases}$ (49)

where $\phi_{{\mathcal{S}}^{c}}(\mathbf{h}_{n},\mathbf{h}_{d})$ is the optimal
cost of the constrained AO corresponding to the constrained PO in (48).

To prove these conditions for the AO of the CS-SVM, in the next section we
follow the principled machinery of [TAH18] that allows simplifying the AO from
a (random) optimization over vector variables to an easier optimization over
only few scalar variables, termed the “scalarized AO".

###  F.3 Proof of Theorem 2

Let $(\hat{\mathbf{w}},\hat{b})$ be solution pair to the CS-SVM in (4) for
some fixed margin-ratio parameter $\delta>0$, which we rewrite here expressing
the constraints in matrix form:

$\displaystyle\min_{\mathbf{w},b}\|\mathbf{w}\|_{2}~{}~{}\text{sub.
to}~{}\begin{cases}\mathbf{w}^{T}\mathbf{x}_{i}+b\geq\delta,~{}y_{i}=+1\\\
-(\mathbf{w}^{T}\mathbf{x}_{i}+b)\geq
1,~{}y_{i}=-1\end{cases},~{}i\in[n]~{}~{}=~{}~{}\min_{\mathbf{w},b}\|\mathbf{w}\|_{2}~{}~{}\text{sub.
to}~{}\mathbf{D}_{\mathbf{y}}(\mathbf{X}\mathbf{w}+b\mathbf{1}_{n})\geq\bm{\delta}_{\mathbf{y}},$
(50)

where we have used the notation

$\displaystyle\mathbf{X}^{T}$
$\displaystyle=\begin{bmatrix}\mathbf{x}_{1}&\cdots&\mathbf{x}_{n}\end{bmatrix},~{}\mathbf{y}=\begin{bmatrix}y_{1}&\cdots&y_{n}\end{bmatrix}^{T},$
$\displaystyle\mathbf{D}_{\mathbf{y}}$
$\displaystyle=\rm{diag}(\mathbf{y})~{}\text{and}~{}\bm{\delta}_{\mathbf{y}}=\begin{bmatrix}\delta\mathds{1}[y_{1}=+1]+\mathds{1}[y_{1}=-1]&\cdots&\delta\mathds{1}[y_{n}=+1]+\mathds{1}[y_{n}=-1]\end{bmatrix}^{T}.$

We further need to define the following one-hot-encoding of the labels:

$\mathbf{y}_{i}=\mathbf{e}_{1}\mathds{1}[y_{i}=1]+\mathbf{e}_{2}\mathds{1}[y_{i}=-1],\quad\text{and}\quad\mathbf{Y}_{n\times
2}^{T}=\begin{bmatrix}\mathbf{y}_{1}&\cdots&\mathbf{y}_{n}\end{bmatrix}.$

where recall that $\mathbf{e}_{1},\mathbf{e}_{2}$ are standard basis vectors
in $\mathbb{R}^{2}$.

With these, notice for later use that under our model,
$\mathbf{x}_{i}=\bm{\mu}_{y_{i}}+\mathbf{z}_{i}=\mathbf{M}\mathbf{y}_{i}+\mathbf{z}_{i},~{}\mathbf{z}_{i}\sim\mathcal{N}(0,1)$.
Thus, in matrix form with $\mathbf{Z}$ having entries $\mathcal{N}(0,1)$:

$\displaystyle\mathbf{X}=\mathbf{Y}\mathbf{M}^{T}+\mathbf{Z}.$ (51)

Following the CGMT strategy [TOH15], we express (50) in a min-max form to
bring it in the form of the PO as follows:

$\displaystyle\min_{\mathbf{w},b}\max_{\mathbf{u}\leq
0}~{}\frac{1}{2}\|\mathbf{w}\|_{2}^{2}+\mathbf{u}^{T}\mathbf{D}_{\mathbf{y}}\mathbf{X}\mathbf{w}+b(\mathbf{u}^{T}\mathbf{D}_{\mathbf{y}}\mathbf{1}_{n})-\mathbf{u}^{T}\bm{\delta}_{\mathbf{y}}$
$\displaystyle=$ $\displaystyle\min_{\mathbf{w},b}\max_{\mathbf{u}\leq
0}~{}\frac{1}{2}\|\mathbf{w}\|_{2}^{2}+\mathbf{u}^{T}\mathbf{D}_{\mathbf{y}}\mathbf{Z}\mathbf{w}+\mathbf{u}^{T}\mathbf{D}_{\mathbf{y}}\mathbf{Y}\mathbf{M}^{T}\mathbf{w}+b(\mathbf{u}^{T}\mathbf{D}_{\mathbf{y}}\mathbf{1}_{n})-\mathbf{u}^{T}\bm{\delta}_{\mathbf{y}}.$
(52)

where in the last line we used (51) and
$\mathbf{D}_{\mathbf{y}}\mathbf{D}_{\mathbf{y}}=\mathbf{I}_{n}$. We
immediately recognize that the last optimization is in the form of a PO (cf.
(44a)) and the corresponding AO (cf. (44b)) is as follows:

$\displaystyle\min_{\mathbf{w},b}\max_{\mathbf{u}\leq
0}~{}\frac{1}{2}\|\mathbf{w}\|_{2}^{2}+\|\mathbf{w}\|_{2}\mathbf{u}^{T}\mathbf{D}_{\mathbf{y}}\mathbf{h}_{n}+\|\mathbf{D}_{\mathbf{y}}\mathbf{u}\|_{2}\mathbf{h}_{d}^{T}\mathbf{w}+\mathbf{u}^{T}\mathbf{D}_{\mathbf{y}}\mathbf{Y}\mathbf{M}^{T}\mathbf{w}+b(\mathbf{u}^{T}\mathbf{D}_{\mathbf{y}}\mathbf{1}_{n})-\mathbf{u}^{T}\bm{\delta}_{\mathbf{y}}.$
(53)

where $\mathbf{h}_{n}\sim\mathcal{N}(0,\mathbf{I}_{n})$ and
$\mathbf{h}_{d}\sim\mathcal{N}(0,\mathbf{I}_{d})$.

In order to apply the CGMT in [TOH15], we need boundedness of the constraint
sets. Thus, we restrict the minimization in (53) and (52) to a bounded set
$\|\mathbf{w}\|_{2}^{2}+b^{2}\leq R$ for (say)
$R:=2\left(q_{\delta}^{2}+b_{\delta}^{2}\right)$. This will allow us to show
that the solutions $\hat{\mathbf{w}}_{R},\hat{b}_{R}$ of this constrained PO
satisfy
$\hat{\mathbf{w}}_{R}\stackrel{{\scriptstyle{P}}}{{\longrightarrow}}q_{\delta}$
and $\hat{b}_{R}\stackrel{{\scriptstyle{P}}}{{\longrightarrow}}b_{\delta}$.
Thus, with overwhelming probability,
$\|\hat{\mathbf{w}}_{R}\|_{2}^{2}+{\hat{b}}_{R}^{2}<R$. From this and
convexity of the PO, we can argue that the minimizers
$\hat{\mathbf{w}},\hat{b}$ of the original unconstrained problem satisfy the
same convergence properties. Please see also Remark 4 in App. A of [DKT19].

For the maximization, we follow the recipe in App. A of [DKT19] who analyzed
the standard SVM. Specifically, combining Remark 3 of [DKT19] together with
(we show this next) the property that the AO is reduced to a convex program,
it suffices to consider the unconstrained maximization.

Thus, in what follows we consider the one-sided constrained AO in (53).
Towards simplifying this auxiliary optimization, note that
$\mathbf{D}_{\mathbf{y}}\mathbf{h}_{n}\sim\mathbf{h}_{n}$ by rotational
invariance of the Gaussian measure. Also,
$\|\mathbf{D}_{\mathbf{y}}\mathbf{u}\|_{2}=\|\mathbf{u}\|_{2}$. Thus, we can
express the AO in the following more convenient form:

$\displaystyle\min_{\|\mathbf{w}\|_{2}^{2}+b^{2}\leq R}\max_{\mathbf{u}\leq
0}~{}\frac{1}{2}\|\mathbf{w}\|_{2}^{2}+\|\mathbf{w}\|_{2}\mathbf{u}^{T}\mathbf{h}_{n}+\|\mathbf{u}\|_{2}\mathbf{h}_{d}^{T}\mathbf{w}+\mathbf{u}^{T}\mathbf{D}_{\mathbf{y}}\mathbf{Y}\mathbf{M}^{T}\mathbf{w}+b(\mathbf{u}^{T}\mathbf{D}_{\mathbf{y}}\mathbf{1}_{n})-\mathbf{u}^{T}\bm{\delta}_{\mathbf{y}}.$
(54)

We are now ready to proceed with simplification of the AO. First we optimize
over the direction of $\mathbf{u}$ and rewrite the AO as

$\displaystyle\min_{\|\mathbf{w}\|_{2}^{2}+b^{2}\leq R}\max_{\beta\geq
0}~{}\frac{1}{2}\|\mathbf{w}\|_{2}^{2}+\beta\left(\Big{\|}\big{(}\,\|\mathbf{w}\|_{2}\mathbf{h}_{n}+\mathbf{D}_{\mathbf{y}}\mathbf{Y}\mathbf{M}^{T}\mathbf{w}+b\,\mathbf{D}_{\mathbf{y}}\mathbf{1}_{n}-\bm{\delta}_{\mathbf{y}}\,\big{)}_{-}\Big{\|}_{2}-\mathbf{h}_{d}^{T}\mathbf{w}\right)$
$\displaystyle=$ $\displaystyle\min_{\|\mathbf{w}\|_{2}^{2}+b^{2}\leq
R}~{}\frac{1}{2}\|\mathbf{w}\|_{2}^{2}\quad\text{sub.
to}~{}\Big{\|}\big{(}\,\|\mathbf{w}\|_{2}\mathbf{h}_{n}+\mathbf{D}_{\mathbf{y}}\mathbf{Y}\mathbf{M}^{T}\mathbf{w}+b\,\mathbf{D}_{\mathbf{y}}\mathbf{1}_{n}-\bm{\delta}_{\mathbf{y}}\,\big{)}_{-}\Big{\|}_{2}\leq\mathbf{h}_{d}^{T}\mathbf{w}.$

Above, $(\cdot)_{-}$ acts elementwise to the entries of its argument.

Now, we wish to further simplify the above by minimizing over the direction of
$\mathbf{w}$ in the space orthogonal to $\mathbf{M}$. To see how this is
possible consider the SVD $\mathbf{M}^{T}=\mathbf{V}\mathbf{S}\mathbf{U}^{T}$
and project $\mathbf{w}$ on the columns of
$\mathbf{U}=\begin{bmatrix}\mathbf{u}_{1}&\mathbf{u}_{2}\end{bmatrix}\in\mathbb{R}^{d\times
2}$ as follows:

$\mathbf{w}=\mathbf{u}_{1}(\mathbf{u}_{1}^{T}\mathbf{w})+\mathbf{u}_{2}(\mathbf{u}_{2}^{T}\mathbf{w})+\mathbf{w}^{\perp},$

where $\mathbf{w}^{\perp}=\mathbf{U}^{\perp}\mathbf{w}$, $\mathbf{U}^{\perp}$
is the orthogonal complement of $\mathbf{U}$. For simplicity we will assume
here that $\mathbf{M}$ is full column rank, i.e.
$\mathbf{S}\succ\mathbf{0}_{2\times 2}$. The argument for the case where
$\mathbf{M}$ is rank 1 is very similar.

Let us denote $\mathbf{u}_{i}^{T}\mathbf{w}:=\mu_{i},i=1,2$ and
$\|\mathbf{w}^{\perp}\|_{2}:=\alpha$. In this notation, the AO becomes

$\displaystyle\min_{\mu_{1}^{2}+\mu_{2}^{2}+\|\mathbf{w}^{\perp}\|_{2}^{2}+b^{2}\leq
R}~{}\frac{1}{2}(\mu_{1}^{2}+\mu_{2}^{2}+\alpha^{2})\quad$
$\displaystyle\text{sub.
to}\quad\Big{\|}\big{(}\,\sqrt{\mu_{1}^{2}+\mu_{2}^{2}+\alpha^{2}}\mathbf{h}_{n}+\mathbf{D}_{\mathbf{y}}\mathbf{Y}\mathbf{V}\mathbf{S}\begin{bmatrix}\mu_{1}\\\
\mu_{2}\end{bmatrix}+b\,\mathbf{D}_{\mathbf{y}}\mathbf{1}_{n}-\bm{\delta}_{\mathbf{y}}\,\big{)}_{-}\Big{\|}_{2}$
$\displaystyle\quad\quad\quad\leq\mu_{1}(\mathbf{h}_{d}^{T}\mathbf{u}_{1})+\mu_{2}(\mathbf{h}_{d}^{T}\mathbf{u}_{2})+\mathbf{h}_{d}^{T}\mathbf{U}^{\perp}\mathbf{w}^{\perp}.$

At this point, we can optimize over the direction of $\mathbf{w}^{\perp}$
which leads to

$\displaystyle\min_{\mu_{1}^{2}+\mu_{2}^{2}+\alpha^{2}+b^{2}\leq
R}~{}\frac{1}{2}(\mu_{1}^{2}+\mu_{2}^{2}+\alpha^{2})\quad$
$\displaystyle\text{sub.
to}\quad\Big{\|}\big{(}\,\sqrt{\mu_{1}^{2}+\mu_{2}^{2}+\alpha^{2}}\mathbf{h}_{n}+\mathbf{D}_{\mathbf{y}}\mathbf{Y}\mathbf{V}\mathbf{S}\begin{bmatrix}\mu_{1}\\\
\mu_{2}\end{bmatrix}+b\,\mathbf{D}_{\mathbf{y}}\mathbf{1}_{n}-\bm{\delta}_{\mathbf{y}}\,\big{)}_{-}\Big{\|}_{2}$
$\displaystyle\quad\quad\quad\leq\mu_{1}(\mathbf{h}_{d}^{T}\mathbf{u}_{1})+\mu_{2}(\mathbf{h}_{d}^{T}\mathbf{u}_{2})+\alpha\|\mathbf{h}_{d}^{T}\mathbf{U}^{\perp}\|_{2}.$

As a last step in the simplification of the AO, it is convenient to introduce
an additional variable $q=\sqrt{\mu_{1}^{2}+\mu_{2}^{2}+\alpha^{2}}.$ It then
follows that the minimization above is equivalent to the following

$\displaystyle\min_{\begin{subarray}{c}q\geq\sqrt{\mu_{1}^{2}+\mu_{2}^{2}+\alpha^{2}}\\\
q^{2}+b^{2}\leq R\end{subarray}}~{}\frac{1}{2}q^{2}\quad$ (55)
$\displaystyle\text{sub.
to}\quad\Big{\|}\big{(}\,q\mathbf{h}_{n}+\mathbf{D}_{\mathbf{y}}\mathbf{Y}\mathbf{V}\mathbf{S}\begin{bmatrix}\mu_{1}\\\
\mu_{2}\end{bmatrix}+b\,\mathbf{D}_{\mathbf{y}}\mathbf{1}_{n}-\bm{\delta}_{\mathbf{y}}\,\big{)}_{-}\Big{\|}_{2}\leq\mu_{1}(\mathbf{h}_{d}^{T}\mathbf{u}_{1})+\mu_{2}(\mathbf{h}_{d}^{T}\mathbf{u}_{2})+\alpha\|\mathbf{h}_{d}^{T}\mathbf{U}^{\perp}\|_{2}.$

In this formulation it is not hard to check that the optimization is jointly
convex in its variables $(\mu_{1},\mu_{2},\alpha,b,q)$. To see this note that:
(i) the constraint $q\geq\sqrt{\mu_{1}^{2}+\mu_{2}^{2}+\alpha^{2}}\iff
q\geq\|\begin{bmatrix}\mu_{1}&\mu_{2}&\alpha\end{bmatrix}\|_{2}$ is a second-
order cone constraint, and, (ii) the function

$\displaystyle\mathcal{L}_{n}(q,\mu_{1},\mu_{2},\alpha,b)$
$\displaystyle:=\frac{1}{\sqrt{n}}\Big{\|}\big{(}\,q\mathbf{h}_{n}+\mathbf{D}_{\mathbf{y}}\mathbf{Y}\mathbf{V}\mathbf{S}\begin{bmatrix}\mu_{1}\\\
\mu_{2}\end{bmatrix}+b\,\mathbf{D}_{\mathbf{y}}\mathbf{1}_{n}-\bm{\delta}_{\mathbf{y}}\,\big{)}_{-}\Big{\|}_{2}$
$\displaystyle\quad-\mu_{1}\frac{\mathbf{h}_{d}^{T}\mathbf{u}_{1}}{\sqrt{n}}-\mu_{2}\frac{\mathbf{h}_{d}^{T}\mathbf{u}_{2}}{\sqrt{n}}-{\alpha}\frac{\|\mathbf{h}_{d}^{T}\mathbf{U}^{\perp}\|_{2}}{\sqrt{n}}$
(56)

is also convex since $\|(\cdot)_{-}\|_{2}:\mathbb{R}^{n}\rightarrow\mathbb{R}$
is itslef convex and is composed here with an affine function.

Now, by law of large numbers, notice that for fixed
$(q,\mu_{1},\mu_{2},\alpha,b)$, $\mathcal{L}_{n}$ converges in probability to

$\displaystyle\mathcal{L}_{n}(q,\mu_{1},\mu_{2},\alpha,b)\stackrel{{\scriptstyle{P}}}{{\longrightarrow}}L(q,\mu_{1},\mu_{2},\alpha,b):=\sqrt{\mathbb{E}\big{(}qG+E_{Y}^{T}\mathbf{V}\mathbf{S}\begin{bmatrix}\mu_{1}\\\
\mu_{2}\end{bmatrix}+{b\,Y-\Delta_{Y}}\big{)}_{-}^{2}}-\alpha\sqrt{\gamma},$
(57)

where the random variables $G,E_{Y},Y,\Delta_{Y}$ are as in the statement of
the theorem. But convergence of convex functions is uniform over compact sets
as per Cor. II.I in [AG82]. Therefore, the convergence in (57) is in fact
uniform in the compact feasible set of (55).

Consider then the deterministic high-probability equivalent of (55) which is
the following convex program:

$\displaystyle\min_{\begin{subarray}{c}q\geq\sqrt{\mu_{1}^{2}+\mu_{2}^{2}+\alpha^{2}}\\\
q^{2}+b^{2}\leq R\\\ L(q,\mu_{1},\mu_{2},\alpha,b)\leq
0\end{subarray}}~{}\frac{1}{2}q^{2}.$

Since $q$ is positive and the constraint
$q\geq\sqrt{\mu_{1}^{2}+\mu_{2}^{2}+\alpha^{2}}$ must be active at the
optimum, it is convenient to rewrite this in terms of new variables
$\bm{\rho}=\begin{bmatrix}\bm{\rho}_{1}\\\
\bm{\rho}_{2}\end{bmatrix}:=\begin{bmatrix}\mu_{1}/q\\\
\mu_{2}/q\end{bmatrix}$ as follows:

$\displaystyle\min_{q^{2}+b^{2}\leq R,q>0,\|\bm{\rho}\|_{2}\leq
1}~{}\frac{1}{2}q^{2}$ (58) $\displaystyle\text{sub.
to}\quad{\mathbb{E}\Big{[}\big{(}G+E_{Y}^{T}\mathbf{V}\mathbf{S}\bm{\rho}+\frac{b\,Y-\Delta_{Y}}{q}\big{)}_{-}^{2}\Big{]}}\leq\left({1-\|\bm{\rho}\|_{2}^{2}}\right){\gamma}.$

Now, recall the definition of the function $\eta_{\delta}$ in the statement of
the theorem and observe that the constraint above is nothing but

$\eta_{\delta}(q,\bm{\rho},b)\leq 0.$

Thus, (58) becomes

$\displaystyle\min\left\\{q^{2}~{}\Big{|}~{}0\leq q\leq\sqrt{R}\quad\text{ and
}\quad\min_{b^{2}\leq R-q^{2},\|\bm{\rho}\|_{2}\leq
1}\eta_{\delta}(q,\bm{\rho},b)\leq 0\right\\}.$ (59)

We will prove that

$\displaystyle\text{the function $f(q):=\min_{b,\|\bm{\rho}\|_{2}\leq
1}\eta_{\delta}(q,\bm{\rho},b)$ is strictly decreasing}.$ (60)

Before that, let us see how this completes the proof of the theorem. Let
$q_{\delta}$ be as in the statement of the theorem, that is such that
$f(q_{\delta})=0$. Then, we have the following relations

$f(q)\leq 0~{}\Rightarrow~{}f(q)\leq f(q_{\delta})~{}\Rightarrow~{}q\geq
q_{\delta}.$

Thus, the minimizers in (59) are $(q_{\delta},\bm{\rho}_{\delta},b_{\delta})$,
where we also recall that we have set $R>q_{\delta}^{2}+b_{\delta}^{2}$.

With all these, we have shown that the AO converges in probability to
$q_{\delta}^{2}$ (cf. condition (ii) in (49)). From the CGMT, the same is true
for the PO. Now, we want to use the same machinery to prove that the
minimizers $(\hat{\mathbf{w}},\hat{b})$ of the PO satisfy (41). To do this, as
explained in the previous section, we use the standard strategy of the CGMT
framework , i.e., to show that the PO with the additional constraint
$(\mathbf{w},b)\in{\mathcal{S}}^{c}$ for the set ${\mathcal{S}}$ in (47) has a
cost that is strictly larger than $q_{\delta}^{2}$ (i.e. the cost of the
unconstrained PO). As per the CGMT this can be done again by showing that the
statement is true for the correspondingly constrained AO (i.e. show condition
(iii) in (49)). With the exact same simplifications as above, the latter
program simplifies to (55) with the additional constraints:

$|q-q_{\delta}|>\epsilon\,,\,\big{|}\mu_{i}/q-\bm{\rho}_{\delta,i}\big{|}>\epsilon,\,i=1,2\,,\,|b-b_{\delta}|>\epsilon.$

Also, using the uniform convergence in (57), it suffices to study the
deterministic equivalent (59) with the additional constraints above. Now, we
can show the desired (cf. condition (i) in (49)) again by exploiting (60).
This part of the argument is similar to Section C.3.5 in [DKT19] and we omit
the details.

Proof of (60): To complete the proof, it remains to show (60). Specifically,
we show that $\frac{\mathrm{d}f}{\mathrm{d}q}<0$ by combining the following
three observations.

First,

$\displaystyle\frac{\mathrm{\partial}\eta_{\delta}}{\mathrm{\partial}q}$
$\displaystyle=\frac{2}{q^{2}}\mathbb{E}\Big{[}(G+E_{Y}^{T}\mathbf{V}\mathbf{S}\bm{\rho}+\frac{b\,Y-\Delta_{Y}}{q}\big{)}_{-}\cdot\Delta_{Y}\Big{]}-\frac{2b}{q^{2}}\mathbb{E}\Big{[}(G+E_{Y}^{T}\mathbf{V}\mathbf{S}\bm{\rho}+\frac{b\,Y-\Delta_{Y}}{q}\big{)}_{-}\cdot
Y\Big{]}$
$\displaystyle<-\frac{2b}{q^{2}}\mathbb{E}\Big{[}(G+E_{Y}^{T}\mathbf{V}\mathbf{S}\bm{\rho}+\frac{b\,Y-\Delta_{Y}}{q}\big{)}_{-}\cdot
Y\Big{]}$ (61)

where for the inequality we observed that $(\cdot)_{-}$ is always non-
positive, its argument has non-zero probability measure on the negative real
axis, and $\Delta_{Y}$ are positive random variables.

Second, letting $\bm{\rho}^{\star}:=\bm{\rho}^{\star}(q)$ and
$b^{\star}:=b^{\star}(q)$ the minimizers of $\eta_{\delta}(q,\bm{\rho},b)$, it
follows from first-order optimality conditions that

$\displaystyle\frac{\mathrm{\partial}\eta_{\delta}}{\mathrm{\partial}b}=0\iff\mathbb{E}\Big{[}(G+E_{Y}^{T}\mathbf{V}\mathbf{S}\bm{\rho}^{*}+\frac{b^{*}\,Y-\Delta_{Y}}{q}\big{)}_{-}\cdot
Y\Big{]}=0.$ (62)

Third, by the envelope theorem

$\displaystyle\frac{\mathrm{d}f}{\mathrm{d}q}=\frac{\mathrm{\partial}\eta_{\delta}}{\mathrm{\partial}q}\big{|}_{\bm{\rho}^{\star},b^{\star}}.$
(63)

The desired inequality $\frac{\mathrm{d}f}{\mathrm{d}q}<0$ follows directly by
successively applying (63), (61) and (62).

Uniqueness of triplet $(q_{\delta},\bm{\rho}_{\delta},b_{\delta})$. First, we
prove that the minimizers $\bm{\rho}_{\delta},b_{\delta}$ are unique. This
follows because $\eta_{\delta}(q,\bm{\rho},b)$ is jointly strictly convex in
$(\bm{\rho},b)$ for fixed $q$. To see this note that the function
$x\mapsto(x)_{-}^{2}$ is strictly convex for $x<0$ and that the random
variable $G+E_{Y}^{T}\mathbf{V}\mathbf{S}\bm{\rho}+(bY-\Delta_{Y})/q$ has
strictly positive measure on the real line (thus, also in the negative axis).
Next, consider $q_{\delta}$, which was defined such that $f(q_{\delta})=0$ for
the function $f(\cdot)$ in (60). From (60) we know that $f(\cdot)$ is strictly
decreasing. Thus, it suffices to prove that the function has a zero crossing
in $(0,\infty)$, which we do by proving $\lim_{q\rightarrow 0}f(q)=\infty$ and
$\lim_{q\rightarrow\infty}f(q)<0.$ Specifically, we have

$\displaystyle\lim_{q\rightarrow 0}f(q)$ $\displaystyle\geq\lim_{q\rightarrow
0}\,\min_{b\in\mathbb{R},\|\bm{\rho}\|_{2}\leq
1}{\mathbb{E}\Big{[}\big{(}G+E_{Y}^{T}\mathbf{V}\mathbf{S}\bm{\rho}+\frac{b\,Y-\Delta_{Y}}{q}\big{)}_{-}^{2}\Big{]}}-\gamma$
$\displaystyle\geq\lim_{q\rightarrow
0}\,\min_{b\in\mathbb{R},\|\bm{\rho}\|_{2}\leq
1}{\mathbb{E}\Big{[}\big{(}G+E_{Y}^{T}\mathbf{V}\mathbf{S}\bm{\rho}+\frac{b\,Y-\Delta_{Y}}{q}\big{)}_{-}^{2}\,\mathds{1}[G+E_{Y}^{T}\mathbf{V}\mathbf{S}\bm{\rho}+(b/q)Y\leq
0]\Big{]}}-\gamma$ $\displaystyle\geq\lim_{q\rightarrow
0}\,\min_{b\in\mathbb{R},\|\bm{\rho}\|_{2}\leq 1}{1/q^{2}}-\gamma=\infty,$

where in the last inequality we used the facts that $x\mapsto(x)_{-}^{2}$ is
decreasing and the event
$\\{G+E_{Y}^{T}\mathbf{V}\mathbf{S}\bm{\rho}+(b/q)Y\leq 0\leq 0\\}$ has non-
zero measure for all $\|\bm{\rho}\|_{2}\leq 1,b\in\mathbb{R}$, as well as,
$\Delta_{Y}\geq 1$ (because $\delta>1$). Moreover,

$\displaystyle\lim_{q\rightarrow\infty}f(q)$
$\displaystyle=\lim_{1/q\rightarrow 0^{+}}f(q)=\lim_{1/q\rightarrow
0^{+}}\,\min_{b\in\mathbb{R},\|\bm{\rho}\|_{2}\leq
1}{\mathbb{E}\Big{[}\big{(}G+E_{Y}^{T}\mathbf{V}\mathbf{S}\bm{\rho}+\frac{b\,Y-\Delta_{Y}}{q}\big{)}_{-}^{2}\Big{]}}-(1-\|\bm{\rho}\|_{2}^{2})\gamma$
$\displaystyle=\lim_{1/q\rightarrow
0^{+}}\,\min_{\tilde{b}\in\mathbb{R},\|\bm{\rho}\|_{2}\leq
1}{\mathbb{E}\Big{[}\big{(}G+E_{Y}^{T}\mathbf{V}\mathbf{S}\bm{\rho}+\tilde{b}Y-\frac{\Delta_{Y}}{q}\big{)}_{-}^{2}\Big{]}}-(1-\|\bm{\rho}\|_{2}^{2})\gamma$
$\displaystyle\leq\min_{\tilde{b}\in\mathbb{R},\|\bm{\rho}\|_{2}\leq
1}{\mathbb{E}\Big{[}\big{(}G+E_{Y}^{T}\mathbf{V}\mathbf{S}\bm{\rho}+\tilde{b}Y\big{)}_{-}^{2}\Big{]}}-(1-\|\bm{\rho}\|_{2}^{2})\gamma$
$\displaystyle\leq\min_{\tilde{b}\in\mathbb{R},\|\bm{\rho}\|_{2}\leq
1}(1-\|\bm{\rho}\|_{2}^{2})\cdot\Big{(}{\mathbb{E}\Big{[}\Big{(}(G+E_{Y}^{T}\mathbf{V}\mathbf{S}\bm{\rho}+\tilde{b}Y)/\sqrt{1-\|\bm{\rho}\|_{2}^{2}}\Big{)}_{-}^{2}\Big{]}}-\gamma\Big{)}$
$\displaystyle\leq\min_{\tilde{b}\in\mathbb{R},\|\bm{\rho}\|_{2}\leq
1}\,{\mathbb{E}\Big{[}\Big{(}(G+E_{Y}^{T}\mathbf{V}\mathbf{S}\bm{\rho}+\tilde{b}Y)/\sqrt{1-\|\bm{\rho}\|_{2}^{2}}\Big{)}_{-}^{2}\Big{]}}-\gamma$
$\displaystyle\leq\min_{\breve{b}\in\mathbb{R},\mathbf{t}\in\mathbb{R}^{r}}\,{\mathbb{E}\Big{[}\big{(}\sqrt{1+\|\mathbf{t}\|_{2}^{2}}\,G+E_{Y}^{T}\mathbf{V}\mathbf{S}\mathbf{t}+\breve{b}Y\big{)}_{-}^{2}\Big{]}}-\gamma=\gamma_{\star}-\gamma<0,$

where to get the penultimate inequality we used the change of variables
$\mathbf{t}=\bm{\rho}/\sqrt{1-\|\bm{\rho}\|_{2}^{2}}$ and
$\breve{b}=\tilde{b}/\sqrt{1-\|\bm{\rho}\|_{2}^{2}}$. Also, in the last line
above, we used the definition of the phase-transition threshold
$\gamma_{\star}$ in Equation (64) and the theorem’s assumption that
$\gamma>\gamma_{\star}$ (aka separable regime).

We note that similar uniqueness argument was presented in [DKT19] for the
special case of antipodal means, _no_ intercept and $\delta=1.$

###  F.4 Antipodal means and non-isotropic data

Antipodal means. In the special case of antipodal means of equal energy
$\bm{\mu}_{+}=-\bm{\mu}_{-}=\bm{\mu}$ with $s:=\|\bm{\mu}\|_{2}$, the formulas
of Theorem 2 simplify as we have $r=1$ with $\mathbf{S}=s\sqrt{2}$ and
$\mathbf{V}=[1/\sqrt{2}\,,\,-1\sqrt{2}]^{T}$. Now, the function
$\eta_{\delta}$ can be written as
$\mathbb{E}\big{[}(G+\tilde{\rho}s+\frac{\tilde{b}}{\tilde{q}}Y-\frac{1}{\tilde{q}}\Delta_{Y})_{-}^{2}\big{]}-\left(1-{\tilde{\rho}}^{2}\right)\gamma.$
The asymptotic performance of SVM for this special geometry of the means has
been recently studied in [DKT19, MKL+20]. We extend this to the CS-SVM
classifier, to general means for the two classes and to
$\bm{\Sigma}\neq\mathbf{I}$.

Non-isotropic data. We show how Theorem 2 for the isotropic case can still be
applied in the general case $\bm{\Sigma}\neq\mathbf{I}$. Assume
$\bm{\Sigma}\succ 0$. Write
$\mathbf{x}_{i}=y_{i}\bm{\mu}_{y_{i}}+\bm{\Sigma}^{1/2}\mathbf{h}_{i}$ for
$\mathbf{h}_{i}\sim\mathcal{N}(0,\mathbf{I}_{d}).$ Consider whitened features
$\mathbf{z}_{i}:=\bm{\Sigma}^{-1/2}\mathbf{x}_{i}=y_{i}\bm{\Sigma}^{-1/2}\bm{\mu}_{y_{i}}+\mathbf{h}_{i}$
and let

$\displaystyle(\hat{\mathbf{w}},\hat{b})$
$\displaystyle=\arg\min_{\mathbf{w},b}\frac{1}{n}\sum_{i\in[n]}\ell(y_{i}(\mathbf{x}_{i}^{T}\mathbf{w}+b)),$
$\displaystyle(\hat{\mathbf{v}},\hat{c})$
$\displaystyle=\arg\min_{\mathbf{v},c}\frac{1}{n}\sum_{i\in[n]}\ell(y_{i}(\mathbf{z}_{i}^{T}\mathbf{v}+c)).$

Clearly, $\hat{\mathbf{w}}=\bm{\Sigma}^{-1/2}\hat{\mathbf{v}}$ and
$\hat{b}=\hat{c}$. Thus,

$\displaystyle\mathcal{R}_{+}\left((\hat{\mathbf{w}},\hat{b})\right)$
$\displaystyle=\mathbb{P}\\{(\mathbf{x}^{T}\hat{\mathbf{w}}+\hat{b})<0\,|\,y=+1\\}=\mathbb{P}\\{\bm{\mu}_{+}^{T}\hat{\mathbf{w}}+\hat{\mathbf{w}}^{T}\bm{\Sigma}^{1/2}\mathbf{h}+\hat{b}<0\\}=Q\left(\frac{\bm{\mu}_{+}^{T}\hat{\mathbf{w}}+\hat{b}}{\|\bm{\Sigma}^{1/2}\hat{\mathbf{w}}\|_{2}}\right)$
$\displaystyle=Q\Big{(}\frac{\bm{\mu}_{+}^{T}\bm{\Sigma}^{-1/2}\hat{\mathbf{v}}+\hat{c}}{\|\hat{\mathbf{v}}\|_{2}}\Big{)}=\mathbb{P}\\{(\mathbf{z}^{T}\hat{\mathbf{v}}+\hat{c})<0\,|\,y=+1\\}$
$\displaystyle=\mathcal{R}_{+}\left((\hat{\mathbf{v}},\hat{c})\right)$

Similar derivation holds for $\mathcal{R}_{-}$. Thus, we can just apply
Theorem 2 for $\mathbf{S},\mathbf{V}$ given by the eigendecomposition of the
new Grammian $\mathbf{M}^{T}\bm{\Sigma}^{-1}\mathbf{M}$.

###  F.5 Phase transition of CS-SVM

Here, we present a formula for the threshold $\gamma_{\star}$ such that the
CS-SVM of (4) is feasible (resp., infeasible) with overwhelming probability
provided that $\gamma>\gamma_{\star}$ (resp., $\gamma<\gamma_{\star}$). The
first observation is that the phase-transition threshold $\gamma_{\star}$ of
feasibility of the CS-SVM is the same as the threshold of feasibility of the
standard SVM for the same model; see Section D.1.3. Then, the desired result
follows [KT21a] who very recently established separability phase-transitions
for the more general multiclass Gaussian mixture model

######  Proposition 1 ([KT21a]).

Consider the same data model and notation as in Theorem 2 and define the event

$\mathcal{E}_{{\rm
sep},n}:=\left\\{\exists(\mathbf{w},b)\in\mathbb{R}^{d}\times\mathbb{R}~{}~{}\text{s.t.}~{}~{}y_{i}(\mathbf{w}^{T}\mathbf{x}_{i}+b)\geq
1,\,~{}\forall i\in[n]\right\\}.$

Define threshold $\gamma_{\star}:=\gamma_{\star}(\mathbf{V},\mathbf{S},\pi)$
as follows:

$\displaystyle\gamma_{\star}:=\min_{\mathbf{t}\in\mathbb{R}^{r},b\in\mathbb{R}}\mathbb{E}\left[\Big{(}\sqrt{1+\|\mathbf{t}\|_{2}^{2}}\,G+E_{Y}^{T}\mathbf{V}\mathbf{S}\mathbf{t}-bY\Big{)}_{-}^{2}\right].$
(64)

Then, the following hold:

$\displaystyle\gamma>\gamma_{\star}\Rightarrow\lim_{n\rightarrow\infty}\mathbb{P}(\mathcal{E}_{{\rm
sep},n})=1\quad\text{ and
}\quad\gamma<\gamma_{\star}\Rightarrow\lim_{n\rightarrow\infty}\mathbb{P}(\mathcal{E}_{{\rm
sep},n})=0.$

In words, the data are linearly separable (with overwhelming probability) if
and only if $\gamma>\gamma_{\star}$. Furthermore, if this condition holds,
then CS-SVM is feasible (with overwhelming probability) for any value of
$\delta>0$.

##  Appendix G Asymptotic analysis of GS-SVM

Figure 17: Visualizing the Gaussian mixture model of Section 4 with $K=2$
imbalanced groups in the two-dimensional space ($d=2$). Different colors
(resp., markers) correspond to different class (resp., group) membership.
Examples in the minority group correspond to cross markers ($\times$). The
means of the majority / minority groups are depicted in white / green markers.
The purple line illustrates the group-sensitive SVM (GS-SVM) classifier that
forces larger margin to the minority group examples in relation to standard
SVM in green.

In Theorem 2 we derived the asymptotic generalization performance of CS-SVM
under the Gaussian mixture data model. Here, we state the counterpart result
for GS-SVM with an appropriate Gaussian mixture data model with group
imbalances, which we repeat here for convenience.

Data model. We study a binary Gaussian-mixture generative model (GMM) for the
data distribution $\mathcal{D}$. For the label $y\in\\{\pm 1\\}$ let
$\pi:=\mathbb{P}\\{y=+1\\}.$ Group membership is decided conditionally on the
label such that $\forall j\in[K]:$ $\mathbb{P}\\{g=j|y=\pm 1\\}=p_{\pm,j}$,
with $\sum_{j\in[K]}p_{+,j}=\sum_{j\in[K]}p_{-,j}=1$. Finally, the feature
conditional given label $y$ and group $g$ is a multivariate Gaussian of mean
$\bm{\mu}_{y,g}\in\mathbb{R}^{d}$ and covariance $\bm{\Sigma}_{y,g}$, that is,
$\mathbf{x}\big{|}(y,g)\,\mathrel{\overset{}{\scalebox{1.5}[1.0]{$\sim$}}}\mathcal{N}(\bm{\mu}_{y,g},\bm{\Sigma}_{y,g}).$
We focus on two groups $K=2$ with
$p_{+,1}=p_{-,1}=p<1-p=p_{+,2}=p_{-,2},\,j=1,2$ and
$\mathbf{x}\,|\,(y,g)\sim\mathcal{N}(y\bm{\mu}_{g},\sigma_{g}\mathbf{I}_{d})$,
for $\sigma_{1}^{2},\sigma_{2}^{2}$ the noise variances of the minority and
the majority groups, respectively. As before, let $\mathbf{M}$ denote the
matrix of means (that is
$\mathbf{M}=\begin{bmatrix}\bm{\mu}_{+}&\bm{\mu}_{-}\end{bmatrix}$ and
$\mathbf{M}=\begin{bmatrix}\bm{\mu}_{1}&\bm{\mu}_{2}\end{bmatrix}$,
respectively) and consider the eigen-decomposition of its Gramian:
$\mathbf{M}^{T}\mathbf{M}=\mathbf{V}\mathbf{S}^{2}\mathbf{V}^{T},~{}~{}\mathbf{S}\succ\mathbf{0}_{r\times
r},\mathbf{V}\in\mathbb{R}^{2\times r},r\in\\{1,2\\},$ with $\mathbf{S}$ an
$r\times r$ diagonal positive-definite matrix and $\mathbf{V}$ an orthonormal
matrix obeying $\mathbf{V}^{T}\mathbf{V}=\mathbf{I}_{r}$. We study linear
classifiers with $h(\mathbf{x})=\mathbf{x}$.

Learning regime. Again, as in Theorem 2, we focus on a regime where training
data are linearly separable. Specifically, there exists threshold
$\widetilde{\gamma}_{\star}:=\widetilde{\gamma}_{\star}(\mathbf{V},\mathbf{S},\pi,p)\leq
1/2$, such that GMM data with groups are linearly separable with probability
approaching one provided that $\gamma>\widetilde{\gamma}_{\star}$ (see Section
G.2). We assume $\gamma>\widetilde{\gamma}_{\star}$, so that GS-SVM is
feasible with probability approaching 1.

Although similar in nature, the result below differs to Theorem 2 since now
each class itself is a Gaussian mixture.

######  Theorem 7 (Sharp asymptotics of GS-SVM).

Consider the GMM with feature distribution and priors as specified in the
‘Data model’ above. Fix $\delta>0$ (corresponding to group VS-loss with
$\Delta_{y,g}=\Delta_{g},g=1,2$ such that $\delta=\Delta_{2}/\Delta_{1}$).
Define $G,Y,S,{\widetilde{\Delta}}_{S},\Sigma_{S}\in\mathbb{R},$ and
$\widetilde{E}_{S}\in\mathbb{R}^{2\times 1}$ as follows:
$G\sim\mathcal{N}(0,1)$; $Y$ is a symmetric Bernoulli with
$\mathbb{P}\\{Y=+1\\}=\pi$; $S$ takes values $1$ or $2$ with probabilities $p$
and $1-p$, respectively;
$\widetilde{E}_{S}=\mathbf{e}_{1}\mathds{1}[S=1]+\mathbf{e}_{2}\mathds{1}[S=2]$;
${\widetilde{\Delta}}_{S}=\delta\cdot\mathds{1}[S=1]+1\cdot\mathds{1}[S=2]$
and $\Sigma_{S}=\sigma_{1}\mathds{1}[S=1]+\sigma_{2}\mathds{1}[S=2]$. With
these define function $\widetilde{\eta}_{\delta}:\mathbb{R}_{\geq
0}\times{\mathcal{S}}^{r}\times\mathbb{R}\rightarrow\mathbb{R}$ as

$\widetilde{\eta}_{\delta}(q,\bm{\rho},b):=\mathbb{E}\big{(}G+\Sigma_{S}^{-1}\widetilde{E}_{S}^{T}\mathbf{V}\mathbf{S}\bm{\rho}+\frac{b\Sigma_{S}^{-1}Y-\Sigma_{S}^{-1}{\widetilde{\Delta}}_{S}}{q}\big{)}_{-}^{2}-(1-\|\bm{\rho}\|_{2}^{2})\gamma.$

Let
$(\widetilde{q}_{\delta},\widetilde{\bm{\rho}}_{\delta},\widetilde{b}_{\delta})$
be the unique triplet satisfying (42) but with $\eta_{\delta}$ replaced with
the function $\widetilde{\eta}_{\delta}$ above. Then, in the limit of
$n,d\rightarrow\infty$ with $d/n=\gamma>\widetilde{\gamma}_{\star}$ it holds
for $i=1,2$ that
$\mathcal{R}_{\pm,i}\stackrel{{\scriptstyle{P}}}{{\longrightarrow}}Q\big{(}{\mathbf{e}_{i}^{T}\mathbf{V}\mathbf{S}\widetilde{\bm{\rho}}_{\delta}\pm\widetilde{b}_{\delta}/{\widetilde{q}_{\delta}}}\big{)}$.
In particular, $\mathcal{R}_{\rm
deo}\stackrel{{\scriptstyle{P}}}{{\longrightarrow}}Q\big{(}{\mathbf{e}_{1}^{T}\mathbf{V}\mathbf{S}\widetilde{\bm{\rho}}_{\delta}+\widetilde{b}_{\delta}/{\widetilde{q}_{\delta}}}\big{)}-Q\big{(}{\mathbf{e}_{2}^{T}\mathbf{V}\mathbf{S}\widetilde{\bm{\rho}}_{\delta}+\widetilde{b}_{\delta}/{\widetilde{q}_{\delta}}}\big{)}.$

###  G.1 Proof of Theorem 7

The proof of Theorem 7 also relies on the CGMT framework and is very similar
to the proof of Theorem 2. To avoid repetitions, we only present the part that
is different. As we will show the PO is slightly different as now we are
dealing with a classification between mixtures of mixtures of Gaussians. We
will derive the new AO and will simplify it to a point from where the same
steps as in Section F.3 can be followed mutatis mutandis.

Let $(\hat{\mathbf{w}},\hat{b})$ be solution pair to the GS-SVM for some fixed
parameter $\delta>0$, which we rewrite here expressing the constraints in
matrix form:

$\displaystyle\min_{\mathbf{w},b}\|\mathbf{w}\|_{2}~{}~{}\text{sub.
to}~{}\begin{cases}y_{i}(\mathbf{w}^{T}\mathbf{x}_{i}+b)\geq\delta,~{}g_{i}=1\\\
y_{i}(\mathbf{w}^{T}\mathbf{x}_{i}+b)\geq
1,~{}g_{i}=2\end{cases},~{}i\in[n]~{}~{}=~{}~{}\min_{\mathbf{w},b}\|\mathbf{w}\|_{2}~{}~{}\text{sub.
to}~{}\mathbf{D}_{\mathbf{y}}(\mathbf{X}\mathbf{w}+b\mathbf{1}_{n})\geq\bm{\delta}_{\mathbf{g}},$
(65)

where we have used the notation

$\displaystyle\mathbf{X}^{T}$
$\displaystyle=\begin{bmatrix}\mathbf{x}_{1}&\cdots&\mathbf{x}_{n}\end{bmatrix},~{}\mathbf{y}=\begin{bmatrix}y_{1}&\cdots&y_{n}\end{bmatrix}^{T},$
$\displaystyle\mathbf{D}_{\mathbf{y}}$
$\displaystyle=\rm{diag}(\mathbf{y})~{}\text{and}~{}\bm{\delta}_{\mathbf{g}}=\begin{bmatrix}\delta\mathds{1}[g_{1}=1]+\mathds{1}[g_{1}=2]&\cdots&\delta\mathds{1}[g_{n}=1]+\mathds{1}[g_{n}=2]\end{bmatrix}^{T}.$

We further need to define the following one-hot-encoding for group membership:

$\mathbf{g}_{i}=\mathbf{e}_{1}\mathds{1}[g_{i}=1]+\mathbf{e}_{2}\mathds{1}[g_{i}=2],\quad\text{and}\quad\mathbf{G}_{n\times
2}^{T}=\begin{bmatrix}\mathbf{g}_{1}&\cdots&\mathbf{g}_{n}\end{bmatrix}.$

where recall that $\mathbf{e}_{1},\mathbf{e}_{2}$ are standard basis vectors
in $\mathbb{R}^{2}$. Finally, let

$\mathbf{D}_{\sigma}={\rm
diag}\big{(}\begin{bmatrix}\sigma_{g_{1}}&\cdots&\sigma_{g_{n}}\end{bmatrix}\big{)}.$

With these, notice for later use that under our model,
$\mathbf{x}_{i}=y_{i}\bm{\mu}_{g_{i}}+\sigma_{g_{i}}\mathbf{z}_{i}=y_{i}\mathbf{M}\mathbf{g}_{i}+\sigma_{g_{i}}\mathbf{z}_{i},~{}\mathbf{z}_{i}\sim\mathcal{N}(0,1)$.
Thus, in matrix form with $\mathbf{Z}$ having entries $\mathcal{N}(0,1)$:

$\displaystyle\mathbf{X}=\mathbf{D}_{\mathbf{y}}\mathbf{G}\mathbf{M}^{T}+\mathbf{D}_{\sigma}\mathbf{Z}.$
(66)

As usual, we express the GS-SVM program in a min-max form to bring it in the
form of the PO as follows:

$\displaystyle\min_{\mathbf{w},b}\max_{\mathbf{u}\leq
0}~{}\frac{1}{2}\|\mathbf{w}\|_{2}^{2}+\mathbf{u}^{T}\mathbf{D}_{\mathbf{y}}\mathbf{X}\mathbf{w}+b(\mathbf{u}^{T}\mathbf{D}_{\mathbf{y}}\mathbf{1}_{n})-\mathbf{u}^{T}\bm{\delta}_{\mathbf{g}}$
$\displaystyle=$ $\displaystyle\min_{\mathbf{w},b}\max_{\mathbf{u}\leq
0}~{}\frac{1}{2}\|\mathbf{w}\|_{2}^{2}+\mathbf{u}^{T}\mathbf{D}_{\mathbf{y}}\mathbf{D}_{\sigma}\mathbf{Z}\mathbf{w}+\mathbf{u}^{T}\mathbf{G}\mathbf{M}^{T}\mathbf{w}+b(\mathbf{u}^{T}\mathbf{D}_{\mathbf{y}}\mathbf{1}_{n})-\mathbf{u}^{T}\bm{\delta}_{\mathbf{g}}.$
(67)

where in the last line we used (66) and
$\mathbf{D}_{\mathbf{y}}\mathbf{D}_{\mathbf{y}}=\mathbf{I}_{n}$. We
immediately recognize that the last optimization is in the form of a PO and
the corresponding AO is as follows:

$\displaystyle\min_{\mathbf{w},b}\max_{\mathbf{u}\leq
0}~{}\frac{1}{2}\|\mathbf{w}\|_{2}^{2}+\|\mathbf{w}\|_{2}\mathbf{u}^{T}\mathbf{D}_{\mathbf{y}}\mathbf{D}_{\sigma}\mathbf{h}_{n}+\|\mathbf{D}_{\mathbf{y}}\mathbf{D}_{\sigma}\mathbf{u}\|_{2}\mathbf{h}_{d}^{T}\mathbf{w}+\mathbf{u}^{T}\mathbf{G}\mathbf{M}^{T}\mathbf{w}+b(\mathbf{u}^{T}\mathbf{D}_{\mathbf{y}}\mathbf{1}_{n})-\mathbf{u}^{T}\bm{\delta}_{\mathbf{g}}.$
(68)

where $\mathbf{h}_{n}\sim\mathcal{N}(0,\mathbf{I}_{n})$ and
$\mathbf{h}_{d}\sim\mathcal{N}(0,\mathbf{I}_{d})$.

As in Section F.3 we consider the one-sided constrained AO in (68). Towards
simplifying this auxiliary optimization, note that
$\mathbf{D}_{y}\mathbf{h}_{n}\sim\mathbf{h}_{n}$ by rotational invariance of
the Gaussian measure. Also,
$\|\mathbf{D}_{\mathbf{y}}\mathbf{D}_{\sigma}\mathbf{u}\|_{2}=\|\mathbf{D}_{\sigma}\mathbf{u}\|_{2}$.
Thus, we can express the AO in the following more convenient form:

$\displaystyle\min_{\|\mathbf{w}\|_{2}^{2}+b^{2}\leq R}\max_{\mathbf{u}\leq
0}~{}\frac{1}{2}\|\mathbf{w}\|_{2}^{2}+\|\mathbf{w}\|_{2}\mathbf{u}^{T}\mathbf{D}_{\sigma}\mathbf{h}_{n}+\|\mathbf{D}_{\sigma}\mathbf{u}\|_{2}\mathbf{h}_{d}^{T}\mathbf{w}+\mathbf{u}^{T}\mathbf{G}\mathbf{M}^{T}\mathbf{w}+b(\mathbf{u}^{T}\mathbf{D}_{\mathbf{y}}\mathbf{1}_{n})-\mathbf{u}^{T}\bm{\delta}_{\mathbf{g}}$
$\displaystyle=$ $\displaystyle\min_{\|\mathbf{w}\|_{2}^{2}+b^{2}\leq
R}\max_{\mathbf{v}\leq
0}~{}\frac{1}{2}\|\mathbf{w}\|_{2}^{2}+\|\mathbf{w}\|_{2}\mathbf{v}^{T}\mathbf{h}_{n}+\|\mathbf{v}\|_{2}\mathbf{h}_{d}^{T}\mathbf{w}+\mathbf{v}^{T}\mathbf{D}_{\sigma}^{-1}\mathbf{G}\mathbf{M}^{T}\mathbf{w}+b(\mathbf{v}^{T}\mathbf{D}_{\sigma}^{-1}\mathbf{D}_{\mathbf{y}}\mathbf{1}_{n})-\mathbf{v}^{T}\mathbf{D}_{\sigma}^{-1}\bm{\delta}_{\mathbf{g}},$

where in the second line we performed the change of variables
$\mathbf{v}\leftrightarrow\mathbf{D}_{\sigma}\mathbf{u}$ and used positivity
of the diagonal entries of $\mathbf{D}_{\sigma}$ to find that $\mathbf{u}\leq
0\iff\mathbf{v}\leq 0$.

Notice that the optimization in the last line above is very similar to the AO
(54) in Section F.3. Following analogous steps, omitted here for brevity, we
obtain the following scalarized AO:

$\displaystyle\min_{\begin{subarray}{c}q\geq\sqrt{\mu_{1}^{2}+\mu_{2}^{2}+\alpha^{2}}\\\
q^{2}+b^{2}\leq R\end{subarray}}~{}\frac{1}{2}q^{2}\quad$ (69)
$\displaystyle\text{sub.
to}\quad\frac{1}{\sqrt{n}}\Big{\|}\big{(}\,q\mathbf{h}_{n}+\mathbf{D}_{\sigma}^{-1}\mathbf{G}\mathbf{V}\mathbf{S}\begin{bmatrix}\mu_{1}\\\
\mu_{2}\end{bmatrix}+b\,\mathbf{D}_{\sigma}^{-1}\mathbf{D}_{y}\mathbf{1}_{n}-\mathbf{D}_{\sigma}^{-1}\bm{\delta}_{\mathbf{g}}\,\big{)}_{-}\Big{\|}_{2}$
$\displaystyle-\mu_{1}\frac{\mathbf{h}_{d}^{T}\mathbf{u}_{1}}{\sqrt{n}}-\mu_{2}\frac{\mathbf{h}_{d}^{T}\mathbf{u}_{2}}{\sqrt{n}}-\alpha\frac{\|\mathbf{h}_{d}^{T}\mathbf{U}^{\perp}\|_{2}}{\sqrt{n}}\leq
0.$

where as in Section F.3 we have decomposed the matrix of means
$\mathbf{M}=\mathbf{U}\mathbf{S}\mathbf{V}^{T}$ and $\mu_{1},\mu_{2},\alpha$
above represent $\mathbf{u}_{1}^{T}\mathbf{w}$, $\mathbf{u}_{1}^{T}\mathbf{w}$
and $\|\mathbf{w}^{\perp}\|_{2}$. Now, by law of large numbers, notice that
for fixed $(q,\mu_{1},\mu_{2},\alpha,b)$, the functional in the constraint
above converges in probability to

$\displaystyle\bar{L}(q,\mu_{1},\mu_{2},\alpha,b):=\sqrt{\mathbb{E}\big{(}qG+\Sigma_{S}^{-1}\widetilde{E}_{S}^{T}\mathbf{V}\mathbf{S}\begin{bmatrix}\mu_{1}\\\
\mu_{2}\end{bmatrix}+{b\,\Sigma_{S}^{-1}Y-\Sigma_{S}^{-1}{\widetilde{\Delta}}_{S}}\big{)}_{-}^{2}}-\alpha\sqrt{\gamma},$
(70)

where the random variables $G,\widetilde{E}_{S},Y,{\widetilde{\Delta}}_{S}$
and $\Sigma_{S}$ are as in the statement of the theorem. Thus, the
deterministic equivalent (high-dimensional limit) of the AO expressed in
variables $\bm{\rho}=\begin{bmatrix}\bm{\rho}_{1}\\\
\bm{\rho}_{2}\end{bmatrix}:=\begin{bmatrix}\mu_{1}/q\\\
\mu_{2}/q\end{bmatrix}$ becomes (cf. Eqn. (58)):

$\displaystyle\min_{q^{2}+b^{2}\leq R,q>0,\|\bm{\rho}\|_{2}\leq
1}~{}\frac{1}{2}q^{2}$ (71) $\displaystyle\text{sub.
to}\quad{\mathbb{E}\big{(}G+\Sigma_{S}^{-1}\widetilde{E}_{S}^{T}\mathbf{V}\mathbf{S}\bm{\rho}+\frac{b\,\Sigma_{S}^{-1}Y-\Sigma_{S}^{-1}\widetilde{\Delta}_{S}}{q}\big{)}_{-}^{2}}\leq\left({1-\|\bm{\rho}\|_{2}^{2}}\right){\gamma}.$

Now, recall the definition of the function $\widetilde{\eta}_{\delta}$ in the
statement of the theorem and observe that the constraint above is nothing but

$\widetilde{\eta}_{\delta}(q,\bm{\rho},b)\leq 0.$

Thus, (71) becomes

$\displaystyle\min\left\\{q^{2}~{}\Big{|}~{}0\leq q\leq\sqrt{R}\quad\text{ and
}\quad\min_{b^{2}\leq R-q^{2},\|\bm{\rho}\|_{2}\leq
1}\widetilde{\eta}_{\delta}(q,\bm{\rho},b)\leq 0\right\\}.$ (72)

The remaining steps of the proof are very similar to those in Section F.3 and
are omitted.

###  G.2 Phase transition of GS-SVM

The phase-transition threshold $\widetilde{\gamma}_{\star}$ of feasibility of
the GS-SVM is the same as the threshold of feasibility of the standard SVM for
the same model (see Section D.1.2). But, the feasibility threshold of SVM
under the group GMM with $K=2$ groups is different from that of Section F.5
for $K=1$, since now each class is itself a mixture of Gaussians. We derive
the desired result from [KT21a], who recently studied the separability
question for the more general case of a multiclass mixture of mixtures of
Gaussians.

######  Proposition 2.

Consider the same data model and notation as in Theorem 7 and consider the
event

$\mathcal{E}_{{\rm
sep},n}:=\left\\{\exists(\mathbf{w},b)\in\mathbb{R}^{d}\times\mathbb{R}~{}~{}\text{s.t.}~{}~{}y_{i}(\mathbf{w}^{T}\mathbf{x}_{i}+b)\geq
1,\,~{}\forall i\in[n]\right\\}.$

Define threshold $\gamma_{\star}:=\gamma_{\star}(\mathbf{V},\mathbf{S},\pi)$
as follows:

$\displaystyle\widetilde{\gamma}_{\star}:=\min_{\mathbf{t}\in\mathbb{R}^{r},b\in\mathbb{R}}\mathbb{E}\left[\Big{(}\sqrt{1+\|\mathbf{t}\|_{2}^{2}}\,G+\widetilde{E}_{S}^{T}\mathbf{V}\mathbf{S}\mathbf{t}-bY\Big{)}_{-}^{2}\right].$
(73)

Then, the following hold:

$\displaystyle\gamma>\widetilde{\gamma}_{\star}\Rightarrow\lim_{n\rightarrow\infty}\mathbb{P}(\mathcal{E}_{{\rm
sep},n})=1\qquad\text{ and
}\qquad\gamma<\widetilde{\gamma}_{\star}\Rightarrow\lim_{n\rightarrow\infty}\mathbb{P}(\mathcal{E}_{{\rm
sep},n})=0.$

In words, the data are linearly separable with overwhelming probability if and
only if $\gamma>\widetilde{\gamma}_{\star}$. Furthermore, if this condition
holds, then GS-SVM is feasible with overwhelming probability for any value of
$\delta>0$.