Does Unlabeled Data Provably Help? Worst-case Analysis of the Sample Complexity of Semi-Supervised Learning

By Shai Ben-David, Tyler Lu, Dávid Pál. 2008

154 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Semi-supervised learning, causality, and the conditional cluster assumption (2019, background): “For example, Ben-David, Lu, and Pál [3, Section 3] show that the cluster assumption, commonly used in SSL settings, can lead to degraded performance even in simple cases, e.g., for binary classiﬁcation with data generated from two unimodal Gaussians.”
Generalizing from a Few Examples (2019, methodology): “or reduce S. Based on how prior knowledge is used, we categorize these works into kinds: •Data: methods that use prior knowledge to augment Dtrain of I samples to I˜samples. In this way, S can be met [12, 107]. And one can obtain a more accurate empirical risk minimizerh I˜ as shown in Figure 2(a). ”
Semi-Supervised Novelty Detection (2010, background): “While a full study of the resulting procedure is out of the scope of the present paper, we want to point out the important difference that the mFDR is necessarily lower bounded by infx∈X PXY(Y = 0”
Semi-supervised interpolation in an anticausal learning scenario (2015, background): “Semi-supervised learning (SSL) has received increasing attention during the past decade (Darnstädt et al., 2013; Ben-David et al., 2008; Yuanyuan et al., 2010; Chapelle et al., 2006).”
Federated Multi-Task Learning under a Mixture of Distributions (2021, background): “(2)We note that whether the conjecture in [4] holds in the agnostic case is still an open problem.”
Improvability Through Semi-Supervised Learning: A Survey of Theoretical Results (2019, background): “The motivation, however, was independent of Ben-David et al. (2008) and was meant as a general theoretical analysis of the manifold learning framework as introduced in Belkin et al. (2006). Also, their results are in-expectation, while the previous papers give PAC bounds, which means that they hold ”
Unlabeled data: Now it helps, now it doesn't (2008, background): “As a result, ther e have been several recent attempts [1, 2, 3, 4, 5, 6] at developing a theoretical understanding o f semi-supervised learning.”
Understanding Self-Training for Gradual Domain Adaptation (2020, background): “Other theory in semi-supervised learning (Rigollet, 2007; Singh et al., 2008; Ben-David et al., 2008) does not analyze domain shift.”
Towards Making Unlabeled Data Never Hurt (2011, background): “There are also some general discussions on the usefulness of unlabeled data from a theoretical perspective [1], [3], [38].”
Self-Training: A Survey (2022, unknown): “In this line, [Ben-David et al., 2008] showed that the access to the marginal distribution over unlabeled training data would not provide sample size guarantees superior to those obtained through supervised learning unless very strong assumptions about the conditional distribution over the class lab”
The Pessimistic Limits and Possibilities of Margin-based Losses in Semi-supervised Learning (2016, background): “The (negative) result presented here is in line with the conclusions of Ben-David et al. (2008), who show that the worst-case sample complexity of a supervised learner is at most a constant factor higher than that of any semi-supervised approach for a classifier over the real line, and they conjectu”
Contrastive Pessimistic Likelihood Estimation for Semi-Supervised Classification (2015, background): “In this work, we demonstrate when and how ML estimators for classiﬁcation can be improved in the semi-supervised setting.”
Dash: Semi-Supervised Learning with Dynamic Thresholding (2021, background): “…data in SSL can help to improve the learning performance [Berthelot et al., 2019b,a, Sohn et al., 2020], however, a series of theoretical studies [Ben-David et al., 2008, Singh et al., 2009, Li and Zhou, 2011b, Balcan and Blum, 2005] have demonstrated that this success is highly relying on a…”
Access to Unlabeled Data can Speed up Prediction Time (2011, background): “However, the work of Ben-David et al. (2008), provides rigorous results indicating that, under worst-case scenarios, the utility of unlabeled data in that setup is very limited.”