# Regularized Linear Regression for Binary Classification

Danil Akhtiamov∗
Department of Computing and Mathematical Sciences
California Institute of Technology
Pasadena, CA 91125
<EMAIL_ADDRESS>
&Reza Ghane∗
Department of Electrical Engineering
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

Regularized linear regression is a promising approach for binary
classification problems in which the training set has noisy labels since the
regularization term can help to avoid interpolating the mislabeled data
points. In this paper we provide a systematic study of the effects of the
regularization strength on the performance of linear classifiers that are
trained to solve binary classification problems by minimizing a regularized
least-squares objective. We consider the over-parametrized regime and assume
that the classes are generated from a Gaussian Mixture Model (GMM) where a
fraction $c<\frac{1}{2}$ of the training data is mislabeled. Under these
assumptions, we rigorously analyze the classification errors resulting from
the application of ridge, $\ell_{1}$, and $\ell_{\infty}$ regression. In
particular, we demonstrate that ridge regression invariably improves the
classification error. We prove that $\ell_{1}$ regularization induces sparsity
and observe that in many cases one can sparsify the solution by up to two
orders of magnitude without any considerable loss of performance, even though
the GMM has no underlying sparsity structure. For $\ell_{\infty}$
regularization we show that, for large enough regularization strength, the
optimal weights concentrate around two values of opposite sign. We observe
that in many cases the corresponding "compression" of each weight to a single
bit leads to very little loss in performance. These latter observations can
have significant practical ramifications.

**footnotetext: Equal contribution

##  1 INTRODUCTION

As the usage of machine learning models becomes more prevalent, the need for
efficiently storing these models and for guaranteeing their performance in the
face of noisy training data becomes increasingly vital. With the advent of
LLMs, which are comprised of many billions of weights, the necessity for
reliable compression schemes becomes ever more critical. Thus, the question is
raised, are there methods that allow us to compress the weights of a deep
neural net without compromising a lot on the performance? In this paper, we
would like to take baby steps towards addressing this question via the
analysis of the toy problem of regularized linear regression for binary
classification. Regularization can be used to avoid fitting corrupted data,
thereby improving performance, as well as to favor solutions with desired
properties, such as sparsity or compressibility. Through theory, intuitive
arguments, and numerical simulations, we demonstrate that regularization can
help the generalization performance on noise-corrupted data sets, as well as
reduce the number of model parameters by orders of magnitude without
significant loss in performance.

##  2 RELATED WORKS AND OUR CONTRIBUTION

There has been a recent surge of results in binary classification that provide
a sharp analysis of a variety of methods tailored to different models (see,
e.g., Thrampoulidis et al., (2018, 2020); Huang, (2017); Candès and Sur,
(2018); Sur and Candès, (2019); Kammoun and Alouini, (2020); Salehi et al.,
(2019); Taheri et al., (2020); Deng et al., (2019); Montanari et al., 2019a ;
Mignacco et al., 2020b ; Lolas, (2020) and the references therein). These
works typically pose the over-parameterized binary classification problem as
an optimization problem and employ either the Convex Gaussian Min-max Theorem
(CGMT) Thrampoulidis et al., 2015b ; Thrampoulidis et al., (2018); Stojnic,
(2013); Gordon, (1985); Loureiro et al., (2021) or the Approximate Message
Passing (AMP) (see, e.g, Donoho et al., (2009); Bayati and Montanari, (2011);
Javanmard and Montanari, (2013)) approach to obtain formulas for the
generalization error that involve solutions to a system of non-linear
equations (in a small number of variables) that often do not admit closed-form
expressions. These results follow a long line of work that deals with
obtaining sharp high-dimensional asymptotics for convex optimization-based
estimators. Most of the papers referred to above use some form of linear,
logistic, or max-margin optimization. Most relevant to the scope of the
present work are those that study binary classification through the lens of
regularized linear regression which we highlight below.

Loureiro et al., (2021) explores both binary and multi-class classification
using an arbitrary convex loss and quadratic regularizer. Since our focus is
on the effects of regularization, such as sparsification and compression, we
instead study quadratic loss and arbitrary regularizer. They demonstrate how
to reduce the analysis of the generalization error to finding fixed points of
a low-dimensional system of equations using AMP. We should remark that we
currently do not know how to use the CGMT framework to analyze the multi-class
setting, a topic that is worthy of investigation in its own right—see e.g.,
Thrampoulidis et al., (2020) for an attempt in this direction.

Mignacco et al., 2020a  uses Gaussian comparison inequalities to analyze the
binary classification error for arbitrary loss functions with $\ell_{2}$
regularization. The main differences between our works are:

$\bullet$ The loss considered in Mignacco et al., 2020a  is of the form
$\mathcal{L}(y(a^{T}w+b))$, whereas ours is $\mathcal{L}(y-a^{T}w)$, as we aim
to study performance of the regression-based approaches to classification.

$\bullet$ We introduce corruption to the labels and analyze how it affects the
generalization error. This seems more natural to do because one of the main
reasons for explicit regularization is finding solutions that do not
interpolate the data.

$\bullet$ We consider arbitrary separable convex regularizers and, in
particular, show that $\ell_{1}$ regularization allows one to find sparse
classifiers and $\ell_{\infty}$ regularization can lead to $1$-bit compression
of the solution. For simplicity, we have focused on quadratic loss so that we
could highlight the effect of the regularizer.

$\bullet$ In the case of $\ell_{2}$ regularization we reduce the number of
scalar parameters to find the generalization error from six in Mignacco et
al., 2020a  to two. Furthermore, in the regime of strong regularization, i.e.,
$\lambda\to\infty$, we find a closed form expression for the generalization
error and use it to conclude that an arbitrary corruption rate $c<0.5$ can be
annihilated with large enough regularization strength.

Other works have studied corruption in the labels. Most notably Chatterji and
Long, (2021) analyzes the performance of the max-margin algorithm for binary
classification of linearly separable data in the presence of corruption in the
labels.

##  3 PRELIMINARIES

###  3.1 Gaussian Mixture Model

We consider a binary classification problem with two classes, where for class
$i=1,2$ the feature vector $x\in\mathbb{R}^{d}$ is drawn at random from
$\mathcal{N}(\mu_{i},\Sigma_{i})$, with $\mu_{i}\in\mathbb{R}^{d}$ the mean
and $\Sigma_{i}\in\mathbb{R}^{d\times d}$ the covariance matrix, and where the
label is chosen as $y=1$ for $i=1$ and $y=-1$ for $i=2$. How well a linear
classifier performs depends on how "close" the mean vectors $\mu_{1}$ and
$\mu_{2}$ are and what the structure of the covariance matrices is. In the
sequel, we will largely assume that the covariances are isotropic
($\Sigma_{1}=\Sigma_{2}=\sigma^{2}I$). For the means, we will assume that
their matching components are drawn iid from zero mean standard normal
distributions with cross-correlation $-1\leq r\leq 1$. The cross-correlation
$r$ allows one to control the distance between the cluster centers. For
example, this means that for large $d$,
$\|\mu_{1}\|^{2}\approx\|\mu_{2}\|^{2}\approx d$ and
$\|\mu_{1}-\mu_{2}\|^{2}\approx 2(1-r)d$.

For simplicity of exposition, we treat only the case of equal class sizes in
this paper, but it is straightforward to apply the same techniques to the case
of unbalanced classes. What we mean by equal classes is that the number of
training data points for each class is $\frac{n}{2}$ (for a total of $n$
training points) and that the probability of drawing an element from each
class, in order to determine the generalization error, is $\frac{1}{2}$. In
all our subsequent analysis we will assume that we are in the over-
parametrized regime, i.e., $n<d$ (often $n\ll d)$. Finally, we will assume
that a fraction $c<\frac{1}{2}$ of the training dataset is mislabeled.

We will consider a linear classifier given by a weight vector
$w\in\mathbb{R}^{d}$. In other words for a given feature vector $x$, we will
declare that $x$ belongs to class 1 if $x^{T}w>0$ and to class 2 if
$x^{T}w<0$. It is then straightforward to show the following result.

######  Lemma 1.

Given a weight vector $w$, and assuming the feature vectors are equally likely
to be drawn from class 1 or class 2, the corresponding generalization error
for the Gaussian mixture model with means $\mu_{1}$ and $\mu_{2}$ and
covariance matrices $\Sigma_{1},\Sigma_{2}$ is given by

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

where $Q(\cdot)$ is the integral of the tail of the standard normal
distribution.

The goal of this paper is to compute and characterize the generalization error
of linear regression using different regularizers for the linear binary
classifier with Gaussian mixture model. As can be seen from Lemma 1, this
requires us to characterize the four quantities

$\mu_{1}^{T}w~{}~{},~{}~{}\mu_{2}^{T}w~{}~{},~{}~{}w^{T}\Sigma_{1}w~{}~{},~{}~{}w^{T}\Sigma_{2}w$

In fact, in much of the subsequent analysis, we shall assume
$\Sigma_{1}=\Sigma_{2}=\sigma^{2}I$, which implies we need to characterize
only the following three quantities

$\mu_{1}^{T}w~{}~{},~{}~{}\mu_{2}^{T}w~{}~{},~{}~{}\|w\|^{2}$ (2)

Since the data model that we are considering is a Gaussian mixture, we shall
make use of the Convex Gaussian Min-Max Theorem (CGMT) (Thrampoulidis et al.,
2015b ), which is a tight and extended version of a classical Gaussian
comparison inequality (Gordon, (1985)).

###  3.2 Convex Gaussian Min-Max Theorem

The CGMT framework has been developed to analyze the properties of the
solutions to non-smooth regularized convex optimization problems and has been
successfully applied to characterize the precise performance in numerous
applications such as $M$-estimators, generalized lasso, massive MIMO, phase
retrieval, regularized logistic regression, adversarial training, max-margin
classifiers, distributionally robust regression, and others (see Stojnic,
(2013); Thrampoulidis et al., (2018); Salehi et al., (2019); Thrampoulidis et
al., 2015a ; Abbasi et al., (2019); Salehi et al., (2018); Miolane and
Montanari, (2021); Taheri et al., (2021); Aubin et al., (2020); Javanmard and
Soltanolkotabi, (2022); Montanari et al., 2019b ; Salehi et al., (2020);
Aolaritei et al., (2023). In this framework, a given so-called primary
optimization (PO) problem, is associated with a simplified auxiliary
optimization (AO) problem from which properties of the optimal solution can be
tightly inferred. Specifically, the (PO) and (AO) problems are defined as
follows:

$\displaystyle\Phi(\mathbf{G})$
$\displaystyle:=\min_{\mathbf{w}\in\mathcal{S}_{\mathbf{w}}}\max_{\mathbf{u}\in\mathcal{S}_{\mathbf{u}}}\mathbf{u}^{\top}\mathbf{Gw}+\psi(\mathbf{w},\mathbf{u})\\!\\!$
(PO) $\displaystyle\phi(\mathbf{g},\mathbf{h})$
$\displaystyle\\!:=\\!\\!\min_{\mathbf{w}\in\mathcal{S}_{\mathbf{w}}}\max_{\mathbf{u}\in\mathcal{S}_{\mathbf{u}}}\|\mathbf{w}\|_{2}\mathbf{g}^{\top}\mathbf{u}\\!+\\!\|\mathbf{u}\|_{2}\mathbf{h}^{\top}\mathbf{w}\\!+\\!\psi(\mathbf{w},\mathbf{u})\\!\\!$
(AO)

where $\mathbf{G}\in\mathbb{R}^{m\times
n},\mathbf{g}\in\mathbb{R}^{m},\mathbf{h}\in\mathbb{R}^{n},\mathcal{S}_{\mathbf{w}}\subset\mathbb{R}^{n},\mathcal{S}_{\mathbf{u}}\subset\mathbb{R}^{m}$
and $\psi:\mathbb{R}^{n}\times\mathbb{R}^{m}\rightarrow\mathbb{R}$. Denoting
any optimal minimizers of (PO) and (AO) as
$\mathbf{w}_{\Phi}:=\mathbf{w}_{\Phi}(\mathbf{G})$ and
$\mathbf{w}_{\phi}:=\mathbf{w}_{\phi}(\mathbf{g},\mathbf{h})$, respectively,
CGMT states:

######  Theorem 1 (CGMT Thrampoulidis et al., (2018)).

Let $\mathcal{S}_{\mathbf{w}}$, $\mathcal{S}_{\mathbf{u}}$ be convex compact
sets, $\psi$ be continuous and convex-concave on
$\mathcal{S}_{\mathbf{w}}\times\mathcal{S}_{\mathbf{u}}$, and,
$\mathbf{G},\mathbf{g}$ and $\mathbf{h}$ all have entries iid standard normal.
Let $\mathcal{S}$ be an arbitrary open subset of $\mathcal{S}_{\mathbf{w}}$
and $\mathcal{S}^{c}:=\mathcal{S}_{\mathbf{w}}/\mathcal{S}$. Denote by
$\Phi_{\mathcal{S}^{c}}(\mathbf{G})$ and
$\phi_{\mathcal{S}^{c}}(\mathbf{g},\mathbf{h})$ the optimal costs of (PO) and
(AO) respectively when $\mathbf{w}$ is minimized over $\mathcal{S}^{c}$. If
there exist constants $\bar{\phi}<\bar{\phi}_{\mathcal{S}^{c}}$ such that
$\phi(\mathbf{g},\mathbf{h})\stackrel{{\scriptstyle
p}}{{\longrightarrow}}\bar{\phi}$, and
$\phi_{\mathcal{S}^{c}}(\mathbf{g},\mathbf{h})\stackrel{{\scriptstyle
p}}{{\longrightarrow}}\bar{\phi}_{\mathcal{S}^{c}}$, (converge in
probability), then
$\lim_{n\rightarrow\infty}\mathbb{P}\left(\mathbf{w}_{\Phi}(\mathbf{G})\in\mathcal{S}\right)=1$.

Let $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ be a convex function. For
$w\in\mathbb{R}^{d}$ and $t>0$ the Moreau envelope of function $f$ (Moreau,
(1965)) is defined as

$\displaystyle\textbf{e}_{f}(w;t):=\min_{x}\frac{1}{2t}\|w-x\|^{2}+f(x)$

We call a convex $f$ separable, when $f(w)=\sum_{i=1}^{d}f_{i}(w_{i})$ for
convex $f_{i}:\mathbb{R}\rightarrow\mathbb{R}$.

###  3.3 Optimal solutions with oracle access to $\mu_{i}$

We need to introduce the following two definitions before proceeding further:

######  Definition 1.

We say that $w\in\mathbb{R}^{d}$ is $k$-sparse if it has at most $k$ non-zero
entries

######  Definition 2.

We say that $w\in\mathbb{R}^{d}$ is a $1$-bit vector if each of its entries is
equal to $\pm a$, for some $a\in\mathbb{R}$

In the over-parametrized regime, since $n<d$, it is not possible to reliably
estimate the means $\mu_{1}$ and $\mu_{2}$ (this is further confounded when
the labels have errors). Nonetheless, it is useful to see what the optimal
linear classifiers would look like when one has oracle access to the means. We
will do this for the general case, as well as for the $k$-sparse and $1$-bit
classifiers.

######  Lemma 2.

1\. The overall optimal classifier is $w=\mu_{1}-\mu_{2}$, which has
performance $Q\left(\sqrt{\frac{d(1-r)}{2\sigma^{2}}}\right)$

2\. The optimal $1$-bit classifier is $w=sign(\mu_{1}-\mu_{2})$, which has
performance $Q\left(\sqrt{\frac{d(1-r)}{\pi\sigma^{2}}}\right)$

3\. The optimal $k$-sparse classifier is obtained from taking the $k$
coordinates of $\mu_{1}-\mu_{2}$ with the largest magnitude and zeroing out
the rest

###  3.4 Regularized linear regression in the presence of corruption in labels

It is natural to use regularized linear regression for classification when not
all labels are reliable. As mentioned earlier, $c<0.5$ stands for the
corruption rate, meaning that $\frac{cn}{2}$ labels within each class are
corrupt. Let $f(\cdot)$ be an arbitrary convex regularizer and $\lambda$ be
the regularization strength. The present paper is concerned with analyzing the
case of the linear regression applied to GMM (cf. 3.1) with means $\mu_{1}$
and $\mu_{2}$ and covariance $\sigma^{2}I$. After reordering the training data
so that the first $\frac{n}{2}$ columns of the data matrix correspond to the
points from the first class, our analysis reduces to the following
optimization problem:

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

Where the entries of $A\in\mathbb{R}^{n\times d}$ are i.i.d.
$\mathcal{N}(0,\sigma^{2})$,
$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}=\begin{pmatrix}\mathds{1}^{T}_{\frac{(1-c)n}{2}}&-\mathds{1}^{T}_{\frac{n}{2}}&\mathds{1}^{T}_{\frac{cn}{2}}\end{pmatrix}$
encodes the training labels.

###  3.5 Approach and intuition behind it

As mentioned earlier, we are interested in computing the inner products and
the norm (2). We focus on the over-parametrized high-dimensional regime where
$\frac{d}{n}=\gamma>1$ is fixed and $n\rightarrow\infty$. In this regime, we
show that the quantities in (2) concentrate and we determine their asymptotic
values. Moreover, in the cases of $\ell_{1}$ and $\ell_{\infty}$
regularization, we do the same for the sparsity and compression rates,
respectively.

To do so, we will employ the CGMT framework. This starts by using the Fenchel
dual of the quadratic loss to rewrite (3) in the following min-max form:

$\displaystyle\min_{w}\max_{v}v^{T}Aw+v^{T}Mw-v^{T}z-\frac{1}{4}\|v\|^{2}+\lambda
f(w)$

Applying CGMT and explicitly performing the maximization over $v$ in the (AO),
we obtain:

$\displaystyle\min_{w}\quad\ (g^{T}w+\sqrt{n}\sigma\|w\|)_{\geq
0}^{2}+\frac{n}{2}(\tilde{\mu_{1}}^{T}w-(1-2c))^{2}+\frac{n}{2}(\tilde{\mu_{2}}^{T}w+(1-2c))^{2}+n(\frac{1}{\sqrt{n}}a^{T}w-2\sqrt{c(1-c)})^{2}+\lambda
f(w)$ (4)

where we have used the following notation

$\displaystyle g,a,a_{1},a_{2}\in\mathcal{N}(0,\sigma^{2}I)$
$\displaystyle\tilde{\mu_{i}}=\mu_{i}+\sqrt{\frac{2}{n}}a_{i}\quad
i\in\\{1,2\\}$ $\displaystyle x_{\geq 0}=\max{(x,0)}$

It is insightful to examine each term in (4) as it provides some explanation
of the phenomenona observed in the simulations.

$\bullet$ The sum of the second and the third terms
$\frac{n}{2}(\tilde{\mu_{1}}^{T}w-(1-2c))^{2}+\frac{n}{2}(\tilde{\mu_{2}}^{T}w+(1-2c))^{2}$
encourages the minimizer $w$ to align with
$\mu_{1}-\mu_{2}+\sqrt{\frac{2}{n}}(a_{1}-a_{2})$. As seen earlier, the
oracle-based optimal $w$ is $\mu_{1}-\mu_{2}$. Thus, it is these two terms
that encourage $w$ to approach the oracle-based optimal. Note that the extra
term $\sqrt{\frac{2}{n}}(a_{1}-a_{2})$ has $\frac{2\sigma^{2}}{n(1-r)}$ of the
variance of $\mu_{1}-\mu_{2}$ and represents the effects of the variance in
the training data from the GMM. The second and third terms represent fitting
the correctly labeled data.

$\bullet$ The fourth term $n(\frac{1}{\sqrt{n}}a^{T}w-2\sqrt{c(1-c)})^{2}$
encourages $w$ to align with the arbitrary Gaussian vector
$\frac{a}{\sqrt{n}}$. This represents the minimizer’s attempt to interpolate
the corrupted labels, as it vanishes when $c=0$.

$\bullet$ The first term $(g^{T}w+\sqrt{n}\sigma\|w\|)_{\geq 0}^{2}$ makes $w$
partly align with a random direction $-g$ and is independent of $c$. It
represents the fact that the problem is over-parametrized.

$\bullet$ The last term $\lambda f(w)$ is the regularization term.

Ideally, we would like the minimizer to minimize the second and third terms
and to ignore the first and fourth ones. We now provide some intuition as to
why the regularization term $f(w)$ helps with this. Due to the equivalence of
norms, our argument applies to any norm $f(w)=\|w\|_{p}$, and so, for
simplicity, we shall focus on $p=2$ and $f(w)=\|w\|_{p}^{2}$.

Due to the existence of the $\|w\|_{2}$ regularizer, the minimizer would like
to minimize the terms in (4) with as small a $\|w\|^{2}$ as possible. This is
much easier to do for the second and third terms, since the squared norm of
the vectors ${\tilde{\mu}}_{1}$ and ${\tilde{\mu}}_{2}$ is
$d(1+\frac{2\sigma^{2}}{n})$, than it is for the fourth term where the squared
norm of the vector $\frac{1}{\sqrt{n}}a$ is $\frac{\sigma^{2}d}{n}$. Thus, the
minimizer will reduce the second and third terms at the expense of the fourth
one. In other words, the regularization term encourages the regressor to
interpolate the correctly labeled data, at the expense of the corrupted
labels, which improves performance and is what we hoped it would do. In fact,
the larger $\lambda$ is, the stronger the incentive to ignore the mislabeled
data.

##  4 MAIN RESULTS

In this section we provide rigorous results along some remarks which will help
to gain more insights on the general problem.

###  4.1 Precise results

The reader can find a theorem describing the generalization error for an
arbitrary convex regularizer $f$ below.

######  Theorem 2 (Master theorem).

The generalization error resulting from the application of the linear
regression with a separable convex regularizer $f=\sum_{i=1}^{d}f_{i}(w_{i})$,
with $f_{i}$’s being identical and regularization strength $\lambda$ to the
Gaussian mixture model with means $\mu_{1},\mu_{2}$ and covariance
$\sigma^{2}I$ is equal to

$E(f,\lambda)=Q\left(\frac{\gamma}{2\sqrt{\frac{1}{n\tau^{2}}-(1-c)(\frac{\gamma}{2}-1)^{2}-c(\frac{\gamma}{2}+1)^{2}}}\right)$

for $\tau$ and $\gamma$ defined by the scalar optimization

$\displaystyle\min_{\tau\geq 0}\max_{\beta\geq
0,\gamma}\frac{\beta\tau}{2}(-\frac{n}{4}\gamma^{2}-\frac{nd(1-r)}{2\sigma^{2}}(\frac{\gamma}{2}-1+2c)^{2}+n)+\frac{\beta}{2\tau}(1-\frac{d}{n})-\frac{1}{4}\beta^{2}+d\lambda\mathbb{E}e_{f_{i}}(\Xi(\gamma,\tau)G;\frac{\lambda}{\beta\tau
n\sigma^{2}})$

where the expectation is taken over $G\sim\mathcal{N}(0,1)$ and
$\Xi(\gamma,\tau):=\sqrt{\frac{1-r}{2\sigma^{4}}(\frac{\gamma}{2}-1+2c)^{2}+\frac{1}{n^{2}\tau^{2}\sigma^{2}}}$

Next, we proceed to provide some specialized results for prominent
regularizers. In the case of $f=\|.\|_{2}$, it turns out that $\hat{w}$ from
Theorem 2 takes form of $w(\alpha,\gamma)=\alpha g+\gamma(\mu_{1}-\mu_{2})$
for some $\alpha,\gamma\in\mathbb{R}$ (see Appendix). This allows for an
easier way of characterising the desired generalization error than the one
suggested by Theorem 2.

######  Theorem 3 ($\ell_{2}$ regularization).

The generalization error resulting from the application of the ridge
regression with regularization strength $\lambda$ to the Gaussian mixture
model with means $\mu_{1},\mu_{2}$ and covariance $\sigma^{2}I$ is equal to

$E(\ell_{2},\lambda)=Q\left(\frac{\gamma
d(1-r)}{\sqrt{\alpha^{2}\sigma^{4}d+2\sigma^{2}\gamma^{2}d(1-r)}}\right)$

where $\alpha,\gamma$ are defined by the following two-dimensional convex
optimization problem:

$\min_{\alpha,\gamma}(\alpha\sigma^{2}d+\sqrt{n\sigma^{2}\Omega(\alpha,\gamma)+\Theta(\alpha,\gamma)})_{\geq
0}^{2}+\lambda\Omega(\alpha,\gamma)$

with

$\displaystyle\Omega(\alpha,\gamma)$
$\displaystyle=\alpha^{2}\sigma^{2}d+2d(1-r)\gamma^{2}$
$\displaystyle\Theta(\alpha,\gamma)$
$\displaystyle=n(1-c)(d(1-r)\gamma-1)^{2}+nc(d(1-r)\gamma+1)^{2}$

For $\ell_{1}$ regularization, one can find the sparsity rate in addition to
analyzing performance.

######  Theorem 4 ($\ell_{1}$ regularization).

The generalization error resulting from the application of the $\ell_{1}$
regularized regression with regularization strength $\lambda$ to the Gaussian
mixture model with means $\mu_{1},\mu_{2}$ and covariance $\sigma^{2}I$ is
equal to

$E(\ell_{1},\lambda)=Q\left(\frac{\gamma}{2\sqrt{\frac{1}{n\tau^{2}}-(1-c)(\frac{\gamma}{2}-1)^{2}-c(\frac{\gamma}{2}+1)^{2}}}\right)$

for $\beta,\tau$ and $\gamma$ defined by the optimization:

$\displaystyle\min_{\tau\geq 0}\max_{\beta\geq
0,\gamma}-\frac{2d\beta}{n\tau}Q(\frac{\lambda}{n\beta\tau\tilde{\sigma}})+\frac{\beta}{2\tau}-\frac{1}{4}\beta^{2}+\frac{\beta\tau
n}{2}[d\sigma^{2}(\frac{\lambda}{n\beta\tau\sigma^{2}})^{2}(2(s^{2}+1)Q(\frac{1}{s})-\frac{2s}{\sqrt{2\pi}}e^{-\frac{1}{2s^{2}}})+$
$\displaystyle+\frac{2\gamma
d}{\sigma^{2}}Q(\frac{\lambda}{n\beta\tau\tilde{\sigma}})(\frac{1-2c}{2}-\frac{\gamma}{4})(1-r)+\frac{\gamma^{2}}{4}+1-(1-2c)\gamma]+\frac{2d\lambda\tilde{\sigma}}{\sigma^{2}\sqrt{2\pi}}e^{-\frac{\lambda^{2}}{2(n\beta\tau\tilde{\sigma})^{2}}}-\frac{2d\lambda^{2}}{n\beta\tau\sigma^{2}}Q(\frac{\lambda}{n\beta\tau\tilde{\sigma}})$

where

$\displaystyle\tilde{\sigma}^{2}$
$\displaystyle=\frac{\sigma^{2}}{n^{2}\tau^{2}}+2(\frac{\gamma}{4}-\frac{1-2c}{2})^{2}(1-r)\text{
and }s=\frac{\tilde{\sigma}n\beta\tau}{\lambda}$

Furthermore, the corresponding solution is
$\lceil{2Q(\frac{\lambda}{n\beta\tau\tilde{\sigma}})}\rceil$-sparse

Finally, in the case of $f=\ell_{\infty}$ we were also able to calculate the
compression rate.

######  Theorem 5 ($\ell_{\infty}$ regularization).

The generalization error resulting from the application of the $\ell_{\infty}$
regularized regression with regularization strength $\lambda$ to the Gaussian
mixture model with means $\mu_{1},\mu_{2}$ and covariance $\sigma^{2}I$ is

$E(\ell_{\infty},\lambda)=Q\left(\frac{\gamma}{2\sqrt{\frac{1}{n\tau^{2}}-(1-c)(\frac{\gamma}{2}-1)^{2}-c(\frac{\gamma}{2}+1)^{2}}}\right)$

for $\beta,\tau$ and $\gamma$ defined by the optimization:

$\displaystyle\min_{\tau,\delta\geq
0}\max_{\gamma}\delta+\bigg{(}\frac{1}{2\tau}+\frac{\tau}{2}(-\frac{n}{4}\gamma^{2}+n)-\frac{nd\sigma^{2}\tau\Xi^{2}}{2}-\frac{nd\sigma^{2}\tau\delta\Xi}{\lambda\sqrt{2\pi}}exp(-\frac{\delta^{2}}{2\lambda^{2}\Xi^{2}})+nd\sigma^{2}\tau(\Xi^{2}+\frac{\delta^{2}}{\lambda^{2}})Q(\frac{\delta}{\lambda\Xi})\bigg{)}^{2}_{\geq
0}$

where

$\Xi(\gamma,\tau):=\sqrt{\frac{1-r}{2\sigma^{4}}(\frac{\gamma}{2}-1+2c)^{2}+\frac{1}{n^{2}\tau^{2}\sigma^{2}}}$

Moreover, $k$ of the weights are equal to $\frac{\delta}{\lambda}$, $k$ of the
weights are equal to $-\frac{\delta}{\lambda}$, and all others weights lie in
between, where $k=\lfloor{dQ(\frac{\delta}{\lambda\Xi})}\rfloor$

###  4.2 Explicit approximations for large $\lambda$

While the theorems above accurately describe the generalization errors, they
are not as explicit as one might wish. To overcome this, we show for $\lambda$
large enough, the first term of (4) is negligible compared to $\lambda f(w)$.
This suggests dropping that term completely from the (AO). Leaving the
technical details for the Appendix, we summarize the implications of this
approximation in the remarks below. In Section 6 we will observe that these
approximations do work well when $\lambda$ is large.

######  Remark 1.

The following approximation for the generalization error takes place in the
case of the ridge regression if $\lambda\gg\sigma^{2}n$:

$\displaystyle\gamma=\frac{1-2c}{d(1-r+\frac{2\sigma^{2}}{n})+2\frac{\lambda}{n}}$
$\displaystyle\beta=\frac{2\sqrt{nc(1-c)}}{d\sigma^{2}+\lambda}$
$\displaystyle
E(\ell_{2},\lambda)=Q\left(\frac{d(1-r)\gamma}{\sigma\sqrt{2d(1-r+\frac{2\sigma^{2}}{n})\gamma^{2}+d\sigma^{2}\beta^{2}}}\right)$

######  Remark 2.

Assume that $\sigma\ll\sqrt{n}$. Then the following approximation can be made:

$\frac{d(1-r)\gamma}{\sigma\sqrt{2d(1-r+\frac{2\sigma^{2}}{n})\gamma^{2}+d\sigma^{2}\beta^{2}}}\approx\frac{\sqrt{d(1-r)}}{\sigma\sqrt{2}}$

Note that the $Q$-function applied to the argument above is a negligibly small
number for big enough $d$. Thus, informally, this remark can be stated as
follows: if the problem is high-dimensional and $\sigma$ is small enough, the
negative effects of any corruption rate $c<0.5$ can be completely eliminated
via ridge regression with a sufficiently large regularization strength.

######  Remark 3.

Dropping the first term of (4) in the case of the $\ell_{1}$-regularized
regression and assuming that $\lambda$ is large enough, one can show that
$w_{i}=0$ unless $|t_{i}|$ is close to $\lambda$, where $t\in\mathbb{R}^{d}$
is defined via

$t=\frac{n}{2}\gamma(\tilde{\mu_{1}}-\tilde{\mu_{2}})+\sqrt{n}\beta a$

Moreover, it turns out that the optimal scalars $\gamma$, $\alpha$, and
$\beta$ are such that $|t_{i}|\leq\lambda$ holds with high probability. This
suggests that $\ell_{1}$ regularization tries to kill all the components of
$w$ apart from the ones corresponding to the top entries of
$|\gamma(\tilde{\mu_{1}}-\tilde{\mu_{2}})+\sqrt{n}\beta a|$ where the latter
can be regarded as an approximation to $\mu_{1}-\mu_{2}$. This is similar to
the description of the optimal sparse classifier from Lemma 2. Thus, for large
enough $\lambda$, the $\ell_{1}$ regularizer tries to find as sparse a
solution as possible that aligns itself with the top entries of
$\mu_{1}-\mu_{2}$.

######  Remark 4.

Assuming that $\lambda$ is large enough, the following approximation can be
made for the $w$ found from the $\ell_{\infty}$-regularized regression:

$w_{i}=-\frac{\delta}{\lambda}\mbox{sign}((\frac{n}{2}\gamma(\tilde{\mu_{1}}-\tilde{\mu_{2}})+\sqrt{n}\beta
a)_{i})$

Where $\gamma,\beta$ and $\delta$ are defined by the optimization:

$\displaystyle\min_{\delta\geq 0}\max_{\gamma,\beta\geq
0}\delta-n(1-2c)\gamma-\frac{\gamma^{2}}{2}-2n\sqrt{c(1-c)}\beta-\frac{\beta^{2}}{4}-\frac{\delta}{\lambda}\|\frac{n}{2}\gamma(\tilde{\mu_{1}}-\tilde{\mu_{2}})+\sqrt{n}\beta
a\|_{1}$

for $a\sim\mathcal{N}(0,\sigma^{2}I)$

Since all entries of $w$ have the same magnitude and since (1) is unaffected
by a scaling of $w$, this implies that we can replace $w$ by $sign(w)$ without
any loss of performance. Thus each component of the optimal $w$ can be encoded
by a single bit.

##  5 A COMPRESSION SCHEME

As discussed in Remark 4, $\ell_{\infty}$-regularization with large $\lambda$
can be used for $1$-bit compression via $\tilde{w}=\mbox{sign}(w)$. One might
wonder whether using the same compression scheme for an arbitrary
$f$-regularized solution would still retain good performance. Turns out that
this scheme does succeed for $f=\ell_{2}^{2}$ and $f=\ell_{1}$ in the small
noise ($\sigma\ll\sqrt{n}$) and large $\lambda$ regime. For $f=\ell_{1}$, this
is discussed in Remark 3. For $f=\ell_{2}^{2}$, as discussed in Section 3.5,
the corresponding $w$ strives to align with $\mu_{1}-\mu_{2}$. This makes
$\mbox{sign}(w)$ approximate $\mbox{sign}(\mu_{1}-\mu_{2})$ which, according
to Lemma 2, is the optimal $1$-bit classifier.

##  6 NUMERICAL RESULTS

To showcase our results, we performed extensive simulations using synthetic
data produced according to the assumptions described in the previous sections.
We generated points equiprobably from two distributions
$\mathcal{N}(\mu_{1},\sigma^{2}I)$ and $\mathcal{N}(\mu_{2},\sigma^{2}I)$,
where the corresponding components of the $\mu_{i}$ were iid standard normal
with cross-correlation $-1\leq r\leq 1$, and with labels $+1$ and $-1$
respectively, a fraction $c$ of those which were subsequently corrupted.
Making use of the MATLAB™ CVX package (Grant and Boyd, (2008, 2014)), we
trained classifiers that minimize the $\ell_{2}$, $\ell_{1}$ and
$\ell_{\infty}$ regression objectives for this data. We simulated the
generalization error of these classifiers, and compared it to the expressions
obtained in theorems 3, 4, and 5 (cf. Fig.1, Fig.2, Fig.3). Moreover, we have
also plotted the predicted sparsity and compression rate for the $\ell_{1}$
and $\ell_{\infty}$ cases. In the following figures, we took the nominal
values $n=200,d=2000,c=0.2,r=0.8,\sigma=2$ as a starting point. Then, to
analyze the effects of these parameters independently, we vary exactly one
parameter per experiment while keeping the others fixed. In the subsections
below, we go over the plots and interpret their results.

###  6.1 Ridge regression

For the ridge regression, we examined the effects of $r,c,\sigma,\frac{d}{n}$
on the generalization error in Fig. 1. As expected, the generalization error
improves as the regularization strength increases. The $E(\ell_{2},\lambda)$,
simulated directly by solving ridge regression, and the prediction for it
derived from Theorem 3 match very closely. Moreover, the closed-form
approximation formulated in Section 4.2 follows the true $E(\ell_{2},\lambda)$
closely for large values of $\lambda$. In addition, it appears to be a lower
bound for the generalization error for all $\lambda>0$, though we leave
proving this to future work. Finally, in light of Section 5, we also
considered the sign of the solution as a possible classifier. It turns out one
does not lose much in performance by compressing each weight to a single bit.
Furthermore, it is evident that increasing either of $c,r,\sigma$ increases
the classification error and, on the opposite, increasing $\frac{d}{n}$,
decreases it.

Figure 1: Black dashed line: simulated error. Red line: Theorem 3 prediction.
Blue dotted line: closed-form approximation for large $\lambda$. Green line:
true error for $sign(w)$. These 4 sets of plots characterize the
generalization error of ridge regression when one parameter changes while the
others are fixed.

###  6.2 $\ell_{1}$ regularization

Similar to the previous section, in Fig. 2 we compared the simulated error to
the error predicted by Theorem 4 and observed a close match. The solution has
many entries that are very close to zero, but are not exactly equal to it
because of small-scale numerical inaccuracies, and so we sparsified this
solution according to the rate suggested by Theorem 4. We observed that this
does affect the performance. Finally, we also compress the $\ell_{1}$ solution
down to $1$ bit. The effects of changing $c,r,\sigma$ on the generalization
error are similar to what was observed in the ridge regression case.
Interestingly, changing these parameters has different impacts on the
theoretical prediction for the sparsity rate. Fig. 4 proposes the sparsity
rate does not change much with $r$, whereas increasing $\sigma,c$ leads to
difficulty in sparsifying. Also note that we obtain sparsity rates close to
zero as we increase $\lambda$. Pairing the observations from Figs. 2 and 4, we
see that one can attain a good generalization error with an extremely sparse
estimator. For instance, when $\sigma=0.5$, we get an $18$-sparse estimator
(in an ambient dimension of 2000) with a generalization error of as little as
$0.0003$. This is despite the fact that the underlying GMM model had no
inherent sparsity structure.

###  6.3 $\ell_{\infty}$ regularization

Repeating the same procedure as before, we verified that the predicted error
matches the simulated error, as can be seen in Fig. 3. Moreover, we checked
the same for the compression rate (cf. Fig. 5). It is noteworthy that the
$1$-bit estimator follows the simulated error closely. Analyzing the
compression rate, it is evident that no matter how corrupt the labels are
(larger $c$), one can still take the one-bit estimator and not lose out much
on performance. The same could also be said about the angle between the means
represented by $r$.

##  7 CONCLUSION

In this work we considered the problem of binary classification with corrupt
labels through the lens of regularized linear regression. We used CGMT to
derive sharp results for the generalization error for a general convex
separable regularizer $f$. Both theoretically, and through simulations, we
showed that regularization helps the generalization performance. We calculated
the sparsity rate for the case $f=\ell_{1}$ and the compression rate for the
case $f=\ell_{\infty}$ and validated the theoretical findings numerically.
These evaluations suggest that good sparse classifiers and good one-bit
classifiers often exist, even when the underlying GMM has no inherent sparsity
structure, and even in the presence of high rates of label corruption.
Possible future directions include extending this work to the case of multi-
class classification and to other regularizers and loss functions.

Figure 2: Black dashed line: simulated error. Red line: prediction from
Theorem 4. Green line: $\mbox{sign}(w)$. Blue line: sparsified solution

Figure 3: Black dashed line: $\ell_{\infty}$ error, Red line: AO prediction,
Green line: $sign(w)$

Figure 4: Effect of each parameter on the sparsity rate

Figure 5: Effect of each parameter on the compression rate

## References

  * Abbasi et al., (2019) Abbasi, E., Salehi, F., and Hassibi, B. (2019).  Performance analysis of convex data detection in mimo.  In ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 4554–4558. IEEE.
  * 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.
  * Aubin et al., (2020) Aubin, B., Krzakala, F., Lu, Y., and Zdeborová, L. (2020).  Generalization error in high-dimensional perceptrons: Approaching bayes error with convex optimization.  Advances in Neural Information Processing Systems, 33:12199–12210.
  * Bayati and Montanari, (2011) Bayati, M. and Montanari, A. (2011).  The dynamics of message passing on dense graphs, with applications to compressed sensing.  IEEE Transactions on Information Theory, 57(2):764–785.
  * Candès and Sur, (2018) Candès, E. J. and Sur, P. (2018).  The phase transition for the existence of the maximum likelihood estimate in high-dimensional logistic regression.  arXiv preprint arXiv:1804.09753.
  * Chatterji and Long, (2021) Chatterji, N. S. and Long, P. M. (2021).  Finite-sample analysis of interpolating linear classifiers in the overparameterized regime.  The Journal of Machine Learning Research, 22(1):5721–5750.
  * Deng et al., (2019) Deng, Z., Kammoun, A., and Thrampoulidis, C. (2019).  A model of double descent for high-dimensional binary linear classification.  arXiv preprint arXiv:1911.05822.
  * Donoho et al., (2009) Donoho, D. L., Maleki, A., and Montanari, A. (2009).  Message-passing algorithms for compressed sensing.  Proceedings of the National Academy of Sciences, 106(45):18914–18919.
  * Gordon, (1985) Gordon, Y. (1985).  Some inequalities for gaussian processes and applications.  Israel Journal of Mathematics, 50:265–289.
  * Grant and Boyd, (2008) Grant, M. and Boyd, S. (2008).  Graph implementations for nonsmooth convex programs.  In Blondel, V., Boyd, S., and Kimura, H., editors, Recent Advances in Learning and Control, Lecture Notes in Control and Information Sciences, pages 95–110. Springer-Verlag Limited.
  * Grant and Boyd, (2014) Grant, M. and Boyd, S. (2014).  CVX: Matlab software for disciplined convex programming, version 2.1.
  * Huang, (2017) Huang, H. (2017).  Asymptotic behavior of support vector machine for spiked population model.  Journal of Machine Learning Research, 18(1):1472–1492.
  * Javanmard and Montanari, (2013) Javanmard, A. and Montanari, A. (2013).  State evolution for general approximate message passing algorithms, with applications to spatial coupling.  Information and Inference: A Journal of the IMA, 2(2):115–144.
  * 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.
  * Kammoun and Alouini, (2020) Kammoun, A. and Alouini, M.-S. (2020).  On the precise error analysis of support vector machines.  arXiv preprint arXiv:2003.12972.
  * Lolas, (2020) Lolas, P. (2020).  Regularization in high-dimensional regression and classification via random matrix theory.  arXiv preprint arXiv:2003.13723.
  * 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.  Advances in Neural Information Processing Systems, 34:10144–10157.
  * (18) Mignacco, F., Krzakala, F., Lu, Y., Urbani, P., and Zdeborova, L. (2020a).  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.
  * (19) Mignacco, F., Krzakala, F., Lu, Y. M., , and Zdeborová, L. (2020b).  The role of regularization in classification of high-dimensional noisy gaussian mixture.  arXiv preprint arXiv:2002.11544.
  * Miolane and Montanari, (2021) Miolane, L. and Montanari, A. (2021).  The distribution of the lasso: Uniform control over sparse balls and adaptive parameter tuning.  The Annals of Statistics, 49(4):2313–2335.
  * (21) Montanari, A., Ruan, F., Sohn, Y., and Yan, J. (2019a).  The generalization error of max-margin linear classifiers: High-dimensional asymptotics in the overparametrized regime.  arXiv preprint arXiv:1911.01544.
  * (22) Montanari, A., Ruan, F., Sohn, Y., and Yan, J. (2019b).  The generalization error of max-margin linear classifiers: High-dimensional asymptotics in the overparametrized regime.  arXiv preprint arXiv:1911.01544.
  * Moreau, (1965) Moreau, J.-J. (1965).  Proximité et dualité dans un espace hilbertien.  Bulletin de la Société mathématique de France, 93:273–299.
  * Salehi et al., (2018) Salehi, F., Abbasi, E., and Hassibi, B. (2018).  A precise analysis of phasemax in phase retrieval.  In 2018 IEEE International Symposium on Information Theory (ISIT), pages 976–980. IEEE.
  * 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.
  * Stojnic, (2013) Stojnic, M. (2013).  A framework to characterize performance of lasso algorithms.  arXiv preprint arXiv:1303.7291.
  * Sur and Candès, (2019) Sur, P. and Candès, E. J. (2019).  A modern maximum-likelihood theory for high-dimensional logistic regression.  Proceedings of the National Academy of Sciences, 116(29):14516–14525.
  * Taheri et al., (2020) Taheri, H., Pedarsani, R., and Thrampoulidis, C. (2020).  Sharp asymptotics and optimal performance for inference in binary models.  Proceedings of Machine Learning Research, pages 3739–3749.
  * Taheri et al., (2021) Taheri, H., Pedarsani, R., and Thrampoulidis, C. (2021).  Fundamental limits of ridge-regularized empirical risk minimization in high dimensions.  In International Conference on Artificial Intelligence and Statistics, pages 2773–2781. PMLR.
  * (31) Thrampoulidis, C., Abbasi, E., and Hassibi, B. (2015a).  Lasso with non-linear measurements is equivalent to one with linear measurements.  Advances in Neural Information Processing Systems, 28.
  * 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.
  * (33) Thrampoulidis, C., Oymak, S., and Hassibi, B. (2015b).  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.

##  Appendix A USEFUL TECHNICAL RESULTS

The following results will be of use for proving the theorems. We will invoke
them multiple times without referring to them explicitly:

An expectation formula. Let $X\sim\mathcal{N}(0,\sigma^{2})$. Then
$\mathbb{E}[(|X|-1)^{2}\mathds{1}_{|X|>1}]=2(\sigma^{2}+1)Q(\frac{1}{\sigma})-\frac{2\sigma}{\sqrt{2\pi}}e^{-\frac{1}{2\sigma^{2}}}$.

###### Proof.

Denote $Y=\frac{X}{\sigma}\sim\mathcal{N}(0,1)$.

