Can semi-supervised learning use all the data effectively? A lower bound perspective
Authors: Alexandru Tifrea
Gizem Yüce
Amartya Sanyal
Fanny Yang
Venue: NeurIPS 2023 spotlight (2023)
Keywords: semi-supervised learning
statistical lower bound
TL;DR: Adaptive statistical lower bound for semi-supervised learning linear classification in 2-GMM data model.

Abstract: Prior theoretical and empirical works have established that semi-supervised learning algorithms can leverage the unlabeled data to improve over the labeled sample complexity of supervised learning (SL) algorithms. However, existing theoretical work focuses on regimes where the unlabeled data is sufficient to learn a good decision boundary using unsupervised learning (UL) alone. This begs the question: Can SSL algorithms simultaneously improve upon both UL and SL? To this end, we derive a tight lower bound for 2-Gaussian mixture models that explicitly depends on the labeled and the unlabeled dataset size as well as the signal-to-noise ratio of the mixture distribution. Surprisingly, our result implies that no SSL algorithm improves upon the minimax-optimal statistical error rates of SL or UL algorithms for these distributions. Nevertheless, in our real-world experiments, SSL algorithms can often outperform UL and SL algorithms. In summary, our work suggests that while it is possible to prove the performance gains of SSL algorithms, this would require careful tracking of constants in the theoretical analysis.

Can semi-supervised learning use all the data effectively? A lower bound perspective
Alexandru Tifrea" ETH Zurich alexandru, tifrealinf ethz. ch
Gizem Yúce* EPFL gizem yuceeupfllecccc
Amartya Sanyal
Fanny Yang ETH Zurich fan. yan@innin .ethz.
Max Planck Institute for Intelligent Systems, Tübingen amsa@di ku. dk
Abstract
Prior theoretical and empirical works have established that semi-supervised learning algorithms leverage the unlabeled data to improve the labeled sample complexity of supervised learning (SL) algorithms. However, existing theoretical work focuses on regimes where the unlabeled data is sufficient to learn good decision boundary using unsupervised learning (UL) alone. This begs the question: Can SSL algorithms simultaneously improve upon both and SL. To this end, we derive tight lower bound for 2-Gaussian mixture models that explicitly depends the labeled and the unlabeled dataset size as well the signal-to- noise ratio of the mixture distribution. Surprisingly, our result implies that no SSL algorithm improves upon the minimax-optimal statistical error rates of SL UL algorithms for these distributions. Nevertheless, in our real-world experiments, SSL algorithms can often outperform UL and SL algorithms. In summary, our work suggests that while it is possible to prove the performance gains of SSL algorithms, this would require careful tracking of constants the theoretical analysis
Introduction
Semi-Supervised Learning (SSL) has recently garnered significant attention, often surpassing tradi- tional supervised learning (SL) methods in practical applications [5] 10 22). Within this framework, the learning algorithm leverages both labeled and unlabeled datasets sampled from the same distribu- tion. Numerous empirical studies suggest that SSL can effectively harness the information from both datasets, outperforming both SL and unsupervised learning (UL) approaches [21 42 25]. This observation prompts the question: how fundamental is the improvement of SSL SL and UL? 2
Prior theoretical results not provide a consensus on this topic. One line of work demonstrates that under certain settings, SSL is capable of lowering the labeled sample complexity. In these settings, the unlabeled data possesses a significant amount of information about the conditional distribution (up permutation). Some examples of this setting include distributions where unlabeled samples enough to obtain small estimation error mixture models 30 [8] or when the data is clusterable [3]. Therefore, despite SSL performing provably better than SL in these settings, it is only good UL (up to permutation). Another line of work challenges the above literature by identifying scenarios where SSL achieves the same error rate SL. In these scenarios, even oracle knowledge about the
I Please consult the arxiv version of the paper for an updated manuscript.
"By error of UL we mean the prediction error to sign. We formalize this paradigm of using UL first and then identifying the correct sign UL+ in Section 2.2
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

