Don’t fear the unlabelled: safe semi-supervised learning via simple debiasing
Authors: Hugo Schmutz
Olivier HUMBERT
Pierre-Alexandre Mattei
Venue: NeurIPS 2022 Submitted (2022)
Keywords: Semi-supervised learning
deep learning
empirical risk minimization
control variate
variance reduction

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 lacking theoretical guarantees. Our starting point is to notice that the estimate of the risk that most discriminative SSL methods minimise is biased, even asymptotically. This bias impedes the use of standard statistical learning theory and can hurt empirical performance. 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 trustworthiness of these modified methods, without having to rely on the strong assumptions on the data distribution that SSL theory usually requires. In particular, we provide generalisation error bounds for the proposed methods. We evaluate debiased versions of different existing SSL methods, such as the Pseudo-label method and Fixmatch, and show that debiasing can compete with classic deep SSL techniques in various settings by providing better calibrated models. Additionally, we provide a theoretical explanation of the intuition of the popular SSL methods. 

Don't fear the unlabelled:
Safe semi-supervised learning via simple debiasing
Anonymous Author(s)
Affiliation
Address
email
Abstract
Semi-supervised learning (SSL) provides effective means of leveraging un- labelled 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 draw of lacking theoretical guarantees. Our starting point is to notice that the estimate of the risk that most discriminative SSL methods minimise is biased, even asymptotically. This bias impedes the use of standard statistical learning theory and can hurt empirical performance. 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 trustworthiness of these modified methods, without having to rely on the strong assumptions on the data distribution that SSL theory usually requires. In particular, we provide generalisation eтror bounds for the proposed methods. We evaluate debiased versions of different existing SSL methods, such as the Pseudo-label method and Fixmatch, and show that debiasing can compete with classic deep SSL techniques in various settings by providing better calibrated models. Additionally, we provide theoretical explanation of the intuition of the popular SSL. methods.
2
4
6
8
10
11
12
13
14
15
Introduction
18
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 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 with predictions made by some estimate of the predictive model and used the obtained pseudo-labels to
19
20
21
23 refine their initial estimate. Other more complex branches of SSL. have been explored since, notably using generative models (from Mcl achlan 1977 to Kingma et al. (014) or graphs (notably following
24
25 Zhu ct 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
27
notion of pseudo-labels (or one of variants), combined with systematic use data augmentation
(e.g. Xie et al. 2019 Sohn et al. 2020 Rizve al. 2021
29
An obvious SSL baseline simply throwing away the unlabelled data. We will call such a baseline the complete case, following the missing data literature (e.g. (Tiatiis 2006). As reported in van Engelen &
30
31 Hoos (202)), the main risk of SSL is the potential degradation caused by the introduction of unlabelled data. Indeed, suiisueeee learning outperforms the complete case baseline only in specific cases
33 (Singh et al. 2008 Schölkopf al. 2012, Li Zhou 2014). This degradation risk for generative models has been analysed in Chapelle et al. 2006 Chapter 4). To overcome this issue, previous works
35
introduced the notion of safe semiisupervised learning for techniques which never reduce predictive
performance by introducing unlabelled data (Li & Zhou 2014 Guo al. 2020h. Our loose definition
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

37 of safeness is as follows: an SSL algorithm is safe if has theoretical guarantees that are similar cause large modification in the labels, p(y (())per((=)) s p(y|z)) or the cluster assumption (data points are distributed on discrete clusters and points the same cluster are likely to share the same label).
38 or stronger to the complete case baseline. The "theoretical" part the definition is motivated by the fact that any empirical assessment of generalisation performances of an SSL algorithm is jeopardised 40 by the scarcity of labels. Unfortunately, popular deep SSL. techniques generally do not benefit from theoretical guarantees without strong and essentially untestable assumptions on the data distribution (eyy & Loog 2019) such as the smoothness assumption (small perturbations on the features æ do not
41
42
44
45
Most cemi-supervised methods rely on these dis- tributional assumptions to ensure performance in entropy minimisation, pseudo-labelle consistency-bant
46
47
and methods. However, no proof is given that guarantees the effectiveness of state- of-the-art methods (Tarvainen & Valpola 2017;
48
50
Miyato et al. 2018 Sohn al. 2020; Pham 52 et al. 2021). To illustrate that SSL requires spe- cific assumptions, we show in a toy example that lebell-la fails at learning. To do so, we draw samples from two uniform distributions with small overlap. Both supervised and semi- supervised neural networks trained using the same labelled dataset. While the supervised al- gorithm learns perfectly the true distribution of p)) the semi-supervised learning methods (both entropy minimisation and pseudo-label) underestimate p( [zr) for x E [1,3] (see Figure We also test our proposed method (DeSSL) on this dataset and show that the unbiased ver- sion of each SSL technique learns the true dis- tribution accurately. See Appendix A for the results with Entropy Minimisation.
54
True distribution Complete Pseudo-label DePseudo-label
56
58
21
60
02
61
62
3.
D.
63
64
Figure 1: (Left) Data histogram. (Right) Posterior probabilities p(1 (ar) of the same model trained following either complete case (only labelled data), Pseudo-label or our DePscudo-label.
65
86
87
88
1.1
Contributions
69
Rather than relying on the strong geometric assumptions usually used in SSL theory, we simply use the missing completely at random (MCAR) assumption, standard assumption from the missing data literature (see e.g. Little & Rubin 2019). With this only assumption on the data distribution, we propose new safe SSL method derived from simply debiasing common SSL risk estimates. Our main contributions are:
70
71
73
74
We introduce debiased SSL (DeSSL), safe method that can be applied to most deep SSL algorithms without assumptions on the data distribution;
75
We propose theoretical explanation of the intuition of 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;
77
79
We show how simple is to apply DeSSL to the most popular methods such as Pseudo-label and Fixmatch, and show empirically that DeSSL leads to models that are never worse than their classical counterparts, generally better calibrated and sometimes much more accurate.
80
81
2
Semi-supervised learning
83
2.1
Learning with labelled data
84 The ultimate objective of most of the learning frameworks is to minimise a risk R, defined as the expectation of a particular loss function L over data distribution p(æ; y). on a set of models So(x), parametrised by E @. Thus, the learning task finding 0* that minimises the risk: R0) [(x,Y))p(a.)) [ X, Y)). The distribution p(x, y) being unknown, generally minimise
86

---

an approximation of the risk, the empirical risk R(0) computed on a sample of n ii. points drawn from p(z,z) y). R(0) is an unbiased and consistent estimate of R()) under mild assumptions. Its unbiased nature is one of the basic properties that used for the development of traditional learning theory and asymptotic statistics (van der Vaart 2000 Shalev-Shward & Ben-David 2014).
88
90
91
92
2.2
Learning with both labelled and unlabelled data
93
Semi-super learning leverages both labelled and unlabelled data improve the model's per- formance and generalisation. Further information on the distribution p(z) provides a better under- standing of the distributions p(z, 3) and also ply 1r). Indeed, p(æ) may contain information on p(y|z)
94
95
96
(Schölkopf et al. 2012 Goodfellow et al. 2016 Chapter 7.6, van Engelen & Hoos 2020).
In the following, labels are missing. We introduce a new random variable r E {0, 1} that governs whether or not a data point is labelled (r 0 missing, r = 1 observed). We note ni the number of labelled and nh, the number of unlabelled datapoints. The MCAR assumption states that the missingness of a label is independent of its features and the value of the label: p(=,, y: r) p(ar, y))(r). then r B(r).. This is the case when nor features nor label carry information about the potential missingness of the labels. This description of cemi-supervised learning
have access to samples drawn from the distribution p(r: y) where some of the
98
99
100
102
103
missing data problem has already been done in multiple works -e.g. [Seeger 20000 AAhook & McLachlan 2019 Moreover, the MCAR assumption implicitly made in most of the SSL works design the experiments, indeed, missing labels are drawn completely as random in datasets such as MNIST, CIFAR or SVHN (Tarvainen & Valpola
104
105
106
107
2017
Miyato et al. 2018 Xie et al. 2019; /Shhn et al. 2020).
108
2.2.1
Complete case: throwing the unlabelled data away
109
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 R()). Therefore. traditional learning theory holds for the complete case under MCAR.
110
111
112
113
114
While these observations are hardly new (see e.g. Liu & Goldberg, 2020)), they can be seen as particular cases of the theory that we develop below. The risk to minimisc is
115
(C)
Σ L(0 V:)...
(1)
116
2.2.2
Incorporating unlabelled data
117
major drawback of the complete case framework is that lot of data ends up not being exploited. A class of SSL approaches, mainly inductive methods with respect to the taxonomy of van Engelen &
118
119
Hoos (2020), generally aim to minimise modified estimator of the risk by including unlabelled data. Therefore, the optimisation problem generally becomes finding i that minimises the SSL risk,
120
RESI (0)
Σ L(O Fi, Vi
H(O:ze).
121
where H/ is a term that does not depend on the labels and X a scalar weight which balances the labelled and unlabelled terms. In the literature, H can generally be seen surrogate of L. Indeed, 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.
123
125
2.2.3
Some examples of surrogates
126
recent overview of the recent SSL techniques has been proposed by van Engelen & Hoos (2020). In this work, we focus on methods suited for discriminative probabilistic model po ())=r) that approximates the conditional p(ylar). We categorised methods into two distinet sections, entropy and bonsistency-based.
127
128
3

---