$\mathbb{E}[(|X|-1)^{2}\mathds{1}_{|X|>1}]=\mathbb{E}[X^{2}\mathds{1}_{|X|>1}]-2\mathbb{E}[|X|\mathds{1}_{|X|>1}]+\mathbb{E}[\mathds{1}_{|X|>1}]=2\mathbb{E}[X^{2}\mathds{1}_{X>1}]-4\mathbb{E}[X\mathds{1}_{X>1}]+2\mathbb{E}[\mathds{1}_{X>1}]=$
$=2\sigma^{2}\mathbb{E}[Y^{2}\mathds{1}_{Y>\frac{1}{\sigma}}]-4\sigma\mathbb{E}[Y\mathds{1}_{Y>\frac{1}{\sigma}}]+2\mathbb{E}[\mathds{1}_{Y>\frac{1}{\sigma}}]=\frac{2\sigma^{2}}{\sqrt{2\pi}}\int^{+\infty}_{\frac{1}{\sigma}}t^{2}e^{-\frac{t^{2}}{2}}dt-\frac{4\sigma}{\sqrt{2\pi}}\int^{+\infty}_{\frac{1}{\sigma}}te^{-\frac{t^{2}}{2}}dt+2Q(\frac{1}{\sigma})=$
$=-\frac{2\sigma^{2}}{\sqrt{2\pi}}\int^{+\infty}_{\frac{1}{\sigma}}tde^{-\frac{t^{2}}{2}}-\frac{4\sigma}{\sqrt{2\pi}}\int^{+\infty}_{\frac{1}{\sigma}}e^{-\frac{t^{2}}{2}}d\frac{t^{2}}{2}+2Q(\frac{1}{\sigma})=-\frac{2\sigma^{2}}{\sqrt{2\pi}}e^{-\frac{t^{2}}{2}}t_{|_{\frac{1}{\sigma}}^{+\infty}}+\frac{2\sigma^{2}}{\sqrt{2\pi}}\int^{+\infty}_{\frac{1}{\sigma}}e^{-\frac{t^{2}}{2}}dt-$
$-\frac{4\sigma}{\sqrt{2\pi}}\int^{+\infty}_{\frac{1}{2\sigma^{2}}}e^{-z}dz+2Q(\frac{1}{\sigma})=\frac{2\sigma}{\sqrt{2\pi}}e^{-\frac{1}{2\sigma^{2}}}+2\sigma^{2}Q(\frac{1}{\sigma})-\frac{4\sigma}{\sqrt{2\pi}}e^{-\frac{1}{2\sigma^{2}}}+2Q(\frac{1}{\sigma})=$
$=2(\sigma^{2}+1)Q(\frac{1}{\sigma})-\frac{2\sigma}{\sqrt{2\pi}}e^{-\frac{1}{2\sigma^{2}}}$

∎

A square root trick. The following equality holds for any $x>0$:

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

###### Proof.

Differentiate the objective from the right hand side by $\beta$:

$\frac{d}{d\beta}(\frac{1}{2\beta}+\frac{\beta
x}{2})=\frac{1}{-2\beta^{2}}+\frac{x}{2}$

We conclude that $\frac{1}{2\beta}+\frac{\beta x}{2}$ is minimized at
$\beta=\frac{1}{\sqrt{x}}$. The value the objective takes at this point is

$\frac{1}{2\beta}+\frac{\beta
x}{2}=\frac{1}{\frac{2}{\sqrt{x}}}+\frac{\frac{1}{\sqrt{x}}x}{2}=\sqrt{x}$ ∎

##  Appendix B PROOFS OF THE LEMMAS

###  B.1 Proof of Lemma 1

###### Proof.

By definition,

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

Rewrite $x=\mu_{1}+y_{1}$ for $x\sim\mathcal{N}(\mu_{1},\Sigma_{1})$ and
$x=\mu_{2}+y_{2}$ for $x\sim\mathcal{N}(\mu_{2},\Sigma_{2})$. Note that
$y_{1}\sim\mathcal{N}(0,\Sigma_{1})$ and $y_{2}\sim\mathcal{N}(0,\Sigma_{2})$.
We obtain:

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

Since $z_{1}=w^{T}y_{1}\sim\mathcal{N}(0,w^{T}\Sigma_{1}w)$ and
$z_{2}=w^{T}y_{2}\sim\mathcal{N}(0,w^{T}\Sigma_{2}w)$ we have:

$E(w)=\frac{1}{2}\mathbb{P}_{z_{1}\sim\mathcal{N}(0,w^{T}\Sigma_{1}w)}(z_{1}<-\mu_{1}^{T}w)+\frac{1}{2}\mathbb{P}_{z_{2}\sim\mathcal{N}(0,w^{T}\Sigma_{2}w)}(z_{2}\geq-\mu_{2}^{T}w)=$
$=\frac{1}{2}\mathbb{P}_{z^{\prime}_{1}\sim\mathcal{N}(0,1)}(z^{\prime}_{1}<-\frac{\mu_{1}^{T}w}{\sqrt{w^{T}\Sigma_{1}w}})+\frac{1}{2}\mathbb{P}_{z^{\prime}_{2}\sim\mathcal{N}(0,1)}(z^{\prime}_{2}\geq-\frac{\mu_{2}^{T}w}{\sqrt{w^{T}\Sigma_{2}w}})=$
$=\frac{1}{2}\mathbb{P}_{z^{\prime}_{1}\sim\mathcal{N}(0,1)}(z^{\prime}_{1}>\frac{\mu_{1}^{T}w}{\sqrt{w^{T}\Sigma_{1}w}})+\frac{1}{2}\mathbb{P}_{z^{\prime}_{2}\sim\mathcal{N}(0,1)}(z^{\prime}_{2}\geq-\frac{\mu_{2}^{T}w}{\sqrt{w^{T}\Sigma_{2}w}})=$
$=\frac{1}{2}Q(\frac{\mu_{1}^{T}w}{\sqrt{w^{T}\Sigma_{1}w}})+\frac{1}{2}Q(-\frac{\mu_{2}^{T}w}{\sqrt{w^{T}\Sigma_{2}w}})$

∎

###  B.2 Proof of Lemma 2

###### Proof.

Note that, since the model for the data distribution is symmetric w.r.t. the
transformation $\mu_{1}\xleftrightarrow{}\mu_{2}$, the equality
$\mu_{1}^{T}w_{opt}=-\mu_{2}^{T}w_{opt}$ has to hold for the optimal $w_{opt}$
from each of the parts (1)-(3) of the lemma. One therefore has:

$E(w_{opt})=\frac{1}{2}Q\left(\frac{\mu_{1}^{T}w_{opt}}{\sigma\|w_{opt}\|}\right)+\frac{1}{2}Q\left(\frac{-\mu_{2}^{T}w_{opt}}{\sigma\|w_{opt}\|}\right)=Q\left(\frac{\mu_{1}^{T}w_{opt}}{\sigma\|w_{opt}\|}\right)=Q\left(\frac{(\mu_{1}-\mu_{2})^{T}w_{opt}}{2\sigma\|w_{opt}\|}\right)$

Now let us proceed to proving each of the points (1)-(3) separately:

1\. Note that for any $w$ satisfying the symmetry condition
$\mu_{1}^{T}w=-\mu_{2}^{T}w$ it holds that

$E(w)=Q\left(\frac{(\mu_{1}-\mu_{2})^{T}w}{2\sigma\|w\|}\right)\geq
Q\left(\frac{(\mu_{1}-\mu_{2})^{T}w_{*}}{2\sigma\|w_{*}\|}\right)=Q\left(\frac{\|\mu_{1}-\mu_{2}\|_{2}}{2\sigma}\right)=Q\left(\sqrt{\frac{d(1-r)}{2\sigma^{2}}}\right)\text{
where }w_{*}=\mu_{1}-\mu_{2}$

2\. Assuming that $\mu_{1}^{T}w=-\mu_{2}^{T}w$ and $w$ is a $1$ \- bit vector
we have

$E(w)=Q\left(\frac{(\mu_{1}-\mu_{2})^{T}w}{2\sigma\|w\|}\right)\geq
Q\left(\frac{(\mu_{1}-\mu_{2})^{T}w_{*}}{2\sigma\|w_{*}\|}\right)=Q\left(\frac{\|\mu_{1}-\mu_{2}\|_{1}}{2\sigma}\right)=Q\left(\sqrt{\frac{d(1-r)}{\pi\sigma^{2}}}\right)\text{
where }w_{*}=sign(\mu_{1}-\mu_{2})$

3\. If $w$ is a $k$ \- sparse vector such that $\mu_{1}^{T}w=-\mu_{2}^{T}w$,
then

$E(w)=Q\left(\frac{(\mu_{1}-\mu_{2})^{T}w}{2\sigma\|w\|}\right)\geq
Q\left(\frac{(\mu_{1}-\mu_{2})^{T}w_{*}}{2\sigma\|w_{*}\|}\right)$

where $w_{*}$ is obtained from taking the $k$ coordinates of $\mu_{1}-\mu_{2}$
with the largest magnitude and zeroing out the rest.

∎

##  Appendix C PROOFS OF THE MAIN RESULTS

###  C.1 Proof of Theorem 2

###### Proof.

As discussed in Section 3.4, the proof reduces to analyzing the following
optimization problem:

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

We rewrite it as a min-max problem to enable invocation of CGMT:

$\displaystyle\min_{w}\max_{v}v^{T}Aw+v^{T}Mw-v^{T}z-\frac{1}{4}\|v\|^{2}+\lambda
f(w)$

Applying CGMT yields the following AO:

$\displaystyle\min_{w}\max_{v}\|v\|g^{T}w+\|w\|h^{T}v+v^{T}(Mw-z)-\frac{1}{4}\|v\|^{2}+\lambda
f(w)$

Performing optimization over $v$ leads to:

$\displaystyle\min_{w}\max_{\beta\geq 0}\beta
g^{T}w+\beta\|h\|w\|+Mw-z\|-\frac{1}{4}\beta^{2}+\lambda f(w)$ (5)

Substituting for the norm of $\|h\|w\|+Mw-z\|$ we obtain:

$\displaystyle\min_{w}\max_{\beta\geq 0}\beta
g^{T}w+\beta\sqrt{n\sigma^{2}\|w\|^{2}+\|Mw\|^{2}+\|z\|^{2}-2z^{T}Mw}-\frac{1}{4}\beta^{2}+\lambda
f(w)$

Recall that by definition $M=\begin{pmatrix}\mathds{1}_{\frac{n}{2}}&0\\\
0&\mathds{1}_{\frac{n}{2}}\end{pmatrix}\begin{pmatrix}\mu_{1}^{T}\\\
\mu_{1}^{T}\end{pmatrix}$. We then have
$M^{T}M=\begin{pmatrix}\frac{n}{2}&0\\\ 0&\frac{n}{2}\end{pmatrix}$ and
therefore

$\|Mw\|^{2}=\frac{n}{2}((\mu_{1}^{T}w)^{2}+(\mu_{2}^{T}w)^{2})$

Noting that $\|z\|^{2}=n$ and using the square root trick we arrive to:

$\displaystyle\min_{w,\tau\geq 0}\max_{\beta\geq 0}\beta
g^{T}w+\frac{\beta}{2\tau}+\frac{\beta\tau}{2}(n\sigma^{2}\|w\|^{2}+\frac{n}{2}(\mu_{1}^{T}w)^{2}+\frac{n}{2}(\mu_{2}^{T}w)^{2}+n-2z^{T}Mw)-\frac{1}{4}\beta^{2}+\lambda
f(w)$

Writing the Fenchel dual for each of $(\mu_{1}^{T}w)^{2}$ and
$(\mu_{2}^{T}w)^{2}$ we get:

$\displaystyle\min_{w,\tau\geq 0}\max_{\beta\geq 0,\gamma_{1},\gamma_{2}}\beta
g^{T}w+\frac{\beta}{2\tau}+\frac{\beta\tau}{2}(n\sigma^{2}\|w\|^{2}+\frac{n}{2}\gamma_{1}(\mu_{1}^{T}w)-\frac{n}{8}\gamma_{1}^{2}+\frac{n}{2}\gamma_{2}(\mu_{2}^{T}w)-\frac{n}{8}\gamma_{2}^{2}+n-2z^{T}Mw)-\frac{1}{4}\beta^{2}+\lambda
f(w)$

Open $f(w)$ up as $\sum_{i=1}^{d}f_{i}(w_{i})$. The objective above can be
rewritten as:

$\displaystyle\min_{\tau\geq 0}\max_{\beta\geq
0,\gamma_{1},\gamma_{2}}\frac{\beta}{2\tau}+\frac{\beta\tau}{2}(-\frac{n}{8}\gamma_{1}^{2}-\frac{n}{8}\gamma_{2}^{2}+n)-\frac{1}{4}\beta^{2}+$
$\displaystyle+\min_{w}\beta g^{T}w+\frac{\beta\tau
n\sigma^{2}}{2}\|w\|^{2}+\frac{\beta\tau
n}{4}\gamma_{1}(\mu_{1}^{T}w)+\frac{\beta\tau
n}{4}\gamma_{2}(\mu_{2}^{T}w)-\beta\tau
z^{T}Mw+\lambda\sum_{i=1}^{d}f_{i}(w_{i})$

We will recover the optimal $w$ now. Since the first part of the expression
above is independent of $w$, we will put it aside for a time being and look
only at the second one:

$\displaystyle\min_{w}\beta g^{T}w+\frac{\beta\tau
n\sigma^{2}}{2}\|w\|^{2}+\frac{n\beta\tau}{4}\gamma_{1}(\mu_{1}^{T}w)+\frac{n\beta\tau}{4}\gamma_{2}(\mu_{2}^{T}w)-\beta\tau
z^{T}Mw+\lambda\sum_{i=1}^{d}f_{i}(w_{i})=$
$\displaystyle=\sum_{i=1}^{d}\min_{w_{i}}\frac{\beta\tau
n\sigma^{2}}{2}w_{i}^{2}+\beta(g+\frac{n\tau}{4}\gamma_{1}\mu_{1}+\frac{n\tau}{4}\gamma_{2}\mu_{2}-\tau
M^{T}z)_{i}w_{i}+\lambda f_{i}(w_{i})=$
$\displaystyle=\sum_{i=1}^{d}\min_{w_{i}}\frac{\beta\tau
n\sigma^{2}}{2}(w_{i}+\frac{1}{n\tau\sigma^{2}}(g+\frac{n\tau}{4}\gamma_{1}\mu_{1}+\frac{n\tau}{4}\gamma_{2}\mu_{2}-\tau
M^{T}z)_{i})^{2}+\lambda
f_{i}(w_{i})-\frac{\beta}{2n\tau\sigma^{2}}(g+\frac{n\tau}{4}\gamma_{1}\mu_{1}+\frac{n\tau}{4}\gamma_{2}\mu_{2}-\tau
M^{T}z)_{i}^{2}$ (6)

The expression above is equal to the following by definition of the Moreau
envelope:

$\displaystyle-\frac{\beta}{2n\tau\sigma^{2}}\sum_{i=1}^{d}(g+\frac{n\tau}{4}\gamma_{1}\mu_{1}+\frac{n\tau}{4}\gamma_{2}\mu_{2}-\tau
M^{T}z)_{i}^{2}+\lambda\sum_{i=1}^{d}e_{f_{i}}(\frac{1}{n\tau\sigma^{2}}(g+\frac{n\tau}{4}\gamma_{1}\mu_{1}+\frac{n\tau}{4}\mu_{2}\gamma_{2}-\tau
M^{T}z)_{i};\frac{\lambda}{\beta\tau n\sigma^{2}})$

We will simplify the objective further. Notice that also by definition
$M^{T}z=\frac{n}{2}(1-2c)(\mu_{1}-\mu_{2})$. This equality can be plugged in
into the corresponding part of the objective:

$\displaystyle
g+\frac{n\tau}{4}\gamma_{1}\mu_{1}+\frac{n\tau}{4}\gamma_{2}\mu_{2}-\tau
M^{T}z=g+(\frac{n\tau}{4}\gamma_{1}-\frac{n\tau}{2}(1-2c))\mu_{1}+(\frac{n\tau}{4}\gamma_{2}+\frac{n}{2}\tau(1-2c))\mu_{2}$

