Semi-Supervised Sparse Gaussian Classification: Provable Benefits of Unlabeled Data

• URL: http://arxiv.org/abs/2409.03335v1
• Date: Thu, 5 Sep 2024 08:21:05 GMT
• Title: Semi-Supervised Sparse Gaussian Classification: Provable Benefits of Unlabeled Data
• Authors: Eyar Azar, Boaz Nadler,
• Abstract summary: We study SSL for high dimensional Gaussian classification. We analyze information theoretic lower bounds for accurate feature selection. We present simulations that complement our theoretical analysis.
• Score: 6.812609988733991
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The premise of semi-supervised learning (SSL) is that combining labeled and unlabeled data yields significantly more accurate models. Despite empirical successes, the theoretical understanding of SSL is still far from complete. In this work, we study SSL for high dimensional sparse Gaussian classification. To construct an accurate classifier a key task is feature selection, detecting the few variables that separate the two classes. % For this SSL setting, we analyze information theoretic lower bounds for accurate feature selection as well as computational lower bounds, assuming the low-degree likelihood hardness conjecture. % Our key contribution is the identification of a regime in the problem parameters (dimension, sparsity, number of labeled and unlabeled samples) where SSL is guaranteed to be advantageous for classification. Specifically, there is a regime where it is possible to construct in polynomial time an accurate SSL classifier. However, % any computationally efficient supervised or unsupervised learning schemes, that separately use only the labeled or unlabeled data would fail. Our work highlights the provable benefits of combining labeled and unlabeled data for {classification and} feature selection in high dimensions. We present simulations that complement our theoretical analysis.

Related papers

• OwMatch: Conditional Self-Labeling with Consistency for Open-World Semi-Supervised Learning [4.462726364160216]
  Semi-supervised learning (SSL) offers a robust framework for harnessing the potential of unannotated data. The emergence of open-world SSL (OwSSL) introduces a more practical challenge, wherein unlabeled data may encompass samples from unseen classes. We propose an effective framework called OwMatch, combining conditional self-labeling and open-world hierarchical thresholding.
  arXiv  Detail & Related papers  (2024-11-04T06:07:43Z)
• Generalized Semi-Supervised Learning via Self-Supervised Feature Adaptation [87.17768598044427]
  Traditional semi-supervised learning assumes that the feature distributions of labeled and unlabeled data are consistent. We propose Self-Supervised Feature Adaptation (SSFA), a generic framework for improving SSL performance when labeled and unlabeled data come from different distributions. Our proposed SSFA is applicable to various pseudo-label-based SSL learners and significantly improves performance in labeled, unlabeled, and even unseen distributions.
  arXiv  Detail & Related papers  (2024-05-31T03:13:45Z)
• Semi-Supervised Learning in the Few-Shot Zero-Shot Scenario [14.916971861796384]
  Semi-Supervised Learning (SSL) is a framework that utilizes both labeled and unlabeled data to enhance model performance. We propose a general approach to augment existing SSL methods, enabling them to handle situations where certain classes are missing. Our experimental results reveal significant improvements in accuracy when compared to state-of-the-art SSL, open-set SSL, and open-world SSL methods.
  arXiv  Detail & Related papers  (2023-08-27T14:25:07Z)
• 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)
• Deep Low-Density Separation for Semi-Supervised Classification [0.0]
  We introduce a novel hybrid method that applies low-density separation to the embedded features. Our approach effectively classifies thousands of unlabeled users from a relatively small number of hand-classified examples.
  arXiv  Detail & Related papers  (2022-05-22T11:00:55Z)
• Robust Deep Semi-Supervised Learning: A Brief Introduction [63.09703308309176]
  Semi-supervised learning (SSL) aims to improve learning performance by leveraging unlabeled data when labels are insufficient. SSL with deep models has proven to be successful on standard benchmark tasks. However, they are still vulnerable to various robustness threats in real-world applications.
  arXiv  Detail & Related papers  (2022-02-12T04:16:41Z)
• 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)
• Dash: Semi-Supervised Learning with Dynamic Thresholding [72.74339790209531]
  We propose a semi-supervised learning (SSL) approach that uses unlabeled examples to train models. Our proposed approach, Dash, enjoys its adaptivity in terms of unlabeled data selection.
  arXiv  Detail & Related papers  (2021-09-01T23:52:29Z)
• Rethinking Re-Sampling in Imbalanced Semi-Supervised Learning [26.069534478556527]
  Semi-Supervised Learning (SSL) has shown its strong ability in utilizing unlabeled data when labeled data is scarce. Most SSL algorithms work under the assumption that the class distributions are balanced in both training and test sets. In this work, we consider the problem of SSL on class-imbalanced data, which better reflects real-world situations.
  arXiv  Detail & Related papers  (2021-06-01T03:58:18Z)
• Matching Distributions via Optimal Transport for Semi-Supervised Learning [31.533832244923843]
  Semi-Supervised Learning (SSL) approaches have been an influential framework for the usage of unlabeled data. We propose a new approach that adopts an Optimal Transport (OT) technique serving as a metric of similarity between discrete empirical probability measures. We have evaluated our proposed method with state-of-the-art SSL algorithms on standard datasets to demonstrate the superiority and effectiveness of our SSL algorithm.
  arXiv  Detail & Related papers  (2020-12-04T11:15:14Z)
• 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.