130
Entropy-basee methods Entropy-basee methods aim to minimise term of entropy of the predic- 131
tions computed on unlabelled data. Thus. they encourage the model be confident on unlabelled data, implicitly using the cluster assumption. Entropy-base -aaeep methods can all be described as an expectation of I. under distribution Ty computed at the datapoint z:
132
133
H H xr)
F (2.8) [L,00; 0)]-
For instance, Grandvalet ( & Bengio 2004) simply use the Shannon entropy as (0;:a)) which can be
134
135
rewritten as equation (3) with Tx (z. y) 6² (e) (), where 8g is the dirac distribution in æ. Also,
136
pscudo-label methods, which consist in picking the class with the maximum predicted probability
137
as a pseudo-label for the unlabelled data (Scudder) 1965), can also be described as Equation 3 See
138
Appendix B for complete description of the entropy- based literature (Berthelot et al. 2019 2020
139
Xie et al. 2019; Sohn et al. 20200
Rizve et al. [021] Zhang et al. 2021a) and further details.
140
Consistency-based methods Another range of SSL methods minimise consistency objective that encourages invariant prediction for perturbations either on the data either on the model in order
141
142
to enforce stability on model predictions. These methods rely on the smoothness assumption. In this category. we cite IT-model from (Sajjadi et al.) 2016), temporal ensembling from (Laine & Aila
143
144
2.17). Mean-teacher proposed by (Tarvainen & Valpola 2017), virtual adversarial training (VAT)
145
from MMyato et al. (0118) and interpolation consistent training (ICT) from (Verma et al. 2019). We
148
remark that these objectives H are equivalent to an expectation of L (see Appendix B). The general
147
form of the unsupervised objective can be written as
(.Er, 2, 7)) S H();)) = Div(ff(z,)) .. per((f(z,.)) S ( [[(;; (e:;.))) ū)],
(4)
148
where fg is the predictions of the model, the Div is a non-negative function that measures the divergence between two distributions, θ is fixed copy of the current parameter 0 (the gradient is not propagated through 6), pert is perturbation applied to the model or the data and 0 S C1 S C2-
150
151
Previous works also remarked that H is an expectation of for entropy-miniiisation and pseudo- label (Zhu et al. 2022 Aminian et al.) 2022). We describe a more general framework covering further methods and provide with our theory an intuition on the choice of H.
152
153
154
2.3
Theoretical guarantees
155
The main risk of SSL is the potential degradation caused by the introduction of unlabelled data when
156
distributional assumptions are not satisfied (Singh et al.) 2008 SSchlkopf et al. 2012 Li & Zhou
2014). specifically in settings where the MCAR assumption does not hold anymore (Oliver et al.
157
158
2018 Guo al., 2020). Additionally, in (Zhu et al. 2022), the authors show disparate impacts of
159
paeudo-lbbelling on the different sub-classes of the population. To mitigate these problems, previous
180
works introduced the notion safe semi-supervised learning for techniques which never reduce learning
161
performance by introducing unlabelled data (Li & Zhou 2014 Kawakita & Takeuchi| [2014] Li et al.
162
2016: Gan et al. 2017 Trapp et al.] [2017] Guo et al. 2020). As remark by Oliver et al. (2018).
163
SSL performances are enabled by leveraging large validation sets which is not suited for real-world applications. Then, theoretical guarantees are required to use safely SSL algorithms. For this reason, in our work, we consider as safe an SSL algorithm that has theoretical guarantees that are similar or stronger than those of the complete case baseline. 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. More over|Schölkop et al. (2012) identify settings on the causal relation between the features x and the target where SSL may systematically fail, even if classic SSL assumptions hold. Our example of Figure [ also shows that classic SSL may fail to generalise in very benign setting with large number of labelled data.
164
165
186
167
168
169
170
172
Presented methods minimise a biased version of the risk under the MCAR assumption and therefore classical learning theory cannot be applied anymore, as we argue more precisely in Appendix C Learning over a biased estimate of the risk is not necessarily unsafe but is difficult to provide theoretical guarantees on such methods even if some works try to do so with strong assumptions
173
174
175
176
on the data distribution (Mey & Loog 2019. Section 4 and 5). Additionally, we remark that the choice of H. can be confusing as seen in the literature. For instance, Grandvalet & Bengio (2004) and
177
178
Corduneanu & Jaakkola (2003) perform respectively entropy and mutual information minimisation
whereas Pereyra et al. (2017) and Krause et al. (2010) perform maximisation of the same quantities.
4

---

180
2.4
Related works
Previous works already proposed safe SSL methods with theoretical guarantees. Unfortunately, so far these methods come with either strong assumptions or important computational burdens. Li & 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 with the assumption that the true model is accessible. However, if the distributional assumptions are not satisfied, improvement or degeneration is expected. [Sakai et al.] (2017) proposed an unbiased estimate of the risk for binary classification by including unlabelled data. The key idea is use unlabelled data better evaluate on the one hand the risk of positive class samples and on the other the risk of negative samples. They provided theoretical guarantees on its variance and generalisation error bound. The method is designed only for binary classification and has not been tested in a deep learning setting, It has been extended to ordinal regression in follow-up work (Tsuchiya et al. 202I). In the context of kernel machines, Liu & Goldberg (2020) used an unbiased estimate of risk, like ours, for a specific choice of H. Guo et al. (2020) proposed DS L, safe method that needs approximately solve a bi-level optimisation problem. In particular, the method is designed for different setting, not under the MCAR assumption, where there 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.
182
184
186
187
188
189
190
191
192
193
194
195
196
197
199
Sokolovska et al. [2008) proposed safe method with strong assumptions such that the feature space finite and the marginal probability distribution of z is fully known. Fox-Roberts & Rosten (2014) proposed an unbiased estimator in the generative setting applicable to a large range of models and they prove that this estimator has lower variance than the one of the complete case.
201
202
3 DeSSL: Unbiased semi-supervised learning
204
To overcome the issues introduced by the second term in the approximation of the risk for the semi- supervised learning approach, we propose DeSSL,, unbiased version of the estimator using labelled data to annul the bias. The idea here is to retrieve the properties of classical learning theory. Fortumately, we will see that the proposed method eventually have better properties than the com- plete case, in particular with regard to the variance of the estimate. The proposed DeSSL objective is
205
206
208
1 n L(0: Ris Ut)
A
nu
X
DessL(()) = n4 1=1
H(0:2:)
H(O
(5)
Thu
T1
209
210
Under the MCAR assumption, this estimator is unbiased for any value of the parameter A. For proof of this result see Appendix D
We prove the optimality of debiasing with the labelled data in Appendix
212
213
Intuitively, for entropy-based methods, H should be applied only on unlabelled data to enforce the confidence of the model only on unlabelled datapoints. Whereas, for consistency- methods,
214
215
H can be applied to any subset of data points. Our theory and proposed method remain the same whether H is applied to all the available data or not (see Appendix K
216
3.1
Does the DeSSL risk estimator make sense?
218
The most intuitive interpretation is that by debiasing the risk estimator, we get back to the basics of learning theory. This way of debiasing is closely related to the method of control variates (Owen
219
220
2013 Chapter 8) which is 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
221
222
estimator without modifying the expectation. Here, DeSSL can also be interpreted as a control variate
on the risk's s gradient itself and should improve the optimisation scheme. This idea is close to the
224
optimisation schemes introduced by Johnson & Zhang (2013) and Defazio et al. (2014) which reduce the variance of the gradients' estimate improve optimisation performance.
5

---

228
Another interesting way to interpret DeSSL is as constrained optimisation problem. Indeed, min- imising RDeSSL is equivalent to minimising the Lagrangian of the following optimisation problem:
227
min
(cc(0)
(6)
s.t. 1 Thu
228 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-minn mirrop-mmiimiiaiion, this program encourages the model to have the same confidence on the unlabelled examples
230
the labelled ones.
232
The debiasing term of our objective will penalise the confidence of the model on the labelled data. Pereyra et al. (2017) show that penalising the entropy in a supervised context acts as a strong regulator for supervised models and improves on the state-of-the-20 on common benchmarks. This comforts us in the idea of debiasing using labelled data in the case of entropy-minimisation Similarly,
233
234
235
236
the debiasing term pseudo-laber turns the problem into plausibility inference as described by (1976). Our objective also resembles doubly-robust risk estimates used for SSL in the context of kernel machines by Liu & Goldberg (2020) and for deep learning in a recent preprint Hu et al. 2022). In both cases, their focus quite different, they consider weaker conditions than MCAR, but very specific choices of H.
Barndorff-Nielse
238
240
3.2
Is R.DSSt (0) an accurate risk estimate?
Because of the connections between our debiased estimate and variance reduction techniques, we 243 have a natural interest in the variance of the estimate. Having a lower-variang, estimate of the risk
242
244 would mean estimating it more accurately, leading to better models. Similarly to traditional control variates (Ownn 2013), the variance can be computed, and optimised in X:
Theorem 3.1. The function À ((RDeSsL reaches its minimum for:
The Cov x. u), H(0;x))
Aopt
(7)
((H(0;z))
247
and Appt:
((RDeSSL(0)) (1- Th pi.n) V(Rcc(t)) s v(Rcc(()).
(8)
n
where PL.H Corr(L(O; v), H) (8:x)).
Additionally, V(RDessL (0) < ((Rco(() (0)) for all X between 0 and 2 A proof of this theorem is available Appendix E This theorem provides formal justification to the heuristic idea that H should be surrogate of I.. Indeed, DeSSL. is a more accurate risk estimate when is strongly positively correlated with I. which is likely to be the case when H is equal or equivalent to an expectation of L. Then, choosing positive a coherent choice. We also demonstrate Appendix [E] that L and H are positively correlated when L is the negative likelihood and // is the entropy. Other SSL methods have variance reduction guarantees and already has shown great promises in SSL, see Fox-Roberts & Rosten (2014) and Sakai et al. (2017). In purely supervised context, Chen et al.
249
251
252
253
255
257
2020> show that the effectiveness of data augmentation techniques lays partially on the variance reduction of the risk estimate. A natural application of this theorem would be tune À automatically Cov(L(0; (0; x, 8). H (0;x)) x)) with few labels
259
by estimating Aopt- In our case however, the estimation led extremely unstable unsatisfactory results. However, we estimate more accurately using the
261
test set (which is course impossible in practice) on different datasets and methods to provide
intuition the order of Nop' and the range of the variance reduction regime in Appendix M.2
3.3 Calibration
264 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

---

286
reliable predictions. A scoring rule S is function assigning a score to the predictive distribution Po(y|z) relative to the event l p(y]z)). S(po. (z, y)), where p(z, y) the true distribution (see e.g. Gneiting & 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 S(pe.p) Ep(S(pp. w)]l- A proper scoring rule is defined as a scoring rule such that ((e..) S S(p, p) (Gneiting & Raftery 2007). The motivation behind having proper scoring rules comes from the following: suppose that the true data distribution is accessible by our set of models. Then, the scoring rule encourages to predict pa = P. The opposite of a proper scoring rule can then be used to train model to encourage the calibration of predictive uncertainty:
267
269
270
271
273
275
L(0; x, y) = -S(p.. (z,, y)). Most common losses used to train models are proper scorings rule such as log- likelihood.
277
= Theorem 3.2. If S(pe. (x) = - L(00 y) is a proper scoring rule, then S' (z. V. r.) PT L(0; x. v) An( 1-r n4
Th "y (H)))))) is also proper scoring rule.
279
The proof is available in Appendix G and follows directly from unbiasedness and the MCAR assumption. The main interpretation of this theorem is that can expect DeSSL to be as well- calibrated as the complete case.
280
281
282
3.4
Consistency
We say that is consistent if c(0, 2 O when n + co, where d is a distance on O. The asymptotic properties of & depend on the behaviours of the functions L. and H. We will thus require the following standard assumptions.
283
284
285
The minimum 0* of R is well-separated: Assumption 3.4. The uniform weak law large number holds for both L and H.
Assumption& 3.3.
R(0) > R(0*).
287
288
Theorem 3.5. Under the MCAR assumption, Assumption
3.3 and Assumption
3.4
θ
289
arg min RDSSLL is consistent.
290
For proof of this theorem see Appendix G This theorem is a simple application of van der Vaart's (000) Theorem 5.7 proving the consistency of an M-estimator. Also, this result holds for the complete case, with À = 0 which proves that the complete case is a solid baseline under the MCAR assumption. Going further, we prove the asymptotic normality of DeSSL and showed that the asymptotic variance can be optimised with respect X.
292
293
294
295
Coupling of ny and nu under the MCAR assumption Under the MCAR assumption, nu and nu random variables. We have that r ~ B(x)) (i.e. any has the probability æ of being labelled). Then, with n growing to infinity, we have n my - x. Therefore, both ny and nu grow to mntn.
297
infinity and ny x-1, This implies n., (mi) and then when goes to infinity, both n. and my R. go to infinity too and even if n. >> n4-
298
300
3.5
Rademacher complexity and generalisation bounds
301
In this section, we prove an upper bound for the generalisation error of DeSSL. The unbiasedness of RASSL can directly be used derive generalisation bounds based on the Rademacher complexity
302
303
Barrllttt & Mendelson 2002), defined in our case
Σ e H( xI)) ]] (9)
X
R, = E(s.)egn
sup #ee
Σ
E (0:
E H(((0
+
TH
304
where are i.i.d. Rademacher variables independent of the data. In the particular case of X = O. we recover the standard Rademacher complexity of the complete case. We can then now bound the generalisation error of model trained using our new loss function.
305
306
307
Theorem 3.6. We assume that labels are MCAR and that both L and H are bounded. Then, there exists a constant k > 0, that depends on X, L. H, and the ratio of observed labels, such that, with probability at least for all 0 E e,
308
309
log(4/8) n
(0) < RoSSt (0) 22), + 1g.
(10)
7

---

310
The proof follows Shalev-Shwariz & Ben-David 2014 Chapter 26), and is available in Appendix U
4
Experiments
311
312
We evaluate the performance of DeSSL against different classic methods. The goal here is to compare DeSSL methods and their original counterparts. In particular, we perform experiments with simple SSL methods such as pseudo-label (PseudoLabel) and entropy minimisation (EntMIN) with varying
313
314
315
on MNIST (LeCun & Cortes, 2010) and CIFAR-I0 and CIFAR- 100 (Krizhevsky) (009) and compare them to the debiased method, respectively DeEntMin and DePseudoL We also compare Lseu and DePseudoLabel on five small datasets of MedMNIST (Yang et al. [)) with a
316
317
318
fixed A. The results of these experiments are reported below. In our figures, the error bars represent
319
the size of the 95% confidence interval (CT). Finally, we modified the implementation of Fixmatch (Shn et al. 2020) and compare it with its debiased version on CIFAR-10.
321
We also compare DeEntMin and DePseudoLabel to the biased version on large range of tabular datasets commonly used in SSL benchmarks (Chapelle et al. 2006; Guo et al. 2010). We do not
322
323
observe differences between the performance, see Appendix Finally, we show how simple it is to debias an existing implementation, by demonstrating it on the consistency-basee models benchmarked by Oliver et al.) 2018), namely VAT, IT-model and MeanTeacher on CIFAR- 10 and SVHN (Netzer et al. 2011). We observe similar performances between the debiased and biased versions for the differ-
324
325
326
327
ent methods, both in terms of cross-entrope 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 O
329
330
4.1 MNIST
331
MNIST is an advantageous dataset for SSL since classes are well-separated. We compare Pseudol.beel and DePseudoLabe for a LeNet-like architecture using 74 = 1000 labelled data on 10 different splits of the training dataset into a labelled and unla- belled set. Models are then evaluated using the standard 10, 000 test samples. We used 10% of ny the validation set. We test the influence of the hyperparameter À and report the accuracy, the cross-entropy and the expected calibration error (ECE, Guo et al. 2017) at the epoch of best validation accuracy, see Fig- ure and Appendix L In this example SSL and DeSSL. have almsst the same accuracy for all X, however, DeSSL. seems to be always better calibrated. To break the cluster assumption, we reproduced the same experiment on modified MNIST. Indeed,
DePsnudiLatel
PacudoLabe
332
333
cars
335
337
339
340
341
54
343
344
we had label noise by replacing the true label for 20% of the dataset with randomly sampled label, see Appendix L In this setting, DeSSL performs better for large À in terms of accuracy and also provides better calibration.
345
The influence of À on Pscudo-label and DePscudo-label for Lenet trained on MNIST with wi 1000: (Top) Mean test accuracy; (Bot- tom) Mean test cross-entropy, with 95% CL.
Figure 2:
346
347
4.2 MedMNIST
349
We compare PseudoLabel and DePscudoLabel 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 datasets it is likely that the cluster assumption no longer holds. We trained
350
351
352
a 5-layer CNN with a fixed À 1 and n; at 10% of the training data. We report in Table [ the mean accuracy and cross- enoss-y on 5 different splits of the labelled and unlabelled data and the number of labelled data used. We report the AUC in Appendix L DePseudoLabee competes with
353
354
Pseudol Label in terms of accuracy and even success when Lael'sLabellss accuracy is less than the
356
complete case. Moreover, DePseudol abel is always better in terms of cross-entropy, so calibration,
whereas PscudoLabel is always worse than the complete case.
8

---

Table I: Test accuracy and cross-entropy of Complete Case (CC), PscudoLabel (PL) and DePseu- doLabel (DePL.) on five datasets of MedMNIST.
DATASET
NL
CC
PL
DEPL
CROSS-ENTROPY
ACCURACY
PROSS-ENTROPY
ACCURACY
CROSS-ENTROPY
ACCURACY
DERMA
1000
1.95 0.09
68,99= 39=110 1.20
2.51 = 0.20
68.88 1.03
1.88
0.12
69.30 0.85
PNEUMONIA
585
1.47 0.04
83,94= 2.40
2.04
= 0,04
85.83:: 2.13
1.40
1: 0.06
84.36 = 3.79
RETINA
0.03
48.30 3.06
0.18
47.751
1.67
BREAST
0.80 + 0.04
76.15= 0.75
1.00 = 0.26
74.74+ 1.04
0.70
+ 0.03
76.67
1.32
BLOOD
1700
6.11 1 0.17
84.13 0.83
6.61
1 0.22
84.091 1.17
6.53
0.30
83.68
0.59
4.3 CIFAR
359
We compare PseudoLabel and DePseudoLabel on CIFAR- 10 and CIFAR-100. We trained CNN-13 from Tarvainen &
DePanttttace
Pseudolabe
Valpola (2017) on 5 different splits. For this experiment, we use 361
14 4000 and use the rest of the dataset unlabelled. Models are then evaluated using the standard 10, 000 test samples. For a
363
364
more realistic validation set, we used 10% of ny the validation
385
set. We test the influence of the hyperparameter and report the accuracy and the cross-entropy at the epoch of best validation
366
387
accuracy, see Figure 3 We report the ECE in Appendix M The
388
performance of both methods on CIFAR- 100 with nl 10000 are reported in Appendix M We observe DeSSL provides both better cross-entropy and ECE with the same accuracy for small A. For larger X, DeSSL. performs better in all the reported metrics. We performed paired Student's t-test to ensure that
389
370
372
155
373
our results are significant and reported the p-values in Appendix
Figure 3: Influence of X on Pseudo- label and DePseudo-label for CNN trained CIFAR with (Left) Mean test accuracy; (Right) Mean test cross woos-enttropy. with 95% CL
374
M The p-values indicate that for close to 10, DeSSL is often significantly better in all the metrics. Moreover, DeSSL for large provides a better cross-entropy and ECE than the complete case whereas SSL never does.
4000:
376
378
4.4
Fixmatch (Sohn al., 2020)
Table 2: 1st line: Accuracy, 2nd line: Worst class accuracy, 3rd line: Cross- entropy.
379
We debiased a version of Fixmatch, see Appendix N for further details. For this experiment, we use nl 4000 on 5
380
different folds.First we report that strong baseline using data augmentation reach 87.27% accuracy. Then, we ob- serve that on the debiasing method improve both accuracy and cross-entropy of this modified version of Fixmatch. Inspired by Zhu et al. (2022), we show that our method improved performance on "poor" classes more equally than the biased version. Indeed, DeFixmatch improves Fixmatch by 1.57% overall but by 4.91% the worst class. We report in Appendix N the accuracy per class of the different methods and the benefit ratio as defined by Zhu et al. (2022).
382
COMPLETE CASE
FIXMATCH
DEFIXMATCH
87.27 1: 0.25
93.87 1 0.13
95.44 1: 0.10 0.20 + 0.01
384
0.93
82.25
0.60 + 0.01
0.27 0.00
386
388
5 Conclusion
390
Motivated by the remarks of van Hngelen & Hoos (2020) and Oliver et al. (2018) on the missingness of theoretical guarantees in SSL, we proposed 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 the- oretical 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 terms of accuracy compared to its biased version but improves significantly the
391
392
393
394
395
396
397
calibration. There are several future directions open to us. We showed that Aopt. exists (Theorem (.1] and therefore our formula provides guidelines for the optimisation of X. Finally, an interesting im- provement would be to go beyond the MCAR assumption by considering settings with a distribution
389
mismatch between labelled and unlabelled data (Guo et al. 2020; Cao et al. 202 1
Hu et al. 2022).

---

References
402
Abadi, M., Agarwal, A., Barham, P., Brevdo, E., Chen, Z., Citro, C., Corrado, G. S., Davis, A., Dean, J., Devin, M., Ghemawat, S., Goodfellow, I., Harp, A., Irving. G., Isard, M., Jia, Y., Jozefowicz, R., Kaiser, L., Kudlur, M., Levenberg, J., Mané, D., Monga, R., Moore, S., Murray, D., Olah, C.,, Schuster, M., Shlens, J., Steiner, B., Sutskever, I., Talwar, K., Tucker, P., Vanhoucke, V., Vasudevan, V., Viégas, F,, Vinyals, O., Warden, P., Wattenberg, M., Wicke, M., Yu, Y., and Zheng, X. TensorFlow: Large-scale machine learning on heterogeneous systems, 2015. URL https: //wp:://www... tensorflox org/ Software available from tensorflow.org.
404
406
408
Ahfock, D. and McLachlan, G. J. On missing label patterns in semi-supervised learning. arXiv preprint arXiv:19044 (28,08899 2019.
410
Aminian, G., Abroshan, M., Khalili, M. M., Toni, L., and Rodrigues, M. An information-thhorrticee approach semi-supervised learning under covariate-shift. In International Conference on Artificial Intelligence and Statistics, pp. 7433-7449. PMLR. 2022.
412
Avramidis, A. N. and Wilson, J. R. A splitting scheme for control variates. Operations Research Letters, 1993.
415
416
Barndorff-Niclsen, O. Plausibility inference. Journal of the Royal Statistical Society: Series B (Methodological), 3832):003-123, 1976.
417
418
Bartlett, L. and Mendelson, S. Rademacher and Gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-483 2002.
420
Berthelot, D., Carlini, Goodfellow, I., Papernot, N., Oliver, A., and Raffel, C. A. Mixmatch:
A holistic approach to semi-supervised learning. Advances in Neural Information Processing Systems, 2019.
422
423
Berthelot, D., Carlini, N., Cubuk, E. D., Kurakin, A., Sohn, K., Zhang, H., and Raffel, C. ReMix- Match: Sepi-supervised learning with distribution matching and augmentation anchoring. Interna- tional conference on Learning Representations, 2020.
425
428
Cao, K., Brbic, M., and Leskovec, J. Open-world semi-supervised learning, 2021.
Chapelle, O., Schölkopf, B., and Zien, A. Semi-supervised learning. MIT Press, 2006.
428
Chen, S., Dobriban, E., and Lee, J. H. A group-theoretic framework for data augmentation. Journal of Machine Learning Research, 21(245):1-71 2020.
429
Corduneanu, A. and Jaakkola, T. On information regularization. In UAL UAT, 2003.
Cubuk, E. D., Zoph, B., Shlens, J., and Le, Q. V. Randaugment: Practical automated data augmen- tation with reduced search space. In Conference on Computer Vision and Pattern Recognition Workshops, 2020.
433
434
Defazio, A., Bach, F., and Lacoste-Julien, S. SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. Advances in Neural Information Processing Systems, 2014.
436
Fox-Roberts, P. and Rosten, E. Unbiased generative semi-supervised learning. The Journal of Machine Learning Research, 15(1):367-443, 2014.
438
439
Gan, H., Li, Z., Fan, Y., and Luo, Z. Dual learning-based safe semi-supervised learning. IEEE Access, 6:2615-2621, 2017.
440
441
Gneiting, T. and Raftery, A. E. Strictly proper scoring rules, prediction, and estimation. Journal of the American statistical Association, 102(477):359-77, 2007.
443
Goodfellow, I., Pouget-Abadie, Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville. A., and Bengio, Y. Generative adversarial nets. Advances in Neural Information Processing Systems, 2014.
Goodfellow, I., Bengio, Y., and Courville, A. Deep Learning, MIT Press, 2016.
10

---

448
Grandvalet, Y. and Bengio, Y. Semi-supervised learning by entropy minimization. Advances in Neural Information Processing Systems, 2004.
447
448
Guo, C., Pleiss, G., Sun, Y., and Weinberger, K. Q. On calibration modern neural networks. International Conference Machine Learning, 2017.
Guo, L.-Z., Zhang, Z.-Y., Jiang, Y., Li, Y.-.,, and Zhou, Z.-H. Safe deep semi-supervised learning for unseen-clan class unlabeled data. International Conference on Machine Learning, 2020.
451
452
Guo, Y., Niu, X., and Zhang, H. An extensive empirical study on semi-supervised learning. IEEE International Conference Data Mining, 2010.
Harris, C. R., Millman, K. J., van der Walt, S. J., Gommers, R., Virtanen, P., Cournapeau, D., Wieser, E., Taylor, J., Berg. S., Smith. N. J., Kern, R., Picus, M., Hoyer, S., van Kerkwijk, M. H., Brett, M., Haldane, A., Fernández del Río. J., Wiebe, M., Peterson. P.,
455
456
P., Sheppard, K., Reddy. T., Weekesser, W., Abbasi, H., Gohlke, C., and Oliphant, T. E. Array programming with
457
458
NumPy. Nature, 585:357-362, 2020. doi: 10.1038/s41 286-020-2649-11
459
Hu, X., NIu, Y., Miao, C.,, Hua, X.-S., and Zhang, H. non-random missing labels in semi- supervised learning. In International Conference on Learning Representations, 2022.
Johnson, R. and Zhang, T. Accelerating stochastic gradient descent using predictive variance reduction. Advances in Neural Information Processing Systems, 2013.
462
463
Kawakita, M. and Takeuchi, J. Safe semi-supervised learning based on weighted likelihood. Neural
Networks, 53:146-164, 2014.
465
Kingma, D. P., Mohamed. S., Rezende. D. J., and Welling, M. Semi-supervised learning with deep
486
generative models. In Advances in Neural Information Processing Systems, pp. 3581-3589, 2014.
467
Krause, A., Perona, P., and Gomes, R. Discriminative clustering by regularized information maxi-
468
mization. Advances in neural information processing systems, 23, 2010.
469
Krizhevsky, A. Learning multiple layers features from tiny images. Technical report, MIT, NYU,
2009.
Laine, S. and Aila, T. Temporal ensembling for semi-supervised learning. International Conference on Learning Representations, 2017.
472
473
J Cenn, Y. and Cortes, C. MNIST handwritten digit database. 2010. URL http::t/p//a.n.eeee lecun com/exdb/mnise
475
Lee, D.-H. Pseudo-Labed The simple and efficient semi-supervised learning method for deep neural networks. Workshop on challenges in representation learning. International conference on machine learning. 2013.
478
477
478
Li, Y.-F. and Zhou, Z.-H. Towards making unlabeled data never hurt. IEEE transactions on pattern analysis and machine intelligence, 37:175 1888 2014.
479
Li, Y.FF,, Kwok, J. T., and Zhou, Z.-H. Towards safe semi-supervised learning for multivariate performance measures. AAAI Conference on Artificial Intelligence, 2016.
481
482
Little, R. J. and Rubin, D. B. Statistical Analysis with Missing Data. John Wiley & Sons, 2019.
483
Liu, T. and Goldberg, Y. Kemel machines with missing responses. Electronic Journal of Statistics, 14:3766-3820. 2020.
485
Lundh, F, Ellis, M., al. Python imaging library (pil), 2012.
486
McKinney, W. al. Data structures for statistical computing in python. In Proceedings of the 9th
Python in Science Conference, volume 445, pp. 51-56. Austin, TX, 2010.
McLachlan, G. Estimating the linear discriminant function from initial samples containing a small
489
number of unclassified observations. Journal of the American statistical association, 72:403-40 1977.
11

---

491
Mey, A. and Loog, M. Improvability through semi cemi-supereised learning: A survey of theoretical results. arXiv preprint arXiv:1908.09574 2019.
492
493
Miyato, T., Maeda, S.-i., Koyama, M., and Ishii, Virtual adversarial training: A regularization
494
method for supervised and superviie learning. IEEE transactions on pattern analysis and machine intelligence, 41:1979- 1993, 2018.
495
496
Netzer, Y., Wang, T., Coates, A., Bissacco, A., Wu, B., and Ng, A. Reading digits in natural images with unsupervised feature learning. 2011.
497
498
Newey, W. K. and McFadden, D. Large sample estimation and hypothesis testing. Handbook of econometrics, 4:2111-2245, 1994.
499
500
Oliver, A., Odena, A., Raffel, C., Cubuk, E. D., and Goodfellow, I. Realistic evaluation of deep semi supervise learning algorithms. Advances in Neural Information Processing Systems, 2018.
502
Owen, A. B. Monte Carlo theory, methods and examples. 2013.
503
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z.,
504
Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang, E., Deto,, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, I.., Bai, J., and Chintala, S. PyTorch: An imperative style, higl-performance deep learning library. Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché-Buc, F., Fox, E., and Garnett, R. (eds.), Advances in Neural Information Processing
505
506
507
508
Systems 32. Curran Associates, Inc., 2019. URL http://papers pempperssneuripee nwwrinurripp.. httpppps.ccppppe/p/pppppppp -abrriig-iibrrr...
510
pdf
511
Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., et al. Scikit-leam: Machine learning in python. Journal of machine learning research, 12(0ct):2855-2830, 2011.
513
514
Pereyra, G., Tucker, G., Chorowski, J., Kaiser, t.., and Hinton, G. Regularizing neural networks by penalizing confident output distributions. Workshop track, International Conference Learning Representations, 2017.
516
517
Pham, H., Dai, Z., Xie, Q. and Le, Q. V. Meta pseudo labels. Conference on Computer Vision and Pattern Recognition, 2021.
Rizve, M. N., Duarte, K., Rawat, Y. S., and Shah, M. In defense of pseudo-labeling: An uncertainty-
520
aware pseudo-label selection framework for semi-supervised learning. International Conference on Learning Representations, 2021.
Sajjadi, M., Javanmardi, M., and Tasdizen, T. Regularization with stochastic transformations and perturbations for deep semi-supervised learning. Advances in Neural Information Processing Systems, 2016.
523
Sakai, T., Plessis, M. C., Niu, G. and Sugiyama, M. Semi-supervised classification based on classification from positive and unlabeled data. International conference on machine learning. 2017.
526
Schölkopf, B., Janzing, D., Peters, J., Sgouritsa, E., Zhang, K., and Mooij. J. On causal and anticausal learning. Internation conference on machine learning, 2012.
529
530
Scudder, H. Probability of error of some adaptive pattemn-recognition machines. IEEE Transactions Information Theory, 11:363- 371, 1965.
Seeger, M. Learning with labeled and unlabeled data. Technical report, 2000.
Serre, D. Matrices. Theory and Applications (Second edition). Springer, 2010.
Shalev-Shwartz. S. and Ben-David, S. Understanding Machine Learning: From Theory to Algorithms. Cambridge university press, 2014.
535
596 Singh, A., Nowak, R., and Zhu, Unlabeled data: Now helps, now doesn't. 't. Advances Neural Information Processing Systems, 2008
12

---

538
Sohn, K., Berthelot, D., Li, C.-L., Zhang, Z., Carlini, N., Cubuk, E. D., Kurakin, A., Zhang, H., and Raffel, C. FixMatch: Simplifying supervvied learning with consistency and confidence. Avances in Neural Information Processing Systems, 2020.
539
541
Sokolovska, N., Cappé, O., and Yvon, F. The asymptotics of semi cemi-supervised learning in discrimina- tive probabilistic models. In International Conference on Machine Learning. 2008.
542
543
Tarvainen, and Valpola, H. Mean teachers are better role models: Weight-averaged consistency
544
targets improve semi-supervisee deep learning results. Advancer in Neural Information Processing Systems, 2017.
545
546
Trapp M. Madl, T., Peharz, R., Pernkopf, F., and Trappl, R. Safe semi-supervised learning of sum-product networks. Conference on Uncertainty Artificial Intelligence, 2017.
547
548
Tsiatis, A. A. Semiparametric theory and missing data. Springer, 2006.
549
Tsuchiya, T., Charoenphakdee, N., Sato, I., and Sugiyama, M. Semisupervised ordinal regression
550
based on empirical risk minimization. Neural Computation, 33:3361-344 2021.
551
van der Vaart, A. W. Asymptotic statistics. Cambridge university press, 2000.
552
van Engelen, J. E. and Hoos, H. H. A survey on semi-supervised learning. Machine Learning, 109: 373 440, 2020.
553
554
Van Rossum, G. and Drake Jr. F. L. Python reference manual. Centrum voor Wiskunde en Informatica Amsterdam, 1995.
555
556
Verma, V., Kawaguchi, K., Lamb, A., Kannala, J., Bengio, Y., and Lopez-Paz, D. Interpolation
557
consistency training for semi-supervised learning. International Joint Conference on Artificial Intelligence, 2019.
558
559
Waskom, M., Botvinnik, O., O'Kane, D., Hobson, P., Lukauskas, S., Gemperline, D. C., Augspurger,
580
T., Halchenko, Y., Cole, J. B., Warmenhoven, J., de Ruiter, J., Pye, C., Hoyer, S., Vanderplas, J.. Villalba, S., Kunter, G., Quintero, E., Bachant, P., Martin, M., Meyer, K., Miles, A., Ram, Y., Yarkoni, T., Williams, M. L.,, Evans, C., Fitzgerald, C., Brian, Fonnesbeck, C., Lee, A.,
581
562
563
and Qalieh, A. mwaskom/seahorm: v0.8.1 (september 2017), September 2017. URL https 7/doi /dgoi.or//10 1ttg//...0000 10.....22///eooooo 9888858
564
565
Wei, C., Shen, K., Chen, Y., and Ma, T. Theoretical analysis of self-training with deep networks on unlabeled data. In International Conference on Learning Representations, 2021.
567
Xie, Q. Dai, Z., Hovy, E., Luong, M.-T., and Le, Q. V. Unsupervised data augmentation for consistency training. Advances in Neural Information Processing Systems, 2019.
569
Yang, J., Shi, R., and Ni, B. MedMNIST classification decathlon: lightweight AutoMI. benchmark for medical image analysis. In JEEE 18th International Symposium on Biomedical Imaging (ISBI),
570
571
pp. 191-195, 2021a.
Yang, J., Shi, R., Wei, D., Liu, Z., Zhao, L., Ke, B., Pfister, H., and Ni, B. MedMNIST v2: A large-scale lightweight benchmark for 2D and 3D biomedical image classification. arXiv preprint arXiv:21 10. 14795, 2021b.
573
574
575
Zhang. B., Wang, Y., Hou, W., Wu, H., Wang, J., Okumura, M., and Shinozaki, FlexMatch: Boost- ing semi-supervised learning with curriculum pseudo labeling. Advances in Neural Information Processing Systems, 2021a.
577
Zhang. H., Cisse, M., Dauphin, N. and Lopez-Paz, D. mixup: Beyond empirical risk minimization.
579
Internation Conference on Learning Representations, 2017.
580
Zhang, S., Wang, M., Liu, S., Chen, P.-Y., and Xiong, J. How unlabeled data improve generalization
581
in self-training? A one-hidden-layer theoretical analysis. In International Conference on Learning Representations, 2021b.
583
Zhu, X., Ghahramani, Z., and Lafferty, J. D. Semi-supervised learning using Gaussian fields and harmonic functions. International conference machine learning, 2003.
585
7hu, 7.,, Luo, T., and Liu, Y. The rich get richer: Disparate impact of semi-supervised learning. In International Conference Learning Representations, 2022.
13

---

Checklist
587
588
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
590
contributions and scope? [Yes]
881
(b) Did you descrihe the limitations of your work? [Yes) See section
582
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Theoretical work
593
594
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
586
2. If you are including theoretical results...
587
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
598
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendices
589
3. If you ran experiments...
600
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material or URL)? [Yes] code and instructions to run Fixmatch.
602
603
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendices
604
605
(c) Did you report error bars (e-g.. with respect the random seed after running experi- ments multiple times)? [Yes] Confidence intervals all figures.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] An estimation in Appendix
608
609
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
610
(a) your work uses existing assets, did you eite the creators? [Yes] See Appendix
611
(b) Did you mention the license of the assets? [Yes]
612
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
Code
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
615
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
617
618
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
620
621
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
622
623
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14

---

625
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 drawn from two ID uniform laws with overlap. We used and a confidence threshold for Pseudo-label using a stochastic gradient descent (SGD) optimiser with a learning rate of 0.1.
627
628
0.70. We optimised the model's weights
Figure 4: Data histogram
True distribution
True distribution
Complete
Complete
Pseudo-label
DePseudo-label
DeEnthin
41100
3.10
228
336 1902
3202 1550
2702
3000
1550
2508
3000
20e00
stees
Figure 5: 4-layer neural net trained using SSL methods on ID dataset drawn from two uniform laws. (Top-left) Posterior probabilities p(1 (æ) of the same model trained following either complete case (only labelled data), Pseudo-label our Dalseudo-label. (Top-right) Same for EntMin and DeEntMin (Bottom-left) Training cross- entropy for Pseudo-label and DePseudo-lahel (Bottom-right) Training cross-entropy for EntMin and DeEntMin
15

---

630
B
Details on surrogates and more examples
631
We provide in this appendix further details on our classification of SSL methods between entropy- based and consisteney-bant (see Section 2.2.3) We detail general framework for both of these methods' classes. We also show how popular SSL methods are related to our framework.
632
633
634
B.1
Entropy-based
635
We class as entropy- -baedd, methods that aim to minimise term of entropy such as Grandvalet & Bengio (2004) which minimises Shannon's 's entropy or pseudo-label which is a form of entropy, see
638
637
Remark E.5 These methods encourage the model be confident on unlabelled data, implicitly using
638
the cluster assumption. We recall those entropy-based based methods can all be described as an expectation
639
of L under a distribution πT computed at the datapoint x::
(0;; x²) = E. (a.5) [10 0)]
(11)
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 Ta (#. ū) = 82 (o) (ū] Recently, Lee (2013)
641
encouraged the pseudo-labell method for deep semi-supervised learning. Then, Riive et al. 2021 recently improved the pseudo-label selection by introducing an uncertainty- -awae mechanism on the confidence of the model concerning the predicted probabilities. |hham et al.] (2021) reaches state-of-the-art on the Imagenet challenge using pseudo-labels on a large dataset of additional images.
643
644
645
648
B.2
Pseudo-label and data augmentation
Recently, several methods based on data augmentation have been proposed and proven perform well on a large spectrum of SSL tasks. The idea is to have a model resilient to strong lata-auumentation of the input (Berthelot et al., 2019 2020 [Sohn et al. 2020 Xie et al.) 2019 Zhang al. [201aa) These methods rely both on the cluster assumption and the smoothness assumption and are at the border between entropy-basee and consistency-basee
648
650
651
methods. The idea to have the same prediction
652
for an input and an augmented version of it. For instance, in Sohn et al. (2020), we first compute labuds 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 strongly augmented version of z. In Xie al. (2019), the method is little bit different we minimise the cross entropy between
653
654
655
658 the prediction of the model on and the predictions of an augmented version. In both cases, the
657
unsupervised part of the risk estimator can reformulated as Equation T1
658
Fixmatch: In Fixmatch, Sohn et al. (020),, the unsupervised objective can be written as:
H(0;z) x) = 1 [mmx (ylp)))) > =]T,(0; x2, arg max (a(y)=1))
(12)
y
where i is fixed copy of the current parameters 0 indicating that the gradient is not prop- agated through it, In is a weakly-augmented version of x and Ø2 a strongly-augmenter one. Therefore, we write H as an expectation of L on the distribution (²,
680
662 5r, (ar max, polaler) (5) [max, pa(y)z1) r].
663
UDA: In UDA, Xie 2019), the unsupervised objective can be written as:
H(0:z) = Σ Pa(ula)(((:m11..))
(13)
where i is fixed copy of the current parameters 0 indicating that the gradient is not propagated 6es through it and v1 is an augmented version of x.. Therefore, we write H as an expectation of I. on the (ū,)) Ø) = dz, (7))).
664
distribution (ū,
16

---

687
Recently, have been proposed in the literature Zhang et al. (2)21a) and Rizve et al. (2021) The former is an improved version of Fixmatch with variable threshold 7 with respect to the class and the training stage. The latter introduces measurement of uncertainty in the pseudo-labelling
Others:
688
670
step to improve the selection. They also introduce negative pseudo-labels improve the single-label
classification.
672
B.3
Consistency-based
678
Consistency-base methods 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 T. but are equivalent to an expectation of L. For all the following methods we can write the unsupervised objective H such that:
675
(LE 9) & H(0;)) x) & (2.) [[0 0)),
(14)
677
with 0 S C1 S C2.
678
Indeed, consistency- methods minimise an unsupervised objective that is a divergence between the model predictions and modified version of the input (data augmentation) or perturbation the model. Using the fact that all norms are equivalent in a mnite-dimensional space such as the space of the labels, we have the equivalence between a consistency-based H and an expectation L.
679
681
The virtual adversarial training method proposed by MMyyato al. 2018 impactful perturbation T Tady to add to z. 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).
VAT
generates the most
683
H ((; x)) Div(f .), fo(a Todv
where the Div is non-negative function that measures the divergence between two distributions, the 686 enossyy or the KL divergence for instance. the divergence function is the cross- cross-entropy, is If the objective function is the KI.
straightforward to write the unlabelled objective as Equation 3 688 divergence, we can write the objective as
(15) with T, (.. 5,.( (Zg((()).. Therefore, variation of H with respect to O are the same as (8+r.8) [L;  , 7)]. VAT is also method between consistency-batt and entropy-based methods as long as we use the KL-divergence or the cross-entropy as the measure of divergence.
H(#: x) = Ex, (.+r.)) [(0; 2, 0)] - Ex_ (L (1,
689
690
692
approach proposed by Tarvainen & Valpola, 2017) where pseudo-labels are generated by teacher model for student model. The parameters of the student model are updated, while the teacher's 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
Mean- Teacher A different form of pseudo-labelling is the
694
696
687
H x) = E(po(elz) Po p)(x))))
where i are the fixed parameters of the teacher.
699
II-Moee The I-Models are intrinsically stochastic models (for example a model with dropout) encouraged to make consistent predictions through several passes of the same in the model. The
701
SSL loss is using the stochastic behaviour of the model where the model fo and penalises different predictions for the same x (Sajjadi et al. 2016). Let's note fo fo(x, -): and fo(x, two passes of through the model fa- A generic form of the unsupervised part of the risk estimator is then
702
703
H(:: x) = Div(fo(x, fa
(16)
704
where Div is measure of divergence between two distributions (often the Kullback-L -Libblr diver- gence).
17

---

706
Temporal ensembling Temporal ensembling (Laine & Aila 2017) is form of II-Model where
707
we compare the current prediction the model on the input a with an accumulation of the previous passes through the model. Then, the training is faster as the network is evaluated only once per input on each epoch and the perturbation expected to be less noisy than for IT-models.
709
710
ICT Interpolation consistency training (Verma et al. 2019)) is an SSL method based on the mixup operation (Zhang et al. 2017). The model trained then consistent to predictions at interpolations. The unsupervised term of the objective is then computed on two terms:
711
H(0; 11, x2) Div (fe(az) + (1 - a)),, afg(z .) + (1 ())2
(17)
713
with a drawn with from a distribution (aa a). With the exact same transformation, we will be able show that this objective is equivalent to form of expectation of L.
714
18

---

C
On the semi-supervised bias
715
716
We provide in this appendix a further explanation of the risk induced by the SSL bias as introduced
717
in Section 2.3
718
Presented methods minimise a biased version of the risk under the MCAR assumption and therefore classical learning theory does not apply anymore,
719
((R)s((0)) = E[ x., (OE + (0)).
(18)
720
Learning over a biased estimate of the risk is not necessarily unsafe but is difficult to provide theoretical guarantees on such methods even if some works try to do so with strong assumptions on the data distribution (Mey & Loog 2019 Section and 5. [Zhang et al. 202Tb). Previous works proposed generalisation error bounds of SSL methods under strong assumptions on the data distribution or the
721
722
723
724
true model. We refer the survey by Mey & Loogg (2019). More recently, WWi al. (2021) proves an upper bound for training deep models with the pseudo-label method under strong assumption. Under soft assumptions, /Aminian et (2022) provides an error bound showing that the choice of H is crucial to provide good performances.
725
726
727
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:
729
730
731
Regularisers have a vanishing impact in the limit of infinite data whereas SSL usually do not in the proposed methods, see Equation [8] A solution would be to choose with respect of the number of data points and make it vanish when n goes to infinity. However, in most works, the choice of is independent of the number of n or ny (Oliver al., 2018 Sohn et al. 2020).
732
733
734
735
736
One of the main advantages of regularisation to turn the learning problem into a "more convex" problem, see (Shalev-Shwartz & Ben-David (2014) Chapter 13). Indeed, ridge regularisation will often turn a convex problem into strongly-convex problem. However, SSL faces the danger to turn the learning problem as non-convex as previously noted by
738
739
740
Sokolovska et al. (2008).
741
The objective of regulariser is to bias the risk towards optimum with smooth decision functions whereas entropy- -based based SSL will lead to sharp decision functions.
743
Regularisation usually does not depend on the data whereas H does in the SSL framework.
744
A entropy bias has been actually used by Pereyra et al. (0177) as a regulariser but as entropy maximisation which should has effect that is the opposite of the SSL method introduced by Grandvalet & Bengio (2004), the entropy minimisation.
746
19

---

D Proof that DesSL (f) is unbiased under MCAR
747
748
Theorem D.1. Under the MCAR assumption, (DESSL(0) is an unbiased estimator of R(().
As a consequence of the theorem, under the MCAR assumption, Roc((0 is also unbiased as special case of (Dsss) for À = 0
749
Proof:
We first recall that the DeSSL risk estimator RDESSL is defined for any by
1
DDSSSL(0) =
L(O; 24, 34) +
H(0:
H(O
T4 1=1
1=1
(19)
L(0 Fz 9i) +
Ti
H(0:z:))
nu
752
By the law of total expectation:
([R) EE, (En(E [[
753
As far as we are under the MCAR assumption, the data (x, y) and the missingness variable are independent thus, E, Ez.y (R) Er [Esy|RDesssL(1]]
We focus on Ex,w R.v.RR (0)] First, we replace RDOSSL (0) by its definition and then use the linearity of the expectation. Then,
755
756
E (e)
L(O; 24, 91)
+
H(0;x+)
H(O; x.x)
by definition
Th
1=1
1=1
n1
E [
24 21]
[H(;a:)))
(H(00;;))
by linearity
The couples (I,, 34) are i.i.d. samples following the same distribution. Then, we have
1
En Rresst (0))
E(L(0=2,v)]
[[H(0x)))
E [[H(0:x)) i.idd samples
The
1=1
= L [0; x,11
R(0).
758 Finally, we have the results that, RDDSSL(() is unbiased as R(0) is a constant,
EjRDessI (0)) = E [Ex. (DDSS (0)]r] E, [R(0)] R())).
(20)
20

---

759
E
Proof and comments about Theorem 3.1
Theorem 3.1
The function À + ((RDessL(0))) reaches its minimum for:
Tu Cov C. v, y). H()))))
Appt
(21)
((H())))
781
and
Bu pL.u)) v(Rcc(0)) ((DDessL(0)))) (1-
n
(22)
((Roc(()),
762
where PL,H = Corr(L(O; v), (0;x))
783
Proof:
For any X E R,we want to compute the variance:
(0))).
Under the MCAR assumption, and are both jointly independent of Also, the couples (Ii, ri) are independent. Therefore, we have
785
1 1-ri ri
(0))))
Σ V (m:n))p((aa))))
L(0, F2, 21, +
ii.d samples
n4
nu
n4.
Ti
L(0, 24, y1) +
(1 (1-7% Pi
Ti
H 2.))
H
(x,z) v) and r independent
T4
71u
786
Using the fact that the couples (x,, Ui) are i.i.d. samples following the same distribution, we have
v(R (0)l) =
Σ V (..))~((a.))
L(O, x, v) A
1 - Ti
H(0,x)
Th
11u
T1
= Σ r?
V(L(O, x, v)) + X2
1-Ti
Ti
((H(0,)))
using covariance
nu
1 1--r rs
Fi
+ 21
Cov(L(O, y), H()
m
Now, we remark that the variable is binary and therefore 72 r,, (1-r22 1- and r(1-r) 0. Using that and simplifying, we have
768
(()Dess((0)r)) Σ Viv(L B)) + 11 r:)mg + rin ((H(0.z))
nf
21 ri Cov(L((, y). H (0,x))
2
Finally, by summing and simplifying the expression (note that ny + n)), we compute the expression variance,
770
v (RDess((0)))) = - V(L x, + X2 n
v(H(0,x)) 2A w)) Tu
m
So V (f))) is quadratic function in À and reaches its minimum for Aopt such that: The Cov (I((O, v. y), H(0, x))
Aopt
(0)))
21

---

772
And, at Aope the variance of RDSSS (f)(r) becomes
1 -((((,,,,v) x,
na Cov y). H (0, ())
((RDess((0)r)
TH
n ((H(0,))VVLLCC a y))
1 V(I(O, x, u)) (1
nu Corr(L( z. v). H(0, x))²
-11 Thu P2,
1 v(L(0,x,g))
1
773
Remark E.1. H is perfectly correlated with L (pI.1 = 1), then the variance of the DeSSL estimator equal the variance of the estimator with no missing labels.
Remark E.2. Is it possible to estimate Aopt in practice ? The data distribution p(z, y) being unknown, the computation of Aont is not possible directly. Therefore, we need to use an estimator of the covariance Cov(I(O; y), (0:))) and the variance VV (0; x)) (See Equation 23p. Also,
776
778
have to be careful not to introduce a new bias with the computation of Aopt. indeed, if we compute
it using the training set, Aopt becomes dependent of x and y and therefore DDSS. (e))))((0)rr) becomes biased, A solution would to use a validation dataset for its computation. Another approach is to compute it using the splitting method (Avramidis & Wilson 1993). Moreover, the computation of
780
782
Aopt is tiresome and time-consen consumnnn in practice as it has to be updated for every different value of 6 each gradient step.
1 1. - T.0)) (()))
R opt
(23)
1 (H(0
where H[0)= = E (0;;;; and T.(0) Em T.(0; yk)
784
785
Remark E.3. About the sign of À As explained in the article, the theorem still has a quantitative merit when it comes choosing X, by telling that the sign of X 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 ongllikelihood is negatively correlated with its entropy and therefore it justifies the choice of X >> 0 in the entropy minimisation.
786
786
790
Proposition E.4. The log-likelihood of the true distribution logl(y))) is negatively correlated with its entropy Hg (p(ū)=))) = -E Eggpp(lz)) [(gg((})=)]
792
Cov(logr(ylx)) Happ:ull)),HHHH(ipa) Ha(p(ū)))) < 0
(24)
Proof.
Cov(logp(uls) Hz(p((lz)) [=y.logg((//)))) |/tp:///000..ttloooooo/////////0
(25)
[log p(7]+)]]
(26)
(27)
793
By the law of total expectation, we have that E,, (g Pog then
Ev, |log p(y p( (log [x]]
(28)
E [og
(29)
(30)
794 On the other hand, also with the law of total expectation, F oo
795 E. (Eyy pog so
Po
Bopeel E (e
Jensen's inequality
2 E, E..glogg(yy))
total expectation law
22

---

796
Finally, we have the results.
Cov(ogpptolr,, - E Ex.g [oggllll)) p(y]z))²
Remark E.5. We can also see the Pseudo-label form of entropy. Indeed, modulo the confidence selection on the predicted probability, the Pscudo-label objective is the inverse of the Rényi min- entropy:
798
Hx) = max log p(y|2:
23

---

F
Why debiasing with the labelled dataset?
801
802
We remark that the debiasing can be performed with any subset of the training data, labelled and unlabelled. The choice of debiasing only with the labelled data can be explained both intuitively and
803
804
computationally in regard to the Theorem 3.1 Intuitively, the debiasing term penalises the confidence on the labelled datapoints and then prevents the overfitting on the train dataset. As remarked in section
805
3.1 Pereyra et al. (2017) showed that penalising low entropy models acts as strong regulariser 808
807
in supervised settings. This comforts the idea of penalising low entropy on the labelled dataset, L.e. debiaising the entropy minimisation with the labelled dataset. Considering Pseudo-Label bbased
808
809
methods, the objective for the labelled data to predict the correct labels with moderate confidence.
This is also similar to the concept of plausibility inference described by [BanndoriiNNelsenn (976).
In regard to Theorem 3.1 show that the optimum choice of subset for debiaising is either only the labelled data or the whole dataset and both are equivalent.
812
We consider subset A of the training set. We defined a as follow:
{
1/|A|
if o4 E AA otherwise
0
a13
The unbiased estimator is then:
RDESSLLA(0)- = 1 Σ
L(0; 2,, 100;
vi)
A Ths
H(O:
Σ
a (0)
(31)
Th
nh
815
We compute the variance of this quantity as in the proof of Theorem 3.1 and show that:
(0)))) Σ (I((),,,))+** n
ai (1-ri nu
2 V(H v(H(),)))) -X ny
22 Ti0l
Cov(L(O, (0,,0,,,))) (0,
(32)
Suppose that no labelled datapoints are in A. Then, the last term of the variance is null. Hence, 817 having no labelled datapoints in A leads to a variance increase. We also remark that debiasing with the entire dataset is equivalent that debiasing with the labelled datapoints. Indeed
72
n
ReSSI (0)
L(0; 3i, 3i)
+
a(0;
H a.))
nu
m2
nu
L(O; 100 oi
mi) +
H(00
H (00
11
Tu
Any
Any
T(O:; (0, 3n uR)
+
H(0:z:).
nu
819 which is equivalent to debiasing with only the labelled dataset by replacing À by A
At this point we can still sample a random subset composed of / labelled datapoints and unlabelled 821 datapoints. Therefore a, = 1/(1 + w) (a, E A). we show the following that the optimum choice of the couple (4, u) are (m,, 0) and (nu, ny)) so only the labelled or the whole dataset.
We sample/ labelled and unlabelled datapoints to debiased the estimator, by simplifying the term in the sum of Equation 32 as follow:
if a;; E A and r, 0
14u
1- Fá
1
if m. E A and r; 1
ai
(L+))
if x; & A and r,
x; & A and r
24

---

823
Then, by summing the term and simplifying, we get:
((DDessL())p (0)rr) = T4
1 v(L(0, 1)) +
Ba u
v(H(0,x))
nu (+
(1+u)² u)²
n
22 14 + u)
Cov(L(0, (, H()
1 V(L(O, m)) + Xa nu +
V(H(O,))) 22 Cov 2),,
T4
Tuu 1+u
14(1 + u)
We want to minimise (0))r) with respect to (A,1, u). V(RDessi (0)lr) reaches is mini- mum in À at
Cov(L(O, x u). H(),)))
Aopt
Ty nh u uu
((H(6,z))
Then,
= V(L(O, (0)))
nu
Cov(L(0, x. y). H0, ((H(0,x))
71 (nu + u)
825 We now want to minimise with respect to S u S nu and I ny. We can easily show that the (nu u [)( u) reaches its mininum for or nhe and for both value:
(0))) V(L(B, x. v)) ny nu +1
Thu
Cov v), H(O,
n2
((H
827
Then (n + 1) a increasing function, then reaches its maximum ng. So finally, the optimal choices for the couple (n4, 0) and (n, ny). We showed that these couples are equivalent.
25

---

829 G Proof of Theorem 3.2
830
Theorem 3.2
Sppo (z, y)) -00 y) a proper scoring rule, then (' (z, v,r) ( n L(0; v) And 1-r
_
(0;(0;))
(33)
nu
831
also a proper scoring rule.
Proof. The scoring rule considered in our SSL framework is:
(pe, (z)
m L(0: x. v) + Aml 1- nu
(((0)))
n4
The proper scoring rule of the fully supervised problem is S(pe, (2, (.,,)))) L(0; x y)
832 Let p be the true distribution of the data y. Under MCAR, is independent of a and y, then 833 p(a, v)r) p(r)p(2,))) v).
/ p(a, (po. ()) du dy dr
S'p,,
/ pla, (oo.v)s((55S (po. (z. U, r)) dx dy dr
by independence
rm / p(zz, v)((r)
= L(0,x,)) + An( 1-r
=(;(( de dy dr
The
Tu
rn dr [ p(a,y) (fr())
L(0;,, x. y) dx dy
2.y
ni
An /
(frre)
(1 1 (1rr _) dr
p(aN))
H(0;z) dx dy
Ja.
n4
n1
=- 2.91
p(x, y): y) dx dy
S(po,r) p))
Therefore, if S(po. (x., 3)) L(0; y) is proper scoring rule, then
835 mathcal.S' (Ir, y, r)) = -( L(0; x, y) + Are( -- m HH x)) is also a proper scoring rule.
26

---

H Proof of Theorem 3.5
837
838
Assumption
3.3
the minimum l of R is well-separated.
inf R(0) R(0*)
(34)
B:d(0 8)2c
839
Assumption 3.4
uniform weak law of large numbers holds for function L if:
sup lE
L(0, L(0. v.) ([ y) 2
(35)
Theorem 3.5
Under assumption A and assumption B for both L and H. 0 arg min ReSLL is asymptotically consistent with respect to n.
841
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, arg min R is asymptotically consistent with respect to Assumption remains unchanged as we have M-estimators of the same R. We now aim to prove that under assumption B for both L and H, we have the assumption B on 0 - L(0; 4r, y) + X(1
844
H (0; .)).
m2
847
Lemma H.1. If the uniform law of large number holds for both L and H, then it holds for - L(0; x. v) X(1 By 12 W)H(O) (0;z).
819
Proof. Suppose assumption for L, then the same result holds we replace n with ny as n and my coupled by the law r. Indeed, when grows to infinity, ny too and inversely. Therefore,
n1
L(0:2,,))) v.) E[ x, v)] 40
sup IE0
TH
Now, suppose we have assumption for H, then we can make the same remark than for L. Now, we 852 have to show that:
sup 8EB
m L(0,I, + An
(1-r r
H(0;
v)
Bg
n2
T4.
1=1
We first split the absolute value and the sup operator
m L(0;,r,) + An
1--r r
H(0;2) x)) E[L(0;x,V))
sup dE+
11
2m1
sup 820
rn
L(0
[E[L(0; w)]l
+
An
1-r
H (0;:z)
Th
Th
711
t=1
1=1
1
1-r
sup
L(0;
ELL(0; 4)1
+ sup AEB
An
H (00xz)
838
111
t=1
The
m
0
854
So we now have to prove that the second term also converging to 0 in probability. Again by splitting the absolute value and the sup, have
sup 0
An
1-r
_ ni
H(0;z)) x)
sup 0c8
r)n H(O;z)
H(0;z)
71
Thu
n
The
m
27

---

856
Then we have that,
sup A50
H()xz)
(0;
Th
A n
sup Ag0
(1 - r):
E|H((:x.
rH(0:x) (8: x. w01
uhu
i=1
i=1 H(0x)) (lH(0; m\1
Bg
sup AE
2(0:z) (1;
1
==1
X B
sup d50
2(0:2) E[H(0;
+ sup OE
H(0;0) EIH
Tbu
74
1= 1+1
E
E>
857 Thus,
L(0;z, An (1-r1 I
sup 6
x(0:z)-
y)]
B 0
71
T4
n
n4
858
And now just have to apply the results of van der Vaart (2000) Theorem 5.7) have the asymptotic
859
consistent of arg min D.SSL
860
861
Remark H.2. A sufficient condition on the function H verify assumption B, the uniform weak law of large numbers, is to be bounded (Newey & McFadden 1994 Lemma 2.4). For instance, the entropy E, po (u/=r) log(po (y]æ:) bounded and therefore, the entropy minimisation
863
884
asymptotically consistent.
28

---

885 I Asymptotic normality of DeSSL
886
In the following, study modified version of the objective simplify the proof. Let consider the following DeSSL objective L' L'(0; [0;0 v) + À + - $ (0; which has the same properties than the original one (unbiasedness, variance reduction property, consistency and benefit from generalisation emror bounds). The idea is replace ny with wn to simplify the expression. The value ny converges to mn then the following Theorem should hold with the true DeSSL objective.
868
870
We define the cross-covariance matrice between random vectors VL x, y) and V (H( x) as Ko (t, Cov(VV((0 x, v)i, (H (0;))))
872
Theorem I.1. Suppose L and H are smooth functions in (O, R). Assume R(0) admit a second- order Taylor expansion at 0 with a non-singular second order derivative Va-. Under the MCAR assumption, we have that DDssL is asymptotically normal with covariance:
873
874
875
1 -Vo DeSSL π
VL( ;., (I,)) 12 2.y) Via 1
X2
Vgr 2 Vg-
V
Kg- Vg
π
876 As a consequence, we can minimise the trace of the covariance. Indeed, Tr(EDessL) reaches its minimum al
Tr Kg. Vg-1)
Nopt (1
(36)
Tr(V
878
and at Aopt:
1- π Tr (6 VH V S
Tr(V- Kg. Vz-
Tr(EDessL) Tr(Ece)
(37)
The complete case is the special case of DeSSL with X 0. Then, the Theorem holds for the 880 complete case.
879
Proof. We define L'(8; 2, 2( + - H(0;2) The assumptions of the
881
theorem are sufficient assumptions to apply Theorem 5.23 of Van der Vaart 1998 to the couple DesSLL L'), Hence, obtain the following representation for representation dessL:
Vn(ODessL - 0²) 1 Vn
1
(2.0)) +
VH(0":20 ; + (1))
1
π
(38)
884
Vn(0pesst - 00) 4, N(O, EpessL)
885
The asymptotic normality follows with variance:
DesSt, = EVL'E(VL'(0" ", x2) Vo-1
Using the MCAR assumption, simplify the expression of EpsSsL:
29

---

DessL = V
V
1
V ( V/ 8)
VL(0
72
1 1-r
+22V0=1
[1 [1-17) )² +
( y) Vi
V E [T (
=0,;,))) V
6 Cov(L(O";
vx,
x(1 Vg L
X²
Vo -Vo Kg. Vgl
887
We remark that the complete case is the particular case of DeSSL with À = 0. Then,
X
DestL = Eco
Vo V,,"",,," V
M(1
π Vo- K 7--
The asymptotic relative efficiency of consequence, the asymptotic relative efficiency DesSL com-
888
pared to Oco is defined as the quotient Tr(Snnss))
This quotien can be minimised with respect to A: Tr(Eco
880
Tr Kg. Vz-
Aopt (1 -
(39)
Tr (I Vo=
and at Appt
Tr(EDessL) Tr(Ecc)
1-T π
Tr Kp p- Vo-
S1.
(40)
Tr(V 6-
Tr((Ec))
892
893
Remark 1.2. On the sign of A. It is easy to show that a sufficient condition to have Aopt >> 0 is to have Kg- positive semi-definite. Indeed, using that Vo- is positive definite and Proposition 6.1 of
Serre 2010 we show that Tr(V-- Kg. VØ-1) > 0 and then Aopt > 0.
Remark I.3. Why minimising the trace of EDSSSL? ? Minimising the trace of DesSt. leads to
887
estimator with smaller asymptotic MSE, see Chen et al. 22200).
Remark L.4. Fully supervised setting, We also remark that our theorem matches the theorem for the supervised setting. Indeed, observing all the labelled corresponds the case æ and we obtain:
E. Ecc
Erully supervised-
30

---

Proof of Theorem 3.6
899 Our proof will be based on the following result from Shalev-Shwartz & Ben-David 2014 Theorem 26.5).
901
Theorem J.1. Let H be set of parameters, ~ 'D a random variable living in a space 2, c 0,
and { xx - 1-c, c). We denote
Lp(h) = Es(e(h, 2)), and Ls(h) Σ eh, 21).
(41)
where 21, 21... 2m are i.i.d. samples from D. For any 8 > 0, with probability at least - 8, we have 903
]
log (4/6)
LD(M) - (h) + 2E (Es)ism
sup hEH
Σ
e3e(h, 2:e(h,,2))
+ 4
(42)
m
904
where ..... Em are i.i.d Rademacher variables independent from "i,... Rm-
We restate and prove generalisation bound.
908
Theorem 3.6, We assume that both and are bounded and that the labels are MCAR. Then, there exists constant that depends X, T, H, and the ratio of observed labels, such that, with probability at least 6, for all E O
908
log(4/6)
R0) S RDSSSL(0) 2R, + kV
(43)
7
where Rn is the Rademacher complexity 909
R1
X nt H(;
Σ ]] (44)
The
e, H (0:
sup dEB
74
Thu
910 with E1, ... Em i.i.d. Rademacher variables independent from the data.
Proof. We use Theorem J.1 with (x, 71 = = n. and
E(h, 2) = nr; L(0; v.) + (n(1 - ra) nr.
H(0:z.).
(45)
ni
912
The unbiasedness of our estimate under the MCAR assumption, proven in Appendix D ensures that the condition of Equation (41) is satisfied with (D( = R())) and Ls(h) (0)))())) Now, since L and H bounded, there exists M such that [L] M and |H] < M. We then 915 bound &
913
72 M + max
n n
[0(h, 2) <
M
=c
(46)
71
T2
916 Now that we have chosen a c that bounds e, we can use Theorem
J.1 and finally get Equation
43
917 with x = 4c
31

---

K DeSSL with H applied on all available data
918
For consistency-based SSL methods it is common use all the available data for the consistency term:
1
(0) = L(0: 24, 91
H(O;
(47)
921
With the same idea, we debias the risk estimate with the labelled data:
1
DesSLL
Σ
L(B; F4, yk
74 1=1
i=
(48)
#(0;
922
Under MCAR, this risk estimate is unbiased and the main theorem of the article hold with minor modifications. In Theorem 3.1 Appt is slightly different and the expression of the variance at Appt remains the same. The scoring rule in Theorem is2 different but the theorem remains the same. Both Theorem and remann the same with very similar proofs.
924
925
Theorem K.1. The function À (eRDes)t reaches its minimum for:
Nopt Cov(L(O; x, y), (0)
(49)
((H(0:))
and
((RDasSL(0)) Aupe
The 2 ((.c))((cc(())) n S <V(Rcc(0))
(50)
where PL,H- = Corr(L(O;x,, v), H (0;x)).
928
When H is applied all labelled and unlabelled data, the scoring rule used in the learning process ny
930
then S' (po, (x, y, r)) = -( L(f:x. + X(1 en H x)) and we have is proper scoring
931 rule.
32

---

L MNIST and MedMNIST
902
933
L.1
MNIST
126
235
Ears
C33
157
3.09
500
Figure The influence of on Pseudo-label DePseudo-label Lenet trained on MNIST with ni 1000:
(Left) Test accuracy; (Middle) Mean test cross-entropy: (Right) Mean test ECE, with 95% CI
L.2
MNIST label noise
Pasucblabel
6.74
1.72
k205
R.25
Figure 7: The influence of on Pseudo-label and DePseudo-Labee for a Lenet trained on MNIST with label noise with = 1000: (Left) Mean test accuracy; (Middle) Mean test cross-entropy; (Right) Test ECE, with 95% CI.
33

---

935
L.3 MedMNIST
Table Test AUC of Complete Case, Lseu and DePseudoLaabe on five datasets of MedM- NIST.
DATASET
COMPLETE CASE
PSEUDOLABEL
DEPSHUDOLABEL
DERMA
84.26 + 0.50
82.64 + 1.19
83.82 + 0.95
PNEUMONIA
94.28 + 0.46
94.34 + 0.91
94.15 + 0.33
RETINA
70.70 + 0.74
70.12 1.01
69.97 + 1.44
BREAST
74.67 +: 3.68
74.86 3.18
75.33 3.05
BLOOD
97.83 + 0.23
97.83 +: 0.23
97.72 0.15
34

---

M PseudoLabel and DePseudoLabel on CIFAR: p-values
936
937 M.1
CIFAR-10
befseuditatel Psoudolabel
Figure 8: The influence of À Pseudo-label and DePseudo-label CIFAR-10 with ni= 4000: (Left)
Mean test accuracy; (Middle) Mean test cross-entropy; (Right) Test ECE, with 95% CI.
1.0
CCL
08-
0.-
0.-
02
16'
16
1.0
Figure 9: p-values of paired student test between PseudoLabel and DePseudol aabel (Right) DePseu- doLabel is better than LseudoLabel; (Left) D is worst than PseudoLabel.
M.2
Computation of Aopt the test set.
As explained in the main text, the estimation of Cov(L(O; y), (0; with few labels led to extremely unstable unsatisfactory results. However, we test the formula on CIFAR-10 and different methods to provide intuition on the order of Aopt and the range of the variance reduction regime (between and 2Aopt). To do so, we estimate Aopt on the test set for CIFAR-10 by training a CNN13 using only 4, 000 labelled data on 200 epochs. The value of Aopt is 1.67, 31.16 and 0.66 for entropy minimisation, pseudo label and Fixmatch. Therefore, the reduced variance regime covers the intuitive choices of in the SSL literature. Unfortunately, computing Aopt on the is not applicable in practice.
939
941
942
943
945
35

---

947
M.3 CIFAR-100
Dehhodbiabsc Proudtiabel
0375
3755
Figure 10: The influence of on Pseudo-label and DePseudo-label on CIFAR-100 with ní= 4000: (Left) Mean test accuracy; (Middle) Mean test cross-entropy; (Right) Test ECE, with 95% CI.
36

---

N
Fixmatch (Sohn et al., 2020
948
948
N.1
Per class accuracy
950
In recent work, Zhu et al. (2022) exposed the disparate effect of SSL on different classes. Indeed, classes with high complete case accuracy benefit more from SSL than classes with low baseline accuracy, They introduced metric called the benefit ratio (BR) that quantifies the impact of SSL on
951
952
953 a class C::
(R(C) accssL(C)) (cccc)C)cccC())
(51)
954
where accssL acccc(C)) and (CCg(C) are respectively the accuracy of the class with an SSL trained model, complete-case model and fully supervised model (a model that has access to all labels). Inspired by this work, we report the per class accuracy and the benefit ratio in Table We that the "poor" classes such bird, cat and dog tend to benefit from DeFixmatch much more than from Fixmatch. We compute accs (C) using pre-trained model with the same architecture Zhu al. (2022) also promote the idea that fair SSL algorithm should benefit different sub-classes cqually, then having (R(C)) = (R(C") for all C. C". While perfect equality seems unachievable in practice we propose look the standard deviation the BR through the different classes. While the standard deviation of Fixmatch 0.12, the one of DeFixmatch is 0.06. Therefore, DeFixmatch improves the "il--ppuultionss accuracies more equally.
956
958
980
962
983
Table 4: Mean accuracy per class and mean benefit ratio (BR) on folds for Fixmatch, DeFixmatch and the Complete Case. Bold: "poor" complete case accuracy classes.
COMPLETE CASE
FIXMATCH
DEFIXMATCH
ACCURACY
ACCURACY
BR
ACCURACY
BR
AIRPLANE
86.94
95.94
0.88
96.62
0.94
AUTOMOBILE
95.26
97.54
0.68
98.22
0.89
BIRD
80.46
90.80
0.68
92.64
0.80
70.08
82.50
0.56
87.16
0.78
DEER
88.88
95.86
0.78
97.26
0.94
DOG
79.66
87.16
0.53
90.98
0.81
FROG
93.12
97.84
0.80
98.62
0.94
HORSE
90.96
96.94
0.83
97.64
0.92
SHIP
94.12
97.26
0.67
98.06
0.84
TRUCK
93.18
96.82
0.84
97.20
0.93
N.2 Fixmatch details
As first detailed in Appendix B. Fixmatch is pscudo-label based method with data augmentation. Indeed, Fixmatch uses weak augmentations of z (fii-and-shiif) for the pseudo-labels selection and then minimises the likelihood with the prediction of the model on a strongly augmented version of æ. Weak augmentations are also used for the supervised part of the loss. In this context,
L(0; ar y) = E (mma(()) log(Po (v(=1))
and
H H(0; mecat(a)) 1 [mmxxp > - Log(pe((())g (arg max (yy((1)) [
985 where I1 is a weak augmentation of and æ2 is a strong augmentation. We tried to debias an 966 implementation of Fixmatch however training was very unstable and led model that were much worst than the complete case. We believed that this behaviour is because the supervised part of
37

---

988
the loss does not include strong augmentation. Indeed, our theoretical results encourage to have strong correlation between L and H. therefore including strong augmentations the supervised term. Moreover, solid baseline for CIFAR-10 10 using only labelled data integrated strong augmentations
969
971
(Cubuk al. 2020). We modify the implementation, see Code in supplementary materials. Therefore, the supervised loss term can be written as:
972
1
L(0; x, v) - 2 (Ex) -eakk(=)))]]] (p + E (attong(ss)) [- (B)
(52)
973
where 21 is weak augmentation of and I2 is a strong augmentation. This modification encourages as the original Fixmatch implementation used À We also remark that this modification degrades the performance of Fixmatch (less than 2%) reported in the work of (Shnn
974
us choose
975
976
al. (2020). However, including strong augmentations in the supervised part greatly improves the performance of the Complete Case.
977
38

---

O
CIFAR and SVHN: Oliver et al. (2018) implementation of consistency-based model.
978
979
In this section, we present the results CIFAR and SVHN by debiasing the implementation of Ollieer et al. 2018) of II-Model, Mean-Teacher and VAT We mimic the experiments of Oliver et al. (2018 4igure-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 cross cross-entropy and accuracy. As reported below, we reach almost the same results as the biased methods.
981
982
984
985
0.1
CIFAR-10
SUT Phity
Mour Theniee
0.2
Cang Cails
426
3800
Figure 11: Test accuracy for each SSL approaches CIFAR-10 with various amounts of labelled data (Left) I1-model and Dell-model. (Right) VAT+EntMin and VAT+DeEntMin. (Bottom) bean-teacher and DeMean- teacher, Shadows represent 95%
84
Ca pits
1200
1200
100
Corp bil Cave
Figure 12: cross-entropy for each SSL approaches on CIFAR- 10 with various amounts labelled data (Leff) 11-model and Dell-model. (Right) VAT+EntMin and VAT+DeEntMin. (Bottom) Mean-teacher and DeMean-teacher Shadows represent 95% Cl.
39

---

986
0.2 SVHN
Muke
WT Patret
2000
+2.0 180
40% 660
Contavee CAB
Figure 13: Test accuracy for each SSL approaches on CIFAR-IO with various amounts labelled nu (Left) 11-model and Dell-model. (Right) VAT+EntMin and VAT+DeEntMin,, (Bottom) Mean-teacher and DeMean- teacher. Shadows represent 95% CI.
One
Cold parta Casa
1000
42/0
100
Ceneer Hacher
8-
Figure 14: Test cross cooss-y for each SSL approaches on CIFAR- 10 with various amounts labelled data (Lef() 11-model and medel (Right) VAT+EntMin and VAT+DeEntMin. (Bottom) Mcan-teacher and DeMecn-teacher. Shadows represent 95% CI.
40

---

P
Tabular benchmarks
987
988 In this section, we tested these methods against the benchmarks of Chapelle et al. 2006 Chapter 21 and UCI datasets already used in an SSL context in (Guo al. 2010p. We trained logistic regression for the case 100 labelled datapoints and finetune with a very small validation set, 20 datapoints. We evaluated the performance in accuracy and cross-entropy of PseudoLabel, EntMin, Dees and DeEntMin
980
982
983
P.1
SSL Benchmark
85
55
80-
80-
12-
70
80
disk) secstr
cok2
text
COL 9281n USPS
seistr oz g241c
COR 9283n USPS
Comp
CompleteCase
Debrttnn ErtMinn
Detat/in
2.00
EriMin
1.75
20-
1.50
3.25
0.75
0.50
digi oxcer cil 801
gittc teet
Coll g24in
USPS
BC)
<igh1
seeer
2l12 g2d1c teat col co4in USPS
Figure 15: Mean accuracy and cross-entropy for cach SSL datasets (Chapelle et al. 2006 on a logistic regression. (Top-Left) Pseudol abel and DePseudoL accuracy (Top-Right) Pscudol.at aaell and DePseudol.ate cross-entropy (Bottom-Left) EntMin and DeEatMin accuracy (Bottom-Right) EntMin and DeEntMin cross- entropy.
41

---

994
P.2
UCI datasets
Moan accusecy
12-
60-
60-
52-
50.
CompleteCare
Comp eteCane
60
DePerutetab abel
DePonccalate
Ponudslatel
Proudetabbl
Erttiin
1.5
Moa
CompleteCave
Figure 16: Mean accuracy and cross cross-entrop entropy for each UCI datasets Guo et al. (Top-Left) PseudoLabel and DePscudoLabes accuracy (Top-Right PseudoLabel and DePseudoLabel cross-
2010 on logistic regression.
entropy (Bottom-Lefi EntMin and DeEntMin accuracy (Bottom Right) EntMin and DeEntMin cross- entsspy
42

---

Computation details
995
996
Q.1
Computation resources
987
Deep Learning experiments of this work required approximately 9,200 hours of GPU computation. In partieular, Fixmatch was trained using 4 GPUs. Here are the details:
998
MNIST: 300 hours
1000
medMNIST: 3 hours
1001
CIFAR-I0: 525 hours
1002
CIFAR-100: 1500 hours
Fixmatch 960 hours
Realistic SSL evaluation on both CIFAR and SVHN: 5880 hours
1005
Q.2
Computation libraries and tools
Python (Van Rossum & Drake Jr
1995)
PyTorch (Paszke al. 2019
1008
TensorFlow (Abadi et al. 2015
1009
Scikit-lcarn (Pedregosa et al
2011
1010
Seaborn Waskom al.
2017
1011
Python imaging library Lundh al.
2012)
Numpy (Hariss al. 2020
1013
Pandas (McKinney et al.
2010)
1014
RandAugment (Cubuk et al. 2020)
1015
Fixmath--PytorchP
1018
Realisti-SSLL-evalutie Oliver et al.
2018
43


Reviews:
[{"review_id": "zva4v1rTTZ2", "reviewer": "Reviewer_M2E5", "summary": "This paper focuses on semi-supervised learning and tries to give theoretical guarantee about the safeness of semi-supervised learning methods. Specifically, the authors propose a dibiasing approach, and combine it with the deep SSL methods. Theoretical ananysis about the generalization are discussed.", "questions": "1) Why is the proposal guaranteed to be safe? It seems that the results cannot guarantee that the proposal will always be better than the simple supervised learning method.", "limitations": "Yes", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1) This paper focuses on safe semi-supervised learning problems. This is an important problem for SSL methods, and it is a good attempt to give a theoretical analysis of semi-supervised learning methods.\n\nWeakness\n\n1) The paper's presentation is very poor and very hard to follow. The figures and tables need to be reorganized.\n\n2) The paper gives a new definition of safe SSL: \"a SSL algorithm is safe if it has theoretical guarantees that are similar or stronger to the complete case baseline\". How to judge whether the theory is stronger?  The \"safe\" is related to the performance, i.e., the performance is guaranteed not to be reduced compared with the baseline supervised learning method.\n\n3)  The theoretical result does not give a guarantee that the performance will always be better than the supervised learning method. So it does not consist with the author's claim.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "SNiCJIVAWvI", "reviewer": "Reviewer_UPnt", "summary": "This paper suggests a simple denoising technique for existing semi-supervised learning methods (with surrogate objectives). The proposed objective is shown to have less variance in some cases, and is now consistent when $n->\\infty$.", "questions": "- The first point in my weaknesses section regarding the theory part.\n\n- If the authors can provide a more complete empirical evaluation of the debiasing term with the most common existing SSL methods (pseudo label, entropy minimization, and consistency-based) to show the benefit of the proposed technique.", "limitations": "The authors claim in the checklist that they have discussed the limitations of the work in Section 5, but no limitations are mentioned there.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n- The debiasing technique is simple and easy to implement, which can be added to existing SSL methods without much effort.\n- The authors provide solid theoretical contributions regarding the variance of the proposed objective and the consistency of its minimizer.\n\n**Weaknesses**\n- Some missing parts on the theory side. I am more interested in the reduced variance of the proposed objective. The authors showed that at $\\lambda_{opt}$, the objective has less variance than the standard complete case. However, this $\\lambda_{opt}$ value is often unknown or hard to estimate in practice due to $\\rho_{L,H}$, so the theorem is less meaningful. I wonder if we can find out the range of $\\lambda$ in which we have reduced/increased variance. For example, if the range for reduced variance is small, the method would be less robust (too sensitive to the choice of $\\lambda$), thus becoming less meaningful.\n\n- The experiments section is weak. Why don't the authors verify the proposed debiasing term with all three well-known pseudo label, entropy minimization, and consistency-based methods for all experiments (MNIST, MeMNIST, CIFAR)? I imagine these experiments are not too computationally expensive.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "QOLHZ3OAix", "reviewer": "Reviewer_5CzW", "summary": "The authors propose a method of removing the bias in semi-supervised learning: debiased SSL (DeSSL). The paper provides generalization error bounds for the proposed methods based on the missing completely at random (MCAR) assumption. The authors also demonstrate the implementation of the debiased component and evaluate debiased versions of different existing SSL methods, such as the Pseudo-label method and Fixmatch, and show that debiasing can compete with classic deep SSL techniques in various settings by providing better calibrated models.", "questions": "Since the focus of the proposed method is to reduce bias, is there a way to directly evaluate the bias reduction in addition to the results reported in the experiments?\n\n", "limitations": "yes", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper has good clarity on the theory presented and has generally sound approaches and good results. The literature review is comprehensive and leads to the proposed method naturally. Technical results are not particularly complex but flow naturally and results are intuitive.\n\nThere are several aspects of the paper that can be strengthened:\n\nThe key to the proof of the consistency is the assumption that the true parameter optimizes the proposed \"debiased\" objective under the true distribution. A natural question is  when such an assumption is viable, and when it is not. For example, would there be situations when the true parameter approximately optimizes the objective without adjusting for bias using the labeled data?\n\nThe theory in the paper is built on the assumption of missing completely at random (MCAR), which is often considered in practice a strong condition and sometimes not realistic. Therefore it would be helpful to evaluate how much the results rely on this assumption and provide some intuition on how MCAR is used in the theory.\n\nIn problems emphasizing the overall prediction error, it could be argued that the bias-variance trade-off can be more important than the bias itself. This paper partially addresses this issue by finding the optimal $\\lambda$ in minimizing the variance of the objective function. The resulting format of the minimal variance is intuitive. An alternative and more direct calculation is to find the $\\lambda$ that leads to the smallest asymptotic variance of the $\\hat{\\theta}$, which should be easy to obtain from the $M$-estimator results.\n\nThe experiments section is comprehensive. In evaluate the influence of $\\lambda$, it would be helpful to visually mark the estimated optimal $\\lambda$ and examine whether it actually achieves better performance.\n\nMinor issues:\nSome definitions are missing which may prevent the reader from following the technical results:\neq (1) $n_l$\neq (2) $n_u$\neq (4) several items are not defined", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "EYktucKNDW", "reviewer": "Reviewer_ZE27", "summary": "This paper proposes to debias the training objective for semi-supervised learning (SSL) methods. The paper suggests a simple modification to the training objective, which de-biases it, by reducing the certainty on labelled datapoints, and considering the whole objective as an optimization of the complete case with a constraint on the two sets of labelled and unlabelled datapoints to satisfy the same property on the SSL loss $H$ on average. Then, the authors proceed to prove statistical learning results on the debiased SSL method, and empirically demonstrate the usefulness of the approach.", "questions": "What will happen if we replace the labeled data points used for debiasing the objective with unlabeled datapoints? I assume that the approach would fail, because the two objectives on the unlabelled datapoints will be competing with each other.\n\nMinor: \n\nLine 35: \"notion safe semi-supervised learning\" <- \"notion of safe semi-supervised learning\". There are other typos. Please, proofread carefully.\n\nFigure 2: in the caption, it should be \"top\" and \"bottom\" instead of \"left\" and \"right\". Likewise for Figure 3.\n\nYou have missed to put some notations in the equation environment within the appendix, please proofread carefully.\n", "limitations": "I think the paper does not yield any major limitations. However, I don't see a dedicated section about limitations in the main text. I suggest the author spend some time thinking about it.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\n1) The idea of the paper is clear and sound. The bound on the variance of the DeSSL risk estimate and the generalization bound are useful. They give us generalization insights about SSL, and the benefit from the correlation between $L$ and $H$.\n\n2) The experiments demonstrate that the intuition about the usefulness of debiasing benefits standard SSL benchmarks. I like the toy task example as well.\n\n3) Overall, the paper is clearly written. The proofs seem correct to me, although I have not been able to check every single detail.\n\nWeaknesses: \n\n1) It would be interesting to test your debiasing on a larger task, such as ImageNet. For example, how does debiasing work for PAWS (https://arxiv.org/abs/2104.13963)? \n\n2) I think the paper should discuss the role of the debiasing, and the role of the reducing of the confidence on the labeled datapoints. I think the latter is important for the success of the method, and the theory as well. However, just by looking at the main paper, this doesn't stand out. \n\nFor example, we can achieve debiasing by splitting the unlabelled dataset in two parts and using the red term on one part and the blue term on the other (using the color convention from Equation 5 in the main text). Doing, this, we will make the estimate unbiased, but we will not learn good representations (I think), because we have two conflicting objectives on the unlabelled dataset. Having the blue term on the labelled dataset is very important, I think, but it does not stand out in the paper right now. I think the blue term helps with calibration, as the ECE experiments show in the Appendix. Please, discuss this more. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject