# A Novel Gaussian Min-Max Theorem and its Applications

Danil Akhtiamov∗
Department of Computing and Mathematical Sciences
California Institute of Technology
Pasadena, CA 91125
<EMAIL_ADDRESS>
&David Bosch∗
Department of Data Science and AI, Computer Science and Engineering
Chalmers University of Technology
Gothenburg, Sweden, 41296
<EMAIL_ADDRESS>
&Reza Ghane∗
Department of Electrical Engineering
California Institute of Technology
Pasadena, CA 91125
<EMAIL_ADDRESS>
K Nithin Varma
Department of Computing and Mathematical Sciences
California Institute of Technology
Pasadena, CA 91125
<EMAIL_ADDRESS>
Babak Hassibi
Department of Electrical Engineering
California Institute of Technology
Pasadena, CA 91125
<EMAIL_ADDRESS>

###### Abstract

A celebrated result by Gordon allows one to compare the min-max behavior of
two Gaussian processes if certain inequality conditions are met. The
consequences of this result include the Gaussian min-max (GMT) and convex
Gaussian min-max (CGMT) theorems which have had far-reaching implications in
high-dimensional statistics, machine learning, non-smooth optimization, and
signal processing. Both theorems rely on a pair of Gaussian processes, first
identified by Slepian, that satisfy Gordon’s comparison inequalities. To date,
no other pair of Gaussian processes satisfying these inequalities has been
discovered. In this paper, we identify such a new pair. The resulting theorems
extend the classical GMT and CGMT Theorems from the case where the underlying
Gaussian matrix in the primary process has iid rows to where it has
independent but non-identically-distributed ones. The new CGMT is applied to
the problems of multi-source Gaussian regression, as well as to binary
classification of general Gaussian mixture models.

**footnotetext: Equal contribution

##  1 Introduction and Motivation

Assume the matrix $G\in{\mathbb{R}}^{n\times d}$, the vectors
$g\in{\mathbb{R}}^{d}$ and $h\in{\mathbb{R}}^{n}$, and the scalar $\gamma$ all
have i.i.d ${\cal N}(0,1)$, i.e., standard normal entries. Then, by
considering deterministic vectors $w\in{\mathbb{R}}^{d}$ and
$v\in{\mathbb{R}}^{n}$, belonging to some sets ${\cal S}_{w}$ and ${\cal
S}_{v}$, we can obtain the following pair of Gaussian processes

$X_{wv}=v^{T}Gw+\gamma\|w|_{2}\|v\|_{2}~{}~{}~{}\mbox{and}~{}~{}~{}Y_{wv}=\|v\|_{2}g^{T}w+\|w\|_{2}h^{T}v,$

which we will refer to as a Slepian pair (Slepian,, 1962). For such Slepian
pairs, it can be readily shown that

$EX_{wv}X_{w^{\prime}v^{\prime}}-EY_{wv}Y_{w^{\prime}v^{\prime}}=\left(\|w\|_{2}\|w^{\prime}\|_{2}-w^{T}w^{\prime})(\|v\|_{2}\|v^{\prime}\|_{2}-v^{T}v^{\prime}\right).$

By recalling Cauchy-Schwarz, this implies that the processes $X_{wv}$ and
$Y_{wv}$ satisfy the following (so-called) comparison inequalities

$EX_{wv}X_{w^{\prime}v^{\prime}}\leq
EY_{wv}Y_{w^{\prime}v^{\prime}}~{}~{}~{}\mbox{and}~{}~{}~{}EX_{wv}X_{wv^{\prime}}\geq
EY_{wv}Y_{wv^{\prime}}$ (1)

For Gaussian processes that satisfy the inequalities (1), Gordon, (1985)
showed that it is possible to relate

$\mathbb{P}\left(\min_{w\in{\cal S}_{w}}\max_{v\in{\cal
S}_{v}}X_{wv}\geq\psi(w,v)\right)~{}~{}~{}\mbox{to}~{}~{}~{}\mathbb{P}\left(\min_{w\in{\cal
S}_{w}}\max_{v\in{\cal S}_{v}}Y_{wv}\geq\psi(w,v)\right),$

for any function $\psi(w,v)$. We refer the reader to the next section for more
details. This remarkable result allows one to infer properties of a so-called
primary optimization (PO)

$\min_{w\in{\cal S}_{w}}\max_{v\in{\cal S}_{v}}v^{T}Gw+\psi(w,v)$

in terms of a simpler so-called auxiliary optimization (AO)

$\min_{w\in{\cal S}_{w}}\max_{v\in{\cal
S}_{v}}\|v\|_{2}g^{T}w+\|w\|_{2}h^{T}v+\psi(w,v).$

This is the gist of the Gaussian min-max (GMT) (Gordon,, 1988) and convex
Gaussian min-max (CGMT) (Thrampoulidis et al.,, 2014) theorems. The CGMT, in
particular, has found numerous recent applications where, along with
statistical physics-inspired methods, such as the replica method and
approximate message passing (AMP), it has been used to derive sharp bounds on
the performance of a variety of problems in high-dimensional statistics,
machine learning, non-smooth convex optimization, and signal processing (e.g.,
(Stojnic,, 2013; Salehi et al.,, 2019; Akhtiamov et al.,, 2023; Mignacco et
al.,, 2020; Thrampoulidis et al.,, 2018; Javanmard and Soltanolkotabi,, 2022;
Montanari et al.,, 2019; Salehi et al.,, 2020; Aolaritei et al.,, 2023))

To date, other than the aforementioned Slepian pair of Gaussian processes, no
other pair of Gaussian processes have been found that satisfy the comparison
inequalities (1). As such it has not been clear whether the comparison lemma
of Gordon, (1985) can be applied to any other processes, and so, whether it
had any power beyond what is obtained from GMT and CGMT.

In this paper, for the first time, we identify a novel pair of Gaussian
processes that satisfy the inequalities (1) and for which the consequences of
Gordon, (1985) can be brought to bear.

The new pair of processes are

$X_{w,v_{1},\ldots,v_{k}}=\sum_{\ell=1}^{k}\left[v_{\ell}^{T}G_{\ell}\Sigma_{\ell}^{\frac{1}{2}}w+\gamma_{\ell}\|\Sigma_{\ell}^{\frac{1}{2}}w\|_{2}\|v_{\ell}\|_{2}\right],$

and

$Y_{w,v_{1},\ldots,v_{k}}=\sum_{\ell=1}^{k}\left[\|v_{\ell}\|_{2}g_{\ell}^{T}\Sigma_{\ell}^{\frac{1}{2}}w+\|\Sigma_{\ell}^{\frac{1}{2}}w\|_{2}h_{\ell}^{T}v_{\ell}\right],$

where $\\{G_{\ell}\in{\mathbb{R}}^{n_{\ell}\times d}\\}_{\ell=1}^{k}$,
$\\{g_{\ell}\in{\mathbb{R}}^{d}\\}_{\ell=1}^{k}$,
$\\{h_{\ell}\in{\mathbb{R}}^{n_{\ell}}\\}_{\ell=1}^{k}$ and $\\{\gamma_{\ell}\
\in{\mathbb{R}}\\}_{\ell=1}^{k}$ all have i.i.d ${\cal N}(0,1)$ standard
normal entries and $\Sigma_{\ell}^{1/2}$ are $d\times d$ are positive semi-
definite (PSD) matrices.

The remainder of the paper is devoted to obtaining the CGMT counterpart of the
above pair of Gaussian random processes and to applying this novel CGMT to
analyze two specific problems: firstly, multi-source Gaussian regression and,
secondarily, binary classification of general Gaussian mixture models. We note
that neither problem lends itself to analysis via the conventional CGMT.

##  2 Preliminaries

###  2.1 Gordon’s comparison inequality for Gaussian Processes

Introduced by Gordon in his landmark paper (Gordon,, 1985), the following
comparison inequality is instrumental in proving the main results of our
paper:

######  Theorem 1 (Gordon’s comparison inequality).

Let $I$ and $J$ be two _finite_ sets and $\\{X_{ij}\\}_{i\in I,j\in J}$,
$\\{Y_{ij}\\}_{i\in I,j\in J}$ be two real valued Gaussian processes, which
satisfy the following conditions:

  1. 1.

$\mathbb{E}X_{ij}=\mathbb{E}Y_{ij}$ for all $i\in I,j\in J$

  2. 2.

$\mathbb{E}(X_{ij}-\mathbb{E}X_{ij})^{2}=\mathbb{E}(Y_{ij}-\mathbb{E}Y_{ij})^{2}$
for all $i\in I,j\in J$

  3. 3.

$\mathbb{E}(X_{ij}-\mathbb{E}X_{ij})(X_{ij^{\prime}}-\mathbb{E}X_{ij^{\prime}})\geq\mathbb{E}(Y_{ij}-\mathbb{E}Y_{ij})(Y_{ij^{\prime}}-\mathbb{E}Y_{ij^{\prime}})$
for all $i\in I,j,j^{\prime}\in J$

  4. 4.

$\mathbb{E}(X_{ij}-\mathbb{E}X_{ij})(X_{i^{\prime}j^{\prime}}-\mathbb{E}X_{i^{\prime}j^{\prime}})\leq\mathbb{E}(Y_{ij}-\mathbb{E}Y_{ij})(Y_{i^{\prime}j^{\prime}}-\mathbb{E}Y_{i^{\prime}j^{\prime}})$
for all $i\neq i^{\prime}\in I,j,j^{\prime}\in J$

Let $\\{t_{ij}\\}_{i\in I,j\in J}$ be an arbitrary sequence of real numbers
indexed by $(i,j)\in I\times J$. Then the following inequality holds:

$\displaystyle\mathbb{P}\left(\bigcap_{i\in I}\bigcup_{j\in J}[Y_{ij}\geq
t_{ij}]\right)\geq\mathbb{P}\left(\bigcap_{i\in I}\bigcup_{j\in J}[X_{ij}\geq
t_{ij}]\right)$

Now, let $G\in\mathbb{R}^{n\times d}$, $\gamma\in\mathbb{R}$,
$g\in\mathbb{R}^{d}$, $h\in\mathbb{R}^{n}$ all have i.i.d $\mathcal{N}(0,1)$
components, $I$ and $J$ be finite sets and $\\{w_{i}\\}_{i\in
I}\subset\mathbb{R}^{d}$, $\\{u_{j}\\}_{j\in J}\subset\mathbb{R}^{n}$ be
arbitrary discrete subsets. It was first observed in Gordon, (1988) that the
following processes satisfy the assumptions of Theorem 1:

$\displaystyle Y_{ij}=v_{j}^{T}Gw_{i}+\gamma\|w_{i}\|_{2}\|v_{j}\|_{2}$
$\displaystyle X_{ij}=\|v_{j}\|_{2}g^{T}w_{i}+\|w_{i}\|_{2}h^{T}v_{j}$

By making an appropriate choice for the values of $\\{t_{ij}\\}_{i\in I,j\in
J}$, and by proving that finite discrete subsets can be extended to compact
sets, the following theorem can be proven. This theorem provides a
probabilistic upper bound on the value of a more complicated optimization
problem $\bm{\Phi}$, which extends $Y_{ij}$, being larger than some threshold
$t$, by means of the same quantity for an alternative optimization $\phi$,
which extends $X_{ij}$. The alternative problem, $\phi$, is in general easier
to analyze.

######  Theorem 2.

Let
$\mathcal{S}_{w}\subset\mathbb{R}^{d},\mathcal{S}_{v}\subset\mathbb{R}^{n}$ be
compact sets and $\psi(w,v):\mathcal{S}_{w}\times\mathcal{S}_{v}\to\mathbb{R}$
be a continuous function. Let $G\in\mathbb{R}^{n\times d}$,
$\gamma\in\mathbb{R}$, $g\in\mathbb{R}^{d}$, $h\in\mathbb{R}^{n}$ all have
i.i.d $\mathcal{N}(0,1)$ components, and be independent of each other. Then
letting

$\displaystyle\Phi(G,\gamma):=\min_{w\in\mathcal{S}_{w}}\max_{v\in\mathcal{S}_{v}}v^{T}Gw+\gamma\|w\|_{2}\|v\|_{2}+\psi(w,v)$
$\displaystyle\phi(g,h):=\min_{w\in\mathcal{S}_{w}}\max_{v\in\mathcal{S}_{v}}\|v\|_{2}g^{T}w+\|w\|_{2}h^{T}v+\psi(w,v)$

We have for any $t\in\mathbb{R}$

$\displaystyle\mathbb{P}(\Phi(G,\gamma)<t)\leq\mathbb{P}(\phi(g,h)<t)$

The theorem above has an immediate corollary:

######  Corollary 1 (Gaussian Min-Max Theorem).

Let
$\mathcal{S}_{w}\subset\mathbb{R}^{d},\mathcal{S}_{v}\subset\mathbb{R}^{n}$ be
compact sets and $\psi(w,v):\mathcal{S}_{w}\times\mathcal{S}_{v}\to\mathbb{R}$
be a continuous function. Furthermore, define $G\in\mathbb{R}^{n\times d}$,
$g\in\mathbb{R}^{d}$, $h\in\mathbb{R}^{n}$ all have i.i.d $\mathcal{N}(0,1)$
components. Then letting

$\displaystyle\Phi(G,\gamma):=\min_{w\in\mathcal{S}_{w}}\max_{v\in\mathcal{S}_{v}}v^{T}Gw+\psi(w,v)$
$\displaystyle\phi(g,h):=\min_{w\in\mathcal{S}_{w}}\max_{v\in\mathcal{S}_{v}}\|v\|_{2}g^{T}w+\|w\|_{2}h^{T}v+\psi(w,v)$

we have for any $t\in\mathbb{R}$

$\displaystyle\mathbb{P}(\Phi(G,\gamma)<t)\leq 2\mathbb{P}(\phi(g,h)<t)$

###  2.2 Standard CGMT

Informally, the corollary above has the following interpretation: if
$\phi(g,h)$ concentrates to a value $c$, then $\Phi(G,\gamma)<c+\epsilon$
holds with high probability for $\epsilon>0$. While this probabilistic upper
bound suffices for some applications, one might need to know the value of
$\Phi$ precisely for others. Another drawback of Corollary 1 is that it
provides information only about the value of $\Phi$ in terms of the value of
$\phi$ and does not yield any relation between their solutions. It turns out
that the inequality from the Corollary 1 can be reversed under the additional
assumptions that $\psi(w,v)$ is convex-concave and that the sets ${\cal
S}_{w}$ and ${\cal S}_{v}$ are convex. Furthermore, in this case, if the
solution of $\phi$ belongs to an open set $\mathcal{S}\subset\mathcal{S}_{w}$
with high probability then so does the solution of $\Phi$. Formally, the
following theorem holds (see (Thrampoulidis et al.,, 2014, 2015;
Thrampoulidis,, 2016)):

######  Theorem 3 (Convex Gaussian Min-Max Theorem).

Let
$\mathcal{S}_{w}\subset\mathbb{R}^{d},\mathcal{S}_{v}\subset\mathbb{R}^{d}$ be
compact convex sets and
$\psi(w,v):\mathcal{S}_{w}\times\mathcal{S}_{v}\to\mathbb{R}$ be convex-
concave. Furthermore, let $G\in\mathbb{R}^{n\times d}$, $g\in\mathbb{R}^{d}$,
$h\in\mathbb{R}^{n}$ all have i.i.d $\mathcal{N}(0,1)$ components. Define

$\displaystyle\Phi(G):=\min_{w\in\mathcal{S}_{w}}\max_{v\in\mathcal{S}_{v}}v^{T}Gw+\psi(w,v)$
$\displaystyle\phi(g,h):=\min_{w\in\mathcal{S}_{w}}\max_{v\in\mathcal{S}_{v}}\|v\|_{2}g^{T}w+\|w\|_{2}h^{T}v+\psi(w,v)$

The following statements hold:

  1. 1.

For any $\eta,c\in\mathbb{R}$

$\displaystyle\mathbb{P}(|\Phi(G)-c|>\eta)\leq
2\mathbb{P}(|\phi(g,h)-c|>\eta)$

  2. 2.

Let $\mathcal{S}$ be an arbitrary open subset of $\mathcal{S}_{w}$ and
$\mathcal{S}^{c}=\mathcal{S}_{w}\setminus\mathcal{S}$. Define:

$\displaystyle\Phi_{\mathcal{S}^{c}}(G):=\min_{w\in\mathcal{S}^{c}}\max_{v\in\mathcal{S}_{v}}v^{T}Gw+\psi(w,v)$
$\displaystyle\phi_{\mathcal{S}^{c}}(g,h):=\min_{w\in\mathcal{S}^{c}}\max_{v\in\mathcal{S}_{v}}\|v\|_{2}g^{T}w+\|w\|_{2}h^{T}v+\psi(w,v)$
$\displaystyle
w_{\Phi}(G)=\operatorname*{arg\,min}_{w\in\mathcal{S}_{w}}\max_{v\in\mathcal{S}_{v}}v^{T}Gw+\psi(w,v)$

Assume also that there exist
$\epsilon>0,\delta>0,\bar{\phi},\bar{\phi}_{\mathcal{S}^{c}}$ such that

     * •

$\bar{\phi}_{\mathcal{S}^{c}}\geq\bar{\phi}+3\delta$

     * •

$\phi(g,h)<\bar{\phi}+\delta$ with probability at least $1-\epsilon$

     * •

$\phi_{\mathcal{S}^{c}}>\bar{\phi}_{\mathcal{S}^{c}}-\delta$ with probability
at least $1-\epsilon$

Then

$\displaystyle\mathbb{P}(w_{\Phi}(G)\in\mathcal{S})\geq 1-4\epsilon$

###  2.3 Multi-source Gaussian regression

To demonstrate the power of the novel CGMT presented in this work, we will
focus on two examples. Here we consider Multi-source Gaussian Regression.
Consider a setup of $k$-measurement devices and consider a dataset of
$\left\\{(x_{i}^{l},y_{i}^{l})\in\mathbb{R}^{d}\times\mathbb{R}\right\\}_{i=1,l=1}^{n,k}$
of $n$ $d-$dimensional observations by each of the $k$ devices, with
corresponding labels $y_{i}^{l}$. We will define $y_{l}\in\mathbb{R}^{n}$
element wise by $(y_{l})_{i}=y_{i,l}$ and similarly define
$X_{l}\in\mathbb{R}^{n\times d}$ by means of $(X_{l})_{i,j}=(x^{l}_{i})_{j}$.
Our regression problem then takes the form of

$\min_{\theta\in\mathbb{R}^{d}}\frac{1}{nk}\sum_{l=1}^{k}\ell_{l}\left(y_{l}-\frac{1}{\sqrt{d}}X_{l}\theta\right)+R(\theta),$
(2)

where $\theta\in\mathbb{R}^{d}$ and $\ell_{l}$ and $R$ are convex loss and
regularization functions respectively. We shall assume that $X_{l}$ are
independent Gaussian matrices, defined by $X_{l}=G_{l}\Sigma_{l}^{1/2}$, where
$G_{l}\in\mathbb{R}^{n\times d}$ have i.i.d standard Gaussian elements, and
$\Sigma_{l}\in\mathbb{R}^{d\times d}$ are covariance matrices. Finally, we
will assume the following model, which relates the labels to the datapoints:

$y_{l}=\frac{1}{\sqrt{d}}X_{l}\theta^{*}+\nu_{l},$

where $\theta^{*}\in\mathbb{R}^{d}$ denotes the "true" relationship, and
$\nu_{l}\in\mathbb{R}^{n}$ is i.i.d zero mean noise, with variance
$\sigma_{\nu,l}^{2}$ independent of $X_{l}$. In other words, we assume some
true linear relationship, between data and labels subject to corruption due to
noise. We allow for different noise power for each channel. We will
specifically concentrate on the generalization error of this regression
problem, which we will define by:

$\mathcal{E}_{gen}=\frac{1}{2k}\mathbb{E}\sum_{l=1}^{k}\left\|y_{l,new}-\frac{1}{\sqrt{d}}x_{l,new}^{T}\hat{\theta}\right\|^{2}$
(3)

where $x_{l,new}$ are drawn from the same distribution as $X_{l}$ and
$y_{l,new}=\frac{1}{\sqrt{d}}x_{l,new}^{T}\theta^{*}+\nu_{l,new}$, where
$\nu_{l,new}$ is new noise drawn from the same noise distribution. We discuss
and analyze this multi-source regression problem in section 4.1.

One cannot leverage the usual CGMT to tackle the problem in (2) which will be
made explicit in the following. By setting
$z_{l}:=y_{l}-\frac{1}{\sqrt{d}}X_{l}\theta$ and introducing Lagrange
multipliers:

$\displaystyle\min_{\theta,z_{l}\in\mathbb{R}^{d}}\max_{v_{l}}R(\bm{\theta})+\frac{1}{nk}\sum_{l=1}^{k}\left[\frac{1}{\sqrt{d}}v_{l}^{T}X_{l}\theta-
v_{l}^{T}y_{l}+v_{l}^{T}z_{l}+\ell_{l}(z_{l})\right].$ (4)

Defining
$X^{T}=\begin{pmatrix}X_{1}^{T}|X_{2}^{T}|\ldots|X_{k}^{T}\end{pmatrix}$ and
$v^{T}=\begin{pmatrix}v_{1}^{T}&v_{2}^{T}&\ldots v_{k}^{T}\end{pmatrix}$
allows us to rewrite (4) as

