*We are merely assuming $\beta=\sigma$ to reduce the number of symbols; our results can be extended to the case of any general $\beta$. *We are merely assuming $\beta=\sigma$ to reduce the number of symbols; our results can be extended to the case of any general $\beta$.

# Retraining with Predicted Hard Labels Provably Increases Model Accuracy

Rudrajit Das Part of this work was done as a student researcher at Google
Research. University of Texas at Austin, {rdas<EMAIL_ADDRESS>Inderjit S. Dhillon  University of Texas at Austin, {rdas@,
<EMAIL_ADDRESS>Google<EMAIL_ADDRESS>Alessandro Epasto  Google
Research, {aepasto, maojm, mirrokni<EMAIL_ADDRESS>Adel Javanmard
Google Research, {aepasto, maojm, mirrokni<EMAIL_ADDRESS>University of
Southern California<EMAIL_ADDRESS>Jieming Mao  Google Research, {aepasto,
maojm, mirrokni<EMAIL_ADDRESS>Vahab Mirrokni  Google Research,
{aepasto, maojm, mirrokni<EMAIL_ADDRESS>Sujay Sanghavi  University of
Texas at Austin, {rdas<EMAIL_ADDRESS>Peilin Zhong  Google
Research, {aepasto, maojm, mirrokni<EMAIL_ADDRESS>
###### Abstract

The performance of a model trained with noisy labels is often improved by
simply retraining the model with its own predicted hard labels (i.e., $1$/$0$
labels). Yet, a detailed theoretical characterization of this phenomenon is
lacking. In this paper, we theoretically analyze retraining in a linearly
separable setting with randomly corrupted labels given to us and prove that
retraining can improve the population accuracy obtained by initially training
with the given (noisy) labels. To the best of our knowledge, this is the first
such theoretical result. Retraining finds application in improving training
with label differential privacy (DP) which involves training with noisy
labels. We empirically show that retraining selectively on the samples for
which the predicted label matches the given label significantly improves label
DP training at no extra privacy cost; we call this consensus-based retraining.
For e.g., when training ResNet-18 on CIFAR-100 with $\epsilon=3$ label DP, we
obtain $6.4\%$ improvement in accuracy with consensus-based retraining.

##  1 Introduction

We study the simple idea of retraining an already trained model with its own
predicted hard labels (i.e., $1$/$0$ labels and not the raw probabilities)
when the given labels with which the model is initially trained are noisy.
This is a simple yet effective way to boost a model’s performance in the
presence of noisy labels. More formally, suppose we train a discriminative
model $\mathcal{M}$ (for a classification problem) on a dataset of $n$ samples
and noisy label pairs
$\\{({\mathbf{x}}_{j},\widehat{\mathrm{y}}_{j})\\}_{j=1}^{n}$. Let
$\widehat{\bm{\theta}}_{0}$ be the final learned weight/checkpoint of
$\mathcal{M}$ and let
$\widetilde{\mathrm{y}}_{j}=\mathcal{M}(\widehat{\bm{\theta}}_{0},{\mathbf{x}}_{j})$
be the current checkpoint’s predicted hard label for sample
${\mathbf{x}}_{j}$. Now, we propose to retrain $\mathcal{M}$ with the
$\widetilde{\mathrm{y}}_{j}$’s in one of two ways.

(i) Full retraining: Retrain $\mathcal{M}$ with
$\\{({\mathbf{x}}_{j},\widetilde{\mathrm{y}}_{j})\\}_{j=1}^{n}$, i.e., retrain
$\mathcal{M}$ with the predicted labels of all the samples.

(ii) Consensus-based retraining: Define
$\mathcal{S}_{\text{cons}}:=\\{j\in\\{1,\ldots,n\\}\text{ }|\text{
}\widetilde{\mathrm{y}}_{j}=\widehat{\mathrm{y}}_{j}\\}$ to be the set of
samples for which the predicted label matches the given noisy label; we call
this the consensus set. Retrain $\mathcal{M}$ with
$\\{({\mathbf{x}}_{j},\widetilde{\mathrm{y}}_{j})\\}_{j\in\mathcal{S}_{\text{cons}}}$,
i.e., retrain $\mathcal{M}$ with the predicted labels of only the consensus
set.

Intuitively, retraining with predicted hard labels can be beneficial when the
underlying classes are “well-separated”. In such a case, the model can
potentially correctly predict the labels of many samples in the training set
far away from the decision boundary which were originally incorrectly labeled
and presented to it. As a result, the model’s accuracy (w.r.t. the actual
labels) on the training data can be significantly higher than the accuracy of
the noisy labels presented to it. Hence, retraining with predicted labels can
potentially improve the model’s performance. This intuition is illustrated in
Figure 1 where we consider a separable binary classification problem with
noisy labels. The exact details are in Appendix A but importantly, Figures
1(a) and 1(b) correspond to versions of this problem with “large” and “small”
separation, respectively. Please see the figure caption for detailed
discussion but in summary, Figure 1 shows us that the success of retraining
depends on the degree of separation between the classes.

The motivation for consensus-based retraining is that matching the predicted
and given labels can potentially yield a smaller but much more accurate subset
compared to the entire set; such a filtering effect can further improve the
model’s performance. As we show in Section 5 (see Tables 3, 4 and 6), this
intuition bears out in practice.

(a) Large separation: predicted labels pretty
accurate.

(b) Small separation: predicted labels not as
accurate.

Figure 1:  Retraining Intuition. Samples to the right (respectively, left) of
the separator (black vertical line in the middle) and colored blue
(respectively, red) have actual label $+1$ (respectively, $-1$). For both
classes, the incorrectly labeled samples are marked by crosses ($\times$),
whereas the correctly labeled samples are marked by dots ($\circ$) of the
appropriate color. The amount of label noise and the number of training
samples are the same in 1(a) and 1(b). The top and bottom plots show the joint
scatter plot of the training samples with the (noisy) labels given to us and
the labels predicted by the model after training with the given labels,
respectively. Notice that in 1(a), the model correctly predicts the labels of
several samples that were given to it with the wrong label – especially, those
that are far away from the separator. This is not quite the case in 1(b). This
difference gets reflected in the performance on the test set after retraining.
Specifically, in 1(a), retraining increases the test accuracy to $97.67\%$
from $89\%$. However, retraining yields no improvement in 1(b). So the success
of retraining depends on the degree of separation between the classes.

There are plenty of ideas revolving around training a model with its own
predictions, the two most common ones being self-training (Scudder,, 1965;
Yarowsky,, 1995; Lee et al.,, 2013) and self-distillation (Furlanello et al.,,
2018; Mobahi et al.,, 2020); we discuss these and important differences from
retraining in Section 2. However, from a theoretical perspective, we are not
aware of any work proving that retraining a model with its predicted hard
labels can be beneficial in the presence of label noise in any setting. In
Section 4, we derive the first theoretical result (to our knowledge) showing
that full retraining with hard labels improves model accuracy.

The primary reason for our interest in retraining is that it turned out to be
a simple yet effective way to improve training with label differential privacy
(DP) whose goal is to safeguard the privacy of labels in a supervised ML
problem by injecting label noise (see Section 3 for a formal definition).
Label DP is used in scenarios where only the labels are considered sensitive,
e.g., advertising, recommendation systems, etc. (Ghazi et al.,, 2021).
Importantly, retraining can be applied on top of any label DP training
algorithm at no extra privacy cost. Our main algorithmic contribution is
empirically demonstrating the efficacy of consensus-based retraining in
improving label DP training (Section 5). Three things are worth clarifying
here. First, as a meta-idea, retraining is not particularly new; however, its
application – especially with consensus-based filtering – as a light-weight
way to improve label DP training at no extra privacy cost is new to our
knowledge. Second, we are not advocating consensus-based retraining as a SOTA
general-purpose algorithm for learning with noisy labels. Third, we do not
view full retraining to be an algorithmic contribution; we consider it for
theoretical analysis and as a baseline for consensus-based retraining.

Our main contributions can be summarized as follows:
(a) In Section 4, we consider a linearly separable binary classification
problem wherein the data (feature) dimension is $d$, and we are given randomly
flipped labels with the label flipping probability being $p<\frac{1}{2}$
independently for each sample. Our main result is proving that full retraining
with the predicted hard labels improves the population accuracy obtained by
initially training with the given labels, provided the degree of separation
between the classes is large enough and the number of samples
$n\in\Big{(}\Theta\Big{(}\frac{d\log
d}{(1-2p)^{2}}\Big{)},\Theta\Big{(}\frac{d^{2}}{(1-2p)^{2}}\Big{)}\Big{)}$;
see Remark 4 for details. Our results also show that retraining becomes more
beneficial as the amount of label noise (i.e., $p$) increases (Remark 4) or as
the degree of separation between the classes increases (Remark 5). To the best
our knowledge, these are the first theoretical results quantifying the
benefits of retraining with predicted hard labels in the presence of label
noise.

(b) In Section 5, we show the promise of consensus-based retraining (i.e.,
retraining on only those samples for which the predicted label matches the
given noisy label) as a simple way to improve the performance of any label DP
algorithm, at no extra privacy cost. For e.g., when training ResNet-18 on
CIFAR-100 with $\epsilon=3$ label DP, we obtain $6.4\%$ improvement in
accuracy with consensus-based retraining (see Table 2). The corresponding
improvement for a small BERT model trained on AG News Subset (a news
classification dataset) with $\epsilon=0.5$ label DP is $11.7\%$ (see Table
5).

##  2 Related Work

Self-Training (ST). Retraining is similar in spirit to ST (Scudder,, 1965;
Yarowsky,, 1995; Lee et al.,, 2013; Sohn et al.,, 2020) which is the process
of progressively training a model with its own predicted hard labels in the
semi-supervised setting. Our main focus is the fully supervised setting;111It
is worth mentioning here that we analyze retraining in a semi-supervised
setting due to certain technical complications (because of independence not
holding) in the supervised setting. But we believe that the crux of our
theoretical insights should carry over to the supervised setting. in fact, our
proposed consensus-based retraining scheme crucially relies on the given
labels for sample selection. This is different from ST (in the semi-supervised
setting) which typically selects samples based on the model’s confidence and
hence, we call our algorithmic idea of interest retraining to distinguish it
from ST. In fact, we show that our consensus-based sample selection strategy
leads to better performance than confidence-based sample selection in Appendix
I. There is a vast body of work on ST and related ideas; see Amini et al.,
(2022) for a survey. On the theoretical side also, there are several papers
showing and quantifying different kinds of benefits of ST and related ideas
(Carmon et al.,, 2019; Raghunathan et al.,, 2020; Kumar et al.,, 2020; Chen et
al.,, 2020; Oymak and Gulcu,, 2020; Wei et al.,, 2020; Zhang et al.,, 2022).
But none of these works characterize the pros/cons of ST or any related
algorithm in the presence of noisy labels. In contrast, we show that
retraining can provably improve accuracy in the presence of label noise in
Section 4. Empirically, ST-based ideas have been proposed to improve learning
with noisy labels (Reed et al.,, 2014; Tanaka et al.,, 2018; Han et al.,,
2019; Nguyen et al.,, 2019; Li et al.,, 2020; Goel et al.,, 2022); but these
works do not have rigorous theory.

Self-Distillation (SD). Retraining is also similar in principle to SD
(Furlanello et al.,, 2018; Mobahi et al.,, 2020); the major difference is that
soft labels (i.e., predicted raw probabilities) are used in SD, whereas we use
hard labels in retraining. Specifically, in SD, a teacher model is first
trained with provided hard labels and then its predicted soft labels are used
to train a student model with the same architecture as the teacher. SD is
usually employed with a temperature parameter (Hinton et al.,, 2015) to force
the teacher and student models to be different; we do not have any such
parameter in retraining as it uses hard labels. SD is known to ameliorate
learning in the presence of noisy labels (Li et al.,, 2017) and this has been
theoretically analyzed by Dong et al., (2019); Das and Sanghavi, (2023). Dong
et al., (2019) propose their own SD algorithm that uses dynamically updated
soft labels and provide some complicated conditions of when their algorithm
can learn the correct labels in the presence of noisy labels. In contrast, we
analyze retraining with fixed hard labels. Das and Sanghavi, (2023) analyze
the standard SD algorithm in the presence of noisy labels with fixed soft
labels but their analysis in the classification setting requires some strong
assumptions such as access to the population, feature maps of all points in
the same class having the same inner product, etc. We do not require such
strong assumptions in this paper (in fact, we present sample complexity
bounds). Moreover, Das and Sanghavi, (2023) have extra
$\ell_{2}$-regularization in their objective function to force the teacher and
student models to be different. We do not apply any extra regularization for
retraining.

Label Differential Privacy (DP). Label DP (described in detail in Section 3)
is a relaxation of full-data DP wherein the privacy of only the labels (and
not the features) is safeguarded (Chaudhuri and Hsu,, 2011; Beimel et al.,,
2013; Wang and Xu,, 2019; Ghazi et al.,, 2021; Malek Esmaeili et al.,, 2021;
Ghazi et al.,, 2022; Badanidiyuru et al.,, 2023). In this work, we are not
trying to propose a SOTA label DP algorithm (with an ingenious noise-injection
scheme); instead, we advocate retraining as a simple post-processing step that
can be applied on top of any label DP algorithm (regardless of the noise-
injection scheme) to improve its performance, at no extra privacy cost.
Similar to our goal, Tang et al., (2022) apply techniques from unsupervised
and semi-supervised learning to improve label DP training. In particular, one
of their steps involves keeping the given noisy label of a sample only if it
matches a pseudo-label generated by unsupervised learning. This is similar in
spirit to our consensus-based retraining scheme but a crucial difference is
that we do not perform any unsupervised learning; we show that matching the
given noisy label to the model’s own predicted label is itself pretty
effective. Further, unlike work, Tang et al., (2022) do not have any rigorous
theory.

##  3 Preliminaries

Notation. We use $\Theta(\cdot)$ and $\Omega(\cdot)$ to denote the standard
big-$\Theta$ and big-$\Omega$ notations. Specifically, $f(d)=\Theta(g(d))$ if
there are absolute constants $c_{1},c_{2}>0$ and a natural number $d_{0}$ such
that $c_{1}g(d)\leq f(d)\leq c_{2}g(d)$ for all $d\geq d_{0}$. In addition,
$f(d)=\Omega(g(d))$ if there is an absolute constant $c$ and a natural number
$d_{0}$ such that $f(d)\geq cg(d)$ for all $d\geq d_{0}$. Throughout the
paper, we sometimes use the big-$\Theta$ notation to absorb different absolute
constants. For any positive integer $m\geq 1$, we denote the set
$\\{1,\ldots,m\\}$ by $[m]$. For any vector ${\mathbf{v}}$, we denote its
$i^{\text{th}}$ coordinate by $\mathrm{v}^{(i)}$. Let ${\mathbf{e}}_{i}$
denote the $i^{\text{th}}$ canonical vector, i.e., the vector of all zeros
except a one in the $i^{\text{th}}$ coordinate. We denote the $\ell_{2}$ norm
of a vector ${\mathbf{v}}$ by $\|{\mathbf{v}}\|$, and the operator norm of a
matrix ${\mathbf{M}}$ by $\|{\mathbf{M}}\|$. The unit $d$-dimensional sphere
(i.e., the set of $d$-dimensional vectors with unit norm) is denoted by
$S^{d-1}$. A random variable ${\mathrm{X}}$ is said to be sub-Gaussian with
parameter $\sigma^{2}$ (abbreviated as SG($\sigma^{2}$)) if for all
$t\in\mathbb{R}$, it holds that
$\mathbb{E}\big{[}e^{t({\mathrm{X}}-\mathbb{E}[{\mathrm{X}}])}\big{]}\leq\exp\big{(}\frac{t^{2}\sigma^{2}}{2}\big{)}$.
We denote the CDF and complementary CDF (CCDF) of a standard normal variable
(i.e., distributed as $\mathcal{N}(0,1)$) by $\Phi(.)$ and
$\Phi^{\text{c}}(.)$, respectively.

######  Definition 1 (Label Differential Privacy (DP)).

A randomized algorithm $\mathcal{A}$ taking as input a dataset and with range
$\mathcal{R}$ is said to be $\epsilon$-labelDP if for any two datasets
${\mathrm{D}}$ and ${\mathrm{D}}^{\prime}$ differing in the label of a single
example and for any $\mathcal{S}\subseteq\mathcal{R}$, it holds that
$\mathbb{P}\big{(}\mathcal{A}({\mathrm{D}})\in\mathcal{S}\big{)}\leq
e^{\epsilon}\mathbb{P}\big{(}\mathcal{A}({\mathrm{D}}^{\prime})\in\mathcal{S}\big{)}$.

Label DP training involves injecting noise into the labels and then training
with these noisy labels. The simplest way of injecting label noise to ensure
label DP is randomized response (RR) introduced by Warner, (1965).
Specifically, suppose we require $\epsilon$-labelDP for a problem with $C$
classes, then the distribution of the output $\widehat{\mathrm{y}}$ of RR when
the true label is ${\mathrm{y}}$ is as follows:

$\mathbb{P}\big{(}\hat{\mathrm{y}}={\mathrm{z}}\big{)}=\begin{cases}\frac{e^{\epsilon}}{e^{\epsilon}+C-1}\quad\text{
for }{\mathrm{z}}={\mathrm{y}},\\\ \frac{1}{e^{\epsilon}+C-1}\quad\text{
otherwise}.\end{cases}$

Our label noise model in Section 4 (eq. 1) is actually RR for 2 classes. Based
on vanilla RR, more sophisticated ways to inject label noise for better
performance under label DP have been proposed (Ghazi et al.,, 2021; Malek
Esmaeili et al.,, 2021). Our empirical results in Section 5 are with RR and
the method of Ghazi et al., (2021).

##  4 Full Retraining in the Presence of Label Noise: Theoretical Analysis

Here we will analyze full retraining (as introduced in Section 1) for a linear
setting with noisy labels. Since full retraining is the only kind of
retraining we consider in this section, we will omit the word “full”
subsequently in this section.

Problem Setting. A sample ${\mathbf{x}}\in\mathbb{R}^{d}$ ($d\geq 2$) drawn
from a distribution $\mathcal{D}$ has a binary label
$\mathrm{y}=\text{sign}\big{(}\langle{\mathbf{x}},\bm{\theta}^{\ast}\rangle\big{)}\in\\{\pm
1\\}$, for some $\bm{\theta}^{\ast}\in S^{d-1}$. Let
$\mathcal{B}:=\\{\bm{\theta}^{\ast},\bar{\bm{\theta}}_{2},\ldots,\bar{\bm{\theta}}_{d}\\}$
be an orthonormal basis for $\mathbb{R}^{d}$. We will now describe
$\mathcal{D}$. Suppose the representation of ${\mathbf{x}}$ w.r.t.
$\mathcal{B}$ is
${\mathrm{a}}^{(1)}\bm{\theta}^{\ast}+\sum_{j=2}^{d}{\mathrm{a}}^{(j)}\bar{\bm{\theta}}_{j}$;
note that ${\mathrm{a}}^{(1)}=\langle{\mathbf{x}},\bm{\theta}^{\ast}\rangle$
and ${\mathrm{a}}^{(j)}=\langle{\mathbf{x}},\bar{\bm{\theta}}_{j}\rangle$ for
$j\geq 2$. The ${\mathrm{a}}^{(j)}$’s ($j\in[d]$) are independent of each
other.
$\mathbb{P}({\mathrm{a}}^{(1)}>0)=\mathbb{P}({\mathrm{a}}^{(1)}<0)=\frac{1}{2}$
and further, the density of ${\mathrm{a}}^{(1)}$ is symmetric about 0.222Here
we consider a balanced classification problem for simplicity. However, it is
possible to analyze a similar imbalanced setting with some suitable
modifications to our proof techniques. Also,
$\text{Var}\big{(}{\mathrm{a}}^{(1)}\big{)}=\sigma^{2}$,
$|{\mathrm{a}}^{(1)}|$ is SG($\sigma^{2}$),
$\mathbb{E}\big{[}|{\mathrm{a}}^{(1)}|\big{]}=\mu\sigma$ where
$\mu\leq\frac{1}{2}$, and $|{\mathrm{a}}^{(1)}|\geq\gamma\sigma$ for some
$\gamma\in(0,\mu]$.333Our analysis can be extended even if
$|{\mathrm{a}}^{(1)}|$ is SG($c\sigma^{2}$) for an arbitrary $c>0$; we
consider $c=1$ to reduce the number of symbols. It can be also adapted to the
case of $\mu\leq c$, for an arbitrary $c<1$ (e.g., $c=\frac{3}{4}$). Here,
$\gamma$ is a parameter quantifying the degree of separation between the two
classes w.r.t. the ground truth classifier $\bm{\theta}^{\ast}$, a.k.a.
margin. For $j\geq 2$, each
${\mathrm{a}}^{(j)}\underset{\text{iid}}{\sim}\mathcal{N}(0,\sigma^{2})$.444Our
analysis can be extended even if each ${\mathrm{a}}^{(j)}$ is
SG($\sigma^{2}$). We assume pure Gaussianity due to the relative simplicity of
some required concentration results, compared to the corresponding ones under
sub-Gaussianity.

We are given $n>d$ labeled examples
$\mathcal{X}_{L}:=\\{{\mathbf{x}}_{1},\ldots,{\mathbf{x}}_{n}\\}$ and $n$
unlabeled examples
$\mathcal{X}_{U}:=\\{{\mathbf{x}}^{\prime}_{1},\ldots,{\mathbf{x}}^{\prime}_{n}\\}$
drawn i.i.d. from $\mathcal{D}$. For $j\in[n]$, let
$\mathrm{y}_{j}=\text{sign}\big{(}\langle{\mathbf{x}}_{j},\bm{\theta}^{\ast}\rangle\big{)}$
be the ground truth label of ${\mathbf{x}}_{j}$. We have access to a noisy
label source which gives us a randomly corrupted version of $\mathrm{y}_{j}$,
namely $\widehat{\mathrm{y}}_{j}$, instead of $\mathrm{y}_{j}$. Specifically,
for some $p<\frac{1}{2}$, we have:555In the context of $\epsilon$-labelDP with
randomized response, $p=\frac{1}{1+e^{\epsilon}}$.

$\widehat{\mathrm{y}}_{j}=\begin{cases}\mathrm{y}_{j}\text{ w.p. }1-p\\\
-\mathrm{y}_{j}\text{ w.p. }p.\end{cases}$ (1)

Let $\mathcal{T}:=\\{({\mathbf{x}}_{j},\widehat{\mathrm{y}}_{j})\\}_{j\in[n]}$
denote the labeled part of the training data. We use $\mathcal{T}$ for vanilla
training. Then, we label $\mathcal{X}_{U}$ using the classifier learned with
vanilla training and use this for retraining. Ideally, we would have liked to
analyze retraining over $\mathcal{X}_{L}$ and not have $\mathcal{X}_{U}$ at
all, but this is complicated and tedious due to independence not holding. In
order to circumvent this extra layer of complication in the analysis with
$\mathcal{X}_{L}$, we analyze retraining over $\mathcal{X}_{U}$ (wherein
independence obviates the said complication). We believe that the main
insights should not change much.

###  4.1 Vanilla Training

Here we train with the given noisy labels as is. Our objective function with
the squared loss is
$\frac{1}{2n}\sum_{j=1}^{n}\big{(}\widehat{\mathrm{y}}_{j}-\bm{\theta}^{\top}{\mathbf{x}}_{j}\big{)}^{2}$
and its minimizer is
$\bar{\bm{\theta}}_{0}=\Big{(}\frac{1}{n}\sum_{k=1}^{n}{\mathbf{x}}_{k}{\mathbf{x}}_{k}^{\top}\Big{)}^{-1}\Big{(}\frac{1}{n}\sum_{j=1}^{n}\widehat{\mathrm{y}}_{j}{\mathbf{x}}_{j}\Big{)}$.
But instead of considering $\bar{\bm{\theta}}_{0}$ as our learned separator,
we will focus on

$\widehat{\bm{\theta}}_{0}=\frac{1}{\sigma^{2}}\Bigg{(}\frac{1}{n}\sum_{j=1}^{n}\widehat{\mathrm{y}}_{j}{\mathbf{x}}_{j}\Bigg{)}.$
(2)

Observe that the empirical covariance matrix
$\frac{1}{n}\sum_{k=1}^{n}{\mathbf{x}}_{k}{\mathbf{x}}_{k}^{\top}$ in
$\bar{\bm{\theta}}_{0}$ is replaced by its expected value, viz.,
$\sigma^{2}{\mathbf{I}}_{d}$ in $\widehat{\bm{\theta}}_{0}$. The reason for
doing this is that the analysis with $\bar{\bm{\theta}}_{0}$ eventually
reduces down to analyzing with $\widehat{\bm{\theta}}_{0}$ by performing some
tedious math first (due to the empirical covariance matrix) which does not
yield any meaningful insights. For completeness, we discuss how the analysis
can be done with $\bar{\bm{\theta}}_{0}$ in Appendix G. Our predicted label
for a sample ${\mathbf{x}}$ with $\widehat{\bm{\theta}}_{0}$ is
$\textup{sign}\big{(}\langle{\mathbf{x}},\widehat{\bm{\theta}}_{0}\rangle\big{)}$
(instead of just $\langle{\mathbf{x}},\widehat{\bm{\theta}}_{0}\rangle$ which
would have been the case in a regression problem).

######  Theorem 1 (Vanilla Training: Probability of Predicted Label = True
Label).

Consider a sample ${\mathbf{x}}\notin\mathcal{X}_{L}$. Let
$\beta({\mathbf{x}})$ denote the angle between ${\mathbf{x}}$ and
$\bm{\theta}^{\ast}$. Then our predicted label for ${\mathbf{x}}$, viz.,
$\textup{sign}\big{(}\langle{\mathbf{x}},\widehat{\bm{\theta}}_{0}\rangle\big{)}$
is equal to the ground truth label of ${\mathbf{x}}$, viz.,
$\textup{sign}\big{(}\langle{\mathbf{x}},\bm{\theta}^{\ast}\rangle\big{)}$
with a probability (over the randomness of $\mathcal{T}$) of at least
$\alpha({\mathbf{x}}):=1-\exp\Big{(}-\frac{n\mu^{2}}{4}(1-2p)^{2}\textup{cos}^{2}\big{(}\beta({\mathbf{x}})\big{)}\Big{)}$
and at most
$\widehat{\alpha}({\mathbf{x}}):=1-\frac{1}{3\sqrt{2\pi}}{\exp\Big{(}-{\big{(}1+\sqrt{n}\mu(1-2p)\big{)}^{2}\textup{cot}^{2}\big{(}\beta({\mathbf{x}})\big{)}}\Big{)}}$.

The proof of Theorem 1 is in Appendix B. Observe that $\alpha({\mathbf{x}})$
and $\widehat{\alpha}({\mathbf{x}})$ have essentially the same dependence on
$n$, $p$ and $\mu$; so, this dependence is tight. Also, notice that the
learned classifier $\widehat{\bm{\theta}}_{0}$ is more likely to be wrong on
the samples that are less aligned with (or closer to orthogonal to) the ground
truth separator, i.e., $\bm{\theta}^{\ast}$. We can view
$\widehat{\bm{\theta}}_{0}$ as a noisy label provider (a.k.a. pseudo-labeler)
where the degree of label noise is non-uniform or sample-dependent unlike the
original noisy source used to learn $\widehat{\bm{\theta}}_{0}$. Specifically,
for a sample ${\mathbf{x}}$ with true label
$\mathrm{y}=\text{sign}\big{(}\langle{\mathbf{x}},\bm{\theta}^{\ast}\rangle\big{)}$
and predicted label
$\widetilde{\mathrm{y}}=\textup{sign}\big{(}\langle{\mathbf{x}},\widehat{\bm{\theta}}_{0}\rangle\big{)}$,
we have:

$\widetilde{\mathrm{y}}=\begin{cases}\mathrm{y}\text{ w.p.
}\geq\alpha({\mathbf{x}})\\\ -\mathrm{y}\text{ w.p. }\leq
1-\alpha({\mathbf{x}}),\text{ where $\alpha({\mathbf{x}})$ is as defined in
<EMAIL_ADDRESS>
We will now provide lower and upper bounds on the population accuracy of the
classifier $\widehat{\bm{\theta}}_{0}$; we denote this by
$\text{acc}(\widehat{\bm{\theta}}_{0})$ and it is defined as:

$\text{acc}(\widehat{\bm{\theta}}_{0}):=\mathbb{P}_{{\mathbf{x}}\sim\mathcal{D},\mathcal{T}}\Big{(}\textup{sign}\big{(}\langle{\mathbf{x}},\widehat{\bm{\theta}}_{0}\rangle\big{)}=\textup{sign}\big{(}\langle{\mathbf{x}},\bm{\theta}^{\ast}\rangle\big{)}\Big{)}.$

######  Theorem 2 (Vanilla Training: Population Accuracy).

We have:

$\displaystyle\textup{acc}(\widehat{\bm{\theta}}_{0})\geq
1-\exp\big{(}-\Theta(d)\big{)}-\exp\Bigg{(}-\frac{n{\mu^{2}}\gamma^{2}(1-2p)^{2}}{\Theta(d)}\Bigg{)},$

and

$\displaystyle\textup{acc}(\widehat{\bm{\theta}}_{0})\leq
1-\Theta(1)\exp\Bigg{(}-\frac{n\mu^{4}(1-2p)^{2}}{\Theta(d)}\Bigg{)}.$

The proof of Theorem 2 is in Appendix C.

######  Remark 1 (Tightness of Accuracy Bounds).

Suppose $\gamma=\Theta(\mu)$. When
$n\leq\Theta\Big{(}\frac{d^{2}}{(1-2p)^{2}\mu^{4}}\Big{)}$, the lower and
upper bounds for $\textup{acc}(\widehat{\bm{\theta}}_{0})$ in Theorem 2
essentially match (modulo constant factors).

Based on Theorem 2, we have the following corollary.

######  Corollary 1 (Vanilla Training: Sample Complexity).

For any $\delta>(1+\Theta(1))\exp(-\Theta({d}))$,
$n=\Omega\Big{(}\frac{\log{1}/{\delta}}{(1-2p)^{2}}\big{(}\frac{d}{\mu^{2}\gamma^{2}}\big{)}\Big{)}$
ensures that $\textup{acc}(\widehat{\bm{\theta}}_{0})>1-\delta$. Specifically,
when $p>(1+\Theta(1))\exp(-\Theta({d}))$,
$n=\Omega\Big{(}\frac{\log{1}/{p}}{(1-2p)^{2}}\big{(}\frac{d}{\mu^{2}\gamma^{2}}\big{)}\Big{)}$
ensures that $\textup{acc}(\widehat{\bm{\theta}}_{0})>1-p$, i.e., our learned
classifier $\widehat{\bm{\theta}}_{0}$ has better accuracy than the source
providing noisy labels (used to learn $\widehat{\bm{\theta}}_{0}$).

We will now present an information-theoretic lower bound on the sample
complexity of any classifier to argue the optimality of the result in
Corollary 1 with respect to the dependence on $d$ and $p$.

######  Theorem 3 (Information-Theoretic Lower Bound on Sample Complexity).

With a slight generalization of notation, let
$\textup{acc}(\widehat{\bm{\theta}};\bm{\theta}^{*})$ denote the accuracy of
the classifier $\widehat{\bm{\theta}}$, when the ground truth model is
$\bm{\theta}^{*}$. For any classifier $\widehat{\bm{\theta}}$ learned from
$\mathcal{T}:=\\{({\mathbf{x}}_{j},\widehat{\mathrm{y}}_{j})\\}_{j\in[n]}$, in
order to achieve $\inf_{\bm{\theta}^{\ast}\in
S^{d-1}}\textup{acc}(\widehat{\bm{\theta}};\bm{\theta}^{*})\geq 1-\delta$,
where $\delta<\frac{1}{5}$,
$n=\Omega\left(\frac{(1-5\delta)}{(1-2p)^{2}}d\right)$ is necessary in our
problem setting.

It is worth mentioning that there is a similar lower bound in Gentile and
Helmbold, (1998) for a different classification setting. In contrast, Theorem
3 is tailored to our setting and moreover, the proof technique is also
different. Specifically, for the proof of Theorem 3, we follow a standard
technique in proving minimax lower bounds which is to reduce the problem of
interest to an appropriate multi-way hypothesis testing problem; this is
accompanied by the application of the conditional version of Fano’s inequality
and some ideas from high-dimensional geometry. This proof is in Appendix D.

######  Remark 2 (Optimality of Sample Complexity).

Note that the dependence of the sample complexity on $d$ and $p$ in Corollary
1 matches that of the lower bound in Theorem 3. Thus, our sample complexity
bound in Corollary 1 is optimal with respect to $d$ and $p$.

######  Remark 3 (Effect of Degree of Separation).

As the parameter quantifying the degree of separation $\gamma$ decreases, the
accuracy lower bound in Theorem 2 also decreases and the sample complexity
required to outperform the noisy label source in Corollary 1 increases. This
is consistent with our intuition that a classification task should become
harder as the degree of separation reduces; we also saw this in Figure 1.

###  4.2 Retraining

We first label the unlabeled set
$\mathcal{X}_{U}:=\\{{\mathbf{x}}^{\prime}_{1},\ldots,{\mathbf{x}}^{\prime}_{n}\\}$
using the learned classifier $\widehat{\bm{\theta}}_{0}$. Let us denote the
predicted label for ${\mathbf{x}}^{\prime}_{j}$ with
$\widehat{\bm{\theta}}_{0}$ by
$\widetilde{\mathrm{y}}_{j}^{\prime}=\textup{sign}\big{(}\langle{\mathbf{x}}^{\prime}_{j},\widehat{\bm{\theta}}_{0}\rangle\big{)}$.
Also, let
$\mathcal{T}_{2}:=\\{({\mathbf{x}}^{\prime}_{j},\widetilde{\mathrm{y}}_{j}^{\prime})\\}_{j\in[n]}$;
we use $\mathcal{T}_{2}$ for retraining. Just like Section 4.1 (using the
squared loss), our separator of interest with $\mathcal{T}_{2}$ is:

$\widehat{\bm{\theta}}_{1}=\frac{1}{\sigma^{2}}\Bigg{(}\frac{1}{n}\sum_{j=1}^{n}\widetilde{\mathrm{y}}_{j}^{\prime}{\mathbf{x}}_{j}^{\prime}\Bigg{)}.$
(3)

######  Theorem 4 (Retraining: Probability of Predicted Label = True Label).

Consider a sample ${\mathbf{x}}\notin\mathcal{X}_{L}\cup\mathcal{X}_{U}$. Let
$\beta({\mathbf{x}})$ denote the angle between ${\mathbf{x}}$ and
$\bm{\theta}^{\ast}$. Also, let
$p_{2}:=\exp\Big{(}-\frac{9(d-1)}{40}\Big{)}+\exp\Big{(}-\frac{n\mu^{2}\gamma^{2}}{12d}(1-2p)^{2}\Big{)}$.
As long as
$|\textup{cos}\big{(}\beta({\mathbf{x}})\big{)}|\geq\frac{16p_{2}}{\mu}$, our
predicted label for ${\mathbf{x}}$, viz.,
$\textup{sign}\big{(}\langle{\mathbf{x}},\widehat{\bm{\theta}}_{1}\rangle\big{)}$
is equal to its ground truth label, viz.,
$\textup{sign}\big{(}\langle{\mathbf{x}},\bm{\theta}^{\ast}\rangle\big{)}$
with a probability (over the randomness of $\mathcal{T}$ and
$\mathcal{T}_{2}$) of at least
$\alpha_{1}({\mathbf{x}}):=1-\exp\Big{(}-\frac{n\mu^{2}}{4}(1-2p_{2})\textup{cos}^{2}\big{(}\beta({\mathbf{x}})\big{)}\Big{)}$.

The proof of Theorem 4 is in Appendix E; it involves non-trivial moment
generating function (MGF) computations. The analysis is especially challenging
because as we discussed after Theorem 1, the classifier learned with vanilla
training, i.e., $\widehat{\bm{\theta}}_{0}$, is a non-uniform noisy label
provider. Also, just like the classifier $\widehat{\bm{\theta}}_{0}$, the
classifier $\widehat{\bm{\theta}}_{1}$ learned with retraining is more likely
to be wrong on the samples that are less aligned with the ground truth
separator $\bm{\theta}^{\ast}$.

We will now provide a lower bound on the population accuracy of the classifier
$\widehat{\bm{\theta}}_{1}$; we denote this by
$\text{acc}(\widehat{\bm{\theta}}_{1})$ and it is defined as:

$\text{acc}(\widehat{\bm{\theta}}_{1}):=\mathbb{P}_{{\mathbf{x}}\sim\mathcal{D},\mathcal{T},\mathcal{T}_{2}}\Big{(}\textup{sign}\big{(}\langle{\mathbf{x}},\widehat{\bm{\theta}}_{1}\rangle\big{)}=\textup{sign}\big{(}\langle{\mathbf{x}},\bm{\theta}^{\ast}\rangle\big{)}\Big{)}.$

######  Theorem 5 (Retraining: Population Accuracy).

Suppose $p>(1+\Theta(1))\exp(-\Theta({d}))$ and
$\gamma\geq\Theta\Big{(}\frac{\sqrt{d}\exp(-\Theta(d))}{\mu}\Big{)}$. Let
$n\geq\Theta\Big{(}\frac{1}{(1-2p)^{2}}\Big{(}\frac{d}{\mu^{2}\gamma^{2}}\Big{)}\max\Big{(}\log\Big{(}\frac{d}{\mu^{2}\gamma^{2}}\Big{)},\log\frac{1}{p}\Big{)}\Big{)}$.
Then:

$\displaystyle\textup{acc}(\widehat{\bm{\theta}}_{1})\geq
1-\exp\big{(}-\Theta(d)\big{)}-\exp\Bigg{(}-\frac{n{\mu^{2}\gamma^{2}}(1-2p_{2})}{\Theta(d)}\Bigg{)},$

with
$p_{2}=\exp\big{(}-\Theta(d)\big{)}+\exp\Big{(}-\frac{n\mu^{2}\gamma^{2}(1-2p)^{2}}{\Theta(d)}\Big{)}\leq\min\Big{(}p,\Theta\big{(}\frac{\mu\gamma}{\sqrt{d}}\big{)}\Big{)}$.

The proof of Theorem 5 is in Appendix F. Note that the sample complexity
required for Theorem 5 to hold is more than the lower bound in Theorem 3
(specifically, there is an extra
$\log\big{(}\frac{d}{\mu^{2}\gamma^{2}}\big{)}$ term in Theorem 5). So Theorem
3 is never violated by Theorem 5.

We will now compare the accuracies of vanilla training and retraining.

######  Remark 4 (When Does Retraining Improve Accuracy?).

Suppose we are in the non-trivial noise regime where $p$ is a constant (e.g.,
$\frac{2}{5}$). Moreover, suppose $\gamma=\Theta(\mu)$. Then, as per Theorem
5, when
$n\geq\Theta\Big{(}\frac{1}{(1-2p)^{2}}\big{(}\frac{d}{\mu^{4}}\big{)}\log\big{(}\frac{d}{\mu^{4}}\big{)}\Big{)}$,666This
follows because $\gamma=\Theta(\mu)$ and $p$ is a constant. the accuracy of
retraining is $\geq
1-\exp\big{(}-\Theta(d)\big{)}-\exp\Big{(}-\frac{n\mu^{4}}{\Theta(d)}\Big{)}$.777This
holds because $\gamma=\Theta(\mu)$ and
$p_{2}\leq\Theta\Big{(}\frac{\mu^{2}}{\sqrt{d}}\Big{)}$, since $p$ is a
constant. This can be further lower-bounded by:

$\geq
1-\Theta(1)\exp\Bigg{(}-\min\Bigg{(}\Theta(d),\frac{n\mu^{4}}{\Theta(d)}\Bigg{)}\Bigg{)}.$
(4)

In comparison, the accuracy of vanilla training as per Theorem 2 is:

$\leq 1-\Theta(1)\exp\Bigg{(}-\frac{n\mu^{4}(1-2p)^{2}}{\Theta(d)}\Bigg{)}.$
(5)

From eq. 4 and eq. 5 and as per the lower bound on $n$ stated before, when

$n\in\Bigg{(}\Theta\Bigg{(}\frac{(d/\mu^{4})\log\big{(}{{d}/{\mu^{4}}}\big{)}}{(1-2p)^{2}}\Bigg{)},\Theta\Bigg{(}\frac{(d^{2}/\mu^{4})}{(1-2p)^{2}}\Bigg{)}\Bigg{)}$
(6)

and $p$ is sufficiently close to $\frac{1}{2}$, the lower bound on the
accuracy of retraining (in eq. 4) is greater than the upper bound on the
accuracy of vanilla training (in eq. 5). This improvement becomes increasingly
significant as $p$ approaches $\frac{1}{2}$.

Regarding $n$ in Remark 4. We expect that the minimum value of $n$ needed for
retraining to be beneficial should be at least the sample complexity needed
for the classifier obtained with vanilla training to outperform the noisy
label source used to train it. We computed the latter in Corollary 1; compared
to this value, the minimum value of $n$ required for Remark 4 to hold (in eq.
6) has an extra mild factor of
$\log\big{(}{\frac{d}{\mu^{4}}}\big{)}$.888Recall that this is when
$\gamma=\Theta(\mu)$ and when $p$ is a constant. On the other hand, the upper
bound on $n$ in eq. 6 of Remark 4 could be an artifact of our analysis;
investigating this is left for future work.999More specifically, this upper
bound on $n$ arises as a result of the $\exp\big{(}-\Theta(d)\big{)}$ term in
the accuracy bound of retraining. If this can be removed, then the upper bound
will not exist.

######  Remark 5 (Effect of Degree of Separation).

Similar to vanilla training (Remark 3), as the parameter quantifying the
degree of separation $\gamma$ decreases, the accuracy lower bound of
retraining in Theorem 5 also decreases101010Note that $p_{2}$ also depends on
$\gamma$ and it is a decreasing function of $\gamma$. and the sample
complexity required for this bound to hold increases. Moreover, in Remark 4,
we considered the regime of $\gamma=\Theta(\mu)$, i.e., $\gamma$ is “large”
enough relative to the mean $\mu$. This tells us that retraining is more
beneficial when the degree of separation is large.

##  5 Improving Label DP Training with Retraining (RT)

Motivated by our theoretical results in Section 4 which show that retraining
(abbreviated as RT henceforth) can improve accuracy in the presence of label
noise, we propose to apply our proposals in Section 1, viz., full RT and more
importantly, consensus-based RT to improve label DP training (because it
involves noisy labels). Note that this can be done on top of any label DP
mechanism and that too at no additional privacy cost (both the predicted
labels and originally provided noisy labels are private). We empirically
evaluate full and consensus-based RT on three classification datasets
(available on TensorFlow) trained with label DP. These include two vision
datasets, namely CIFAR-10 and CIFAR-100, and one language dataset, namely AG
News Subset (Zhang et al.,, 2015). All the empirical results are averaged over
three different runs. We only provide important experimental details here; the
other details can be found in Appendix H.

CIFAR-10/100. We train a ResNet-18 model on CIFAR-10 and CIFAR-100 with label
DP. Label DP training is done with the prior-based method of Ghazi et al.,
(2021) – specifically, Alg. 3 with two stages. Our training set consists of
45k examples and we assume access to a validation set with clean labels
consisting of 5k examples which we use for deciding when to stop training,
setting hyper-parameters, etc.111111In practice, we do not need full access to
the validation set. Instead, the validation set can be stored by a secure
agent which returns us a private version of the validation accuracy and this
will not be too far off from the true validation accuracy when the validation
set is large enough. For CIFAR-10 and CIFAR-100 with three different values of
$\epsilon$, we list the test accuracies of the baseline (i.e., the method of
Ghazi et al., (2021)), full RT and consensus-based RT in Tables 1 and 2,
respectively. Notice that consensus-based RT is the clear winner. Also, for
the three values of $\epsilon$ in Table 1 (CIFAR-10), the size of the
consensus set (used in consensus-based RT) is $\sim 31\%$, $55\%$ and $76\%$,
respectively, of the entire training set. The corresponding numbers for Table
2 (CIFAR-100) are $\sim 11\%$, $34\%$ and $56\%$, respectively. So for small
$\epsilon$ (high label noise), consensus-based RT comprehensively outperforms
full RT and baseline with a small fraction of the training set. Further, in
Tables 3 and 4, we list the accuracies of predicted labels and given labels
over the entire (training) dataset and accuracies of predicted (= given)
labels over the consensus set for CIFAR-10 and CIFAR-100. Please see the table
captions for detailed discussion but to summarize, the accuracy of predicted
labels over the consensus set is significantly more than the accuracy of
predicted and given labels over the entire dataset. This gives us an idea of
why consensus-based RT is much better than full RT and baseline, even though
the consensus set is smaller than the full dataset.

Table 1: CIFAR-10. Test set accuracies (mean $\pm$ standard deviation). Consensus-based RT is better than full RT which is better than the baseline. $\epsilon$ | Baseline | Full RT | Consensus-based RT
---|---|---|---
1 | $57.78\pm 1.13$ | $60.07\pm 0.63$ | $\textbf{63.84}\pm 0.56$
2 | $79.06\pm 0.59$ | $81.34\pm 0.40$ | $\textbf{83.31}\pm 0.28$
3 | $85.18\pm 0.50$ | $86.67\pm 0.28$ | $\textbf{87.67}\pm 0.28$
Table 2: CIFAR-100. Test set accuracies (mean $\pm$ standard deviation). Overall, consensus-based RT is significantly better than full RT which is somewhat better than the baseline. $\epsilon$ | Baseline | Full RT | Consensus-based RT
---|---|---|---
3 | $23.53\pm 1.01$ | $24.42\pm 1.22$ | $\textbf{29.98}\pm 1.11$
4 | $44.53\pm 0.81$ | $46.99\pm 0.66$ | $\textbf{51.30}\pm 0.98$
5 | $55.75\pm 0.36$ | $56.98\pm 0.43$ | $\textbf{59.47}\pm 0.26$
Table 3: CIFAR-10. Accuracies of predicted labels and given labels over the entire (training) dataset and accuracies of predicted (= given) labels over the consensus set. Note that the accuracy of predicted labels over the consensus set $\gg$ accuracy of predicted labels over the entire dataset $\gg$ accuracy of given labels over the entire dataset. This gives us an idea of why consensus-based RT is much better than full RT and baseline, even though the consensus set is smaller than the full dataset ($\sim$ $31\%$, $55\%$ and $76\%$ of the full dataset for $\epsilon=1,2$ and $3$, respectively). $\epsilon$ |  Acc. of predicted labels on full dataset |  Acc. of given labels on full dataset |  Acc. of predicted labels on consensus set
---|---|---|---
1 | $59.30\pm 0.74$ | $32.61\pm 0.74$ | $\textbf{76.17}\pm 0.15$
2 | $81.62\pm 0.18$ | $57.11\pm 0.05$ | $\textbf{92.65}\pm 0.22$
3 | $89.28\pm 0.35$ | $76.73\pm 0.12$ | $\textbf{95.94}\pm 0.23$
Table 4: CIFAR-100. Accuracies of predicted labels and given labels over the entire (training) dataset and accuracies of predicted (= given) labels over the consensus set. Here the accuracy of predicted labels over the consensus set $\gg$ accuracy of predicted labels over the entire dataset $\approx$ accuracy of given labels over the entire dataset. This gives us an idea of why consensus-based RT is much better than full RT and baseline, even though the consensus set is much smaller than the full dataset ($\sim$ $11\%$, $34\%$ and $56\%$ of the full dataset for $\epsilon=3,4$ and $5$, respectively). But unlike CIFAR-10 (Table 3), here the accuracy of predicted labels over the entire dataset is not too much better than the given labels. Thus, full RT is only somewhat better than the baseline for CIFAR-100 (see Table 2). $\epsilon$ |  Acc. of predicted labels on full dataset |  Acc. of given labels on full dataset |  Acc. of predicted labels on consensus set
---|---|---|---
3 | $24.90\pm 0.92$ | $22.35\pm 0.41$ | $\textbf{76.09}\pm 0.85$
4 | $50.85\pm 0.82$ | $46.32\pm 0.34$ | $\textbf{91.59}\pm 1.24$
5 | $66.51\pm 0.02$ | $68.09\pm 0.33$ | $\textbf{94.83}\pm 0.15$

AG News Subset (https://www.tensorflow.org/datasets/catalog/ag_news_subset).
This is a news article classification dataset consisting of 4 categories –
world, sports, business or sci/tech. We reserve 10% of the given training set
for validation and we use the rest for training with label DP. Just like the
CIFAR experiments, we assume that the validation set comes with clean labels.
We use the small BERT model available in TensorFlow and the BERT English
uncased preprocessor; links to both of these are in Appendix H. We pool the
output of the BERT encoder, add a dropout layer with probability = 0.2,
followed by a softmax layer. We fine-tune the full model. Here, label DP
training is done with randomized response. We list the test accuracies of the
baseline (i.e., randomized response), full RT and consensus-based RT in Table
5 for three different values of $\epsilon$. Even here, consensus-based RT is
the clear winner. For the three values of $\epsilon$ in Table 5, the size of
the consensus set (used in consensus-based RT) is $\sim 28\%$, $32\%$ and
$38\%$, respectively, of the entire training set. So here, consensus-based RT
appreciably outperforms full RT and baseline with less than two-fifths of the
entire training set. Finally, in Table 6, we list the accuracies of predicted
labels and given labels over the entire dataset and accuracies of predicted (=
given) labels over the consensus set. Even here, the accuracy of predicted
labels over the consensus set is significantly more than the accuracy of
predicted and given labels over the entire dataset. This explains why
consensus-based RT performs the best, even though the consensus set is much
smaller than the full dataset.

Table 5: AG News Subset. Test set accuracies (mean $\pm$ standard deviation). Consensus-based RT is better than full RT which is better than the baseline. $\epsilon$ | Baseline | Full RT | Consensus-based RT
---|---|---|---
0.3 | $54.54\pm 0.97$ | $60.03\pm 2.90$ | $\bm{65.91}\pm 1.93$
0.5 | $69.21\pm 0.31$ | $75.63\pm 1.08$ | $\bm{80.95}\pm 1.47$
0.8 | $79.10\pm 1.43$ | $82.19\pm 1.54$ | $\bm{84.26}\pm 1.03$
Table 6: AG News Subset. Accuracies of predicted labels and given labels over the entire dataset and accuracies of predicted (= given) labels over the consensus set. Conclusions are the same as Table 3. $\epsilon$ |  Acc. of predicted labels on full dataset |  Acc. of given labels on full dataset |  Acc. of predicted labels on consensus set
---|---|---|---
0.3 | $53.20\pm 2.82$ | $32.52\pm 2.05$ | $\bm{61.81}\pm 2.66$
0.5 | $66.78\pm 1.31$ | $35.5\pm 0.14$ | $\bm{76.48}\pm 0.93$
0.8 | $79.98\pm 0.80$ | $42.53\pm 0.13$ | $\bm{89.59}\pm 0.43$

So in summary, consensus-based RT significantly improves model accuracy. In
Appendix I, we show that consensus-based RT also outperforms retraining on
samples for which the model is the most confident; this is similar to self-
training’s method of sample selection in the semi-supervised setting.
Furthermore, going beyond label DP, we show that consensus-based RT is also
beneficial in the presence of human annotation errors which can be thought of
as “real” label noise in Appendix J. Also, the test accuracies without label
DP for all the above datasets are listed in Appendix H.

##  6 Conclusion and Limitations

In this work, we provided the first theoretical result showing retraining with
hard labels can provably increase model accuracy in the presence of label
noise. We also showed the efficacy of consensus-based retraining (i.e.,
retraining on only those samples for which the predicted label matches the
given noisy label) in improving label DP training at no extra privacy cost.

We will conclude by discussing some limitations of our work which also pave
the way for some future directions of work. Our retraining analysis is done on
an unlabeled dataset different from the initial labeled dataset used for
vanilla training (due to certain technical complications). In the future, we
would like to analyze retraining on the same labeled dataset. We did not
investigate the tightness of the results in Theorem 5 and Remark 4;
investigating this is left for future work. Moreover, we have only analyzed
full retraining in this work. Given that consensus-based retraining worked
very well empirically, we would like to analyze it theoretically later.
Another potential extension of our work is to analyze retraining under non-
uniform label noise models. Our experiments in this paper are not on very
large-scale models or datasets. We hope to test our ideas on larger scale
problems in the future.

## References

  * Abramowitz and Stegun, (1968) Abramowitz, M. and Stegun, I. A. (1968).  Handbook of mathematical functions with formulas, graphs, and mathematical tables, volume 55.  US Government printing office.
  * Amini et al., (2022) Amini, M.-R., Feofanov, V., Pauletto, L., Devijver, E., and Maximov, Y. (2022).  Self-training: A survey.  arXiv preprint arXiv:2202.12040.
  * Badanidiyuru et al., (2023) Badanidiyuru, A., Ghazi, B., Kamath, P., Kumar, R., Leeman, E., Manurangsi, P., Varadarajan, A. V., and Zhang, C. (2023).  Optimal unbiased randomizers for regression with label differential privacy.  arXiv preprint arXiv:2312.05659.
  * Ball et al., (1997) Ball, K. et al. (1997).  An elementary introduction to modern convex geometry.  Flavors of geometry, 31(1-58):26.
  * Beimel et al., (2013) Beimel, A., Nissim, K., and Stemmer, U. (2013).  Private learning and sanitization: Pure vs. approximate differential privacy.  In International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 363–378. Springer.
  * Carmon et al., (2019) Carmon, Y., Raghunathan, A., Schmidt, L., Duchi, J. C., and Liang, P. S. (2019).  Unlabeled data improves adversarial robustness.  Advances in neural information processing systems, 32.
  * Chaudhuri and Hsu, (2011) Chaudhuri, K. and Hsu, D. (2011).  Sample complexity bounds for differentially private learning.  In Proceedings of the 24th Annual Conference on Learning Theory, pages 155–186. JMLR Workshop and Conference Proceedings.
  * Chen et al., (2020) Chen, Y., Wei, C., Kumar, A., and Ma, T. (2020).  Self-training avoids using spurious features under domain shift.  Advances in Neural Information Processing Systems, 33:21061–21071.
  * Das and Sanghavi, (2023) Das, R. and Sanghavi, S. (2023).  Understanding self-distillation in the presence of label noise.  In International Conference on Machine Learning, pages 7102–7140. PMLR.
  * Dong et al., (2019) Dong, B., Hou, J., Lu, Y., and Zhang, Z. (2019).  Distillation $\approx$ early stopping? harvesting dark knowledge utilizing anisotropic information retrieval for overparameterized neural network.  arXiv preprint arXiv:1910.01255.
  * Furlanello et al., (2018) Furlanello, T., Lipton, Z., Tschannen, M., Itti, L., and Anandkumar, A. (2018).  Born again neural networks.  In International Conference on Machine Learning, pages 1607–1616. PMLR.
  * Gentile and Helmbold, (1998) Gentile, C. and Helmbold, D. P. (1998).  Improved lower bounds for learning from noisy examples: An information-theoretic approach.  In Proceedings of the eleventh annual conference on Computational learning theory, pages 104–115.
  * Ghazi et al., (2021) Ghazi, B., Golowich, N., Kumar, R., Manurangsi, P., and Zhang, C. (2021).  Deep learning with label differential privacy.  Advances in neural information processing systems, 34:27131–27145.
  * Ghazi et al., (2022) Ghazi, B., Kamath, P., Kumar, R., Leeman, E., Manurangsi, P., Varadarajan, A. V., and Zhang, C. (2022).  Regression with label differential privacy.  arXiv preprint arXiv:2212.06074.
  * Ghosh, (2021) Ghosh, M. (2021).  Exponential tail bounds for chisquared random variables.  Journal of Statistical Theory and Practice, 15(2):35.
  * Goel et al., (2022) Goel, A., Jiao, Y., and Massiah, J. (2022).  Pars: Pseudo-label aware robust sample selection for learning with noisy labels.  arXiv preprint arXiv:2201.10836.
  * Han et al., (2019) Han, J., Luo, P., and Wang, X. (2019).  Deep self-learning from noisy labels.  In Proceedings of the IEEE/CVF international conference on computer vision, pages 5138–5147.
  * Hinton et al., (2015) Hinton, G., Vinyals, O., Dean, J., et al. (2015).  Distilling the knowledge in a neural network.  arXiv preprint arXiv:1503.02531, 2(7).
  * Jin et al., (2019) Jin, C., Netrapalli, P., Ge, R., Kakade, S. M., and Jordan, M. I. (2019).  A short note on concentration inequalities for random vectors with subgaussian norm.  arXiv preprint arXiv:1902.03736.
  * Kumar et al., (2020) Kumar, A., Ma, T., and Liang, P. (2020).  Understanding self-training for gradual domain adaptation.  In International conference on machine learning, pages 5468–5479. PMLR.
  * Lee et al., (2013) Lee, D.-H. et al. (2013).  Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks.  In Workshop on challenges in representation learning, ICML, volume 3, page 896. Atlanta.
  * Li et al., (2020) Li, J., Socher, R., and Hoi, S. C. (2020).  Dividemix: Learning with noisy labels as semi-supervised learning.  arXiv preprint arXiv:2002.07394.
  * Li et al., (2017) Li, Y., Yang, J., Song, Y., Cao, L., Luo, J., and Li, L.-J. (2017).  Learning from noisy labels with distillation.  In Proceedings of the IEEE International Conference on Computer Vision, pages 1910–1918.
  * Malek Esmaeili et al., (2021) Malek Esmaeili, M., Mironov, I., Prasad, K., Shilov, I., and Tramer, F. (2021).  Antipodes of label differential privacy: Pate and alibi.  Advances in Neural Information Processing Systems, 34:6934–6945.
  * Mobahi et al., (2020) Mobahi, H., Farajtabar, M., and Bartlett, P. (2020).  Self-distillation amplifies regularization in hilbert space.  Advances in Neural Information Processing Systems, 33:3351–3361.
  * Nguyen et al., (2019) Nguyen, D. T., Mummadi, C. K., Ngo, T. P. N., Nguyen, T. H. P., Beggel, L., and Brox, T. (2019).  Self: Learning to filter noisy labels with self-ensembling.  arXiv preprint arXiv:1910.01842.
  * Oymak and Gulcu, (2020) Oymak, S. and Gulcu, T. C. (2020).  Statistical and algorithmic insights for semi-supervised learning with self-training.  arXiv preprint arXiv:2006.11006.
  * Raghunathan et al., (2020) Raghunathan, A., Xie, S. M., Yang, F., Duchi, J., and Liang, P. (2020).  Understanding and mitigating the tradeoff between robustness and accuracy.  arXiv preprint arXiv:2002.10716.
  * Reed et al., (2014) Reed, S., Lee, H., Anguelov, D., Szegedy, C., Erhan, D., and Rabinovich, A. (2014).  Training deep neural networks on noisy labels with bootstrapping.  arXiv preprint arXiv:1412.6596.
  * Rinaldo and Neopane, (2018) Rinaldo, A. and Neopane, O. (2018).  Advanced statistical theory: Lecture 13.  https://www.stat.cmu.edu/~arinaldo/Teaching/36709/S19/Scribed_Lectures/Feb26_Ojash.pdf.
  * Scarlett and Cevher, (2019) Scarlett, J. and Cevher, V. (2019).  An introductory guide to fano’s inequality with applications in statistical estimation.  arXiv preprint arXiv:1901.00555.
  * Scudder, (1965) Scudder, H. (1965).  Probability of error of some adaptive pattern-recognition machines.  IEEE Transactions on Information Theory, 11(3):363–371.
  * Sohn et al., (2020) Sohn, K., Berthelot, D., Carlini, N., Zhang, Z., Zhang, H., Raffel, C. A., Cubuk, E. D., Kurakin, A., and Li, C.-L. (2020).  Fixmatch: Simplifying semi-supervised learning with consistency and confidence.  Advances in neural information processing systems, 33:596–608.
  * Tanaka et al., (2018) Tanaka, D., Ikami, D., Yamasaki, T., and Aizawa, K. (2018).  Joint optimization framework for learning with noisy labels.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5552–5560.
  * Tang et al., (2022) Tang, X., Nasr, M., Mahloujifar, S., Shejwalkar, V., Song, L., Houmansadr, A., and Mittal, P. (2022).  Machine learning with differentially private labels: Mechanisms and frameworks.  Proceedings on Privacy Enhancing Technologies.
  * Wang and Xu, (2019) Wang, D. and Xu, J. (2019).  On sparse linear regression in the local differential privacy model.  In International Conference on Machine Learning, pages 6628–6637. PMLR.
  * Warner, (1965) Warner, S. L. (1965).  Randomized response: A survey technique for eliminating evasive answer bias.  Journal of the American Statistical Association, 60(309):63–69.
  * Wei et al., (2020) Wei, C., Shen, K., Chen, Y., and Ma, T. (2020).  Theoretical analysis of self-training with deep networks on unlabeled data.  arXiv preprint arXiv:2010.03622.
  * Wei et al., (2021) Wei, J., Zhu, Z., Cheng, H., Liu, T., Niu, G., and Liu, Y. (2021).  Learning with noisy labels revisited: A study using real-world human annotations.  arXiv preprint arXiv:2110.12088.
  * Yarowsky, (1995) Yarowsky, D. (1995).  Unsupervised word sense disambiguation rivaling supervised methods.  In 33rd annual meeting of the association for computational linguistics, pages 189–196.
  * Zhang et al., (2022) Zhang, S., Wang, M., Liu, S., Chen, P.-Y., and Xiong, J. (2022).  How does unlabeled data improve generalization in self-training? a one-hidden-layer theoretical analysis.  arXiv preprint arXiv:2201.08514.
  * Zhang et al., (2015) Zhang, X., Zhao, J., and LeCun, Y. (2015).  Character-level convolutional networks for text classification.  Advances in neural information processing systems, 28.

Appendix

## Contents:

  * •

Appendix A: Problem Setting of Figure 1

  * •

Appendix B: Proof of Theorem 1

  * •

Appendix C: Proof of Theorem 2

  * •

Appendix D: Proof of Theorem 3

  * •

Appendix E: Proof of Theorem 4

  * •

Appendix F: Proof of Theorem 5

  * •

Appendix G: Roadmap of Analysis with Exact Minimizer $\bar{\bm{\theta}}_{0}$

  * •

Appendix H: Remaining Experimental Details

  * •

Appendix I: Consensus-Based Retraining Does Better than Confidence-Based
Retraining

  * •

Appendix J: Beyond Label DP: Evaluating Retraining in the Presence of Human
Annotation Errors

##  Appendix A Problem Setting of Figure 1

The setting is exactly the same as the problem setting in Section 4 with
$\bm{\theta}^{*}={\mathbf{e}}_{1}$,
$\mathcal{B}=\\{{\mathbf{e}}_{1},{\mathbf{e}}_{2},\ldots,{\mathbf{e}}_{d}\\}$,
$\sigma=1$, $d=50$ and $p=0.4$, except for the distribution of
${\mathrm{a}}^{(1)}$ which is equal to ${\mathrm{x}}^{(1)}$ as
$\bm{\theta}^{*}={\mathbf{e}}_{1}$. Specifically for some $\Delta>0$,
${\mathrm{x}}^{(1)}$ is drawn from $\text{Unif}[\Delta,5\Delta]$ with
probability $\frac{1}{2}$ or from $\text{Unif}[-5\Delta,-\Delta]$ otherwise
($\text{Unif}[a,b]$ denotes the uniform distribution over the interval
$[a,b]$). Note that this distribution is similar in principle to the one
assumed in Section 4 (where we did not assume ${\mathrm{a}}^{(1)}$ to have any
specific distribution). In Figure 1(a), $\Delta=0.5$ (large separation) and in
Figure 1(b), $\Delta=0.3$ (small separation). The number of training samples
in each case is 300 and the retraining is done on the same training set on
which the model is initially trained. The learned classifiers from vanilla
training and retraining are the same as in Section 4 (i.e., eq. 2 and eq. 3,
respectively). Finally, the test accuracy of both vanilla training and
retraining in Figure 1(b) is $68\%$.

##  Appendix B Proof of Theorem 1

###### Proof.

Recall the problem setting at the beginning of Section 4. Without loss of
generality, we can prove the result for $\bm{\theta}^{\ast}={\mathbf{e}}_{1}$
and
$\mathcal{B}=\\{{\mathbf{e}}_{1},{\mathbf{e}}_{2},\ldots,{\mathbf{e}}_{d}\\}$
(i.e., the canonical basis). In that case,
${\mathrm{a}}^{(j)}={\mathrm{x}}^{(j)}=\langle{\mathbf{x}},{\mathbf{e}}_{j}\rangle$
for $j\in[d]$. Let ${\mathrm{y}}=\text{sign}({\mathrm{x}}^{(1)})$ be the
ground truth label of ${\mathbf{x}}$. Note that proving Theorem 1 is
equivalent to proving the following statement. For a sample
${\mathbf{x}}\notin\mathcal{X}_{L}$, the following holds with a probability of
at least
$\alpha({\mathbf{x}})=1-\exp\Big{(}-\frac{n\mu^{2}}{4}(1-2p)^{2}\textup{cos}^{2}\big{(}\beta({\mathbf{x}})\big{)}\Big{)}$
and at most
$\widehat{\alpha}({\mathbf{x}})=1-\frac{1}{3\sqrt{2\pi}}{\exp\Big{(}-{\big{(}1+\sqrt{n}\mu(1-2p)\big{)}^{2}\textup{cot}^{2}\big{(}\beta({\mathbf{x}})\big{)}}\Big{)}}$:

$\begin{cases}\langle{\mathbf{x}},\widehat{\bm{\theta}}_{0}\rangle\geq 0\text{
when }{\mathrm{y}}=1\text{ i.e., }{\mathrm{x}}^{(1)}\geq 0,\\\
\langle{\mathbf{x}},\widehat{\bm{\theta}}_{0}\rangle<0\text{ when
}{\mathrm{y}}=-1\text{ i.e., }{\mathrm{x}}^{(1)}<0.\end{cases}$ (7)

(a) Lower bound $\alpha({\mathbf{x}})$. First note that
$\big{|}\textup{cos}\big{(}\beta({\mathbf{x}})\big{)}\big{|}=\frac{|{\mathrm{x}}^{(1)}|}{\|{\mathbf{x}}\|}$
in our choice of basis for the proof. We will prove the result for the case of
${\mathrm{y}}=1$ or equivalently ${\mathrm{x}}^{(1)}\geq 0$; the result for
the other case (i.e., ${\mathrm{y}}=-1$ or equivalently
${\mathrm{x}}^{(1)}<0$) can be derived similarly.

We have:

$\langle{\mathbf{x}},\widehat{\bm{\theta}}_{0}\rangle=\frac{1}{\sigma^{2}}\Bigg{\\{}\frac{1}{n}\sum_{k=1}^{n}\widehat{\mathrm{y}}_{k}\langle{\mathbf{x}}_{k},{\mathbf{x}}\rangle\Bigg{\\}}.$
(8)

Since $\frac{1}{n\sigma^{2}}$ is a constant independent of the training set
$\mathcal{T}$, we will analyze

$\varepsilon=\sum_{k=1}^{n}\widehat{\mathrm{y}}_{k}\langle{\mathbf{x}}_{k},{\mathbf{x}}\rangle.$
(9)

Using the Chernoff bound, we have for any $r<0$:

$\displaystyle\mathbb{P}\big{(}\varepsilon\leq 0\big{)}$
$\displaystyle=\mathbb{P}\big{(}\exp\big{(}r\varepsilon\big{)}\geq
1\big{)}\leq\mathbb{E}\Big{[}\exp\big{(}r\varepsilon\big{)}\Big{]}.$ (10)

For $k\in[n]$, let
$\varepsilon_{k}:=\widehat{\mathrm{y}}_{k}\langle{\mathbf{x}}_{k},{\mathbf{x}}\rangle$;
thus, $\varepsilon=\sum_{k\in[n]}\varepsilon_{k}$. For any $r\in\mathbb{R}$,
we have:

$\displaystyle\mathbb{E}\Big{[}\exp\big{(}r\varepsilon\big{)}\Big{]}=\mathbb{E}\Big{[}\exp\big{(}r\sum_{k\in[n]}\varepsilon_{k}\big{)}\Big{]}=\mathbb{E}\Big{[}\prod_{k\in[n]}\exp\big{(}r\varepsilon_{k}\big{)}\Big{]}=\Big{(}\mathbb{E}\Big{[}\exp\big{(}r\varepsilon_{1}\big{)}\Big{]}\Big{)}^{n},$
(11)

where the last step follows because of the i.i.d. nature of the data and label
noise. Now:

$\displaystyle\mathbb{E}\Big{[}\exp\big{(}r\varepsilon_{1}\big{)}\Big{]}$
$\displaystyle=\mathbb{E}\Big{[}\exp\big{(}r\widehat{\mathrm{y}}_{1}\langle{\mathbf{x}}_{1},{\mathbf{x}}\rangle\big{)}\Big{]}.$
(12)

Using the definition of $\widehat{\mathrm{y}}_{1}$ from eq. 1, we have:

$\displaystyle\mathbb{E}\Big{[}\exp\big{(}r\widehat{\mathrm{y}}_{1}\langle{\mathbf{x}}_{1},{\mathbf{x}}\rangle\big{)}\Big{]}$
$\displaystyle=\Bigg{(}(1-p)\mathbb{E}\Big{[}\exp\big{(}r{\mathrm{y}}_{1}\langle{\mathbf{x}}_{1},{\mathbf{x}}\rangle\big{)}\Big{]}+p\mathbb{E}\Big{[}\exp\big{(}-r{\mathrm{y}}_{1}\langle{\mathbf{x}}_{1},{\mathbf{x}}\rangle\big{)}\Big{]}\Bigg{)}.$
(13)

So now we need to evaluate
$\mathbb{E}\Big{[}\exp\big{(}r{\mathrm{y}}_{1}\langle{\mathbf{x}}_{1},{\mathbf{x}}\rangle\big{)}\Big{]}$
and
$\mathbb{E}\Big{[}\exp\big{(}-r{\mathrm{y}}_{1}\langle{\mathbf{x}}_{1},{\mathbf{x}}\rangle\big{)}\Big{]}$.
Recalling that
${\mathrm{y}}_{1}=\text{sign}\big{(}{\mathrm{x}}_{1}^{(1)}\big{)}$, we have:

$\mathbb{E}\Big{[}\exp\big{(}r{\mathrm{y}}_{1}\langle{\mathbf{x}}_{1},{\mathbf{x}}\rangle\big{)}\Big{]}=\mathbb{E}\Bigg{[}\exp\Bigg{(}r\text{sign}\big{(}{\mathrm{x}}_{1}^{(1)}\big{)}\Bigg{(}{\mathrm{x}}_{1}^{(1)}{\mathrm{x}}^{(1)}+\sum_{j=2}^{d}{\mathrm{x}}_{1}^{(j)}{\mathrm{x}}^{(j)}\Bigg{)}\Bigg{)}\Bigg{]},$
(14)

Simplifying the above by using the independence of ${\mathrm{x}}_{1}^{(j)}$’s
and recalling that each ${\mathrm{x}}_{1}^{(j)}\sim\mathcal{N}(0,\sigma^{2})$
for $j\in\\{2,\ldots,d\\}$, we get:

$\displaystyle\mathbb{E}\Big{[}\exp\big{(}r{\mathrm{y}}_{1}\langle{\mathbf{x}}_{1},{\mathbf{x}}\rangle\big{)}\Big{]}$
$\displaystyle=\mathbb{E}_{{\mathrm{x}}_{1}^{(1)},{\mathrm{x}}_{1}^{(2)},\ldots,{\mathrm{x}}_{1}^{(d)}}\Bigg{[}\exp\Big{(}r{\mathrm{x}}^{(1)}\big{|}{\mathrm{x}}_{1}^{(1)}\big{|}\Big{)}\prod_{j=2}^{d}\exp\Big{(}r{\mathrm{x}}^{(j)}\text{sign}\big{(}{\mathrm{x}}_{1}^{(1)}\big{)}{\mathrm{x}}_{1}^{(j)}\Big{)}\Bigg{]}$
(15)
$\displaystyle=\mathbb{E}_{{\mathrm{x}}_{1}^{(1)}}\Bigg{[}\exp\Big{(}r{\mathrm{x}}^{(1)}\big{|}{\mathrm{x}}_{1}^{(1)}\big{|}\Big{)}\prod_{j=2}^{d}\mathbb{E}_{{\mathrm{x}}_{1}^{(j)}}\Big{[}\exp\Big{(}r{\mathrm{x}}^{(j)}\text{sign}\big{(}{\mathrm{x}}_{1}^{(1)}\big{)}{\mathrm{x}}_{1}^{(j)}\Big{)}\Big{]}\Bigg{]}$
(16)
$\displaystyle=\mathbb{E}_{{\mathrm{x}}_{1}^{(1)}}\Bigg{[}\exp\Big{(}r{\mathrm{x}}^{(1)}\big{|}{\mathrm{x}}_{1}^{(1)}\big{|}\Big{)}\prod_{j=2}^{d}\exp\Bigg{(}\frac{\big{(}\sigma
r{\mathrm{x}}^{(j)}\text{sign}\big{(}{\mathrm{x}}_{1}^{(1)}\big{)}\big{)}^{2}}{2}\Bigg{)}\Bigg{]}$
(17)
$\displaystyle={\mathbb{E}_{{\mathrm{x}}_{1}^{(1)}}\Bigg{[}\exp\Big{(}r{\mathrm{x}}^{(1)}\big{|}{\mathrm{x}}_{1}^{(1)}\big{|}\Big{)}\Bigg{]}}\exp\Bigg{(}\frac{(\sigma
r)^{2}}{2}\sum_{j=2}^{d}\big{(}{\mathrm{x}}^{(j)}\big{)}^{2}\Bigg{)}$ (18)
$\displaystyle\leq\exp\big{(}\mu\sigma
r{\mathrm{x}}^{(1)}\big{)}\exp\Bigg{(}\frac{(\sigma
r)^{2}}{2}({\mathrm{x}}^{(1)})^{2}\Bigg{)}\exp\Bigg{(}\frac{(\sigma
r)^{2}}{2}\Big{(}\|{\mathbf{x}}\|^{2}-({\mathrm{x}}^{(1)})^{2}\Big{)}\Bigg{)}$
(19) $\displaystyle=\exp\big{(}\mu\sigma
r{\mathrm{x}}^{(1)}\big{)}\exp\Bigg{(}\frac{(\sigma
r\|{\mathbf{x}}\|)^{2}}{2}\Bigg{)}.$ (20)

Equation 17 follows from the standard formula of the moment-generating
function of a zero-mean Gaussian. Equation 19 follows because
$|{\mathrm{x}}_{1}^{(1)}|$ is SG($\sigma^{2}$) with
$\mathbb{E}\big{[}|{\mathrm{x}}^{(1)}|\big{]}=\mu\sigma$ and
$\sum_{j=1}^{d}\big{(}{\mathrm{x}}^{(j)}\big{)}^{2}=\|{\mathbf{x}}\|^{2}$.
Since the derivation above holds for any $r\in\mathbb{R}$, we also have:

$\displaystyle\mathbb{E}\Big{[}\exp\big{(}-r{\mathrm{y}}_{1}\langle{\mathbf{x}}_{1},{\mathbf{x}}\rangle\big{)}\Big{]}$
$\displaystyle\leq\exp\big{(}-\mu\sigma
r{\mathrm{x}}^{(1)}\big{)}\exp\Bigg{(}\frac{(\sigma
r\|{\mathbf{x}}\|)^{2}}{2}\Bigg{)}.$ (21)

Next, plugging in equations (20) and (21) into eq. 13, we get:

$\displaystyle\mathbb{E}\Big{[}\exp\big{(}r\widehat{\mathrm{y}}_{1}\langle{\mathbf{x}}_{1},{\mathbf{x}}\rangle\big{)}\Big{]}$
$\displaystyle\leq\exp\Bigg{(}\frac{(\sigma
r\|{\mathbf{x}}\|)^{2}}{2}\Bigg{)}\Big{(}(1-p)\exp\big{(}\mu\sigma
r{\mathrm{x}}^{(1)}\big{)}+p\exp\big{(}-\mu\sigma
r{\mathrm{x}}^{(1)}\big{)}\Big{)}$ (22)
$\displaystyle=\exp\Bigg{(}\frac{(\sigma r\|{\mathbf{x}}\|)^{2}}{2}+\mu\sigma
r{\mathrm{x}}^{(1)}\Bigg{)}\Big{(}1-p+p\exp\big{(}-2\mu\sigma
r{\mathrm{x}}^{(1)}\big{)}\Big{)}$ (23)
$\displaystyle\leq\exp\Bigg{(}\frac{(\sigma
r\|{\mathbf{x}}\|)^{2}}{2}+\mu\sigma
r{\mathrm{x}}^{(1)}-p+p\exp\big{(}-2\mu\sigma
r{\mathrm{x}}^{(1)}\big{)}\Bigg{)},$ (24)

where the last step follows because $\exp(z)\geq 1+z$ for all
$z\in\mathbb{R}$. Substituting eq. 24 into eq. 12 followed by eq. 11 yields:

$\mathbb{E}\Big{[}\exp\big{(}r\varepsilon\big{)}\Big{]}\leq\exp\Bigg{(}n\Bigg{\\{}\frac{(\sigma
r\|{\mathbf{x}}\|)^{2}}{2}+\mu\sigma
r{\mathrm{x}}^{(1)}-p+p\exp\big{(}-2\mu\sigma
r{\mathrm{x}}^{(1)}\big{)}\Bigg{\\}}\Bigg{)}.$ (25)

Plugging in eq. 25 into eq. 10, we get:

$\mathbb{P}\big{(}\varepsilon\leq
0\big{)}\leq\exp\Bigg{(}n\Bigg{\\{}\underbrace{\frac{(\sigma
r\|{\mathbf{x}}\|)^{2}}{2}+\mu\sigma
r{\mathrm{x}}^{(1)}-p+p\exp\big{(}-2\mu\sigma
r{\mathrm{x}}^{(1)}\big{)}}_{:=\nu}\Bigg{\\}}\Bigg{)},$ (26)

for any $r<0$. Let $\nu:=\frac{(\sigma r\|{\mathbf{x}}\|)^{2}}{2}+\mu\sigma
r{\mathrm{x}}^{(1)}-p+p\exp\big{(}-2\mu\sigma r{\mathrm{x}}^{(1)}\big{)}$. We
will pick
$r=-c\Big{(}\frac{\mu{\mathrm{x}}^{(1)}}{\sigma\|{\mathbf{x}}\|^{2}}\Big{)}$
for some $c\in(0,1)$. Putting this into the expression of $\nu$, we get:

$\nu=\mu^{2}\Bigg{(}\frac{{\mathrm{x}}^{(1)}}{\|{\mathbf{x}}\|}\Bigg{)}^{2}\Big{(}\frac{c^{2}}{2}-c\Big{)}+p\Bigg{(}\exp\Bigg{(}2c\mu^{2}\Bigg{(}\frac{{\mathrm{x}}^{(1)}}{\|{\mathbf{x}}\|}\Bigg{)}^{2}\Bigg{)}-1\Bigg{)}$
(27)

For brevity, let
$u=\mu^{2}\Big{(}\frac{{\mathrm{x}}^{(1)}}{\|{\mathbf{x}}\|}\Big{)}^{2}$. Note
that $u\leq\frac{1}{4}$, as $\mu\leq\frac{1}{2}$ and
${\mathrm{x}}^{(1)}\leq\|{\mathbf{x}}\|$. Rewriting the above equation in
terms of $u$, we get:

$\nu=u\Big{(}\frac{c^{2}}{2}-c\Big{)}+p\big{(}\exp(2cu)-1\big{)}$ (28)

Note that $2cu\leq\frac{1}{2}$ as $c\leq 1$ and $u\leq\frac{1}{4}$. Therefore,
applying Lemma 1 above, we get:

$\displaystyle\nu\leq
u\Big{(}\frac{c^{2}}{2}-c\Big{)}+p\big{(}2cu+4c^{2}u^{2}\big{)}\leq\underbrace{u\Big{(}\frac{c^{2}}{2}-c\Big{)}+p\big{(}2cu+c^{2}u\big{)}}_{\text{(A)}},$
(29)

where the last step is obtained by using the fact that $u\leq\frac{1}{4}$. (A)
is minimized by choosing $c=\frac{1-2p}{1+2p}$. With this choice of $c$, we
get:

$\nu\leq-\frac{u}{2}\Bigg{(}\frac{(1-2p)^{2}}{1+2p}\Bigg{)}.$ (30)

Further using the fact $1+2p\leq 2$ and plugging in the value of
$u=\mu^{2}\Big{(}\frac{{\mathrm{x}}^{(1)}}{\|{\mathbf{x}}\|}\Big{)}^{2}$
above, we get:

$\nu\leq-\frac{\mu^{2}}{4}(1-2p)^{2}\Bigg{(}\frac{{\mathrm{x}}^{(1)}}{\|{\mathbf{x}}\|}\Bigg{)}^{2}.$
(31)

Plugging this into eq. 26 and recalling that
$\big{|}\textup{cos}\big{(}\beta({\mathbf{x}})\big{)}\big{|}=\frac{|{\mathrm{x}}^{(1)}|}{\|{\mathbf{x}}\|}$,
we get:

$\mathbb{P}\big{(}\varepsilon\leq
0\big{)}\leq\exp\Bigg{(}-\frac{n\mu^{2}}{4}(1-2p)^{2}\textup{cos}^{2}\big{(}\beta({\mathbf{x}})\big{)}\Bigg{)}.$
(32)

Recalling the definition of $\varepsilon$ (eq. 9) and using the result before
that in eq. 8, we obtain the following bound for the case of ${\mathrm{y}}=1$:

$\mathbb{P}\Big{(}\langle{\mathbf{x}},\widehat{\bm{\theta}}_{0}\rangle\leq
0\Big{)}\leq\exp\Bigg{(}-\frac{n\mu^{2}}{4}(1-2p)^{2}\textup{cos}^{2}\big{(}\beta({\mathbf{x}})\big{)}\Bigg{)}.$
(33)

This finishes the proof of the result for the case of ${\mathrm{y}}=1$. The
result for the other case, i.e. ${\mathrm{y}}=-1$, can be derived similarly as
above by analyzing with $r>0$ instead. In particular, for the case of
${\mathrm{y}}=-1$, we get:

$\mathbb{P}\Big{(}\langle{\mathbf{x}},\widehat{\bm{\theta}}_{0}\rangle>0\Big{)}\leq\exp\Bigg{(}-\frac{n\mu^{2}}{4}(1-2p)^{2}\textup{cos}^{2}\big{(}\beta({\mathbf{x}})\big{)}\Bigg{)}.$
(34)

(b) Upper bound $\widehat{\alpha}({\mathbf{x}})$. From eq. 8 and eq. 9, recall
that:

$\langle{\mathbf{x}},\widehat{\bm{\theta}}_{0}\rangle=\frac{\varepsilon}{n\sigma^{2}},\text{
where
}\varepsilon=\sum_{k=1}^{n}\widehat{\mathrm{y}}_{k}\langle{\mathbf{x}}_{k},{\mathbf{x}}\rangle.$
(35)

Again, we will prove the result for the case of ${\mathrm{y}}=1$ (i.e.,
${\mathrm{x}}^{(1)}>0$); the result for the other case can be derived
similarly.

Note that:

$\varepsilon=\sum_{k=1}^{n}\widehat{\mathrm{y}}_{k}\mathrm{x}_{k}^{(1)}\mathrm{x}^{(1)}+\underbrace{\sum_{k=1}^{n}\widehat{\mathrm{y}}_{k}\sum_{l=2}^{d}\mathrm{x}_{k}^{(l)}\mathrm{x}^{(l)}}_{\tilde{\varepsilon}}.$
(36)

Conditioned on $\widehat{\mathrm{y}}_{k}$ and $\mathrm{x}_{k}^{(1)}$,
$\tilde{\varepsilon}\sim\mathcal{N}\big{(}0,n\sigma^{2}\sum_{l=2}^{d}(\mathrm{x}^{(l)})^{2}\big{)}$
using the fact that
$\mathrm{x}^{(1)},\mathrm{x}^{(2)},\ldots,\mathrm{x}^{(d)}$ are all
independent of each other. But
$\sum_{l=2}^{d}(\mathrm{x}^{(l)})^{2}=\|{\mathbf{x}}\|^{2}-(\mathrm{x}^{(1)})^{2}=\|{\mathbf{x}}\|^{2}\Big{(}1-\textup{cos}^{2}\big{(}\beta({\mathbf{x}})\big{)}\Big{)}=\|{\mathbf{x}}\|^{2}\textup{sin}^{2}\big{(}\beta({\mathbf{x}})\big{)}$.
So in other words, conditioned on $\widehat{\mathrm{y}}_{k}$ and
$\mathrm{x}_{k}^{(1)}$,
$\tilde{\varepsilon}\sim\mathcal{N}\big{(}0,n\sigma^{2}\|{\mathbf{x}}\|^{2}\textup{sin}^{2}\big{(}\beta({\mathbf{x}})\big{)}\big{)}$.
Also, recalling that ${\mathrm{y}}_{k}=\text{sign}(\mathrm{x}_{k}^{(1)})$ and
${\mathrm{x}}^{(1)}>0$, we have that
$\widehat{\mathrm{y}}_{k}\mathrm{x}_{k}^{(1)}\mathrm{x}^{(1)}=\widehat{\mathrm{y}}_{k}{\mathrm{y}}_{k}\big{|}\mathrm{x}_{k}^{(1)}\big{|}\big{|}\mathrm{x}^{(1)}\big{|}$.
Let $\delta_{k}:=\widehat{\mathrm{y}}_{k}{\mathrm{y}}_{k}$. Using eq. 1, we
have:

$\delta_{k}=\begin{cases}1\quad\text{ w.p. }1-p,\\\ -1\quad\text{
o/w.}\end{cases}$ (37)

Moreover, $\delta_{k}$ is independent of $\mathrm{x}_{k}^{(1)}$. Using of all
this, we get:

$\displaystyle\mathbb{P}\big{(}\varepsilon\leq 0\big{)}$
$\displaystyle=\mathbb{P}\Big{(}\sum_{k=1}^{n}\delta_{k}\big{|}\mathrm{x}_{k}^{(1)}\big{|}\big{|}\mathrm{x}^{(1)}\big{|}+\varepsilon\leq
0\Big{)}$ (38)
$\displaystyle=\mathbb{E}_{\big{\\{}\delta_{k},\mathrm{x}_{k}^{(1)}\big{\\}}_{k=1}^{n}}\Bigg{[}\Phi\Bigg{(}-\frac{\sum_{k=1}^{n}\delta_{k}\big{|}\mathrm{x}_{k}^{(1)}\big{|}\big{|}\mathrm{x}^{(1)}\big{|}}{\sqrt{n}\sigma\|{\mathbf{x}}\|\big{|}\textup{sin}\big{(}\beta({\mathbf{x}})\big{)}\big{|}}\Bigg{)}\Bigg{]}$
(39)
$\displaystyle\geq\mathbb{E}_{\big{\\{}\delta_{k},\mathrm{x}_{k}^{(1)}\big{\\}}_{k=1}^{n}}\Bigg{[}\Phi\Bigg{(}-\frac{\big{|}\sum_{k=1}^{n}\delta_{k}\big{|}\mathrm{x}_{k}^{(1)}\big{|}\big{|}\times\big{|}\mathrm{x}^{(1)}\big{|}}{\sqrt{n}\sigma\|{\mathbf{x}}\|\big{|}\textup{sin}\big{(}\beta({\mathbf{x}})\big{)}\big{|}}\Bigg{)}\Bigg{]}.$
(40)

Using the convexity of $\Phi(.)$ on $\mathbb{R}_{\leq 0}$, we can further
lower bound eq. 40 by:

$\displaystyle\mathbb{P}\big{(}\varepsilon\leq 0\big{)}$
$\displaystyle\geq\Phi\Bigg{(}-\frac{\mathbb{E}\Big{[}\big{|}\sum_{k=1}^{n}\delta_{k}\big{|}\mathrm{x}_{k}^{(1)}\big{|}\big{|}\Big{]}\times\big{|}\mathrm{x}^{(1)}\big{|}}{\sqrt{n}\sigma\|{\mathbf{x}}\|\big{|}\textup{sin}\big{(}\beta({\mathbf{x}})\big{)}\big{|}}\Bigg{)},$
(41)

using Jensen’s inequality. Using the result of Lemma 2 and the fact that
$\big{|}\mathrm{x}^{(1)}\big{|}=\|{\mathbf{x}}\|\big{|}\textup{cos}\big{(}\beta({\mathbf{x}})\big{)}\big{|}$
above, we get:

$\displaystyle\mathbb{P}\big{(}\varepsilon\leq 0\big{)}$
$\displaystyle\geq\Phi\Big{(}-{\big{(}1+\sqrt{n}\mu(1-2p)\big{)}\big{|}\textup{cot}\big{(}\beta({\mathbf{x}})\big{)}\big{|}}\Big{)}.$
(42)

Recalling eq. 35 and using the fact that $\Phi(-z)=\Phi^{\text{c}}(z)$ for all
$z\in\mathbb{R}$ (recall that $\Phi^{\text{c}}(.)$ is the complementary CDF of
a standard normal variable), we obtain the following bound for the case of
${\mathrm{y}}=1$:

$\mathbb{P}\Big{(}\langle{\mathbf{x}},\widehat{\bm{\theta}}_{0}\rangle\leq
0\Big{)}\geq\Phi^{\text{c}}\Big{(}{\big{(}1+\sqrt{n}\mu(1-2p)\big{)}\big{|}\textup{cot}\big{(}\beta({\mathbf{x}})\big{)}\big{|}}\Big{)}.$
(43)

Using Formula 7.1.13 from Abramowitz and Stegun, (1968), we have for any
$z>0$:

$\Phi^{\text{c}}(z)>\sqrt{\frac{2}{\pi}}\Bigg{(}\frac{e^{-\frac{z^{2}}{2}}}{z+\sqrt{z^{2}+4}}\Bigg{)}.$

Further, using the fact that $z+\sqrt{z^{2}+4}<2(z+1)$ for $z>0$ above, we
get:

$\Phi^{\text{c}}(z)>\frac{1}{\sqrt{2\pi}}\Bigg{(}\frac{e^{-\frac{z^{2}}{2}}}{z+1}\Bigg{)}.$
(44)

Now if $z\leq 2$, $z+1\leq 3$. Using this in eq. 44, we get:

$\Phi^{\text{c}}(z)>\frac{1}{3\sqrt{2\pi}}\exp\Big{(}-\frac{z^{2}}{2}\Big{)}.$
(45)

If $z>2$, $z+1<e^{z}<e^{z^{2}/2}$. Using this in eq. 44, we get:

$\Phi^{\text{c}}(z)>\frac{1}{\sqrt{2\pi}}\exp(-{z^{2}}).$ (46)

Combining eq. 45 and eq. 46, we get the following simpler bound:

$\Phi^{\text{c}}(z)>\frac{1}{3\sqrt{2\pi}}\exp(-{z^{2}}).$ (47)

Using this in eq. 43, we get:

$\mathbb{P}\Big{(}\langle{\mathbf{x}},\widehat{\bm{\theta}}_{0}\rangle\leq
0\Big{)}\geq\frac{1}{3\sqrt{2\pi}}{\exp\Big{(}-{\big{(}1+\sqrt{n}\mu(1-2p)\big{)}^{2}\textup{cot}^{2}\big{(}\beta({\mathbf{x}})\big{)}}\Big{)}}.$
(48)

This finishes the proof of the result for the case of ${\mathrm{y}}=1$. The
result for the other case (i.e., ${\mathrm{y}}=-1$) can be derived similarly
as above; in particular, here we get:

$\mathbb{P}\Big{(}\langle{\mathbf{x}},\widehat{\bm{\theta}}_{0}\rangle>0\Big{)}\geq\frac{1}{3\sqrt{2\pi}}{\exp\Big{(}-{\big{(}1+\sqrt{n}\mu(1-2p)\big{)}^{2}\textup{cot}^{2}\big{(}\beta({\mathbf{x}})\big{)}}\Big{)}}.$
(49)

This finishes the proof. ∎

######  Lemma 1.

For $t\leq\frac{1}{2}$, it holds that:

$e^{t}-1\leq t+t^{2}.$

###### Proof.

Using the Taylor expansion of $e^{t}$, we get:

$\displaystyle e^{t}-1$
$\displaystyle=t+\frac{t^{2}}{2!}+\frac{t^{3}}{3!}+\frac{t^{4}}{4!}\ldots$
(50) $\displaystyle\leq t+\frac{t^{2}}{2}\big{(}1+t+t^{2}+\ldots\big{)}$ (51)
$\displaystyle=t+\frac{t^{2}}{2(1-t)}.$ (52)

Since $t\leq\frac{1}{2}$, $2(1-t)\geq 1$. Using this above gives us the
desired result. ∎

######  Lemma 2.

For $p\leq\frac{1}{2}$, we have:

$\mathbb{E}\Big{[}\big{|}\sum_{k=1}^{n}\delta_{k}\big{|}\mathrm{x}_{k}^{(1)}\big{|}\big{|}\Big{]}\leq\sqrt{n}\sigma+n(1-2p)\mu\sigma.$

###### Proof.

First, note that:

$\mathbb{E}\Big{[}\big{|}\sum_{k=1}^{n}\delta_{k}\big{|}\mathrm{x}_{k}^{(1)}\big{|}\big{|}\Big{]}\leq\sqrt{\mathbb{E}\Bigg{[}\Big{|}\sum_{k=1}^{n}\delta_{k}\big{|}\mathrm{x}_{k}^{(1)}\big{|}\Big{|}^{2}\Bigg{]}}.$
(53)

Now using independence, we have:

$\mathbb{E}\Bigg{[}\Big{|}\sum_{k=1}^{n}\delta_{k}\big{|}\mathrm{x}_{k}^{(1)}\big{|}\Big{|}^{2}\Bigg{]}\leq\sum_{k}\mathbb{E}\Big{[}\big{|}\mathrm{x}_{k}^{(1)}\big{|}^{2}\Big{]}+\sum_{k\neq
l}\mathbb{E}\big{[}\delta_{k}\big{]}\mathbb{E}\big{[}\delta_{l}\big{]}\mathbb{E}\Big{[}\big{|}\mathrm{x}_{k}^{(1)}\big{|}\Big{]}\mathbb{E}\Big{[}\big{|}\mathrm{x}_{l}^{(1)}\big{|}\Big{]}.$
(54)

As per our setting,
$\mathbb{E}\Big{[}\big{|}\mathrm{x}_{k}^{(1)}\big{|}^{2}\Big{]}=\sigma^{2}$,
$\mathbb{E}\Big{[}\big{|}\mathrm{x}_{k}^{(1)}\big{|}\Big{]}=\mu\sigma$ and
$\mathbb{E}\big{[}\delta_{k}\big{]}=1-2p$. Using all of this in eq. 54, we
get:

$\mathbb{E}\Bigg{[}\Big{|}\sum_{k=1}^{n}\delta_{k}\big{|}\mathrm{x}_{k}^{(1)}\big{|}\Big{|}^{2}\Bigg{]}\leq
n\sigma^{2}+n(n-1)(1-2p)^{2}\mu^{2}\sigma^{2}\leq
n\sigma^{2}+n^{2}(1-2p)^{2}\mu^{2}\sigma^{2}.$ (55)

Using this in eq. 53, we get:

$\mathbb{E}\Big{[}\big{|}\sum_{k=1}^{n}\delta_{k}\big{|}\mathrm{x}_{k}^{(1)}\big{|}\big{|}\Big{]}\leq\Big{(}n\sigma^{2}+n^{2}(1-2p)^{2}\mu^{2}\sigma^{2}\Big{)}^{1/2}\leq\sqrt{n}\sigma+n(1-2p)\mu\sigma.$
(56)

This finishes the proof. ∎

##  Appendix C Proof of Theorem 2

###### Proof.

Just like Theorem 1, we can prove the result for
$\bm{\theta}^{\ast}={\mathbf{e}}_{1}$ and
$\mathcal{B}=\\{{\mathbf{e}}_{1},{\mathbf{e}}_{2},\ldots,{\mathbf{e}}_{d}\\}$
without loss of generality. In that case,
${\mathrm{a}}^{(j)}={\mathrm{x}}^{(j)}=\langle{\mathbf{x}},{\mathbf{e}}_{j}\rangle$
for $j\in[d]$, the ground truth label of ${\mathbf{x}}$ is
$\text{sign}({\mathrm{x}}^{(1)})$,
$\big{|}\textup{cos}\big{(}\beta({\mathbf{x}})\big{)}\big{|}=\frac{|{\mathrm{x}}^{(1)}|}{\|{\mathbf{x}}\|}$
and
$\big{|}\textup{cot}\big{(}\beta({\mathbf{x}})\big{)}\big{|}=\frac{|{\mathrm{x}}^{(1)}|}{\sqrt{\sum_{j=2}^{d}({\mathrm{x}}^{(j)})^{2}}}$.
Also note that:

$\text{acc}(\widehat{\bm{\theta}}_{0})=\mathbb{P}_{{\mathbf{x}}\sim\mathcal{D},\mathcal{T}}\Big{(}\textup{sign}\big{(}\langle{\mathbf{x}},\widehat{\bm{\theta}}_{0}\rangle\big{)}=\textup{sign}\big{(}{\mathrm{x}}^{(1)}\big{)}\Big{)}=\mathbb{E}_{{\mathbf{x}}\sim\mathcal{D},\mathcal{T}}\Big{[}\mathbbm{1}\Big{(}\textup{sign}\big{(}\langle{\mathbf{x}},\widehat{\bm{\theta}}_{0}\rangle\big{)}=\textup{sign}\big{(}{\mathrm{x}}^{(1)}\big{)}\Big{)}\Big{]}.$

(a) Lower bound. For the above case, we have:

$\displaystyle\text{acc}(\widehat{\bm{\theta}}_{0})$
$\displaystyle=\mathbb{E}_{{\mathbf{x}}\sim\mathcal{D},\mathcal{T}}\Bigg{[}\mathbbm{1}\Big{(}\textup{sign}\big{(}\langle{\mathbf{x}},\widehat{\bm{\theta}}_{0}\rangle\big{)}=\textup{sign}\big{(}{\mathrm{x}}^{(1)}\big{)}\Big{)}\Bigg{]}$
(57)
$\displaystyle=\mathbb{E}_{{\mathbf{x}}\sim\mathcal{D}}\Bigg{[}\mathbb{P}_{\mathcal{T}}\Big{(}\textup{sign}\big{(}\langle{\mathbf{x}},\widehat{\bm{\theta}}_{0}\rangle\big{)}=\textup{sign}\big{(}{\mathrm{x}}^{(1)}\big{)}\Big{)}\Bigg{]}$
(58)
$\displaystyle\geq\mathbb{E}_{{\mathbf{x}}\sim\mathcal{D}}\Big{[}\alpha({\mathbf{x}})\Big{]}=1-\mathbb{E}_{{\mathbf{x}}\sim\mathcal{D}}\Bigg{[}\exp\Bigg{(}-\frac{n\mu^{2}}{4}(1-2p)^{2}\textup{cos}^{2}\big{(}\beta({\mathbf{x}})\big{)}\Bigg{)}\Bigg{]},$
(59)

where eq. 59 follows from Theorem 1.121212To be explicit, in the series of
equations above, we can go from eq. 58 to eq. 59 because $\mathcal{X}_{L}$ has
zero measure. For brevity, let $t:=\frac{n\mu^{2}}{4}(1-2p)^{2}$. Also, we
will omit the subscript ${\mathbf{x}}\sim\mathcal{D}$ henceforth for
conciseness. Now, for any $\nu\in(0,1)$:

$\mathbb{E}\Big{[}\exp\Big{(}-t\textup{cos}^{2}\big{(}\beta({\mathbf{x}})\big{)}\Big{)}\Big{]}=\underbrace{\mathbb{E}\Big{[}\exp\Big{(}-t\textup{cos}^{2}\big{(}\beta({\mathbf{x}})\big{)}\Big{)}\Big{|}\big{|}\textup{cos}\big{(}\beta({\mathbf{x}})\big{)}\big{|}\leq\nu\Big{]}}_{\leq
1}\mathbb{P}\Big{(}\big{|}\textup{cos}\big{(}\beta({\mathbf{x}})\big{)}\big{|}\leq\nu\Big{)}\\\
+\underbrace{\mathbb{E}\Big{[}\exp\Big{(}-t\textup{cos}^{2}\big{(}\beta({\mathbf{x}})\big{)}\Big{)}\Big{|}\big{|}\textup{cos}\big{(}\beta({\mathbf{x}})\big{)}\big{|}>\nu\Big{]}}_{\leq\exp(-t\nu^{2})}\underbrace{\mathbb{P}\Big{(}\big{|}\textup{cos}\big{(}\beta({\mathbf{x}})\big{)}\big{|}>\nu\Big{)}}_{\leq
1}.$ (60)

Thus,

$\mathbb{E}\Big{[}\exp\Big{(}-t\textup{cos}^{2}\big{(}\beta({\mathbf{x}})\big{)}\Big{)}\Big{]}\leq\mathbb{P}\Big{(}\big{|}\textup{cos}\big{(}\beta({\mathbf{x}})\big{)}\big{|}\leq\nu\Big{)}+\exp(-t\nu^{2}).$
(61)

From Lemma 3, we have for $\nu\leq\frac{\gamma}{\sqrt{\gamma^{2}+{3}(d-1)}}$:

$\displaystyle\mathbb{P}\Big{(}\big{|}\textup{cos}\big{(}\beta({\mathbf{x}})\big{)}\big{|}\leq\nu\Big{)}$
$\displaystyle\leq\exp\Bigg{(}-\frac{9(d-1)}{20}\Bigg{)}.$ (62)

Using this in eq. 61 and plugging in the value of $t$, we get:

$\displaystyle\mathbb{E}\Bigg{[}\exp\Bigg{(}-\frac{n\mu^{2}}{4}(1-2p)^{2}\textup{cos}^{2}\big{(}\beta({\mathbf{x}})\big{)}\Bigg{)}\Bigg{]}$
$\displaystyle\leq\exp\Bigg{(}-\frac{9(d-1)}{20}\Bigg{)}+\exp\Bigg{(}-\frac{n\mu^{2}}{4}(1-2p)^{2}\nu^{2}\Bigg{)},$
(63)

for any $\nu\leq\frac{\gamma}{\sqrt{\gamma^{2}+{3}(d-1)}}$. Since
$\gamma<\frac{1}{2}$, we can choose $\nu=\frac{\gamma}{\sqrt{3d}}$. Plugging
this choice into eq. 63 yields:

$\displaystyle\mathbb{E}\Bigg{[}\exp\Bigg{(}-\frac{n\mu^{2}}{4}(1-2p)^{2}\textup{cos}^{2}\big{(}\beta({\mathbf{x}})\big{)}\Bigg{)}\Bigg{]}$
$\displaystyle\leq\exp\Bigg{(}-\frac{9(d-1)}{20}\Bigg{)}+\exp\Bigg{(}-\frac{n\mu^{2}\gamma^{2}(1-2p)^{2}}{12d}\Bigg{)}.$
(64)

Plugging this into eq. 59 gives us:

$\displaystyle\text{acc}(\widehat{\bm{\theta}}_{0})$ $\displaystyle\geq
1-\exp\Bigg{(}-\frac{9(d-1)}{20}\Bigg{)}-\exp\Bigg{(}-\frac{n\mu^{2}\gamma^{2}(1-2p)^{2}}{12d}\Bigg{)}$
(65)
$\displaystyle=1-\exp\big{(}-\Theta(d)\big{)}-\exp\Bigg{(}-\frac{n{\mu^{2}}\gamma^{2}(1-2p)^{2}}{\Theta(d)}\Bigg{)}.$
(66)

(b) Upper bound. We have:

$\displaystyle\text{acc}(\widehat{\bm{\theta}}_{0})$
$\displaystyle=\mathbb{E}_{{\mathbf{x}}\sim\mathcal{D},\mathcal{T}}\Bigg{[}\mathbbm{1}\Big{(}\textup{sign}\big{(}\langle{\mathbf{x}},\widehat{\bm{\theta}}_{0}\rangle\big{)}=\textup{sign}\big{(}{\mathrm{x}}^{(1)}\big{)}\Big{)}\Bigg{]}$
(67)
$\displaystyle=\mathbb{E}_{{\mathbf{x}}\sim\mathcal{D}}\Bigg{[}\mathbb{P}_{\mathcal{T}}\Big{(}\textup{sign}\big{(}\langle{\mathbf{x}},\widehat{\bm{\theta}}_{0}\rangle\big{)}=\textup{sign}\big{(}{\mathrm{x}}^{(1)}\big{)}\Big{)}\Bigg{]}$
(68)
$\displaystyle\leq\mathbb{E}_{{\mathbf{x}}\sim\mathcal{D}}\Big{[}\widehat{\alpha}({\mathbf{x}})\Big{]}=1-\frac{1}{3\sqrt{2\pi}}\mathbb{E}_{{\mathbf{x}}\sim\mathcal{D}}\Bigg{[}{\exp\Big{(}-{\big{(}1+\sqrt{n}\mu(1-2p)\big{)}^{2}\textup{cot}^{2}\big{(}\beta({\mathbf{x}})\big{)}}\Big{)}}\Bigg{]},$
(69)

where eq. 69 follows from Theorem 1.131313To be explicit, in the series of
equations above, we can go from eq. 68 to eq. 69 because $\mathcal{X}_{L}$ has
zero measure. For brevity, let $t:=(1+\sqrt{n}\mu(1-2p))^{2}$. Also, we will
omit the subscript ${\mathbf{x}}\sim\mathcal{D}$ henceforth for conciseness.
Now, for any $\nu>0$:

$\displaystyle\mathbb{E}\Big{[}\exp\big{(}-t\textup{cot}^{2}\big{(}\beta({\mathbf{x}})\big{)}\big{)}\Big{]}$
$\displaystyle\geq\mathbb{E}\Big{[}\exp\big{(}-t\textup{cot}^{2}\big{(}\beta({\mathbf{x}})\big{)}\big{)}\Big{|}\big{|}\textup{cot}\big{(}\beta({\mathbf{x}})\big{)}\big{|}\leq\nu\Big{]}\mathbb{P}\Big{(}\big{|}\textup{cot}\big{(}\beta({\mathbf{x}})\big{)}\big{|}\leq\nu\Big{)}$
(70)
$\displaystyle\geq\exp\big{(}-{t\nu^{2}}\big{)}\mathbb{P}\Big{(}\big{|}\textup{cot}\big{(}\beta({\mathbf{x}})\big{)}\big{|}\leq\nu\Big{)}.$
(71)

Let us choose $\nu=\frac{2\sqrt{2}\mu}{\sqrt{d-1}}$. Then, using the result of
Lemma 4, we have:

$\displaystyle\mathbb{E}\Big{[}\exp\big{(}-t\textup{cot}^{2}\big{(}\beta({\mathbf{x}})\big{)}\big{)}\Big{]}$
$\displaystyle\geq\frac{1}{2}\Bigg{(}1-\exp\Big{(}-\frac{d-1}{16}\Big{)}\Bigg{)}\exp\Big{(}-\frac{8\mu^{2}t}{d-1}\Big{)}.$
(72)

Using this in eq. 69 after plugging in the value of
$t=(1+\sqrt{n}\mu(1-2p))^{2}\leq 2(1+n\mu^{2}(1-2p)^{2})$, we get:

$\displaystyle\text{acc}(\widehat{\bm{\theta}}_{0})$ $\displaystyle\leq
1-\frac{1}{6\sqrt{2\pi}}\Bigg{(}1-\exp\Big{(}-\frac{d-1}{16}\Big{)}\Bigg{)}\exp\Bigg{(}-\frac{16\mu^{2}(1+n\mu^{2}(1-2p)^{2})}{d-1}\Bigg{)}$
(73) $\displaystyle\leq
1-\Theta(1)\exp\Bigg{(}-\frac{n\mu^{4}(1-2p)^{2}}{\Theta(d)}\Bigg{)}.$ (74)

This completes the proof. ∎

######  Lemma 3.

In the setting of the proof of Theorem 2, we have for any
$\nu\leq\frac{\gamma}{\sqrt{\gamma^{2}+{3}(d-1)}}$:

$\mathbb{P}\Big{(}{\mathbf{x}}:|\textup{cos}(\beta({\mathbf{x}}))|\leq\nu\Big{)}\leq\exp\Bigg{(}-\frac{9(d-1)}{20}\Bigg{)}.$

###### Proof.

We have:

$\displaystyle\mathbb{P}\Big{(}{\mathbf{x}}:|\textup{cos}(\beta({\mathbf{x}}))|\geq\nu\Big{)}$
$\displaystyle=\mathbb{P}\Bigg{(}\frac{\big{(}{\mathrm{x}}^{(1)}\big{)}^{2}}{\big{(}{\mathrm{x}}^{(1)}\big{)}^{2}+\sum_{j=2}^{d}\big{(}{\mathrm{x}}^{(j)}\big{)}^{2}}\geq\nu^{2}\Bigg{)}$
(75)
$\displaystyle=\mathbb{P}\Bigg{(}\sum_{j=2}^{d}\Big{(}\frac{{\mathrm{x}}^{(j)}}{\sigma}\Big{)}^{2}\leq\Big{(}\frac{1-\nu^{2}}{\nu^{2}}\Big{)}\Big{(}\frac{{\mathrm{x}}^{(1)}}{\sigma}\Big{)}^{2}\Bigg{)}.$
(76)

Let ${\mathrm{z}}:=\sum_{j=2}^{d}\big{(}{\mathrm{x}}^{(j)}/\sigma\big{)}^{2}$
and $\overline{\mathrm{x}}^{(1)}:={\mathrm{x}}^{(1)}/\sigma$. Note that
${\mathrm{z}}$ is a chi-squared random variable with $(d-1)$ degrees of
freedom and $\big{|}\overline{\mathrm{x}}^{(1)}\big{|}\geq\gamma$ per our
setting. Thus, continuing from eq. 76, we have:

$\displaystyle\mathbb{P}\Big{(}{\mathbf{x}}:|\textup{cos}(\beta({\mathbf{x}}))|\geq\nu\Big{)}$
$\displaystyle\geq\mathbb{P}\Bigg{(}{\mathrm{z}}<\Big{(}\frac{1-\nu^{2}}{\nu^{2}}\Big{)}\gamma^{2}\Bigg{)}.$
(77)

A simple application of Theorem 1 of Ghosh, (2021) yields:

$\mathbb{P}\big{(}{\mathrm{z}}\geq
3(d-1)\big{)}\leq\exp\Bigg{(}-\frac{(d-1)}{2}(2-\log
3)\Bigg{)}\leq\exp\Bigg{(}-\frac{9(d-1)}{20}\Bigg{)}.$ (78)

Thus, for any $w\geq 3(d-1)$, $\mathbb{P}({\mathrm{z}}<w)\geq
1-\exp\Big{(}-\frac{9(d-1)}{20}\Big{)}$. Using this in eq. 77 yields:

$\mathbb{P}\Big{(}{\mathbf{x}}:|\textup{cos}(\beta({\mathbf{x}}))|\geq\nu\Big{)}\geq
1-\exp\Bigg{(}-\frac{9(d-1)}{20}\Bigg{)},$ (79)

when $\Big{(}\frac{1-\nu^{2}}{\nu^{2}}\Big{)}\gamma^{2}\geq 3(d-1)$ or
$\nu\leq\frac{\gamma}{\sqrt{\gamma^{2}+{3}(d-1)}}$. So:

$\mathbb{P}\Big{(}{\mathbf{x}}:|\textup{cos}(\beta({\mathbf{x}}))|\leq\nu\Big{)}\leq\exp\Bigg{(}-\frac{9(d-1)}{20}\Bigg{)},$
(80)

for $\nu\leq\frac{\gamma}{\sqrt{\gamma^{2}+{3}(d-1)}}$. This finishes the
proof. ∎

######  Lemma 4.

In the setting of the proof of Theorem 2, we have for any
$\nu\geq\frac{2\sqrt{2}\mu}{\sqrt{d-1}}$:

$\mathbb{P}\Big{(}{\mathbf{x}}:|\textup{cot}(\beta({\mathbf{x}}))|\leq\nu\Big{)}\geq\frac{1}{2}\Bigg{(}1-\exp\Big{(}-\frac{d-1}{16}\Big{)}\Bigg{)}.$

###### Proof.

We have:

$\displaystyle\mathbb{P}\Big{(}{\mathbf{x}}:|\textup{cot}(\beta({\mathbf{x}}))|\leq\nu\Big{)}$
$\displaystyle=\mathbb{P}\Bigg{(}\frac{\big{(}{\mathrm{x}}^{(1)}\big{)}^{2}}{\sum_{j=2}^{d}\big{(}{\mathrm{x}}^{(j)}\big{)}^{2}}\leq\nu^{2}\Bigg{)}$
(81)
$\displaystyle=\mathbb{P}\Bigg{(}\Big{(}\frac{{\mathrm{x}}^{(1)}}{\sigma}\Big{)}^{2}\leq\nu^{2}\sum_{j=2}^{d}\Big{(}\frac{{\mathrm{x}}^{(j)}}{\sigma}\Big{)}^{2}\Bigg{)}.$
(82)

Let ${\mathrm{z}}:=\sum_{j=2}^{d}\big{(}{\mathrm{x}}^{(j)}/\sigma\big{)}^{2}$
and $\overline{\mathrm{x}}^{(1)}:={\mathrm{x}}^{(1)}/\sigma$. Note that
${\mathrm{z}}$ is a chi-squared random variable with $(d-1)$ degrees of
freedom. Thus, continuing from eq. 82, we have:

$\displaystyle\mathbb{P}\Big{(}{\mathbf{x}}:|\textup{cot}(\beta({\mathbf{x}}))|\leq\nu\Big{)}$
$\displaystyle\geq\mathbb{P}\Big{(}\big{(}\overline{\mathrm{x}}^{(1)}\big{)}^{2}\leq\nu^{2}{\mathrm{z}}\Big{)}$
(83)
$\displaystyle\geq\mathbb{P}\Bigg{(}\big{(}\overline{\mathrm{x}}^{(1)}\big{)}^{2}\leq\nu^{2}{\mathrm{z}}\text{
}\big{|}\text{
}{\mathrm{z}}>\frac{d-1}{2}\Bigg{)}\mathbb{P}\Bigg{(}{\mathrm{z}}>\frac{d-1}{2}\Bigg{)}$
(84)
$\displaystyle\geq\mathbb{P}\Bigg{(}\big{(}\overline{\mathrm{x}}^{(1)}\big{)}^{2}\leq\nu^{2}\Big{(}\frac{d-1}{2}\Big{)}\Bigg{)}\mathbb{P}\Bigg{(}{\mathrm{z}}>\frac{d-1}{2}\Bigg{)}.$
(85)

From Theorem 2 of Ghosh, (2021), we have that:

$\mathbb{P}\Bigg{(}{\mathrm{z}}>\frac{d-1}{2}\Bigg{)}\geq
1-\exp\Bigg{(}-\frac{d-1}{16}\Bigg{)}.$ (86)

Plugging this into eq. 85, we get:

$\displaystyle\mathbb{P}\Big{(}{\mathbf{x}}:|\textup{cot}(\beta({\mathbf{x}}))|\leq\nu\Big{)}$
$\displaystyle\geq\mathbb{P}\Bigg{(}\big{(}\overline{\mathrm{x}}^{(1)}\big{)}^{2}\leq\nu^{2}\Big{(}\frac{d-1}{2}\Big{)}\Bigg{)}\Bigg{(}1-\exp\Big{(}-\frac{d-1}{16}\Big{)}\Bigg{)}$
(87)
$\displaystyle=\mathbb{P}\Bigg{(}\big{|}\overline{\mathrm{x}}^{(1)}\big{|}\leq\nu\sqrt{\frac{d-1}{2}}\Bigg{)}\Bigg{(}1-\exp\Big{(}-\frac{d-1}{16}\Big{)}\Bigg{)}.$
(88)

As per our setting, we have that
$\mathbb{E}[\big{|}\overline{\mathrm{x}}^{(1)}\big{|}]=\mu$. Note that for
$\nu\geq\frac{2\sqrt{2}\mu}{\sqrt{d-1}}$, we have that:

$\mathbb{P}\Bigg{(}\big{|}\overline{\mathrm{x}}^{(1)}\big{|}\leq\nu\sqrt{\frac{d-1}{2}}\Bigg{)}\geq\mathbb{P}\Big{(}\big{|}\overline{\mathrm{x}}^{(1)}\big{|}\leq
2\mu\Big{)}\geq\frac{1}{2},$ (89)

where the last step above follows from Markov’s inequality. Plugging in eq. 89
into eq. 88 gives us the desired result. ∎

##  Appendix D Proof of Theorem 3

###### Proof.

We will consider the case of $\widehat{\bm{\theta}}\in S^{d-1}$; the norm of
$\widehat{\bm{\theta}}$ does not affect the sign of
$\langle{\mathbf{x}},\bm{\theta}^{\ast}\rangle$, so we can assume
$\|\widehat{\bm{\theta}}\|=1$ without loss of generality. In particular, the
prediction of a classifier $\widehat{\bm{\theta}}\notin S^{d-1}$ is the same
as the prediction of its projection onto $S^{d-1}$ (i.e.,
${\widehat{\bm{\theta}}}/{\|\widehat{\bm{\theta}}\|}$).

We first follow a standard argument to “reduce” the classification problem to
a multi-way hypothesis testing problem. Let $\rho\in(0,1)$ be an arbitrary but
fixed value which we can choose. We define a $\rho$-packing of $S^{d-1}$ as a
set $\Theta=\\{\bm{\theta}_{1},\dotsc,\bm{\theta}_{M}\\}\subset S^{d-1}$ such
that $\langle\bm{\theta}_{l},\bm{\theta}_{k}\rangle\leq\rho$ for $l\neq k$.
Also define the $\rho$-packing number of $S^{d-1}$ as

$\displaystyle M(\rho,S^{d-1}):=\sup\\{M\in\mathbb{N}:\text{there exists a
$\rho$-packing $\Theta$ of $S^{d-1}$ with size $M$}\\}\,.$ (90)

For convenience, we define the misclassification error of a classifier
$\widehat{\bm{\theta}}\in S^{d-1}$ as
$\textup{err}(\widehat{\bm{\theta}};\bm{\theta}^{*})=1-\textup{acc}(\widehat{\bm{\theta}};\bm{\theta}^{*})$.
By our assumption,

$\displaystyle\delta\geq\sup_{\bm{\theta}^{\ast}\in
S^{d-1}}\textup{err}(\widehat{\bm{\theta}};\bm{\theta}^{*})\geq\sup_{\bm{\theta}^{\ast}\in\Theta}\textup{err}(\widehat{\bm{\theta}};\bm{\theta}^{*})\,.$
(91)

In order to further lower bound the right hand side, we let $I$ be a random
variable uniformly distributed on the hypothesis set $\\{1,2,\dotsc,M\\}$ and
consider the case of $\bm{\theta}^{\ast}=\bm{\theta}_{I}$. We also define
$\widehat{I}$ as the index of the element in $\Theta$ with maximum inner
product with $\widehat{\bm{\theta}}$ (it does not matter how we break ties).
We then have

$\displaystyle\sup_{\bm{\theta}^{\ast}\in\Theta}\textup{err}(\widehat{\bm{\theta}};\bm{\theta}^{*})$
$\displaystyle\geq\max_{i\in[M]}\mathbb{P}\left(\mathrm{sign}(\langle\mathbf{x},\bm{\theta}_{I}\rangle)\neq\mathrm{sign}(\langle\mathbf{x},\widehat{\bm{\theta}}\rangle)\Big{|}I=i\right)$
$\displaystyle\geq\frac{1}{M}\sum_{i=1}^{M}\mathbb{P}\left(\mathrm{sign}(\langle\mathbf{x},\bm{\theta}_{I}\rangle)\neq\mathrm{sign}(\langle\mathbf{x},\widehat{\bm{\theta}}\rangle)\Big{|}I=i\right)$
$\displaystyle\geq\Phi\Bigg{(}-\sqrt{\frac{1+\rho}{1-\rho}}\mu\Bigg{)}\frac{1}{M}\sum_{i=1}^{M}\mathbb{P}(\widehat{I}\neq
i|I=i)$ (92)
$\displaystyle=\Phi\Bigg{(}-\sqrt{\frac{1+\rho}{1-\rho}}\mu\Bigg{)}\mathbb{P}(\widehat{I}\neq
I)\,,$ (93)

with $\Phi$ denoting the CDF of a standard normal variable. Equation 92 above
follows from the lemma below.

######  Lemma 5.

For any $i\in[M]$, we have

$\mathbb{P}\left(\mathrm{sign}(\langle\mathbf{x},\bm{\theta}_{I}\rangle)\neq\mathrm{sign}(\langle\mathbf{x},\widehat{\bm{\theta}}\rangle)\Big{|}I=i\right)\geq\Phi\Bigg{(}-\sqrt{\frac{1+\rho}{1-\rho}}\mu\Bigg{)}\;\mathbb{P}(\widehat{I}\neq
i|I=i)\,.$

Combining (91) and (93), we obtain that

$\delta_{0}:=\frac{\delta}{\Phi\Big{(}-\sqrt{\frac{1+\rho}{1-\rho}}\mu\Big{)}}\geq\mathbb{P}(\widehat{I}\neq
I)\,.$ (94)

Next recall the set
$\mathcal{T}:=\\{({\mathbf{x}}_{j},\widehat{\mathrm{y}}_{j})\\}_{j\in[n]}$,
and let
$\mathbf{X}=[{\mathbf{x}}_{1}^{T},\dotsc,{\mathbf{x}}_{n}^{T}]^{T}\in\mathbb{R}^{n\times
d}$ and
$\widehat{\mathbf{y}}=[\widehat{\mathrm{y}}_{1},\dotsc,\widehat{\mathrm{y}}_{n}]^{T}$.
By an application of Fano’s inequality, with conditioning on $\mathbf{X}$ (see
e.g. (Scarlett and Cevher,, 2019, Section 2.3)) we have

$\displaystyle\mathcal{I}(I;\widehat{I}|\mathbf{X})\geq\left(1-\delta_{0}\right)\log(M(\rho,S^{d-1}))-\log
2\,,$ (95)

where $\mathcal{I}(I;\widehat{I}|\mathbf{X})$ represents the conditional
mutual information between $I$ and $\widehat{I}$. Using the fact that
$I\to\widehat{\mathbf{y}}\to\widehat{I}$ forms a Markov chain conditioned on
$\mathbf{X}$, and by an application of the data processing inequality we have:

$\mathcal{I}(I;\widehat{I}|\mathbf{X})\leq\mathcal{I}(I;\widehat{\mathbf{y}}|\mathbf{X})$
(96)

We will now upper bound $\mathcal{I}(I;\widehat{\mathbf{y}}|\mathbf{X})$. Let
$\mathrm{w}_{j}:=\frac{1}{2}\big{(}\mathrm{sign}(\langle\mathbf{x}_{j},\bm{\theta}_{I}\rangle)+1\big{)}$
be the 0-1 version of the actual label of $\mathbf{x}_{j}$, viz.,
$\mathrm{sign}(\langle\mathbf{x}_{j},\bm{\theta}_{I}\rangle)$. As per our
setting, we have $\widehat{\mathrm{y}}_{j}=2\big{(}\mathrm{w}_{j}\oplus
z_{j}\big{)}-1$ where $z_{j}\sim\text{Bernoulli}(p)$ and $\oplus$ denotes
modulo-2 addition. Since the noise variables $z_{j}$ are independent and
$\widehat{\mathrm{y}}_{j}$ depends on $(I,\mathbf{X})$ only through
$\mathrm{w}_{j}=\frac{1}{2}\big{(}\mathrm{sign}(\langle\mathbf{x}_{j},\bm{\theta}_{I}\rangle)+1\big{)}$,
by using the tensorization property of the mutual information (see e.g.
(Scarlett and Cevher,, 2019, Lemma 2, part (iii))), we have

$\displaystyle\mathcal{I}(I;\mathbf{y}|\mathbf{X})\leq\sum_{j=1}^{n}\mathcal{I}\big{(}\mathrm{w}_{j};\widehat{\mathrm{y}}_{j}\big{)}\leq
n(\log 2-H_{2}(p))\,,$ (97)

where the second inequality follows since $\widehat{\mathrm{y}}_{j}$ is
generated by passing $\mathrm{w}_{j}$ through a binary symmetric channel,
which has capacity $\log 2-H_{2}(p)$ with $H_{2}(p):=-p\log p-(1-p)\log(1-p)$
denoting the binary entropy function.

We next use the lemma below to further upper bound the right-hand side of
(97).

######  Lemma 6.

For a discrete probability distribution, consider the entropy function given
by

$H(p_{1},\dotsc,p_{k})=\sum_{i=1}^{k}p_{k}\log(1/p_{k})\,.$

We have the following bound:

$H(p_{1},\dotsc,p_{k})\geq\log k-k\sum_{i=1}^{k}(p_{i}-1/k)^{2}\,.$

Using Lemma 6 with $k=2$ we obtain $\log 2-H_{2}(p)\leq
4(p-1/2)^{2}=(1-2p)^{2}$, which along with (97), (96) and (95) gives

$\displaystyle\frac{n(1-2p)^{2}+\log
2}{1-\delta_{0}}\geq\log(M(\rho,S^{d-1}))\,.$ (98)

In our next lemma, we lower bound $M(\rho,S^{d-1})$.

######  Lemma 7.

Recall the definition of $\rho$-packing number of $S^{d-1}$ given by (90). We
have the following bound:

$M(\rho,S^{d-1})\geq\exp\Big{(}\frac{d\rho^{2}}{2}\Big{)}\,.$

Using Lemma 7 along with (98), we obtain the following lower bound on the
sample complexity:

$n\geq\frac{\frac{\rho^{2}}{2}(1-\delta_{0})d-\log 2}{(1-2p)^{2}},\text{ with
}\delta_{0}=\frac{\delta}{\Phi\Big{(}-\sqrt{\frac{1+\rho}{1-\rho}}\mu\Big{)}}.$

Let us pick $\rho=\frac{(4/5)^{2}-\mu^{2}}{(4/5)^{2}+\mu^{2}}$; it can be
shown that $\rho>\frac{2}{5}$, because $\mu\leq\frac{1}{2}$ as per our
setting. In that case, using the fact that $\Phi(-\frac{4}{5})>\frac{1}{5}$,
we have that $\delta_{0}<5\delta$. Using all of this gives us the desired
result for $\delta<\frac{1}{5}$.

∎

We now prove Lemmas 5, 6 and 7.

Proof of Lemma 5. Let us consider the event $\widehat{I}\neq i$, given that
$I=i$. We note that if $\widehat{I}\neq I$, then
$\langle\widehat{\bm{\theta}},\bm{\theta}_{I}\rangle\leq\sqrt{\frac{1+\rho}{2}}$
or equivalently, the angle between $\widehat{\bm{\theta}}$ and
$\bm{\theta}_{I}$ is $\geq b:=\cos^{-1}\Big{(}\sqrt{\frac{1+\rho}{2}}\Big{)}$.
Otherwise, by definition of $\widehat{I}$ we have
$\langle\widehat{\bm{\theta}},\bm{\theta}_{\widehat{I}}\rangle\geq\langle\widehat{\bm{\theta}},\bm{\theta}_{I}\rangle>\sqrt{\frac{1+\rho}{2}}$,
and therefore the angle between $\bm{\theta}_{\widehat{I}}$ and
$\bm{\theta}_{I}$ is $<2b$. Noting that $\cos(2b)=2\cos^{2}(b)-1=\rho$, we
would then have
$\langle\bm{\theta}_{\widehat{I}},\bm{\theta}_{I}\rangle>\rho$, which is a
contradiction since $\Theta$ forms a $\rho$-packing.

Next, under our data model and conditioned on the value of $I$,
$\mathbb{E}\big{[}|\langle\mathbf{x},\bm{\theta}_{I}\rangle|\big{]}=\mu$ and
on the space orthogonal to $\bm{\theta}_{I}$, $\mathbf{x}$ follows
$\mathcal{N}(0,\sigma^{2}\mathbf{I}_{d-1})$ distribution. By rotating the
basis and without loss of generality in lower bounding
$\mathbb{P}\left(\mathrm{sign}(\langle\mathbf{x},\bm{\theta}_{I}\rangle)\neq\mathrm{sign}(\langle\mathbf{x},\widehat{\bm{\theta}}\rangle)\Big{|}I=i\right)$,
we can assume $\bm{\theta}_{I}=\bm{\theta}_{i}=\mathbf{e}_{1}$ and
$\widehat{\bm{\theta}}$ is an arbitrary vector in $S^{d-1}$ such that
$\theta:=\langle\widehat{\bm{\theta}},\bm{e}_{1}\rangle\leq\sqrt{\frac{1+\rho}{2}}$.
We proceed by writing

$\mathbb{P}\left(\mathrm{sign}(\langle\mathbf{x},\bm{\theta}_{I}\rangle)\neq\mathrm{sign}(\langle\mathbf{x},\widehat{\bm{\theta}}\rangle)\Big{|}I=i\right)=\mathbb{P}\left(\mathrm{sign}({\mathrm{x}}^{(1)})\Big{(}{\mathrm{x}}^{(1)}\theta+\langle\mathbf{x}^{(-1)},\widehat{\bm{\theta}}^{(-1)}\rangle\Big{)}\leq
0\right)\,,$

where for a vector ${\mathbf{v}}\in\mathbb{R}^{d}$, we use the notation
${\mathbf{v}}^{(-1)}\in\mathbb{R}^{d-1}$ to refer to the vector obtained by
dropping its first coordinate. Note that $\mathbf{x}$ is a test data point,
independent of the training data $\mathcal{T}$ and so it is independent of
$\bm{\widehat{\theta}}$. Therefore, we have
$\mathrm{sign}({\mathrm{x}}^{(1)})\langle\mathbf{x}^{(-1)},\widehat{\bm{\theta}}^{(-1)}\rangle\sim\mathcal{N}(0,\sigma^{2}\|\widehat{\bm{\theta}}^{(-1)}\|^{2})$.
By invoking the condition $\|\widehat{\bm{\theta}}\|=1$, this can be written
as
$\mathrm{sign}({\mathrm{x}}^{(1)})\langle\mathbf{x}^{(-1)},\widehat{\bm{\theta}}^{(-1)}\rangle=\sqrt{1-\theta^{2}}\,Z$,
where $Z$ is a standard normal variable. Hence, we have:

$\displaystyle\mathbb{P}\left(\mathrm{sign}({\mathrm{x}}^{(1)})\Big{(}{\mathrm{x}}^{(1)}\theta+\langle\mathbf{x}^{(-1)},\widehat{\bm{\theta}}^{(-1)}\rangle\Big{)}\leq
0\right)$
$\displaystyle=\mathbb{P}\left(|{\mathrm{x}}^{(1)}|\theta+\sqrt{1-\theta^{2}}\,Z\leq
0\right)$
$\displaystyle=\mathbb{P}\left(Z\leq-\frac{|{\mathrm{x}}^{(1)}|\theta}{\sqrt{1-\theta^{2}}}\right)$
$\displaystyle=1-\mathbb{E}\Bigg{[}\Phi\Big{(}\frac{\theta}{\sqrt{1-\theta^{2}}}|{\mathrm{x}}^{(1)}|\Big{)}\Bigg{]}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}1-\mathbb{E}\Bigg{[}\Phi\Bigg{(}\sqrt{\frac{1+\rho}{1-\rho}}|{\mathrm{x}}^{(1)}|\Bigg{)}\Bigg{]}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\geq}}1-\Phi\Bigg{(}\sqrt{\frac{1+\rho}{1-\rho}}\mathbb{E}\big{[}|{\mathrm{x}}^{(1)}|\big{]}\Bigg{)}$
$\displaystyle=1-\Phi\Bigg{(}\sqrt{\frac{1+\rho}{1-\rho}}\mu\Bigg{)}$
$\displaystyle=\Phi\Bigg{(}-\sqrt{\frac{1+\rho}{1-\rho}}\mu\Bigg{)}\,,$

where $(a)$ follows from the fact that $\theta\leq\sqrt{\frac{1+\rho}{2}}$ and
$(b)$ holds due to Jensen’s inequality and concavity of $\Phi(.)$ on the
positive values. Combining the above bound with the event $\widehat{I}\neq i$
given that $I=i$ gives us the desired result.

Proof of Lemma 6. Define $q_{i}=p_{i}-1/k$. Note that $q_{i}$ can be negative,
and we have $\sum_{i=1}^{k}q_{i}=0$. We write

$\displaystyle H(p_{1},\dotsc,p_{k})$ $\displaystyle=-\sum_{i=1}^{k}p_{i}\log
p_{i}$ $\displaystyle=-\sum_{i=1}^{k}(1/k+q_{i})\log(1/k+q_{i})$
$\displaystyle=-\sum_{i=1}^{k}(1/k+q_{i})[\log(1/k)+\log(1+kq_{i})]$
$\displaystyle\geq\log k-\sum_{i=1}^{k}(1/k+q_{i})kq_{i}$ (99)
$\displaystyle=\log k-k\sum_{i=1}^{k}q_{i}^{2}$ $\displaystyle=\log
k-k\sum_{i=1}^{k}(p_{i}-1/k)^{2}\,.$

Note that in eq. 99 we used the fact that $1+kq_{i}\geq 0$ and $\log x\leq
x-1$ for all $x\geq 0$.

This completes the proof of the lemma.

Proof of Lemma 7. Define a $\rho$-cover of $S^{d-1}$ as a set of
$\mathcal{V}:=\\{\mathbf{v}_{1},\dotsc,\mathbf{v}_{N}\\}$ such that for any
$\bm{\theta}\in S^{d-1}$, there exists some $\mathbf{v}_{i}$ such that
$\langle\bm{\theta},\mathbf{v}_{i}\rangle\geq\rho$. The $\rho$-covering number
of $S^{d-1}$ is

$N(\rho,S^{d-1}):=\inf\\{N\in\mathbb{N}:\text{there exists a $\rho$-cover
$\mathcal{V}$ of $S^{d-1}$ with size $N$}\\}\,.$

By a simple argument we have $M(\rho,S^{d-1})\geq N(\rho,S^{d-1})$.
Concretely, we construct a $\rho$-packing greedily by adding an element at
each step which has inner product at most $\rho$ with all the previously
selected elements, until it is no longer possible. This means that any point
on $S^{d-1}$ has inner product larger than $\rho$ by some of the elements in
the constructed set (otherwise it contradicts its maximality). Hence, we have
a set that is both a $\rho$-cover and a $\rho$-packing of $S^{d-1}$, and by
definition it results in $M(\rho,S^{d-1})\geq N(\rho,S^{d-1})$.

We next lower bound $N(\rho,S^{d-1})$ via a volumetric argument. Let
$\mathcal{V}:=\\{\mathbf{v}_{1},\dotsc,\mathbf{v}_{N}\\}$ be a $\rho$-cover of
$S^{d-1}$. For each element $\mathbf{v}_{i}\in\mathcal{V}$ we consider the
cone around it with apex angle $\textup{cos}^{-1}(\rho)$. Its intersection
with $S^{d-1}$ defines a spherical cap which we denote by
$\mathcal{C}(\mathbf{v}_{i},\rho)$. Since $\mathcal{V}$ forms a $\rho$-cover
of $S^{d-1}$, we have

$\textup{Vol}(S^{d-1})\leq\textup{Vol}(\cup_{i=1}^{N}\mathcal{C}(\mathbf{v}_{i},\rho))\leq\sum_{i=1}^{N}\textup{Vol}(\mathcal{C}(\mathbf{v}_{i},\rho))\,.$

We next use Lemma 2.2 from Ball et al., (1997) by which we have
$\frac{\mathcal{C}(\mathbf{v}_{i},\rho)}{\textup{Vol}(S^{d-1})}\leq
e^{-d\rho^{2}/2}$. Using this above, we get

$1\leq Ne^{-d\rho^{2}/2}\,$

for any $\rho$-cover $\mathcal{V}$. Thus, we have
$N(\rho,S^{d-1})\geq\exp(\frac{d\rho^{2}}{2})$, which completes the proof of
the lemma.

##  Appendix E Proof of Theorem 4

###### Proof.

Recall the problem setting at the beginning of Section 4. Without loss of
generality, we can prove the result for $\bm{\theta}^{\ast}={\mathbf{e}}_{1}$
and
$\mathcal{B}=\\{{\mathbf{e}}_{1},{\mathbf{e}}_{2},\ldots,{\mathbf{e}}_{d}\\}$
(just like the proof of Theorem 1). In that case,
${\mathrm{a}}^{(j)}={\mathrm{x}}^{(j)}=\langle{\mathbf{x}},{\mathbf{e}}_{j}\rangle$
for $j\in[d]$.

Let ${\mathrm{y}}=\text{sign}({\mathrm{x}}^{(1)})$ be the ground truth label
of ${\mathbf{x}}$. Note that proving Theorem 4 is equivalent to proving the
following statement with
$p_{2}=\exp\Big{(}-\frac{9(d-1)}{40}\Big{)}+\exp\Big{(}-\frac{n\mu^{2}\gamma^{2}}{12d}(1-2p)^{2}\Big{)}$.
For a sample ${\mathbf{x}}\notin\mathcal{X}_{L}\cup\mathcal{X}_{U}$ such that
$|\textup{cos}\big{(}\beta({\mathbf{x}})\big{)}|\geq\frac{{16p_{2}}}{\mu}$,
the following holds with a probability of at least
$1-\exp\Big{(}-\frac{n\mu^{2}}{4}(1-2p_{2})\textup{cos}^{2}\big{(}\beta({\mathbf{x}})\big{)}\Big{)}$:

$\begin{cases}\langle{\mathbf{x}},\widehat{\bm{\theta}}_{1}\rangle\geq 0\text{
when }{\mathrm{y}}=1\text{ i.e., }{\mathrm{x}}^{(1)}\geq 0\\\
\langle{\mathbf{x}},\widehat{\bm{\theta}}_{1}\rangle<0\text{ when
}{\mathrm{y}}=-1\text{ i.e., }{\mathrm{x}}^{(1)}<0.\end{cases}$ (100)

Also note that
$\big{|}\textup{cos}\big{(}\beta({\mathbf{x}})\big{)}\big{|}=\frac{|{\mathrm{x}}^{(1)}|}{\|{\mathbf{x}}\|}$
in our choice of basis for the proof.

Just like the proof of Theorem 1, we will prove the above for the case of
${\mathrm{y}}=1$ or equivalently $\mathrm{x}^{(1)}\geq 0$, and the result for
the other case (i.e., ${\mathrm{y}}=-1$ or equivalently $\mathrm{x}^{(1)}<0$)
can be derived similarly.

Recall that:

$\widehat{\bm{\theta}}_{1}:=\frac{1}{\sigma^{2}}\Bigg{(}\frac{1}{n}\sum_{j=1}^{n}\widetilde{\mathrm{y}}_{j}^{\prime}{\mathbf{x}}_{j}^{\prime}\Bigg{)}.$
(101)

Note that:

$\widetilde{\mathrm{y}}_{j}^{\prime}=\begin{cases}\mathrm{y}_{j}^{\prime}\text{
w.p. }\geq\alpha({\mathbf{x}}_{j}^{\prime})\\\ -\mathrm{y}_{j}^{\prime}\text{
w.p. }\leq 1-\alpha({\mathbf{x}}_{j}^{\prime}),\end{cases}$ (102)

where
$\alpha({\mathbf{x}})=1-\exp\Big{(}-\frac{n\mu^{2}}{4}(1-2p)^{2}\textup{cos}^{2}\big{(}\beta({\mathbf{x}})\big{)}\Big{)}$
is as defined in Theorem 1.

We have:

$\langle{\mathbf{x}},\widehat{\bm{\theta}}_{1}\rangle=\frac{1}{\sigma^{2}}\Bigg{\\{}\frac{1}{n}\sum_{k=1}^{n}\widetilde{\mathrm{y}}_{k}^{\prime}\langle{\mathbf{x}}_{k}^{\prime},{\mathbf{x}}\rangle\Bigg{\\}}.$
(103)

Since $\frac{1}{n\sigma^{2}}$ is a constant independent of $\mathcal{T}$ and
$\mathcal{T}_{2}$, we will analyze

$\varepsilon^{\prime}=\sum_{k=1}^{n}\widetilde{\mathrm{y}}_{k}^{\prime}\langle{\mathbf{x}}_{k}^{\prime},{\mathbf{x}}\rangle.$
(104)

Using the Chernoff bound, we have for any $r<0$:

$\displaystyle\mathbb{P}\big{(}\varepsilon^{\prime}\leq 0\big{)}$
$\displaystyle=\mathbb{P}\big{(}\exp\big{(}r\varepsilon^{\prime}\big{)}\geq
1\big{)}\leq\mathbb{E}\Big{[}\exp\big{(}r\varepsilon^{\prime}\big{)}\Big{]}.$
(105)

For $k\in[n]$, let
$\varepsilon_{k}^{\prime}:=\widetilde{\mathrm{y}}_{k}^{\prime}\langle{\mathbf{x}}_{k}^{\prime},{\mathbf{x}}\rangle$;
thus, $\varepsilon^{\prime}=\sum_{k\in[n]}\varepsilon_{k}^{\prime}$. For any
$r\in\mathbb{R}$, we have:

$\displaystyle\mathbb{E}\Big{[}\exp\big{(}r\varepsilon^{\prime}\big{)}\Big{]}=\mathbb{E}\Big{[}\exp\big{(}r\sum_{k\in[n]}\varepsilon_{k}^{\prime}\big{)}\Big{]}=\mathbb{E}\Big{[}\prod_{k\in[n]}\exp\big{(}r\varepsilon_{k}^{\prime}\big{)}\Big{]}=\Big{(}\mathbb{E}\Big{[}\exp\big{(}r\varepsilon_{1}^{\prime}\big{)}\Big{]}\Big{)}^{n},$
(106)

where the last step follows because of the i.i.d. nature of the data. Now:

$\displaystyle\mathbb{E}\Big{[}\exp\big{(}r\varepsilon_{1}^{\prime}\big{)}\Big{]}$
$\displaystyle=\mathbb{E}\Big{[}\exp\big{(}r\widetilde{\mathrm{y}}_{1}^{\prime}\langle{\mathbf{x}}_{1}^{\prime},{\mathbf{x}}\rangle\big{)}\Big{]}.$
(107)

Taking expectation w.r.t. the randomness in
$\widetilde{\mathrm{y}}_{1}^{\prime}$ first, we get:

$\mathbb{E}\Big{[}\exp\big{(}r\widetilde{\mathrm{y}}_{1}^{\prime}\langle{\mathbf{x}}_{1}^{\prime},{\mathbf{x}}\rangle\big{)}\Big{]}=\mathbb{E}\Bigg{[}\mathbb{E}\Big{[}\exp\big{(}r\widetilde{\mathrm{y}}_{1}^{\prime}\langle{\mathbf{x}}_{1}^{\prime},{\mathbf{x}}\rangle\big{)}\big{|}\widetilde{\mathrm{y}}_{1}^{\prime}={\mathrm{y}}_{1}^{\prime}\Big{]}\underbrace{\mathbb{P}\Big{(}\widetilde{\mathrm{y}}_{1}^{\prime}={\mathrm{y}}_{1}^{\prime}\Big{)}}_{=1-\mathbb{P}\big{(}\widetilde{\mathrm{y}}_{1}^{\prime}=-{\mathrm{y}}_{1}^{\prime}\big{)}}\\\
+\mathbb{E}\Big{[}\exp\big{(}r\widetilde{\mathrm{y}}_{1}^{\prime}\langle{\mathbf{x}}_{1}^{\prime},{\mathbf{x}}\rangle\big{)}\big{|}\widetilde{\mathrm{y}}_{1}^{\prime}=-{\mathrm{y}}_{1}^{\prime}\Big{]}\mathbb{P}\Big{(}\widetilde{\mathrm{y}}_{1}^{\prime}=-{\mathrm{y}}_{1}^{\prime}\Big{)}\Bigg{]}.$
(108)
$\mathbb{E}\Big{[}\exp\big{(}r\widetilde{\mathrm{y}}_{1}^{\prime}\langle{\mathbf{x}}_{1}^{\prime},{\mathbf{x}}\rangle\big{)}\Big{]}=\mathbb{E}\Big{[}\exp\big{(}r{\mathrm{y}}_{1}^{\prime}\langle{\mathbf{x}}_{1}^{\prime},{\mathbf{x}}\rangle\big{)}\Big{]}+\underbrace{\mathbb{E}\Bigg{[}\Big{(}\exp\big{(}-r{\mathrm{y}}_{1}^{\prime}\langle{\mathbf{x}}_{1}^{\prime},{\mathbf{x}}\rangle\big{)}-\exp\big{(}r{\mathrm{y}}_{1}^{\prime}\langle{\mathbf{x}}_{1}^{\prime},{\mathbf{x}}\rangle\big{)}\Big{)}\mathbb{P}\Big{(}\widetilde{\mathrm{y}}_{1}^{\prime}=-{\mathrm{y}}_{1}^{\prime}\Big{)}\Bigg{]}}_{:=\text{(I)}}.$
(109)

We already evaluated
$\mathbb{E}\Big{[}\exp\big{(}r{\mathrm{y}}_{1}^{\prime}\langle{\mathbf{x}}_{1}^{\prime},{\mathbf{x}}\rangle\big{)}\Big{]}$
in the proof of Theorem 1; see eq. 20. It was:

$\mathbb{E}\Big{[}\exp\big{(}r{\mathrm{y}}_{1}^{\prime}\langle{\mathbf{x}}_{1}^{\prime},{\mathbf{x}}\rangle\big{)}\Big{]}\leq\exp\big{(}\mu\sigma
r{\mathrm{x}}^{(1)}\big{)}\exp\Bigg{(}\frac{(\sigma
r\|{\mathbf{x}}\|)^{2}}{2}\Bigg{)}.$ (110)

Next, we need to evaluate
$\text{(I)}:=\mathbb{E}\Big{[}\Big{(}\exp\big{(}-r{\mathrm{y}}_{1}^{\prime}\langle{\mathbf{x}}_{1}^{\prime},{\mathbf{x}}\rangle\big{)}-\exp\big{(}r{\mathrm{y}}_{1}^{\prime}\langle{\mathbf{x}}_{1}^{\prime},{\mathbf{x}}\rangle\big{)}\Big{)}\mathbb{P}\big{(}\widetilde{\mathrm{y}}_{1}^{\prime}=-{\mathrm{y}}_{1}^{\prime}\big{)}\Big{]}$.
However, evaluating (I) exactly seems difficult as both
$\big{(}\exp\big{(}-r{\mathrm{y}}_{1}^{\prime}\langle{\mathbf{x}}_{1}^{\prime},{\mathbf{x}}\rangle\big{)}-\exp\big{(}r{\mathrm{y}}_{1}^{\prime}\langle{\mathbf{x}}_{1}^{\prime},{\mathbf{x}}\rangle\big{)}\big{)}$
and
$\mathbb{P}\big{(}\widetilde{\mathrm{y}}_{1}^{\prime}=-{\mathrm{y}}_{1}^{\prime}\big{)}$
depend on ${\mathbf{x}}_{1}^{\prime}$ and are hence correlated. So we upper
bound (I) using Hölder’s inequality to get:

$\text{(I)}\leq\sqrt{\mathbb{E}\Bigg{[}\Big{(}\exp\big{(}-r{\mathrm{y}}_{1}^{\prime}\langle{\mathbf{x}}_{1}^{\prime},{\mathbf{x}}\rangle\big{)}-\exp\big{(}r{\mathrm{y}}_{1}^{\prime}\langle{\mathbf{x}}_{1}^{\prime},{\mathbf{x}}\rangle\big{)}\Big{)}^{2}\Bigg{]}{\mathbb{E}\Bigg{[}\Big{(}\mathbb{P}\big{(}\widetilde{\mathrm{y}}_{1}^{\prime}=-{\mathrm{y}}_{1}^{\prime}\big{)}\Big{)}^{2}\Bigg{]}}}.$
(111)

From eq. 102, we have
$\mathbb{P}\big{(}\widetilde{\mathrm{y}}_{1}^{\prime}=-{\mathrm{y}}_{1}^{\prime}\big{)}\leq
1-\alpha({\mathbf{x}}_{1}^{\prime})=\exp\Big{(}-\frac{n\mu^{2}}{4}(1-2p)^{2}\textup{cos}^{2}\big{(}\beta({\mathbf{x}}_{1}^{\prime})\big{)}\Big{)}$.
Thus:

$\mathbb{E}\Bigg{[}\Big{(}\mathbb{P}\big{(}\widetilde{\mathrm{y}}_{1}^{\prime}=-{\mathrm{y}}_{1}^{\prime}\big{)}\Big{)}^{2}\Bigg{]}\leq\mathbb{E}\Bigg{[}\exp\Bigg{(}-\frac{n\mu^{2}}{2}(1-2p)^{2}\textup{cos}^{2}\big{(}\beta({\mathbf{x}}_{1}^{\prime})\big{)}\Bigg{)}\Bigg{]}.$
(112)

Similar to eq. 64 in the proof of Theorem 2, it can be shown that:

$\displaystyle\mathbb{E}\Bigg{[}\exp\Bigg{(}-\frac{n\mu^{2}}{2}(1-2p)^{2}\textup{cos}^{2}\big{(}\beta({\mathbf{x}}_{1}^{\prime})\big{)}\Bigg{)}\Bigg{]}\leq\exp\Bigg{(}-\frac{9(d-1)}{20}\Bigg{)}+\exp\Bigg{(}-\frac{n\mu^{2}}{6d}(1-2p)^{2}\gamma^{2}\Bigg{)},$
(113)

and so:

$\mathbb{E}\Bigg{[}\Big{(}\mathbb{P}\big{(}\widetilde{\mathrm{y}}_{1}^{\prime}=-{\mathrm{y}}_{1}^{\prime}\big{)}\Big{)}^{2}\Bigg{]}\leq\exp\Bigg{(}-\frac{9(d-1)}{20}\Bigg{)}+\exp\Bigg{(}-\frac{n\mu^{2}}{6d}(1-2p)^{2}\gamma^{2}\Bigg{)}.$
(114)

Next,

$\displaystyle\mathbb{E}\Bigg{[}\Big{(}\exp\big{(}-r{\mathrm{y}}_{1}^{\prime}\langle{\mathbf{x}}_{1}^{\prime},{\mathbf{x}}\rangle\big{)}-\exp\big{(}r{\mathrm{y}}_{1}^{\prime}\langle{\mathbf{x}}_{1}^{\prime},{\mathbf{x}}\rangle\big{)}\Big{)}^{2}\Bigg{]}$
$\displaystyle=\mathbb{E}\Big{[}\exp\big{(}-2r{\mathrm{y}}_{1}^{\prime}\langle{\mathbf{x}}_{1}^{\prime},{\mathbf{x}}\rangle\big{)}+\exp\big{(}2r{\mathrm{y}}_{1}^{\prime}\langle{\mathbf{x}}_{1}^{\prime},{\mathbf{x}}\rangle\big{)}-2\Big{]}.$
(115)

Using eq. 20 and eq. 21 in the proof of Theorem 1 above, we get:

$\mathbb{E}\Bigg{[}\Big{(}\exp\big{(}-r{\mathrm{y}}_{1}^{\prime}\langle{\mathbf{x}}_{1}^{\prime},{\mathbf{x}}\rangle\big{)}-\exp\big{(}r{\mathrm{y}}_{1}^{\prime}\langle{\mathbf{x}}_{1}^{\prime},{\mathbf{x}}\rangle\big{)}\Big{)}^{2}\Bigg{]}\leq\\\
\Big{(}\underbrace{\exp\big{(}-2\mu\sigma
r{\mathrm{x}}^{(1)}\big{)}+\exp\big{(}2\mu\sigma
r{\mathrm{x}}^{(1)}\big{)}}_{=2\text{cosh}(2\mu\sigma
r{\mathrm{x}}^{(1)})}\Big{)}\exp\Big{(}2{(\sigma
r\|{\mathbf{x}}\|)^{2}}\Big{)}-2.$ (116)

For brevity, let $h(r):=2\text{cosh}\big{(}2\mu\sigma
r{\mathrm{x}}^{(1)}\big{)}\exp\big{(}2{(\sigma
r\|{\mathbf{x}}\|)^{2}}\big{)}-2$. Plugging in eq. 114 and eq. 116 into eq.
111 yields:

(I)
$\displaystyle\leq\sqrt{h(r)}\sqrt{\exp\Bigg{(}-\frac{9(d-1)}{20}\Bigg{)}+\exp\Bigg{(}-\frac{n\mu^{2}}{6d}(1-2p)^{2}\gamma^{2}\Bigg{)}}$
$\displaystyle\leq\sqrt{h(r)}\underbrace{\Bigg{(}\exp\Bigg{(}-\frac{9(d-1)}{40}\Bigg{)}+\exp\Bigg{(}-\frac{n\mu^{2}}{12d}(1-2p)^{2}\gamma^{2}\Bigg{)}\Bigg{)}}_{=p_{2}},$
(117)

where the last step is obtained using the fact that
$\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ for any $a,b\geq 0$. Also, let us put
$p_{2}=\exp\Big{(}-\frac{9(d-1)}{40}\Big{)}+\exp\Big{(}-\frac{n\mu^{2}}{12d}(1-2p)^{2}\gamma^{2}\Big{)}$.
Here we consider the case of $n$ and $d$ being large enough so that
$p_{2}\leq\frac{1}{2}$. Now plugging in eq. 110 and eq. 117 into eq. 109 gives
us:

$\mathbb{E}\Big{[}\exp\big{(}r\widetilde{\mathrm{y}}_{1}^{\prime}\langle{\mathbf{x}}_{1}^{\prime},{\mathbf{x}}\rangle\big{)}\Big{]}\leq\exp\big{(}\mu\sigma
r{\mathrm{x}}^{(1)}\big{)}{\exp\Bigg{(}\frac{(\sigma
r\|{\mathbf{x}}\|)^{2}}{2}\Bigg{)}}+p_{2}\sqrt{h(r)}.$ (118)

Let us pick
$r=r^{*}:=-\frac{\mu{\mathrm{x}}^{(1)}(1-2p_{2})}{2\sigma\|{\mathbf{x}}\|^{2}}$
(recall ${\mathrm{x}}^{(1)}>0$). Note that $r^{*}<0$ and we needed $r$ to be
$<0$ for the Chernoff bound in eq. 105 to hold. With this value of $r$, we
have:

$\displaystyle\exp\big{(}\mu\sigma
r^{*}{\mathrm{x}}^{(1)}\big{)}{\exp\Bigg{(}\frac{(\sigma
r^{*}\|{\mathbf{x}}\|)^{2}}{2}\Bigg{)}}$
$\displaystyle=\exp\Bigg{(}-\frac{(\mu{\mathrm{x}}^{(1)})^{2}(1-2p_{2})}{2\|{\mathbf{x}}\|^{2}}\Bigg{(}1-\frac{1-2p_{2}}{4}\Bigg{)}\Bigg{)}$
$\displaystyle\leq\exp\Bigg{(}-\frac{3(\mu{\mathrm{x}}^{(1)})^{2}(1-2p_{2})}{8\|{\mathbf{x}}\|^{2}}\Bigg{)}.$
(119)

Let $u:=\frac{(\mu{\mathrm{x}}^{(1)})^{2}}{\|{\mathbf{x}}\|^{2}}$. The above
equation in terms of $u$ is:

$\exp\big{(}\mu\sigma r^{*}{\mathrm{x}}^{(1)}\big{)}{\exp\Bigg{(}\frac{(\sigma
r^{*}\|{\mathbf{x}}\|)^{2}}{2}\Bigg{)}}\leq\exp\Big{(}-\frac{3u}{8}(1-2p_{2})\Big{)}.$
(120)

Also, recall that:

$\displaystyle h(r^{*})$ $\displaystyle=2\text{cosh}\big{(}2\mu\sigma
r^{*}{\mathrm{x}}^{(1)}\big{)}\exp\big{(}2{(\sigma
r^{*}\|{\mathbf{x}}\|)^{2}}\big{)}-2.$

It can be checked that:

$\displaystyle
h(r^{*})={2\text{cosh}\big{(}u(1-2p_{2})\big{)}\exp\Big{(}\frac{u}{2}(1-2p_{2})^{2}\Big{)}-2}.$
(121)

Since $\mu\leq\frac{1}{2}$ and ${\mathrm{x}}^{(1)}\leq\|{\mathbf{x}}\|$,
$u\leq\frac{1}{4}$ and thus, $u(1-2p_{2})\leq\frac{1}{4}$ and
$\frac{u}{2}(1-2p_{2})^{2}\leq\frac{1}{8}$. Using Lemma 8 and Lemma 9 above,
we get:

$\displaystyle h(r^{*})$ $\displaystyle\leq
2\Big{(}1+\frac{8}{15}u^{2}(1-2p_{2})^{2}\Big{)}\Big{(}1+\frac{4}{7}u(1-2p_{2})^{2}\Big{)}-2$
(122)
$\displaystyle={8}u(1-2p_{2})^{2}\Bigg{(}\frac{1}{7}+\frac{2}{15}u+\frac{8}{105}u^{2}(1-2p_{2})^{2}\Bigg{)}.$
(123)

Further, using the fact that $u\leq\frac{1}{4}$ and
$u^{2}(1-2p_{2})^{2}\leq\frac{1}{16}$ above, we get:

$h(r^{*})\leq{2u}(1-2p_{2})^{2}.$ (124)

Plugging in eq. 120 and eq. 124 into eq. 118, we get for $r=r^{*}$:

$\displaystyle\mathbb{E}\Big{[}\exp\big{(}r^{*}\widetilde{\mathrm{y}}_{1}^{\prime}\langle{\mathbf{x}}_{1}^{\prime},{\mathbf{x}}\rangle\big{)}\Big{]}$
$\displaystyle\leq\exp\Big{(}-\frac{3u}{8}(1-2p_{2})\Big{)}+{p_{2}\sqrt{2u}}(1-2p_{2})$
$\displaystyle=\exp\Big{(}-\frac{3u}{8}(1-2p_{2})\Big{)}\Bigg{(}1+{p_{2}\sqrt{2u}}(1-2p_{2})\exp\Big{(}\frac{3u}{8}(1-2p_{2})\Big{)}\Bigg{)}.$

Now note that $\exp\Big{(}\frac{3u}{8}(1-2p_{2})\Big{)}\leq e^{\frac{3}{32}}$
as $u(1-2p_{2})\leq\frac{1}{4}$. Using this above together with the fact that
$\sqrt{2}\times e^{\frac{3}{32}}\leq 2$, we get:

$\displaystyle\mathbb{E}\Big{[}\exp\big{(}r^{*}\widetilde{\mathrm{y}}_{1}^{\prime}\langle{\mathbf{x}}_{1}^{\prime},{\mathbf{x}}\rangle\big{)}\Big{]}$
$\displaystyle\leq\exp\Big{(}-\frac{3u}{8}(1-2p_{2})\Big{)}\Big{(}1+2{p_{2}\sqrt{u}}(1-2p_{2})\Big{)}$
$\displaystyle\leq\exp\Big{(}-\frac{3u}{8}(1-2p_{2})+2{p_{2}\sqrt{u}}(1-2p_{2})\Big{)},$
(125)

where the last step follows by using the fact that $\exp(z)\geq 1+z$ for all
$z\in\mathbb{R}$. Plugging in the value of
$u=\frac{(\mu{\mathrm{x}}^{(1)})^{2}}{\|{\mathbf{x}}\|^{2}}$ above and
recalling that
$\big{|}\textup{cos}\big{(}\beta({\mathbf{x}})\big{)}\big{|}=\frac{|{\mathrm{x}}^{(1)}|}{\|{\mathbf{x}}\|}$,
we get:

$\displaystyle\mathbb{E}\Big{[}\exp\big{(}r^{*}\widetilde{\mathrm{y}}_{1}^{\prime}\langle{\mathbf{x}}_{1}^{\prime},{\mathbf{x}}\rangle\big{)}\Big{]}$
$\displaystyle\leq\exp\Bigg{(}-(1-2p_{2})\Bigg{(}\frac{3\mu^{2}}{8}\textup{cos}^{2}\big{(}\beta({\mathbf{x}})\big{)}-{2p_{2}\mu}\big{|}\textup{cos}\big{(}\beta({\mathbf{x}})\big{)}\big{|}\Bigg{)}\Bigg{)}.$
(126)

Plugging in eq. 126 into eq. 107 and then applying that into eq. 106 yields:

$\mathbb{E}\Big{[}\exp\big{(}r^{*}\varepsilon^{\prime}\big{)}\Big{]}\leq\exp\Bigg{(}-n(1-2p_{2})\Bigg{(}\frac{3\mu^{2}}{8}\textup{cos}^{2}\big{(}\beta({\mathbf{x}})\big{)}-{2p_{2}\mu}\big{|}\textup{cos}\big{(}\beta({\mathbf{x}})\big{)}\big{|}\Bigg{)}\Bigg{)}.$
(127)

Next, plugging this into eq. 105 gives us:

$\displaystyle\mathbb{P}\big{(}\varepsilon^{\prime}\leq
0\big{)}\leq\exp\Bigg{(}-n(1-2p_{2})\Bigg{(}\underbrace{\frac{3\mu^{2}}{8}\textup{cos}^{2}\big{(}\beta({\mathbf{x}})\big{)}-{2p_{2}\mu}\big{|}\textup{cos}\big{(}\beta({\mathbf{x}})\big{)}\big{|}}_{:=\text{(II)}}\Bigg{)}\Bigg{)}.$
(128)

Now as long as
$|\textup{cos}\big{(}\beta({\mathbf{x}})\big{)}|\geq\frac{{16p_{2}}}{\mu}$,
$\text{(II)}\geq\frac{\mu^{2}}{4}\textup{cos}^{2}\big{(}\beta({\mathbf{x}})\big{)}$
and thus:

$\displaystyle\mathbb{P}\big{(}\varepsilon^{\prime}\leq
0\big{)}\leq\exp\Bigg{(}-\frac{n\mu^{2}}{4}(1-2p_{2})\textup{cos}^{2}\big{(}\beta({\mathbf{x}})\big{)}\Bigg{)}.$
(129)

Recalling the definition of $\varepsilon^{\prime}$ (eq. 104) and using the
result above that in eq. 103, we obtain the following bound for the case of
${\mathrm{y}}=1$:

$\mathbb{P}\Big{(}\langle{\mathbf{x}},\widehat{\bm{\theta}}_{1}\rangle\leq
0\Big{)}\leq\exp\Bigg{(}-\frac{n\mu^{2}}{4}(1-2p_{2})\textup{cos}^{2}\big{(}\beta({\mathbf{x}})\big{)}\Bigg{)},$
(130)

as long as
$|\textup{cos}\big{(}\beta({\mathbf{x}})\big{)}|\geq\frac{{16p_{2}}}{\mu}$
with
$p_{2}=\exp\Big{(}-\frac{9(d-1)}{40}\Big{)}+\exp\Big{(}-\frac{n\mu^{2}}{12d}(1-2p)^{2}\gamma^{2}\Big{)}$.
This finishes the proof of the result for the case of ${\mathrm{y}}=1$. The
result for the other case, i.e. ${\mathrm{y}}=-1$, can be derived similarly as
above by analyzing with $r>0$ instead. In particular, for the case of
${\mathrm{y}}=-1$, we get:

$\mathbb{P}\Big{(}\langle{\mathbf{x}},\widehat{\bm{\theta}}_{1}\rangle>0\Big{)}\leq\exp\Bigg{(}-\frac{n\mu^{2}}{4}(1-2p_{2})\textup{cos}^{2}\big{(}\beta({\mathbf{x}})\big{)}\Bigg{)},$
(131)

again as long as
$|\textup{cos}\big{(}\beta({\mathbf{x}})\big{)}|\geq\frac{{16p_{2}}}{\mu}$. ∎

######  Lemma 8.

For $t\leq\frac{1}{4}$, it holds that:

$\textup{cosh}(t)\leq 1+\frac{8t^{2}}{15}.$

###### Proof.

Using the Taylor expansion of $\textup{cosh}(t)$, we get:

$\displaystyle\textup{cosh}(t)$
$\displaystyle=1+\frac{t^{2}}{2!}+\frac{t^{4}}{4!}+\ldots$ (132)
$\displaystyle\leq 1+\frac{t^{2}}{2}\Big{(}1+t^{2}+\ldots\Big{)}$ (133)
$\displaystyle=1+\frac{t^{2}}{2(1-t^{2})}$ (134)

Since $t\leq\frac{1}{4}$, $1-t^{2}\geq\frac{15}{16}$. Using this above gives
us the desired result. ∎

######  Lemma 9.

For $t\leq\frac{1}{8}$, it holds that:

$e^{t}\leq 1+\frac{8t}{7}.$

###### Proof.

Using the Taylor expansion of $e^{t}$, we get:

$\displaystyle e^{t}$
$\displaystyle=1+t+\frac{t^{2}}{2!}+\frac{t^{3}}{3!}+\frac{t^{4}}{4!}+\ldots$
(135) $\displaystyle\leq 1+t\big{(}1+t+t^{2}+\ldots\big{)}$ (136)
$\displaystyle=1+\frac{t}{(1-t)}.$ (137)

Since $t\leq\frac{1}{8}$, $(1-t)\geq\frac{7}{8}$. Using this above gives us
the desired result. ∎

##  Appendix F Proof of Theorem 5

###### Proof.

Just like the proof of Theorem 2, we can prove the result for
$\bm{\theta}^{\ast}={\mathbf{e}}_{1}$ and
$\mathcal{B}=\\{{\mathbf{e}}_{1},{\mathbf{e}}_{2},\ldots,{\mathbf{e}}_{d}\\}$
without loss of generality. In that case,
${\mathrm{a}}^{(j)}={\mathrm{x}}^{(j)}=\langle{\mathbf{x}},{\mathbf{e}}_{j}\rangle$
for $j\in[d]$, the ground truth label of ${\mathbf{x}}$ is
$\text{sign}({\mathrm{x}}^{(1)})$ and
$\big{|}\textup{cos}\big{(}\beta({\mathbf{x}})\big{)}\big{|}=\frac{|{\mathrm{x}}^{(1)}|}{\|{\mathbf{x}}\|}$.

For the above case, we have:141414To be explicit, in the series of equations
below, we can go from eq. 140 to eq. 141 because
$\mathcal{X}_{L}\cup\mathcal{X}_{U}$ has zero measure.

$\displaystyle\text{acc}(\widehat{\bm{\theta}}_{1})$
$\displaystyle=\mathbb{P}_{{\mathbf{x}}\sim\mathcal{D},\mathcal{T},\mathcal{T}_{2}}\Big{(}\textup{sign}\big{(}\langle{\mathbf{x}},\widehat{\bm{\theta}}_{1}\rangle\big{)}=\text{sign}({\mathrm{x}}^{(1)})\Big{)}$
(138)
$\displaystyle=\mathbb{E}_{{\mathbf{x}}\sim\mathcal{D},\mathcal{T},\mathcal{T}_{2}}\Bigg{[}\mathbbm{1}\Big{(}\textup{sign}\big{(}\langle{\mathbf{x}},\widehat{\bm{\theta}}_{1}\rangle\big{)}=\textup{sign}\big{(}{\mathrm{x}}^{(1)}\big{)}\Big{)}\Bigg{]}$
(139)
$\displaystyle=\mathbb{E}_{{\mathbf{x}}\sim\mathcal{D}}\Bigg{[}\mathbb{P}_{\mathcal{T},\mathcal{T}_{2}}\Big{(}\textup{sign}\big{(}\langle{\mathbf{x}},\widehat{\bm{\theta}}_{1}\rangle\big{)}=\textup{sign}\big{(}{\mathrm{x}}^{(1)}\big{)}\Big{)}\Bigg{]}$
(140)
$\displaystyle\geq\mathbb{E}_{{\mathbf{x}}\sim\mathcal{D}}\Bigg{[}\alpha_{1}({\mathbf{x}})\Big{|}|\textup{cos}\big{(}\beta({\mathbf{x}})\big{)}|\geq\frac{\gamma}{\sqrt{\gamma^{2}+{3}(d-1)}}\Bigg{]}\mathbb{P}\Bigg{(}|\textup{cos}\big{(}\beta({\mathbf{x}})\big{)}|\geq\frac{\gamma}{\sqrt{\gamma^{2}+{3}(d-1)}}\Bigg{)},$
(141)

where
$\alpha_{1}({\mathbf{x}})=1-\exp\Big{(}-\frac{n\mu^{2}}{4}(1-2p_{2})\textup{cos}^{2}\big{(}\beta({\mathbf{x}})\big{)}\Big{)}$
is as defined in Theorem 4 and we will ensure
$\frac{\gamma}{\sqrt{\gamma^{2}+{3}(d-1)}}\geq\frac{{16p_{2}}}{\mu}$, which
can be simplified to:

$p_{2}\leq\Theta\Big{(}\frac{\gamma\mu}{\sqrt{d}}\Big{)}.$

Recall that
$p_{2}=\exp\Big{(}-\frac{9(d-1)}{40}\Big{)}+\exp\Big{(}-\frac{n\mu^{2}\gamma^{2}}{12d}(1-2p)^{2}\Big{)}=\exp\big{(}-\Theta(d)\big{)}+\exp\Big{(}-\frac{n\mu^{2}\gamma^{2}(1-2p)^{2}}{\Theta(d)}\Big{)}$.
Note that
$\exp\big{(}-\Theta(d)\big{)}\leq\Theta\Big{(}\frac{\gamma\mu}{\sqrt{d}}\Big{)}$
when $\gamma\geq\Theta\Big{(}\frac{\sqrt{d}\exp(-\Theta(d))}{\mu}\Big{)}$.
Imposing
$\exp\Big{(}-\frac{n\mu^{2}\gamma^{2}(1-2p)^{2}}{\Theta(d)}\Big{)}\leq\Theta\Big{(}\frac{\gamma\mu}{\sqrt{d}}\Big{)}$
gives us:

$n\geq\Theta\Bigg{(}\frac{1}{(1-2p)^{2}}\Big{(}\frac{d}{\mu^{2}\gamma^{2}}\Big{)}\log\Big{(}\frac{d}{\mu^{2}\gamma^{2}}\Big{)}\Bigg{)}.$
(142)

Also, just like Corollary 1, when $p>(1+\Theta(1))\exp(-\Theta({d}))$ and
$n>\Theta\Big{(}\frac{\log{1}/{p}}{(1-2p)^{2}}\Big{(}\frac{d}{\mu^{2}\gamma^{2}}\Big{)}\Big{)}$,
$p_{2}<p$; merging this bound on $n$ with the one in eq. 142 $\Big{(}$which
ensures $p_{2}\leq\Theta\Big{(}\frac{\gamma\mu}{\sqrt{d}}\Big{)}\Big{)}$, we
get:

$n\geq\Theta\Bigg{(}\frac{1}{(1-2p)^{2}}\Big{(}\frac{d}{\mu^{2}\gamma^{2}}\Big{)}\max\Bigg{(}\log\Big{(}\frac{d}{\mu^{2}\gamma^{2}}\Big{)},\log\frac{1}{p}\Bigg{)}\Bigg{)}.$
(143)

So our final bound for $p_{2}$ is:

$p_{2}\leq\min\Big{(}p,\Theta\Big{(}\frac{\gamma\mu}{\sqrt{d}}\Big{)}\Big{)}.$
(144)

With the above constraint, we get after applying Lemma 3:

$\mathbb{P}\Bigg{(}|\textup{cos}\big{(}\beta({\mathbf{x}})\big{)}|\geq\frac{\gamma}{\sqrt{\gamma^{2}+{3}(d-1)}}\Bigg{)}\geq
1-\exp\big{(}-\Theta(d)\big{)}.$ (145)

Moreover, with our constraint:

$\mathbb{E}_{{\mathbf{x}}\sim\mathcal{D}}\Bigg{[}\alpha_{1}({\mathbf{x}})\Big{|}|\textup{cos}\big{(}\beta({\mathbf{x}})\big{)}|\geq\frac{\gamma}{\sqrt{\gamma^{2}+{3}(d-1)}}\Bigg{]}\geq
1-\exp\Bigg{(}-\frac{n{\mu^{2}\gamma^{2}}(1-2p_{2})}{\Theta(d)}\Bigg{)}.$
(146)

Plugging in eq. 145 and eq. 146 into eq. 141 gives us:

$\text{acc}(\widehat{\bm{\theta}}_{1})\geq
1-\exp\big{(}-\Theta(d)\big{)}-\exp\Bigg{(}-\frac{n{\mu^{2}\gamma^{2}}(1-2p_{2})}{\Theta(d)}\Bigg{)}.$
(147)

This completes the proof. ∎

##  Appendix G Roadmap of Analysis with Exact Minimizer
$\bar{\bm{\theta}}_{0}$

Let

${\mathbf{P}}:=\Bigg{(}\frac{1}{n}\sum_{k=1}^{n}{\mathbf{x}}_{k}{\mathbf{x}}_{k}^{\top}-\sigma^{2}{\mathbf{I}}_{d}\Bigg{)}.$
(148)

Then, we can write:

$\displaystyle\bar{\bm{\theta}}_{0}=\Bigg{(}\frac{1}{n}\sum_{k=1}^{n}{\mathbf{x}}_{k}{\mathbf{x}}_{k}^{\top}\Bigg{)}^{-1}\Bigg{(}\frac{1}{n}\sum_{j=1}^{n}\widehat{\mathrm{y}}_{j}{\mathbf{x}}_{j}\Bigg{)}=\frac{1}{\sigma^{2}}\Bigg{(}{\mathbf{I}}_{d}+\frac{{\mathbf{P}}}{\sigma^{2}}\Bigg{)}^{-1}\Bigg{(}\frac{1}{n}\sum_{j=1}^{n}\widehat{\mathrm{y}}_{j}{\mathbf{x}}_{j}\Bigg{)}.$
(149)

We can bound $\|{\mathbf{P}}\|$ with high probability. For instance, using
Theorem 13.3 of Rinaldo and Neopane, (2018), we have with a probability of at
least $1-\delta$:

$\|{\mathbf{P}}\|\leq
C\sigma^{2}\max\Bigg{(}\sqrt{\frac{d+\log(2/\delta)}{n}},\frac{d+\log(2/\delta)}{n}\Bigg{)},$
(150)

for some absolute constant $C>0$. We will focus on the case of
$n>\mathcal{O}\big{(}d+\log(2/\delta)\big{)}$; in that case, we have:

$\|{\mathbf{P}}\|\leq C\sigma^{2}\sqrt{\frac{d+\log(2/\delta)}{n}},$ (151)

with a probability of at least $1-\delta$. From eq. 2, recall:

$\widehat{\bm{\theta}}_{0}=\frac{1}{\sigma^{2}}\Bigg{(}\frac{1}{n}\sum_{j=1}^{n}\widehat{\mathrm{y}}_{j}{\mathbf{x}}_{j}\Bigg{)},$
(152)

Then using Lemma 10, we get:

$\|\bar{\bm{\theta}}_{0}-\widehat{\bm{\theta}}_{0}\|\leq\Bigg{(}\frac{\frac{\|{\mathbf{P}}\|}{\sigma^{2}}}{1-\frac{\|{\mathbf{P}}\|}{\sigma^{2}}}\Bigg{)}\|\widehat{\bm{\theta}}_{0}\|.$
(153)

Next, using eq. 151 above, we get:

$\|\bar{\bm{\theta}}_{0}-\widehat{\bm{\theta}}_{0}\|\leq\Bigg{(}\frac{C\sqrt{\frac{d+\log(2/\delta)}{n}}}{1-{C}\sqrt{\frac{d+\log(2/\delta)}{n}}}\Bigg{)}\|\widehat{\bm{\theta}}_{0}\|,$
(154)

with a probability of at least $1-\delta$. Note that:

$\displaystyle\langle{\mathbf{x}}^{\prime},\bar{\bm{\theta}}_{0}\rangle$
$\displaystyle=\langle{\mathbf{x}}^{\prime},\widehat{\bm{\theta}}_{0}\rangle+\langle{\mathbf{x}}^{\prime},\bar{\bm{\theta}}_{0}-\widehat{\bm{\theta}}_{0}\rangle.$

Using the Cauchy-Schwarz inequality and eq. 154 above, we get:

$\displaystyle\Big{|}\langle{\mathbf{x}}^{\prime},\bar{\bm{\theta}}_{0}\rangle-\langle{\mathbf{x}}^{\prime},\widehat{\bm{\theta}}_{0}\rangle\Big{|}\leq\Bigg{(}\frac{C\sqrt{\frac{d+\log(2/\delta)}{n}}}{1-C\sqrt{\frac{d+\log(2/\delta)}{n}}}\Bigg{)}\|{\mathbf{x}}^{\prime}\|\|\widehat{\bm{\theta}}_{0}\|,$
(155)

with a probability of at least $1-\delta$. So if we can bound
$\|\widehat{\bm{\theta}}_{0}\|$ with high probability, then we can focus on
analyzing $\langle{\mathbf{x}}^{\prime},\widehat{\bm{\theta}}_{0}\rangle$
(which we did previously) and slightly adapting the rest of the analysis to
account for this extra perturbation. We can indeed obtain sharp high-
probability bounds for $\|\widehat{\bm{\theta}}_{0}\|$ by showing that it is
norm-subGaussian as defined in Jin et al., (2019); we skip these calculations
here as they are lengthy and tedious. Thus, as stated in Section 4.1, the crux
of the proofs is in the analysis of
$\langle{\mathbf{x}}^{\prime},\widehat{\bm{\theta}}_{0}\rangle$.

######  Lemma 10.

For any ${\mathbf{z}}\in\mathbb{R}^{d}$ and
${\mathbf{\Delta}}\in\mathbb{R}^{d\times d}$ such that
$\|{\mathbf{\Delta}}\|<1$, we have:

$\|({\mathbf{I}}_{d}+{\mathbf{\Delta}})^{-1}{\mathbf{z}}-{\mathbf{z}}\|\leq\Bigg{(}\frac{\|{\mathbf{\Delta}}\|}{1-\|{\mathbf{\Delta}}\|}\Bigg{)}\|{\mathbf{z}}\|.$
(156)

###### Proof.

We have:

$\displaystyle\|({\mathbf{I}}_{d}+{\mathbf{\Delta}})^{-1}{\mathbf{z}}-{\mathbf{z}}\|$
$\displaystyle=\|({\mathbf{I}}_{d}+{\mathbf{\Delta}})^{-1}{\mathbf{z}}-({\mathbf{I}}_{d}+{\mathbf{\Delta}})({\mathbf{I}}_{d}+{\mathbf{\Delta}})^{-1}{\mathbf{z}}\|$
(157)
$\displaystyle=\Big{\|}\Big{(}{\mathbf{I}}_{d}-({\mathbf{I}}_{d}+{\mathbf{\Delta}})\Big{)}({\mathbf{I}}_{d}+{\mathbf{\Delta}})^{-1}{\mathbf{z}}\Big{\|}$
(158)
$\displaystyle\leq\|{\mathbf{\Delta}}\|\|({\mathbf{I}}_{d}+{\mathbf{\Delta}})^{-1}{\mathbf{z}}\|.$
(159)

But by the triangle inequality, we also have:

$\displaystyle\|({\mathbf{I}}_{d}+{\mathbf{\Delta}})^{-1}{\mathbf{z}}\|$
$\displaystyle\leq\|({\mathbf{I}}_{d}+{\mathbf{\Delta}})^{-1}{\mathbf{z}}-{\mathbf{z}}\|+\|{\mathbf{z}}\|$
(160)
$\displaystyle\leq\|{\mathbf{\Delta}}\|\|({\mathbf{I}}_{d}+{\mathbf{\Delta}})^{-1}{\mathbf{z}}\|+\|{\mathbf{z}}\|,$
(161)

where eq. 161 follows from eq. 159. Rearranging eq. 161 yields: