# Don’t fear the unlabelled: safe deep semi-supervised learning via simple
debiasing

Hugo Schmutz<EMAIL_ADDRESS>
Université Côte d’Azur
TIRO-MATOS, UMR CEA E4320
Inria, Maasai project-team
Laboratoire J.A. Dieudonné, UMR CNRS 7351
Nice, France Olivier Humbert<EMAIL_ADDRESS>
Université Côte d’Azur
TIRO-MATOS, UMR CEA E4320
Centre Antoine Lacassagne
Nice, France Pierre-Alexandre Mattei<EMAIL_ADDRESS>
Université Côte d’Azur
Inria, Maasai project-team
Laboratoire J.A. Dieudonné, UMR CNRS 7351
Nice, France

###### Abstract

Semi supervised learning (SSL) provides an effective means of leveraging
unlabelled data to improve a model’s performance. Even though the domain has
received a considerable amount of attention in the past years, most methods
present the common drawback of being unsafe. By safeness we mean the quality
of not degrading a fully supervised model when including unlabelled data. Our
starting point is to notice that the estimate of the risk that most
discriminative SSL methods minimise is biased, even asymptotically. This bias
makes these techniques untrustable without a proper validation set, but we
propose a simple way of removing the bias. Our debiasing approach is
straightforward to implement, and applicable to most deep SSL methods. We
provide simple theoretical guarantees on the safeness of these modified
methods, without having to rely on the strong assumptions on the data
distribution that SSL theory usually requires. We evaluate debiased versions
of different existing SSL methods and show that debiasing can compete with
classic deep SSL techniques in various classic settings and even performs well
when traditional SSL fails.

##  1 Introduction

The promise of semi-supervised learning (SSL) is to be able to learn powerful
predictive models using partially labelled data. In turn, this would allow
machine learning to be less dependent on the often costly and sometimes
dangerously biased task of labelling data.

Early SSL approaches—e.g. Scudder’s (1965) untaught pattern recognition
machine—simply replaced unknown labels by predictions made by some estimate of
the predictive model and used the obtained _pseudo-labels_ to refine their
initial estimate. Other more complex branches of SSL have been explored since,
notably using generative models (from McLachlan, 1977, to Kingma et al., 2014)
or graphs (notably following Zhu et al., 2003).

Deep neural networks, which are state-of-the art supervised predictors, have
been trained successfully using SSL. Somewhat surprisingly, the main
ingredient of their success is still the notion of pseudo-labels (or one of
its variants), combined with a systematic use of data augmentation (e.g. Xie
et al., 2019; Sohn et al., 2020; Rizve et al., 2021).

An obvious SSL baseline is to simply throw away the unlabelled data. We will
call such a baseline the _complete case_ , following the missing data
literature (e.g. Tsiatis, 2006). As reported in van Engelen and Hoos (2020),
the main risk of SSL is the potential degradation caused by the introduction
of unlabelled data. Indeed, semi-supervised learning outperforms the complete
case baseline only in specific cases (Singh et al., 2008; Schölkopf et al.,
2012; Li and Zhou, 2014). The degradation risk for generative models has been
analysed in Chapelle et al. (2006, Chapter 4). To overcome this issue,
previous works introduced the notion safe semi-supervised learning for
techniques which never reduce predictive performance by introducing unlabelled
data (Li and Zhou, 2014; Kawakita and Takeuchi, 2014; Li et al., 2016; Gan et
al., 2017; Trapp et al., 2017; Guo et al., 2020). Our loose definition of
safeness is as follows: _a SSL algorithm is safe if it has theoretical
guarantees that are similar or stronger to the complete case baseline_. The
“theoretical” part of the definition is motivated by the fact that any
empirical assessment of generalisation performances of an SSL algorithm is
jeopardised by the scarcity of labels. Indeed, with few labels, it is risky to
rely too much on a very small validation set.

Their is a growing interest for safe semi-supervised learning in the SSL
community. First, Guo et al. (2020) introduced a double optimisation process
assigning individual weights to the contribution of unlabelled data in the SSL
algortihms (Guo et al., 2020). The process can assign null weights to
unlabelled data, therefore the optimal solution is at least better then the
complete case. Sakai et al. (2017) focus on binary classification problem.
Inspired by positive unlabelled clasification, a framework where we do not
have labelled data for the negative class, they proposed an unbiased
modification of the risk estimate. The idea is to use unlabelled data to
better evaluate the risk for both negative and positive samples in order to
reduce its variance. In follow-up work (Tsuchiya et al., 2021) proposed a
similar approach based on an unbiased risk estimate for ordinal regression,
and demonstrated the Fisher consistency of their method, as well as other
theoretical properties. Older works have already proposed safe methods. For
instance, Sokolovska et al. (2008) use unlabelled data to weight the
contribution of labelled data in the risk estimator. S4VM (safe semi-
supervised support vector machine) is another discriminative model which is
not degrading the complete case, proposed by (Li and Zhou, 2014). The S4VM
comes with theoretical guarantees on the inclusion of unlabelled data, indeed
they show that if the true model is accessible, the accuracy of S4VM is never
worse than the complete case SVM. However, if the distributional assumptions
are not satisfied, no improvement or degeneration is expected.

Unfortunately, popular deep SSL techniques are generally not safe. Indeed,
they rely on strong and essentially untestable assumptions on the data
distribution:

  * •

the smoothness assumption: small perturbations on the features $x$ do not
cause large modification in the labels, $p(y|\text{pert}(x))\approx p(y|x)$;

  * •

the manifold assumption: data distribution support is a manifold lower
dimension than the input space then knowledge on $p(x)$ improves the
understanding of $p(x,y)$ or $p(y|x)$;

  * •

the cluster assumption: data points are distributed on discrete clusters and
points in the same cluster are likely to share the same label.

Most of semi-supervised methods rely on these distributional assumptions to
ensure performance in entropy minimisation, pseudo-labelling and consistency-
based methods. However, no proof is given that guarantees the effectiveness of
state-of-the-art methods (Tarvainen and Valpola, 2017; Miyato et al., 2018;
Sohn et al., 2020; Pham et al., 2021). To illustrate that SSL requires
specific assumptions, we show in a toy example that pseudo-labelling fails at
learning on a simple dataset on a simple setting. To do so, we draw samples
from two uniform distributions with a small overlap. Both supervised and semi-
supervised neural networks are trained using the same labelled dataset. While
the supervised algorithm learns perfectly the true distribution of $p(1|x)$,
the semi-supervised learning methods (both entropy minimisation and pseudo-
label) underestimate $p(1|x)$ for $x\in[1,3]$ (see Figure 1). We also tested
our proposed method (DeSSL) on this dataset and show that the unbiased version
of each SSL technique learns the true distribution perfectly. See Appendix A
for the results with Entropy Minimisation.

Figure 1: Neural net trained using SSL methods on a 1D dataset drawn from two
uniform laws. (Left) Data histogram. (Right) Posterior probabilities $p(1|x)$
of the same model trained following either complete case (only labelled data),
Pseudo-label or our DePseudo-label.

###  1.1 Contributions

Rather than relying on the strong geometric assumptions usually used in SSL
theory, we simply use the _missing completely at random (MCAR)_ assumption, a
standard assumption from the missing data literature (see e.g. Little and
Rubin, 2019). With this only assumption on the data distribution, we propose a
new safe SSL method derived from simply debiasing common SSL risk estimates.
Our main contributions are:

  * •

We introduce debiased SSL (DeSSL), a safe method that can be applied to most
deep SSL algorithms;

  * •

We propose a theoretical explanation of the intuition of the popular SSL
methods. We provide theoretical guarantees on the safeness of using DeSSL both
on consistency and calibration of the method. We also provide a generalisation
error bound;

  * •

We show how simple it is to apply DeSSL to existing methods and show
empirically that DeSSL leads to models that are never worse than their
classical counterparts, generally better calibrated and sometimes much more
accurate.

##  2 Semi-supervised learning

###  2.1 Learning with labelled data

The ultimate objective of most of the learning frameworks is to minimise a
risk $\mathcal{R}$, defined as the expectation of a particular loss function
$L$ over a data distribution $p(x,y)$, on a set of models $f_{\theta}(x)$,
parametrised by $\theta\in\Theta$. Thus, the learning task is finding
$\theta^{*}$ that minimises the risk:

$\mathcal{R}(\theta)=\mathbb{E}_{(X,Y)\sim p(x,y)}[L(\theta;X,Y)].$ (1)

The distribution $p(x,y)$ being unknown, we generally minimise an
approximation of the risk, the empirical risk $\hat{\mathcal{R}}(\theta)$
computed on a samples of $n$ i.i.d points drawn from $p(x,y)$.

$\hat{\mathcal{R}}(\theta)$ is an unbiased and consistent estimate of
$\mathcal{R}(\theta)$ under mild assumptions. Its unbiased nature is one of
the basic properties that is used for the development of traditional learning
theory and asymptotic statistics (van der Vaart, 2000; Shalev-Shwartz and Ben-
David, 2014).

###  2.2 Learning with both labelled and unlabelled data

The success of deep learning is contingent with the access to a large training
dataset. In fact, Hestness et al. (2017) argue that deep learning model
accuracy grows as a power law of the training set size. However, large
labelled datasets come with a cost since labelling must be done by an expert
and can be very time-consuming in the case of lung tumour segmentation for
instance. Fortunately, unlabelled data can be acquired at a significantly
lower cost and then may be used to improve the performance of a fully
supervised model. This is the idea behind semi-supervised learning: leveraging
both labelled and unlabelled data to improve the model’s performance and
generalisation. Indeed, having further information on the distribution $p(x)$
provides a better understanding of the distributions $p(x,y)$ and also
$p(y|x)$. Indeed, $p(x)$ may contain information on $p(y|x)$ (Schölkopf et al.
2012, Goodfellow et al. 2016, Chapter 7.6,van Engelen and Hoos 2020).

In the following, we have access to $n$ samples drawn from the distribution
$p(x,y)$ where some of the labels are missing. We introduce a new random
variable $r\in\\{0,1\\}$ that governs whether or not a data point is labelled
($r=0$ missing, $r=1$ observed). The MCAR assumption states that the
missingness of a label $y$ is independent of its features and the value of the
label: $p(x,y,r)=p(x,y)p(r)$. This is the case when nor features nor label
carry information about the potential missingness of the labels. This
description of semi-supervised learning as a missing data problem has already
been done in multiple works (Seeger, 2000; Grandvalet and Bengio, 2004; Ji et
al., 2012; Ahfock and McLachlan, 2019; Liu and Goldberg, 2020) and in a
reference book Chapelle et al. (2006, Chapters 5, 8 and 9). Moreover, the MCAR
assumption is implicitly made in most of the SSL works to design the
experiments, indeed, missing labels are drawn completely as random in datasets
such as MNIST, CIFAR or SVHN (Tarvainen and Valpola, 2017; Miyato et al.,
2018; Xie et al., 2019; Sohn et al., 2020).

####  2.2.1 Complete case: throwing the unlabelled data away

In missing data theory, the complete case is the learning scheme that only
uses fully observed instances, namely labelled data. The natural estimator of
the risk is then simply the empirical risk computed on the labelled data.
Fortunately, in the MCAR setting, the complete case risk estimate keeps the
same good properties of the traditional supervised one: it is unbiased and
converges pointwisely to $\mathcal{R}(\theta)$. Therefore, traditional
learning theory holds for the complete case under MCAR. While these
observations are hardly new (see e.g. Liu and Goldberg, 2020), they can be
seen as particular cases of the theory that we develop below. The risk to
minimise is

$\hat{\mathcal{R}}_{CC}(\theta)=\frac{1}{n_{l}}\sum_{i=1}^{n_{l}}L(\theta;x_{i},y_{i}).$
(2)

As discussed in the introduction, SSL faces the risk of performance
degradation when distributional assumptions are not satisfied (Singh et al.,
2008; Schölkopf et al., 2012; Li and Zhou, 2014) and specifically in settings
where the MCAR assumption does not hold anymore (Oliver et al., 2018; Guo et
al., 2020). In particular, in (Zhu et al., 2022), the authors show disparate
impacts of pseudo-labelling on the different sub-classes of the population.
Indeed, sub-classes with a higher baseline accuracy would tends to benefit
more from SSL than the others. Moreover, sub-classes with poor baseline
accuracy can even observe a performance drop. ”The rich get richer, the poor
get poorer”. To mitigate these problems, previous works introduced the notion
safe semi-supervised learning for techniques which never reduce learning
performance by introducing unlabelled data (Li and Zhou, 2014; Kawakita and
Takeuchi, 2014; Li et al., 2016; Gan et al., 2017; Trapp et al., 2017; Guo et
al., 2020). In real-world applications, validation sets are not large enough
to ensure the generalisation of the trained model and therefore, the
introduction of unlabelled data may come at the risk of degrading
performances. Then, theoretical guarantees are required to use safely SSL
algorithms. For this reason, in our work, we consider as _safe_ a SSL
algorithm that has theoretical guarantees that are similar or stronger than
those of the complete case baseline.

####  2.2.2 Incorporating unlabelled data

A major drawback of the complete case framework is that a lot of data ends up
not being exploited. A class of SSL approaches, mainly inductive methods with
respect to the taxonomy of van Engelen and Hoos (2020), generally aim to
minimise a modified estimator of the risk by including unlabelled data.
Therefore, the optimisation problem generally becomes finding $\hat{\theta}$
that minimises the SSL risk,

$\begin{split}\hat{\mathcal{R}}_{SSL}(\theta)&=\frac{1}{n_{l}}\sum_{i=1}^{n_{l}}L(\theta;x_{i},y_{i})\color[rgb]{1,0,0}{+\frac{\lambda}{n_{u}}\sum_{i=1}^{n_{u}}H(\theta;x_{i})}.\\\
\end{split}$ (3)

where $H$ is a term that does not depend on the labels and $\lambda$ is a
scalar weight which balances the labelled and unlabelled terms. In the
literature, $H$ can generally be seen as a surrogate of $L$. Indeed, it looks
like the intuitive choices of $H$ are equal or equivalent to a form of
expectation of $L$ on a distribution given by the model. Our theory will
indicate that it is desirable, indeed, that $H$ is positively correlated with
$L$.

####  2.2.3 Some examples of surrogates

A recent overview of the recent SSL techniques has been proposed by van
Engelen and Hoos (2020). Most of the methods considered here are suited for a
discriminative probabilistic model $p_{\theta}(y|x)$ that approximates the
conditional $p(y|x)$. Methods can be categorised into two distinct sections,
the entropy and the consistency-based methods. The former aim to minimise a
form of entropy of the model predictions, the latter will enforce stability on
model predictions given modifications of the input (data augmentation) or
perturbations of the model.

##### Entropy-based methods:

Entropy-based methods aim to minimise a term of entropy of the predictions
computed on unlabelled data. Thus, they encourage the model to be confident on
unlabelled data, implicitely using the cluster assumption. As we detail in
Appendix B, entropy-based methods can all be described as an expectation of
$L$ under a distribution $\pi_{x}$ computed at the datapoint $x$:

$H(\theta;x)=\mathbb{E}_{\pi_{x}(\tilde{x},\tilde{y})}[L(\theta;\tilde{x},\tilde{y})].$
(4)

Entropy Minisation (EntMin)
Grandvalet and Bengio (2004) simply use the Shannon entropy as $H(\theta;x)$.
This penalisation can be interpreted as favouring parameters inducing small
class overlap (Chapelle et al., 2006, Chapter 9). This Shannon entropy can be
rewritten as equation (4) with
$\pi_{x}(\tilde{x},\tilde{y})=\delta_{x}(\tilde{x})p_{\theta}(\tilde{y}|\tilde{x})$.
We note that entropy minimisation is the only method for which,
$\pi_{x}(\tilde{x},\tilde{y})$ does also depend of $\theta$.

Pseudo-label
Pseudo-labelling consists in picking the class with the maximum predicted
probability as a pseudo-label for the unlabelled data (Scudder, 1965).
Commonly, pseudo-labels are selected only if the predicted probability is
above a predefined threshold $\tau>0$. Again, this objective can be rewritten
in the form of Equation 4 (see Appendix B). Recently, (Rizve et al., 2021)
proposed an improved selection of pseudo-labels using uncertainty estimation
methods on the predicted probability.

Pseudo-label and data augmentation
Recently, several methods based on data-augmentation have been proposed and
proven to perform well on a large spectrum of SSL tasks. The idea is to have a
model resilient to strong data-augmentation of the input by predicting pseudo-
labels for unlabelled data using a augmented version of the input (Berthelot
et al., 2019, 2020; Xie et al., 2019; Sohn et al., 2020; Zhang et al., 2021).
These method rely both on the cluster assumption and the smoothness assumption
and are at the border between entropy-based and consistency-based methods. See
Appendix B.

##### Consistency-based methods

Another range of SSL methods minimise a consistency objective that encourages
invariant prediction for perturbations either on the data either on the model.
These methods rely on the smoothness assumption. In particular, consistency-
based method aim to smooth the decision function of the models or have more
stable predictions. These objectives $H$ are not directly a form of
expectation of $L$ but are equivalent to an expectation of $L$ (see Appendix
B). The general form of the unsupervised objective can be written as

$\displaystyle
H(\theta;x)=\textbf{Div}(f_{\hat{\theta}}(x,.),\text{pert}(f_{\theta}(x,.)),$
(5)

where the Div is a non-negative function that measures the divergence between
two distributions, the cross-entropy, the KL divergence or the $L^{2}$-norm
for instance and $\hat{\theta}$ is a fixed copy of the current parameter
$\theta$ (the gradient is not propagated throught $\hat{\theta}$).

In this category, we cite $\Pi$-model from (Sajjadi et al., 2016), temporal
ensembling from (Laine and Aila, 2017), Mean-teacher proposed by (Tarvainen
and Valpola, 2017), virtual adversarial training (VAT) from (Miyato et al.,
2018) and interpolation consistent training (ICT) from (Verma et al., 2019).

Intuitively, for entropy-based methods $H$ should be applied only on
unlabelled data. Indeed, entropy minimisation aims to enforce the confidence
of the model on unlabelled datapoints and therefore, applying also $H$ on
labelled data will increase the confidence of the model on labelled datapoints
and this may degrade the calibration. Whereas, for consistency-based method,
$H$ can be applied to any subset of data points. Our theory and proposed
method remain the same whether $H$ is applied on all the available data or not
(see Appendix H).

###  2.3 Theoretical guarantees

As explained previously, the main risk of SSL is the potential degradation
caused by the introduction of unlabelled data. At the moment, SSL performances
are enabled by leveraging large validation sets. Indeed, SSL performances rely
on extensive hyperparameter finetuning using a labelled validation set
significantly larger than the labelled training set (Oliver et al., 2018). In
real-world applications of SSL, it is reasonable to assume that the validation
set would be smaller than the labelled dataset used for training. Oliver et
al. (2018) show that for realistic validation set size ($\leq 20\%$ of
training data) it is impossible to differentiate different SSL models.
Therefore, for a real-world applications of SSL, theoretical guarantees should
ensure good performances.

Even though the methods presented above produce good performances in a variety
of SSL benchmarks, they generally do not benefit from theoretical guarantees,
even elementary. Assumptions such as the cluster or the smoothness assumptions
are invoked by the literature to identify cases where SSL methods would work.
However, these assumptions are strong and restrictive and, above all,
difficult to test in practice. For instance, Schölkopf et al. (2012) show that
depending on the causal relation between the features $x$ and the target $y$,
SSL may systematically fail, even if classic SSL assumptions hold. With our
toy example of Figure 1, we show that classic SSL may fail to generalise in a
very benign setting without restrictive distributional assumptions. This
example also shows that SSL fails even with a large number of labelled data.
Indeed, the risk estimate is not necessarily asymptotically consistent meaning
that even with an infinite amount of data the estimator would not give the
correct value of the risk $\mathcal{R}$. Therefore models may fail to
generalise even with an infinite number of labelled datapoints, as we show in
Figure 1. For these reasons, classic SSL assumptions do not afford enough
guarantees on the introduction of unlabelled data in the learning scheme in
real-world applications. To sum up, the performance of these methods are
evaluated empirically in particular scenarios chosen by the authors. Even if
it is quite straightforward to understand the motivation behind the methods,
they present no theoretical guarantees and may fail in real-world situations.

Presented methods minimise a biased version of the risk under the MCAR
assumption and therefore classical learning theory does not apply anymore,

$\mathbb{E}[\hat{\mathcal{R}}_{SSL}(\theta)]=\mathbb{E}[L(\theta;x,y)]{\color[rgb]{1,0,0}{+\lambda\mathbb{E}[H(\theta;x,y)]}}\neq\mathcal{R}(\theta).$
(6)

Indeed, the unbiased nature of the risk estimate is crucial in the development
of learning theory. This bias on the risk estimate may look like the one of a
regularisation, such as the ridge regularisation. However, SSL and
regularisation are intrinsically different for several reasons:

  * •

Regularisers have a vanishing impact in the limit of infinite data whereas SSL
usually do not in the proposed methods, see Equation 6. A solution would be to
choose $\lambda$ with respect of the number of data points and make it vanish
when $n$ goes to infinity. However, in most works, the choice of $\lambda$ is
independent of the number of $n$ or $n_{l}$ (Oliver et al., 2018; Sohn et al.,
2020).

  * •

One of the main advantages of regularisation is to turn the learning problem
into a “more convex” problem, see Shalev-Shwartz and Ben-David (2014, Chapter
13). Indeed, ridge regularisation will often turn a convex problem into a
strongly-convex problem. However, SSL faces the danger to turn the learning
problem as non-convex as previously noted by Sokolovska et al. (2008).

  * •

The objective of a regulariser is to bias the risk towards optimum with smooth
decision functions whereas entropy-based SSL will lead to sharp decision
functions.

  * •

Regularisation usually does not depend on the data whereas $H$ does in the SSL
framework.

A entropy bias has been actually used by Pereyra et al. (2017) as a
regulariser but as entropy maximisation which should has an effect that is the
opposite of the SSL method introduced by Grandvalet and Bengio (2004), the
entropy minimisation.

Previous works already proposed safe SSL methods with theoretical guarantees.
Unfortunately, so far these methods come with either strong assumptions or
important computational burden. Li and Zhou (2014) introduced a safe semi-
supervised SVM and showed that the accuracy of their method is never worse
than SVMs trained with only labelled data. Sakai et al. (2017) proposed an
unbiased estimate of the risk for binary classification by including
unlabelled data. The key idea is to use unlabelled data (knowledge about the
data distribution) to better evaluate in one hand the risk of positive class
samples and on the other hand the risk of negative samples. They provided
theoretical guarantees on its variance and a generalisation error bound. The
method is designed only for binary classification and has not been tested in a
deep learning setting. It has extended to ordinal regression in a follow-up
work (Tsuchiya et al., 2021).In the context of kernel machines, Liu and
Goldberg (2020) used an unbiased estimate of risk, similar to ours, for a
specific choice of $H$. Guo et al. (2020) proposed $DS^{3}L$, a method safe
that needs to approximately solve a bi-level optimisation problem. In
particular, the method is designed for a different setting, not under the MCAR
assumptiom, where there is a class mismatch between labelled and unlabelled
data. The resolution of the optimisation problem provides a solution not worse
than the complete case but comes with approximations. They provide a
generalisation error bound. Also the method does not outperform classic SSL
methods in the MCAR setting as it is designed for non-MCAR situations.
Sokolovska et al. (2008) proposed a safe method with strong assumptions such
that the feature space is finite and the marginal probability distribution of
$x$ is fully known. The idea is to use a infinite number of unlabelled data,
so a full knowledge of $p(x)$ to better approximate the joint density
$\hat{p}(x,y)$ in the risk estimator
$\mathbb{E}_{\hat{p}(x,y)}[L(\theta;x,y)]$.

##  3 DeSSL: Unbiased semi-supervised learning

In order to overcome the issues introduced by the second term in the
approximation of the risk for the semi-supervised learning approach, we
propose DeSSL, an unbiased version of the SSL estimator using labelled data to
annul the bias. The idea here is to retrieve the properties of classical
learning theory. Fortunately, we will see that the proposed method can
eventually have better properties than the complete case, in particular with
regards to the variance of the estimate. The proposed DeSSL objective is

$\begin{split}\hat{\mathcal{R}}_{DeSSL}(\theta)=\frac{1}{n_{l}}\sum_{i=1}^{n_{l}}L(\theta;x_{i},y_{i})&\color[rgb]{1,0,0}{+\frac{\lambda}{n_{u}}\sum_{i=1}^{n_{u}}H(\theta;x_{i})}\\\
&\color[rgb]{0,0,1}{-\frac{\lambda}{n_{l}}\sum_{i=1}^{n_{l}}H(\theta;x_{i}).}\end{split}$
(7)

Under the MCAR assumption, this estimator is unbiased for any value of the
parameter $\lambda$. For a proof of this result see Appendix C. This way of
debiasing is closely related to the method of control variates (Owen, 2013,
Chapter 8) which is a common variance reduction technique. The idea is to add
an additional term to a Monte-Carlo estimator with a null expectation in order
to reduce the variance of the estimator without modifying the expectation.

###  3.1 Does the DeSSL risk estimator make sense?

There are different ways to interpret the DeSSL method. The most intuitive
interpretation is that by debiasing the risk estimator, we get back to the
basics of learning theory. As mentioned above, there is also a close
relationship with the method of control variates. Moreover, DeSSL can also be
interpreted as a control variate on the risk’s gradient itself in order to
reduce its variance and improve the optimisation scheme. This idea is close to
the optimisation schemes introduced by Johnson and Zhang (2013) and Defazio et
al. (2014) which reduce the variance of the gradients’ estimate to improve
optimisation performance.

Another interesting way to interpret DeSSL is as a constrained optimisation
problem. Indeed, minimising $\hat{\mathcal{R}}_{DeSSL}$ is equivalent to
minimising the Lagrangian of the following optimisation problem:

$\displaystyle\min_{\theta}$ $\displaystyle\hat{\mathcal{R}}_{CC}(\theta)$ (8)
s.t.
$\displaystyle\frac{1}{n_{u}}\sum_{i=1}^{n_{u}}H(\theta;x_{i})=\frac{1}{n_{l}}\sum_{i=1}^{n_{l}}H(\theta;x_{i}).$

The idea of this optimisation problem is to minimise the complete case risk
estimator by assessing that some properties represented by $H$ are on average
equal for the labelled data and the unlabelled data. For example, if we
consider entropy-minimisation, this program encourages the model to have the
same confidence on the unlabelled examples as on the labelled ones.

The debiasing term of our objective will penalise the confidence of the model
on the labelled data. Pereyra et al. (2017) actually show that penalising the
entropy in a supervised context acts as a strong regulator for supervised
model and improves on the state-of-the-art on common benchmarks. This comforts
us in the idea of debiasing using labelled data in the case of entropy-
minimisation.

Our objective also resembles doubly-robust risk estimates used for SSL in the
context of kernel machines by Liu and Goldberg (2020) and for deep learning in
a recent preprint (Hu et al., 2022a). In both cases, their focus is quite
different, as they consider weaker conditions than MCAR, but very specific
choices of $H$.

###  3.2 Is $\hat{\mathcal{R}}_{DeSSL}(\theta)$ an accurate risk estimate?

Because of the connections between our debiased estimate and variance
reduction techniques, we have a natural interest in the variance of the
estimate. Having a lower-variance estimate of the risk would mean estimating
it more accurately, leading to better models.

Similarly to traditional control variates (Owen, 2013), the variance can in
fact be computed, and optimised in $\lambda$:

###### Theorem 1

The function $\lambda\mapsto\mathbb{V}(\hat{\mathcal{R}}_{DeSSL}(\theta))$
reaches its minimum for:

$\lambda_{opt}=\frac{n_{u}}{n}\frac{\mathrm{Cov}(L(\theta;x,y),H(\theta;x))}{\mathbb{V}(H(\theta;x))},$
(9)

and at $\lambda_{opt}$:

$\begin{split}\small\mathbb{V}(\hat{\mathcal{R}}_{DeSSL}(\theta))|_{\lambda_{opt}}&=\left(1-\frac{n_{u}}{n}\rho_{L,H}^{2}\right)\mathbb{V}(\hat{\mathcal{R}}_{CC}(\theta))\\\
&\leq\mathbb{V}(\hat{\mathcal{R}}_{CC}(\theta)),\end{split}$ (10)

where $\rho_{L,H}=\mathrm{Corr}(L(\theta;x,y),H(\theta;x))$.

A proof of this theorem is available as Appendix D. This theorem provides a
formal justification to the heuristic idea that $H$ should be a surrogate of
$L$. Indeed, DeSSL is a more accurate risk estimate when $H$ is strongly
positively correlated with $L$, which is likely to be the case when $H$ is
equal or equivalent to an expectation of $L$.

A natural application of this theorem would be to tune $\lambda$ automatically
by estimating $\lambda_{opt}$. Again, this is common practice when dealing
with control variates. In our case however, this is a rather difficult task,
since the covariance $\mathrm{Cov}(L(\theta;x,y),H(\theta;x))$ is hard to
estimate with few labels. In practice, using simple esti- mates of
$\lambda_{opt}$ was extremely unstable, and led to un- satisfactory results.
The theorem still has a _quantitative_ merit when it comes to choosing
$\lambda$, by telling that the sign of $\lambda$ is positive when $H$ and $L$
are positively correlated which will generally be the case with the examples
mentioned above. We give in Appendix D a proof that $L$ and $H$ are positively
correlated when $L$ is the negative likelihood and $H$ is the entropy.
Furthermore, with the form of $H$ given in the equation (4), it is intuitive
to think that $L$ and $H$ are positively correlated. Therefore, a positive
$\lambda$ is a natural choice. Also, it is natural to think that unlabelled
data points should not have individually more weight ($\frac{\lambda}{n_{u}}$)
than labelled data points ($\frac{1}{n_{l}}$) in the risk estimate. To do so,
$\lambda$ should remain lower than $\frac{n_{u}}{n_{l}}$. Other SSL methods
have variance reduction guarantees and already has shown great promises in
SSL, see Sakai et al. (2017). In a purely supervised context, Chen et al.
(2020) show that the effectiveness of data augmentation techniques lays
partially on the variance reduction of the risk estimate.

###  3.3 Calibration

The calibration of a model is its capacity of predicting probability estimates
that are representative of the true distribution. This property is determinant
in real-world application when we need reliable predictions. In this section
we first introduce scoring rules and their relationship to well-calibrated
models.

A scoring rule $\mathcal{S}$ is a function assigning a score to the predictive
distribution $p_{\theta}(y|x)$ relative to the event $y|x\sim p(y|x)$,
$\mathcal{S}(p_{\theta},(x,y))$, where $p(x,y)$ is the true distribution (see
e.g. Gneiting and Raftery, 2007). A scoring rule measures both the accuracy
and the quality of predictive uncertainty, meaning that better calibration is
rewarded. The expected scoring rule is defined as
$\mathcal{S}(p_{\theta},p)=\mathbb{E}_{p}[\mathcal{S}(p_{\theta},(x,y))]$. A
proper scoring rule is defined as a scoring rule such that
$\mathcal{S}(p_{\theta},p)\leq\mathcal{S}(p,p)$ (Gneiting and Raftery, 2007).

The motivation behind having proper scoring rules comes from the following:
suppose that the true data distribution $p$ is accessible by our set of
models. Then, the scoring rule encourages to predict $p_{\theta}=p$. The
opposite of a proper scoring rule can then be used to train a model to
encourage the calibration of predictive uncertainty:
$L(\theta;x,y)=-\mathcal{S}(p_{\theta},(x,y))$. Most common losses used to
train models are proper scorings rule such as log-likelihood.

###### Theorem 2

If $\mathcal{S}(p_{\theta},(x,y))=-L(\theta;x,y)$ is a proper scoring rule,
then
$\mathcal{S}^{\prime}(p_{\theta},(x,y,r))=-(\frac{rn}{n_{l}}L(\theta;x,y)+\lambda
n(\frac{1-r}{n_{u}}-\frac{r}{n_{l}})H(\theta;x))$ is also a proper scoring
rule.

The proof is available in Appendix E, and follows direclty from unbiasedness
and the MCAR assumption. The main interpretation of this theorem is that we
can expect DeSSL to be as well-calibrated as the complete case.

###  3.4 Consistency

We say that $\hat{\theta}$ is consistent if
$d(\hat{\theta},\theta^{*})\xrightarrow{p}0$ when $n\xrightarrow{}\infty$,
where $d$ is a distance on $\Theta$. The asymptotic properties of
$\hat{\theta}$ depend on the behaviours of the functions $L$ and $H$. We will
thus require the following standard assumptions.

###### Assumption 3

The minimum $\theta^{*}$ of $\mathcal{R}$ is well-separated:

$\inf_{\theta:d(\theta^{*},\theta)\geq\epsilon}\mathcal{R}(\theta)>\mathcal{R}(\theta^{*}).$
(11)

###### Assumption 4

The uniform weak law of large number holds for a function $L$ if:

$\sup_{\theta\in\Theta}\left|\frac{1}{n}\sum_{i=1}^{n}L(\theta,x_{i},y_{i})-\mathbb{E}[L(\theta,x,y)]\right|\xrightarrow{p}0.$
(12)

We assume that the uniform weak law of large number holds for both $L$ and
$H$.

###### Theorem 5

Under the MCAR assumption, Assumption 11 and Assumption 4,
$\hat{\theta}=\operatorname*{arg\,min}\hat{\mathcal{R}}_{DeSSL}$ is
consistent.

For a proof of this theorem see Appendix E. This theorem is a simple
application of van der Vaart’s (2000) Theorem 5.7 proving the consistency of a
M-estimator. Also, this results holds for the complete case, with $\lambda=0$
which prove that the complete case is a solid baseline under the MCAR
assumption.

##### Coupling of $n_{l}$ and $n_{u}$ under the MCAR assumption

Under the MCAR assumption, $n_{l}$ and $n_{u}$ are random variables. We have
that $r\sim\mathcal{B}(\pi)$ (i.e. any $x$ has the probability $\pi$ of being
labelled). Then, with $n$ growing to infinity, we have
$\frac{n_{l}}{n}=\frac{n_{l}}{n_{l}+n_{u}}\xrightarrow{}\pi$. Therefore, both
$n_{l}$ and $n_{u}$ grow to infinity and
$\frac{n_{l}}{n_{u}}\xrightarrow{}\frac{\pi-1}{\pi}$. This implies
$n_{u}=\mathcal{O}(n_{l})$ and then when $n$ goes to infinity, both $n_{u}$
and $n_{l}$ go to infinity too and even if $n_{u}>>n_{l}$.

###  3.5 Rademacher complexity and generalisation bounds

In this section, we prove an upper bound for the generalisation error of
DeSSL. The unbiasedness of $\hat{\mathcal{R}}_{DeSSL}$ can directly be used to
derive generalisation bounds based on the Rademacher complexity (Bartlett and
Mendelson, 2002), defined in our case as

where $\varepsilon_{i}$ are i.i.d. Rademacher variables independent of the
data. In the particular case of $\lambda=0$, we recover the standard
Rademacher complexity of the complete case.

We can then now bound the generalisation error of a model trained using our
new loss function.

###### Theorem 6

We assume that labels are MCAR and that both $L$ and $H$ are bounded. Then,
there exists a constant $\kappa>0$, that depends on $\lambda$, $L$, $H$, and
the ratio of observed labels, such that, with probability at least $1-\delta$,
for all $\theta\in\Theta$,

$\mathcal{R}(\theta)\leq\hat{\mathcal{R}}_{DeSSL}(\theta)+2R_{n}+\kappa\sqrt{\frac{\log(4/\delta)}{n}}.$
(13)

The proof follows Shalev-Shwartz and Ben-David (2014, Chapter 26), and is
available in Appendix G.

##  4 Experiments

We evaluate the performance of DeSSL against different classic methods. In the
experiments, our goal is not to produce state-of-the-art results, but instead
to compare DeSSL methods and their orginal counterparts. In particular, we
perform experiments with simple SSL methods such as pseudo-label (PseudoLabel)
and entropy minimisation (EntMIN) with varying $\lambda$ on MNIST (LeCun and
Cortes, 2010) and CIFAR-10 (Krizhevsky, 2009) and compare them to the debiased
method, respectively DeEntMin and DePseudoLabel. For a more challenging
version of MNIST, we decide to add $20\%$ label noise in order to break the
cluster assumption. We also compare PseudoLabel and DePseudoLabel on five
small datasets of MedMNIST (Yang et al., 2021a, b) with a fixed $\lambda$. The
results of these experiments are reported below. In our figures, the error
bars represent the size of the 95% confidence interval (CI).

In addition, we also compare DeEntMin and DePseudoLabel to the biased version
on a large range of tabular datasets commonly used in SSL benchmarks (Chapelle
et al., 2006; Guo et al., 2010). We do not observe differences between the
performance, see Appendix L. Finally, we show how simple it is to debias an
existing implementation, by demonstrating it on the consistency-based models
benchmarked by (Oliver et al., 2018), namely VAT, $\Pi$-model and MeanTeacher.
We observe similar performances between the debiased and biased version for
the different methods, both in terms of loss and accuracy. Moreover, these
results have been obtained using the hyperparameters finetuned for the biased
versions. Therefore, it is likely that optimising the hyperparameters for
DeSSL will yield even better with the right hyperparameters, see Appendix K.

###  4.1 MNIST

MNIST is an advantageous dataset for SSL as the cluster assumption holds. We
compare PseudoLabel and DePseudoLabel for a LeNet-like architecture using
$n_{l}=1000$ labelled data on 10 different splits of the training dataset into
a labelled and unlabelled set. Models are then evaluated using the standard
$10,000$ test samples. We used 10% of $n_{l}$ as the validation set. We test
the influence of the hyperparameter $\lambda$ and report the accuracy, the
loss and the expected calibration error (ECE, Guo et al., 2017) at the epoch
of best validation accuracy, see Figure 2 and Appendix I.

Figure 2: The influence of $\lambda$ on Pseudo-label and DePseudo-label for a
Lenet trained on MNIST with $n_{l}=1000$: (Left) Mean test accuracy; (Right)
Mean test loss, with 95% CI.

In this exemple SSL and DeSSL have the almost the same accuracy for all
$\lambda$, however, DeSSL seems to be alway better calibrated. In order to
break the cluster assumption, we reproduced the same experiment on a modified
MNIST. Indeed, we had label noise by replacing the true label for 20% of the
dataset by a randomly sampled label, see Figure 3. In this setting, DeSSL
performs better for large $\lambda$ in term of accuracy and also provides a
better calibration.

Figure 3: The influence of $\lambda$ on Pseudo-label and DePseudo-label for a
Lenet trained on MNIST with label noise with $n_{l}=1000$: (Left) Mean test
accuracy; (Right) Mean test loss, with 95% CI.

###  4.2 MedMNIST

We compare PseudoLabel and DePseudoLabel on different datasets of MedMNIST, a
large-scale MNIST-like collection of biomedical images. We selected the five
smallest 2D datasets of the collection, for these dataset it is likely that
the cluster assumption no longer holds. We trained a 5-layer CNN with a fixed
$\lambda=1$ and $n_{l}$ at 10% of the training data. We report in Table 1 the
mean accuracy on 5 different split of the labelled and unlabelled data and the
number of labelled data used. The mean loss is reported in Table 2. We report
the AUC in Appendix I.

Table 1: Test accuracy of Complete Case , PseudoLabel and DePseudoLabel on five datasets of MedMNIST. Dataset | $n_{l}$ | CC | PL | DePL
---|---|---|---|---
Derma | 1000 |  68.99$\pm$ 1.20 |  68.88$\pm$ 1.03 | 69.30$\pm$ 0.85
Pneumonia | 585 |  83.94$\pm$ 2.40 | 85.83$\pm$ 2.13 |  84.36 $\pm$ 3.79
Retina | 160 |  48.30$\pm$ 3.06 |  47.75$\pm$ 2.50 | 49.40 $\pm$ 2.62
Breast | 78 |  76.15$\pm$ 0.75 |  74.74$\pm$ 1.04 | 76.67 $\pm$ 1.32
Blood | 1700 | 84.13$\pm$ 0.83 |  84.09$\pm$ 1.17 |  83.68 $\pm$ 0.59
Table 2: Test loss of Complete Case (CC), PseudoLabel (PL) and DePseudoLabel (DePL) on five datasets of MedMNIST. Dataset | CC | PL | DePL
---|---|---|---
Derma |  1.95 $\pm$ 0.09 |  2.51 $\pm$ 0.20 | 1.88 $\pm$ 0.12
Pneumonia |  1.47 $\pm$ 0.04 |  2.04 $\pm$ 0.04 | 1.40 $\pm$ 0.06
Retina |  1.68 $\pm$ 0.03 |  1.80 $\pm$ 0.18 | 1.67 $\pm$ 0.06
Breast |  0.80 $\pm$ 0.04 |  1.00 $\pm$ 0.26 | 0.70 $\pm$ 0.03
Blood |  6.11 $\pm$ 0.17 |  6.61 $\pm$ 0.22 |  6.53 $\pm$ 0.30

DePseudoLabel compete with PseudoLabel in terms of accuracy and even success
when PseudoLabel’s accuracy is less than the complete case. Moreover,
DePseudoLabel is always better in term of loss, so calibration, whereas
PseudoLabel is always worse than the complete case.

###  4.3 CIFAR

We compare PseudoLabel and DePseudoLabel on CIFAR-10. We trained a CNN-13 from
Tarvainen and Valpola (2017) on 5 different splits of the training dataset
into a labelled and unlabelled set. For this experiement, we use $n_{l}=4000$
and use the rest of the dataset as unlabelled. Models are then evaluated using
the standard $10,000$ test samples. For a more realistic validation set, we
used 10% of $n_{l}$ as the validation set. We test the influence of the
hyperparameter $\lambda$ and report the accuracy and the loss at the epoch of
best validation accuracy, see Figure 4. We report the ECE in Appendix J.

Figure 4: The influence of $\lambda$ on Pseudo-label and DePseudo-label for a
CNN trained on CIFAR with $n_{l}=4000$: (Left) Mean test accuracy; (Right)
Mean test loss, with 95% CI.

We observe DeSSL provides both a better loss and ECE with the same accuracy
for small $\lambda$. For larger $\lambda$, DeSSL performs better in all the
reported metrics. We performed a paired Student’s t-test to ensure that our
results are significant and reported the p-values in Appendix J. The p-values
indicates that for $\lambda$ close to 10, DeSSL is often significantly better
in all the metrics. Moreover, DeSSL for large $\lambda$ provides a better loss
and ECE than the complete case whereas SSL never does.

##  5 Conclusion

Motivated by the remarks of van Engelen and Hoos (2020) and Oliver et al.
(2018) on the missingness of theoretical guarantees about the use of
unlabelled data in SSL, we proposed a simple modification of SSL frameworks.
We consider frameworks based on the inclusion of unlabelled data in the
computation of the risk estimator and debias them using labelled data. We show
theoretically that this debiasing comes with several theoretical guarantees.
We demonstrate these theoretical results experimentally on several common SSL
datasets and some more challenging ones such as MNIST with label noise. DeSSL
shows competitive performance in term of accuracy compared to its biased
version but improves significantly the calibration. Moreover, we attest that
the modification of the existing SSL methods to make them unbiased is simple.
There are several future directions open to us. First, there should be
continued investigation of state-of-the-art methods such as Sohn et al. (2020)
and Rizve et al. (2021) to debias them and make them safe. We showed that
$\lambda_{opt}$ exists (Theorem 1) and therefore our formula provides
guidelines for the optimisation of $\lambda$. Finally, an interesting
improvement would be to go beyond the MCAR assumption by considering settings
with a distribution mismatch between labelled and unlabelled data (Guo et al.,
2020; Cao et al., 2021; Hu et al., 2022b).

## Acknowledgements

This work has been supported by the French government, through the 3IA Côte
d’Azur Investments in the Future project managed by the National Research
Agency (ANR) with the reference number ANR-19-P3IA-0002.

## References

  * Ahfock and McLachlan (2019) Daniel Ahfock and Geoffrey J McLachlan.  On missing label patterns in semi-supervised learning.  _arXiv preprint arXiv:1904.02883_ , 2019.
  * Bartlett and Mendelson (2002) Peter L Bartlett and Shahar Mendelson.  Rademacher and Gaussian complexities: Risk bounds and structural results.  _Journal of Machine Learning Research_ , 3(Nov):463–482, 2002.
  * Berthelot et al. (2019) David Berthelot, Nicholas Carlini, Ian Goodfellow, Nicolas Papernot, Avital Oliver, and Colin A Raffel.  Mixmatch: A holistic approach to semi-supervised learning.  _Advances in Neural Information Processing Systems_ , 2019.
  * Berthelot et al. (2020) David Berthelot, Nicholas Carlini, Ekin D. Cubuk, Alex Kurakin, Kihyuk Sohn, Han Zhang, and Colin Raffel.  ReMixMatch: Semi-supervised learning with distribution matching and augmentation anchoring.  _International conference on Learning Representations_ , 2020.
  * Cao et al. (2021) Kaidi Cao, Maria Brbic, and Jure Leskovec.  Open-world semi-supervised learning, 2021.
  * Chapelle et al. (2006) Olivier Chapelle, Bernhard Scholkopf, and Alexander Zien.  Semi-supervised learning.  _MIT Press_ , 2006.
  * Chen et al. (2020) Shuxiao Chen, Edgar Dobriban, and Jane H Lee.  A group-theoretic framework for data augmentation.  _Journal of Machine Learning Research_ , 21(245):1–71, 2020.
  * Defazio et al. (2014) Aaron Defazio, Francis Bach, and Simon Lacoste-Julien.  SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives.  _Advances in Neural Information Processing Systems_ , 2014.
  * Gan et al. (2017) Haitao Gan, Zhenhua Li, Yingle Fan, and Zhizeng Luo.  Dual learning-based safe semi-supervised learning.  _IEEE Access_ , 6:2615–2621, 2017.
  * Gneiting and Raftery (2007) Tilmann Gneiting and Adrian E Raftery.  Strictly proper scoring rules, prediction, and estimation.  _Journal of the American statistical Association_ , 102(477):359–378, 2007.
  * Goodfellow et al. (2014) Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial nets.  _Advances in Neural Information Processing Systems_ , 2014.
  * Goodfellow et al. (2016) Ian Goodfellow, Yoshua Bengio, and Aaron Courville.  _Deep Learning_.  MIT Press, 2016.
  * Grandvalet and Bengio (2004) Yves Grandvalet and Yoshua Bengio.  Semi-supervised learning by entropy minimization.  _Advances in Neural Information Processing Systems_ , 2004.
  * Guo et al. (2017) Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger.  On calibration of modern neural networks.  _International Conference on Machine Learning_ , 2017.
  * Guo et al. (2020) Lan-Zhe Guo, Zhen-Yu Zhang, Yuan Jiang, Yu-Feng Li, and Zhi-Hua Zhou.  Safe deep semi-supervised learning for unseen-class unlabeled data.  _International Conference on Machine Learning_ , 2020.
  * Guo et al. (2010) Yuanyuan Guo, Xiaoda Niu, and Harry Zhang.  An extensive empirical study on semi-supervised learning.  _IEEE International Conference on Data Mining_ , 2010.
  * Hestness et al. (2017) Joel Hestness, Sharan Narang, Newsha Ardalani, Gregory F. Diamos, Heewoo Jun, Hassan Kianinejad, Md. Mostofa Ali Patwary, Yang Yang, and Yanqi Zhou.  Deep learning scaling is predictable, empirically.  _CoRR_ , 2017.
  * Hu et al. (2022a) Xinting Hu, Yulei Niu, Chunyan Miao, Xian-Sheng Hua, and Hanwang Zhang.  On non-random missing labels in semi-supervised learning.  _International Conference on Learning Representations_ , 2022a.
  * Hu et al. (2022b) Xinting Hu, Yulei Niu, Chunyan Miao, Xian-Sheng Hua, and Hanwang Zhang.  On non-random missing labels in semi-supervised learning.  In _International Conference on Learning Representations_ , 2022b.
  * Ji et al. (2012) Ming Ji, Tianbao Yang, Binbin Lin, Rong Jin, and Jiawei Han.  A simple algorithm for semi-supervised learning with improved generalization error bound.  _International Conference on Machine Learning_ , 2012.
  * Johnson and Zhang (2013) Rie Johnson and Tong Zhang.  Accelerating stochastic gradient descent using predictive variance reduction.  _Advances in Neural Information Processing Systems_ , 2013.
  * Kawakita and Takeuchi (2014) Masanori Kawakita and Jun’ichi Takeuchi.  Safe semi-supervised learning based on weighted likelihood.  _Neural Networks_ , 53:146–164, 2014.
  * Kingma et al. (2014) Diederik P Kingma, Shakir Mohamed, Danilo Jimenez Rezende, and Max Welling.  Semi-supervised learning with deep generative models.  In _Advances in Neural Information Processing Systems_ , pages 3581–3589, 2014.
  * Krizhevsky (2009) Alex Krizhevsky.  Learning multiple layers of features from tiny images.  Technical report, MIT, NYU, 2009.
  * Laine and Aila (2017) Samuli Laine and Timo Aila.  Temporal ensembling for semi-supervised learning.  _International Conference on Learning Representations_ , 2017.
  * LeCun and Cortes (2010) Yann LeCun and Corinna Cortes.  MNIST handwritten digit database.  2010\.  URL http://yann.lecun.com/exdb/mnist/.
  * Lee (2013) Dong-Hyun Lee.  Pseudo-Label : The simple and efficient semi-supervised learning method for deep neural networks.  _Workshop on challenges in representation learning, International conference on machine learning_ , 2013.
  * Li and Zhou (2014) Yu-Feng Li and Zhi-Hua Zhou.  Towards making unlabeled data never hurt.  _IEEE transactions on pattern analysis and machine intelligence_ , 37:175–188, 2014.
  * Li et al. (2016) Yu-Feng Li, James T Kwok, and Zhi-Hua Zhou.  Towards safe semi-supervised learning for multivariate performance measures.  _AAAI Conference on Artificial Intelligence_ , 2016.
  * Little and Rubin (2019) Roderick JA Little and Donald B Rubin.  _Statistical Analysis with Missing Data_.  John Wiley & Sons, 2019.
  * Liu and Goldberg (2020) Tiantian Liu and Yair Goldberg.  Kernel machines with missing responses.  _Electronic Journal of Statistics_ , 14:3766–3820, 2020\.
  * McLachlan (1977) Geoffrey John McLachlan.  Estimating the linear discriminant function from initial samples containing a small number of unclassified observations.  _Journal of the American statistical association_ , 72:403–406, 1977.
  * Miyato et al. (2018) Takeru Miyato, Shin-ichi Maeda, Masanori Koyama, and Shin Ishii.  Virtual adversarial training: A regularization method for supervised and semi-supervised learning.  _IEEE transactions on pattern analysis and machine intelligence_ , 41:1979–1993, 2018.
  * Newey and McFadden (1994) Whitney K Newey and Daniel McFadden.  Large sample estimation and hypothesis testing.  _Handbook of econometrics_ , 4:2111–2245, 1994.
  * Oliver et al. (2018) Avital Oliver, Augustus Odena, Colin Raffel, Ekin D Cubuk, and Ian J Goodfellow.  Realistic evaluation of deep semi-supervised learning algorithms.  _Advances in Neural Information Processing Systems_ , 2018.
  * Owen (2013) Art B. Owen.  _Monte Carlo theory, methods and examples_.  2013\.
  * Pereyra et al. (2017) Gabriel Pereyra, George Tucker, Jan Chorowski, Łukasz Kaiser, and Geoffrey Hinton.  Regularizing neural networks by penalizing confident output distributions.  _Workshop track, International Conference on Learning Representations_ , 2017.
  * Pham et al. (2021) Hieu Pham, Zihang Dai, Qizhe Xie, and Quoc V Le.  Meta pseudo labels.  _Conference on Computer Vision and Pattern Recognition_ , 2021.
  * Rizve et al. (2021) Mamshad Nayeem Rizve, Kevin Duarte, Yogesh S Rawat, and Mubarak Shah.  In Defense of Pseudo-Labeling: An Uncertainty-Aware Pseudo-label Selection Framework for Semi-Supervised Learning.  _International Conference on Learning Representations_ , 2021.
  * Sajjadi et al. (2016) Mehdi Sajjadi, Mehran Javanmardi, and Tolga Tasdizen.  Regularization with stochastic transformations and perturbations for deep semi-supervised learning.  _Advances in Neural Information Processing Systems_ , 2016.
  * Sakai et al. (2017) Tomoya Sakai, Marthinus Christoffel Plessis, Gang Niu, and Masashi Sugiyama.  Semi-supervised classification based on classification from positive and unlabeled data.  _International conference on machine learning_ , 2017.
  * Schölkopf et al. (2012) Bernhard Schölkopf, Dominik Janzing, Jonas Peters, Eleni Sgouritsa, Kun Zhang, and Joris Mooij.  On causal and anticausal learning.  _Internation conference on machine learning_ , 2012.
  * Scudder (1965) Henry Scudder.  Probability of error of some adaptive pattern-recognition machines.  _IEEE Transactions on Information Theory_ , 11:363–371, 1965.
  * Seeger (2000) Matthias Seeger.  Learning with labeled and unlabeled data.  _Technical report_ , 2000.
  * Shalev-Shwartz and Ben-David (2014) Shai Shalev-Shwartz and Shai Ben-David.  _Understanding Machine Learning: From Theory to Algorithms_.  Cambridge university press, 2014.
  * Singh et al. (2008) Aarti Singh, Robert Nowak, and Jerry Zhu.  Unlabeled data: Now it helps, now it doesn’t.  _Advances in Neural Information Processing Systems_ , 2008.
  * Sohn et al. (2020) Kihyuk Sohn, David Berthelot, Chun-Liang Li, Zizhao Zhang, Nicholas Carlini, Ekin D Cubuk, Alex Kurakin, Han Zhang, and Colin Raffel.  FixMatch: Simplifying semi-supervised learning with consistency and confidence.  _Avances in Neural Information Processing Systems_ , 2020.
  * Sokolovska et al. (2008) Nataliya Sokolovska, Olivier Cappé, and François Yvon.  The asymptotics of semi-supervised learning in discriminative probabilistic models.  In _International Conference on Machine Learning_ , 2008.
  * Tarvainen and Valpola (2017) Antti Tarvainen and Harri Valpola.  Mean teachers are better role models: Weight-averaged consistency targets improve semi-supervised deep learning results.  _Advancer in Neural Information Processing Systems_ , 2017.
  * Trapp et al. (2017) Martin Trapp, Tamas Madl, Robert Peharz, Franz Pernkopf, and Robert Trappl.  Safe semi-supervised learning of sum-product networks.  _Conference on Uncertainty in Artificial Intelligence_ , 2017.
  * Tsiatis (2006) Anastasios A Tsiatis.  _Semiparametric theory and missing data_.  Springer, 2006.
  * Tsuchiya et al. (2021) Taira Tsuchiya, Nontawat Charoenphakdee, Issei Sato, and Masashi Sugiyama.  Semisupervised ordinal regression based on empirical risk minimization.  _Neural Computation_ , 33:3361–3412, 2021.
  * van der Vaart (2000) Aad W van der Vaart.  _Asymptotic statistics_.  Cambridge university press, 2000.
  * van Engelen and Hoos (2020) Jesper E van Engelen and Holger H Hoos.  A survey on semi-supervised learning.  _Machine Learning_ , 109:373–440, 2020.
  * Verma et al. (2019) Vikas Verma, Kenji Kawaguchi, Alex Lamb, Juho Kannala, Yoshua Bengio, and David Lopez-Paz.  Interpolation consistency training for semi-supervised learning.  _International Joint Conference on Artificial Intelligence_ , 2019\.
  * Xie et al. (2019) Qizhe Xie, Zihang Dai, Eduard Hovy, Minh-Thang Luong, and Quoc V Le.  Unsupervised data augmentation for consistency training.  _Advances in Neural Information Processing Systems_ , 2019.
  * Yang et al. (2021a) Jiancheng Yang, Rui Shi, and Bingbing Ni.  MedMNIST classification decathlon: A lightweight AutoML benchmark for medical image analysis.  In _IEEE 18th International Symposium on Biomedical Imaging (ISBI)_ , pages 191–195, 2021a.
  * Yang et al. (2021b) Jiancheng Yang, Rui Shi, Donglai Wei, Zequan Liu, Lin Zhao, Bilian Ke, Hanspeter Pfister, and Bingbing Ni.  MedMNIST v2: A large-scale lightweight benchmark for 2D and 3D biomedical image classification.  _arXiv preprint arXiv:2110.14795_ , 2021b.
  * Zhang et al. (2021) Bowen Zhang, Yidong Wang, Wenxin Hou, Hao Wu, Jindong Wang, Manabu Okumura, and Takahiro Shinozaki.  FlexMatch: Boosting semi-supervised learning with curriculum pseudo labeling.  _Advances in Neural Information Processing Systems_ , 2021.
  * Zhang et al. (2017) Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz.  mixup: Beyond empirical risk minimization.  _Internation Conference on Learning Representations_ , 2017.
  * Zhu et al. (2003) Xiaojin Zhu, Zoubin Ghahramani, and John D Lafferty.  Semi-supervised learning using Gaussian fields and harmonic functions.  _International conference on machine learning_ , 2003.
  * Zhu et al. (2022) Zhaowei Zhu, Tianyi Luo, and Yang Liu.  The rich get richer: Disparate impact of semi-supervised learning.  In _International Conference on Learning Representations_ , 2022.

##  A Toy example

We trained a 4 layer neural network (1/20/100/20/1) with ReLU activation
function using $25,000$ labelled and $25,000$ unlabelled points draw from two
1D uniform laws with an overlap. We used $\lambda=1$ and a confidence
threshold for Pseudo-label $\tau=0.70$. We optimised the model’s weights using
a stochastic gradient descent (SGD) optimiser with a learning rate of $0.1$.

Figure 5: Data histogram

Figure 6: 4 layer neural net trained using SSL methods on a 1D dataset drawn
from two uniform laws. (Top-left) Posterior probabilities $p(1|x)$ of the same
model trained following either complete case (only labelled data), Pseudo-
label or our DePseudo-label. (Top-right) Same for EntMin and DeEntMin (Bottom-
left) Training losses for Pseudo-label and DePseudo-label (Bottom-right) Same
for EntMin and DeEntMin

##  B Details on surrogates and more examples

###  B.1 Entropy-based

##### Pseudo-label:

As presented in the core article, the unsupervised objective of pseudo-label
can be written as an expectation of $L$ on the distribution
$\pi_{x}(\tilde{x},\tilde{y})=\delta_{x}(\tilde{x})p_{\theta}(\tilde{y}|\tilde{x})$.
Recently, Lee (2013) encouraged the pseudo-labels method for deep semi-
supervised learning. Then, Rizve et al. (2021) recently improved the pseudo-
label selection by introducing an uncertainty-aware mechanism on the
confidence of the model concerning the predicted probabilities. Pham et al.
(2021) reaches state-of-the-art on the Imagenet challenge using pseudo-labels
on a large dataset of additional images.

###  B.2 Pseudo-label and data augmentation

Recently, several methods based on data-augmentation have been proposed and
proven to perform well on a large spectrum of SSL tasks. The idea is to have a
model resilient to strong data-augmentation of the input (Berthelot et al.,
2019, 2020; Sohn et al., 2020; Xie et al., 2019; Zhang et al., 2021). These
method rely both on the cluster assumption and the smoothness assumption and
are at the border between entropy-based and consistency-based methods. The
idea is to have same prediction for an input and a augmented version of it.
For instance, in Sohn et al. (2020), we first compute pseudo-labels predicted
using a weakly-augmented version of $x$ (flip-and-shift data augmentation) and
then minimise the likelihood with the predictions of the model on a strongly
augmented version of $x$. In Xie et al. (2019), the method is a little bit
different as we minimise the cross entropy between the prediction of the model
on $x$ and the predictions of a augmented version. In both case, the
unsupervised part of the risk estimator can be reformulated as Equation 4.

##### Fixmatch:

In Fixmatch, Sohn et al. (2020), the unsupervised objective can be written as:

$\displaystyle
H(\theta;x)=\mathbb{1}[\max_{y}p_{\hat{\theta}}(y|x_{1})>\tau]L(\theta;x_{2},\operatorname*{arg\,max}_{y}p_{\hat{\theta}}(y|x_{1}))$
(14)

where $\hat{\theta}$ is a fixed copy of the current parameters $\theta$
indicating that the gradient is not propagated through it, $x_{1}$ is a
weakly-augmented version of $x$ and $x_{2}$ a strongly-augmented one.
Therefore, we write $H$ as an expectation of $L$ on the distribution
$\pi_{x}(\tilde{x},\tilde{y})=\delta_{x_{2}}(\tilde{x})\delta_{\operatorname*{arg\,max}_{y}p_{\hat{\theta}}(y|x_{1})}(\tilde{y})\mathbb{1}[\max_{y}p_{\hat{\theta}}(y|x_{1})>\tau]$.

##### UDA:

In UDA, Xie et al. (2019), the unsupervised objective can be written as:

$\displaystyle H(\theta;x)=\sum_{y}p_{\hat{\theta}}(y|x)L(\theta;x_{1},y)$
(15)

where $\hat{\theta}$ is a fixed copy of the current parameters $\theta$
indicating that the gradient is not propagated through it and $x_{1}$ is an
augmented version of $x$. Therefore, we write $H$ as an expectation of $L$ on
the distribution
$\pi_{x}(\tilde{x},\tilde{y})=\delta_{x_{1}}(\tilde{x})p_{\hat{\theta}}(\tilde{y}|\tilde{x})$.

##### Other:

Recently, have been proposed in the literature Zhang et al. (2021) and Rizve
et al. (2021). The former is an improved verion of Fixmatch with a variable
threshold $\tau$ with respect to the class and the training stage. The latter
introduces a measurement of uncertainty in the pseudo-labelling step to
improve the selection. They also introduce negative pseudo-labels to improve
the single-label classification.

###  B.3 VAT

The virtual adversarial training method proposed by (Miyato et al., 2018)
generates the most impactful perturbation $r_{\textit{adv}}$ to add to $x$.
The objective is to train a model robust to input perturbations. This method
is closely related to adversarial training introduced by Goodfellow et al.
(2014).

$\displaystyle
H(\theta;x)=\textbf{Div}(f_{\hat{\theta}}(x,.),f_{\theta}(x+r_{\textit{adv}},.))$

where the Div is a non-negative function that measures the divergence between
two distributions, the cross-entropy or the KL divergence for instance. If the
divergence function is the cross-entropy, it is straightforward to write the
unlabelled objective as Equation 4. If the objective function is the KL
divergence, we can write the objective as

$H(\theta;x)=\mathbb{E}_{\pi_{x}(\tilde{x}+r,\tilde{y})}[L(\theta;\tilde{x},\tilde{y})]-\mathbb{E}_{\pi_{x}(\tilde{x},\tilde{y})}[L(\hat{\theta};\tilde{x},\tilde{y})]$
(16)

with
$\pi_{x}(\tilde{x},\tilde{y})=\delta_{x}(\tilde{x})p_{\hat{\theta}}(y|x)$.
Therefore, variation of $H$ with respect to $\theta$ are the same as
$\mathbb{E}_{\pi_{x}(\tilde{x}+r,\tilde{y})}[L(\theta;\tilde{x},\tilde{y})]$.
VAT is also a method between consistency-based and entropy-based method as
long as we use the KL-divergence or the cross-entropy as the measure of
divergence.

###  B.4 Consitency-based

Consistency-based method aim to smooth the decision function of the models or
have more stable predictions. These objectives $H$ are not directly a form of
expectation of $L$ but are equivalent to an expectation of $L$. For all the
following methods we are able to write the unsupervised objective $H$ such
that:

$C_{1}\mathbb{E}_{\pi_{x}(\tilde{x},\tilde{y})}[L(\theta;\tilde{x},\tilde{y})]\leq
H(\theta;x)\leq
C_{2}\mathbb{E}_{\pi_{x}(\tilde{x},\tilde{y})}[L(\theta;\tilde{x},\tilde{y})],$
(17)

with $0\leq C_{1}\leq C_{2}$.

Indeed, consistency-based method minimise an unsupervised objective that is a
divergence between the model predictions and a modified version of the input
(data augmentation) or a perturbation of the model. Using the fact that all
norms are equivalent in a finite dimensional space such as the space of the
labels, we have the equivalence between a consistency-based $H$ and an
expectation of $L$.

##### Mean-Teacher

A different form of pseudo-labelling is the Mean-Teacher approach proposed by
(Tarvainen and Valpola, 2017) where pseudo-labels are generated by a teacher
model for a student model. The parameters of the student model are updated,
while the teacher’s are a moving average of the student’s parameters from the
previous training steps. The idea is to have a more stable pseudo-labelling
using the teacher than in the classic Pseudo-label. Final predictions are made
by the student model. A generic form of the unsupervised part of the risk
estimator is then

$\displaystyle
H(\theta;x)=\sum_{y}(p_{\theta}(y|x)-p_{\hat{\theta}}(y|x))^{2},$

where $\hat{\theta}$ are the fixed parameters of the teacher.

#####  $\Pi$-Model

The $\Pi$-Models are intrinsically stochastic models (for example a model with
dropout) encouraged to make consistent prediction through several passes of
the same $x$ in the model. The SSL loss is using the stochastic behavior of
the model where the model $f_{\theta}$ and penalises different predictions for
the same $x$ (Sajjadi et al., 2016). Let’s note $f_{\theta}(x,.)_{1}$ and
$f_{\theta}(x,.)_{2}$ two passes of $x$ through the model $f_{\theta}$. A
generic form of the unsupervised part of the risk estimator is then

$\displaystyle
H(\theta;x)=\textbf{Div}(f_{\theta}(x,.)_{1},f_{\hat{\theta}}(x,.)_{2}),$ (18)

where Div is a measure of divergence between two distributions (often the
Kullback-Leibler divergence).

##### Temporal ensembling

Temporal ensembling (Laine and Aila, 2017) is a form of $\Pi$-Model where we
compare the current prediction of the model on the input $x$ with an
accumulation of the previous passes trhough the model. Then, the training is
faster as the network is evaluated only once per input on each epoch and the
perturbation is expected to be less noisy than for $\Pi$-models.

##### ICT

Interpolation consistency training (Verma et al., 2019) is a SSL method based
on the mixup operation (Zhang et al., 2017). The model trained is then
consistent to preditions at interpolations. The unsupervised term of the
objective is then computed on two terms:

$\displaystyle H(\theta;x_{1},x_{2})=\textbf{Div}\left(f_{\theta}(\alpha
x_{1}+(1-\alpha)x_{2},.),\alpha
f_{\hat{\theta}}(x_{1},.)+(1-\alpha)f_{\hat{\theta}}(x_{2},.)\right),$ (19)

with $\alpha$ drawn with from a distribution $\mathcal{B}(a,a)$. With the
exact same transformation, we will be able to show that this objective is
equivalent to a form of expectation of $L$.

##  C Proof that $\hat{\mathcal{R}}_{DeSSL}(\theta)$ is unbiased under MCAR

###### Theorem 7

Under the MCAR assumption, $\hat{\mathcal{R}}_{DeSSL}(\theta)$ is an unbiased
estimator of $\mathcal{R}(\theta)$.

As a consequence of the theorem, under the MCAR assumption,
$\hat{\mathcal{R}}_{CC}(\theta)$ is also unbiased as a special case of
$\hat{\mathcal{R}}_{DeSSL}(\theta)$ for $\lambda=0$

##### Proof:

We first recall that the DeSSL risk estimator
$\hat{\mathcal{R}}_{DeSSL}(\theta)$ is defined for any $\lambda$ by

$\begin{split}\hat{\mathcal{R}}_{DeSSL}(\theta)&=\frac{1}{n_{l}}\sum_{i=1}^{n_{l}}L(\theta;x_{i},y_{i})+\frac{\lambda}{n_{u}}\sum_{i=1}^{n_{u}}H(\theta;x_{i})-\frac{\lambda}{n_{l}}\sum_{i=1}^{n_{l}}H(\theta;x_{i})\\\
&=\sum_{i=1}^{n}\left(\frac{r_{i}}{n_{l}}L(\theta;x_{i},y_{i})+\lambda\left(\frac{1-r_{i}}{n_{u}}-\frac{r_{i}}{n_{l}}\right)H(\theta;x_{i})\right).\\\
\end{split}$ (20)

By the law of total expectation:

$\begin{split}\mathbb{E}[\hat{\mathcal{R}}_{DeSSL}(\theta)]&=\mathbb{E}_{r}\left[\mathbb{E}_{x,y}[\hat{\mathcal{R}}_{DeSSL}(\theta)|r]\right].\\\
\end{split}$

As far as we are under the MCAR assumption, the data $(x,y)$ and the
missingness variable $r$ are independent thus,
$\mathbb{E}_{r}\left[\mathbb{E}_{x,y}[\hat{\mathcal{R}}_{DeSSL}(\theta)|r]\right]=\mathbb{E}_{r}\left[\mathbb{E}_{x,y}[\hat{\mathcal{R}}_{DeSSL}(\theta)]\right]$.

We focus on $\mathbb{E}_{x,y}[\hat{\mathcal{R}}_{DeSSL}(\theta)]$. First, we
replace $\hat{\mathcal{R}}_{DeSSL}(\theta)$ by its definition and then use the
linearity of the expectation. Then,

$\displaystyle\mathbb{E}_{x,y}[\hat{\mathcal{R}}_{DeSSL}(\theta)]$
$\displaystyle=\mathbb{E}\left[\frac{1}{n_{l}}\sum_{i=1}^{n_{l}}L(\theta;x_{i},y_{i})+\frac{\lambda}{n_{u}}\sum_{i=1}^{n_{u}}H(\theta;x_{i})-\frac{\lambda}{n_{l}}\sum_{i=1}^{n_{l}}H(\theta;x_{i})\right]$
by definition
$\displaystyle=\frac{1}{n_{l}}\sum_{i=1}^{n_{l}}\mathbb{E}\left[L(\theta;x_{i},y_{i})\right]+\frac{\lambda}{n_{u}}\sum_{i=1}^{n_{u}}\mathbb{E}\left[H(\theta;x_{i})\right]-\frac{\lambda}{n_{l}}\sum_{i=1}^{n_{l}}\mathbb{E}\left[H(\theta;x_{i})\right]$
by linearity

The couples $(x_{i},y_{i})$ are i.i.d. samples following the same
distribution. Then, we have

$\displaystyle\mathbb{E}_{x,y}[\hat{\mathcal{R}}_{DeSSL}(\theta)]$
$\displaystyle=\frac{1}{n_{l}}\sum_{i=1}^{n_{l}}\mathbb{E}\left[L(\theta;x,y)\right]+\frac{\lambda}{n_{u}}\sum_{i=1}^{n_{u}}\mathbb{E}\left[H(\theta;x)\right]-\frac{\lambda}{n_{l}}\sum_{i=1}^{n_{l}}\mathbb{E}\left[H(\theta;x)\right]$
i.i.d samples $\displaystyle=\mathbb{E}\left[L(\theta;x,y)\right]$
$\displaystyle=\mathcal{R}(\theta).$

Finally, we have the results that , $\hat{\mathcal{R}}_{DeSSL}(\theta)$ is
unbiased as $\mathcal{R}(\theta)$ is a constant,

$\mathbb{E}[\hat{\mathcal{R}}_{DeSSL}(\theta)]=\mathbb{E}\left[\mathbb{E}_{x,y}[\hat{\mathcal{R}}_{DeSSL}(\theta)]|r\right]=\mathbb{E}_{r}\left[\mathcal{R}(\theta)\right]=\mathcal{R}(\theta).$
(21)

##  D Proof and comments about Theorem 1

##### Theorem 1

_The function $\lambda\mapsto\mathbb{V}(\hat{\mathcal{R}}_{DeSSL}(\theta)|r)$
reaches its minimum for:_

$\lambda_{opt}=\frac{n_{u}}{n}\frac{\mathrm{Cov}(L(\theta;x,y),H(\theta;x))}{\mathbb{V}(H(\theta;x))}$
(22)

_and_

$\begin{split}\small\mathbb{V}(\hat{\mathcal{R}}_{DeSSL}(\theta)|r)|_{\lambda_{opt}}&=\left(1-\frac{n_{u}}{n}\rho_{L,H}^{2}\right)\mathbb{V}(\hat{\mathcal{R}}_{CC}(\theta))\\\
&\leq\mathbb{V}(\hat{\mathcal{R}}_{CC}(\theta)),\end{split}$ (23)

_where $\rho_{L,H}=\mathrm{Corr}(L(\theta;x,y),H(\theta;x))$._

##### Proof:

For any $\lambda\in\mathbb{R}$,we want to compute the variance:

$\begin{split}\mathbb{V}(\hat{\mathcal{R}}_{DeSSL}(\theta)|r).\end{split}$

Under the MCAR assumption, $x$ and $y$ are both jointly independent of $r$.
Also, the couples $(x_{i},y_{i},r_{i})$ are independent. Therefore, we have

$\displaystyle\mathbb{V}(\hat{\mathcal{R}}_{DeSSL}(\theta)|r)$
$\displaystyle=\sum_{i=1}^{n}\mathbb{V}_{(x_{i},y_{i})\sim
p(x,y|r)}\left(\frac{r_{i}}{n_{l}}L(\theta,x_{i},y_{i})+\lambda\left(\frac{1-r_{i}}{n_{u}}-\frac{r_{i}}{n_{l}}\right)H(\theta,x_{i})\right)$
i.i.d samples $\displaystyle=\sum_{i=1}^{n}\mathbb{V}_{(x_{i},y_{i})\sim
p(x,y)}\left(\frac{r_{i}}{n_{l}}L(\theta,x_{i},y_{i})+\lambda\left(\frac{1-r_{i}}{n_{u}}-\frac{r_{i}}{n_{l}}\right)H(\theta,x_{i})\right)$
$(x,y)$ and $r$ independent

Using the fact that the couples (xi,yi) are i.i.d. samples following the same
distribution, we have

$\displaystyle\mathbb{V}(\hat{\mathcal{R}}_{DeSSL}(\theta)|r)$
$\displaystyle=\sum_{i=1}^{n}\mathbb{V}_{(x,y)\sim
p(x,y)}\left(\frac{r_{i}}{n_{l}}L(\theta,x,y)+\lambda\left(\frac{1-r_{i}}{n_{u}}-\frac{r_{i}}{n_{l}}\right)H(\theta,x)\right)$
$\displaystyle=\sum_{i=1}^{n}\frac{r_{i}^{2}}{n_{l}^{2}}\mathbb{V}(L(\theta,x,y))+\lambda^{2}\left(\frac{1-r_{i}}{n_{u}}-\frac{r_{i}}{n_{l}}\right)^{2}\mathbb{V}(H(\theta,x))$
using covariance
$\displaystyle\qquad\qquad\qquad+2\lambda\frac{r_{i}}{n_{l}}\left(\frac{1-r_{i}}{n_{u}}-\frac{r_{i}}{n_{l}}\right)\mathrm{Cov}(L(\theta,x,y),H(\theta,x))$

Now, we remark that the variable $r$ is binary and therefore $r^{2}=r$,
$(1-r)^{2}=1-r$ and $r(1-r)=0$. Using that and simplifying, we have

$\displaystyle\mathbb{V}(\hat{\mathcal{R}}_{DeSSL}(\theta)|r)$
$\displaystyle=\sum_{i=1}^{n}\frac{r_{i}}{n_{l}^{2}}\mathbb{V}(L(\theta,x,y))+\lambda^{2}\frac{(1-r_{i})n_{l}^{2}+r_{i}n_{u}^{2}}{n_{l}^{2}n_{u}^{2}}\mathbb{V}(H(\theta,x))$
$\displaystyle\qquad\qquad\qquad-2\lambda\frac{r_{i}}{n_{l}^{2}}\mathrm{Cov}(L(\theta,x,y),H(\theta,x))$

Finally, by summing and simplifying the expression (note that
$n_{l}+n_{u}=n$), we compute the expression variance,

$\displaystyle\mathbb{V}(\hat{\mathcal{R}}_{DeSSL}(\theta)|r)$
$\displaystyle=\frac{1}{n_{l}}\mathbb{V}(L(\theta,x,y))+\lambda^{2}\frac{n}{n_{l}n_{u}}\mathbb{V}(H(\theta,x))-\frac{2\lambda}{n_{l}}\mathrm{Cov}(L(\theta,x,y),H(\theta,x))$

So $\mathbb{V}(\hat{\mathcal{R}}_{DeSSL}(\theta)|r)$ is a quadratic function
in $\lambda$ and reaches its minimum for $\lambda_{opt}$ such that:

$\lambda_{opt}=\frac{n_{u}}{n}\frac{\mathrm{Cov}(L(\theta,x,y),H(\theta,x))}{\mathbb{V}(H(\theta,x))}$

And, at $\lambda_{opt}$, the variance of
$\hat{\mathcal{R}}_{DeSSL}(\theta)|r)$ becomes