$\displaystyle\min_{\theta,z_{l}\in\mathbb{R}^{d}}\max_{v}R(\theta)+\frac{1}{nk\sqrt{d}}v^{T}X\theta+\frac{1}{nk}v^{T}z-\frac{1}{nk}v^{T}y+\frac{1}{nk}\ell(z),$
(5)

where $z^{T}=\begin{pmatrix}z_{1}^{T}\ldots z_{k}^{T}\end{pmatrix}$,
$y^{T}=\begin{pmatrix}y_{1}^{T}\ldots y_{k}^{T}\end{pmatrix}$, and
$\ell(z)=\sum_{l=1}^{k}\ell_{l}(z_{l})$. Now note that we cannot apply the
standard CGMT to either of (4) and (5) since in (4) the vector $\theta$
couples the optimizations over $v_{l},z_{l}$, and in (5), as discussed, the
rows of the Gaussian matrix $X$ are not identically distributed. We therefore
need a new CGMT that can apply to the Gaussian process,
$v^{T}X\theta=\sum_{l=1}^{k}v_{l}G_{l}\Sigma_{l}^{1/2}\theta$, which is the
main contribution of the current paper.

###  2.4 Binary classification for Gaussian Mixture Models

We next consider the binary linear classification problem on data generated
from a Gaussian Mixture Model (GMM) with arbitrary covariance. To be precise,
the data $\mathbf{x}_{i}\in\mathbb{R}^{d}$ is generated as:

$\mathbf{x}_{i}\sim\mathcal{N}(\mu_{k},\Sigma_{k})\quad\text{where}\quad
k\sim\textit{Unif}\\{1,2\\},$

$\mu_{k}\in\mathbb{R}^{d}$ are the mean vectors and
$\Sigma_{k}\in\mathbb{R}^{d\times d}$ are the corresponding covariance
matrices. For simplicity, we assume that we uniformly sample from both the
mixtures but the analysis can be extended to arbitrary sampling priors. We set
the labels $y_{i}=1$ if data is generated from the cluster with mean $\mu_{1}$
and $y_{i}=-1$ if data is generated from the cluster with mean $\mu_{2}$. We
then formulate the learning objective in terms of the following regression
problem.

$\min_{w}\mathcal{L}((A+M)w-z)+\lambda f(w)$ (6)

where $\lambda\in\mathbb{R}_{+}$ controls the degree of regularization,
$M^{T}=(\underbrace{\begin{matrix}\mu_{1}&...&\mu_{1}\end{matrix}}_{\frac{n}{2}}\underbrace{\begin{matrix}\mu_{2}&...&\mu_{2}\end{matrix}}_{\frac{n}{2}})$
encodes the means corresponding to each class,
$z^{T}=(\underbrace{\begin{matrix}1&...&1\end{matrix}}_{\frac{n}{2}}\underbrace{\begin{matrix}-1&...&-1\end{matrix}}_{\frac{n}{2}})$
corresponds to the labels and

$A=\begin{pmatrix}G_{1}&0\\\
0&G_{2}\end{pmatrix}\begin{pmatrix}\Sigma_{1}^{\frac{1}{2}}\\\
\Sigma_{2}^{\frac{1}{2}}\\\ \end{pmatrix}$

where $G_{1},G_{2}\in\mathbb{R}^{\frac{n}{2}\times d}$ are Gaussian matrices
with iid $\mathcal{N}(0,1)$ entries. Therefore, the rows of $A+M$ denote the
data generated by the GMM and without loss of generality we assume that the
data is ordered and split into two equal halves from the two mixtures.
Additionally, we assume both loss function $\mathcal{L}(\cdot)$ and
regularization function $f(\cdot)$ to be separable convex functions. Given a
linear $\hat{w}$, the classification rule at inference is
$\hat{y}(x)=\text{sign}(\hat{w}^{T}x)$. The classification error, or the error
on unseen data, generated for the above GMM is given as:

$E(\hat{w})=\frac{1}{2}Q\left(\frac{\mu_{1}^{T}\hat{w}}{\sqrt{\hat{w}^{T}\Sigma_{1}\hat{w}}}\right)+\frac{1}{2}Q\left(-\frac{\mu_{2}^{T}\hat{w}}{\sqrt{\hat{w}^{T}\Sigma_{2}\hat{w}}}\right)$
(7)

where $Q(\cdot)$ is the standard Gaussian CCDF.

Finally, to make the results as explicit as possible we assume that $\mu_{1}$
and $\mu_{2}$ are i.i.d. $\mathcal{N}(0,1)$ and their matching entries are
correlated according to $\mathbb{E}\mu_{1i}\mu_{2i}=r$ for some $-1\leq r\leq
1$. Under this assumption we have
$\|\mu_{1}\|\approx\|\mu_{2}\|\approx\sqrt{d}$ and $\mu_{1}^{T}\mu_{2}\approx
rd$.***Theorem 6 further below is true for arbitrary $\mu_{1}$ and $\mu_{2}$
and one can still use it to derive versions of Theorem 7 and Corollary 2 for
any other given model for $\mu_{1}$ and $\mu_{2}$ but we prefer to follow with
this specific assumption because it is meant to capture the simplest case of
two ”typical” $d$-dimensional vectors that are not necessarily orthogonal.

To illustrate why one cannot just readily apply the standard CGMT in this
setting, we have to spell out (6) further. The standard way of dealing with
(6) is introducing $u:=(A+M)w-z$ and inserting a Lagrange multiplier, after
which we would have:

$\min_{w,u}\max_{v}v^{T}Aw+v^{T}Mw-v^{T}z-v^{T}u+\mathcal{L}(u)+\lambda f(w)$

The standard CGMT cannot be applied here because $A$ is not i.i.d. To try
resolving it, one can denote $v^{T}=(v_{1}^{T},v_{2}^{T})$ for
$v_{1},v_{2}\in\mathbb{R}^{\frac{n}{2}}$ and obtain

$\min_{w,u}\max_{v_{1},v_{2}}v_{1}^{T}G_{1}\Sigma_{1}^{\frac{1}{2}}w+v_{2}^{T}G_{2}\Sigma_{2}^{\frac{1}{2}}w+v^{T}Mw-v^{T}z-v^{T}u+\mathcal{L}(u)+\lambda
f(w)$ (8)

Note first of all that the objective above does not separate into a CGMT
instance with $G_{1}$ and a CGMT instance with $G_{2}$ because $w$ "sees" both
of these matrices. If $\Sigma_{1}=\Sigma_{2}$, we can define
$\tilde{w}=\Sigma_{2}^{\frac{1}{2}}w$,
$(M\Sigma_{2}^{-\frac{1}{2}})^{T}=\left(\tilde{M}_{1}|\tilde{M}_{2}\right)^{T},\tilde{M}_{1},\tilde{M}_{2}\in\mathbb{R}^{d\times\frac{n}{2}}$,
$\tilde{f}(x)=f(\Sigma_{2}^{-\frac{1}{2}}x)$ and arrive at:

$\min_{\tilde{w},u}\max_{v}v^{T}(G_{1}^{T}|G_{2}^{T})^{T}\tilde{w}+v^{T}\tilde{M}^{T}\tilde{w}-v^{T}z-v^{T}u+\mathcal{L}(u)+\lambda\tilde{f}(\tilde{w})$

Hence, when $\Sigma_{1}=\Sigma_{2}$, since $(G_{1}^{T}|G_{2}^{T})$ is i.i.d.
Gaussian we can analyze (8) using the standard CGMT. However, for the case of
general $\Sigma_{1}$ and $\Sigma_{2}$ the same argument does not apply and it
appears that one just has to develop a framework allowing for terms of the
form
$v_{1}^{T}G_{1}\Sigma_{1}^{\frac{1}{2}}w+v_{2}^{T}G_{2}\Sigma_{2}^{\frac{1}{2}}w$
to be present in the objective. This is essentially what Theorem 4 addresses.

##  3 Main results

We will occasionally shorten $\|\cdot\|_{2}$ to $\|\cdot\|$ for brevity in the
expressions below.

######  Lemma 1.

Let $G_{1}\in\mathbb{R}^{n_{1}\times d},\dots,G_{k}\in\mathbb{R}^{n_{k}\times
d}$, $\gamma_{1},\dots,\gamma_{k}\in\mathbb{R}$,
$g_{1},\dots,g_{k}\in\mathbb{R}^{d}$,
$h_{1}\in\mathbb{R}^{n_{1}},\dots,h_{k}\in\mathbb{R}^{n_{k}}$ all have i.i.d
$\mathcal{N}(0,1)$ components,
$\Sigma_{1},\dots,\Sigma_{k}\in\mathbb{R}^{d\times d}$ be arbitrary PSD
matrices, $I,J_{1},\dots,J_{k}$ be finite sets and $\\{w_{i}\\}_{i\in
I}\subset\mathbb{R}^{d}$, $\\{u_{j_{1}}\\}_{j_{1}\in
J_{1}}\subset\mathbb{R}^{n_{1}},\dots,\\{u_{j_{k}}\\}_{j_{k}\in
J_{k}}\subset\mathbb{R}^{n_{k}}$ be arbitrary discrete subsets. Then the
following two Gaussian Processes defined on $I\times J$, where
$J=J_{1}\times\dots\times J_{k}$ and $j\in J$ denotes $(j_{1},\dots,j_{k})\in
J_{1}\times\dots\times J_{k}$, satisfy the assumptions of Theorem 1:

$\displaystyle
Y_{ij}=\sum_{\ell=1}^{k}\left[v_{j_{\ell}}^{T}G_{\ell}\Sigma_{\ell}^{\frac{1}{2}}w_{i}+\gamma_{\ell}\|\Sigma_{\ell}^{\frac{1}{2}}w_{i}\|\|v_{j_{\ell}}\|\right]$
$\displaystyle
X_{ij}=\sum_{\ell=1}^{k}\left[\|v_{j_{\ell}}\|w_{i}^{T}\Sigma_{\ell}^{\frac{1}{2}}g_{\ell}+\|\Sigma_{\ell}^{\frac{1}{2}}w_{i}\|h_{\ell}^{T}v_{j_{\ell}}\right]$

Moreover, the processes defined by $\tilde{X}_{ji}=X_{ij}$ and
$\tilde{Y}_{ji}=Y_{ij}$ on $J\times I$ satisfy these assumptions as well.

After making several additional technical steps, the result above combined
with Theorem 1 can be used to deduce the following generalization of Theorem
3:

######  Theorem 4 (Generalized CGMT).

Let
$\mathcal{S}_{w}\subset\mathbb{R}^{d},\mathcal{S}_{v_{1}}\subset\mathbb{R}^{n_{1}},\dots,\mathcal{S}_{v_{k}}\subset\mathbb{R}^{n_{k}}$
be compact convex sets. Denote
$\mathcal{S}_{v}:=\mathcal{S}_{v_{1}}\times\dots\times\mathcal{S}_{v_{k}}$,
let $v\in\mathcal{S}_{v}$ stand for
$(v_{1},\dots,v_{k})\in\mathcal{S}_{v_{1}}\times\dots\times\mathcal{S}_{v_{k}}$
and $\psi(w,v):\mathcal{S}_{w}\times\mathcal{S}_{v}\to\mathbb{R}$ be convex on
$\mathcal{S}_{w}$ and concave on $\mathcal{S}_{v}$. Also let
$\Sigma_{1},\dots,\Sigma_{k}\in\mathbb{R}^{d\times d}$ be arbitrary PSD
matrices. Furthermore, let $G_{1}\in\mathbb{R}^{n_{1}\times
d},\dots,G_{k}\in\mathbb{R}^{n_{k}\times d}$,
$g_{1},\dots,g_{k}\in\mathbb{R}^{d}$,
$h_{1}\in\mathbb{R}^{n_{1}},\dots,h_{k}\in\mathbb{R}^{n_{k}}$ all have i.i.d
$\mathcal{N}(0,1)$ components and $G=(G_{1},\dots,G_{k})$,
$g=\left(g_{1},\dots,g_{k}\right)$, $h=\left(h_{1},\dots,h_{k}\right)$ be the
corresponding $k$-tuples. Define

$\displaystyle\Phi(G):=\min_{w\in\mathcal{S}_{w}}\max_{v\in\mathcal{S}_{v}}\sum_{\ell=1}^{k}v_{\ell}^{T}G_{\ell}\Sigma_{\ell}^{\frac{1}{2}}w+\psi(w,v)$
$\displaystyle\phi(g,h):=\min_{w\in\mathcal{S}_{w}}\max_{v\in\mathcal{S}_{v}}\sum_{\ell=1}^{k}\left[\|v_{\ell}\|_{2}g_{\ell}^{T}\Sigma_{\ell}^{\frac{1}{2}}w+\|\Sigma_{\ell}^{\frac{1}{2}}w\|_{2}h_{\ell}^{T}v_{\ell}\right]+\psi(w,v)$

The following statements hold:

  1. 1.

For all $\eta,c\in\mathbb{R}$ such that $\eta>0$, then
$\mathbb{P}(|\Phi(G)-c|>\eta)\leq 2^{k}\mathbb{P}(|\phi(g,h)-c|>\eta)$

  2. 2.

Let $\mathcal{S}$ be an arbitrary open subset of $\mathcal{S}_{w}$ and
$\mathcal{S}^{c}=\mathcal{S}_{w}\setminus\mathcal{S}$. Define:

$\displaystyle\Phi_{\mathcal{S}^{c}}(G):=\min_{w\in\mathcal{S}^{c}}\max_{v\in\mathcal{S}_{v}}\sum_{\ell=1}^{k}v_{\ell}^{T}G_{\ell}\Sigma_{\ell}^{\frac{1}{2}}w+\psi(w,v)$
$\displaystyle\phi_{\mathcal{S}^{c}}(g,h):=\min_{w\in\mathcal{S}^{c}}\max_{v\in\mathcal{S}_{v}}\sum_{\ell=1}^{k}\left[\|v_{\ell}\|_{2}g_{\ell}^{T}\Sigma_{\ell}^{\frac{1}{2}}w+\|\Sigma_{\ell}^{\frac{1}{2}}w\|_{2}h_{\ell}^{T}v_{\ell}\right]+\psi(w,v)$
$\displaystyle
w_{\Phi}(G)=\operatorname*{arg\,min}_{w\in\mathcal{S}_{w}}\max_{v\in\mathcal{S}_{v}}\sum_{\ell=1}^{k}v_{\ell}^{T}G_{\ell}\Sigma_{\ell}^{\frac{1}{2}}+\psi(w,v)$

Assume also that there exist $\epsilon,\delta>0$,
$\bar{\phi},\bar{\phi}_{\mathcal{S}^{c}}$ such that

     * •

$\bar{\phi}_{\mathcal{S}^{c}}\geq\bar{\phi}+3\delta$

     * •

$\phi(g,h)<\bar{\phi}+\delta$ with probability at least $1-\epsilon$

     * •

$\phi_{\mathcal{S}^{c}}>\bar{\phi}_{\mathcal{S}^{c}}-\delta$ with probability
at least $1-\epsilon$

Then $\mathbb{P}(w_{\Phi}(G)\in\mathcal{S})\geq 1-2^{k+1}\epsilon$

Part 1 of Theorem 4 says that if $\phi(g,h)$ concentrates to a value $c$, then
so does $\Phi(G)$, albeit with a possibly slightly worse tail bound. Moreover,
it turns out that $\phi(g,h)$ concentrates to $\mathbb{E}\phi(g,h)$
exponentially fast, which we prove in Appendix B. As such, Theorem 4 implies
that $\Phi(G)$ concentrates exponentially fast to the same value. Part $2$ of
the theorem says that if the solution of $\phi(g,h)$ satisfies a certain
property with probability very close to $1$, such as for example belonging to
a ball of a fixed radius, then the same is true for the solution of $\Phi(G)$.

##  4 Applications

###  4.1 Multi-source regression

We recall the problem is given in equation (2). Also recall the definition of
the Moreau envelope, for a function $f$ and matrix $T$:

$\mathcal{M}_{T\ f(\cdot)}(x)=\min_{z}f(z)+\frac{1}{2}(x-z)^{T}T^{-1}(x-z),$
(9)

where $T^{-1}$ is a positive definite matrix. We also note that the optimal
point of the optimization in (9) is the proximal operator, denoted
$\mathrm{prox}_{T\ f(\cdot)}(x)$. The application of the generalized CGMT to
the multi-source regression problem gives us the following theorem:

######  Theorem 5 (Multi-source Generalization Error).

Consider the following scalarized optimization problem:

$\displaystyle\min_{\xi,q\succeq 0}\max_{\beta,r\succeq
0}\sum_{l=1}^{k}\frac{\beta_{l}q_{l}}{2k}-\frac{\xi_{l}r_{l}}{2k}+\frac{1}{nk}\mathcal{M}_{\frac{q_{l}}{\beta_{l}}I\
\ell_{l}}\left(\nu_{l}-\xi_{l}h_{l}\right)$
$\displaystyle-\frac{1}{k^{2}}\frac{\beta_{l}^{2}}{n}\text{Tr}\Sigma_{l}\left(\frac{1}{k}\sum_{l^{\prime}=1}^{k}\frac{r_{l^{\prime}}}{\xi_{l^{\prime}}}\Sigma_{l^{\prime}}\right)^{-1}+\frac{1}{d}\mathcal{M}_{A^{-1}\
R}\left(\theta^{*}-A^{-1}b\right)$ (10)

Here $\xi,q,\beta,r\in\mathbb{R}^{k}$, and element-wise non-negative, and
$h_{l}\in\mathbb{R}^{n}$ for $l=1,\ldots,k$ are i.i.d standard Gaussian
vectors independent of each other. Furthermore, $A$ and $b$ are defined as
follows:

$\displaystyle A(r,\xi)\in\mathbb{R}^{d\times
d}=\left(\frac{1}{k}\sum_{l=1}^{k}\frac{r_{l}}{\xi_{k}}\Sigma_{l}\right)\qquad
b(\beta)\in\mathbb{R}^{d}=\left(\frac{1}{k}\sqrt{\frac{d}{n}}\sum_{l=1}^{k}\beta_{l}\Sigma_{l}^{1/2}g_{l}\right).$

We denote by $\hat{r}_{i},\hat{\xi}_{i},\hat{\beta}_{i},\hat{q}_{i}$ the
optimal values of the scalarized optimization problem, and define
$\hat{A}=A(\hat{r},\hat{\xi})$ and $\hat{b}=b(\hat{\beta})$. Then the
generalization error (as defined in equation 3) for the multi-source Gaussian
Regression problem is given by:

$\mathcal{E}_{gen}=\frac{1}{2k}\mathbb{E}\sum_{l=1}^{k}\left\|y_{l,new}-\frac{1}{\sqrt{d}}x_{l,new}^{T}\mathrm{prox}_{\hat{A}^{-1}\
R}(\theta^{*}-\hat{A}^{-1}\hat{b})\right\|$

###  4.2 Binary classification for general GMMs

In this section, we provide the precise asymptotic analysis of binary linear
classification for data generated from a GMM with arbitrary covariances.

######  Theorem 6 (Binary Classification Error).

The classification error obtained from the solution of (6) is given as

$\frac{1}{2}Q\left(\frac{\gamma_{1}}{\theta_{1}}\right)+\frac{1}{2}Q\left(-\frac{\gamma_{2}}{\theta_{2}}\right)$

where $\gamma_{i}$ and $\theta_{i}$ are solutions of the following scalar
optimization problem:

$\displaystyle\min_{\tau_{i},\theta_{i},\zeta_{i}\geq
0,\gamma_{i}}\max_{\beta_{i}\geq 0,\eta_{i}}\lambda\mathcal{M}_{\lambda\
f(\Sigma^{-\frac{1}{2}})}\left(\Sigma^{-\frac{1}{2}}x\right)-\frac{x^{T}\Sigma^{-1}x}{2}+\sum^{2}_{i=1}\left[\beta_{i}\frac{\tau_{i}}{2}+\mathcal{M}_{\frac{\tau_{i}}{\beta_{i}}\
\mathcal{L}}\left(\gamma_{i}\mathds{1}-\theta_{i}h_{i}-z_{i}\right)-\frac{\theta_{i}\zeta_{i}}{2}-\eta_{i}\gamma_{i}\right]$

where $\Sigma=\sum_{i=1}^{2}\frac{\zeta_{i}}{\theta_{i}}\Sigma_{i}$ and
$x=\sum_{i=1}^{2}\beta_{i}\Sigma_{i}^{\frac{1}{2}}g_{i}-\eta_{i}\mu_{i}$

In the special case of the $\ell_{2}$-norm square loss and regularization, we
have the following simplified result:

######  Theorem 7.

The classification error obtained from the solution of (6) when
$\mathcal{L}(\cdot)=\|\cdot\|^{2}$ and $f(\cdot)=\|\cdot\|^{2}$ is given as

$\displaystyle\frac{1}{2}Q\left(\frac{\gamma_{1}+2}{\sqrt{\frac{8}{n}\tau_{1}^{2}-\gamma_{1}^{2}}}\right)+\frac{1}{2}Q\left(\frac{-\gamma_{2}+2}{\sqrt{\frac{8}{n}\tau_{2}^{2}-\gamma_{2}^{2}}}\right)$

where $\beta_{i},\gamma_{i}$ and $\tau_{i}$ are solutions of the following
scalar optimization problem:

$\displaystyle\min_{\tau_{i}\geq 0}\max_{\beta_{i}\geq 0,\gamma_{i}}$
$\displaystyle-\frac{1}{4}\text{Tr}\left[(\lambda
I+\frac{n\beta_{1}}{4\tau_{1}}\Sigma_{1}+\frac{n\beta_{2}}{4\tau_{2}}\Sigma_{2})^{-1}(\frac{n^{2}\beta_{1}\beta_{2}\gamma_{1}\gamma_{2}}{8\tau_{1}\tau_{2}}rI+\sum_{i=1}^{2}\beta_{i}^{2}\Sigma_{i}+\frac{n^{2}\beta_{i}^{2}\gamma_{i}^{2}}{16\tau_{i}^{2}}I)\right]+$
$\displaystyle+\sum_{i=1}^{2}\left[\frac{\beta_{i}\tau_{i}}{2}-\frac{n\beta_{i}\gamma_{i}^{2}}{16\tau_{i}}-\frac{n\beta_{i}\gamma_{i}(-1)^{i+1}}{4\tau_{i}}-\frac{\beta_{i}^{2}}{4}\right]$

The performances of various classification algorithms have been analyzed in
depth using the standard CGMT for the case of scalar $\Sigma_{1}$ and
$\Sigma_{2}$ (see, for example, (Mignacco et al.,, 2020; Thrampoulidis et
al.,, 2020; Akhtiamov et al.,, 2023)). As a baby step towards developing a
better understanding of the effects of the structure of $\Sigma_{1}$ and
$\Sigma_{2}$ on the classification error, we apply Theorem 7 to the following
explicitly defined model:

$\displaystyle\Sigma_{1}=\sigma_{1}^{2}I+\nu_{1}\nu_{1}^{T}~{}~{}~{}\mbox{and}~{}~{}~{}\Sigma_{2}=\sigma_{2}^{2}I+\nu_{2}\nu_{2}^{T}$
(11) $\displaystyle\text{ where
}\sigma_{1},\sigma_{2},\sigma\in\mathbb{R}~{}~{}~{}\mbox{and}~{}~{}~{}\nu_{1},\nu_{2}\text{
are i.i.d. }\mathcal{N}(0,\sigma^{2})$

######  Corollary 2.

The classification error obtained from the solution of (6) when
$\mathcal{L}(\cdot)=\|\cdot\|^{2},f(\cdot)=\|\cdot\|^{2}$ for $\Sigma_{1}$ and
$\Sigma_{2}$ defined as above is given as:

$\displaystyle\frac{1}{2}Q\left(\frac{\gamma_{1}+2}{\sqrt{\frac{8}{n}\tau_{1}^{2}-\gamma_{1}^{2}}}\right)+\frac{1}{2}Q\left(\frac{-\gamma_{2}+2}{\sqrt{\frac{8}{n}\tau_{2}^{2}-\gamma_{2}^{2}}}\right)$

where $\beta_{i},\gamma_{i}$ and $\tau_{i}$ are solutions of the following
scalar optimization problem:

$\displaystyle\min_{\tau_{i}\geq 0}\max_{\beta_{i}\geq
0,\gamma_{i}}(d-2)(\lambda+\frac{n\beta_{1}}{4\tau_{1}}\sigma^{2}_{1}+\frac{n\beta_{2}}{4\tau_{2}}\sigma^{2}_{2})^{-1}\left(\frac{n^{2}\beta_{1}\beta_{2}\gamma_{1}\gamma_{2}}{8\tau_{1}\tau_{2}}r+\sum_{i=1}^{2}\left[\beta_{i}^{2}\sigma^{2}_{i}+\frac{n^{2}\beta_{i}^{2}\gamma_{i}^{2}}{16\tau_{i}^{2}}\right]\right)+$
$\displaystyle+(\lambda+\frac{n\beta_{1}}{4\tau_{1}}(\sigma^{2}_{1}+\sigma^{2}d)+\frac{n\beta_{2}}{4\tau_{2}}\sigma^{2}_{2})^{-1}\left(\frac{n^{2}\beta_{1}\beta_{2}\gamma_{1}\gamma_{2}}{8\tau_{1}\tau_{2}}r+\beta_{1}^{2}\sigma^{2}d+\sum_{i=1}^{2}\left[\beta_{i}^{2}\sigma^{2}_{i}+\frac{n^{2}\beta_{i}^{2}\gamma_{i}^{2}}{16\tau_{i}^{2}}\right]\right)+$
$\displaystyle+(\lambda+\frac{n\beta_{1}}{4\tau_{1}}\sigma^{2}_{1}+\frac{n\beta_{2}}{4\tau_{2}}(\sigma^{2}_{2}+\sigma^{2}d))^{-1}\left(\frac{n^{2}\beta_{1}\beta_{2}\gamma_{1}\gamma_{2}}{8\tau_{1}\tau_{2}}r+\beta_{2}^{2}\sigma^{2}d+\sum_{i=1}^{2}\left[\beta_{i}^{2}\sigma^{2}_{i}+\frac{n^{2}\beta_{i}^{2}\gamma_{i}^{2}}{16\tau_{i}^{2}}\right]\right)+$
$\displaystyle+\sum_{i=1}^{2}\left[\frac{\beta_{i}\tau_{i}}{2}-\frac{n\beta_{i}\gamma_{i}^{2}}{16\tau_{i}}-\frac{n\beta_{i}\gamma_{i}(-1)^{i+1}}{4\tau_{i}}-\frac{\beta_{i}^{2}}{4}\right]$

######  Remark 1.

Since the first term in the objective above has $(d-2)$ in front of it, and
the other two do not, one might approximate the objective by only the first
term for large enough $d$. Indeed, even though the second and the third terms
have some occurrences of $d$ as well, in both cases this quantity is present
both in the numerator and the denominator of a certain fraction. This tells us
that as $d$ grows large, we should not expect the performance to be very
different from the case
$\tilde{\Sigma}_{1}=\sigma_{1}^{2}I,\tilde{\Sigma}_{2}=\sigma_{2}^{2}I$, as
this is what the first term corresponds to if we replace $(d-2)$ by $d$, again
by the virtue of the fact that $d$ is large. Since this observation is not
rigorous, we check it numerically in the next section.

To conclude, note that it is also feasible to study linear classification for
GMMs via approaches based on AMP (see (Loureiro et al.,, 2021)). Since the
present paper is devoted to studying approaches based on Gaussian comparison
inequalities, covering other methods goes beyond its scope. But in any case,
the authors believe that developing new tools for tackling a problem is always
of value, as it usually leads to new insights, such as Remark 1, which has not
been observed before in the literature to the best of the authors’ knowledge.

##  5 Numerical experiments

###  5.1 Multi-source regression plots

To validate Theorem 5 numerically we consider the specific case of all
$\ell_{l}$ being the square loss and $R$ being square regularization
parameterized by regularization strength $\lambda$, ie
$R=\lambda\left\|\cdot\right\|_{2}^{2}$. For this particular choice of loss
and regularizer, the expressions are given in the supplement section C.1.2.
The results for a variety of values of the regularization strengths $\lambda$
can be seen in Fig. 1, for several choices for the ratio $\frac{d}{n}$. The
figure on the left shows the training error and the right shows the
generalization error with respect to new data. The data has $k=3$ channels,
and $n=100$, and $d=50,100,150$ for each of the three curves. For $\Sigma_{l}$
we use the model described in equation (11), with
$\sigma_{1}=0.5,\sigma_{2}=0.7,\sigma_{3}=0.3$ respectively and $\nu_{i}$
drawn from i.i.d standard Gaussian. For the choice of $\theta^{*}$ we choose a
vector of all $1$s. Finally, the noise strength for each of the channels was
chosen to be
$\sigma_{\bm{\nu},1}=0.1,\sigma_{\bm{\nu},2}=0.2,\sigma_{\bm{\nu},3}=0.3$. In
Fig. 1, the solid line denotes the values predicted by our alternative
optimization, given in (5) solved numerically using zeroth order gradient
ascent/descent. The marks are given by a numerical simulation of the problem
(2) with the same parameters. As can be observed the predicted values match
with a high degree of accuracy to their numerical equivalents, even while
being in the finite regime.

$10^{0}$$10^{1}$$10^{2}$$0.2$$0.4$$0.6$$0.8$$1$$1.2$$1.4$$\lambda$Training
Error$\frac{d}{n}=\frac{1}{2}$$\frac{d}{n}=1$$\frac{d}{n}=\frac{3}{2}$

(a) Training Error

$10^{0}$$10^{1}$$10^{2}$$0.2$$0.4$$0.6$$0.8$$1$$1.2$$\lambda$Generalization
Error$\frac{d}{n}=\frac{1}{2}$$\frac{d}{n}=1$$\frac{d}{n}=\frac{3}{2}$

(b) Generalization Error

Figure 1: Training and Generalization Error for the Multi-source Gaussian
Regression

###  5.2 Binary classification for general GMMs

We conducted experiments to validate the results of Section 4.2 numerically as
presented in Fig. 2. To do so, we fixed
$\mathcal{L}(\cdot)=f(\cdot)=\|\cdot\|_{2}^{2}$ and defined
$\Sigma_{1},\Sigma_{2}$ following the notation from (11). We took
$\sigma_{1}=\sigma_{2}=3,\sigma=10,d=700,n=300,r=0.9$ for the plot on the LHS
and $\sigma_{1}=\sigma_{2}=5,\sigma=15,d=500,n=400,r=0.8$ for the plot on the
RHS, solved (6) directly for
$\lambda\in\\{1,10,50,100,250,500,1000,2000,5000\\}$ using CVXPY (Diamond and
Boyd,, 2016; Agrawal et al.,, 2018), evaluated the corresponding
classification errors via (7) and plotted them in red with legends
"$\sigma=10$" and "$\sigma=15$" respectively. After that, we solved the
scalarized objective from Corollary 2 by noticing that $\beta_{1}=\beta_{2}$,
$\tau_{1}=\tau_{2}$ and $\gamma_{1}=-\gamma_{2}$ due to the distribution of
$(\Sigma_{1},\Sigma_{2})$ being exchangeable, running a grid search over
$\tau:=\tau_{1}=\tau_{2}$ and using scipy.optimize.minimize to perform
optimization over the remaining parameters, which we then used to evaluate the
corresponding classification error predicted by Corollary 2 for each $\lambda$
and plotted it in blue with a legend "AO". Finally, as an additional sanity
check, we decided to plot the classification error corresponding to
$\tilde{\Sigma}_{1}=\sigma_{1}^{2}I$ and $\tilde{\Sigma}_{2}=\sigma_{2}^{2}I$
because according to Remark 1 we expect it to not deviate too much from the
classification error for the GMM with the corresponding
$\Sigma_{1},\Sigma_{2}$. The results of the latter procedure are depicted in
black with a legend "$\sigma=0$". All three described lines match very closely
in both settings as expected.

$10^{0}$$10^{1}$$10^{2}$$10^{3}$$10^{4}$$8$$10$$12$$\lambda$Classification
Error$\text{, }\%$$\sigma=10$$\sigma=0$AO

(a) $d=700,n=300$

$10^{0}$$10^{1}$$10^{2}$$10^{3}$$10^{4}$$20$$25$$30$$\lambda$Classification
Error$\text{, }\%$$\sigma=15$$\sigma=0$AO

(b) $d=500,n=400$

Figure 2: The error for binary classification for GMMs

##  6 Conclusion and future work

We presented a new pair of Gaussian processes that satisfy Gordon’s comparison
conditions and thereby developed a generalization of the Convex Gaussian Min-
Max Theorem. We further demonstrated its use in two examples, namely multi-
source regression and binary classification for Gaussian data with arbitrary
covariance matrices. Future work would be to see if further pairs of
comparable processes can be found. Of particular interest are those where
$G_{\ell}$ and $G_{\ell^{\prime}}$ do not have to be independent for
$\ell\neq\ell^{\prime}$.

##  Appendix A Proof of Theorem 4

We will need the following technical lemma:

######  Lemma 2.

Under the notation from Theorem 4, let $\delta>0$ and
$\mathcal{S}^{\delta}_{w},\mathcal{S}^{\delta}_{v}$ be arbitrary finite
$\delta$ \- nets for $\mathcal{S}_{w}$ and $\mathcal{S}_{v}$ respectively and
define

$\displaystyle\tilde{\Phi}(G)=\min_{v\in\mathcal{S}_{v}}\max_{w\in\mathcal{S}_{w}}\sum_{\ell=1}^{k}v_{\ell}^{T}G_{\ell}\Sigma_{\ell}^{\frac{1}{2}}w-\psi(w,v)$
$\displaystyle\tilde{\Phi}^{\delta}(G)=\min_{v\in\mathcal{S}^{\delta}_{v}}\max_{w\in\mathcal{S}^{\delta}_{w}}\sum_{\ell=1}^{k}v_{\ell}^{T}G_{\ell}\Sigma_{\ell}^{\frac{1}{2}}w-\psi(w,v)$
$\displaystyle\tilde{\phi}(g,h)=\min_{v\in\mathcal{S}_{v}}\max_{w\in\mathcal{S}_{w}}\sum_{\ell=1}^{k}\|v_{\ell}\|_{2}g_{\ell}^{T}\Sigma_{\ell}^{\frac{1}{2}}w+\|\Sigma_{\ell}^{\frac{1}{2}}w\|_{2}h_{\ell}^{T}v_{\ell}-\psi(w,v)$
$\displaystyle\tilde{\phi}^{\delta}(g,h)=\min_{v\in\mathcal{S}^{\delta}_{v}}\max_{w\in\mathcal{S}^{\delta}_{w}}\sum_{\ell=1}^{k}\|v_{\ell}\|_{2}g_{\ell}^{T}\Sigma_{\ell}^{\frac{1}{2}}w+\|\Sigma_{\ell}^{\frac{1}{2}}w\|_{2}h_{\ell}^{T}v_{\ell}-\psi(w,v)$
$\displaystyle\Phi^{\delta}(G)=\min_{w\in\mathcal{S}^{\delta}_{w}}\max_{v\in\mathcal{S}^{\delta}_{v}}\sum_{\ell=1}^{k}v_{\ell}^{T}G_{\ell}\Sigma_{\ell}^{\frac{1}{2}}w+\psi(w,v)$
$\displaystyle\phi^{\delta}(g,h)=\min_{w\in\mathcal{S}^{\delta}_{w}}\max_{v\in\mathcal{S}^{\delta}_{v}}\sum_{\ell=1}^{k}\|v_{\ell}\|_{2}g_{\ell}^{T}\Sigma_{\ell}^{\frac{1}{2}}w+\|\Sigma_{\ell}^{\frac{1}{2}}w\|_{2}h_{\ell}^{T}v_{\ell}+\psi(w,v)$

Then the following holds:

$\displaystyle\lim_{\delta\to 0}\mathbb{P}(\chi^{\delta}<\chi)=1\text{ if
}\chi\in\\{\Phi(G),\tilde{\Phi}(G)\\}~{}~{}~{}\mbox{and}~{}~{}~{}\lim_{\delta\to
0}\mathbb{P}(\chi<\chi^{\delta})=1\text{ if
}\chi\in\\{\phi(g,h),\tilde{\phi}(g,h)\\}$

###### Proof.

Define

$\displaystyle
D=\max_{w\in\mathcal{S}_{w},v\in\mathcal{S}_{v}}\\{\|w\|,\|v\|\\}$
$\displaystyle
L=\max_{(w,v)\neq(w^{\prime},v^{\prime})}\frac{|\psi(w,v)-\psi(w^{\prime},v^{\prime})|}{\|w-w^{\prime}\|+\|v-v^{\prime}\|}$

We then have:

$\displaystyle\Phi^{\delta}(G)-\Phi(G)=\min_{w\in\mathcal{S}^{\delta}_{w}}\max_{v\in\mathcal{S}^{\delta}_{v}}\sum_{\ell=1}^{k}v_{\ell}^{T}G_{\ell}\Sigma_{\ell}^{\frac{1}{2}}w+\psi(w,v)-\min_{w\in\mathcal{S}_{w}}\max_{v\in\mathcal{S}_{v}}\sum_{\ell=1}^{k}v_{\ell}^{T}G_{\ell}\Sigma_{\ell}^{\frac{1}{2}}w+\psi(w,v)\leq$
$\displaystyle\leq\min_{w\in\mathcal{S}^{\delta}_{w}}\max_{v\in\mathcal{S}^{\delta}_{v}}\sum_{\ell=1}^{k}v_{\ell}^{T}G_{\ell}\Sigma_{\ell}^{\frac{1}{2}}w+\psi(w,v)-\min_{w\in\mathcal{S}_{w}}\max_{v\in\mathcal{S}^{\delta}_{v}}\sum_{\ell=1}^{k}v_{\ell}^{T}G_{\ell}\Sigma_{\ell}^{\frac{1}{2}}w+\psi(w,v)\leq$
$\displaystyle\leq\max_{v\in\mathcal{S}^{\delta}_{v}}\sum_{\ell=1}^{k}v_{\ell}^{T}G_{\ell}\Sigma_{\ell}^{\frac{1}{2}}w^{\delta}_{*}+\psi(w^{\delta}_{*},v)-\max_{v\in\mathcal{S}^{\delta}_{v}}\sum_{\ell=1}^{k}v_{\ell}^{T}G_{\ell}\Sigma_{\ell}^{\frac{1}{2}}w_{*}+\psi(w_{*},v)\leq$
$\displaystyle\leq\max_{v\in\mathcal{S}^{\delta}_{v}}\left[\sum_{\ell=1}^{k}v_{\ell}^{T}G_{\ell}\Sigma_{\ell}^{\frac{1}{2}}w^{\delta}_{*}+\psi(w^{\delta}_{*},v)\right]-\left[\sum_{\ell=1}^{k}v_{\ell}^{T}G_{\ell}\Sigma_{\ell}^{\frac{1}{2}}w_{*}+\psi(w_{*},v)\right]=$
$\displaystyle=\left[\sum_{\ell=1}^{k}{v_{\ell}}_{*}^{T}G_{\ell}\Sigma_{\ell}^{\frac{1}{2}}w^{\delta}_{*}+\psi(w^{\delta}_{*},v_{*})\right]-\left[\sum_{\ell=1}^{k}{v_{\ell}}_{*}^{T}G_{\ell}\Sigma_{\ell}^{\frac{1}{2}}w_{*}+\psi(w_{*},v_{*})\right]\leq\left(\sum^{k}_{\ell=1}\|G_{\ell}\|_{op}\|\Sigma_{\ell}^{\frac{1}{2}}\|_{op}\right)D\delta+L\delta\leq$
$\displaystyle\leq\left(\sum^{k}_{\ell=1}\sqrt{d}+\sqrt{n_{\ell}}+\frac{1}{\sqrt{\delta}}\right)D\sigma\delta+L\delta\text{
with probability at least }(1-2e^{\frac{-1}{4\delta}})^{k}\text{ due to
Gaussian concentration, where }$
$\displaystyle\sigma=\max_{\ell}\|\Sigma^{\frac{1}{2}}_{\ell}\|_{op}$
$\displaystyle
w_{*}=\operatorname*{arg\,min}_{w\in\mathcal{S}_{w}}\max_{v\in\mathcal{S}^{\delta}_{v}}\sum_{\ell=1}^{k}v_{\ell}^{T}G_{\ell}\Sigma_{\ell}^{\frac{1}{2}}w+\psi(w,v)$
$\displaystyle w^{\delta}_{*}\in\mathcal{S}^{\delta}_{w}\text{ is such that
}\|w^{\delta}_{*}-w_{*}\|\leq\delta$ $\displaystyle
v_{*}=\operatorname*{arg\,max}_{v\in\mathcal{S}^{\delta}_{v}}\left[\sum_{\ell=1}^{k}v_{\ell}^{T}G_{\ell}\Sigma_{\ell}^{\frac{1}{2}}w^{\delta}_{*}+\psi(w^{\delta}_{*},v)\right]-\left[\sum_{\ell=1}^{k}v_{\ell}^{T}G_{\ell}\Sigma_{\ell}^{\frac{1}{2}}w_{*}+\psi(w_{*},v)\right]$

We also have:

$\displaystyle\phi^{\delta}(g,h)-\phi(g,h)=\min_{w\in\mathcal{S}^{\delta}_{w}}\max_{v\in\mathcal{S}^{\delta}_{v}}\sum_{\ell=1}^{k}\|v_{\ell}\|_{2}g_{\ell}^{T}\Sigma_{\ell}^{\frac{1}{2}}w+\|\Sigma_{\ell}^{\frac{1}{2}}w\|_{2}h_{\ell}^{T}v_{\ell}+\psi(w,v)-$
$\displaystyle-\min_{w\in\mathcal{S}_{w}}\max_{v\in\mathcal{S}_{v}}\sum_{\ell=1}^{k}\|v_{\ell}\|_{2}g_{\ell}^{T}\Sigma_{\ell}^{\frac{1}{2}}w+\|\Sigma_{\ell}^{\frac{1}{2}}w\|_{2}h_{\ell}^{T}v_{\ell}+\psi(w,v)\geq\min_{w\in\mathcal{S}^{\delta}_{w}}\max_{v\in\mathcal{S}^{\delta}_{v}}\sum_{\ell=1}^{k}\|v_{\ell}\|_{2}g_{\ell}^{T}\Sigma_{\ell}^{\frac{1}{2}}w+\|\Sigma_{\ell}^{\frac{1}{2}}w\|_{2}h_{\ell}^{T}v_{\ell}+\psi(w,v)-$
$\displaystyle-\min_{w\in\mathcal{S}^{\delta}_{w}}\max_{v\in\mathcal{S}_{v}}\sum_{\ell=1}^{k}\|v_{\ell}\|_{2}g_{\ell}^{T}\Sigma_{\ell}^{\frac{1}{2}}w+\|\Sigma_{\ell}^{\frac{1}{2}}w\|_{2}h_{\ell}^{T}v_{\ell}+\psi(w,v)\geq$
$\displaystyle\geq\min_{w\in\mathcal{S}^{\delta}_{w}}\left[\max_{v\in\mathcal{S}^{\delta}_{v}}\sum_{\ell=1}^{k}\|v_{\ell}\|_{2}g_{\ell}^{T}\Sigma_{\ell}^{\frac{1}{2}}w+\|\Sigma_{\ell}^{\frac{1}{2}}w\|_{2}h_{\ell}^{T}v_{\ell}+\psi(w,v)\right]-$
$\displaystyle-\left[\max_{v\in\mathcal{S}_{v}}\sum_{\ell=1}^{k}\|v_{\ell}\|_{2}g_{\ell}^{T}\Sigma_{\ell}^{\frac{1}{2}}w+\|\Sigma_{\ell}^{\frac{1}{2}}w\|_{2}h_{\ell}^{T}v_{\ell}+\psi(w,v)\right]\geq$
$\displaystyle\geq\left[\sum_{\ell=1}^{k}\|{v^{\delta}_{\ell}}_{*}\|_{2}g_{\ell}^{T}\Sigma_{\ell}^{\frac{1}{2}}w_{*}+\|\Sigma_{\ell}^{\frac{1}{2}}w_{*}\|_{2}h_{\ell}^{T}{v^{\delta}_{\ell}}_{*}+\psi(w_{*},v^{\delta}_{*})\right]-$
$\displaystyle-\left[\sum_{\ell=1}^{k}\|{v_{\ell}}_{*}\|_{2}g_{\ell}^{T}\Sigma_{\ell}^{\frac{1}{2}}w_{*}+\|\Sigma_{\ell}^{\frac{1}{2}}w_{*}\|_{2}h_{\ell}^{T}{v_{\ell}}_{*}+\psi(w_{*},v_{*})\right]\geq$
$\displaystyle\geq-\left(\sum^{k}_{\ell=1}(\|g_{\ell}\|+\|h_{\ell}\|)\|\Sigma_{\ell}^{\frac{1}{2}}\|_{op}\right)D\delta-L\delta\geq-\left(\sum^{k}_{\ell=1}\sqrt{d}+\sqrt{n_{\ell}}+\frac{1}{\sqrt{\delta}}\right)D\sigma\delta-L\delta$
$\displaystyle\text{ with probability at least
}(1-2e^{\frac{-1}{4\delta}})^{k}\text{ due to Gaussian concentration, where}$
$\displaystyle
w_{*}=\operatorname*{arg\,min}_{w\in\mathcal{S}^{\delta}_{w}}\left[\max_{v\in\mathcal{S}^{\delta}_{v}}\sum_{\ell=1}^{k}\|v_{\ell}\|_{2}g_{\ell}^{T}\Sigma_{\ell}^{\frac{1}{2}}w+\|\Sigma_{\ell}^{\frac{1}{2}}w\|_{2}h_{\ell}^{T}v_{\ell}+\psi(w,v)\right]-$
$\displaystyle-\left[\max_{v\in\mathcal{S}_{v}}\sum_{\ell=1}^{k}\|v_{\ell}\|_{2}g_{\ell}^{T}\Sigma_{\ell}^{\frac{1}{2}}w+\|\Sigma_{\ell}^{\frac{1}{2}}w\|_{2}h_{\ell}^{T}v_{\ell}+\psi(w,v)\right]$
$\displaystyle
v_{*}=\operatorname*{arg\,max}_{v\in\mathcal{S}_{v}}\sum_{\ell=1}^{k}\|{v_{\ell}}\|_{2}g_{\ell}^{T}\Sigma_{\ell}^{\frac{1}{2}}w_{*}+\|\Sigma_{\ell}^{\frac{1}{2}}w_{*}\|_{2}h_{\ell}^{T}{v_{\ell}}+\psi(w_{*},v)$
$\displaystyle v^{\delta}_{*}\in\mathcal{S}^{\delta}_{v}\text{ is such that
}\|v^{\delta}_{*}-v_{*}\|\leq\delta$

We obtain in a similar fashion:

$\displaystyle\tilde{\Phi}^{\delta}(G)-\tilde{\Phi}(G)=\min_{v\in\mathcal{S}^{\delta}_{v}}\max_{w\in\mathcal{S}^{\delta}_{w}}\sum_{\ell=1}^{k}v_{\ell}^{T}G_{\ell}\Sigma_{\ell}^{\frac{1}{2}}w-\psi(w,v)-\min_{v\in\mathcal{S}_{v}}\max_{w\in\mathcal{S}_{w}}\sum_{\ell=1}^{k}v_{\ell}^{T}G_{\ell}\Sigma_{\ell}^{\frac{1}{2}}w-\psi(w,v)\leq$
$\displaystyle\leq\min_{v\in\mathcal{S}^{\delta}_{v}}\max_{w\in\mathcal{S}^{\delta}_{w}}\sum_{\ell=1}^{k}v_{\ell}^{T}G_{\ell}\Sigma_{\ell}^{\frac{1}{2}}w-\psi(w,v)-\min_{v\in\mathcal{S}_{v}}\max_{w\in\mathcal{S}^{\delta}_{w}}\sum_{\ell=1}^{k}v_{\ell}^{T}G_{\ell}\Sigma_{\ell}^{\frac{1}{2}}w-\psi(w,v)\leq$
$\displaystyle\leq\max_{w\in\mathcal{S}^{\delta}_{w}}\sum_{\ell=1}^{k}{v^{\delta}_{\ell}}_{*}^{T}G_{\ell}\Sigma_{\ell}^{\frac{1}{2}}w-\psi(w,v^{\delta}_{*})-\max_{w\in\mathcal{S}^{\delta}_{w}}\sum_{\ell=1}^{k}v_{*}^{T}G_{\ell}\Sigma_{\ell}^{\frac{1}{2}}w-\psi(w,v_{*})\leq$
$\displaystyle\leq\max_{w\in\mathcal{S}^{\delta}_{w}}\left[\sum_{\ell=1}^{k}{v^{\delta}_{\ell}}_{*}^{T}G_{\ell}\Sigma_{\ell}^{\frac{1}{2}}w-\psi(w,v^{\delta}_{*})\right]-\left[\sum_{\ell=1}^{k}v_{*}^{T}G_{\ell}\Sigma_{\ell}^{\frac{1}{2}}w-\psi(w,v_{*})\right]=$
$\displaystyle=\left[\sum_{\ell=1}^{k}{v^{\delta}_{\ell}}_{*}^{T}G_{\ell}\Sigma_{\ell}^{\frac{1}{2}}w_{*}-\psi(w_{*},v^{\delta}_{*})\right]-\left[\sum_{\ell=1}^{k}{v_{\ell}}_{*}^{T}G_{\ell}\Sigma_{\ell}^{\frac{1}{2}}w_{*}-\psi(w_{*},v_{*})\right]\leq\left(\sum^{k}_{\ell=1}\|G_{\ell}\|_{op}\|\Sigma_{\ell}^{\frac{1}{2}}\|_{op}\right)D\delta+L\delta\leq$
$\displaystyle\leq\left(\sum^{k}_{\ell=1}\sqrt{d}+\sqrt{n_{\ell}}+\frac{1}{\sqrt{\delta}}\right)D\sigma\delta+L\delta\text{
with probability at least }(1-2e^{\frac{-1}{4\delta}})^{k}\text{ due to
Gaussian concentration, where }$
$\displaystyle\sigma=\max_{\ell}\|\Sigma^{\frac{1}{2}}_{\ell}\|_{op}$
$\displaystyle
v_{*}=\operatorname*{arg\,min}_{v\in\mathcal{S}_{v}}\max_{w\in\mathcal{S}^{\delta}_{w}}\sum_{\ell=1}^{k}v_{\ell}^{T}G_{\ell}\Sigma_{\ell}^{\frac{1}{2}}w+\psi(w,v)$
$\displaystyle v^{\delta}_{*}\in\mathcal{S}^{\delta}_{v}\text{ is such that
}\|v^{\delta}_{*}-v_{*}\|\leq\delta$ $\displaystyle
w_{*}=\operatorname*{arg\,max}_{w\in\mathcal{S}^{\delta}_{w}}\left[\sum_{\ell=1}^{k}{v^{\delta}_{\ell}}_{*}^{T}G_{\ell}\Sigma_{\ell}^{\frac{1}{2}}w-\psi(w,v^{\delta}_{*})\right]-\left[\sum_{\ell=1}^{k}v_{*}^{T}G_{\ell}\Sigma_{\ell}^{\frac{1}{2}}w-\psi(w,v_{*})\right]$

Finally, derived in a similar fashion:

$\displaystyle\tilde{\phi}^{\delta}(g,h)-\tilde{\phi}(g,h)=\min_{v\in\mathcal{S}^{\delta}_{v}}\max_{w\in\mathcal{S}^{\delta}_{w}}\sum_{\ell=1}^{k}\|v_{\ell}\|_{2}g_{\ell}^{T}\Sigma_{\ell}^{\frac{1}{2}}w+\|\Sigma_{\ell}^{\frac{1}{2}}w\|_{2}h_{\ell}^{T}v_{\ell}-\psi(w,v)-$
$\displaystyle-\min_{v\in\mathcal{S}_{v}}\max_{w\in\mathcal{S}_{w}}\sum_{\ell=1}^{k}\|v_{\ell}\|_{2}g_{\ell}^{T}\Sigma_{\ell}^{\frac{1}{2}}w+\|\Sigma_{\ell}^{\frac{1}{2}}w\|_{2}h_{\ell}^{T}v_{\ell}-\psi(w,v)\geq$
$\displaystyle\geq\min_{v\in\mathcal{S}^{\delta}_{v}}\max_{w\in\mathcal{S}^{\delta}_{w}}\sum_{\ell=1}^{k}\|v_{\ell}\|_{2}g_{\ell}^{T}\Sigma_{\ell}^{\frac{1}{2}}w+\|\Sigma_{\ell}^{\frac{1}{2}}w\|_{2}h_{\ell}^{T}v_{\ell}-\psi(w,v)-$
$\displaystyle-\min_{v\in\mathcal{S}^{\delta}_{v}}\max_{w\in\mathcal{S}_{w}}\sum_{\ell=1}^{k}\|v_{\ell}\|_{2}g_{\ell}^{T}\Sigma_{\ell}^{\frac{1}{2}}w+\|\Sigma_{\ell}^{\frac{1}{2}}w\|_{2}h_{\ell}^{T}v_{\ell}-\psi(w,v)\geq$
$\displaystyle\geq\min_{v\in\mathcal{S}^{\delta}_{v}}\left[\max_{w\in\mathcal{S}^{\delta}_{w}}\sum_{\ell=1}^{k}\|v_{\ell}\|_{2}g_{\ell}^{T}\Sigma_{\ell}^{\frac{1}{2}}w+\|\Sigma_{\ell}^{\frac{1}{2}}w\|_{2}h_{\ell}^{T}v_{\ell}-\psi(w,v)\right]-$
$\displaystyle-\left[\max_{w\in\mathcal{S}_{w}}\sum_{\ell=1}^{k}\|v_{\ell}\|_{2}g_{\ell}^{T}\Sigma_{\ell}^{\frac{1}{2}}w+\|\Sigma_{\ell}^{\frac{1}{2}}w\|_{2}h_{\ell}^{T}v_{\ell}-\psi(w,v)\right]\geq$
$\displaystyle\geq\left[\sum_{\ell=1}^{k}\|{v_{\ell}}_{*}\|_{2}g_{\ell}^{T}\Sigma_{\ell}^{\frac{1}{2}}w^{\delta}_{*}+\|\Sigma_{\ell}^{\frac{1}{2}}w^{\delta}_{*}\|_{2}h_{\ell}^{T}{v_{\ell}}_{*}+\psi(w^{\delta}_{*},v_{*})\right]-$
$\displaystyle-\left[\sum_{\ell=1}^{k}\|{v_{\ell}}_{*}\|_{2}g_{\ell}^{T}\Sigma_{\ell}^{\frac{1}{2}}w_{*}+\|\Sigma_{\ell}^{\frac{1}{2}}w_{*}\|_{2}h_{\ell}^{T}{v_{\ell}}_{*}+\psi(w_{*},v_{*})\right]\geq$
$\displaystyle\geq-\left(\sum^{k}_{\ell=1}(\|g_{\ell}\|+\|h_{\ell}\|)\|\Sigma_{\ell}^{\frac{1}{2}}\|_{op}\right)D\delta-L\delta\geq-\left(\sum^{k}_{\ell=1}\sqrt{d}+\sqrt{n_{\ell}}+\frac{1}{\sqrt{\delta}}\right)D\sigma\delta-L\delta$
$\displaystyle\text{ with probability at least
}(1-2e^{\frac{-1}{4\delta}})^{k}\text{ due to Gaussian concentration, where}$
$\displaystyle
v_{*}=\operatorname*{arg\,min}_{v\in\mathcal{S}^{\delta}_{v}}\left[\max_{w\in\mathcal{S}^{\delta}_{w}}\sum_{\ell=1}^{k}\|v_{\ell}\|_{2}g_{\ell}^{T}\Sigma_{\ell}^{\frac{1}{2}}w+\|\Sigma_{\ell}^{\frac{1}{2}}w\|_{2}h_{\ell}^{T}v_{\ell}-\psi(w,v)\right]-$
$\displaystyle-\left[\max_{w\in\mathcal{S}_{w}}\sum_{\ell=1}^{k}\|v_{\ell}\|_{2}g_{\ell}^{T}\Sigma_{\ell}^{\frac{1}{2}}w+\|\Sigma_{\ell}^{\frac{1}{2}}w\|_{2}h_{\ell}^{T}v_{\ell}-\psi(w,v)\right]$
$\displaystyle
w_{*}=\operatorname*{arg\,max}_{w\in\mathcal{S}_{w}}\sum_{\ell=1}^{k}\|{v_{\ell}}_{*}\|_{2}g_{\ell}^{T}\Sigma_{\ell}^{\frac{1}{2}}w+\|\Sigma_{\ell}^{\frac{1}{2}}w\|_{2}h_{\ell}^{T}{v_{\ell}}_{*}+\psi(w,v_{*})$
$\displaystyle w^{\delta}_{*}\in\mathcal{S}^{\delta}_{w}\text{ is such that
}\|w^{\delta}_{*}-w_{*}\|\leq\delta$

Taking the limit $\delta\to 0$ in all inequalities above, we arrive at the
desired results. ∎

We are now ready to prove Theorem 4 modulo Lemma 1:

###### Proof.

1. Note that $|\Phi(G)-c|>\eta$ holds if and only if either $\Phi(G)>c+\eta$ or $\Phi(G)<c-\eta$ and, moreover, the latter two events are disjoint since $\eta>0$. The same description is true for $|\phi(g,h)-c|>\eta$. Thus, it suffices to show the following two inequalities:

$\displaystyle\mathbb{P}(\Phi(G)<c-\eta)\leq
2^{k}\mathbb{P}(\phi(g,h)<c-\eta)$ (12)
$\displaystyle\mathbb{P}(-\Phi(G)<-c-\eta)\leq
2^{k}\mathbb{P}(-\phi(g,h)<-c-\eta)$ (13)

To simplify the second inequality above, swap min and max in the definition of
$\Phi(G)$ due to the convexity-concavity of $\psi(w,v)$ and note that:

$\displaystyle-\Phi(G)=-\max_{v\in\mathcal{S}_{v}}\min_{w\in\mathcal{S}_{w}}v^{T}\begin{pmatrix}G_{1}&0&\cdots&0\\\
0&G_{2}&\cdots&0\\\ \vdots&&\ddots&\vdots\\\
0&0&\cdots&G_{k}\end{pmatrix}\begin{pmatrix}\Sigma_{1}^{\frac{1}{2}}\\\
\Sigma_{2}^{\frac{1}{2}}\\\ \vdots\\\
\Sigma_{k}^{\frac{1}{2}}\end{pmatrix}w+\psi(w,v)$
$\displaystyle=\min_{v\in\mathcal{S}_{v}}\max_{w\in\mathcal{S}_{w}}v^{T}\begin{pmatrix}-G_{1}&0&\cdots&0\\\
0&-G_{2}&\cdots&0\\\ \vdots&&\ddots&\vdots\\\
0&0&\cdots&-G_{k}\end{pmatrix}\begin{pmatrix}\Sigma_{1}^{\frac{1}{2}}\\\
\Sigma_{2}^{\frac{1}{2}}\\\ \vdots\\\
\Sigma_{k}^{\frac{1}{2}}\end{pmatrix}w-\psi(w,v)$

Hence, using that $G_{1},\dots,G_{k}$ are i.i.d. $\mathcal{N}(0,1)$, we
obtain:

$\displaystyle\mathbb{P}(-\Phi(G)<-c-\eta)=\mathbb{P}(\tilde{\Phi}(G)<-c-\eta)$

where

$\displaystyle\tilde{\Phi}(G)=\min_{v\in\mathcal{S}_{v}}\max_{w\in\mathcal{S}_{w}}v^{T}\begin{pmatrix}G_{1}&0&\cdots&0\\\
0&G_{2}&\cdots&0\\\ \vdots&&\ddots&\vdots\\\
0&0&\cdots&G_{k}\end{pmatrix}\begin{pmatrix}\Sigma_{1}^{\frac{1}{2}}\\\
\Sigma_{2}^{\frac{1}{2}}\\\ \vdots\\\
\Sigma_{k}^{\frac{1}{2}}\end{pmatrix}w-\psi(w,v)$

Also remark:

$\displaystyle\mathbb{P}(-\phi(g,h)<-c-\eta)=\mathbb{P}\left(-\min_{w\in\mathcal{S}_{w}}\max_{v\in\mathcal{S}_{v}}\sum_{\ell=1}^{k}\|v_{\ell}\|_{2}g_{\ell}^{T}\Sigma_{\ell}^{\frac{1}{2}}w+\|\Sigma_{\ell}^{\frac{1}{2}}w\|_{2}h_{\ell}^{T}v_{\ell}+\psi(w,v)<-c-\eta\right)=$
$\displaystyle=\mathbb{P}\left(\max_{w\in\mathcal{S}_{w}}\min_{v\in\mathcal{S}_{v}}\sum_{\ell=1}^{k}\|v_{\ell}\|_{2}(-g_{\ell})^{T}\Sigma_{\ell}^{\frac{1}{2}}w+\|\Sigma_{\ell}^{\frac{1}{2}}w\|_{2}(-h_{\ell})^{T}v_{\ell}-\psi(w,v)<-c-\eta\right)=$
$\displaystyle=\mathbb{P}\left(\max_{w\in\mathcal{S}_{w}}\min_{v\in\mathcal{S}_{v}}\sum_{\ell=1}^{k}\|v_{\ell}\|_{2}g_{\ell}^{T}\Sigma_{\ell}^{\frac{1}{2}}w+\|\Sigma_{\ell}^{\frac{1}{2}}w\|_{2}h_{\ell}^{T}v_{\ell}-\psi(w,v)<-c-\eta\right)\leq$
$\displaystyle\leq\mathbb{P}\left(\min_{v\in\mathcal{S}_{v}}\max_{w\in\mathcal{S}_{w}}\sum_{\ell=1}^{k}\|v_{\ell}\|_{2}g_{\ell}^{T}\Sigma_{\ell}^{\frac{1}{2}}w+\|\Sigma_{\ell}^{\frac{1}{2}}w\|_{2}h_{\ell}^{T}v_{\ell}-\psi(w,v)<-c-\eta\right)=\mathbb{P}(\tilde{\phi}(g,h)<-c-\eta)$
$\displaystyle\text{ where
}\tilde{\phi}(g,h)=\min_{v\in\mathcal{S}_{v}}\max_{w\in\mathcal{S}_{w}}\sum_{\ell=1}^{k}\|v_{\ell}\|_{2}g_{\ell}^{T}\Sigma_{\ell}^{\frac{1}{2}}w+\|\Sigma_{\ell}^{\frac{1}{2}}w\|_{2}h_{\ell}^{T}v_{\ell}-\psi(w,v)$

Denoting $C=c-\eta$ and $\tilde{C}=-c-\eta$, we then have to show the
following two inequalities:

$\displaystyle\mathbb{P}(\Phi(G)<C)\leq 2^{k}\mathbb{P}(\phi(g,h)<C)$ (14)
$\displaystyle\mathbb{P}(\tilde{\Phi}(G)<\tilde{C})\leq
2^{k}\mathbb{P}(\tilde{\phi}(g,h)<\tilde{C})$ (15)

Note that according to Lemma 2, it is enough to prove the desired inequalities
for any sequence of $\delta$-nets
$\mathcal{S}^{\delta}_{w},\mathcal{S}^{\delta}_{v}$ with $\delta\to 0$.
Indeed, we would then have

$\mathbb{P}(\Phi(G)>C)\geq\mathbb{P}(\Phi^{\delta}(G)>C)\geq
2^{k}\mathbb{P}(\phi^{\delta}(g,h)>C)\geq 2^{k}\mathbb{P}(\phi(g,h)>C)$

as well as the same chain of inequalities for
$\tilde{\Phi}(G),\tilde{\phi}(g,h)$ and $\tilde{C}$. Moreover, we can assume
that each $\mathcal{S}^{\delta}_{v}$ is of the form
$\mathcal{S}^{\delta}_{v}=\mathcal{S}^{\delta}_{v_{1}}\times\dots\times\mathcal{S}^{\delta}_{v_{k}}$.
Denote $\mathcal{S}^{\delta}_{w}=\\{w_{i}\\}_{i\in
I},\mathcal{S}^{\delta}_{v_{1}}=\\{u_{j_{1}}\\}_{j_{1}\in
J_{1}},\dots,\mathcal{S}^{\delta}_{v_{k}}=\\{u_{j_{k}}\\}_{j_{k}\in J_{k}}$,
$t_{ij}=C-\psi(w_{i},v_{j}),\tilde{t}_{ji}=\tilde{C}+\psi(w_{i},v_{j})$.
Construct processes $X_{ij},\tilde{X}_{ji},Y_{ij},\tilde{Y}_{ji}$ as in the
statement of Lemma 1 for $I,J_{1},\dots,J_{k}$ introduced in the previous
sentence. Applying Lemma 1 and Theorem 1 to $X,Y,t$ and
$\tilde{X},\tilde{Y},\tilde{t}$ we obtain:

$\displaystyle\mathbb{P}(\bigcap_{i\in I}\bigcup_{j\in J}[Y_{ij}\geq
t_{ij}])\geq\mathbb{P}(\bigcap_{i\in I}\bigcup_{j\in J}[X_{ij}\geq t_{ij}])$
$\displaystyle\mathbb{P}(\bigcap_{j\in J}\bigcup_{i\in
I}[\tilde{Y}_{ji}\geq\tilde{t}_{ji}])\geq\mathbb{P}(\bigcap_{j\in
J}\bigcup_{i\in I}[\tilde{X}_{ji}\geq\tilde{t}_{ji}])$

We then deduce:

$\displaystyle\mathbb{P}(\min_{i\in I}\max_{j\in
J}{X_{ij}+\psi(w_{i},v_{j})<C})=1-\mathbb{P}(\bigcap_{i\in I}\bigcup_{j\in
J}[X_{ij}+\psi(w_{i},v_{j})\geq C])=1-\mathbb{P}(\bigcap_{i\in I}\bigcup_{j\in
J}[X_{ij}\geq t_{ij}])\geq$ $\displaystyle\geq 1-\mathbb{P}(\bigcap_{i\in
I}\bigcup_{j\in J}[Y_{ij}\geq t_{ij}])=1-\mathbb{P}(\bigcap_{i\in
I}\bigcup_{j\in J}[Y_{ij}+\psi(w_{i},v_{j})\geq C])=\mathbb{P}(\min_{i\in
I}\max_{j\in J}{Y_{ij}+\psi(w_{i},v_{j})<C})$
$\displaystyle\mathbb{P}(\min_{j\in J}\max_{i\in
I}{\tilde{X}_{ji}-\psi(w_{i},v_{j})<\tilde{C}})=1-\mathbb{P}(\bigcap_{j\in
J}\bigcup_{i\in
I}[\tilde{X}_{ji}-\psi(w_{i},v_{j})\geq\tilde{C}])=1-\mathbb{P}(\bigcap_{j\in
J}\bigcup_{i\in I}[\tilde{X}_{ji}\geq\tilde{t}_{ji}])\geq$ $\displaystyle\geq
1-\mathbb{P}(\bigcap_{j\in J}\bigcup_{i\in
I}[\tilde{Y}_{ji}\geq\tilde{t}_{ji}])=1-\mathbb{P}(\bigcap_{j\in
J}\bigcup_{i\in
I}[\tilde{Y}_{ji}-\psi(w_{i},v_{j})\geq\tilde{C}])=\mathbb{P}(\min_{j\in
J}\max_{i\in I}{\tilde{Y}_{ji}-\psi(w_{i},v_{j})<\tilde{C}})$

Note that

$\displaystyle\mathbb{P}(\min_{i\in I}\max_{j\in
J}{X_{ij}+\psi(w_{i},v_{j})<C})=\mathbb{P}(\phi^{\delta}(g,h)<C)$
$\displaystyle\mathbb{P}(\min_{j\in J}\max_{i\in
I}{\tilde{X}_{ji}-\psi(w_{i},v_{j})<\tilde{C}})=\mathbb{P}(\tilde{\phi}^{\delta}(g,h)<\tilde{C})$

Hence, it suffices to show the following two inequalities:

$\displaystyle\mathbb{P}(\Phi^{\delta}(G)<C)\geq\frac{1}{2^{k}}\mathbb{P}(\min_{i\in
I}\max_{j\in J}{Y_{ij}+\psi(w_{i},v_{j})<C})$
$\displaystyle\mathbb{P}(\tilde{\Phi}^{\delta}(G)<\tilde{C})\geq\frac{1}{2^{k}}\mathbb{P}(\min_{j\in
J}\max_{i\in I}{\tilde{Y}_{ji}-\psi(w_{i},v_{j})<\tilde{C}})$

The latter inequalities follow directly by conditioning on the event
$\gamma_{1},\dots,\gamma_{k}>0$, which happens with probability
$\frac{1}{2^{k}}$.

2. As we know from the proof of the previous part of the theorem, the following upper bound takes place:

$\displaystyle\mathbb{P}(\Phi(G)<\bar{\phi}+\delta)\leq
2^{k}\mathbb{P}(\phi<\bar{\phi}+\delta)\leq 2^{k}\epsilon$

Since $\mathcal{S}^{c}$ is compact, we can apply the same $\delta$-net
argument to deduce the following inequality as well:

$\displaystyle\mathbb{P}(\Phi_{\mathcal{S}^{c}}(G)<\bar{\phi}_{\mathcal{S}^{c}}-\delta)\leq
2^{k}\mathbb{P}(\phi_{\mathcal{S}^{c}}<\bar{\phi}_{\mathcal{S}^{c}}-\delta)\leq
2^{k}\epsilon$

Combining the results above implies:

$\displaystyle\mathbb{P}(\\{\Phi(G)>\bar{\phi}+\delta\\}\cup\\{\Phi_{\mathcal{S}^{c}}(G)<\bar{\phi}_{\mathcal{S}^{c}}-\delta\\})\leq
2^{k+1}\epsilon$

Which yields:

$\displaystyle
1-2^{k+1}\epsilon<\mathbb{P}(\\{\Phi(G)\leq\bar{\phi}+\delta\\}\cap\\{\Phi_{\mathcal{S}^{c}}(G)\geq\bar{\phi}_{\mathcal{S}^{c}}-\delta\\})$

By assumption $\bar{\phi}_{\mathcal{S}^{c}}>\bar{\phi}+3\delta$. Thus:

$\displaystyle
1-2^{k+1}\epsilon<\mathbb{P}(\\{\Phi(G)\leq\bar{\phi}+\delta\\}\cap\\{\Phi_{\mathcal{S}^{c}}(G)\geq\bar{\phi}_{\mathcal{S}^{c}}-\delta\\})\leq\mathbb{P}(\Phi(G)<\Phi_{\mathcal{S}^{c}}(G)-\delta)$

Therefore:

$\displaystyle 1-2^{k+1}\epsilon<\mathbb{P}(w_{\Phi(G)}\in\mathcal{S})$

∎

We proceed to prove Lemma 1 now:

###### Proof.

Recall the definitions of the Gaussian processes we have to compare, where
$v_{j}$ stands as a shorthand notation for
$(v_{j_{1}},\dots,v_{j_{k}})^{T}\in\mathbb{R}^{n_{1}}\times\dots\times\mathbb{R}^{n_{k}}$:

$Y_{ij}={v_{j}}^{T}\begin{pmatrix}G_{1}&0&\cdots&0\\\ 0&G_{2}&\cdots&0\\\
\vdots&&\ddots&\vdots\\\
0&0&\cdots&G_{k}\end{pmatrix}\begin{pmatrix}\Sigma_{1}^{\frac{1}{2}}\\\
\Sigma_{2}^{\frac{1}{2}}\\\ \vdots\\\
\Sigma_{k}^{\frac{1}{2}}\end{pmatrix}w_{i}+\sum^{k}_{\ell=1}\gamma_{\ell}\|v_{j_{\ell}}\|\|\Sigma_{\ell}^{\frac{1}{2}}w_{i}\|~{}~{}~{}\mbox{and}~{}~{}~{}X_{ij}=\sum^{k}_{\ell=1}\|v_{j_{\ell}}\|w_{i}^{T}\Sigma^{\frac{1}{2}}_{\ell}g_{\ell}+{v_{j_{\ell}}}^{T}h_{\ell}\|\Sigma^{\frac{1}{2}}_{\ell}w_{i}\|$

Calculating the covariances is straightforward using that $G_{\ell}$ and
$G_{\ell^{\prime}}$ are independent whenever $\ell\neq\ell^{\prime}$:

$\mathbb{E}[Y_{ij}Y_{i^{\prime}j^{\prime}}]=\sum^{k}_{\ell=1}{v_{j_{\ell}}}^{T}v_{j^{\prime}_{\ell}}w_{i}^{T}\Sigma_{\ell}w_{i^{\prime}}+\|v_{j_{\ell}}\|\|v_{j^{\prime}_{\ell}}\|\|\Sigma_{\ell}^{\frac{1}{2}}w_{i}\|\|\Sigma_{\ell}^{\frac{1}{2}}w_{i^{\prime}}\|$
$\mathbb{E}[X_{ij}X_{i^{\prime}j^{\prime}}]=\sum^{k}_{\ell=1}\|v_{j_{\ell}}\|\|v_{j^{\prime}_{\ell}}\|w_{i}^{T}\Sigma_{\ell}w_{i^{\prime}}+{v_{j_{\ell}}}^{T}v_{j^{\prime}_{\ell}}\|\Sigma_{\ell}^{\frac{1}{2}}w_{i}\|\|\Sigma_{\ell}^{\frac{1}{2}}w_{i^{\prime}}\|$

Hence, the third assumption of Gordon’s Gaussian comparison theorem follows
from Cauchy-Schwartz:

$\mathbb{E}[Y_{ij}Y_{i^{\prime}j^{\prime}}-X_{ij}X_{i^{\prime}j^{\prime}}]=\sum_{\ell=1}^{k}({v_{j_{\ell}}}^{T}v_{j^{\prime}_{\ell}}-\|v_{j_{\ell}}\|\|v_{j^{\prime}_{\ell}}\|)({w_{i}}^{T}\Sigma_{\ell}w_{i^{\prime}}-\|\Sigma_{\ell}^{\frac{1}{2}}w_{i}\|\|\Sigma_{\ell}^{\frac{1}{2}}w_{i^{\prime}}\|)\geq
0$

Moreover, if either $i=i^{\prime}$ or $j=j^{\prime}$ then the expression above
vanishes, implying the first and the second assumptions as well. The proof is
almost identical for the processes $\tilde{X}$ and $\tilde{Y}$.

∎

##  Appendix B Concentration

######  Lemma 3.

$\phi(g,h)$ is a $\sigma\sqrt{2}R_{w}R_{v}$\- Lipschitz function of $(g,h)$,
where

$\displaystyle\sigma=\max_{\ell}\|\Sigma^{\frac{1}{2}}_{\ell}\|_{op}$
$\displaystyle R_{w}=\max_{w\in\mathcal{S}_{w}}\\{\|w\|\\}$ $\displaystyle
R_{v}=\max_{v\in\mathcal{S}_{v}}\\{\|v\|\\}$

###### Proof.

Let $g_{1},g_{2}\in\mathbb{R}^{d\times\ell}$ and
$h_{1},h_{2}\in\mathbb{R}^{n\times\ell}$ be $\ell$-tuples of i.i.d. Gaussian
vectors.

Define:

$\displaystyle(w_{1},v_{1})=\operatorname*{arg\,min}_{w\in S_{w}}\max_{v\in
S_{v}}\sum^{k}_{\ell=1}\|v_{\ell}\|w^{T}\Sigma^{\frac{1}{2}}_{\ell}{g_{1}}_{\ell}+v_{\ell}^{T}{h_{1}}_{\ell}\|\Sigma^{\frac{1}{2}}_{\ell}w\|+\psi(w,v)$
$\displaystyle v_{2}=\operatorname*{arg\,max}_{v\in
S_{v}}\sum^{k}_{\ell=1}\|v_{\ell}\|w_{1}^{T}\Sigma^{\frac{1}{2}}_{\ell}g_{2\ell}+v_{\ell}^{T}h_{2\ell}\|\Sigma^{\frac{1}{2}}_{\ell}w_{1}\|+\psi(w_{1},v)$

We then have:

$\displaystyle\phi(g_{2},h_{2})\leq\sum^{k}_{\ell=1}\|v_{2}\|w_{1}^{T}\Sigma^{\frac{1}{2}}_{\ell}{g_{2}}_{\ell}+{v_{2}}_{\ell}^{T}{h_{2}}_{\ell}\|\Sigma^{\frac{1}{2}}_{\ell}w_{1}\|+\psi(w_{1},v_{2})$
$\displaystyle\phi(g_{1},h_{1})\geq\sum^{k}_{\ell=1}\|v_{2}\|w_{1}^{T}\Sigma^{\frac{1}{2}}_{\ell}{g_{1}}_{\ell}+{v_{2}}_{\ell}^{T}{h_{1}}_{\ell}\|\Sigma^{\frac{1}{2}}_{\ell}w_{1}\|+\psi(w_{1},v_{2})$

Therefore:

$\displaystyle\phi(g_{2},h_{2})-\phi(g_{1},h_{1})$
$\displaystyle\leq\sum^{k}_{\ell=1}\|v_{2}\|w_{1}^{T}\Sigma^{\frac{1}{2}}_{\ell}(g_{2\ell}-g_{1\ell})+{v_{2}}_{\ell}^{T}(h_{2\ell}-h_{1\ell})\|\Sigma^{\frac{1}{2}}_{\ell}w_{1}\|\leq$
$\displaystyle\leq\sum^{k}_{\ell=1}\|v_{2}\|\|w_{1}^{T}\Sigma^{\frac{1}{2}}_{\ell}\|\|g_{1\ell}-g_{2\ell}\|+\|\Sigma^{\frac{1}{2}}_{\ell}w_{1}\|\|v_{2}\|\|h_{1\ell}-h_{2\ell}\|=$
$\displaystyle=\sum^{k}_{\ell=1}\|v_{2}\|\|w_{1}^{T}\Sigma^{\frac{1}{2}}_{\ell}\|(\|g_{1\ell}-g_{2\ell}\|+\|h_{1\ell}-h_{2\ell}\|)\leq$
$\displaystyle\leq\sqrt{2\sum^{k}_{\ell=1}\|v_{2}\|^{2}\|\Sigma^{\frac{1}{2}}_{\ell}w_{1}\|^{2}}\sqrt{\sum^{k}_{\ell=1}\|g_{1\ell}-g_{2\ell}\|^{2}+\|h_{1\ell}-h_{2\ell}\|^{2}}\leq$
$\displaystyle\leq\sigma\sqrt{2}R_{w}R_{v}\sqrt{\sum^{k}_{\ell=1}\|g_{1\ell}-g_{2\ell}\|^{2}+\|h_{1\ell}-h_{2\ell}\|^{2}}$

∎

######  Corollary 3.

Under the notation from the lemma above,

$\mathbb{P}(|\phi(g,h)-\mathbb{E}\phi(g,h)|>\epsilon)\leq
exp(-\frac{\epsilon^{2}}{4\sigma^{2}R^{2}_{w}R^{2}_{v}})$

###### Proof.

Follows immediately from the lemma above and Theorem 5.6 in Boucheron et al.,
(2013). ∎

##  Appendix C Applications

###  C.1 Multi-Source Gaussian Regression

####  C.1.1 Assumptions

The following assumptions are necessary for the Multi-source Gaussian
Regression Results to hold.

  * A1

The functions $\ell_{l}$, for all $l=1,\ldots,k$ and $R$ are proper, lower
semi-continuous, and convex. Furthermore, the function
$\sum_{l=1}^{k}\ell_{l}+R$ should be coercive, by which we mean:

$\displaystyle\lim_{\left\|\bm{\theta}\right\|_{2}\rightarrow\infty}\left(\sum_{l=1}^{k}\ell_{l}+R\right)(\theta)=+\infty$

  * A2

the Regularization function $R$ must satisfy the following scaling condition.
For any vector $x$ such that $\left\|x\right\|_{2}\leq c\sqrt{d}$ for some
constant $c$, this implies that

$\displaystyle\sup_{z\in\partial R(z)}\left\|z\right\|\leq C\sqrt{d}$

where $\partial R$ is the subdifferential of $R$, and $C$ is some constant.

  * A3

the noise $\nu_{l}$, for all $l=1,\ldots,k$, is a zero mean sub-Gaussian
random vector, with variance $\sigma_{\bm{\nu},l}$.

We recall the setup discussed in section 2.3

$\min_{\bm{\theta}\in\mathbb{R}^{d}}\frac{1}{nk}\sum_{l=1}^{k}\ell_{l}\left(y_{l}-\frac{1}{\sqrt{d}}X_{l}\theta\right)+R(\theta),$
(16)

Where $y_{l}\in\mathbb{R}^{n},X_{l}\in\mathbb{R}^{n\times
d},\theta\in\mathbb{R}^{d}$. We recall that $X_{l}$ are Gaussian matrices,
defined by $G_{k}\Sigma^{1/2}_{l}$, where $G\in\mathbb{R}^{n\times d}$ has
i.i.d Gaussian elements, and $\Sigma_{l}\in\mathbb{R}^{d\times d}$ are PSD
covariance matrices. Finally, recalling the assumption that
$\mathbf{y}_{k}=\frac{1}{\sqrt{d}}X\theta^{*}+\nu_{k}$ where $\bm{\nu}_{k}$ is
i.i.d zero mean noise, with variance $\sigma_{\nu,k}$

We first define $e=\theta-\theta^{*}$ as the error vector and rewrite our
optimization as

$\displaystyle\min_{e\in\mathbb{R}^{d}}\frac{1}{nk}\sum_{l=1}^{k}\ell_{l}(\nu_{l}-\frac{1}{\sqrt{d}}G_{l}\Sigma^{1/2}\mathbf{e})+R(e+\theta^{*})$

We then let $z_{l}=\nu_{l}-G_{l}\Sigma^{1/2}_{l}e$ and let $\lambda_{l}$ be a
Lagrange multiplier

$\displaystyle\min_{e\in\mathbb{R}^{d},Z\in\mathbb{R}^{n\times
d}}\max_{\Lambda\in\mathbb{R}^{n\times
d}}\sum_{l=1}^{k}\frac{1}{nk}\lambda_{l}^{T}(z_{l}-\nu_{l}+\frac{1}{\sqrt{d}}G_{l}\Sigma_{k}^{1/2}e)+\frac{1}{nk}\ell_{l}(z_{l})+R(\mathbf{e}+\theta^{*}).$
(17)

Before we can apply our application of the generalized CGMT we must restrict
our optimization to compact and convex sets. We demonstrate this in the
following lemma.

######  Lemma 4 (Compact and Convex Sets).

Let $\hat{e}$, $\hat{Z}$, $\hat{\Lambda}$ be the optimal solution to (17).
There exist positive constants $C_{e},C_{Z},C_{\Lambda}$ such that:

$\displaystyle\Pr\left(\left\|\hat{e}\right\|_{2}\leq
C_{e}\sqrt{d}\right)\xrightarrow[d\rightarrow\infty]{P}1$
$\displaystyle\Pr\left(\left\|\hat{Z}\right\|_{2}\leq
C_{Z}\sqrt{n}\right)\xrightarrow[n\rightarrow\infty]{P}1$
$\displaystyle\Pr\left(\left\|\hat{\Lambda}\right\|_{2}\leq
C_{\Lambda}\sqrt{n}\right)\xrightarrow[n\rightarrow\infty]{P}1$

###### Proof.

We first show that the set of minimizers for $e$ is non-empty and compact. We
assume that the sum
$f(e)=\sum_{l=1}^{k}\ell(\nu_{l}-m^{-1/2}G_{l}\Sigma^{1/2}_{l}e)+R(e+\theta^{*})$
is a coercive, proper, and lower-semi continuous functions. As the function is
proper, there exists at least a single value $e_{0}$ such that
$f(\mathbf{e}_{0})<\infty$. Furthermore, by the fact that $f$ is coercive,
there exists an $\epsilon\in\mathbb{R}\geq 0$ such that for every
$e\in\mathbb{R}^{d\times k}$ for which $\left\|e-e_{0}\right\|\geq\epsilon$
implies that $f(e)\geq f(e_{0})$.

We then define

$\displaystyle S=\set{e\in\mathbb{R}^{d}}{\
\left\|e-e_{0}\right\|_{2}\leq\epsilon},$

we can then see that $S\cap\mathbb{R}^{d\times k}\neq\emptyset$ is nonempty
and compact. As such, there there exists an $\hat{e}\in S$ such that
$f(\hat{e})=\inf_{e\in S}f(e)\leq f(e_{0})$. From this we can conclude that
$f(\hat{e})\in\inf_{e\in\mathbb{R}^{d}}f(e)$, and that the set of minimizers
is bounded.

Having determined that the set of minimizers is a compact set with at least
one element, we can conclude that there exists a constant $C_{\mathbf{E}}$
which is independent of the ambient dimension $d$, such that

$\displaystyle\left\|\hat{e}\right\|_{2}\leq C_{e}\sqrt{d}.$

We now recall equation (17), and examine the optimality condition:

$\displaystyle\nabla_{\lambda_{l}}:\ $
$\displaystyle\nu_{l}-\frac{1}{\sqrt{m}}G_{l}\Sigma_{l}^{1/2}e=z_{l}$
$\displaystyle\nabla_{z_{l}}:\ $
$\displaystyle\lambda_{l}\in\partial\ell_{l}(z_{l})\qquad$
$\displaystyle\nabla_{e}:\ $
$\displaystyle\sum_{l=1}^{k}\Sigma_{l}^{1/2}G_{l}^{T}\lambda_{l}\in\left.\partial
R(x)\right|_{x=e+\theta^{*}}.$