marginal distribution fails to improve upon the error rates of SL algorithms since the marginal does not carry any information about the labeling i.e. the conditional distribution. Therefore, these settings do not allow SSL. to improve upon SI. but only upon UI
In summary, the previous bounds do not provide conclusive answer the benefits of SSL; the positive and negative results consider different regimes dependent on sample sizes and the "compatibilibity" of the marginal distribution with the conditional distribution. partieular, they either improve upon UL or upon SL, but never both simultancously. In this paper, we provide a first answer the following question
Can semi-supervised classification algorithms simultaneously improve over the minimax rates of both SL and UL?
Specifically, in Sections 2 and 3 we study this question in the context of linear classification for
symmetric 2-Gaussian mixture models (GMMs) as done in several works this domain [30 18] 2
24 [39.
In this setting, we derive minimax error rates for semi-supervised learning that specifically depend on the "regime", characterized by three quantities: the amount of available unlabeled data Yhs amount of available labeled data n,, and the inherent signal-to-noie ratio (SNR) that quantifies the amount of information the marginal input distribution has about the conditional label distribution (see for more details). An SNR-dependent minimax rate allows us analyze the whole spectrum of problem difficulties for 2-GMMs. By contrasting the SSL minimax rates with established minimax rates for SL. and UL., we find that in regime can SSL surpass the statistical rates of both SL and UL. In conclusion, the optimal algorithm is the one that can adeptly switch between SL and UL algorithms depending the regime and hence, it never
the available data fully.
Nevertheless, statistical rates may not offer a complete picture for explaining the practical benefits of SSL algorithms. Several prevalent SSL algorithms, such self-training are more sophisticated than UI. approaches and use labeled data not only for determining the sign but also for learning the decision boundary. In Section 4 we show that SSL ensembling method and self-training [41,7l can indeed improve upon the best of SL and UL algorithms even in proof-of-concee experiments for linear classification tasks on both synthetic and real-world datasets. Since the improvements cannot be captured by statistical rates, our results highlight the significance of the constant factors in future theoretical work that analyzes the advantage of SSL algorithms.
2 Problem setting and background
Before providing our main results, in this section, we first define the problem setting for our theoretical analysis. the evaluation metrics and the types of learning algorithms that we compare. We then describe how we compare the rates between SSL and supervised and unsupervised learning
2.1 Linear classification for 2-GMM data
Data distribution. We consider linear binary classification problems where the data is drawn from a Gaussian Mixture Model consisting of two identical spherical Gaussians with identity covariance and uniform mixing weights. The means of the components 0" -0" are symmetrie with respect to the origin but can have arbitrary non-zero norm. We denote this family of joint distributions as P2-GMM- := {PXr- 0 E Rd} that can be factorized so that the density reads (x y) = y (Zly)py (y) with
py = 11, and PhT = NN(Y8 Ia).
This family of distributions has often been considered in the context of analysing both SSL [30 18 and SL/UL 2 24 39 algorithms. For E (0, 2o), denote by p(.) C P2-GMM and ((*) Rd
the of distributions P.r and the of parameters with ||0*|| s, respectively. With this definition, we will be able to obtain refined bounds that depend explicitly on s. We consider algorithms A that take as input labeled dataset D;- (PXr) of size ny, an unlabeled dataset
Du (P8*) of size nu or both, and output an estimator A (D;, D.) Rd. The estimator used to predict the label of a test point x as ÿ = sign (0. .x)

---

Learning paradigm
Excess risk rate
Estimation error rate
2/2 d
SL
UL(+)
Table 1: Known minimax rates of SL and UL for learning 2- 2-GMMs [9 24 The minimax rates for UL are up choosing the correct sign. This rate is the same as for UL+ if nt 2 log(na). The notation ((x) = (ar) is equivalent to (g))
Evaluation metrics In this work, we consider two natural error metrics for this class of problems: prediction and parameter estimation erro For any vector 0, define its
Prediction error: Rered (0, 00 == Pxy (sign (0, # Y), and
Estimation error: Restim (0, 0*) = 100 1
When the true l" is clear from the context, we drop the second argument for simplicity. our discussions, we focus on the prediction error, but include a minimax rate for the estimation error for completeness. In particular, we bound the excess risk of 0, defined as the distance between the risk of 0 and the Bayes optimal risk
Excess prediction error: & (0, 0*) = Reeed (0, 0*) - inf Rpred (0, 0")
0
where infe Rpeed (*) ) is achieved at 0 but can be non-zero.
For the set of all classification algorithms, we study the minimax expected error over a set of parameters θ. This worst-case error over θ indicates the limits of what is achievable with the algorithm class. For instance, the minimax optimal expected excess error of the algorithm class over takes the form:
Minimax excess error: c (nq, Th.s θ) := inf sup E(E (A)D,,
A ee
2.2 Minimax optimal rates of supervised and unsupervised learning
We distinguish between three kinds learning that can be used in the SSL setting to learn a decision boundary Ó but are designed to leverage the available data differently. For simplification, our discussion tailored towards learning P2-GMM, though the ideas hold more generally.
1) Semi-supervised learning (SSL) SSL algorithms, denoted as ASsi, can utilize both labeled Di and unlabeled samples D., to learn the decision boundary and to produce an estimator 0SSL = AssI. (Dt, D.). The promise of SSL. is that by combining labeled and unlabeled data, SSL can reduce both the labeled and unlabeled sample complexities compared to algorithms solely dependent on either dataset.
2) Supervised learning (SL) SL algorithms, represented by AsI., can only use the labeled dataset Dj to yield an estimator dsL AsI. (D;, 0). The minimax rates of SL for distributions from p(s) 2-GMM (see Table are achieved by the mean estimator Òst. = . >T Y.X,, for both excess risk and estimation error.
3) Unsupervised learning (UL) Traditionally, UL algorithms tailored to learning the generative model for marginal distributions. For PZ-MM the marginal is governed by 0" and UL algorithms output set of estimators (ōuL.-oun the true 0*, To evaluate prediction performance, we define the minimax rate of UL algorithms as the minimax rate for the closer (to the true 0*) of the two estimators. This minimax rate of
AuL (0, D.) one of which is guaranteed to be close to
UL algorithms over (*)
P2GMM is known for both the excess risk and the estimation error 24 39
(see Table 1). These rates are achieved by the unsupervised estimator Q.. = V( 1)+0, where Σ
(2, () is the leading eigenpair of the sample covariance matrix = 1 R. == X,X3 and we use the notation (z)+ == max(0, vr.
For linear classification and a 2-GMM distribution from the family PLAMM. low estimation error implies only good predictive performance, but also good calibration under logistic model (29).

---

2.3 A "wasteful" type of SSL algorithm
Several SSL algorithms used in practice (e.g. Sim- CLR 19). SwAV [8] follow a two-stage procedure: i) determine decision boundaries using only unlabeled data; and ii) label decision regions using only labeled data. We refer to this class of two-stage algorithms as UL and denote them by AuL+- Early analyses of semi-superveee learning focus, in fact, on algorithms
Algorithm 1: UL+ algorithms AUL+
Input:D;, Du
(Oul, 0m.) + (D..
Oun- < Select from (Oin. Ovn. using Dr return OUL
that fit the description of UL+ [30 31..
For linear binary classification, the two-stage framework depicted in Algorithm | The following proposition upper bounds the excess risk and estimation error incurred by the UL+ estimator given by
OUL+ sign (0 Bu)) dUL with θsL = ASL (Di).
(5)
Proposition (Upper bounds for OUL= ). Let OuL+ be the estimator defined in Equation E (0, 1] the following holds when nu 2 (160/s) /// and d 2 2:
For any
E Rpred (uuL+ 0+)] 2
n l-coy floggina!
+ se
and
s
E 3 0")
S t0²
d
2 (1-c0y]
# Aingin
+
s
Appendix A contains the complete statement of the proposition including logarithmic factors and the proof. Note that for n; = o log (n.)), the first term in the upper bound dominates, thereby resulting in the same rate as the minimax rate of UL up to choosing the correct sign. We remark that, while Algorithm [ defines UL+ algorithms as only using the unlabeled dataset DD for the unsupervised learning step, one can also use the labeled dataset DD, without labels in that step. However, typically, in practice, UI. style algorithms (e-g. SimCLR, SwAV) do not use the labeled data in this way, as they operate in a regime where unlabeled data is far more numerous than labeled data. Thus, we analyze Algorithm in this work.
Why UL+ algorithms are "wasteful" As indicated in Algorithm I UL+ type algorithms follow precise structure where labeled data is used solely select from the set of estimators output by a UL algorithm. Intuitively, such algorithms do not take full advantage of the labeled data as it is not used refine the decision boundary. In prior empirical and theoretical studies, this inefficiency has not been problem since they have focused on the regime n. = w(n).. where unlabeled data is often orders of magnitude more abundant than labeled data. When n. = O(n)) or even nu < nt, however, Proposition [ shows how this two-stage approach of UL+ can become strikingly ineffective. For simplicity, consider the extreme scenario where n. is finite, but ny + Dc. The error of a UL+ algorithm will, at best, mirror the error of UL algorithm with the correct sign (e.g. (d/n.) for the excess risk). Thus, despite using both labeled and unlabeled data, UL+ algorithms bear close resemblance to UL algorithms that only use unlabeled data.
2.4 Brief overview of prior error bounds for SSL
In this section, we discuss prior theoretical works that aim to show benefits and limitations of SSL.
Upper bounds There are numerous known upper bounds on the excess risk of SSL algorithms for PMMMM distributions. However, despite showing better dependence on the labeled set size, these earlier bounds primarily match the UL+ rates 33 31 or exhibit slower rates than UI+ [18]. That is, we cannot conclude from existing results that SSL algorithms can consistently outperform both SL. and UL+ which is the question we aim to address in this paper.
Lower bounds In contrast to the upper bounds that aim to demonstrate benefits of SSL, three distinct minimax lower bounds for SSL. have been proposed to show the limitations of SSL. Each proves, different settings, that there exists distribution Pxy where SSL cannot outperform the SL. minimax rate. Ben- David et al. [6] substantiate this claim for learning thresholds from univariate data

---

sourced from uniform distribution on [0. 1]. Göpfert et al. [20] expand upon this by considering arbitrary marginal distributions Px and "rich" set of realizable labeling functions, such that no volume of unlabeled data can differentiate between possible hypotheses. Lastly, Tolstikhin and Lopez- Paz [36] set a lower bound for scenarios with no implied association between the labeling function and the marginal distribution, a condition recognized as being unfavorable for SSL improvements (32). Each of the aforementioned results contends that a particular worst-case distribution Pxy exists, where the labeled sample complexity for SSL matches that of SL, even with limitless unlabeled data.
To summarize, the upper bounds show that SSL improves upon SL in settings where ny is significantly larger than ny. In fact, for such large unlabeled sample size even UL+ can achieve small error. On the other hand. the lower bounds prove the futility of SSL for distributions where even infinite unlabeled data cannot help i.c. Px does not contain sufficient information about the conditional distribution. However these works fail to answer the question: does there exist relatively moderate nh regime where SSL is better than both SL. and UL+
In the family of P2-GMM distributions, the above lower bounds translate to the hard setting where nu < 1/s. We now aim to prove a minimax lower bound for a fixed difficulty >> O, that allows us to answer the above question in different regimes in terms of nt; Rby
3 Minimax rates for SSL
In this section we provide tight minimax lower bounds for SSL algorithms and 2-GMM distributions in Plet P2MMMM- Our results indicate that it is, in fact, not possible for SSL algorithms to simultaneously achieve faster minimax rates than both SL. and UL+
3.1 Minimax rate
We begin by introducing tight lower bounds on the excess risk 4 of a linear estimator obtained using both labeled and unlabeled data. In addition, we also present tight lower bounds on estimation error (3) for the means of class-conditional distributions obtained similarly using labelled and unlabelled data.
This is especially relevant when addressing lincar classification of symmetric and spherical GMMs. In this setring, a reduced estimation error points to only a low excess risk but also suggests small calibration error under the assumption of a logistic noise model (29]. Both of these results are presented in Theorem [ We present short proof sketches here and relegate the formal conditions required by the theorem to hold as well as the full proofs to Appendices B (for the estimation error and excess risk, respectively).
Theorem 1 (SSL Minimax Rate for Excess Risk and Estimation Error). Assume the conditions in Proposition 1 and additionally let > O log Then for any (0, 1). we have
inf sup (AAsz. (Di, Du), = ee 2/2 min Ase 1 1--1==
d sug + s )
and
d
inf sup E [Resimm (AssL (Di, min s,
Ass |0-1|==
mi + s2n
where the infimum is over all the possible SSL algorithms that have access to both unlabeled and labeled data and the expectation is over D: (PyY)" and D. (P The
In the rest of the section, we focus solely on the bound for excess risk; however, we note that the discussion here transfers to estimation error well. In Section 3.2 we discuss the new in- sights that this bound provides. A direct implication of the result is that CssL (n4, nu, O(+)) x nwe nu, @(+))). that is, the minimax rate of SSL is the same as either
min (est. (ni. O, @(+)) , CUL+ (mi,
that of SL. or UL+ depending on the value of s and the rate of growth n, compared to n,. Therefore, we can conclude that no SSL algorithm can simultaneously improve the rates of both SL and UL+ for
E ((s), We provide a full discussion of the rate improvements in more detail in Section 3.2
Proof sketch The proof of the lower bound for excess risk is presented in Appendix For this proof, we adopt the packing construction in Li et al. (24 and apply Fano's method. Since the algorithms have access to both labeled and unlabeled datasets in the semi-supervised setting, KL
5

---

divergences between both the marginal and the joint distributions appear in the lower bound after the application of Fano's method, which is the key difference from its SL and UL counterparts.
We then show that the rate can be matched by the SSL Switching Algorithm (SSL-S) in Algorithm 2 an oracle algorithm that switches between using (minimax optimal) SL or UL+ algorithm based on the values of s, Tht, and fu. The upper bound then follows as a corollary from Proposition and the upper bounds for supervised learning.
Algorithm 2: SSL-S algorithm
Input:D;. Du, 8, Ast,, AuL.
Result: OssLS
Os. + (Di)
Oun Ann, Di)
if S min {v=n
For the parameter estimation eπror lower bound, use Fano's method with the packing construction in Wu and Zhou [3) who have employed this method to derive lower bounds in the context of unsuper- vised learning. Similar to the excess risk analysis, the lower bound reveals that the SSL rate is either determined by the SL rate or the UL+ rate depend- ing on 8 and the ratio of the sizes of the labeled and unlabeled samples. Once again, the minimax er- ror rate is matched by the SSL Switching algorithm presented in Algorithm
OSSLS =0 else if min
1/4
d
<
S
nu
L ÔSSLS = OSL
else
L OSsiSS O.L. return ASsLS
Discussion of the details of the theorem We note that the SSL-S algorithm chooses to output the trivial estimator oSsL-S 0 if the SNR is low. In the low-SNR regime, the trivial estimator O 0 achieves small excess risk of & (0, 0*) + (s) + (0) ~ /'' where + is the CDF of the standard normal distribution.
Moreover, the technical condition 8 E (0, 1] is not overly restrictive as this range for the SNR is already sufficient for seeing all the relevant regimes, e.g. SSL-S switches from using SL. to UL+ within this range. Finally, while the rates of either SL or UL+ cannot be improved further using SSL algorithms, it is nonetheless possible to improve the error by a constant factor, independent of nu and we describe an algorithm that uses both Dj and P. effectively and can
nu To see this, in Section 4 hence achieve a provable improvement in error over both SL and UL+
3.2 Comparison of SSL with UL+ and SL. in different regimes
To understand whether an SSL algorithm is using the labeled and unlabeled data effectively, we compare the error rate of SSL algorithms to the minimax rates for SL. and UL+ algorithms.
gap in these rates for a certain SSL algorithm would indicate that the algorithm can obtain lower error than both SL and UL+ when presented with the same amount of (large enough) data. We study the improvement rates defined below, which capture the error ratio for the worst-case distributions between the minimax rate for SSL and the minimax rate for SL or UL+
Definition (SSL improvement rates). For a set of parameters θ S Rd, we define the improvement rates of SSL over SL and UL+ as by and hi, respectively, where
hi(n,, nu, 0) = inf se E [E (Assz. (Di, Dw), 0*)]
(6)
inf supo ce E [E (Ase (Di, (1) 0*)] Asg supa.ce E [ (Assz (Di, D.). 0*)]
hy(n,, Puy θ) := inf Am, supø Eo [ (AuL+ (Di, D.),, 0.)
where the expectations are over Dj (P&T)") m and D. (P n..
To simplify notation, we denote the improvement rates of SL and UL+ over (ls)) as hy Buy s) and ha (n, Rug s), respectively. A straightforward upper bound for these rates is h4. hy S 1, achieved when utilizing an SL and UL+ algorithm, respectively. SSL demonstrates an enhanced error rate over SL. and UL+ if both limmy oc. hu [i, The +) = 0 and limm, -o hy (wi, Tu. +) 0. If hy or h. lies in (0, 1) without converging to zero as ri,, Tu - xc, then SSL surpasses SL. or UL+ respectively, only by constant factor.

---

SNR Regime
Rate of growth of ne vs ny
hy nus s)
hu hn( Res s)
1/mma
Any
CSL
Thu o (m))
CST. 0
0 CUL
fixed 8 >>0 0
yu = w ((i)
Se
limm +000
T+es
CSt.
1+85c
CUL
Table 2: SSL improvement rates over SL and UL+ for different regimes of 8; My and nhe where by and hy are evaluated for lim,,,,.~70-
Given Theorem | we can directly derive the improvement rates of SSL in the following corollary.
Corollary 1. Assuming the setting of Theorem 7 the improvement rates of SSL can be written as:
Improvement rate over SL: by (mg, Duy 8) nn + s
s n
Improvement rate over UL+: by (ni, Thuy x
ny 2
Based on this corollary, we now argue how SSL algorithm can simultaneously improve the rates of both SL and UL+ for any regime of 8, ny and nu as summarized in Table
1. SSL rate is not faster than SL,, but is faster than UL+ For extremely low values of SNR (i.e. s - O faster than ynu -> oo), we have that limm,,.. he(n,, nue 8) = eST. >> 0 and hence SSL fails to improve the SL rates even with infinite unlabeled data. This setting has been the focus of previous worst-case analyses for SSL 66 36 20). Alternatively, the SSL rate is also not better than the SL rate for fixed SNR, when the labeled dataset is significantly larger than the unlabeled data, iee. n2 = o(m)).
2. SSL rate is faster than SL, but not faster than UL+ As mentioned in Göpfert et al. 200 in order for SSL to lead to rate improvement compared to SI., is necessary that the unlabeled set size is at least a superlinear function of the labeled set size, i.c. n, (nz). Corollary D shows that this condition is, in fact, sufficient for 2-GMM distributions: for > O, as long as n. grows superlinearly with respect to ny, he(n,, na, s) + 0, and hence, SSL can achieve faster rates than SL. Despite the improvement over SL, for this setting, the asymptotic error ratio between SSL and UL+ does not vanish, i.e. lim h2 (nt, nu, 8) CUL O.
SSL rate is not faster than either SL or UL+ Finally, in the regime where the unlabeled dataset size depends linearly on the size of the labeled set i.c lim an - c for some constant
0, neither of the improvement rates vanishes for n. +
As explained in Section 2.2 prior UL+ algorithms that work well in practice do use the labeled data for the unsupervised learning step. Interestingly, for the case when both the labeled and unlabeled data are used for the unsupervised step, the trends in reble the same, with only one exception: the improvement rates in the last line of the table (i.e. + E 20)) would only change by small constant. More importantly, the main takeaway from Table remiann the same: SSL cannot achieve better rates than both UL+ and SL at the same time since there is no regime for which h; and hy are simultaneously 0.
4 Empirical improvements over the rate-optimal SSL-S algorithm
Section 3 shows that the SSL minimax rates can be achieved with a simple algorithm that switches between a minimax optimal SL and a minimax optimal UL+ algorithm. Despite being optimal in terms of statistical rates, this SSL Switching algorithm does not make the most effective use of the available data: SL algorithms solely uses the labeled data whereas UL+ learns the decision boundary using just the unlabeled data and the labeled data is used to only label the different prediction regions. Alternatively, one could use both labeled and unlabeled data to learn the decision boundary. In this section, we investigate the following question: possible to improve over the error of SSL-S even though the rate would be, at best, good as the 'wasteful' SSL-S algorithm per Section 3
7

---

In this section, we present experiments to show that, in fact, a remarkably simple algorithm (i.e. a weighted ensemble of the SL and UL+ classifiers) can outperform the minimax optimal SSL-S algorithm. We show that algorithms such as self-training, which have been shown to excel in practice 40 34 22], can also improve over SSL--S. Consequently, it remains an exciting avenue for future work to derive tight analyses that characterize the improvement of such algorithms over SL/UL.+
A simple algorithm more effective than SSL-S A nat- ural approach to improve upon the naive SSL-S algo- rithm is to construct a weighted ensemble of an SL and UL+ estimator, trained on D2 and D.,, respectively, with a controllable weighting hyperparameter 1. We call this the SSL Weighted algorithm (SSL--W) shown in Algo- rithm 3 With an appropriate choice of t. it is possible to show that the SSL-W algorithm performs better (up to sign permutation) than SSL-S. The formal statement of this re- sult together with the proof are deferred to Appendix [ In practice, one can fix the sign permutation of the fSsL. w estimator using small amount of labeled data. The intuition for this improvement is that the ensemble estimator OssL-W achieves lower error than the constituent estimators of the ensemble (i.e. OSt. and O,,,,, which, in turn, determine the error of the SSL-S algorithm.
Algorithm 3: SSL-W algorithm
Input: Dj, Du.
Result: OSsL.W
OSI. (Di
Oun + (D; Du)
Ws) t0sl (1 t)0Ul+
return (s)
4.1 Empirical improvements over the minimax optimal SSL-S algorithm
In this section we present linear classification experiments on synthetic and real-world data to show that there indeed exist SSL algorithms that can improve over the error of the (minimax optimal) SSL Switching Algorithm. For both synthetic and real-world data, we use OSL. = 1 Ei=1 V,X; as the SL. estimator and an Dnpectattio-Maximmiaae for details). The optimal switching point for SSL-S and the optimal weight for SSL-W, as well as the optimal & penalty for logistic regression are chosen using a validation set.
nu
(EM) algorithm for the UL algorithm (see Appendix [
Synthetic data. We consider data drawn from symmetric and isotropic 2-GMM distribution P' over R²2 The labeled and unlabeled set sizes are set to 20 and 2000, respectively. Figure La shows the gap between SSL-W and SL or UL+ as function of the SNR s (Figure 3 in Appendix[F shows the dependence of the error gap on ny). There are two main takeaways. First, for varying SNR values
s. SSL-W always outperforms SL and UL+, and hence, also SSL-S. Second, as argued in Section 3.2 SSL-W improves more over UL+ for small values of the SNR 8, and it improves more over SL for large values of the SNR.
Real-world data. We consider 10 binary classification real-world datasets: five from the OpenML repository (37) and five 2-class subsets of the MNIST dataset [33. For the MNIST subsets, we choose class pairs that have linear Bayes error varying between 0.1% and 2.5% 4 We choose from
OpenML datasets that have a large enough number of samples compared to dimensionality (see Appendix D for details on how we choose the datasets). The OpenML datasets span a range of Bayes errors that varies between 3% and 34%.
In the absence of the exact data data-generating process, we quantify the difficulty of SSL on real-world
datasets using& a notion of compatibility, reminiscent of Balcan and Blum 4.. Specifically, we consider the compatibility given by p-1 with p 2va
1 (A(0i L+z 0 Bayes) + (e )). where
A00 Bayes) == 20 (8pga)))) d is the dimension of the data, Ojayes is obtained via SL on the entire dataset and Bin, determines the predictor with optimal sign obtained via UL on the entire dataset. Intuitively, this notion of compatibility captures both the Bayes error of dataset, as well as how compatible the 2-GMM parametric assumption actually is for the given data.
Rema((hinn)
In addition to SSL-S (Algorithm 2 and SSL-W (Algorithm 3) we also evaluate the performance of self-training, using procedure similar to the one analyzed Frei et al. [88. We use a logistic regression estimator for the pscudolabeling, and train logistic regression with a ridge penalty in the second stage of the self-training procedure. Note that an ls penalty corresponds to input consistency regularization 38 with respect to & perturbations.
We estimate the Bayes error of dataset by training linear classifier on the entire labeled dataset.
8

---

10
0.20
within the EntiLo) briseuWi
0.15
Entor gao
0.10
Ener p00rpa0
-0.05
-0.10
mrit, 30l
SuB
gin
matelre 1u Dut
0.12
8.30
0.25
025 0.40
Dalasels by compalibily large)
(a) 2-GMM synthetic data.
(b) Real-world data.
Figure I: Error gap between SL or UL+ and SSL-W for varying task difficulties. We assess problem difficulty using the SNR (for 2-GMMs) or the compatibility o (for real-world data). We see the same trends for both synthetic and real-world data. Moreover, self-training also exhibits the same trend OSsL-W-
Figure Ib shows the improvement in classification error of SSL algorithms (i.e. SSL-W and self- training) compared to SL and UL+ The positive values of the error gap indicate that SSL-W outperforms both SL and UL+ even on real-world datasets. This finding suggests that the intuition presented in this section carries over to more generic distributions beyond just 2-GMMs. Finally, Figure Appendix (Fshowss that SSL-W improves over the error of the minimax optimal SSL-S algorithm, for varying values of These findings provide some existing SSL algorithms may already obtaining lower error than the minimax optimal SSL-S algorithm. We hope this observation will encourage future research into characterizing this error gap for practically relevant algorithms such as self-training.
evidence that
Related work
Other theoretical analyses of SSL algorithms. Beyond the theoretical studies highlighted in Sec- tion there are few others pertinent our research. Specifically, Azizyan al. [1] Singh al. present upper bounds for semi-supervised regression, which are contingent on the degree to which the marginal Px informs the labeling function. This is akin to the results derive in this work. However, obtaining a minimax lower bound for semi-supervised regression remains an exciting direction for future work. We refer
3
27 for overview of prior theoretical results for SSL.
Balcan and Blum 4 introduced a compatibility score, denoted as x(f, Px) E [o, 1], which connects the space of marginal distributions the space of labeling functions. While their findings hint that SSL may surpass the SL minimax rates, they offer no comparisons with UL/UL+. Moreover, the paper does not diseuss minimax optimality of the proposed SSL algorithms.
On another note, even though SSL does not enhance rates of UL. Sula and Zheng 35 demonstrate that labeled samples can bolster the convergence speed of Expectation-Maximiae context of our study.
To conclude, Schölkopf et al. [32] leveraged causality framework to pinpoint scenarios where SSL does offer any advantage over SL. essence, when the covariates, represented by X, act as causal ancestors to the labels Y, the independent causal mechanism assumption dictates that the marginal Px offers no insights about the labeling function.
Minimax rates for SL and UL. The proofs in this work rely techniques used to derive minimax rates for SL and UL algorithms. Most of these prior results consider the same distributional assump- tions as paper. Wu and Zhou (39 show tight minimax lower bound for estimation error for spherical 2-GMMs from P2GMM- Moreover, Azizyan et al. (2). Li et al. 24 derive minimax rates over P2-MMM for classification and clustering (up to permutation).
3 Expectation-Maxinnee Maximization (EM) another family of algorithms that is commonly analyzed for the same distributional setting considered our paper. For instance, Wu and Zhou (39] rely on techniques from several previous seminal
In addition to SL and UL algorithms considered in Section
papers 12 3 14 to obtain upper bounds for EM-style algorithms.

---

Conclusions and limitations
In this paper, we establish tight lower bound for semi-supervised classification within the class of 2-GMM distributions. Our findings demonstrate that SSL cannot simultaneously improve the error rates of both SL and UL across all signal-to-noiss ratios. However, empirical evidence suggests that SSL can improve upon the error of minimax optimal SL or UL algorithms. This observation calls for careful analyses of the error of SSL algorithms that also track constant factors, not only rates.
Our theoretical analysis focuses exclusively on isotropic and symmetric GMMs due to limitations in the technical tools employed for the proofs. Similar constraints be observed in recent analyses of SL or UL algorithms [24] 33]. However, it is worth noting that whenever the bounds for SL and UL can be extended more general distributions in the future, these results can be scamlessly used to also extend Theorem to these settings.
Acknowledgement
was supported by PhD fellowship from the Swiss Data Science Center. We also thank the anonymous reviewers for their helpful comments.
10

---

References
[1] Martin Azizyan, Aarti Singh, and Larry Wasserman. Density- semisupervised inference. The Annals of Statistics, 2013.
[2] Martin Azizyan, Aarti Singh, and Larry Wasserman. Minimax theory for high-dimensiona. gaussian mixtures with sparse mean separation. In Advances in Neural Information Processing Systems, 2013.
[3] Sivaraman Balakrishnan, Martin J. Wainwright, and Bin Yu. Statistical guarantees for the EM algorithm: From population sample-base based analysis. The Annals of Staristics, 2017.
[4] Maria-Florina Balean and Avrim Blum. A discriminative model for semi-supervised learning. Journal of the ACM, 2010.
[5] Randall Balestriero, Mark Ibrahim, Vlad Sobal, Ari Morcos, Shashank Shekhar, Tom Goldstein, Florian Bordes, Adrien Bardes, Gregoire Mialon, Yuandong Tian, et A cookbook of self-supervised learning. A.Kiv:2304.122111 2023.
[6] Shai Ben-David, Tyler Lu, and Dávid Pál. Does unlabeled data provably help? Worst-case analysis of the sample complexity of semi-supervised learning. In Annual Conference on Learning Theory (COLT), 2008
[7] Avrim Blum and Tom Mitchell. Combining labeled and unlabeled data with co-training. In Annual Conference Learning Theory (COLT), 1998.
(8) Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised learning of visual features by contrasting cluster assignments. Advances in Neural Information Processing Systems 33, 2020.
[9] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. simple framework for contrastive learning of visual representations. In 37th International Conference on Machine Learning. 2020.
[10] Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey Hinton. Big self-supervised models strong semi-supervised learners. In Advances in Neural Information Processing Systems 33, 2020.
[11] Thomas M. Cover and Joy A. Thomas. Flements of Information Theory. 2006.
[12] Constantinos Daskalakis, Christos Tzamos, and Manolis Zampetakis. Ten steps of EM suffice for mixtures two gaussians. In Annual Conference on Learning Theory (COLT), 2017.
[13] Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 2012.
[14] Raaz Dwivedi, Nhat Ho, Koulik Khamaru, Michael I. Jordan, Martin J. Wainwright, and Bin Yu. Singularity, misspecification and the convergence rate of em. The Annals of Statistics, 2018.
[15] Raaz Dwivedi, Nhat Ho, Koulik Khamaru, Martin Wainwright, and Michael Jordan. Theo- retical guarantees for EM under misspecified gaussian mixture models. In Advances in Neural Information Processing Systems 31, 2018.
[16) Raaz. Dwivedi, Nhat Ho, Koulik Khamaru, Martin Wainwright, Michael Jordan, and Bin Yu. Sharp analysis of maxiaiizaoinniiiiiiiiioonoooonn for weakly identifiable models. In International Conference on Artificial Intelligence and Statistics, 2020.
[17] Alaaeldin El-Nouby, Gautier Izacard, Hugo Touvron, Ivan Laptev, Hervé Jegou, and Edouard Grave. Are large-scale datasets necessary for self-supervised pre-training? arXiv:21 10740, 2021.
[18] Spencer Frei, Difan Zou, Zixiang Chen, and Quanquan Gu. Self-training converts weak learners to strong learners mixture models. International Conference on Artificial Intelligence and Statistics, 2022.

---

[19] Christophe Giraud. Introduction to high- high-dimensional statistics. CRC Press, 2021.
[20] Christina Göpfert, Shai Ben-David, Olivier Bousquet, Sylvain Gelly, Ilya O. Tolstikhin, and Ruth Urner. When can unlabeled data improve the learning rate? In Annual Conference Computational Learning Theory, 2019.
[21] Priya Goyal, Dhruv Mahajan, Abhinav Gupta, and Ishan Misra. Scaling and benchmarking self-supervised visual representation learning. In International Conference on Computer Vision, 2019.
[22] Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, al. Bootstrap your own latent-a new approach self-supervised learning. Advances in Neural Information Processing Systems 33, 2020.
[23] Yann LeCun and Corinna Cortes. MNIST handwritten digit database, 2010. URL http:
//yann. lecun. com/ exdb/mnist//
[24] Tianyang Li, Xinyang Yi, Constantine Carmanis, and Pradeep Ravikumar. Minimax Gaussian Classification & Clustering. In 20th International Conference on Artificial Intelligence and Statistics, 2017.
[25] Thomas Lucas, Philippe Weinzaepfel, and Gregory Rogez. Barely- learning: semi- supervised learning with very few labeled images. In AAAI Conference on Artificial Intelligence. 2022.
[26] Pascal Massart. Concentration inequalities and model selection; Ecole d' E'é de Probubilités de Saint-Flowd XXXIII-2003. Springer, 2007.
[27] Alexander Mey and Marco Loog. Improvability through semi-supervised learning: A survey of theoretical results. arXhv:1908.09557 2020.
(28) F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 2011.
[29] John Platt et al. Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. Advances Large Margin Classifiess, 1999.
[30] Joel Ratsaby and Santosh S. Venkatesh. Learning from a mixture of labeled and unlabeled examples with parametric side information. In Annual Conference Learning Theory (COLT), 1995.
[31] Philippe Rigollet. Generalization error bounds in semi-supervised classification under the cluster assumption. Journal of Machine Learning Research, 2006.
[32] Bernhard Schölkopf, Dominik Janzing, Jonas Peters, Eleni Sgouritsa, Kun Zhang, and Joris Mooij. On causal and anticausal learning. In 29th International Conference on Machine Learning, 2012.
[33] Aarti Singh, Robert D. Nowak, and Xiaojin Zhu. Unlabeled data: Now it helps, now it doesn't. In Advances in Neural Information Processing Systems 21, 2008.
[34] Kihyuk Sohn, David Berthelot, Nicholas Carlini, Zizhao Zhang, Han Zhang, Colin A Raf- fel, Ekin Dogus Cubuk, Alexey Kurakin, and Chun-Liang Li. FixMatch: Simplifying semi- supervised learning with consistency and confidence. In Advances in Neural Information Processing Systems, 2020.
[35] Erixhen Sula and Lizhong Zheng. On the semi-supervised expectation maximization. arXiv:2211 1.0053,, 2022.
[36] Ilya O. Tolstikhin and David Laz. Minimax lower bounds for realizable transductive classification, arXiv:1602.03027 2016.
12

---

[37] Joaquin Vanschoren, Jan N. van Rijn, Bernd Bischl, and Luis Torgo. OpenML: networked science in machine learning. SIGKDD Explorations, 2013.
[38] Colin Wei, Kendrick Shen, Yining Chen, and Tengyu Ma. Theoretical analysis of self-training with deep networks on unlabeled data. In International Conference on Learning Representations, 2021.
[39] Yihong Wu and Harrison H. Zhou. Randomly initialized EM algorithm for two-component gaussian mixture achieves near optimality in O(yn) iterations. Mathematicaa Statistics and Learning, 2021.
[40] Qizhe Xie, Minh- improves ImageNet classification. June 2020.
Minh-Thang Thang Luong, Eduard Hovy, and Quoc V. Le. Self-training with noisy student
[41] David Yarowsky. Unsupervised word sense disambiguation rivaling supervised methods. In 33rd Annual Meeting on Association for Computational Linguistics, 1995.
[42] Barret Zoph, Golnaz Ghiasi, Tsung- Yi Lin, Yin Cui, Hanxiao Liu, Ekin Dogus Cubuk, and Quoe
Le. Rethinking pre-training and self- self-training. In Advances in Neural Information Processing
Systems 33, 2020.
13

---

A Proof of Proposition
In this section we provide the formal statement of Proposition I and its proof.
Proposition 2 (Fixing the sign of duz). There exist universal constants co. C1. C2 C3. C4 > 0 such that for Ru (160/s)²d, dd d and (0, 11, holds that:
d
C2se 11 slggen))
E 0 -01l
Ciy s
and
E [((U)))) Oze- 70² d dloo(dwu))
-2e-22oun -200mm (1-c0/
+ Cae
n
Proof. Recall that consider the UL+ estimator Oun sign (0 OvL Q.. and denote B := sign (03, D..). Now let B sign(0" (un.) arg me( 11300. 0-1
Note that we can write the expected estimation error of dUL+ as
|1uu 0']] = E 11,0uz 0*1]
18=03 (18=0)11000. - + 1 [0+0] 11 11.001. +01l|
= L
< E 18-0) 1150uu - |] + E (1488) (11 00 + 2 0
< EE 11,60ur 0-1 + 2 3).
(8)
Next, we recall a result by Wu and Zhou 39 established for this particular UL estimator, namely
that E 11,80u 1* S sm.. Moreover, the probability of incorrectly estimating the sign (permutation) can be written as
[3 = PP sign (0 Bu) # sign (o-Toul) where Ōst ~ ~N(0", -Ta IP sign( ?) # sign (oTTOul) where 7 ~ -N 0-, m 1 (0T ((.))
n
<P z' 01) where 2' ~NO0 my
Ou.))
P 2 2 (clu,
where Z N(O0 1) and So (0_1, 0*)
00 0- 1t. |||@01
Therefore, for any A we have:
P(β + B) < P(Z 2 V (1 A)) + P (S 0*) s A)
<e- ( P (0 01= 11
dlog(n.)) where we used the Chernoff bound the last step. Finally, setting A = co stn
as a corollary
of Proposition 6 in Azizyan et 2 for n., 2 (160/s)²d we have IP (0n.. 0*) S A
S d_
n...
Therefore, for n. 2 (160/s) yd, we have the following upper bound on estimating the sign incorrectly:
P( + B) Se 2nnn =
of Jogt
d
14

---

Combining this result with Equation 8 finishes the proof of the estimation error bound in the proposition, as we obtain that for some C₁. C2 0, the following holds:
E E[110L- 001 s
d s
+ C2sc (1-02 y
Similarly, we can decompose the expected excess risk as follows:
E [((UL))) = [ = L (d= ((80UL) (1=0))((00)) + [840)
E (8-8) ((30UL) [ +
(8 8 (
E ((30m)) + 11 [8=0}]
(10)
E [((SOUL) P( + B),
where in Equation (TO) upper bound the indicator function and the excess risk terms by 1. Finally, combining Equation with the upper bound in Li et al. [24] for E [((0u)) we obtain the desired result. More concretely, we get that for some C3 C4 > 0,
E [(((u))) s Cge-fo" (ggddog) + C4e = /d /dlggtmn
B Proof of SSL Minimax Rate for Estimation Error in Theorem 1
In this section we provide the proofs for the lower and upper bounds on the estimation error presented in Theorem
The proof for the excess risk rates can be found in Appendix I
B.1 Proof of estimation error lower bound
We first prove the estimation error lower bound in Theorem |
As discussed Section 2 consider
the 2-GMM distributions from (s)
2-GMM- with isotropic components and identical covariance matrices.
Consider an arbitrary set of predictors M {0: M. We can apply Fano's method to obtain
that the following holds:
inf sup ED, (Resim (Di, Du), P Assi 0 ||ms
1+ 1 MM M
D xx "p.""
"12"" Px 00
-=
100 - -1ill (M ifj
min
log(M)
1+ 1 ΣM
1i=1 myD P& 11
+ n.D (PLt (PP.111PP))) [1P)00
1 min
M
| 0;
(11)
log(M) (M)
ifj
pe. (p (p + n. max D (P&
+ ny max (E[M]
[E[M]
2 2
min
|0; 0
{.jE[M]]
log(M)
#
(12)
15

---

where D (-I1-) denotes the KL divergence. In Equation (TI). we use the fact that the labeled and
unlabeled samples are drawn i.i.. from Px and Pxy and in Equation (12) we upper bound the
average with the maximum. The next step of the proof consists in choosing an appropriate packing
(0.),-r and Og on the sphere of radius i.e. 0 5d-1, that optimizes the trade-off between the minimum and the maxima in Equation (22)
For the packing, we use the same construction that was employed by Wu and Zhou 33 for deriving adaptive bounds for unsupervised learning. This construction has the advantage that it also leads to a tight lower bound for the supervised setting. Let co and Cu be positive absolute constants and let M {vi, .... v'M} } be co-net on the unit sphere 5d such that we have |M M 2 eood For an absolute constant [0, 1], we construct the following packing of the sphere of radius in Rd:
VII a²
M 0:
4/s E M
and define du = [s, 0, .... 0J. Note that, by definition, |00 - , cusa, for any distinct i, E [M], which lower bounds the first term in 12).. Furthermore, |00 - 0ol S 22ss, for all E [M].
In the next step, upper bound the maxima in Equation between two GMMs with identity covariance matrices:
12 First, we write the KL divergence
D (
P 110: -01l S aass for all [M].
(13)
Second, we upper bound the KL divergence between marginal distributions, namely D p ) using Lemma 27 in Wu and Zhou [39 which implies that:
max D iE[M]
( 1
0 11 S
max xE[M]
1 -
00 84
(14)
8
Plugging Equations 13 and (14) into Equation
12
we obtain the following lower bound for the
minimax error, which holds for any a <
inf sup ED. (Assi (Assi Dw), 00) coass (1 (1- Assi | =a
1 + nisaa 2 + n, nnstaaaa)
Cod
Cod }. Minimizing over a yields the optimum value a = min +-C s. where the minimum
comes from how have constructed the packing, which requires that S 1. Using this value for concludes the proof.
B.2 Proof of estimation error upper bound
We now prove the tightness of our lower bound by establishing the upper bound for the estimation error of the SSL Switching algorithm presented in Algorithm We choose the following minimax optimal SL and UL+ estimators
0S1.
Y,X,
(15)
i=1
dUL+ sign (0 Ou our with duL Va 1)+0.
(16)
where (i, 6) is the leading eigenpair of the sample covariance matrix E = n. Σラ= X,X7 and
use the notation (z)+ max(0, 2². is known that this UL estimator is minimax optimal 39 As
unsupervised learning can only obtain classifiers up to sign permutation, it is necessary to endow the UL+ algorithm with means to discer between dur and -OUL. explained in Section 2.2 In
16

---

the case of the estimator introduced in Equation (16), the sign is selected so to obtain an estimator that aligns better with the Ast. The upper bound for the expected error incurred by the UL+ estimator given Proposition 2
For the SL estimator OSL. we upply standard results for Gaussian distributions to upper bound the estimation error that holds for any regime of n and d:
Ep. [10sl - 0'1
(17)
Using Equation 177 and Proposition 2 and switching between dsL and duL- according to the conditions in Algorithm 2 that pick the better performing of the two algorithms depending on the regime, we can show that there exist universal constants C, such that for 1.d2? and nu 2 (160/s)²d d, it holds that
E [[OSSLS -0'l 0'l]
d
d
+ tnnoa (1-eoy
Zloginn)
C'mnn 8,
(18)
ni
spm,
where the expectation is over Dj (Px)) n and Du (P8))
becomes negligible and the first additive component dominates in the last term in the right-hand side of
Matching lower and upper bound. When ny
0 los(())))
). the exponential
Equation 18). Basic calculations then yield that the expected error of the switching algorithm is
upper bounded by C" Cmmin" { nutt-ny for some constant C², which concludes the proof of the theorem.
C Proof of SSL Minimax Rate for Excess Risk in Theorem 1
In this section, prove the minimax lower bound on excess risk for algorithm that uses both labeled and unlabeled data and matching (up to logarithmic factors) upper bound.
C.1 Proof of excess risk lower bound
We first prove the excess error minimax lower bound in Theorem I namely we aim to show that there exists constant Cp such that for any 0, Rl; ny and d 2 have
d
inf sup E {E (AssL (Di, Du), )) 2 Coe 3/2 min Assi |0
(19)
smi + S
where the expectation over Dr ~ (Pyr T4 and D. (P$*) Our approach to proving this
lower bound is again to apply Fano's 's method [99 using the excess risk as the evaluation method. The reduction from estimation to testing usually hinges on the triangle inequality a metric space. Since the excess risk does not satisfy the metric axioms, employ technique introduced in Azizyan et al. to derive an alternative sufficient condition for applying Fano's inequality.
Let 0,, .......,0A OM E O, 2 2, and 7 > If all 1 S i + j. M and O,
E (0.0: < implies E (0.0.) 2
(20)
then
inf max E [E (Assi (Di, Dw). 0.) Ass. sE[O..M]
(21)
1 max D (
1 +
11
max D
11
if1
2 ?
log(M)
17

---

where the expectation is over Dj (Pfr) and D, ~ ( Thu
In order to get lower bound, we again pick 0 .,..... DM to be an appropriate packing, so that the condition in Equation (20) can be satisfied. For this purpose, we can simply use the construction from Li et al. [24). which was previously used to obtain tight bounds for supervised and unsupervised settings. Let
(d 1)/6. By Lemma 4.10 in Massart (26), there exists set M {vI,..., vMM) h. such that || ll = 4/: E [0,1) the Hamming distance ó (1h,, vby)) > p/2 for all 1 isi<) M MM, and log M 2 log di P
2 d llg(())/60 =ld.
Define
V pa? azi;
W M
M = 0
for some absolute constant a. Note that since |011| = and 10; 0, a²8 (1hr, 0g)) we have
pa
2 - 00: - 0 < 2pa2
(22)
and
3² - pa
0 0, S 3² pa? /4.
(23)
First, we show that the excess risk satisfies the condition in Equation 20 As in the proof of Theorem in Li et al. [24), we have that for any 0,
0 0.) E(0,0, 2c0e - pa2
and thus, for all i and j + i, it holds that
pa2
E(0,0,) 2 cue que- 202
E 00 0,) S cue
(24)
Then since the condition in Equation (20 is satisfied, we obtain
inf sup EDI.D, [E (Assi. (Di, , 0*)]
ASs |10 ||=s
2 inf max Assa iE(O..M)
EE (AssL (D), Du), 0:)]
(25)
1 nu max D (pxillex)) XX nu max D
(P& ||
Cue 22/2pa2
(f)
183
1
log(M)
Next, we bound the KL divergences between the two joint distributions and between the two marginals that appear in Equation (25). For the joint distributions we have that:
D (P
- 1 sa?
(26)
where the inequality follows from Equation (22). bound the KL divergence between the two marginals
Using Proposition 24 in Azizyan et al. [ we
0. 02
D
Px
S ps 2
(27)
||
where the inequality follows from
23 Plugging
26 and (27 into 25) and setting
cjd log 2
a² min
8(pn) s2pm,, p
gives the desired result
inf sup ED, [E (AssL (D,, (,),00)] ) e - min
Assi ||0- =
18

---

C.2 Proof of excess risk upper bound
Next, we prove the upper bound on the excess risk of the SSL switching estimator OSLLS output by Algorithm with the supervised and unsupervised estimators defined in Appendix [8.2 to show the tightness of the excess risk lower bound in Theorem [ In particular, we show that there exist universal constants C, co > such that for 0 S 8 1.
and for sufficiently large na and nt,
[(Oss & Ce - 20² min dllo((m) dllo(ddnn)
3400 ny
(1-000
te
83
where the expectation is over Dj (Pxr) " and D.
(PX nM
The proof follows the same arguments the proof presented Appendix B.2 where we instead use excess risk upper bounds for SL and UL from Li et al. (24).
In addition, we also result that follows from Proposition estimator.
2 choose the sign of the UL+
Note that the upper bound on the excess risk of fSSL- is matching the lower bound in Equation 19 up to logarithmic factors. We conjecture that the logarithmic factors are an artifact of the analysis and can be removed. For instance, it may be possible to extend results in Ratsaby and Venkatesh 30 that bound the excess risk using the estimation error upper bound without incurring logarithmic factors. However, their results not directly applicable here because they only valid under the assumption that the estimation error is arbitrarily small and hence not enough for bounding the expectation.
D Theoretical motivation for the SSL Weighted Algorithm
In this section, we show theoretically that the SSL-W procedure introduced in Section 4 can achieve lower squared estimation error (up to sign permutation) compared to SSL-S. This result shows that it possible to improve the error of the naïve SSL-S algorithm by making effective use of all the data that is available.
For the purpose of the theoretical analysis, we consider slightly different SSL-- estimator compared to the one introduced Section First, recall that for the classification problem we consider, unsupervised learning produces a set of two feasible predictors {Ou.. - -On.} and cannot discern between them without access to a (small) labeled dataset. We denote by oü. the UL estimator with correct sign, namely din := arg min g
E ||e 1000-)11) Here, the hat symbol indicates that finite sample is used obtain the set of estimators {Ôu.. O. while the star symbol indicates that oracle information is employed to choose the sign of the estimator.
1-]]
In what follows, we study theoretically the error of the SSL-W estimator constructed using Oür, i.e. ÖSSL- (t) t0st + (1 f) -1-1)0in Therefore, our result characterizes the error of the SSL-W estimator up to a sign permutation. To choose the correct sign, one needs only small labeled dataset, similar in size to what is prescribed by Proposition 2 While this step is not captured by Proposition 3 SSL-S is unlikely to close the gap to SSL-W when provided with this small amount of additional labeled data. Moreover, for a fairer comparison also give the switching estimator access to the UL estimator with correct sign and define 05SL.S == arg minoe (i.)) E ||e [1]
We can now state Proposition Bl which shows that there exists optimal weight for which the SSL-W predictor achieves lower estimation error than the SSL Switching predictor, ŌSSLSS
Proposition 3. Consider distribution poy E p(s) aamm and let 2 2, and n4s ny > Let (isr.w(t") be the SSL- W estimator introduced above. Then there exists t" E E00, for which
- E 0 (0)) -0'1""
1 min r,
L (is) [ -o
E
SSL. - 0"
(28)
where
Elll0t1
El
00
and the expectations over Dr (PYt) n DD, (PZ")"
19

---

Err(SSL-S) Err(SSL-W)
10-2
10
Error gap
10
10
n, 50, nu = 10000
n, 100, n, 10000
10 -10
n = 1000, nU = 10000
0.0
0.2
0.4
0.6
0.8
1.0
SNR
Figure 2: Estimation error gap between SSL-S and SSL-W as revealed by Proposition for varying SNR and ny (n,, 10000). The maximum gap is reached the switching point, indicated by the vertical dashed lines.
Since the RHS Equation 28 is always positive, Ss (L*) always outperforms dssL. as long as the conditions of Proposition are satisfied. The magnitude of the error gap between SSL-S and SSL-W depends on the gap between SL and UL+ (see Figure 2). The maximum gap is reached for
0ūL 0"
~ 0s1
0-
when SSL-W obtains half the error of SSL-S.
D.1 Proof of Proposition 3
The first step in proving Proposition 3 to express the estimation error of (t") in terms the estimation errors of Ōsl and dün which is captured by Lemma]
Lemma Let 0 and 02 be two statistically independent estimators of 0 E Rd and let 0 be unbiased, iee. F 0 0" Then, the expected squared error of the weighted estimator dr.
F 1 1-
00 + (1- 02 with to Elo - 0
is given by
+E
02 1-
(F [ (
E [10.- 1/]]]]
1
IF |000 0-112)
We can apply Lemma since Ôs.. is unbiased and f.. and oü are trained on Dj and D, respectively, and hence, independent. The proof then follows from calculating the difference between the harmonic mean and the minimum of estimation errors of θs and θUL.. Let x, y E R4 and w.l.o.g. assume < y. Then we have:
1
x²
T Ty
1/
T.
1
E E|110_
Applying this identity concludes the proof after choosing t" El -0-1 +E O2 1-|
and for
min (lll0t - [P] Os. 111 and max [ElI00 0 0*11 (s.. 0 0'11
Remark. Note that this lemma holds for arbitrary distributions and estimators as long as they are independent and one of them is unbiased. Therefore, future results that derive upper bounds for SL and UL+ for other distributional assumptions and estimators can seamlessly be plugged into Lemma [ By the same argument, @SsL. obtained by other SI. and UL+ estimators can also be expected to improve over the respective SL and UL+ estimators, given that one of them is unbiased.
20

---

D.2 Proof of Lemmal
By definition of e.., we have
[100,- 11
||t 0, + + (1-t")02 1-
1<2 0 0- (1- 11- 0-1 21" (1- (=) T 07)
p22 01 10 + (1- -1- - 0113 -0010)
where the last equality holds due the independence of 0, and 02 and the unbiasedness of 0
=1102-0'12
Plugging in 1"
we get
134110
10-1-
E E
1
E 0 0-1
E|10;
-011
1-
02 1
El 0 1 12
E| 2
E
0-112 + E| 02 0- 112
E 0 || 02 - 1-
E
0 0 1 + E 0 0+ 112
0
01
E Simulation details
E.1
Methodology
We split each dataset in test set, validation set and training set. The unlabeled set size is fixed to 5000 for the synthetic experiments and 4000 for the real-world datasets. The size of the labeled set ny is varied in each experiment. For each dataset, we draw a different labeled subset 20 times and report the average and the standard deviation the error gap (or the error) over these runs. The (unlabeled) validation set and the test set have 1000 labeled samples each.
We use logistic regression from Scikit-Learn (8 the supervised algorithm. We use the validation set to select the ridge penalty for SL. For the unsupervised algorithm, we use an implementation of pnpecaation-Maxiizzzaiiio from the Scikit-Leamn library. We also use the self-training algorithm from Scikit-Leean with logistic regression estimator. The best confidence threshold for the pseudolabels selected using the validation set. Moreover, the optimal weight for SSL-W also chosen with the help of the validation set. Since we an unlabeled validation set, need to employ an appropriate criterion for hyperparameter selection. Therefore, we select models that lead to a large (average) margin measured on the unlabeled validation set. We give SSL-S the benefit of choosing the optimal switching point between SL and UL+ by using the test set. Even with this important advantage, SSL-W (and sometimes self- telf-iraining) still manage outperform SSL-S.
E.2 Details about the real-world datasets
Tabular data. We select tabular datasets from the OpenML repository [37 according to a number of criteria. We focus high-dimensional data with 100 < d < 1000, where the two classes are not suffering from extreme class imbalance, i.e. the imbalance ratio between the majority and the minority class is at most 5. Moreover, only consider datasets that have substantially more samples than the number of features, i.e. 4 > 10. the end, we are left with 5 datasets, that span a broad range of application domains, from ecology chemistry and finance.
To assess the difficulty of the datasets, we train logistic regression on the entire data that is available, and report the training error. Since we train substantially more samples than the number of
21

---

dimensions, the predictor that we obtain is good estimate of the linear Bayes classifier for each dataset.
Furthermore, we measure the extent to which the data follows a GMM distribution with spherical components. We fit spherical Gaussian data coming from each class and use linear discriminant analysis (LDA) for prediction. We record the training error (of the best permutation). Intuitively, this a score of how much our assumption about the connection between the marginal Px and the labeling we take 0 Bayes to be the linear Bayes classifier and frr the LDA classifier described above If the data is almost linearly separable (i.e. Rered P0 (ayes) - 0.01), then we simply take the linear Bayes error as the compatibility.
function P(Y (X) is satisfied. For Figure I
Image data. In addition to the tabular data, we also consider number of datasets that subsets of the MNIST dataset [23]. More specifically, we create binary classification problems by selecting class pairs from MNIST. We choose 5 classification problems which vary in difficulty, as measured by the Bayes error, from easier (e.g. digit O vs digit I) to more difficult (e.g. digit 5 vs digit 9). Table presents the exact class pairs that we selected. To make the problem more amenable for linear classification, we consider covariates the 20 principle components of the MNIST images.
Datasct name
d
Linear classif. training error
LDA w/ sphorical GMM training ertor
mnist_ Ovl
784
0.001
0.009
mnist Iv7
784
0.006
0.036
madeline
259
0.344
0.381
philippine
308
0.240
0,318
vehicleNorn
0.177
mnist 5v9
784
0.024
0,045
mnist
0.042
a9n
123
0.150
0,216
mnist_3v8
784
0.042
0,105
musk
166
0.037
0.270
Table 3: Some characteristics of the datasets considered in our experimental study.
F
More experiments
In this section we present further experiments that indicate that the SSL Weighted algorithm (SSL-W) can indeed outperform the minimax optimal Switching algorithm (SSL-S). Figures 3 and 4 show that there exists a positive error gap between SSL-S and SSL-W for a broad range of values, for synthetic and real-world data, respectively. The extent of the error gap is determined by the The ratio as well the signal-tonoisee ratio that is specific to each data distribution. In addition, Figure also indicates that self-training can outperform SSL-W in some scenarios. It remains an exciting direction for future work to provide tight analysis of self-training that can indicate when outperforms both SL and UL+ simultaneously.
0.0200
Em(SSL-S)- Em(SSL-W)
0.0175
Error gap
0.0150
0.0125
0.0100
0.0075
0.0050
0.0025
100
150
200
250
Labeled set size ni
Figure 3: Error gap between SSL-S and SSL-W on synthetic 2-GMM data with s 0.1. The positive gap indicates that SSL-W outperforms SSL-S (and hence, also SL and UL+).
'Note that we refer to the LDA estimator as UL since we use it as a proxy to assess how well unsupervised learning can perform on each dataset.
22

---

philippine
musk
mmist. 5v8
Em(SSL-S- Em(SSL-W)
0.00
0.01
En(SwrT)- Em(BSL JN]
-0.05
Error gRD
Error 9R0
-2.10
EmSSL: EmSSL W)
0.18
Br(SerT) EMSSLLW)
-000
Em|SSL-S) EmSSL-W)
Em[SelfT) EmSSL-Wi
0.00
-225
-390
Labeledd set size
Labeled size
Labeled set size
mniet 3v8
a9a
mnist, 5v6
Em(SSL-S EmSSSLWW
Er(Sw(T)) Em188L JN)
Eiror gep
-0.05
gap
Er(SSL-S)) Em(SBL-W (r(()))) Em185L-W)
Fri(8LL-8) EmSSL-W) Er((arIT) EM(SSL-W)
0.01
-0.15
Labeled siz9
Labeled size
Labeled get size
vehideNomn
madeline
mrrist 1v7
En(SSL Em(SSL
0.00
0.82
0,000
Em(SeiT) Emrsst 4V)
-3.02
0,010
-0002
-2.08
EmSSL-S)- EmSSL-W) EmSerT) EmSSLL W)
0,008
EmISSL-S)- ErISSL-W
0,000
Em:SelfT) EmSSL-W)
-0.05
-210
20 Labeled eot
30
Labeled
Labeled
mnist
0.00
-0.01
Eroor gap
-3.02
0.00
Em((SLL-8) EmSSL-WW
Err/eefT)) EmSSL-W)
20 20
40
"Labeled set size Ry
Figure 4: Error gap between SSL--S/selftrrinnngg and SSL-W real-world datasets. The positive gap indicates that SSL-W (and, in turn, self-training) outperforms SSL-S (and hence, also SL and UL+) for broad range of ny values.
23


Reviews:
[{"review_id": "XCbT5ggse9", "reviewer": "Reviewer_N4Bc", "summary": "The paper provides a tight lower bound for semi-supervised learning for the 2GMM model. It compares the minimax rate with supervised and unsupervised learning. The authors also provide supporting experiments on real-world and synthetic datasets.\"", "questions": "1. Line 65: There seems to be a typographical error in the notation \"A(D_l, D_l).\" Please clarify this notation.\n\n2. Line 121: I assume that 'u' represents a function mapping the number of labeled data points to the corresponding number of unlabeled data points. Can you please confirm this understanding?", "limitations": "The authors have adequately addressed the limitations.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The paper is very well-written. The authors have effectively communicated their ideas, making it easy for readers to follow and understand the research.\n\n2. The results presented in the paper go beyond existing prior work (when s > 0). \n\n3. The authors have conducted experiments to support their theoretical analysis. This empirical validation strengthens the credibility of their findings and enhances the practical relevance of the proposed approach.", "weaknesses": "The paper relies on strong assumptions regarding the 2GMM and linear model. This might limit the generalizability of the proposed method to other scenarios or data distributions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for appreciating our results and empirical validation as well as the clarity of our writing! We are grateful for the points that you have brought up in the review! We addressed your comment on the 2-GMM distribution in the “General comments” and now answer your remaining specific questions.\n\n> There seems to be a typographical error in the notation \"A(D_l, D_l).\" Please clarify this notation.\n\nIndeed, the notation should read $\\mathcal{A}(\\mathcal{D}_I, \\mathcal{D}_u)$, that is, the algorithm $\\mathcal{A}$ is applied to the labeled set $\\mathcal{D}_l$ and the unlabeled set $\\mathcal{D}_u$ – we will correct this and other typos in the final version of our manuscript.\n\n\n> I assume that 'u' represents a function mapping the number of labeled data points to the corresponding number of unlabeled data points. Can you please confirm this understanding?\n\nYour understanding is indeed correct.\n\nWe again appreciate your time and effort in reviewing the paper.  We will be happy to answer any further questions you may have about our manuscript.\n"}, {"review_id": "hSkexiNyWz", "reviewer": "Reviewer_KqNv", "summary": "This paper analyzes the effect of SSL methods to improve the error bound. The results suggest that SSL cannot improve over the statistical rates of both SL and UL at the same time, but it is possible to improve the errors by a constant factor. Simple experiments on synthetic and small-scale real-world data validate the theoretical findings.", "questions": "Please address the concerns in the weaknesses part.", "limitations": "The main limitation of this paper is that the analyses mainly focus on GMMs, which limits the scope of application.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper studies an interesting and important problem: whether semi-supervised learning can effectively use all the data.\n- A detailed theoretical study is provided on the 2-GMM distribution, which sheds light on this problem. Modification:\n- Though simple, the proposed SSL switching algorithm is interesting and insightful. ", "weaknesses": "- The theoretical analysis is based on GMM, which introduces a strong assumption about the data distribution. This limits the scope of application of the theoretical analysis. \n- The proposed SSL switching algorithm introduces an extra hyperparameter s/t, and it seems that the algorithm is sensitive to the choice of the hyperparameter. Though it can be chosen by holdout labeled validation set, labeled data are relatively rare in the SSL setting. Is it possible to estimate the value of the hyperparameters?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank you for appreciating the importance of the problem that we study as well as the significance of the insights that follow from our theoretical analysis. We are also grateful for bringing up the important observation that in the SSL setting, model selection based on only the unlabeled data is much more desirable than using a labeled validation set. As we argue in the “General comments” above, we find that selecting hyperparameters using a margin-based criterion computed on unlabeled validation data leads to similar results as the ones currently presented in the manuscript. We provide as evidence for this claim some key experimental results that we include in the attached PDF file. We will update all experiments to use the unsupervised model selection metric and stress that this does not affect in any way the takeaways of our experimental analysis.\n\nWe are thankful for your time and effort in reviewing our paper. In case you have any further questions regarding this manuscript, we will be happy to answer them promptly."}, {"review_id": "D4ZTExwmyV", "reviewer": "Reviewer_4XfH", "summary": "The paper presents a detailed analysis of semi-supervised learning (SSL) algorithms. Specifically, the authors establish lower bounds for 2-Gaussian mixture model distributions, revealing that no SSL algorithm can improve the sample complexities of optimal supervised or unsupervised learning. However, SSL can improve their error rates by a constant factor. The authors propose an algorithm that achieves lower error than both supervised and unsupervised learning, and conduct experiments on synthetic and real-world data.", "questions": "- The paper only considers Gaussian mixture distributions. Could more complex distributions be considered in future work to accommodate more real-world problems?\n\n- The paper only considers the worst-case scenario. Is it possible to consider milder cases? For instance, could a data-dependent bound that relates to problem difficulty be derived?\n\n- The statement on line 103 seems to be erroneous: when using the UL algorithm, why can't labeled data be considered as unlabeled data, so that UL can use $n_l + n_u$?\n", "limitations": "- As mentioned in the Questions section, the authors should provide further clarification on the method and theory parts.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper investigates the learning capacity of SSL algorithms and theoretically establishes a lower bound, which is an inherently interesting and meaningful endeavor.\n\n- The paper is well-organized and easy to comprehend. The authors provide a clear overview of the problem and their proposed solution.", "weaknesses": "- Some details about the method and theory part should be further elaborated on, see Questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank you for appreciating the clarity of our manuscript and the importance of the contribution presented in it. In the “General comments” we address your question regarding possible extensions of our results to more general distributions, beyond GMMs. In what follows, we answer the remaining points in the review.\n\n> The paper only considers the worst-case scenario. Is it possible to consider milder cases? For instance, could a data-dependent bound that relates to problem difficulty be derived?\n\nWe would like to point out that one of the novel characteristics of the lower bound that we derive is that it adapts to the problem difficulty, which in the setting considered in the paper is quantified by the signal-to-noise ratio $s$. This is in contrast to existing lower bounds for SSL [6, 18, 32] that only focuses on the worst-case scenario in which SSL achieves the same sample complexity as SL. We hope that our answer addresses the point that you have raised. If you have further questions regarding this aspect, we would like to kindly ask you to let us know, and we would be happy to provide further clarifications.\n\n\n> The statement on line 103 seems to be erroneous: when using the UL algorithm, why can't labeled data be considered as unlabeled data, so that UL can use n_l+n_u?\n\nThank you for raising this point! This paragraph should indeed be revised. \n\nFirst of all, it is indeed true that UL+ can use the labeled data without the labels in the first stage, when it performs unsupervised learning. However, typically, in empirical papers, UL+ style algorithms (e.g. SimCLR, SwAV etc) do not use the labeled data in this way since $n_u =\\omega(n_l)$, and hence, it would not make a significant difference. This fact is also reflected in our rate comparisons: even if we allow UL+ to use the samples in $\\mathcal{D}_l$ as unlabeled data, only the last line of Table 1 would change by a small constant in the regime when $n_u / u(n_l) = \\Theta(n_l)$. More importantly, the main takeaway from Table 1 would not change: SSL cannot be both better than UL+ and SL at the same time since there is no regime for which $h_l$ and $h_u$ are simultaneously $0$. For the above reasons and in order to reduce notational overhead, we chose the slightly simpler definition of UL+ as algorithms that do not use the labeled set as unlabeled data. However, we acknowledge that you raise a very natural question, and, if it helps to avoid confusion, we would be happy to revise the definition of UL+ to also use the labeled data without the labels.\n\nSecondly, the paragraph you have referenced (lines 103-110) is intended to show how UL+ algorithms are not making the best use of the available data. This shortcoming is not immediately obvious in some of the practical settings where UL+ style algorithms were applied in prior work, i.e. where unlabeled data is many orders of magnitude more numerous than labeled data. However, the “wasteful” aspect of UL+ algorithms becomes clear when $n_u$ is, for instance, only larger than $n_l$ by a constant factor. The issue is caused by the two-stage nature of UL+, which selects and commits to a small set of estimators using the unlabeled set, before choosing among them using labeled data.\n\nFinally, in this paragraph (lines 103-110), we consider an exaggerated scenario in order to illustrate this failure of UL+. This is, of course, not a scenario likely to occur in practical applications, where $n_u$ is usually not smaller than $n_l$. We do acknowledge, however, that the current phrasing can lead to confusion, and will change it in the final version of the manuscript to better reflect our intention.\n\nWe again appreciate your time and effort in critically reviewing our paper. We will be happy to promptly answer any further questions you may have about our manuscript.\n\n"}, {"review_id": "GN4ICfR8iW", "reviewer": "Reviewer_9F3v", "summary": "this paper investigates whether improvements in the rates of sample complexities are possible for semi-supervised learning compared with supervised learning and unsupervised learning (up to a change in sign) for the specific case of a classification problem where each class is a symmetrical Gaussian. it is found that no improvement in the rate can be made, but it is possible to improve the constants.", "questions": "5 for Algorithm 3, how does it make sense that $t$ is an input? should this not be learned also? similarly, I see the same problem with Theorem 6. This would imply the algorithm has knowledge of the distribution? Or is there a universal (distribution independent) t?\n\n6 Similarly, in the experiments, these parameters seem to be tuned on a holdout labeled set. Why is that appropiate? \n\n", "limitations": "none", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1 I think it is a very relevant question to investigate whether SSL can improve performance in theory over sup and unsup, and this can have a great impact\n\n2 I like the deep theoretical analysis where minimax upper and lower bounds are derived \n\n3 the theory is complemented by some experiments to validate the theoretical findings", "weaknesses": "4 the work misses a very relevant recent survey concerning this question in general:\nMey, A., & Loog, M. (2019). Improvability through semi-supervised learning: A survey of theoretical results. arXiv preprint arXiv:1908.09574.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for appreciating the importance of the problem as well as the thorough theoretical and experimental analyses in our paper. We are grateful for the feedback that you have provided and hope that our answers address the points raised in your review.\n\n> 5 for Algorithm 3, how does it make sense that $t$ is an input? should this not be learned also? similarly, I see the same problem with Theorem 6. This would imply the algorithm has knowledge of the distribution? Or is there a universal (distribution independent) t?\n\nThe reviewer is correct in noting that the algorithm takes $t$ as a hyperparameter And that different $t$ leads to different estimators. The $t^\\star$ that achieves a smaller risk than the switching algorithm via Theorem 6 indeed depends on $s$ (for both algorithms that we are comparing), which is a distributional parameter that describes the hardness of the problem. Theorem 6 belongs to a standard type of result that shows the existence of a hyper-parameter for which the estimator achieves certain favorable properties [Wei et al; Li et al, Meinshausen et al; van de Geer]. In practice, it is very common to use standard data-dependent model selection tools that also can achieve good performance. We show this empirically  and leave an analysis of the impact of model selection with held-out data as an exciting direction for future work. We refer the reviewer to the “General comments” for a more detailed discussion on this topic. For Theorem 6 specifically, we would like to furthermore emphasize that both SSL-S and SSL-W with optimal $t^\\star$ require the knowledge of $s$.  \n\n\n\n\n> the work misses a very relevant recent survey concerning this question in general\n\nThank you for bringing this to our attention! As a survey paper that is aimed at the same question as us, it does indeed discuss a lot of prior work that our paper is based on. We will include this reference in our related work section in the revised version. \n\nReferences:\n\n[Wei et al] – Y. Wei, F. Yang, M. Wainwright. Early stopping for kernel boosting algorithms: A general analysis\nwith localized complexities, 2017.\n\n[Li et al] – M. Li, M. Soltanolkotabi, S. Oymak. Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks, 2020.\n\n[Meinshausen et al] – N. Meinshausen, P. Buhlmann. High-dimensional graphs and variable selection with the Lasso, 2006.\n\n[van de Geer] – S. van de Geer. On tight bounds for the Lasso, 2018.\n\n"}]

Author rebuttal:
We extend our sincere thanks to the reviewers for their thorough review of our manuscript and for the constructive feedback provided. We are heartened by the acknowledgment of the importance of our research question: whether SSL algorithms can enhance performance over optimal SL and UL algorithms. It is particularly encouraging that all reviewers considered our theoretical analyses to be "inherently interesting" and that it "goes beyond prior work". Furthermore, we are gratified that our experimental analysis, which "validates our theory", was deemed “insightful” by the reviewers.

We deeply appreciate the feedback and recognize its helpful role in improving our manuscript. In the ensuing comments, we address the prominent concerns raised in the reviews. Specific feedback from the reviewers will be attended to in our individual responses.

**Theoretical analysis focuses solely on GMM distributions.**

We agree that it would be interesting to obtain theoretical results that go beyond GMM distributions in future work. Nevertheless, we would like to emphasize the following:

 Analyzing the lower bound for GMM distributions is insightful in its own right:

Not only is it common to model various real-world distributions as a mixture of Gaussians [Bouguila et al], but this choice also allows our analysis to yield precise upper and lower bounds that depend on the hardness of the problem. In particular, this is reflected by the dependence on the signal-to-noise ratio $s$ in our results. 

Previous works on SSL with concrete upper bounds have also focused on 2-GMMs (or slight generalizations thereof) for likely similar reasons (e.g. [16]). Moreover, giving lower or upper bounds for this commonly analyzed setting has the added benefit that it allows for comparisons with prior works. 

Going beyond GMM distributions requires fundamental advances in the analysis of UL algorithms, which we consider to be beyond the scope of this paper. For instance, it is only recently that the (tight) lower and upper bounds for UL on isotropic 2-GMMs have been proven [12, 13, 22, 35], and precise rates for more general distributions are even more difficult to come by.

Having said that, we agree with reviewers that analysis of more general distributions would be interesting and leave that to future work. 

**Algorithms 1, and 2 take in the switching point/weighting coefficient as parameters.**

The primary goal of this paper is to prove a “hardness”-dependent minimax lower bound and show that it is tight. For the purpose of the latter, we prove a simple upper bound for the SSL-S algorithm (with oracle knowledge of $s$). As a second contribution, we prove that there exist algorithms that can improve over the error of SSL-S by a constant factor and give one example (SSL-W with a particular choice of $t$) – papers of such flavor are common, e.g. the theoretical analyses of early stopping [Wei et al; Li et al], or Lasso [Meinshausen et al; van de Geer].

Even though our optimality guarantees for the algorithms hold for specific hyperparameters $s$ and $t$ that are derived from theory and unknown to the method, in practice, we can estimate them using held-out data, which is what we show empirically in our experiments (see also the next section of the “General comments” about labeled vs. unlabeled validation data).

We agree that it would be desirable to prove guarantees for data-dependent hyperparameter search with an appropriate model selection procedure. We believe this is one of the many exciting directions for future work that could follow from our paper.

**In experiments, the switching point and weighting coefficient are selected using labeled data, which is scarce in SSL settings.**

We thank the reviewers for bringing up this point which is indeed important for applying the algorithms in practice. We have now run additional experiments using unsupervised validation data for model selection and observe the same trends as when using a labeled validation set. We use a margin-based metric for hyperparameter selection i.e. we choose the hyperparameters that lead to the model with the largest (average) margin on the unlabeled validation set. We attach the revised version of Figures 3a and 3b in the PDF file and will change all experiments to use an unlabeled validation set. Notably, the new figures preserve the important trends that we discuss in Section 4.2, namely: 1) SSL-W is always better than SL and UL+; and 2) the gap between SSL-W and SL decreases with the SNR, and the gap between SSL and UL+ increases with the SNR.

References:

[Bouguila et al] – N. Bouguila and W. Fan. Mixture Models and Applications, 2019.

[Wei et al] – Y. Wei, F. Yang, M. Wainwright. Early stopping for kernel boosting algorithms: A general analysis
with localized complexities, 2017.

[Li et al] – M. Li, M. Soltanolkotabi, S. Oymak. Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks, 2020.

[Meinshausen et al] – N. Meinshausen, P. Buhlmann. High-dimensional graphs and variable selection with the Lasso, 2006.

[van de Geer] – S. van de Geer. On tight bounds for the Lasso, 2018.


Meta-review: Unanimous accept from reviewers, congrats to the authors for an excellent paper.
Decision: Accept (spotlight)