$\displaystyle\mathbb{V}(\hat{\mathcal{R}}_{DeSSL}(\theta)|r)$
$\displaystyle=\frac{1}{n_{l}}\mathbb{V}(L(\theta,x,y))\left(1-\frac{n_{u}}{n}\frac{\mathrm{Cov}(L(\theta,x,y),H(\theta,x))^{2}}{\mathbb{V}(H(\theta,x))\mathbb{V}(L(\theta;x,y))}\right)$
$\displaystyle=\frac{1}{n_{l}}\mathbb{V}(L(\theta,x,y))\left(1-\frac{n_{u}}{n}\mathrm{Corr}(L(\theta,x,y),H(\theta,x))^{2}\right)$
$\displaystyle=\left(1-\frac{n_{u}}{n}\rho_{L,H}^{2}\right)\frac{1}{n_{l}}\mathbb{V}(L(\theta,x,y))$

###### Remark 8

If $H$ is perfectly correlated with $L$ ($\rho_{L,H}=1$), then the variance of
the DeSSL estimator is equal to the variance of the estimator with no missing
labels.

###### Remark 9

Is it possible to estimate $\lambda_{opt}$ in practice ? The data distribution
$p(x,y)$ being unknown, the computation of $\lambda_{opt}$ is not possible
directly. Therefore, we need to use an estimator of the covariance
$\mathrm{Cov}(L(\theta;x,y),H(\theta;x))$ and the variance
$\mathbb{V}(H(\theta;x))$ (See Equation 24). Also, we have to be careful not
to introduce a new bias with the computation of $\lambda_{opt}$, indeed, if we
compute it using the training set, $\lambda_{opt}$ becomes dependent of $x$
and $y$ and therefore $\hat{\mathcal{R}}_{DeSSL}(\theta)|r)$ becomes biased. A
solution would be to use a validation dataset for its computation. Another
approach is to compute it using the splitting method (Owen, 2013). Moreover,
the computation of $\lambda_{opt}$ is tiresome and time-consuming in practice
as it has to be updated for every different value of $\theta$, so at each
gradient step.

$\hat{\lambda}_{opt}=\frac{\frac{1}{n_{l}}\sum_{i=1}^{n_{l}}(L(\theta;x_{i},y_{i})-\bar{L}(\theta))(H(\theta;x_{i})-\bar{H}(\theta))}{\frac{1}{n}\sum_{i=1}^{n}(H(\theta;x_{i})-\bar{H}(\theta))^{2}}$
(24)

where $\bar{H}(\theta)=\frac{1}{n}\sum_{i=1}^{n}H(\theta;x_{i})$ and
$\bar{L}(\theta)=\frac{1}{n_{l}}\sum_{i=1}^{n_{l}}L(\theta;x_{i},y_{i})$

###### Remark 10

About the sign of $\lambda$ As explained in the article, the theorem still has
a _quantitative_ merit when it comes to choosing $\lambda$, by telling that
the sign of $\lambda$ is positive when $H$ and $L$ are positively correlated
which will generally be the case with the examples mentioned in the article.
For instance, concerning the entropy minimisation technique, the following
proposition proves that the log-likelihood is negatively correlated with its
entropy and therefore it justifies the choice of $\lambda>0$ in the entropy
minimisation.

###### Proposition 11

The log-likelihood of the true distribution $\log p(y|x)$ is negatively
correlated with its entropy
$\mathbb{H}_{\tilde{y}}(p(\tilde{y}|x))=-\mathbb{E}_{\tilde{y}\sim
p(.|x)}[\log p(\tilde{y}|x)]$ .

$\mathrm{Cov}(\log p(y|x),\mathbb{H}_{\tilde{y}}(p(\tilde{y}|x)))<0$ (25)

Proof

$\displaystyle\mathrm{Cov}(\log
p(y|x),\mathbb{H}_{\tilde{y}}(p(\tilde{y}|x)))$
$\displaystyle=\mathbb{E}_{x,y}[\log
p(y|x)\mathbb{H}_{\tilde{y}}(p(\tilde{y}|x))]-\mathbb{E}_{x,y}[\log
p(y|x)]\mathbb{E}_{x}[\mathbb{H}_{\tilde{y}}(p(\tilde{y}|x))]$ (26)
$\displaystyle=-\mathbb{E}_{x,y}[\log p(y|x)\mathbb{E}_{\tilde{y}|x}[\log
p(\tilde{y}|x)]]+\mathbb{E}_{x,y}[\log
p(y|x)]\mathbb{E}_{x}[\mathbb{E}_{\tilde{y}|x}[\log p(\tilde{y}|x)]]$ (27)

By the law of total expectation, we have that
$\mathbb{E}_{x}[\mathbb{E}_{\tilde{y}|x}[\log
p(\tilde{y}|x)]]=\mathbb{E}_{x,\tilde{y}}[\log p(\tilde{y}|x)]$, then

$\displaystyle\mathrm{Cov}(\log p(y|x),\mathbb{H}_{\tilde{y}}(p(\tilde{y}|x))$
$\displaystyle=-\mathbb{E}_{x,y}[\log p(y|x)\mathbb{E}_{\tilde{y}|x}[\log
p(\tilde{y}|x)]]+\mathbb{E}_{x,y}[\log p(y|x)]^{2}$ (29)
$\displaystyle=\mathbb{E}_{x,y}[\log p(y|x)]^{2}-\mathbb{E}_{x,y}[\log
p(y|x)\mathbb{E}_{\tilde{y}|x}[\log p(\tilde{y}|x)]]$ (30)

On the other hand, also with the law of total expectation,
$\mathbb{E}_{x,y}[\log p(y|x)\mathbb{E}_{\tilde{y}|x}[\log
p(\tilde{y}|x)]]=\mathbb{E}_{x}[\mathbb{E}_{y|x}[\log
p(y|x)]\mathbb{E}_{\tilde{y}|x}[\log p(\tilde{y}|x)]]$, so

$\displaystyle\mathbb{E}_{x,y}[\log p(y|x)\mathbb{E}_{\tilde{y}|x}[\log
p(\tilde{y}|x)]]$ $\displaystyle=\mathbb{E}_{x}[\mathbb{E}_{y|x}[\log
p(y|x)]^{2}]$ $\displaystyle\geq\mathbb{E}_{x}[\mathbb{E}_{y|x}[\log
p(y|x)]]^{2}$ Jensen’s inequality $\displaystyle\geq\mathbb{E}_{x,y}[\log
p(y|x)]^{2}$ total expectation law

Finally, we have the results,

$\begin{split}\mathrm{Cov}(\log
p(y|x),\mathbb{H}_{\tilde{y}}(p(\tilde{y}|x)))&\leq\mathbb{E}_{x,y}[\log
p(y|x)]^{2}-\mathbb{E}_{x,y}[\log p(y|x)]^{2}\\\ &\leq 0\end{split}$

###### Remark 12

We can also see the Pseudo-label as a form of entropy. Indeed, modulo the
confidence selection on the predicted probability, the Pseudo-label objective
is the inverse of the Rényi min-entropy:

$\mathbb{H}_{\infty}(x)=-\max_{y}\log p(y|x)$

##  E Proof of Theorem 2

##### Theorem 2

_If $\mathcal{S}(p_{\theta},(x,y))=-L(\theta;x,y)$ is a proper scoring rule,
then_

$\mathcal{S}^{\prime}(p_{\theta},(x,y,r))=-(\frac{rn}{n_{l}}L(\theta;x,y)+\lambda
n(\frac{1-r}{n_{u}}-\frac{r}{n_{l}})H(\theta;x))$ (32)

_is also a proper scoring rule._

Proof  The scoring rule considered in our SSL framework is:

$\mathcal{S}^{\prime}(p_{\theta},(x,y,r))=-\left(\frac{rn}{n_{l}}L(\theta;x,y)+\lambda
n(\frac{1-r}{n_{u}}-\frac{r}{n_{l}})H(\theta;x)\right)$

. The proper scoring rule of the fully supervised problem is

$\mathcal{S}(p_{\theta},(x,y,r))=-L(\theta;x,y)$

. Let p be the true distribution of the data $(x,y,r)$. Under MCAR, $r$ is
independent of $x$ and $y$, then $p(x,y,r)=p(r)p(x,y)$.

$\displaystyle\mathcal{S}^{\prime}(p_{\theta},p)$ $\displaystyle=\int
p(x,y,r)\mathcal{S}^{\prime}(p_{\theta},(x,y,r))\,dx\,dy\,dr$ (33)
$\displaystyle=\int
p(x,y)p(r)\mathcal{S}^{\prime}(p_{\theta},(x,y,r))\,dx\,dy\,dr$ by
independence (34) $\displaystyle=-\int
p(x,y)p(r)\frac{rn}{n_{l}}L(\theta;x,y)+\lambda
n(\frac{1-r}{n_{u}}-\frac{r}{n_{l}})H(\theta;x)\,dx\,dy\,dr$ (35)
$\displaystyle=-\int_{x,y}p(x,y)\underbrace{\left(\int_{r}p(r)\frac{rn}{n_{l}}\,dr\right)}_{=1}L(\theta;x,y)\,dx\,dy$
(36) $\displaystyle\quad\quad\quad-\lambda
n\int_{x,y}p(x,y)\underbrace{\left(\int_{r}p(r)\left(\frac{1-r}{n_{u}}-\frac{r}{n_{l}})\right)\,dr\right)}_{=0}H(\theta;x)\,dx\,dy$
(37) $\displaystyle=-\int_{x,y}p(x,y)L(\theta;x,y)\,dx\,dy$ (38)
$\displaystyle=\mathcal{S}(p_{\theta},p)$ (39)

Therefore, if $\mathcal{S}(p_{\theta},(x,y))=-L(\theta;x,y)$ is a proper
scoring rule, then $\\\
mathcal{S}^{\prime}(p_{\theta},(x,y,r))=-(\frac{rn}{n_{l}}L(\theta;x,y)+\lambda
n(\frac{1-r}{n_{u}}-\frac{r}{n_{l}})H(\theta;x))$ is also a proper scoring
rule.

##  F Proof of Theorem 5

Assumption 11: the minimum $\theta^{*}$ of $\mathcal{R}$ is well-separated.

$\inf_{\theta:d(\theta^{*},\theta)\geq\epsilon}\mathcal{R}(\theta)>\mathcal{R}(\theta^{*})$
(40)

Assumption 4: uniform weak law of large numbers holds for a function $L$ if:

$\sup_{\theta\in\Theta}\left|\frac{1}{n}\sum_{i=1}^{n}L(\theta,x_{i},y_{i})-\mathbb{E}[L(\theta,x,y)]\right|\xrightarrow{p}0$
(41)

##### Theorem 5.

_Under assumption A and assumption B for both $L$ and $H$,
$\hat{\theta}=\operatorname*{arg\,min}\hat{\mathcal{R}}_{DeSSL}$ is
asymptotically consistent with respect to $n$. _

This result is a direct application of Theorem 5.7 from van der Vaart (2000,
Chapter 5) that states that under assumption A and B for $L$,
$\hat{\theta}=\operatorname*{arg\,min}\hat{\mathcal{R}}$ is asymptotically
consistent with respect to $n$. Assumption A remains unchanged as we have
M-estimators of the same $\mathcal{R}$. We now aim to prove that under
assumption B for both $L$ and $H$, we have the assumption B on
$\theta\longrightarrow\frac{rn}{n_{l}}L(\theta;x,y)+\lambda(1-\frac{rn}{n_{l}})H(\theta;x)$.

###### Lemma 13

If the uniform law of large number holds for both $L$ and $H$, then it holds
for
$\theta\longrightarrow\frac{rn}{n_{l}}L(\theta;x,y)+\lambda(1-\frac{rn}{n_{l}})H(\theta;x)$.

Proof  Suppose assumption B for $L$, then the same result holds if we replace
$n$ with $n_{l}$ as $n$ and $n_{l}$ are coupled by the law of $r$. Indeed,
when $n$ grows to infinity, $n_{l}$ too and inversely. Therefore,

$\begin{split}\sup_{\theta\in\Theta}\left|\frac{1}{n_{l}}\sum_{i=1}^{n_{l}}L(\theta;x_{i},y_{i})-\mathbb{E}[L(\theta;x,y)]\right|\xrightarrow[n]{p}0\\\
\end{split}$

Now, suppose we have assumption B for $H$, then we can make the same remark
than for $L$. Now, we have to show that:

$\begin{split}\sup_{\theta\in\Theta}\left|\frac{1}{n}\sum_{i=1}^{n}\frac{rn}{n_{l}}L(\theta;x,y)+\lambda
n\left(\frac{1-r}{n_{u}}-\frac{r}{n_{l}}\right)H(\theta;x)-\mathbb{E}[L(\theta;x,y)]\right|\xrightarrow[n]{p}0\\\
\end{split}$

We first split the absolute value and the sup operator as

$\begin{split}\sup_{\theta\in\Theta}\left|\frac{1}{n}\sum_{i=1}^{n}\frac{rn}{n_{l}}L(\theta;x,y)+\lambda
n\left(\frac{1-r}{n_{u}}-\frac{r}{n_{l}}\right)H(\theta;x)-\mathbb{E}[L(\theta;x,y)]\right|\\\
\leq\sup_{\theta\in\Theta}\left|\frac{1}{n_{l}}\sum_{i=1}^{n}\frac{rn}{n_{l}}L(\theta;x,y)-\mathbb{E}[L(\theta;x,y)]\right|+\left|\frac{1}{n}\sum_{i=1}^{n}\lambda
n\left(\frac{1-r}{n_{u}}-\frac{r}{n_{l}}\right)H(\theta;x)\right|\\\
\leq\underbrace{\sup_{\theta\in\Theta}\left|\frac{1}{n_{l}}\sum_{i=1}^{n_{l}}L(\theta;x,y)-\mathbb{E}[L(\theta;x,y)]\right|}_{\xrightarrow[n]{p}0}+\sup_{\theta\in\Theta}\left|\frac{1}{n}\sum_{i=1}^{n}\lambda
n\left(\frac{1-r}{n_{u}}-\frac{r}{n_{l}}\right)H(\theta;x)\right|.\end{split}$

So we now have to prove that the second term is also converging to $0$ in
probability. Again by splitting the absolute value and the sup, we have

$\begin{split}\sup_{\theta\in\Theta}\left|\frac{1}{n}\sum_{i=1}^{n}\lambda
n\left(\frac{1-r}{n_{u}}-\frac{r}{n_{l}}\right)H(\theta;x)\right|&=\sup_{\theta\in\Theta}\left|\frac{\lambda}{n}\sum_{i=1}^{n}\frac{(1-r)n}{n_{u}}H(\theta;x)-\frac{\lambda}{n}\sum_{i=1}^{n}\frac{rn}{n_{l}}H(\theta;x)\right|\\\
\end{split}$

Then we have that,

$\begin{split}\sup_{\theta\in\Theta}\left|\frac{\lambda}{n_{u}}\sum_{i=1}^{n}(1-r)H(\theta;x)-\frac{\lambda}{n_{l}}\sum_{i=1}^{n}rH(\theta;x)\right|\\\
=\sup_{\theta\in\Theta}\left|\frac{\lambda}{n_{u}}\sum_{i=1}^{n}(1-r)H(\theta;x)-\mathbb{E}[H(\theta;x,y)]-\left(\frac{\lambda}{n_{l}}\sum_{i=1}^{n}rH(\theta;x)-\mathbb{E}[H(\theta;x,y)]\right)\right|\\\
=\sup_{\theta\in\Theta}\left|\frac{\lambda}{n_{u}}\sum_{i=n_{l}+1}^{n_{l}+n_{u}}H(\theta;x)-\mathbb{E}[H(\theta;x,y)]-\left(\frac{\lambda}{n_{l}}\sum_{i=1}^{n_{l}}H(\theta;x)-\mathbb{E}[H(\theta;x,y)]\right)\right|\\\
\leq\underbrace{\sup_{\theta\in\Theta}\left|\frac{\lambda}{n_{u}}\sum_{i=n-l+1}^{n_{l}+n_{u}}H(\theta;x)-\mathbb{E}[H(\theta;x,y)]\right|}_{\xrightarrow[n]{p}0}+\underbrace{\sup_{\theta\in\Theta}\left|\left(\frac{\lambda}{n_{l}}\sum_{i=1}^{n_{l}}H(\theta;x)-\mathbb{E}[H(\theta;x,y)]\right)\right|}_{\xrightarrow[n]{p}0}\\\
.\end{split}$

Thus,

$\begin{split}\sup_{\theta\in\Theta}\left|\frac{1}{n}\sum_{i=1}^{n}\frac{rn}{n_{l}}L(\theta;x,y)+\lambda
n\left(\frac{1-r}{n_{u}}1-\frac{r}{n_{l}}\right)H(\theta;x)-\mathbb{E}[L(\theta;x,y)]\right|\xrightarrow[n]{p}0\\\
\end{split}$

And we now just have to apply the results of van der Vaart (2000, Theorem 5.7)
to have the asymptotic consistent of
$\hat{\theta}=\operatorname*{arg\,min}\hat{\mathcal{R}}_{DeSSL}$.

###### Remark 14

A sufficient condition on the function $H$ to verify assumption B, the uniform
weak law of large numbers, is to be bounded (Newey and McFadden, 1994, Lemma
2.4). For instance, the entropy
$H=-\sum_{y}p_{\theta}(y|x)\log(p_{\theta}(y|x))$ is bounded and therefore,
the entropy minimisation is asymptotically consistent.

##  G Proof of Theorem 6

Our proof will be based on the following result from Shalev-Shwartz and Ben-
David (2014, Theorem 26.5).

###### Theorem 15

Let $\mathcal{H}$ be a set of parameters, $z\sim\mathcal{D}$ a random variable
living in a space $\mathcal{Z}$, $c>0$, and
$\ell:\mathcal{H}\times\mathcal{Z}\longrightarrow[-c,c]$. We denote

$L_{\mathcal{D}}(h)=\mathbb{E}_{z}[\ell(h,z)],\;and\;L_{\mathcal{S}}(h)=\frac{1}{m}\sum_{i=1}^{m}\ell(h,z_{i}),$
(42)

where $z_{1},...,z_{m}$ are i.i.d. samples from $\mathcal{D}$. For any
$\delta>0$, with probability at least $1-\delta$, we have

$L_{\mathcal{D}}(h)\leq
L_{\mathcal{S}}(h)+2\mathbb{E}_{(\varepsilon_{i})_{i\leq
m}}\left[\sup_{h\in\mathcal{H}}\left(\frac{1}{m}\sum_{i=1}^{m}\varepsilon_{i}\ell(h,z_{i})\right)\right]+4c\sqrt{\frac{2\log(4/\delta)}{m}},$
(43)

where $\varepsilon_{1},...,\varepsilon_{m}$ are i.i.d. Rademacher variables
independent from $z_{1},...,z_{m}$.

We can now restate and prove our generalisation bound.

##### Theorem 6.

_We assume that both $L$ and $H$ are bounded and that the labels are MCAR.
Then, there exists a constant $\kappa>0$, that depends on $\lambda$, $L$, $H$,
and the ratio of observed labels, such that, with probability at least
$1-\delta$, for all $\theta\in\Theta$,_

$\mathcal{R}(\theta)\leq\hat{\mathcal{R}}_{DeSSL}(\theta)+2R_{n}+\kappa\sqrt{\frac{\log(4/\delta)}{n}},$
(44)

_where $R_{n}$ is the Rademacher complexity_

$R_{n}=\mathbb{E}_{(\varepsilon_{i})_{i\leq
n}}\left[\sup_{\theta\in\Theta}\left(\frac{1}{n_{l}}\sum_{i=1}^{n_{l}}\varepsilon_{i}L(\theta;x_{i},y_{i})-\frac{\lambda}{n_{l}}\sum_{i=1}^{n_{l}}\varepsilon_{i}H(\theta;x_{i})+\frac{\lambda}{n_{u}}\sum_{i=1}^{n_{u}}\varepsilon_{i}H(\theta;x_{i})\right)\right],$
(45)

_with $\varepsilon_{1},...,\varepsilon_{m}$ i.i.d. Rademacher variables
independent from the data. _

Proof  We use Theorem 15 with $z=(x,y,r)$, $\mathcal{H}=\Theta$, $m=n$, and

$\ell(h,z)=\frac{nr_{i}}{n_{l}}L(\theta;x_{i},y_{i})+\lambda\left(\frac{n(1-r_{i})}{n_{u}}-\frac{nr_{i}}{n_{l}}\right)H(\theta;x_{i}).$
(46)

The unbiasedness of our estimate under the MCAR assumption, proven in Appendix
C, ensures that the condition of Equation (42) is satisfied with
$L_{\mathcal{D}}(h)=\mathcal{R}(\theta)$ and
$L_{S}(h)=\hat{\mathcal{R}}_{DeSSL}(\theta)$. Now, since $L$ and $H$ are
bounded, there exists $M>0$ such that $|L|<M$ and $|H|<M$. We can then bound
$\ell$:

$|\ell(h,z)|\leq\frac{n}{n_{l}}M+\lambda\max\left\\{\frac{n}{n_{u}},\frac{n}{n_{l}}\right\\}M=c.$
(47)

Now that we have chosen a $c$ that bounds $\ell$, we can use Theorem 15 and
finally get Equation (44) with $\kappa=4c\sqrt{2}$.

##  H DeSSL with $H$pplied on all available data

For consistency-based SSL methods it is common to use all the available data
for the consistency term:

$\begin{split}\hat{\mathcal{R}}_{SSL}(\theta)&=\frac{1}{n_{l}}\sum_{i=1}^{n_{l}}L(\theta;x_{i},y_{i})\color[rgb]{1,0,0}{+\frac{\lambda}{n}\sum_{i=1}^{n}H(\theta;x_{i})}.\\\
\end{split}$ (48)

With the same idea, we debias the risk estimate with the labelled data:

$\begin{split}\hat{\mathcal{R}}_{DeSSL}(\theta)=\frac{1}{n_{l}}\sum_{i=1}^{n_{l}}L(\theta;x_{i},y_{i})&\color[rgb]{1,0,0}{+\frac{\lambda}{n}\sum_{i=1}^{n}H(\theta;x_{i})}\\\
&\color[rgb]{0,0,1}{-\frac{\lambda}{n_{l}}\sum_{i=1}^{n_{l}}H(\theta;x_{i}).}\end{split}$
(49)

Under MCAR, this risk estimate is unbiased and the main theorem of the article
hold with minor modifications. In Theorem 1, $\lambda_{opt}$ is slightly
different and the expression of the variance at $\lambda_{opt}$ remains the
same. The scoring rule in Theorem 2 is different but the theorem remains the
same. Both Theorem 5 and 6 remain the same with very similar proofs.

###### Theorem 16

The function $\lambda\mapsto\mathbb{V}(\hat{\mathcal{R}}_{DeSSL}(\theta))$
reaches its minimum for:

$\lambda_{opt}=\frac{\mathrm{Cov}(L(\theta;x,y),H(\theta;x))}{\mathbb{V}(H(\theta;x))}$
(50)

and

$\begin{split}\small\mathbb{V}(\hat{\mathcal{R}}_{DeSSL}(\theta))|_{\lambda_{opt}}&=(1-\frac{n_{u}}{n}\rho_{L,H}^{2})\mathbb{V}(\hat{\mathcal{R}}_{CC}(\theta))\\\
&\leq\mathbb{V}(\hat{\mathcal{R}}_{CC}(\theta))\end{split}$ (51)

where $\rho_{L,H}=\mathrm{Corr}(L(\theta;x,y),H(\theta;x))$.

When $H$ is applied on all labelled and unlabelled data, the scoring rule used
in the learning process is then
$\mathcal{S}^{\prime}(p_{\theta},(x,y,r))=-(\frac{rn}{n_{l}}L(\theta;x,y)+\lambda(1-\frac{rn}{n_{l}})H(\theta;x))$
and we have $\mathcal{S}^{\prime}$ is a proper scoring rule.

##  I MNIST and MedMNIST

###  I.1 MNIST

Figure 7: The influence of $\lambda$ on Pseudo-label and DePseudo-label for a
Lenet trained on MNIST with $n_{l}=1000$: (Left) Test accuracy; (Middle) Mean
test loss; (Right) Mean test ECE, with 95% CI

###  I.2 MNIST label noise

Figure 8: The influence of $\lambda$ on Pseudo-label and DePseudo-label for a
Lenet trained on MNIST with label noise with $n_{l}=1000$: (Left) Mean test
accuracy; (Middle) Mean test loss; (Right) Test ECE, with 95% CI.

###  I.3 MedMNIST

Table 3: Test AUC of Complete Case , PseudoLabel and DePseudoLabel on five
datasets of MedMNIST.
Dataset | Complete Case | PseudoLabel | DePseudoLabel
---|---|---|---
Derma |  84.26 $\pm$ 0.50 |  82.64 $\pm$ 1.19 |  83.82 $\pm$ 0.95
Pneumonia |  94.28 $\pm$ 0.46 |  94.34 $\pm$ 0.91 |  94.15 $\pm$ 0.33
Retina |  70.70 $\pm$ 0.74 |  70.12 $\pm$ 1.01 |  69.97 $\pm$ 1.44
Breast |  74.67 $\pm$ 3.68 |  74.86 $\pm$ 3.18 |  75.33 $\pm$ 3.05
Blood |  97.83 $\pm$ 0.23 |  97.83 $\pm$ 0.23 |  97.72 $\pm$ 0.15

##  J PseudoLabel and DePseudoLabel on CIFAR: p-values

Figure 9: The influence of $\lambda$ on Pseudo-label and DePseudo-label on
CIFAR with nl= 4000: (Left) Mean test accuracy; (Middle) Mean test loss;
(Right) Test ECE, with 95% CI.

Figure 10: p-values of a paired student test between PseudoLabel and
DePseudoLabel (Right) DePseudoLabel is better than PseudoLabel; (Left)
DePseudoLabel is worst than PseudoLabel.

##  K CIFAR and SVHN: Oliver et al. (2018)mplementation of consistency-based
model.

In this section we present the results on CIFAR and SVHN by debiasing the
(Oliver et al., 2018) implementation of Pseudo-label, $\Pi$-Model, Mean-
Teacher and VAT 111https://github.com/brain-research/realistic-ssl-evaluation.
We mimic the experiments of Oliver et al. (2018, figure-4) with the same
configuration and the exact same hyperparameters (Oliver et al., 2018,
Appendix B and C). We perform an early stopping independently on both loss and
accuracy. As reported below, we reach almost the same results as (Oliver et
al., 2018) by using all the data.

###  K.1 CIFAR-10

Figure 11: Test loss for each SSL approaches on CIFAR-10 with various amounts
of labelled data $n_{l}$.(Left) $\Pi$-model and De$\Pi$-model. (Middle)
VAT+EntMin and VAT+DeEntMin. (Right) Mean-teacher and DeMean-teacher. Shadows
represent 95% CI.

Figure 12: Test loss for each SSL approaches on CIFAR-10 with various amounts
of labelled data $n_{l}$.(Left) $\Pi$-model and De$\Pi$-model. (Middle)
VAT+EntMin and VAT+DeEntMin. (Right) Mean-teacher and DeMean-teacher. Shadows
represent 95% CI.

###  K.2 SVHN

Figure 13: Test loss for each SSL approaches on CIFAR-10 with various amounts
of labelled data $n_{l}$.(Left) $\Pi$-model and De$\Pi$-model. (Middle)
VAT+EntMin and VAT+DeEntMin. (Right) Mean-teacher and DeMean-teacher. Shadows
represent 95% CI.

Figure 14: Test loss for each SSL approaches on CIFAR-10 with various amounts
of labelled data $n_{l}$.(Left) $\Pi$-model and De$\Pi$-model. (Middle)
VAT+EntMin and VAT+DeEntMin. (Right) Mean-teacher and DeMean-teacher. Shadows
represent 95% CI.

##  L Tabular benchmarks

In this section, we tested these methods against the benchmarks of Chapelle et
al., 2006, Chapter 21 and UCI datasets already used in a SSL context in (Guo
et al., 2010). We trained a logistic regression for the case of 100 labelled
datapoints and finetune $\lambda$ with a very small validation set, 20
datapoints. We evaluated the performance in accuracy and loss of PseudoLabel,
EntMin, DePseudoLabel and DeEntMin

###  L.1 SSL Benchmark

Figure 15: Mean accuracy and loss for each SSL datasets (Chapelle et al.,
2006) on a logistic regression. (Top-Left) PseudoLabel and DePseudoLabel
accuracy (Top-Right) PseudoLabel and DePseudoLabel loss (Bottom-Left) EntMin
and DeEntMin accuracy (Bottom-Right) EntMin and DeEntMin loss.

###  L.2 UCI datasets

Figure 16: Mean accuracy and loss for each UCI datasets (Guo et al., 2010) on
a logistic regression. (Top-Left) PseudoLabel and DePseudoLabel accuracy (Top-
Right) PseudoLabel and DePseudoLabel loss (Bottom-Left) EntMin and DeEntMin
accuracy (Bottom-Right) EntMin and DeEntMin loss.