From the optimality condition of $\lambda_{k}$ we can see that

$\displaystyle\left\|z_{l}\right\|\leq\left\|\nu_{l}\right\|_{2}+\frac{1}{\sqrt{d}}\left\|G_{l}\right\|_{2}\left\|\Sigma_{l}^{1/2}\right\|_{2}\left\|e\right\|$

We note that $\nu_{l}$ is a sub-Gaussian random variable, as such its norm can
asymptotically be bounded by a $C\sqrt{n}$ for some constant $C$. Similarly
$\frac{1}{\sqrt{m}}\left\|G_{l}\right\|$ is bounded in operator norm by a
constant asymptotically by standard random matrix theory results (see for
example (Papaspiliopoulos,, 2020)[corollary 7.3.3]). By making use of the
bound on $\left\|e\right\|$ we can find that each $z_{l}$ is bounded in norm.
From this we can see that there exists some constant $C_{Z}$ such that

$\displaystyle\Pr\left(\left\|\hat{Z}\right\|_{2}\leq
C_{Z}\sqrt{n}\right)\xrightarrow[n\rightarrow\infty]{P}1$

Finally, the scaling condition on $R$ implies the existence of a constant
$C_{\lambda}$. ∎

We now define the following sets

$\displaystyle\mathcal{S}_{e}=\set{e\in\mathbb{R}^{d}}{\ \left\|e\right\|\leq
C_{e}\sqrt{d}}$ $\displaystyle\mathcal{S}_{Z}=\set{Z\in\mathbb{R}^{n\times
k}}{\ \left\|Z\right\|\leq C_{Z}\sqrt{n}}$
$\displaystyle\mathcal{S}_{\Lambda}=\set{\Lambda\in\mathbb{R}^{n\times k}}{\
\left\|\Lambda\right\|\leq C_{\Lambda}\sqrt{n}},$

and note that our optimization problem can be expressed as:

$\displaystyle\min_{e\in\mathcal{S}_{e},Z\in\mathcal{S}_{Z}}\max_{\Lambda\in\mathcal{S}_{\Lambda}}\sum_{l=1}^{k}\frac{1}{nk}\lambda_{l}^{T}(z_{l}-\nu_{l}+\frac{1}{\sqrt{d}}G_{l}\Sigma_{k}^{1/2}e)+\frac{1}{nk}\ell_{l}(z_{l})+R(e+\theta^{*})$
$\displaystyle\overset{def}{=}\min_{e\in\mathcal{S}_{e}}\mathcal{P}(e,G_{1},\cdots,G_{k})$

We note that we now have a min-max optimization over compact and convex sets
in the form required for the application of theorem 4. We apply the
generalized CGMT to $\mathcal{P}$, from which we obtain:

$\displaystyle\min_{e\in\mathcal{S}_{e}}\left[\min_{Z\in\mathcal{S}_{Z}}\max_{\Lambda\in\mathcal{S}_{\Lambda}}\sum_{l=1}^{k}\frac{1}{nk\sqrt{d}}\left\|\lambda_{l}\right\|g_{l}^{T}\Sigma_{l}^{1/2}e+\frac{1}{nk\sqrt{d}}\left\|\Sigma^{1/2}_{l}e\right\|h_{l}^{T}\lambda_{l}\right.$
$\displaystyle\left.+\frac{1}{nk}\lambda_{l}^{T}z_{l}-\frac{1}{nk}\lambda_{l}^{T}\nu_{l}+\frac{1}{nk}\ell_{l}(z_{l})+R(e+\theta^{*})\right]$
$\displaystyle\overset{def}{=}\min_{e\in\mathcal{S}_{e}}\mathcal{A}(e,g_{1},\ldots,g_{k},h_{1},\ldots,h_{k})$

We can now note that if for a fixed value of $e$, if in the asymptotic limit
of $n,m\rightarrow\infty$ that $\mathcal{A}\rightarrow\bar{\mathcal{A}}$
converges to some fixed value, the CGMT guarantees that
$\mathcal{P}\rightarrow\bar{\mathcal{A}}$. This implies pointwise convergence
on the set $\mathcal{S}_{e}$, we can further establish uniform convergence by
noting that $\mathcal{S}_{e}$ is compact, and that $\mathcal{P}$ is Lipschitz
with respect to $e$, implying equicontinuity. Classical results from analysis
guarantee uniform convergence in these cases. As such we drop the outer
parenthesis and consider the joint minimization over $e,Z$ in the analysis of
$\mathcal{A}$.

$\displaystyle\min_{Z\in\mathcal{S}_{Z},e\in\mathcal{S}_{e}}\max_{\Lambda\in\mathcal{S}_{\Lambda}}\sum_{l=1}^{k}\frac{1}{nk\sqrt{d}}\left\|\lambda_{l}\right\|g_{l}^{T}\Sigma_{l}^{1/2}e+\frac{1}{nk\sqrt{d}}\left\|\Sigma^{1/2}_{l}e\right\|h_{l}^{T}\lambda_{l}$
$\displaystyle+\frac{1}{nk}\lambda_{l}^{T}z_{l}-\frac{1}{nk}\lambda_{l}^{T}\nu_{l}+\frac{1}{nk}\ell_{l}(z_{l})+R(\mathbf{e}+\theta^{*})$

We now define $p_{l}=\Sigma^{1/2}_{l}e$, and reintroduce this constraint using
the Lagrange multiplier $\mu_{l}$. We can note for each each $p_{l}$ that
$\left\|p_{l}\right\|\leq\sqrt{\sigma_{max}(\Sigma_{l})}\left\|e\right\|$, by
noting that $\Sigma_{l}$ has finite maximum singular value, and the bounds on
$\left\|\mathbf{e}\right\|$, we can conclude that there exists a compact set
$\mathcal{S}_{P}=\set{P\in\mathbb{R}^{d\times k}}{\ \left\|P\right\|_{2}\leq
C_{P}\sqrt{d}}$, where $P$ has columns $p_{l}$:

$\displaystyle\min_{Z\in\mathcal{S}_{Z},e\in\mathcal{S}_{e},P\in\mathcal{S}_{P}}\max_{\Lambda\in\mathcal{S}_{\Lambda},M}\sum_{l=1}^{k}\frac{1}{nk\sqrt{d}}\left\|\lambda_{l}\right\|g_{l}^{T}p_{l}+\frac{1}{nk\sqrt{d}}\left\|p_{l}\right\|h_{l}^{T}\lambda_{l}$
$\displaystyle+\frac{1}{nk}\lambda_{l}^{T}z_{l}-\frac{1}{nk}\lambda_{l}^{T}\nu_{l}+\frac{1}{nk}\ell_{l}(z_{l})+\frac{1}{dk}\mu_{l}^{T}(p_{l}-\Sigma^{1/2}_{l}e)+R(e+\theta^{*})$

where $M\in\mathbb{R}^{d\times k}$ has columns $\mu_{l}$.

We now let $\beta_{l}=\frac{1}{\sqrt{n}}\left\|\Lambda_{l}\right\|$ and solve
over $\lambda_{l}$, as shorthand we will define $\beta\in\mathbb{R}^{k}$, with
elements $\beta_{l}$.

$\displaystyle\min_{Z\in\mathcal{S}_{Z},e\in\mathcal{S}_{e},P\in\mathcal{S}_{P}}\max_{\beta\succeq
0,M}\sum_{l=1}^{k}\frac{\beta_{l}}{k\sqrt{nd}}g_{l}^{T}p+\frac{\beta_{l}}{k\sqrt{n}}\left\|\frac{1}{\sqrt{d}}\left\|p_{l}\right\|_{2}h_{l}+z_{l}-\nu_{l}\right\|_{2}$
$\displaystyle+\frac{1}{nk}\ell_{l}(z_{l})+\frac{1}{dk}\mu_{l}^{T}(p_{l}-\Sigma^{1/2}e)+R(e+\theta^{*})$

We now interchange the order of min and max, let
$\xi_{l}=\frac{1}{\sqrt{d}}\left\|p_{l}\right\|_{2}$, and solve over $P$. We
obtain:

$\displaystyle\max_{\beta\succeq
0,M}\min_{Z\in\mathcal{S}_{Z},e\in\mathcal{S}_{e},\xi\succeq
0}\sum_{l=1}^{k}\frac{\beta_{l}}{\sqrt{n}k}\left\|\xi_{l}h_{l}+z_{l}-\nu_{l}\right\|_{2}-\frac{\xi_{l}}{k\sqrt{d}}\left\|\sqrt{\frac{d}{n}}\beta_{l}\mathbf{g}_{l}+\mu_{l}\right\|_{2}$
$\displaystyle+\frac{1}{nk}\ell_{l}(z_{l})-\frac{1}{dk}\mu_{l}^{T}\Sigma^{1/2}e+R(e+\theta^{*})$

Recalling the square-root trick, where for any vector $a$, we can note that
$\left\|a\right\|_{2}=\min\limits_{q>0}\frac{q}{2}+\frac{\left\|a\right\|^{2}}{2q}$.
We apply the square root trick twice to the optimization above with parameters
$q_{l}$ and $r_{l}$

$\displaystyle\max_{\beta,r\succeq
0,M}\min_{Z\in\mathcal{S}_{Z},e\in\mathcal{S}_{e},\xi,q\succeq
0}\sum_{l=1}^{k}\frac{\beta_{l}q_{l}}{2k}-\frac{\xi_{l}r_{l}}{2k}+\frac{\beta_{l}}{2nkq_{l}}\left\|\xi_{l}h_{l}+z_{l}-\nu_{l}\right\|^{2}_{2}-\frac{\xi_{l}}{2kdr_{l}}\left\|\sqrt{\frac{d}{n}}\beta_{l}g_{l}+\mu_{l}\right\|_{2}^{2}$
$\displaystyle+\frac{1}{nk}\ell_{l}(z_{l})-\frac{1}{kd}\mu_{l}^{T}\Sigma^{1/2}e+R(e+\theta^{*})$

We can now recognize the Moreau envelopes over $\ell_{l}$:

$\displaystyle\max_{\beta,r\succeq 0,M}\min_{e\in\mathcal{S}_{e},\xi,q\succeq
0}\sum_{l=1}^{k}\frac{\beta_{l}q_{l}}{2k}-\frac{\xi_{l}r_{l}}{2k}-\frac{\xi_{l}}{2kmr_{l}}\left\|\sqrt{\frac{d}{n}}\beta_{l}g_{l}+\mu_{l}\right\|_{2}^{2}$
$\displaystyle+\frac{1}{nk}\mathcal{M}_{\frac{q_{l}}{\beta_{l}}\
\ell_{l}}\left(\nu_{l}-\xi_{l}h_{l}\right)-\frac{1}{kd}\mu_{l}^{T}\Sigma^{1/2}_{l}e+R(e+\theta^{*})$

We once again interchange the order of min and max and now solve over
$\mu_{l}$. We can find that the optimal solution is given by:

$\displaystyle\hat{\mu}_{l}=-\sqrt{\frac{d}{n}}\beta_{l}g_{l}-\frac{r_{l}}{\xi_{l}}\Sigma^{1/2}_{l}e$

Substituting in this value we obtain:

$\displaystyle\min_{\xi,q\succeq 0}\max_{\beta,r\succeq
0}\sum_{l=1}^{k}\frac{\beta_{l}q_{l}}{2k}-\frac{\xi_{l}r_{l}}{2k}+\frac{1}{nk}\mathcal{M}_{\frac{q_{l}}{\beta_{l}}\
\ell_{l}}\left(\nu_{l}-\xi_{l}h_{l}\right)$
$\displaystyle+\min_{e\in\mathcal{S}_{e}}\frac{1}{2d}e^{T}\left(\frac{1}{k}\sum_{l=1}^{k}\frac{r_{l}}{\xi_{k}}\Sigma_{l}\right)e+\frac{1}{d}\left(\frac{1}{k}\sum_{l=1}^{k}\beta_{l}\sqrt{\frac{d}{n}}\Sigma_{l}^{1/2}g_{l}\right)^{T}e_{l}+R(e+\theta^{*})$

We can now complete the square over $e$, from which we find that

$\displaystyle\min_{\xi,q\succeq 0}\max_{\bm{\beta},\mathbf{r}\succeq
0}\sum_{l=1}^{k}\frac{\beta_{l}q_{l}}{2k}-\frac{\xi_{l}r_{l}}{2k}+\frac{1}{nk}\mathcal{M}_{\frac{q_{l}}{\beta_{l}}\
\ell_{l}}\left(\nu_{l}-\xi_{l}h_{l}\right)-\frac{1}{2kd}b^{T}A^{-1}b$
$\displaystyle+\min_{e\in\mathcal{S}_{e}}\frac{1}{2d}\left(e+A^{-1}b\right)^{T}A\left(e+A^{-1}b\right)+R(e+\theta^{*})$

Where we have defined
$A=\left(\frac{1}{k}\sum_{l=1}^{k}\frac{r_{l}}{\xi_{k}}\Sigma_{l}\right)$ and
$b=\left(\frac{1}{k}\sum_{l=1}^{k}\beta_{l}\sqrt{\frac{d}{n}}\Sigma_{l}^{1/2}g_{l}\right)$.
We can note that $b^{T}A^{-1}b$ will concentrate to

$\displaystyle\frac{1}{k^{2}}\sum_{l=1}^{k}\frac{\beta_{l}^{2}d}{n}\text{Tr}\Sigma_{l}\left(\frac{1}{k}\sum_{l^{\prime}=1}^{k}\frac{r_{l^{\prime}}}{\xi_{l^{\prime}}}\Sigma_{l^{\prime}}\right)^{-1}$

We can now return $\theta=e+\theta^{*}$ as the optimization variable, and then
recognize the Moreau envelope over $R$, we obtain the optimization:

$\displaystyle\min_{\bm{\xi},\mathbf{q}\succeq\mathbf{0}}\max_{\bm{\beta},\mathbf{r}\succeq
0}\sum_{l=1}^{k}\frac{\beta_{l}q_{l}}{2k}-\frac{\xi_{l}r_{l}}{2k}+\frac{1}{nk}\mathcal{M}_{\frac{q_{l}}{\beta_{l}}\
\ell_{l}}\left(\nu_{l}-\xi_{l}h_{l}\right)$
$\displaystyle-\frac{1}{k^{2}}\sum_{l=1}^{k}\frac{\beta_{l}^{2}}{n}\text{Tr}\Sigma_{l}\left(\frac{1}{k}\sum_{l^{\prime}=1}^{k}\frac{r_{l^{\prime}}}{\xi_{l^{\prime}}}\Sigma_{l^{\prime}}\right)^{-1}+\frac{1}{d}\mathcal{M}_{A^{-1}\
R}\left(\theta^{*}-A^{-1}b\right)$

####  C.1.2 $\ell_{2}^{2}$ loss, and $\ell_{2}^{2}$ regularization

We consider the loss functions $\frac{1}{2}\left\|\cdot\right\|_{2}^{2}$. For
the regularization we will consider the following function

$\displaystyle R(\theta)=\frac{\lambda}{2d}\left\|\theta\right\|_{2}^{2}$

where $\lambda$ is a regularization parameter. We will assume that the noise
$\nu_{l}$ will be distributed normally, by
$\nu_{l}\sim\mathcal{N}(0,\sigma_{\nu,l}^{2}I)$. We can find the following
results:

#####  $\left\|\cdot\right\|_{2}$ loss

In this case we have:

$\displaystyle\mathcal{M}_{\frac{q_{l}}{\beta_{l}}\
\left\|\cdot\right\|_{2}^{2}}(\nu_{l}-\xi_{l}h_{l})=\min_{z_{l}}\frac{1}{2}\left\|z_{l}\right\|_{2}^{2}+\frac{\beta_{l}}{2q_{l}}\left\|\nu_{l}-\xi_{l}h_{l}-z_{l}\right\|_{2}^{2}$

We can find the optimal solution to be given by:

$\displaystyle\hat{z_{l}}=\frac{\beta_{l}}{\beta_{l}+q_{l}}(\nu_{l}-\xi_{l}h_{l})$

Similarly we can find the optimal value to be:

$\displaystyle\mathcal{M}_{\frac{q_{l}}{\beta_{l}}\
\left\|\cdot\right\|_{2}^{2}}(\nu_{l}-\xi_{l}h_{l})=\frac{1}{2}\left\|\frac{\beta_{l}}{\beta_{l}+q_{l}}(\nu_{l}-\xi_{l}h_{l})\right\|_{2}^{2}+\frac{\beta_{l}}{2q_{l}}\left\|\frac{q_{l}}{\beta_{l}+q_{l}}\nu_{l}-\frac{q_{l}\xi_{l}}{\beta_{l}+q_{l}}h_{l}\right\|_{2}^{2}$

This concentrates on its expected value, given by:

$\displaystyle\mathbb{E}\mathcal{M}_{\frac{q_{l}}{\beta_{l}}\
\left\|\cdot\right\|_{2}^{2}}(\nu_{l}-\xi_{l}h_{l})=\frac{n}{2}\frac{\beta_{l}}{\beta_{l}+q_{l}}(\sigma_{\nu,l}^{2}+\xi_{l}^{2})$

##### Regularization Function

We can find that the regularization function in this case take the form

$\displaystyle\mathcal{M}_{A^{-1}\
R}\left(\theta^{*}-A^{-1}b\right)=\min_{\theta}\frac{\lambda}{2d}\left\|\theta\right\|_{2}^{2}+\frac{1}{2d}\left(\theta-\theta^{*}+A^{-1}b\right)A(\theta-\theta^{*}+A^{-1}b)$

From this we can find that the optimal value for $\theta$ is given by:

$\displaystyle\hat{\theta}=\mathrm{prox}_{A^{-1}\
R}\left(\theta^{*}-A^{-1}b\right)=(\lambda
I+A)^{-1}\left(A\theta^{*}-b\right)$ (18)

We also find that the optimal value in this case is given by:

$\displaystyle-\frac{1}{2d}\left(A\theta^{*}-b\right)\left(\lambda
I+A\right)^{-1}\left(A\theta^{*}-b\right)+\frac{1}{2d}\theta^{*}A\theta^{*}+\frac{1}{d}\theta^{*T}b+\frac{1}{2d}b^{T}A^{-1}b$

We can note that this concentrates to:

$\displaystyle-\frac{1}{2d}\theta^{*T}\left(\frac{1}{k}\sum_{l=1}^{k}\frac{r_{l}}{\xi_{l}}\Sigma_{l}\right)\left(\lambda
I+\frac{1}{k}\sum_{l=1}^{k}\frac{r_{l}}{\xi_{l}}\Sigma_{l}\right)^{-1}\left(\frac{1}{k}\sum_{l=1}^{k}\frac{r_{l}}{\xi_{l}}\Sigma_{l}\right)\theta^{*}$
$\displaystyle-\frac{1}{2dk^{2}}\sum_{l=1}^{k}\frac{\beta_{l}^{2}d}{n}\text{Tr}\Sigma_{l}\left(\lambda
I+\frac{1}{k}\sum_{l=1}^{k}\frac{r_{l}}{\xi_{l}}\Sigma_{l}\right)^{-1}+\frac{1}{2dk}\theta^{*}\left(\sum_{l=1}^{k}\frac{r_{l}}{\xi_{l}}\Sigma_{l}\right)\theta^{*}$
$\displaystyle+\frac{1}{k^{2}}\sum_{l=1}^{k}\frac{\beta_{l}^{2}}{n}\text{Tr}\Sigma_{l}\left(\frac{1}{k}\sum_{l^{\prime}=1}^{k}\frac{r_{l^{\prime}}}{\xi_{l^{\prime}}}\Sigma_{l^{\prime}}\right)^{-1}$

As such we have as our total optimization problem:

$\displaystyle\min_{\xi,q\succeq 0}\max_{\beta,r\succeq
0}\sum_{l=1}^{k}\frac{\beta_{l}q_{l}}{2k}-\frac{\xi_{l}r_{l}}{2k}+\frac{n}{2}\frac{\beta_{l}}{\beta_{l}+q_{l}}(\sigma_{\nu,l}^{2}+\xi_{l}^{2})$
$\displaystyle-\frac{1}{2dk^{2}}\theta^{*T}\left(\sum_{l=1}^{k}\frac{r_{l}}{\xi_{l}}\Sigma_{l}\right)\left(\lambda
I+\frac{1}{k}\sum_{l=1}^{k}\frac{r_{l}}{\xi_{l}}\Sigma_{l}\right)^{-1}\left(\sum_{l=1}^{k}\frac{r_{l}}{\xi_{l}}\Sigma_{l}\right)\theta^{*}$
$\displaystyle-\frac{1}{2dk^{2}}\sum_{l=1}^{k}\frac{\beta_{l}^{2}d}{n}\text{Tr}\Sigma_{l}\left(\lambda
I+\frac{1}{k}\sum_{l=1}^{k}\frac{r_{l}}{\xi_{l}}\Sigma_{l}\right)^{-1}+\frac{1}{2dk}\theta^{*T}\left(\sum_{l=1}^{k}\frac{r_{l}}{\xi_{l}}\Sigma_{l}\right)\theta^{*}$

##### Generalization Error

We note that the generalization error is given by:

$\displaystyle\mathbb{E}\frac{1}{2k}\sum_{l=1}^{k}\left\|y_{k,new}-\frac{1}{\sqrt{d}}g_{k,new}^{T}\Sigma^{1/2}_{k}\hat{\theta}\right\|_{2}^{2}$
$\displaystyle=\frac{1}{2k}\sum_{k}\sigma_{\nu,k}^{2}-\frac{2}{d}\theta^{*T}\left(\sum_{l^{\prime}=1}^{k}\frac{r_{l^{\prime}}}{\xi_{l^{\prime}}}\Sigma_{l^{\prime}}\right)\left(\lambda
I+\frac{1}{k}\sum_{l^{\prime}=1}^{k}\frac{r_{l^{\prime}}}{\xi_{l^{\prime}}}\Sigma_{l^{\prime}}\right)^{-1}\Sigma_{l}\theta^{*}+\frac{1}{d}\theta^{*T}\Sigma_{l}\theta^{*}$
$\displaystyle+\frac{1}{d}\theta^{*T}\left(\sum_{l^{\prime}=1}^{k}\frac{r_{l^{\prime}}}{\xi_{l^{\prime}}}\Sigma_{l^{\prime}}\right)\left(\lambda
I+\frac{1}{k}\sum_{l^{\prime}=1}^{k}\frac{r_{l^{\prime}}}{\xi_{l^{\prime}}}\Sigma_{l^{\prime}}\right)^{-1}\Sigma_{l}\left(\lambda
I+\frac{1}{k}\sum_{l^{\prime}=1}^{k}\frac{r_{l^{\prime}}}{\xi_{l^{\prime}}}\Sigma_{l^{\prime}}\right)^{-1}\left(\sum_{l^{\prime}=1}^{k}\frac{r_{l^{\prime}}}{\xi_{l^{\prime}}}\Sigma_{l^{\prime}}\right)\theta^{*}$
$\displaystyle+\frac{1}{2k^{2}}\frac{\beta_{l}^{2}}{n}\text{Tr}\Sigma_{l}\left(\lambda
I+\frac{1}{k}\sum_{l^{\prime}=1}^{k}\frac{r_{l^{\prime}}}{\xi_{l^{\prime}}}\Sigma_{l^{\prime}}\right)^{-1}\Sigma_{l}\left(\lambda
I+\frac{1}{k}\sum_{l^{\prime}=1}^{k}\frac{r_{l^{\prime}}}{\xi_{l^{\prime}}}\Sigma_{l^{\prime}}\right)^{-1}$

Where we have made use of the optimal value of $\hat{\theta}$ given in
equation (18).

###  C.2 Binary Classification for GMMs with arbitrary covariance matrices

The following trick will be of use for the purposes of the present section:

The square root trick. If $x>0$, then its square root can be "linearized" as
follows:

$\sqrt{x}=\min_{\beta>0}\frac{1}{2\beta}+\frac{\beta x}{2}$

####  C.2.1 Proof of Theorem 6

###### Proof.

Recall the notation of Section 2.4, and also define
$M_{1},M_{2}\in\mathbb{R}^{\frac{n}{2}\times d}$ as

$M^{T}=(\underbrace{\begin{matrix}\mu_{1}&...&\mu_{1}\end{matrix}}_{\frac{n}{2}}\underbrace{\begin{matrix}\mu_{2}&...&\mu_{2}\end{matrix}}_{\frac{n}{2}})=\left(M_{1}^{T}|M_{2}^{T}\right)$
$z^{T}=\begin{pmatrix}\mathds{1}^{T}_{\frac{n}{2}}&-\mathds{1}^{T}_{\frac{n}{2}}\end{pmatrix}$

encode the means and the labels corresponding to each class respectively and
the classifier if found via solving

$\min_{w}\mathcal{L}((A+M)w-z)+\lambda f(w)$

Introducing $u:=(A+M)w-z$ and inserting a Lagrange multiplier, we have

$\min_{w,u}\max_{v}v^{T}Aw+v^{T}Mw-v^{T}z-v^{T}u+\mathcal{L}(u)+\lambda f(w)$

Applying Theorem 4 to the objective above and denoting
$v^{T}=(v_{1}^{T},v_{2}^{T})$ we arrive at the following:

$\min_{w,u}\max_{v_{1},v_{2}}v^{T}Mw-v^{T}z-v^{T}u+\mathcal{L}(u)+\lambda
f(w)+\sum^{2}_{i=1}\|v_{i}\|w^{T}\Sigma^{\frac{1}{2}}_{i}g_{i}+v_{i}^{T}h_{i}\|\Sigma^{\frac{1}{2}}_{i}w\|$

Performing the optimization over $v_{1},v_{2}$ yields:

$\min_{w,u}\max_{\beta_{1},\beta_{2}\geq 0}\mathcal{L}(u)+\lambda
f(w)+\sum^{2}_{i=1}\beta_{i}(w^{T}\Sigma^{\frac{1}{2}}_{i}g_{i}+\|h_{i}\|\Sigma^{\frac{1}{2}}_{i}w\|+M_{i}w-z_{i}-u_{i}\|)$

Using the square root trick we obtain:

$\displaystyle\min_{w,u}\max_{\beta_{1},\beta_{2}\geq
0}\min_{\tau_{1},\tau_{2}\geq 0}\mathcal{L}(u)+\lambda
f(w)+\sum^{2}_{i=1}\beta_{i}(w^{T}\Sigma^{\frac{1}{2}}_{i}g_{i}+\frac{\tau_{i}}{2}+$
$\displaystyle+\frac{1}{2\tau_{i}}(\frac{n}{2}\|\Sigma^{\frac{1}{2}}_{i}w\|^{2}+\frac{n}{2}(\mu_{i}^{T}w)^{2}+\frac{n}{2}+\|u_{i}\|^{2}-2\|\Sigma^{\frac{1}{2}}_{i}w\|h_{i}^{T}u_{i}-n(1-2c)\mu_{i}^{T}w-2u_{i}^{T}M_{i}w+2u_{i}^{T}z_{i}))$

Regrouping some terms and swapping the min and the max:

$\displaystyle\min_{\tau_{1},\tau_{2}\geq 0}\max_{\beta_{1},\beta_{2}\geq
0}\sum_{i=1}^{2}\beta_{i}\frac{\tau_{i}}{2}+\min_{w,u}\mathcal{L}(u)+\lambda
f(w)+\sum^{2}_{i=1}\beta_{i}(w^{T}\Sigma^{\frac{1}{2}}_{i}g_{i}+$
$\displaystyle+\frac{1}{2\tau_{i}}(\frac{n}{2}\|\Sigma^{\frac{1}{2}}_{i}w\|^{2}+\|M_{i}w\|^{2}+\|z_{i}\|^{2}+\|u_{i}\|^{2}+2\|\Sigma^{\frac{1}{2}}_{i}w\|h_{i}^{T}u_{i}-2z_{i}^{T}M_{i}w-2u_{i}^{T}M_{i}w+2u_{i}^{T}z_{i}))$
(19)

By definitions of $M_{1}$ and $M_{2}$,

$\displaystyle u_{i}^{T}M_{i}w=(\mu_{i}^{T}w)(\mathds{1}^{T}u_{i})$
$\displaystyle\|M_{i}w\|^{2}=\frac{n}{2}(\mu_{i}^{T}w)^{2}$

Consider the inner optimization of (19):

