Can semi-supervised learning use all the data effectively? A lower bound perspective

• URL: http://arxiv.org/abs/2311.18557v1
• Date: Thu, 30 Nov 2023 13:48:50 GMT
• Title: Can semi-supervised learning use all the data effectively? A lower bound perspective
• Authors: Alexandru \c{T}ifrea, Gizem Y\"uce, Amartya Sanyal, Fanny Yang
• Abstract summary: We show that semi-supervised learning algorithms can leverage unlabeled data to improve over the labeled sample complexity of supervised learning algorithms. Our work suggests that, while proving performance gains for SSL algorithms is possible, it requires careful tracking of constants.
• Score: 58.71657561857055
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Prior works have shown that semi-supervised learning algorithms can leverage unlabeled data to improve over the labeled sample complexity of supervised learning (SL) algorithms. However, existing theoretical analyses focus 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 can improve upon the minimax-optimal statistical error rates of SL or UL algorithms for these distributions. Nevertheless, we show empirically on real-world data that SSL algorithms can still outperform UL and SL methods. Therefore, our work suggests that, while proving performance gains for SSL algorithms is possible, it requires careful tracking of constants.

Related papers

• Active Semi-Supervised Learning by Exploring Per-Sample Uncertainty and Consistency [30.94964727745347]
  We propose a method called Active Semi-supervised Learning (ASSL) to improve accuracy of models at a lower cost. ASSL involves more dynamic model updates than Active Learning (AL) due to the use of unlabeled data. ASSL achieved about 5.3 times higher computational efficiency than Semi-supervised Learning (SSL) while achieving the same performance.
  arXiv  Detail & Related papers  (2023-03-15T22:58:23Z)
• MaxMatch: Semi-Supervised Learning with Worst-Case Consistency [149.03760479533855]
  We propose a worst-case consistency regularization technique for semi-supervised learning (SSL) We present a generalization bound for SSL consisting of the empirical loss terms observed on labeled and unlabeled training data separately. Motivated by this bound, we derive an SSL objective that minimizes the largest inconsistency between an original unlabeled sample and its multiple augmented variants.
  arXiv  Detail & Related papers  (2022-09-26T12:04:49Z)
• OpenLDN: Learning to Discover Novel Classes for Open-World Semi-Supervised Learning [110.40285771431687]
  Semi-supervised learning (SSL) is one of the dominant approaches to address the annotation bottleneck of supervised learning. Recent SSL methods can effectively leverage a large repository of unlabeled data to improve performance while relying on a small set of labeled data. This work introduces OpenLDN that utilizes a pairwise similarity loss to discover novel classes.
  arXiv  Detail & Related papers  (2022-07-05T18:51:05Z)
• Collaborative Intelligence Orchestration: Inconsistency-Based Fusion of Semi-Supervised Learning and Active Learning [60.26659373318915]
  Active learning (AL) and semi-supervised learning (SSL) are two effective, but often isolated, means to alleviate the data-hungry problem. We propose an innovative Inconsistency-based virtual aDvErial algorithm to further investigate SSL-AL's potential superiority. Two real-world case studies visualize the practical industrial value of applying and deploying the proposed data sampling algorithm.
  arXiv  Detail & Related papers  (2022-06-07T13:28:43Z)
• Unlabeled Data Help: Minimax Analysis and Adversarial Robustness [21.79888306754263]
  Self-supervised learning (SSL) approaches successfully demonstrate the great potential of supplementing learning algorithms with additional unlabeled data. It is still unclear whether the existing SSL algorithms can fully utilize the information of both labelled and unlabeled data. This paper gives an affirmative answer for the reconstruction-based SSL algorithm citeplee 2020predicting under several statistical models.
  arXiv  Detail & Related papers  (2022-02-14T19:24:43Z)
• Self-supervised Learning is More Robust to Dataset Imbalance [65.84339596595383]
  We investigate self-supervised learning under dataset imbalance. Off-the-shelf self-supervised representations are already more robust to class imbalance than supervised representations. We devise a re-weighted regularization technique that consistently improves the SSL representation quality on imbalanced datasets.
  arXiv  Detail & Related papers  (2021-10-11T06:29:56Z)
• RETRIEVE: Coreset Selection for Efficient and Robust Semi-Supervised Learning [9.155410614399159]
  We propose RETRIEVE, a coreset selection framework for efficient and robust semi-supervised learning. We show that RETRIEVE achieves a speedup of around 3X in the traditional SSL setting and achieves a speedup of 5X compared to state-of-the-art (SOTA) robust SSL algorithms.
  arXiv  Detail & Related papers  (2021-06-14T21:18:47Z)
• Semi-supervised learning objectives as log-likelihoods in a generative model of data curation [32.45282187405337]
  We formulate SSL objectives as a log-likelihood in a generative model of data curation. We give a proof-of-principle for Bayesian SSL on toy data.
  arXiv  Detail & Related papers  (2020-08-13T13:50:27Z)
• Distribution Aligning Refinery of Pseudo-label for Imbalanced Semi-supervised Learning [126.31716228319902]
  We develop Distribution Aligning Refinery of Pseudo-label (DARP) algorithm. We show that DARP is provably and efficiently compatible with state-of-the-art SSL schemes.
  arXiv  Detail & Related papers  (2020-07-17T09:16:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.