Recall that $\mu_{1}$ and $\mu_{2}$ are i.i.d Gaussian by assumption.
Therefore, we have the following equality asymptotically when $d\to\infty$,
where $G\sim\mathcal{N}(0,1)$:

$\displaystyle
d\frac{1}{d}\sum_{i=1}^{d}e_{f_{i}}(\frac{1}{n\tau\sigma^{2}}(g+\frac{n\tau}{4}\gamma_{1}\mu_{1}+\frac{n\tau}{4}\mu_{2}\gamma_{2}-\tau
M^{T}z)_{i};\frac{\lambda}{\beta\tau n\sigma^{2}})\rightarrow$ $\displaystyle
d\mathbb{E}e_{f_{i}}(\frac{1}{n\tau\sigma^{2}}\sqrt{(\frac{n\tau}{4}\gamma_{1}-\frac{n\tau}{2}(1-2c))^{2}+(\frac{n\tau}{4}\gamma_{2}+\frac{n\tau}{2}(1-2c))^{2}+2r(\frac{n\tau}{4}\gamma_{1}-\frac{n\tau}{2}(1-2c))(\frac{n\tau}{4}\gamma_{2}+\frac{n\tau}{2}(1-2c))+\sigma^{2}}G;\frac{\lambda}{\beta\tau
n\sigma^{2}})$

Note that we can take $\gamma_{1}=\gamma=-\gamma_{2}$ because our model for
the data is symmetric w.r.t to the substitution
$\mu_{1}\xleftrightarrow{}-\mu_{2}$. Thus, the expression above simplifies
into:

$\displaystyle
d\mathbb{E}e_{f_{i}}(\sqrt{\frac{1-r}{2\sigma^{4}}(\frac{\gamma}{2}-1+2c)^{2}+\frac{1}{n^{2}\tau^{2}\sigma^{2}}}G;\frac{\lambda}{\beta\tau
n\sigma^{2}})$

Note also that

$\displaystyle\sum_{i=1}^{d}(g+(\frac{n\tau}{4}\gamma-\frac{n\tau}{2}(1-2c))(\mu_{1}-\mu_{2}))_{i}^{2}=\|g\|^{2}+(\frac{n\tau}{4}\gamma-\frac{n\tau}{2}(1-2c))^{2}\|\mu_{1}-\mu_{2}\|^{2}=d\sigma^{2}+2d(1-r)(\frac{n\tau}{4}\gamma-\frac{n\tau}{2}(1-2c))^{2}$

Putting all derivations above together, we are left with the following
optimization problem:

$\displaystyle\min_{\tau\geq 0}\max_{\beta\geq
0,\gamma}\frac{\beta}{2\tau}+\frac{\beta\tau}{2}(-\frac{n}{4}\gamma^{2}+n)-\frac{1}{4}\beta^{2}-\frac{d\beta}{2n\tau}-\frac{nd(1-r)\beta\tau}{4\sigma^{2}}(\frac{\gamma}{2}-1+2c)^{2}$
$\displaystyle+d\lambda\mathbb{E}e_{f_{i}}(\sqrt{\frac{1-r}{2\sigma^{4}}(\frac{\gamma}{2}-1+2c)^{2}+\frac{1}{n^{2}\tau^{2}\sigma^{2}}}G;\frac{\lambda}{\beta\tau
n\sigma^{2}})$

Denoting
$\Xi(\gamma,\tau):=\sqrt{\frac{1-r}{2\sigma^{4}}(\frac{\gamma}{2}-1+2c)^{2}+\frac{1}{n^{2}\tau^{2}\sigma^{2}}}$,
we arrive to the desired result:

$\displaystyle\min_{\tau\geq 0}\max_{\beta\geq
0,\gamma}\frac{\beta}{2\tau}(1-\frac{d}{n})+\frac{\beta\tau}{2}(-\frac{n}{4}\gamma^{2}-\frac{nd(1-r)}{2\sigma^{2}}(\frac{\gamma}{2}-1+2c)^{2}+n)-\frac{1}{4}\beta^{2}$
$\displaystyle+d\lambda\mathbb{E}e_{f_{i}}(\Xi(\gamma,\tau)G;\frac{\lambda}{\beta\tau
n\sigma^{2}})$

∎

###  C.2 Proof of Theorem 3

###### Proof.

Apply the same reasoning as in the proof of Theorem 2 up to the equation
(C.1). We have:

$\displaystyle\sum_{i=1}^{d}\min_{w_{i}}\frac{\beta\tau
n\sigma^{2}}{2}(w_{i}+\frac{1}{n\tau\sigma^{2}}(g+\frac{n\tau}{4}\gamma_{1}\mu_{1}+\frac{n\tau}{4}\gamma_{2}\mu_{2}-\tau
M^{T}z)_{i})^{2}+\lambda
w_{i}^{2}-\frac{\beta}{2n\tau\sigma^{2}}(g+\frac{n\tau}{4}\gamma_{1}\mu_{1}+\frac{n\tau}{4}\gamma_{2}\mu_{2}-\tau
M^{T}z)_{i}^{2}$

Taking the derivative by $w$ of the expression above and setting it to $0$ we
get:

$\beta\tau
n\sigma^{2}(w+\frac{1}{n\tau\sigma^{2}}(g+\frac{n\tau}{4}\gamma_{1}\mu_{1}+\frac{n\tau}{4}\gamma_{2}\mu_{2}-\tau
M^{T}z))+2\lambda w=0$

Since $M^{T}z=\frac{n}{2}(1-2c)(\mu_{1}-\mu_{2})$, we arrive at:

$w=-\frac{\beta\tau
n\sigma^{2}(g+\frac{n\tau}{4}\gamma_{1}\mu_{1}+\frac{n\tau}{4}\gamma_{2}\mu_{2}-\frac{n\tau}{2}(1-2c)(\mu_{1}-\mu_{2}))}{n\tau\sigma^{2}(\beta\tau
n\sigma^{2}+2\lambda)}$

We conclude from the identity above that $w$ belongs in the span of
$g,\mu_{1}$ and $\mu_{2}$. Moreover, since this identity is invariant under
the transformation
$(\gamma_{1},\gamma_{2},\mu_{1},\mu_{2})\to(-\gamma_{2},\gamma_{1},-\mu_{2},\mu_{1})$,
we also conclude that $\gamma_{1}=-\gamma_{2}$. Put together, this implies
that $w$ can be written as $w=\alpha g+\gamma(\mu_{1}-\mu_{2})$. Now return to
the equation (5) derived the proof of Theorem 2 and specify it to the case
$f=\ell_{2}$:

$\displaystyle\min_{w}\max_{\beta\geq 0}\beta
g^{T}w+\beta\|h\|w\|+Mw-z\|-\frac{1}{4}\beta^{2}+\lambda\|w\|^{2}$

Performing optimization over $\beta$ we obtain:

$\displaystyle\min_{w}(g^{T}w+\|h\|w\|+Mw-z\|)_{\geq
0}^{2}+\lambda\|w\|_{2}^{2}$ (7)

Denote:

$\displaystyle\Omega(\alpha,\gamma)$
$\displaystyle=\alpha^{2}\sigma^{2}d+2d(1-r)\gamma^{2}$
$\displaystyle\Theta(\alpha,\gamma)$
$\displaystyle=n(1-c)(d(1-r)\gamma-1)^{2}+nc(d(1-r)\gamma+1)^{2}$

It is straightforward to open up each term from the objective above in terms
of $\alpha$ and $\gamma$:

$\displaystyle g^{T}w=g^{T}(\alpha
g+\gamma(\mu_{1}-\mu_{2}))=\alpha\sigma^{2}d$ $\displaystyle\|w\|^{2}=\|\alpha
g+\gamma(\mu_{1}-\mu_{2})\|^{2}=\alpha^{2}\sigma^{2}d+2d(1-r)\gamma^{2}=\Omega(\alpha,\gamma)$
$\displaystyle\|h\|w\|+Mw-z\|=\sqrt{n\sigma^{2}\|w\|^{2}+\|Mw-z\|^{2}}=$
$\displaystyle=\sqrt{n\sigma^{2}\|w\|^{2}+\frac{n(1-c)}{2}((\mu_{1}^{T}w-1)^{2}+(\mu_{2}^{T}w+1)^{2})+\frac{nc}{2}((\mu_{1}^{T}w+1)^{2}+(\mu_{2}^{T}w-1)^{2})}=$
$\displaystyle=\sqrt{n\sigma^{2}\Omega(\alpha,\gamma)+\Theta(\alpha,\gamma)}$

Plugging these into equation (7), we get the desired objective:

$\min_{\alpha,\gamma}(\alpha\sigma^{2}d+\sqrt{n\sigma^{2}\Omega(\alpha,\gamma)+\Theta(\alpha,\gamma)})_{\geq
0}^{2}+\lambda\Omega(\alpha,\gamma)$

Using Lemma 1 we also derive:

$E(w)=\frac{1}{2}Q\left(\frac{\mu_{1}^{T}w}{\sigma\|w\|}\right)+\frac{1}{2}Q\left(\frac{-\mu_{2}^{T}w}{\sigma\|w\|}\right)=Q\left(\frac{\mu_{1}^{T}w}{\sigma\|w\|}\right)=Q\left(\frac{\mu_{1}^{T}w}{\sqrt{\sigma^{2}\Omega(\alpha,\gamma)}}\right)=Q\left(\frac{\gamma
d(1-r)}{\sqrt{\alpha^{2}\sigma^{4}d+2\sigma^{2}\gamma^{2}d(1-r)}}\right)$

∎

###  C.3 Proof of Theorem 4

###### Proof.

Starting from the equation (C.1) derived in the proof of Theorem 2 applied to
$f=\ell_{1}$:

$\displaystyle\min_{w,\tau\geq 0}\max_{\beta\geq 0}\beta
g^{T}w+\frac{\beta}{2\tau}+\frac{\beta\tau}{2}(n\sigma^{2}\|w\|^{2}+\frac{n}{2}(\mu_{1}^{T}w)^{2}+\frac{n}{2}(\mu_{2}^{T}w)^{2}+n-2z^{T}Mw)-\frac{1}{4}\beta^{2}+\lambda\|w\|_{1}$

Using Fenchel duality and introducing $\gamma_{1},\gamma_{2}$ yields the
following expression:

$\displaystyle\min_{w,\tau\geq 0}\max_{\beta\geq 0,\gamma_{1},\gamma_{2}}\beta
g^{T}w+\frac{\beta}{2\tau}+\frac{\beta\tau}{2}(n\sigma^{2}\|w\|^{2}+\frac{n}{2}\gamma_{1}(\mu_{1}^{T}w)-\frac{n}{8}\gamma_{1}^{2}+\frac{n}{2}\gamma_{2}(\mu_{2}^{T}w)-\frac{n}{8}\gamma_{2}^{2}+n-2z^{T}Mw)-\frac{1}{4}\beta^{2}+\lambda\|w\|_{1}$

Due to the symmetry to the transformation
$(\gamma_{1},\gamma_{2},\mu_{1},\mu_{2})\to(-\gamma_{2},\gamma_{1},-\mu_{2},\mu_{1})$,
we have $\gamma_{1}=-\gamma_{2}=:\gamma$ leading to the following optimization
problem:

$\displaystyle\min_{w,\tau\geq 0}\max_{\beta\geq 0,\gamma}\beta
g^{T}w+\frac{\beta}{2\tau}+\frac{\beta\tau}{2}(n\sigma^{2}\|w\|^{2}+n\gamma(\mu_{1}^{T}w)-\frac{n}{4}\gamma^{2}+n-2z^{T}M)-\frac{1}{4}\beta^{2}+\lambda\|w\|_{1}$

Solving for $w$ we get:

$\displaystyle w_{opt}$
$\displaystyle=\begin{cases}\frac{X}{\sigma^{2}}-\lambda\frac{1}{n\beta\tau\sigma^{2}}&X>\lambda\frac{1}{n\beta\tau}\\\
\frac{X}{\sigma^{2}}+\lambda\frac{1}{n\beta\tau\sigma^{2}}&X<-\lambda\frac{1}{n\beta\tau}\\\
0&o.w\end{cases}$

Where

$\displaystyle X$
$\displaystyle=-\frac{1}{n\tau}g_{i}+(\frac{1-2c}{2}-\frac{\gamma}{4})(\mu_{1,i}-\mu_{2,i})\sim\mathcal{N}(0,\tilde{\sigma}^{2})$
$\displaystyle\tilde{\sigma}^{2}$
$\displaystyle=\frac{\sigma^{2}}{n^{2}\tau^{2}}+2(\frac{\gamma}{4}-\frac{1-2c}{2})^{2}(1-r)$

The optimization would then be

$\displaystyle\min_{\tau\geq 0}\max_{\beta\geq 0,\gamma}\beta
g^{T}w_{opt}+\frac{\beta}{2\tau}+\frac{\beta\tau}{2}(n\sigma^{2}\|w_{opt}\|^{2}+n\gamma(\mu_{1}^{T}w_{opt})-\frac{n}{4}\gamma^{2}+n-2z^{T}Mw_{opt})-\frac{1}{4}\beta^{2}+\lambda\|w_{opt}\|_{1}$

Now we will plug in $w_{opt}$ and calculate each term. The first term
concentrates to

$\displaystyle
g^{T}w_{opt}=-\frac{2d}{n\tau}Q(\frac{\lambda}{n\beta\tau\tilde{\sigma}})$

Similarly, we have for $\mu_{1}^{T}w_{opt}$ and $z^{T}Mw_{opt}$:

$\displaystyle\mu_{1}^{T}w_{opt}=d\mathbb{E}\mu_{1,i}w_{i}=\frac{d}{\sigma^{2}}\mathbb{E}\mu_{1,i}X=\frac{2d}{\sigma^{2}}Q(\frac{\lambda}{n\beta\tau\tilde{\sigma}})(\frac{1-2c}{2}-\frac{\gamma}{4})(1-r)$
$\displaystyle
z^{T}Mw_{opt}=\frac{n(1-2c)}{2}(\mu_{1}-\mu_{2})^{T}w_{opt}=\frac{2dn(1-2c)}{\sigma^{2}}Q(\frac{\lambda}{n\beta\tau\tilde{\sigma}})(\frac{1-2c}{2}-\frac{\gamma}{4})(1-r)$

For $\|w_{opt}\|_{1}$ and $\|w_{opt}\|^{2}$ we get:

$\displaystyle\|w_{opt}\|_{1}=d(\mathbb{E}(\frac{X}{\sigma^{2}}-\frac{\lambda}{n\beta\tau\sigma^{2}})\mathds{1}_{X>\frac{\lambda}{n\beta\tau}}+\mathbb{E}(-\frac{X}{\sigma^{2}}-\frac{\lambda}{n\beta\tau\sigma^{2}})\mathds{1}_{X<-\frac{\lambda}{n\beta\tau}})=$
$\displaystyle=\frac{2d\tilde{\sigma}}{\sigma^{2}\sqrt{2\pi}}e^{-\frac{\lambda^{2}}{2(n\beta\tau\tilde{\sigma})^{2}}}-\frac{2d\lambda}{n\beta\tau\sigma^{2}}Q(\frac{\lambda}{n\beta\tau\tilde{\sigma}})$

Denoting $s:=\frac{\tilde{\sigma}n\beta\tau}{\lambda}$

$\displaystyle\|w_{opt}\|^{2}=d\mathbb{E}(\frac{X}{\sigma^{2}}-\frac{\lambda}{n\beta\tau\sigma^{2}})^{2}\mathds{1}_{|X|\geq\frac{\lambda}{n\beta\tau}}=d(\frac{\lambda}{n\beta\tau\sigma^{2}})^{2}[2(s^{2}+1)Q(\frac{1}{s})-\frac{2s}{\sqrt{2\pi}}e^{-\frac{1}{2s^{2}}}]$

Putting the results together, we arrive at the following objective:

$\displaystyle\min_{\tau\geq 0}\max_{\beta\geq
0,\gamma}-\frac{2d\beta}{n\tau}Q(\frac{\lambda}{n\beta\tau\tilde{\sigma}})+\frac{\beta}{2\tau}+\frac{\beta\tau
n}{2}(d\sigma^{2}(\frac{\lambda}{n\beta\tau\sigma^{2}})^{2}[2(s^{2}+1)Q(\frac{1}{s})-\frac{2s}{\sqrt{2\pi}}e^{-\frac{1}{2s^{2}}}]+\frac{2\gamma
d}{\sigma^{2}}Q(\frac{\lambda}{n\beta\tau\tilde{\sigma}})(\frac{1-2c}{2}-\frac{\gamma}{4})(1-r))+$
$\displaystyle+\frac{\beta\tau
n}{2}(-\frac{\gamma^{2}}{4}+1-\frac{4d(1-2c)}{\sigma^{2}}Q(\frac{\lambda}{n\beta\tau\tilde{\sigma}})(\frac{1-2c}{2}-\frac{\gamma}{4})(1-r))-\frac{1}{4}\beta^{2}+\frac{2d\lambda\tilde{\sigma}}{\sigma^{2}\sqrt{2\pi}}e^{-\frac{\lambda^{2}}{2(n\beta\tau\tilde{\sigma})^{2}}}-\frac{2d\lambda^{2}}{n\beta\tau\sigma^{2}}Q(\frac{\lambda}{n\beta\tau\tilde{\sigma}})$

To calculate the sparsity rate, we analyze the probability of $w_{opt,i}$
attaining non-zero values which is equivalent to the occurrence of the event
$\\{|X|>\frac{\lambda}{n\beta\tau}\\}$:

$\displaystyle\mathbb{P}(w_{i}\neq
0)=\mathbb{P}\left(|X|>\frac{\lambda}{n\beta\tau}\right)$

A straightforward calculation of integrals yields
$\mathbb{P}(|X|>\frac{\lambda}{n\beta\tau})=2Q(\frac{\lambda}{n\beta\tau\tilde{\sigma}})$
and therefore $\mathbb{P}(w_{i}\neq
0)=2Q(\frac{\lambda}{n\beta\tau\tilde{\sigma}})$. Subsequently, the solution
is $k$-sparse, where $k=\lfloor
2dQ(\frac{\lambda}{n\beta\tau\tilde{\sigma}})\rfloor$. ∎

###  C.4 Proof of Theorem 5

###### Proof.

Starting from equation (C.1) again, we introduce the $\ell_{\infty}$
regularization term as a constraint using a new variable $\delta$:

$\displaystyle\min_{\|w\|_{\infty}\leq\frac{\delta}{\lambda},\delta,\tau\geq
0}\max_{\beta\geq 0}\beta
g^{T}w+\frac{\beta}{2\tau}+\frac{\beta\tau}{2}(n\sigma^{2}\|w\|^{2}+\frac{n}{2}(\mu_{1}^{T}w)^{2}+\frac{n}{2}(\mu_{2}^{T}w)^{2}+n-2z^{T}Mw)-\frac{1}{4}\beta^{2}+\delta$

Using Fenchel duality and introducing $\gamma_{1},\gamma_{2}$ yields the
following expression:

$\displaystyle\min_{\|w\|_{\infty}\leq\frac{\delta}{\lambda},\delta,\tau\geq
0}\max_{\beta\geq 0,\gamma_{1},\gamma_{2}}\beta
g^{T}w+\frac{\beta}{2\tau}+\frac{\beta\tau}{2}(n\sigma^{2}\|w\|^{2}+\frac{n}{2}\gamma_{1}(\mu_{1}^{T}w)-\frac{n}{8}\gamma_{1}^{2}+\frac{n}{2}\gamma_{2}(\mu_{2}^{T}w)-\frac{n}{8}\gamma_{2}^{2}+n-2z^{T}Mw)-\frac{1}{4}\beta^{2}+\delta$

Due to the same symmetry as in the proof of the previous theorem, it holds
that $\gamma_{1}=-\gamma_{2}=:\gamma$ and the objective turns into

$\displaystyle\min_{\|w\|_{\infty}\leq\frac{\delta}{\lambda},\delta,\tau\geq
0}\max_{\beta\geq 0,\gamma}\beta
g^{T}w+\frac{\beta}{2\tau}+\frac{\beta\tau}{2}(n\sigma^{2}\|w\|^{2}+\frac{n}{2}\gamma(\mu_{1}^{T}w)-\frac{n}{4}\gamma^{2}-\frac{n}{2}\gamma(\mu_{2}^{T}w)+n-2z^{T}Mw)-\frac{1}{4}\beta^{2}+\delta$

Now we can take derivative w.r.t $w$ and find the optimal solution, $w_{opt}$

$\displaystyle(w_{opt})_{i}=\begin{cases}\frac{\delta}{\lambda}&\frac{1}{{n\tau\sigma^{2}}}(\tau
M^{T}z-g-\frac{n\tau\gamma}{4}\mu_{1}+\frac{n\tau\gamma}{4}\mu_{2})_{i}>\frac{\delta}{\lambda}\\\
\frac{1}{{n\tau\sigma^{2}}}(\tau
M^{T}z-g-\frac{n\tau\gamma}{4}\mu_{1}+\frac{n\tau\gamma}{4}\mu_{2})_{i}&-\frac{\delta}{\lambda}\leq\frac{1}{{n\tau\sigma^{2}}}(\tau
M^{T}z-g-\frac{n\tau\gamma}{4}\mu_{1}+\frac{n\tau\gamma}{4}\mu_{2})_{i}\leq\frac{\delta}{\lambda}\\\
-\frac{\delta}{\lambda}&\frac{1}{{n\tau\sigma^{2}}}(\tau
M^{T}z-g-\frac{n\tau\gamma}{4}\mu_{1}+\frac{n\tau\gamma}{4}\mu_{2})_{i}<-\frac{\delta}{\lambda}\end{cases}$

We note that $M^{T}z=\frac{n}{2}(1-2c)(\mu_{1}-\mu_{2})$ and thus

$\displaystyle
g+\frac{n\tau}{4}\gamma\mu_{1}-\frac{n\tau}{4}\gamma\mu_{2}-\tau
M^{T}z=g+(\frac{n\tau}{4}\gamma-\frac{n\tau}{2}(1-2c))\mu_{1}+(-\frac{n\tau}{4}\gamma+\frac{n}{2}\tau(1-2c))\mu_{2}$

Then plugging in the previous expression,

$\displaystyle(w_{opt})_{i}=\begin{cases}\frac{\delta}{\lambda}&\frac{1}{{2\sigma^{2}}}(-(\frac{\gamma}{2}-1+2c)(\mu_{1}-\mu_{2})-\frac{2}{n\tau}g)_{i}>\frac{\delta}{\lambda}\\\
\frac{1}{{2\sigma^{2}}}(-(\frac{\gamma}{2}-1+2c)(\mu_{1}-\mu_{2})-\frac{2}{n\tau}g)_{i}&-\frac{\delta}{\lambda}\leq\frac{1}{{2\sigma^{2}}}(-(\frac{\gamma}{2}-1+2c)(\mu_{1}-\mu_{2})-\frac{2}{n\tau}g)_{i}\leq\frac{\delta}{\lambda}\\\
-\frac{\delta}{\lambda}&\frac{1}{{2\sigma^{2}}}(-(\frac{\gamma}{2}-1+2c)(\mu_{1}-\mu_{2})-\frac{2}{n\tau}g)_{i}<-\frac{\delta}{\lambda}\end{cases}$

Let
$\Xi(\gamma,\tau):=\sqrt{\frac{1-r}{2\sigma^{4}}(\frac{\gamma}{2}-1+2c)^{2}+\frac{1}{n^{2}\tau^{2}\sigma^{2}}}$.
Using the assumptions on $\mu_{1},\mu_{2}$ we model the randomness coming from
$\mu_{1},\mu_{2},g$ by a single $G_{i}\sim\mathcal{N}(0,1)$:

$\displaystyle(w_{opt})_{i}=\begin{cases}\frac{\delta}{\lambda}&\Xi(\gamma,\tau)G_{i}>\frac{\delta}{\lambda}\\\
\Xi(\gamma,\tau)G_{i}&-\delta\leq\Xi(\gamma,\tau)G_{i}\leq\frac{\delta}{\lambda}\\\
-\frac{\delta}{\lambda}&\Xi(\gamma,\tau)G_{i}<-\frac{\delta}{\lambda}\end{cases}$

After finding $w_{opt}$ we plug its value into the original optimization

$\displaystyle\min_{\tau\geq 0}\max_{\beta\geq
0,\gamma}\frac{\beta}{2\tau}+\frac{\beta\tau}{2}(-\frac{n}{4}\gamma^{2}+n)-\frac{1}{4}\beta^{2}+\delta$
$\displaystyle+\frac{n\sigma^{2}\beta\tau}{2}\|w_{opt}\|^{2}+(\beta
g+\frac{\beta\tau n}{4}\gamma\mu_{1}-\frac{\beta\tau n}{4}\mu_{2}-\beta\tau
M^{T}z)^{T}w_{opt}$

It remains to express $\|w_{opt}\|^{2}$ and $(\beta g+\frac{\beta\tau
n}{4}\gamma\mu_{1}-\frac{\beta\tau n}{4}\mu_{2}-\beta\tau M^{T}z)^{T}w_{opt}$
in terms of the scalars. For $\|w_{opt}\|^{2}$ we have

$\displaystyle\|w_{opt}\|^{2}=\frac{d}{\sqrt{2\pi}}\int_{\lambda\Xi|G|\geq\delta}\frac{\delta^{2}}{\lambda^{2}}exp(-\frac{G^{2}}{2})dG+\frac{d\Xi^{2}}{\sqrt{2\pi}}\int_{\lambda\Xi|G|\leq\delta}G^{2}exp(-\frac{G^{2}}{2})dG=$
$\displaystyle\frac{2d\delta^{2}}{\lambda^{2}}Q(\frac{\delta}{\lambda\Xi})-\frac{2d\delta\Xi}{\lambda\sqrt{2\pi}}exp(-\frac{\delta^{2}}{2\lambda^{2}\Xi^{2}})+d\Xi^{2}(1-2Q(\frac{\delta}{\lambda\Xi}))$

For inner product we observe the following concentration phenomenon:

$\displaystyle(g+\frac{n\tau}{4}\gamma_{1}\mu_{1}+\frac{n\tau}{4}\gamma_{2}\mu_{2}-\tau
M^{T}z)^{T}w_{opt}=(g+(\frac{n\tau}{4}\gamma_{1}-\frac{n\tau}{2}(1-2c))\mu_{1}+(\frac{n\tau}{4}\gamma_{2}+\frac{n}{2}\tau(1-2c))\mu_{2})^{T}w_{opt}$
$=-dn\sigma^{2}\tau\Xi\mathbb{E}Gw_{opt,i}$

Thus we have:

$\displaystyle\mathbb{E}Gw_{opt,i}=\frac{\delta}{\lambda\sqrt{2\pi}}\int_{\lambda\Xi
G\geq\delta}Gexp(-\frac{G^{2}}{2})dG-\frac{\delta}{\lambda\sqrt{2\pi}}\int_{\lambda\Xi
G\leq-\delta}Gexp(-\frac{G^{2}}{2})dG+\frac{\Xi}{\sqrt{2\pi}}\int_{\lambda\Xi|G|\leq\delta}G^{2}exp(-\frac{G^{2}}{2})dG=$
$=\Xi(1-2Q(\frac{\delta}{\lambda\Xi}))$

Therefore:

$\displaystyle\frac{n\sigma^{2}\beta\tau}{2}\|w_{opt}\|^{2}+(\beta
g+\frac{\beta\tau}{2}\frac{n}{2}\gamma_{1}\mu_{1}+\frac{\beta\tau}{2}\frac{n}{2}\gamma_{2}\mu_{2}-\beta\tau
M^{T}z)^{T}w_{opt}=$
$\displaystyle-\frac{nd\sigma^{2}\beta\tau\delta\Xi}{\lambda\sqrt{2\pi}}exp(-\frac{\delta^{2}}{2\lambda^{2}\Xi^{2}})+nd\sigma^{2}\beta\tau(\Xi^{2}+\frac{\delta^{2}}{\lambda^{2}})Q(\frac{\delta}{\lambda\Xi})-\frac{nd\sigma^{2}\beta\tau\Xi^{2}}{2}$

The optimization problem turns into:

$\displaystyle\min_{\tau,\delta\geq 0}\max_{\beta\geq
0,\gamma}\frac{\beta}{2\tau}+\frac{\beta\tau}{2}(-\frac{n}{4}\gamma^{2}+n)-\frac{1}{4}\beta^{2}+\delta$
$\displaystyle-\frac{nd\sigma^{2}\beta\tau\delta\Xi}{\lambda\sqrt{2\pi}}exp(-\frac{\delta^{2}}{2\lambda^{2}\Xi^{2}})+nd\sigma^{2}\beta\tau(\Xi^{2}+\frac{\delta^{2}}{\lambda^{2}})Q(\frac{\delta}{\lambda\Xi})-\frac{nd\sigma^{2}\beta\tau\Xi^{2}}{2}$

Performing the optimization over $\beta$ we get the final expression:

$\displaystyle\min_{\tau,\delta\geq
0}\max_{\gamma}\left(\frac{1}{2\tau}+\frac{\tau}{2}(-\frac{n}{4}\gamma^{2}+n)-\frac{nd\sigma^{2}\tau\delta\Xi}{\lambda\sqrt{2\pi}}exp(-\frac{\delta^{2}}{2\lambda^{2}\Xi^{2}})+nd\sigma^{2}\tau(\Xi^{2}+\frac{\delta^{2}}{\lambda^{2}})Q(\frac{\delta}{\lambda\Xi})-\frac{nd\sigma^{2}\tau\Xi^{2}}{2}\right)^{2}_{\geq
0}+\delta$

Considering the expression for $w_{opt}$, it can also be seen that

$\displaystyle
d\mathbb{P}(|w_{opt,i}|=\frac{\delta}{\lambda})=d\mathbb{P}(|\Xi
G|\geq\frac{\delta}{\lambda})=\frac{d}{\sqrt{2\pi}}\int_{\lambda\Xi|G|\geq\delta}exp(-\frac{G^{2}}{2})dG=2dQ(\frac{\delta}{\lambda\Xi})$

∎

###  C.5 Calculating the generalization error

###### Proof.

As an attentive reader might have noticed, we omitted derivations for the
expressions for the generalization error from the proofs of Theorems 2, 4, 5.
The purpose of this subsection is filling in this gap.

Applying Lemma 1 and using that $\mu_{1}^{T}w=-\mu_{2}^{T}w$ holds for the
optimal $w$ from each of Theorems 2, 4, 5, we have
$E(w)=Q(\frac{\mu_{1}^{T}w}{\sigma\|w\|})$. Thus, our goal is to determine the
values of $\mu_{1}^{T}w$ and $\|w\|$. The former is immediate, as
$\gamma=2\mu_{1}^{T}w$. The latter is less trivial but still straightforward;
by definition,

$n\sigma^{2}\|w\|^{2}+\|Mw-z\|^{2}=\frac{1}{\tau^{2}}$

and

$\|Mw-z\|^{2}=\frac{n}{2}(1-c)(\mu_{1}^{T}w-1)^{2}+\frac{n}{2}(1-c)(\mu_{2}^{T}w+1)^{2}+\frac{nc}{2}(\mu_{1}^{T}w+1)^{2}+\frac{nc}{2}(\mu_{2}^{T}w-1)^{2}=$
$=n(1-c)(\frac{\gamma}{2}-1)^{2}+nc(\frac{\gamma}{2}+1)^{2}$

We derive

$\|w\|^{2}=\frac{\frac{1}{\tau^{2}}-n(1-c)(\frac{\gamma}{2}-1)^{2}-nc(\frac{\gamma}{2}+1)^{2}}{n\sigma^{2}}$

Putting the equalities above together yields

$E(w)=Q(\frac{\gamma}{2\sigma\|w\|})=Q(\frac{\gamma\sigma\sqrt{n}}{2\sigma\sqrt{\frac{1}{\tau^{2}}-n(1-c)(\frac{\gamma}{2}-1)^{2}-nc(\frac{\gamma}{2}+1)^{2}}})=Q(\frac{\gamma}{2\sqrt{\frac{1}{n\tau^{2}}-(1-c)(\frac{\gamma}{2}-1)^{2}-c(\frac{\gamma}{2}+1)^{2}}})$

∎

##  Appendix D DERIVATIONS BEHIND THE REMARKS

Recall from Section 3.4 that the problem is equivalent to analyzing the
following:

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

To gain more insight, we would like to apply a unitary transformation $U$,
such that

$UM=\begin{pmatrix}\sqrt{\frac{n}{2}}\mu_{1}^{T}\\\
\sqrt{\frac{n}{2}}\mu_{2}^{T}\\\ 0\dots 0\\\ \dots\\\ 0\dots
0\end{pmatrix}\text{ and }Uz=\begin{pmatrix}\sqrt{\frac{n}{2}}(1-2c)\\\
-\sqrt{\frac{n}{2}}(1-2c)\\\ 2\sqrt{c(1-c)n}\\\ 0\\\ \dots\\\ 0\\\
\end{pmatrix}$

To explain why it exists, note that the desired matrix equality
$UM=\begin{pmatrix}\sqrt{\frac{n}{2}}\mu_{1}^{T}\\\
\sqrt{\frac{n}{2}}\mu_{2}^{T}\\\ 0\dots 0\\\ \dots\\\ 0\dots 0\end{pmatrix}$
is guaranteed by the following two vector equalities:

$U\begin{pmatrix}0_{\frac{n}{2}}\\\
1_{\frac{n}{2}}\end{pmatrix}=\begin{pmatrix}\sqrt{\frac{n}{2}}\\\ 0\\\
\dots\\\ 0\end{pmatrix}\text{ and }U\begin{pmatrix}1_{\frac{n}{2}}\\\
0_{\frac{n}{2}}\end{pmatrix}=\begin{pmatrix}0\\\ \sqrt{\frac{n}{2}}\\\ 0\\\
\dots\\\ 0\end{pmatrix}$

Due to the defining property of a unitary operator, such a unitary $U$ exists
if and only if it would preserve all pairwise dot products between the vectors
it is defined on. It is easy to see that all the coordinates of the vectors in
the image of $U$ are chosen so that this would indeed be true.

Apply $U$ to the term under the norm in the equation (8). We have:

$\displaystyle\min_{w}\left\|UAw+\begin{pmatrix}\sqrt{\frac{n}{2}}\mu_{1}^{T}\\\
\sqrt{\frac{n}{2}}\mu_{2}^{T}\\\ 0\dots 0\\\ \dots\\\ 0\dots
0\end{pmatrix}w-\begin{pmatrix}\sqrt{\frac{n}{2}}(1-2c)\\\
-\sqrt{\frac{n}{2}}(1-2c)\\\ 2\sqrt{c(1-c)n}\\\ 0\\\ \dots\\\ 0\\\
\end{pmatrix}\right\|_{2}^{2}+\lambda f(w)$ (9)

Since $UA$ has the same distribution as $A$, it can be written as
$UA=\begin{pmatrix}a_{1}\\\ a_{2}\\\ a_{3}\\\ \tilde{A}\end{pmatrix}$, where
$a_{i}\sim\mathcal{N}(0,\sigma^{2}I)$ for each $i=1,2,3$ and
$\tilde{A}\in\mathbb{R}^{(n-3)\times d}$ has its entries
$\tilde{A}_{ij}\sim\mathcal{N}(0,\sigma^{2})$. Also denoting
$\tilde{\mu_{1}}=\mu_{1}+\sqrt{\frac{2}{n}}a_{1}$,
$\tilde{\mu_{2}}=\mu_{2}+\sqrt{\frac{2}{n}}a_{2}$ and $a=a_{3}$, we transform
(9) into the following:

$\displaystyle\min_{w}\|\tilde{A}w\|_{2}^{2}+\frac{n}{2}(\tilde{\mu_{1}}^{T}w-(1-2c))^{2}+\frac{n}{2}(\tilde{\mu_{2}}^{T}w+(1-2c))^{2}+n(\frac{1}{\sqrt{n}}a^{T}w-2\sqrt{c(1-c)})^{2}+\lambda
f(w)$

Applying CGMT to the objective above in the same way as in the proof of
Theorem 2 yields:

$\displaystyle\min_{w}(g^{T}w+\sqrt{n}\sigma\|w\|)_{\geq
0}^{2}+\frac{n}{2}(\tilde{\mu_{1}}^{T}w-(1-2c))^{2}+\frac{n}{2}(\tilde{\mu_{2}}^{T}w+(1-2c))^{2}+n(\frac{1}{\sqrt{n}}a^{T}w-2\sqrt{c(1-c)})^{2}+\lambda
f(w)$ (10)

###  D.1 Derivations behind Remark 1

Specifying equation (10) to the case of $f=\ell_{2}$ we get:

$\displaystyle\min_{w}(g^{T}w+\sqrt{n}\sigma\|w\|)_{\geq
0}^{2}+\frac{n}{2}(\tilde{\mu_{1}}^{T}w-(1-2c))^{2}+\frac{n}{2}(\tilde{\mu_{2}}^{T}w+(1-2c))^{2}+n(\frac{1}{\sqrt{n}}a^{T}w-2\sqrt{c(1-c)})^{2}+\lambda\|w\|^{2}$
(11)

Note that $(g^{T}w+\sqrt{n}\sigma\|w\|)_{\geq 0}^{2}\leq
n\sigma^{2}\|w\|^{2}\ll\lambda\|w\|^{2}$ if $\lambda\gg n\sigma^{2}$. Thus,
the term $(g^{T}w+\sqrt{n}\sigma\|w\|)_{\geq 0}^{2}$ is dominated by the
regularization term, which is why we can drop it in this regime. After doing
so, we get the following objective:

$\displaystyle\min_{w}\frac{n}{2}(\tilde{\mu_{1}}^{T}w-(1-2c))^{2}+\frac{n}{2}(\tilde{\mu_{2}}^{T}w+(1-2c))^{2}+n(\frac{1}{\sqrt{n}}a^{T}w-2\sqrt{c(1-c)})^{2}+\lambda\|w\|^{2}$

We claim that $w$ can be written in the form $w=\alpha g+\beta
a+\gamma_{1}\tilde{\mu_{1}}+\gamma_{2}\tilde{\mu_{2}}$. Indeed, $w$ belongs in
the span of $g,a,\mu_{1}$ and $\mu_{2}$ because all terms of (11) but the last
one depend only on the projections of $w$ onto these directions and the last
term is does not increase if all other directions are dropped from $w$. Note
also that $\gamma_{1}=-\gamma_{2}=:\gamma$ because (11) is invariant under the
transformation
$(\gamma_{1},\gamma_{2},\mu_{1},\mu_{2})\to(-\gamma_{2},\gamma_{1},-\mu_{2},\mu_{1})$.
Hence, $w=\alpha g+\beta a+\gamma(\tilde{\mu_{1}}-\tilde{\mu_{2}})$.

Taking derivative of (11) w.r.t $\beta$:

$\displaystyle
2\sqrt{n}d\sigma^{2}(\frac{d\sigma^{2}}{\sqrt{n}}\beta-2\sqrt{c(1-c)})+2\lambda
d\sigma^{2}\beta=0$
$\displaystyle\sqrt{n}(\frac{d\sigma^{2}}{\sqrt{n}}\beta-2\sqrt{c(1-c)})+\lambda\beta=0$
$\displaystyle(d\sigma^{2}+\lambda)\beta-2\sqrt{nc(1-c)}=0$

For $\gamma$:

$\displaystyle n(d(1-r+\frac{2\sigma^{2}}{n})\gamma-1+2c)+2\lambda\gamma=0$
$\displaystyle(dn(1-r+\frac{2\sigma^{2}}{n})+2\lambda)\gamma-n(1-2c)=0$

We thus obtain:

$\displaystyle\beta=\frac{2\sqrt{nc(1-c)}}{d\sigma^{2}+\lambda}$
$\displaystyle\gamma=\frac{1-2c}{d(1-r+\frac{2\sigma^{2}}{n})+2\frac{\lambda}{n}}$

To calculate the generalization error, note that
$\|w\|^{2}=d(\alpha^{2}\sigma^{2}+\beta^{2}\sigma^{2}+2\gamma^{2}(1-r+\frac{2\sigma^{2}}{n}))$
and $\tilde{\mu_{1}}^{T}w=d\gamma(1-r+\frac{2\sigma^{2}}{n}))$. Since we
deemed the effect of the first term in (11) negligible, we can set $\alpha=0$,
as this parameter does not play any role. The error then equals to the
following:

$\displaystyle
E(w)=Q(\frac{d(1-r)\gamma}{\sigma\sqrt{2d(1-r+\frac{2\sigma^{2}}{n})\gamma^{2}+d\sigma^{2}\beta^{2}}})$

###  D.2 Derivations behind Remark 2

Assume $\sigma\ll\sqrt{n}$ and note that

$\frac{d(1-r)\gamma}{\sigma\sqrt{2d(1-r+\frac{2\sigma^{2}}{n})\gamma^{2}+d\sigma^{2}\beta^{2}}}=\frac{d(1-r)}{\sigma\sqrt{2d(1-r+\frac{2\sigma^{2}}{n})+d\sigma^{2}(\frac{\beta}{\gamma})^{2}}}\approx\frac{d(1-r)}{\sigma\sqrt{2d(1-r)+d\sigma^{2}(\frac{\beta}{\gamma})^{2}}}$

Plugging in the expressions for $\beta$ and $\gamma$ from the previous remark,
we have

$\displaystyle\frac{\beta}{\gamma}\xrightarrow[\lambda\to+\infty]{}\frac{\sqrt{c(1-c)}(1-2c)}{\sqrt{n}}$

Denoting $C=\sqrt{c(1-c)}(1-2c)$, we derive

$\frac{d(1-r)}{\sigma\sqrt{2d(1-r)+d\sigma^{2}(\frac{\beta}{\gamma})^{2}}}\xrightarrow[\lambda\to+\infty]{}\frac{d(1-r)}{\sigma\sqrt{2d(1-r)+\frac{d\sigma^{2}C^{2}}{n}}}$

Since $\sigma\ll\sqrt{n}$, the last term in the denominator can be neglected
and the expression can be approximated as

$\frac{d(1-r)}{\sigma\sqrt{2d(1-r)}}=\frac{\sqrt{d(1-r)}}{\sigma\sqrt{2}}$

###  D.3 Derivations behind Remark 3

In this section we present the optimal values of $\gamma$ and $\beta$ which
are used in the statement of Remark 3 and show that indeed the optimal $w_{i}$
attains the value $0$ except when
$|t_{i}|:=|(\frac{n}{2}\gamma(\tilde{\mu_{1}}-\tilde{\mu_{2}})+\sqrt{n}\beta
a)_{i}|\geq\lambda$. Let us consider the following optimization which comes
from the equation (10):

$\displaystyle\min_{w}(g^{T}w+\sqrt{n}\sigma\|w\|)_{\geq
0}^{2}+\frac{n}{2}(\tilde{\mu_{1}}^{T}w-(1-2c))^{2}+\frac{n}{2}(\tilde{\mu_{2}}^{T}w+(1-2c))^{2}+n(\frac{1}{\sqrt{n}}a^{T}w-2\sqrt{c(1-c)})^{2}+\lambda\|w\|_{1}$

For large enough $\lambda$, in a similar argument to the ridge regression
case, we can neglect the first term because it is dominated by the
regularization term, which yields:

$\displaystyle\min_{w}\frac{n}{2}(\tilde{\mu_{1}}^{T}w-(1-2c))^{2}+\frac{n}{2}(\tilde{\mu_{2}}^{T}w+(1-2c))^{2}+n(\frac{1}{\sqrt{n}}a^{T}w-2\sqrt{c(1-c)})^{2}+\lambda\|w\|_{1}$

Now we introduce $\gamma_{1},\gamma_{2},\beta$ through taking the Fenchel Dual
of the square terms:

$\displaystyle\min_{w}\max_{\gamma_{1},\gamma_{2},\beta}\frac{n}{2}\gamma_{1}(\tilde{\mu_{1}}^{T}w-(1-2c))-\frac{n\gamma_{1}^{2}}{8}+\frac{n}{2}\gamma_{2}(\tilde{\mu_{2}}^{T}w+(1-2c))-\frac{n\gamma_{2}^{2}}{8}+n\beta(\frac{1}{\sqrt{n}}a^{T}w-2\sqrt{c(1-c)})-\frac{n\beta^{2}}{4}+\lambda\|w\|_{1}$

Rearranging the order of optimization to find the optimal w:

$\displaystyle\max_{\gamma_{1},\gamma_{2},\beta}-\frac{n}{2}(1-2c)\gamma_{1}-\frac{n\gamma_{1}^{2}}{8}+\frac{n}{2}(1-2c)\gamma_{2}-\frac{n\gamma_{1}^{2}}{8}-2n\sqrt{c(1-c)}\gamma-\frac{n\beta^{2}}{4}+$
$\displaystyle+\sum_{i=1}^{d}\min_{w_{i}}(\frac{n}{2}\gamma_{1}\tilde{\mu_{1}}+\frac{n}{2}\gamma_{2}\tilde{\mu_{2}}+\sqrt{n}\beta
a)_{i}w_{i}+\lambda|w_{i}|$

The optimization over $w$ reduces to:

$\displaystyle\min_{w_{i}}c_{i}w_{i}+\lambda|w_{i}|=\begin{cases}0&|c_{i}|<\lambda\\\
0&|c_{i}|=\lambda\\\ -\infty&|c_{i}|>\lambda\end{cases}$

Therefore the solution would be:

$\displaystyle w_{opt,i}=\begin{cases}0&|c_{i}|<\lambda\\\
[0,\infty)sign(-c_{i})&|c_{i}|=\lambda\\\ \infty
sign(-c_{i})&|c_{i}|>\lambda\end{cases}$

Note that plugging in $w_{opt,i}$ results in adding the following constraint:

$|(\frac{n}{2}\gamma_{1}\tilde{\mu_{1}}+\frac{n}{2}\gamma_{2}\tilde{\mu_{2}}+\sqrt{n}\beta
a)_{i}|\leq\lambda$

Or overall,

$\max_{i}|(\frac{n}{2}\gamma_{1}\tilde{\mu_{1}}+\frac{n}{2}\gamma_{2}\tilde{\mu_{2}}+\sqrt{n}\beta
a)_{i}|\leq\lambda$

Which is equivalent to:

$\|\frac{n}{2}\gamma_{1}\tilde{\mu_{1}}+\frac{n}{2}\gamma_{2}\tilde{\mu_{2}}+\sqrt{n}\beta
a\|_{\infty}\leq\lambda$

Denote

$\Psi:=\frac{n}{2}\gamma_{1}\tilde{\mu_{1}}+\frac{n}{2}\gamma_{2}\tilde{\mu_{2}}+\sqrt{n}\beta
a$

Using the preceding discussion, the optimization can be written as:

$\displaystyle\max_{\begin{subarray}{c}\gamma_{1},\gamma_{2},\beta\\\
\|\Psi\|_{\infty}\leq\lambda\end{subarray}}-\frac{n}{2}(1-2c)\gamma_{1}-\frac{n\gamma_{1}^{2}}{8}+\frac{n}{2}(1-2c)\gamma_{2}-\frac{n\gamma_{1}^{2}}{8}-2n\sqrt{c(1-c)}\beta-\frac{n\beta^{2}}{4}$

Furthermore, using the assumptions on $\mu_{1},\mu_{2}$, one can observe:

$(\frac{n}{2}\gamma_{1}\tilde{\mu_{1}}+\frac{n}{2}\gamma_{2}\tilde{\mu_{2}}+\sqrt{n}\beta
a)_{i}\stackrel{{\scriptstyle
d}}{{=}}\sqrt{\frac{n^{2}}{4}(1+\frac{2\sigma^{2}}{n})(\gamma_{1}^{2}+\gamma_{2}^{2})+\frac{n^{2}}{2}r\gamma_{1}\gamma_{2}+n\sigma^{2}\beta^{2}}G_{i}$

where $G_{i}\sim\mathcal{N}(0,1)$ and $\stackrel{{\scriptstyle d}}{{=}}$
stands for equality in distribution.

Denote
$q:=\sqrt{\frac{n^{2}}{4}(1+\frac{2\sigma^{2}}{n})(\gamma_{1}^{2}+\gamma_{2}^{2})+\frac{n^{2}}{2}r\gamma_{1}\gamma_{2}+n\sigma^{2}\beta^{2}}$.
Then the equivalent optimization would be:

$\displaystyle\max_{\begin{subarray}{c}\gamma_{1},\gamma_{2},\beta\\\
q\mathbb{E}\|G\|_{\infty}\leq\lambda\end{subarray}}-\frac{n}{2}(1-2c)\gamma_{1}-\frac{n\gamma_{1}^{2}}{8}+\frac{n}{2}(1-2c)\gamma_{2}-\frac{n\gamma_{1}^{2}}{8}-2n\sqrt{c(1-c)}\beta-\frac{n\beta^{2}}{4}$

We know that $\|X\|_{\infty}$ concentrates to
$\mathbb{E}\|X\|_{\infty}=\sqrt{2\log(2d)}$ for i.i.d. standard Gaussians
$X=(X_{1},X_{2},...,X_{d})$ (cf. Gumbel distribution for Gaussian random
variables). Then, using a Lagrange multiplier:

$\displaystyle\max_{\gamma_{1},\gamma_{2},\beta}\min_{\eta\geq
0}-\frac{n}{2}(1-2c)\gamma_{1}-\frac{n\gamma_{1}^{2}}{8}+\frac{n}{2}(1-2c)\gamma_{2}-\frac{n\gamma_{1}^{2}}{8}-2n\sqrt{c(1-c)}\beta-\frac{n\beta^{2}}{4}+$
$\displaystyle+\eta\left(\lambda^{2}-2\left[\frac{n^{2}}{4}(1+\frac{2\sigma^{2}}{n})(\gamma_{1}^{2}+\gamma_{2}^{2})+\frac{n^{2}}{2}r\gamma_{1}\gamma_{2}+n\sigma^{2}\beta^{2}\right]\log(2d)\right)$

Convexity in $\eta$ and concavity in all other variables allow us to swap min
and max:

$\displaystyle\min_{\eta\geq
0}\lambda^{2}\eta++\max_{\gamma_{1},\gamma_{2},\beta}$
$\displaystyle-\begin{pmatrix}\gamma_{1}&\gamma_{2}&\beta&1\end{pmatrix}\begin{pmatrix}\frac{n}{8}+\frac{n^{2}}{2}\eta(1+\frac{2\sigma^{2}}{n})\log(2d)&\frac{n^{2}}{2}r\eta\log(2d)&0&\frac{n}{4}(1-2c)\\\
\frac{n^{2}}{2}r\eta\log(2d)&\frac{n}{8}+\frac{n^{2}}{2}\eta(1+\frac{2\sigma^{2}}{n})\log(2d)&0&-\frac{n}{4}(1-2c)\\\
0&0&\frac{n}{4}+2n\sigma^{2}\eta\log(2d)&n\sqrt{c(1-c)}\\\
\frac{n}{4}(1-2c)&-\frac{n}{4}(1-2c)&n\sqrt{c(1-c)}&0\end{pmatrix}\begin{pmatrix}\gamma_{1}\\\
\gamma_{2}\\\ \beta\\\ 1\end{pmatrix}$

Note that

$\displaystyle\frac{1}{a^{2}-b^{2}}\begin{pmatrix}x&-x\end{pmatrix}\begin{pmatrix}a&-b\\\
-b&a\end{pmatrix}\begin{pmatrix}x\\\
-x\end{pmatrix}=\frac{x^{2}}{a^{2}-b^{2}}\begin{pmatrix}a+b&-b-a\end{pmatrix}\begin{pmatrix}1\\\
-1\end{pmatrix}=\frac{2a+2b}{a^{2}-b^{2}}x^{2}=\frac{2x^{2}}{a-b}$

To do the quadratic optimization, we calculate the Schur Complement:

Wenotethatindeed

γ_1 = - γ_2 =: γ$andsubsequently,\begin{aligned} \min_{\eta\geq
0}\lambda^{2}\eta+\frac{n^{2}}{8}(1-2c)^{2}\frac{1}{\frac{n}{8}+\frac{n^{2}}{2}\eta(1-r+\frac{2\sigma^{2}}{n})\log(2d)}+\frac{n^{2}c(1-c)}{\frac{n}{4}+2n\sigma^{2}\eta\log(2d)}\end{aligned}Consequently,tofind$γ,
β$itsufficestosolvethefollowing1-variableoptimization\begin{aligned}
\min_{\eta\geq
0}\lambda^{2}\eta+\frac{n(1-2c)^{2}}{1+4n\eta(1-r+\frac{2\sigma^{2}}{n})\log(2d)}+\frac{4nc(1-c)}{1+8\sigma^{2}\eta\log(2d)}\end{aligned}Havingfound$η$fromtheaboveoptimization,wecanpluginthevalueof$η$tofind$γ,
β$:\begin{aligned}
\beta=-\frac{4\sqrt{c(1-c)}}{1+8\sigma^{2}\eta\log(2d)},\quad\gamma=-\frac{2(1-2c)}{1+4n\eta(1-r+\frac{2\sigma^{2}}{n})\log(2d)}\end{aligned}Bygoingthroughthismachinery,wereducedacomplicatedoptimizationover3variables,toarathersimpleoptimizationover1variableas$η$isthesolutiontoadegree4equation.\par$

###  D.4 Derivations behind Remark 4

Similar to the previous section, we present an approach through which,
$\gamma,\beta$ can be calculated efficiently. By taking $\lambda$ to be large
enough, we can drop the first term which in turn yields:

$\displaystyle\min_{w}\frac{n}{2}(\tilde{\mu_{1}}^{T}w-(1-2c))^{2}+\frac{n}{2}(\tilde{\mu_{2}}^{T}w+(1-2c))^{2}+n(\frac{1}{\sqrt{n}}a^{T}w-2\sqrt{c(1-c)})^{2}+\lambda\|w\|_{\infty}$

Adding a new variable $\delta$ for $\lambda\|w\|_{\infty}$ we obtain:

$\displaystyle\min_{\|w\|_{\infty}\leq\frac{\delta}{\lambda},\delta\geq
0}\frac{n}{2}(\tilde{\mu_{1}}^{T}w-(1-2c))^{2}+\frac{n}{2}(\tilde{\mu_{2}}^{T}w+(1-2c))^{2}+n(\frac{1}{\sqrt{n}}a^{T}w-2\sqrt{c(1-c)})^{2}+\delta$

Introducing $\gamma_{1},\gamma_{2}$ through Fenchel Dual and changing the
order of optimization we derive the following objective:

$\displaystyle\min_{\delta\geq
0}\delta+\max_{\gamma_{1},\gamma_{2},\beta}-\frac{n}{2}(1-2c)\gamma_{1}-\frac{\gamma_{1}^{2}}{4}+\frac{n}{2}(1-2c)\gamma_{2}-\frac{\gamma_{2}^{2}}{4}-2n\sqrt{c(1-c)}\beta-\frac{\beta^{2}}{4}+$
$\displaystyle+\sum_{i=1}^{d}\min_{|w_{i}|\leq\frac{\delta}{\lambda}}(\frac{n}{2}\gamma_{1}\tilde{\mu_{1}}+\frac{n}{2}\gamma_{2}\tilde{\mu_{2}}+\sqrt{n}\beta
a)_{i}w_{i}$

It is straightforward to see that
$w_{opt,i}=-\frac{\delta}{\lambda}sign((\frac{n}{2}\gamma_{1}\tilde{\mu_{1}}+\frac{n}{2}\gamma_{2}\tilde{\mu_{2}}+\sqrt{n}\beta
a)_{i})$. So, the optimization would be

$\displaystyle\min_{\delta\geq
0}\delta+\max_{\gamma_{1},\gamma_{2},\beta}-\frac{n}{2}(1-2c)\gamma_{1}-\frac{\gamma_{1}^{2}}{4}+\frac{n}{2}(1-2c)\gamma_{2}-\frac{\gamma_{1}^{2}}{4}-2n\sqrt{c(1-c)}\beta-\frac{\beta^{2}}{4}+$
$\displaystyle-\frac{\delta}{\lambda}\|\frac{n}{2}\gamma_{1}\tilde{\mu_{1}}+\frac{n}{2}\gamma_{2}\tilde{\mu_{2}}+\sqrt{n}\beta
a\|_{1}$

Let
$\Psi:=\frac{n}{2}\gamma_{1}\tilde{\mu_{1}}+\frac{n}{2}\gamma_{2}\tilde{\mu_{2}}+\sqrt{n}\beta
a$. Optimizing over $\delta$ yields:

$\displaystyle\max_{\begin{subarray}{c}\gamma_{1},\gamma_{2},\beta\\\
\|\Psi\|_{1}\leq\lambda\end{subarray}}-\frac{n}{2}(1-2c)\gamma_{1}-\frac{\gamma_{1}^{2}}{4}+\frac{n}{2}(1-2c)\gamma_{2}-\frac{\gamma_{1}^{2}}{4}-2n\sqrt{c(1-c)}\beta-\frac{\beta^{2}}{4}$

In a manner similar to the previous section we note:

$(\frac{n}{2}\gamma_{1}\tilde{\mu_{1}}+\frac{n}{2}\gamma_{2}\tilde{\mu_{2}}+\sqrt{n}\beta
a)_{i}\stackrel{{\scriptstyle
d}}{{=}}\sqrt{\frac{n^{2}}{4}(1+\frac{2\sigma^{2}}{n})(\gamma_{1}^{2}+\gamma_{2}^{2})+\frac{n^{2}}{2}r\gamma_{1}\gamma_{2}+n\sigma^{2}\beta^{2}}G_{i}$

with $G_{i}\sim\mathcal{N}(0,1)$. Denoting,
$q:=\sqrt{\frac{n^{2}}{4}(1+\frac{2\sigma^{2}}{n})(\gamma_{1}^{2}+\gamma_{2}^{2})+\frac{n^{2}}{2}r\gamma_{1}\gamma_{2}+n\sigma^{2}\beta^{2}}$
This result entails the following objective:

$\displaystyle\max_{\begin{subarray}{c}\gamma_{1},\gamma_{2},\beta\\\
q\mathbb{E}\|G\|_{1}\leq\lambda\end{subarray}}-\frac{n}{2}(1-2c)\gamma_{1}-\frac{\gamma_{1}^{2}}{4}+\frac{n}{2}(1-2c)\gamma_{2}-\frac{\gamma_{1}^{2}}{4}-2n\sqrt{c(1-c)}\beta-\frac{\beta^{2}}{4}$

We leverage the fact that for iid standard Gaussians
$X=(X_{1},X_{2},...,X_{d})$, $\mathbb{E}\|X\|_{1}\sim d\sqrt{\frac{2}{\pi}}$.
To write the optimization in a more tractable format, we use a Lagrange
multiplier to bring in the constraint:

$\displaystyle\max_{\gamma_{1},\gamma_{2},\beta}\min_{\eta\geq
0}-\frac{n}{2}(1-2c)\gamma_{1}-\frac{\gamma_{1}^{2}}{4}+\frac{n}{2}(1-2c)\gamma_{2}-\frac{\gamma_{1}^{2}}{4}-2n\sqrt{c(1-c)}\beta-\frac{\beta^{2}}{4}+$
$\displaystyle+\eta\left(\lambda^{2}-2\left[\frac{n^{2}}{4}(1+\frac{2\sigma^{2}}{n})(\gamma_{1}^{2}+\gamma_{2}^{2})+\frac{n^{2}}{2}r\gamma_{1}\gamma_{2}+n\sigma^{2}\beta^{2}\right]\frac{d^{2}}{\pi}\right)$

It can be seen that we arrive at an objective which is essentially the same as
the one in the previous section, but with $\log(2d)$ being replaced by
$\frac{d^{2}}{\pi}$. Therefore we can use the results from before and derive
the final optimization for $\eta$:

$\displaystyle\min_{\eta\geq
0}\lambda^{2}\eta+\frac{n^{2}(1-2c)^{2}}{2+4n^{2}\eta(1-r+\frac{2\sigma^{2}}{n})\frac{d^{2}}{\pi}}+\frac{4n^{2}c(1-c)}{1+8n\sigma^{2}\eta\frac{d^{2}}{\pi}}$

We note that $\gamma_{1}=-\gamma_{2}=:\gamma$. Having found the $\eta$, we
therefore obtain:

$\displaystyle\beta=-\frac{4\sqrt{c(1-c)}}{1+8\sigma^{2}\eta\frac{d^{2}}{\pi}},\quad\gamma=-\frac{2(1-2c)}{1+4n\eta(1-r+\frac{2\sigma^{2}}{n})\frac{d^{2}}{\pi}}$

##  Appendix E SOLVING THE SCALARIZED AO NUMERICALLY

Having simplified a high-dimensional optimization problem to a low-
dimensional, i.e. one having 2-3 variables, the task of solving the scalarized
optimization remains. Since the objective from the conclusion of Theorem 3 is
a convex minimization problem, it could be handled directly using CVX.
However, this is not the case for Theorems 4 and 5, where one must deal with a
$\min\max$. Since there are no packages available for solving $\min\max$
problems numerically, we needed to adapt different approaches. For Theorem 4,
we conducted a grid search over $\tau$ and for each $\tau$ we performed
maximization over $\beta$ and $\gamma$ using MATLAB fmincon. Alternatively,
doing a grid search over all variables is also a feasible approach, which may
not work effectively when the number of variables and the number of points in
the grid increase. Nevertheless, this is what we used for simulating Theorem
5, which turned out to work well in practice for $3$ variables and a grid with
$8000000$ points.