$\displaystyle\min_{w,u}\mathcal{L}(u)+\lambda
f(w)+\sum^{2}_{i=1}\beta_{i}(w^{T}\Sigma^{\frac{1}{2}}_{i}g_{i}+\frac{1}{2\tau_{i}}(\frac{n}{2}\|\Sigma^{\frac{1}{2}}_{i}w\|^{2}+\frac{n}{2}(\mu_{i}^{T}w)^{2}+\frac{n}{2}+\|u_{i}\|^{2}-$
$\displaystyle-2\|\Sigma^{\frac{1}{2}}_{i}w\|h_{i}^{T}u_{i}-n(1-2c)\mu_{i}^{T}w-2(\mu_{i}^{T}w)(\mathds{1}^{T}u_{i})+2u_{i}^{T}z_{i})$
(20)

We focus on optimizing over $u$ first:

$\displaystyle\min_{u}\mathcal{L}(u)+\sum_{i=1}^{2}\frac{\beta_{i}}{2\tau_{i}}(\|u_{i}\|^{2}+2\|\Sigma^{\frac{1}{2}}_{i}w\|h_{i}^{T}u_{i}-2(\mu_{i}^{T}w)(\mathds{1}^{T}u_{i})+2z_{i}^{T}u_{i})$

Assuming $\mathcal{L}$ is separable, we complete the squares and arrive at:

$\displaystyle\min_{u}\sum^{2}_{i=1}\mathcal{L}(u_{i})+\frac{\beta_{i}}{2\tau_{i}}(\|(\mu_{i}^{T}w)\mathds{1}-h_{i}\|\Sigma^{\frac{1}{2}}_{i}w\|-z_{i}-u_{i}\|^{2})$

Noting that the expression above is the Moreau Envelope of $\cal L$ by the
definition 9:

$\displaystyle\min_{\tau_{1},\tau_{2}\geq 0}\max_{\beta_{1},\beta_{2}\geq
0}\sum_{i=1}^{2}\beta_{i}\frac{\tau_{i}}{2}+\min_{w}\lambda
f(w)+\sum^{2}_{i=1}\beta_{i}w^{T}\Sigma^{\frac{1}{2}}_{i}g_{i}+\mathcal{M}_{\frac{\tau_{i}}{\beta_{i}}\
\mathcal{L}}\left((\mu_{i}^{T}w)\mathds{1}-h_{i}\|\Sigma^{\frac{1}{2}}_{i}w\|-z_{i}\right)$

Let $p_{i}=\Sigma^{\frac{1}{2}}_{i}w$ and $\gamma_{i}=\mu_{i}^{T}w$, then (20)
can be rewritten as:

$\displaystyle\min_{w,p,\gamma}\max_{\nu,\eta}\lambda
f(w)+\sum^{2}_{i=1}\beta_{i}p_{i}^{T}g_{i}+\mathcal{M}_{\frac{\tau_{i}}{\beta_{i}}\
\mathcal{L}}\left(\gamma_{i}\mathds{1}-h_{i}\|p_{i}\|-z_{i}\right)+\nu_{i}^{T}(\Sigma^{\frac{1}{2}}_{i}w-p_{i})+\eta_{i}(\mu_{i}^{T}w-\gamma_{i})$

Performing the optimization over the direction of $p_{i}$ and denoting
$\theta_{i}=\|p_{i}\|$:

$\displaystyle\min_{w,\theta_{i}\geq 0,\gamma}\max_{\nu,\eta}\lambda
f(w)+\sum^{2}_{i=1}-\theta_{i}\|\beta_{i}g_{i}-\nu_{i}\|+\mathcal{M}_{\frac{\tau_{i}}{\beta_{i}}\
\mathcal{L}}\left(\gamma_{i}\mathds{1}-\theta_{i}h_{i}-z_{i}\right)+\nu_{i}^{T}\Sigma^{\frac{1}{2}}_{i}w+\eta_{i}(\mu_{i}^{T}w-\gamma_{i})$

Applying the square root trick again:

$\displaystyle\min_{w,\theta_{i}\geq 0,\gamma,\zeta_{i}\geq
0}\max_{\nu,\eta}\lambda
f(w)+\sum^{2}_{i=1}\mathcal{M}_{\frac{\tau_{i}}{\beta_{i}}\
\mathcal{L}}\left(\gamma_{i}\mathds{1}-\theta_{i}h_{i}-z_{i}\right)-\frac{\theta_{i}\zeta_{i}}{2}-\frac{\theta_{i}}{2\zeta_{i}}\|\beta_{i}g_{i}-\nu_{i}\|^{2}+$
$\displaystyle+\nu_{i}^{T}\Sigma^{\frac{1}{2}}_{i}w+\eta_{i}(\mu_{i}^{T}w-\gamma_{i})$

Optimizing over $\nu_{i}$ yields:

$\displaystyle\min_{w,\theta_{i}\geq 0,\gamma,\zeta_{i}\geq
0}\max_{\eta}\lambda
f(w)+\sum^{2}_{i=1}\mathcal{M}_{\frac{\tau_{i}}{\beta_{i}}\
\mathcal{L}}\left(\gamma_{i}\mathds{1}-\theta_{i}h_{i}-z_{i}\right)-\frac{\theta_{i}\zeta_{i}}{2}-\frac{d\theta_{i}\beta_{i}^{2}}{2\zeta_{i}}$
$\displaystyle+\frac{\theta_{i}}{2\zeta_{i}}\|\beta_{i}g_{i}-\frac{\zeta_{i}}{\theta_{i}}\Sigma^{\frac{1}{2}}_{i}w\|^{2}+\eta_{i}(\mu_{i}^{T}w-\gamma_{i})$

Optimize over $w$:

$\displaystyle\min_{w}\lambda
f(w)+\sum^{2}_{i=1}\frac{\theta_{i}}{2\zeta_{i}}\|\beta_{i}g_{i}-\frac{\zeta_{i}}{\theta_{i}}\Sigma^{\frac{1}{2}}_{i}w\|^{2}+\eta_{i}\mu_{i}^{T}w$

Opening up the norm:

$\displaystyle\min_{w}\lambda
f(w)+\frac{1}{2}w^{T}\left(\sum_{i=1}^{2}\frac{\zeta_{i}}{\theta_{i}}\Sigma_{i}\right)w-w^{T}\left(\sum_{i=1}^{2}\beta_{i}\Sigma_{i}^{\frac{1}{2}}g_{i}-\eta_{i}\mu_{i}\right)+\frac{d\theta_{i}\beta_{i}^{2}}{2\zeta_{i}}$

Define $\Sigma=\sum_{i=1}^{2}\frac{\zeta_{i}}{\theta_{i}}\Sigma_{i}$ and
vector
$x=\sum_{i=1}^{2}\beta_{i}\Sigma_{i}^{\frac{1}{2}}g_{i}-\eta_{i}\mu_{i}$, then
the objective above can written in terms of the Moreau Envelope as:

$\displaystyle\min_{w}\lambda\mathcal{M}_{\lambda\
f(\Sigma^{-\frac{1}{2}})}\left(\Sigma^{-\frac{1}{2}}x\right)-\frac{x^{T}\Sigma^{-1}x}{2}+\frac{d\theta_{i}\beta_{i}^{2}}{2\zeta_{i}}$

Plugging everything back into (19), we derive:

$\displaystyle\min_{\tau_{i}\geq 0,\theta_{i}\geq 0,\zeta_{i}\geq
0,\gamma_{i}}\max_{\beta_{i}\geq 0,\eta_{i}}\lambda\mathcal{M}_{\lambda\
f(\Sigma^{-\frac{1}{2}})}\left(\Sigma^{-\frac{1}{2}}x\right)-\frac{x^{T}\Sigma^{-1}x}{2}+\sum^{2}_{i=1}\beta_{i}\frac{\tau_{i}}{2}+$
$\displaystyle+\mathcal{M}_{\frac{\tau_{i}}{\beta_{i}}\
\mathcal{L}}\left(\gamma_{i}\mathds{1}-\theta_{i}h_{i}-z_{i}\right)-\frac{\theta_{i}\zeta_{i}}{2}-\eta_{i}\gamma_{i}$

∎

####  C.2.2 Proof of Theorem 7

###### Proof.

Under the assumptions of Theorem 7, the objective (6) turns into the
following:

$\displaystyle\min_{w}\|(A+M)w-z\|^{2}+\lambda\|w\|^{2}$

Taking the Fenchel dual of the first term we obtain:

$\displaystyle\min_{w}\max_{v_{1},v_{2}}v_{1}^{T}A_{1}\Sigma^{\frac{1}{2}}_{1}w+v_{2}^{T}A_{2}\Sigma^{\frac{1}{2}}_{2}w+v_{1}^{T}M_{1}w+v_{2}^{T}M_{2}w-v_{1}^{T}z_{1}-v_{2}^{T}z_{2}-\frac{1}{4}\|v_{1}\|^{2}-\frac{1}{4}\|v_{2}\|^{2}+\lambda\|w\|^{2}$

Applying Theorem 4 to the objective above:

$\displaystyle\min_{w}\max_{v_{1},v_{2}}\lambda\|w\|^{2}+\sum^{2}_{i=1}\|v_{i}\|w^{T}\Sigma^{\frac{1}{2}}_{i}g_{i}+v_{i}^{T}h_{i}\|\Sigma^{\frac{1}{2}}_{i}w\|+v_{i}^{T}M_{i}w-v_{i}^{T}z_{i}-\frac{1}{4}\|v_{i}\|^{2}$

Optimizing over the direction of $v_{i}$ yields:

$\displaystyle\min_{w}\max_{\beta_{1},\beta_{2}\geq
0}\lambda\|w\|^{2}+\sum^{2}_{i=1}\beta_{i}w^{T}\Sigma^{\frac{1}{2}}_{i}g_{i}+\beta_{i}\|M_{i}w+h_{i}\|\Sigma^{\frac{1}{2}}_{i}w\|-z_{i}\|-\frac{\beta_{i}^{2}}{4}$

Using the square root trick and definition of $M_{i}$ and $z_{i}$:

$\displaystyle\min_{w}\max_{\beta_{1},\beta_{2}\geq
0}\min_{\tau_{1},\tau_{2}\geq
0}\lambda\|w\|^{2}+\sum^{2}_{i=1}\beta_{i}w^{T}\Sigma^{\frac{1}{2}}_{i}g_{i}+\frac{\beta_{i}\tau_{i}}{2}+\frac{\beta_{i}}{2\tau_{i}}(\|M_{i}w-z_{i}\|^{2}+\frac{n}{2}w^{T}\Sigma_{i}w)-\frac{\beta_{i}^{2}}{4}$

Introducing $\gamma_{i}$’s:

$\displaystyle\min_{w}\max_{\beta_{1},\beta_{2}\geq
0,\gamma_{1},\gamma_{2}}\min_{\tau_{1},\tau_{2}\geq
0}\lambda\|w\|^{2}+\sum^{2}_{i=1}\beta_{i}w^{T}\Sigma^{\frac{1}{2}}_{i}g_{i}+\frac{\beta_{i}\tau_{i}}{2}+\frac{n\beta_{i}}{4\tau_{i}}(\gamma_{i}(\mu_{i}^{T}w-(-1)^{i+1})-\frac{\gamma_{i}^{2}}{4}+\|\Sigma^{\frac{1}{2}}_{i}w\|^{2})-\frac{\beta_{i}^{2}}{4}$

Changing orders of optimization:

$\displaystyle\min_{\tau_{1},\tau_{2}\geq 0}\max_{\beta_{1},\beta_{2}\geq
0,\gamma_{1},\gamma_{2}}\sum_{i=1}^{2}\frac{\beta_{i}\tau_{i}}{2}-\frac{n\beta_{i}\gamma_{i}^{2}}{16\tau_{i}}-\frac{n\beta_{i}\gamma_{i}(-1)^{i+1}}{4\tau_{i}}-\frac{\beta_{i}^{2}}{4}+$
$\displaystyle+\min_{w}\left[\sum_{i=1}^{2}\beta_{i}\Sigma^{\frac{1}{2}}_{i}g_{i}+\frac{n\beta_{i}\gamma_{i}}{4\tau_{i}}\mu_{i}\right]^{T}w+w^{T}(\lambda
I+\frac{n\beta_{1}}{4\tau_{1}}\Sigma_{1}+\frac{n\beta_{2}}{4\tau_{2}}\Sigma_{2})w$

Optimizing over $w$ we are left with the following:

$\displaystyle\min_{\tau_{1},\tau_{2}\geq 0}\max_{\beta_{1},\beta_{2}\geq
0,\gamma_{1},\gamma_{2}}-\frac{1}{4}\left[\sum_{i=1}^{2}\beta_{i}\Sigma^{\frac{1}{2}}_{i}g_{i}+\frac{n\beta_{i}\gamma_{i}}{4\tau_{i}}\mu_{i}\right]^{T}(\lambda
I+\frac{n\beta_{1}}{4\tau_{1}}\Sigma_{1}+\frac{n\beta_{2}}{4\tau_{2}}\Sigma_{2})^{-1}\left[\sum_{i=1}^{2}\beta_{i}\Sigma^{\frac{1}{2}}_{i}g_{i}+\frac{n\beta_{i}\gamma_{i}}{4\tau_{i}}\mu_{i}\right]+$
$\displaystyle+\sum_{i=1}^{2}\frac{\beta_{i}\tau_{i}}{2}-\frac{n\beta_{i}\gamma_{i}^{2}}{16\tau_{i}}-\frac{n\beta_{i}\gamma_{i}(-1)^{i+1}}{4\tau_{i}}-\frac{\beta_{i}^{2}}{4}$
(21)

Due to our assumptions on $\mu_{i}$’s we have:

$\displaystyle\sum_{i=1}^{2}\beta_{i}\Sigma^{\frac{1}{2}}_{i}g_{i}+\frac{n\beta_{i}\gamma_{i}}{4\tau_{i}}\mu_{i}\sim\mathcal{N}(0,\frac{n^{2}\beta_{1}\beta_{2}\gamma_{1}\gamma_{2}}{8\tau_{1}\tau_{2}}rI+\sum_{i=1}^{2}\beta_{i}^{2}\Sigma_{i}+\frac{n^{2}\beta_{i}^{2}\gamma_{i}^{2}}{16\tau_{i}^{2}}I)$

In other words,

$\displaystyle\sum_{i=1}^{2}\beta_{i}\Sigma^{\frac{1}{2}}_{i}g_{i}+\frac{n\beta_{i}\gamma_{i}}{4\tau_{i}}\mu_{i}\sim(\frac{n^{2}\beta_{1}\beta_{2}\gamma_{1}\gamma_{2}}{8\tau_{1}\tau_{2}}rI+\sum_{i=1}^{2}\beta_{i}^{2}\Sigma_{i}+\frac{n^{2}\beta_{i}^{2}\gamma_{i}^{2}}{16\tau_{i}^{2}}I)^{\frac{1}{2}}G\text{
where }G\sim\mathcal{N}(0,I)$

Simplify the first term of (21) via leveraging the corresponding Gaussian
concentration:

$\displaystyle\left[\sum_{i=1}^{2}\beta_{i}\Sigma^{\frac{1}{2}}_{i}g_{i}+\frac{n\beta_{i}\gamma_{i}}{4\tau_{i}}\mu_{i}\right]^{T}(\lambda
I+\frac{n\beta_{1}}{4\tau_{1}}\Sigma_{1}+\frac{n\beta_{2}}{4\tau_{2}}\Sigma_{2})^{-1}\left[\sum_{i=1}^{2}\beta_{i}\Sigma^{\frac{1}{2}}_{i}g_{i}+\frac{n\beta_{i}\gamma_{i}}{4\tau_{i}}\mu_{i}\right]=$
$\displaystyle=\text{Tr}\left(\mathbb{E}\left[\sum_{i=1}^{2}\beta_{i}\Sigma^{\frac{1}{2}}_{i}g_{i}+\frac{n\beta_{i}\gamma_{i}}{4\tau_{i}}\mu_{i}\right]^{T}(\lambda
I+\frac{n\beta_{1}}{4\tau_{1}}\Sigma_{1}+\frac{n\beta_{2}}{4\tau_{2}}\Sigma_{2})^{-1}\left[\sum_{i=1}^{2}\beta_{i}\Sigma^{\frac{1}{2}}_{i}g_{i}+\frac{n\beta_{i}\gamma_{i}}{4\tau_{i}}\mu_{i}\right]\right)=$
$\displaystyle=\text{Tr}\left(\mathbb{E}\left[\sum_{i=1}^{2}\beta_{i}\Sigma^{\frac{1}{2}}_{i}g_{i}+\frac{n\beta_{i}\gamma_{i}}{4\tau_{i}}\mu_{i}\right]\left[\sum_{i=1}^{2}\beta_{i}\Sigma^{\frac{1}{2}}_{i}g_{i}+\frac{n\beta_{i}\gamma_{i}}{4\tau_{i}}\mu_{i}\right]^{T}(\lambda
I+\frac{n\beta_{1}}{4\tau_{1}}\Sigma_{1}+\frac{n\beta_{2}}{4\tau_{2}}\Sigma_{2})^{-1}\right)=$
$\displaystyle=\text{Tr}\left((\frac{n^{2}\beta_{1}\beta_{2}\gamma_{1}\gamma_{2}}{8\tau_{1}\tau_{2}}rI+\sum_{i=1}^{2}\beta_{i}^{2}\Sigma_{i}+\frac{n^{2}\beta_{i}^{2}\gamma_{i}^{2}}{16\tau_{i}^{2}}I)(\lambda
I+\frac{n\beta_{1}}{4\tau_{1}}\Sigma_{1}+\frac{n\beta_{2}}{4\tau_{2}}\Sigma_{2})^{-1}\right)=$
$\displaystyle=\text{Tr}\left((\lambda
I+\frac{n\beta_{1}}{4\tau_{1}}\Sigma_{1}+\frac{n\beta_{2}}{4\tau_{2}}\Sigma_{2})^{-1}(\frac{n^{2}\beta_{1}\beta_{2}\gamma_{1}\gamma_{2}}{8\tau_{1}\tau_{2}}rI+\sum_{i=1}^{2}\beta_{i}^{2}\Sigma_{i}+\frac{n^{2}\beta_{i}^{2}\gamma_{i}^{2}}{16\tau_{i}^{2}}I)\right)$

Plugging everything back into (21) we deduce:

$\displaystyle\min_{\tau_{1},\tau_{2}\geq 0}\max_{\beta_{1},\beta_{2}\geq
0,\gamma_{1},\gamma_{2}}-\frac{1}{4}\text{Tr}\left((\lambda
I+\frac{n\beta_{1}}{4\tau_{1}}\Sigma_{1}+\frac{n\beta_{2}}{4\tau_{2}}\Sigma_{2})^{-1}(\frac{n^{2}\beta_{1}\beta_{2}\gamma_{1}\gamma_{2}}{8\tau_{1}\tau_{2}}rI+\sum_{i=1}^{2}\beta_{i}^{2}\Sigma_{i}+\frac{n^{2}\beta_{i}^{2}\gamma_{i}^{2}}{16\tau_{i}^{2}}I)\right)+$
$\displaystyle+\sum_{i=1}^{2}\frac{\beta_{i}\tau_{i}}{2}-\frac{n\beta_{i}\gamma_{i}^{2}}{16\tau_{i}}-\frac{n\beta_{i}\gamma_{i}(-1)^{i+1}}{4\tau_{i}}-\frac{\beta_{i}^{2}}{4}$

∎

####  C.2.3 Classification Error

An attentive reader might have noticed that we held up the classification
error derivations to this point. Recall that the classification error for a
weight $\hat{w}$ and a general GMM is given by:

$E(\hat{w})=\frac{1}{2}Q\left(\frac{\mu_{1}^{T}\hat{w}}{\sqrt{\hat{w}^{T}\Sigma_{1}\hat{w}}}\right)+\frac{1}{2}Q\left(-\frac{\mu_{2}^{T}\hat{w}}{\sqrt{\hat{w}^{T}\Sigma_{2}\hat{w}}}\right)$

The proof is a straightforward calculation but we provide it here for
completeness:

###### Proof.

Note that

$E(\hat{w})=\frac{1}{2}\mathbb{P}_{x\sim\mathcal{N}(\mu_{1},\Sigma_{1})}(\hat{w}^{T}x<0)+\frac{1}{2}\mathbb{P}_{x\sim\mathcal{N}(\mu_{2},\Sigma_{2})}(\hat{w}^{T}x>0)$

Subtracting the means from the sample point we have: $x=\mu_{1}+\eta_{1}$ for
$x\sim\mathcal{N}(\mu_{1},\Sigma_{1})$ and $x=\mu_{2}+\eta_{2}$ for
$x\sim\mathcal{N}(\mu_{2},\Sigma_{2})$ we obtain:

$E(\hat{w})=\frac{1}{2}\mathbb{P}_{\eta_{1}\sim\mathcal{N}(0,\Sigma_{1})}(\hat{w}^{T}y_{1}<-\mu_{1}^{T}\hat{w})+\frac{1}{2}\mathbb{P}_{\eta_{2}\sim\mathcal{N}(0,\Sigma_{2})}(\hat{w}^{T}\eta_{2}>-\mu_{2}^{T}\hat{w})$

Noticing that $\hat{w}^{T}\eta_{1}\sim\mathcal{N}(0,w^{T}\Sigma_{1}w)$ and
$\hat{w}^{T}\eta_{2}\sim\mathcal{N}(0,w^{T}\Sigma_{2}w)$ we derive:

$\displaystyle
E(\hat{w})=\frac{1}{2}\mathbb{P}_{\zeta_{1}\sim\mathcal{N}(0,\hat{w}^{T}\Sigma_{1}\hat{w})}(\zeta_{1}<-\mu_{1}^{T}\hat{w})+\frac{1}{2}\mathbb{P}_{\zeta_{2}\sim\mathcal{N}(0,\hat{w}^{T}\Sigma_{2}\hat{w})}(\zeta_{2}>-\mu_{2}^{T}\hat{w})=$
$\displaystyle=\frac{1}{2}\mathbb{P}_{\xi_{1}\sim\mathcal{N}(0,1)}(\xi_{1}<-\frac{\mu_{1}^{T}\hat{w}}{\sqrt{\hat{w}^{T}\Sigma_{1}\hat{w}}})+\frac{1}{2}\mathbb{P}_{\xi_{2}\sim\mathcal{N}(0,1)}(\xi_{2}>-\frac{\mu_{2}^{T}\hat{w}}{\sqrt{\hat{w}^{T}\Sigma_{2}\hat{w}}})=$
$\displaystyle=\frac{1}{2}Q\left(\frac{\mu_{1}^{T}\hat{w}}{\sqrt{\hat{w}^{T}\Sigma_{1}\hat{w}}}\right)+\frac{1}{2}Q\left(-\frac{\mu_{2}^{T}\hat{w}}{\sqrt{\hat{w}^{T}\Sigma_{2}\hat{w}}}\right)$

∎

The classification error part for Theorem 6 follows immediately then by the
definitions of $\gamma_{i}$ and $\Theta_{i}$ for that case. We now proceed to
derive the expressions for the classification error for Theorem 7 and
Corollary 2. Note that by definition

$\displaystyle\gamma_{i}=2(\mu_{i}^{T}w-(-1)^{i+1})$
$\displaystyle\tau_{i}^{2}=\frac{n}{2}(\frac{\gamma_{i}^{2}}{4}+\|\Sigma^{\frac{1}{2}}_{i}w\|^{2})=\frac{n}{2}(\frac{\gamma_{i}^{2}}{4}+w^{T}\Sigma_{i}w)$

Therefore:

$\displaystyle\frac{1}{2}Q\left(\frac{\mu_{1}^{T}w}{\sqrt{w^{T}\Sigma_{1}w}}\right)+\frac{1}{2}Q\left(-\frac{\mu_{2}^{T}w}{\sqrt{w^{T}\Sigma_{2}w}}\right)=\frac{1}{2}Q\left(\frac{\gamma_{1}+2}{\sqrt{\frac{8}{n}\tau_{1}^{2}-\gamma_{1}^{2}}}\right)+\frac{1}{2}Q\left(\frac{-\gamma_{2}+2}{\sqrt{\frac{8}{n}\tau_{2}^{2}-\gamma_{2}^{2}}}\right)$

###  C.3 Proof of Corollary 2

###### Proof.

Recall the model:

$\displaystyle\Sigma_{1}=\sigma_{1}^{2}I+\nu_{1}\nu_{1}^{T}$
$\displaystyle\Sigma_{2}=\sigma_{2}^{2}I+\nu_{2}\nu_{2}^{T}$
$\displaystyle\text{ where }\nu_{1},\nu_{2}\in\mathcal{N}(0,\sigma^{2}I)$

Denote the space spanned by $\nu_{1}$ and $\nu_{2}$ by $V$ and also denote

$T=\lambda
I+\frac{n\beta_{1}}{4\tau_{1}}\Sigma_{1}+\frac{n\beta_{2}}{4\tau_{2}}\Sigma_{2}$

Note that both $V$ and $V^{\perp}$ form invariant subspaces of the operator
$T$. Also, since we are interested in the asymptotic regime $d\to\infty$, we
can take $\|\nu_{1}\|=\|\nu_{2}\|\approx\sigma^{2}d$ and
$\nu_{1}^{T}\nu_{2}\approx 0$ due to the Gaussian concentration. Therefore, we
can write:

$\displaystyle
T\nu_{1}=(\lambda+\frac{n\beta_{1}}{4\tau_{1}}(\sigma_{1}^{2}+\|\nu_{1}\|^{2})+\frac{n\beta_{2}}{4\tau_{2}}\sigma_{2}^{2})\nu_{1}$
$\displaystyle
T\nu_{2}=(\lambda+\frac{n\beta_{1}}{4\tau_{1}}\sigma_{1}^{2}+\frac{n\beta_{2}}{4\tau_{2}}(\sigma_{2}^{2}+\|\nu_{2}\|^{2}))\nu_{2}$

Decomposing $\mathbb{R}^{d}=V^{\perp}\oplus\nu_{1}\oplus\nu_{2}$ and using
that for any operator $F$ one in this case has
$\text{Tr}F=\text{Tr}F_{|V^{\perp}}+\text{Tr}F_{|\nu_{1}}+\text{Tr}F_{|\nu_{2}}$,
we derive:

$\displaystyle\text{Tr}\left[(\lambda
I+\frac{n\beta_{1}}{4\tau_{1}}\Sigma_{1}+\frac{n\beta_{2}}{4\tau_{2}}\Sigma_{2})^{-1}(\frac{n^{2}\beta_{1}\beta_{2}\gamma_{1}\gamma_{2}}{8\tau_{1}\tau_{2}}rI+\sum_{i=1}^{2}\beta_{i}^{2}\Sigma_{i}+\frac{n^{2}\beta_{i}^{2}\gamma_{i}^{2}}{16\tau_{i}^{2}}I)\right]=$
$\displaystyle=\text{Tr}\left[(\lambda+\frac{n\beta_{1}}{4\tau_{1}}\sigma^{2}_{1}+\frac{n\beta_{2}}{4\tau_{2}}\sigma^{2}_{2})^{-1}(\frac{n^{2}\beta_{1}\beta_{2}\gamma_{1}\gamma_{2}}{8\tau_{1}\tau_{2}}r+\sum_{i=1}^{2}\beta_{i}^{2}\sigma^{2}_{i}+\frac{n^{2}\beta_{i}^{2}\gamma_{i}^{2}}{16\tau_{i}^{2}})I\right]_{|V_{\perp}}+$
$\displaystyle+(\lambda+\frac{n\beta_{1}}{4\tau_{1}}(\sigma^{2}_{1}+\sigma^{2}d)+\frac{n\beta_{2}}{4\tau_{2}}\sigma^{2}_{2})^{-1}(\frac{n^{2}\beta_{1}\beta_{2}\gamma_{1}\gamma_{2}}{8\tau_{1}\tau_{2}}r+\beta_{1}^{2}(\sigma^{2}_{1}+\sigma^{2}d)+\beta_{2}^{2}\sigma^{2}_{2}+\frac{n^{2}\beta_{i}^{2}\gamma_{i}^{2}}{16\tau_{i}^{2}})+$
$\displaystyle+(\lambda+\frac{n\beta_{1}}{4\tau_{1}}\sigma^{2}_{1}+\frac{n\beta_{2}}{4\tau_{2}}(\sigma^{2}_{2}+\sigma^{2}d))^{-1}(\frac{n^{2}\beta_{1}\beta_{2}\gamma_{1}\gamma_{2}}{8\tau_{1}\tau_{2}}r+\beta_{1}^{2}\sigma^{2}_{1}+\beta_{2}^{2}(\sigma^{2}_{2}+\sigma^{2}d)+\frac{n^{2}\beta_{i}^{2}\gamma_{i}^{2}}{16\tau_{i}^{2}})=$
$\displaystyle=(d-2)(\lambda+\frac{n\beta_{1}}{4\tau_{1}}\sigma^{2}_{1}+\frac{n\beta_{2}}{4\tau_{2}}\sigma^{2}_{2})^{-1}(\frac{n^{2}\beta_{1}\beta_{2}\gamma_{1}\gamma_{2}}{8\tau_{1}\tau_{2}}r+\sum_{i=1}^{2}\beta_{i}^{2}\sigma^{2}_{i}+\frac{n^{2}\beta_{i}^{2}\gamma_{i}^{2}}{16\tau_{i}^{2}})+$
$\displaystyle+(\lambda+\frac{n\beta_{1}}{4\tau_{1}}(\sigma^{2}_{1}+\sigma^{2}d)+\frac{n\beta_{2}}{4\tau_{2}}\sigma^{2}_{2})^{-1}(\frac{n^{2}\beta_{1}\beta_{2}\gamma_{1}\gamma_{2}}{8\tau_{1}\tau_{2}}r+\beta_{1}^{2}\sigma^{2}d+\sum_{i=1}^{2}\beta_{i}^{2}\sigma^{2}_{i}+\frac{n^{2}\beta_{i}^{2}\gamma_{i}^{2}}{16\tau_{i}^{2}})$
$\displaystyle+(\lambda+\frac{n\beta_{1}}{4\tau_{1}}\sigma^{2}_{1}+\frac{n\beta_{2}}{4\tau_{2}}(\sigma^{2}_{2}+\sigma^{2}d))^{-1}(\frac{n^{2}\beta_{1}\beta_{2}\gamma_{1}\gamma_{2}}{8\tau_{1}\tau_{2}}r+\beta_{2}^{2}\sigma^{2}d+\sum_{i=1}^{2}\beta_{i}^{2}\sigma^{2}_{i}+\frac{n^{2}\beta_{i}^{2}\gamma_{i}^{2}}{16\tau_{i}^{2}})$

∎

######  Remark 2.

One might ask where exactly we used the fact that $\nu_{1}$ and $\nu_{2}$ are
independent from $\mu_{1}$ and $\mu_{2}$ in the derivations above. The answer
is that we cannot take the expectation over $\mu_{1}$ and $\mu_{2}$ first to
get the expression with the trace we used if $\nu_{1}$ and $\nu_{2}$ depend on
$\mu_{1}$ and $\mu_{2}$.

## References

  * Agrawal et al., (2018) Agrawal, A., Verschueren, R., Diamond, S., and Boyd, S. (2018).  A rewriting system for convex optimization problems.  Journal of Control and Decision, 5(1):42–60.
  * Akhtiamov et al., (2023) Akhtiamov, D., Ghane, R., and Hassibi, B. (2023).  Regularized linear regression for binary classification.  arXiv preprint arXiv:2311.02270.
  * Aolaritei et al., (2023) Aolaritei, L., Shafieezadeh-Abadeh, S., and Dörfler, F. (2023).  The performance of wasserstein distributionally robust m-estimators in high dimensions.  arXiv:2206.13269.
  * Boucheron et al., (2013) Boucheron, S., Lugosi, G., and Massart, P. (2013).  Concentration Inequalities - A Nonasymptotic Theory of Independence.  Oxford University Press.
  * Diamond and Boyd, (2016) Diamond, S. and Boyd, S. (2016).  CVXPY: A Python-embedded modeling language for convex optimization.  Journal of Machine Learning Research, 17(83):1–5.
  * Gordon, (1985) Gordon, Y. (1985).  Some inequalities for gaussian processes and applications.  Israel Journal of Mathematics, 50:265–289.
  * Gordon, (1988) Gordon, Y. (1988).  On Milman’s inequality and random subspaces which escape through a mesh in $\mathbb{R}^{n}$.  Geometric Aspects of Functional Analysis, pages 84–106.
  * Javanmard and Soltanolkotabi, (2022) Javanmard, A. and Soltanolkotabi, M. (2022).  Precise statistical analysis of classification accuracies for adversarial training.  The Annals of Statistics, 50(4):2127–2156.
  * Loureiro et al., (2021) Loureiro, B., Sicuro, G., Gerbelot, C., Pacco, A., Krzakala, F., and Zdeborová, L. (2021).  Learning gaussian mixtures with generalized linear models: Precise asymptotics in high-dimensions.  In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W., editors, Advances in Neural Information Processing Systems, volume 34, pages 10144–10157. Curran Associates, Inc.
  * Mignacco et al., (2020) Mignacco, F., Krzakala, F., Lu, Y., Urbani, P., and Zdeborova, L. (2020).  The role of regularization in classification of high-dimensional noisy Gaussian mixture.  In III, H. D. and Singh, A., editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 6874–6883. PMLR.
  * Montanari et al., (2019) Montanari, A., Ruan, F., Sohn, Y., and Yan, J. (2019).  The generalization error of max-margin linear classifiers: High-dimensional asymptotics in the overparametrized regime.  arXiv preprint arXiv:1911.01544.
  * Papaspiliopoulos, (2020) Papaspiliopoulos, O. (2020).  High-dimensional probability: An introduction with applications in data science.
  * Salehi et al., (2019) Salehi, F., Abbasi, E., and Hassibi, B. (2019).  The impact of regularization on high-dimensional logistic regression.  Advances in Neural Information Processing Systems, 32.
  * Salehi et al., (2020) Salehi, F., Abbasi, E., and Hassibi, B. (2020).  The performance analysis of generalized margin maximizers on separable data.  In International conference on machine learning, pages 8417–8426. PMLR.
  * Slepian, (1962) Slepian, D. (1962).  The one-sided barrier problem for gaussian noise.  Bell System Technical Journal, 41(2):463–501.
  * Stojnic, (2013) Stojnic, M. (2013).  A framework to characterize performance of lasso algorithms.  arXiv preprint arXiv:1303.7291.
  * Thrampoulidis, (2016) Thrampoulidis, C. (2016).  Recovering structured signals in high dimensions via non-smooth convex optimization: Precise performance analysis.  PhD thesis, California Institute of Technology.
  * Thrampoulidis et al., (2018) Thrampoulidis, C., Abbasi, E., and Hassibi, B. (2018).  Precise error analysis of regularized $m$ -estimators in high dimensions.  IEEE Transactions on Information Theory, 64(8):5592–5628.
  * Thrampoulidis et al., (2014) Thrampoulidis, C., Oymak, S., and Hassibi, B. (2014).  The gaussian min-max theorem in the presence of convexity.  http://arxiv.org/abs/1408.4837v2.
  * Thrampoulidis et al., (2015) Thrampoulidis, C., Oymak, S., and Hassibi, B. (2015).  Regularized linear regression: A precise analysis of the estimation error.  In Conference on Learning Theory, pages 1683–1709. PMLR.
  * Thrampoulidis et al., (2020) Thrampoulidis, C., Oymak, S., and Soltanolkotabi, M. (2020).  Theoretical insights into multiclass classification: A high-dimensional asymptotic view.  Advances in Neural Information Processing Systems, 33:8907–8920.