Semi-Supervised Sparse Gaussian Classification: Provable Benefits of Unlabeled Data
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.
Code (0)
등록된 구현이 없습니다.
Tasks
feature selectionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Semi-unsupervised Learning of Human Activity using Deep Generative Models
We introduce 'semi-unsupervised learning', a problem regime related to transfer learning and zero-shot learning where, in the training data, some classes are sparsely labelled and others entirely unlabelled. Models able …
ClassificationGeneral ClassificationTime SeriesTime Series Analysis+2Outlier-Robust Tensor PCA
Low-rank tensor analysis is important for various real applications in computer vision. However, existing methods focus on recovering a low-rank tensor contaminated by Gaussian or gross sparse noise and hence cannot effe…
ClusteringOutlier DetectionSemi-unsupervised Learning for Time Series Classification
Time series are ubiquitous and therefore inherently hard to analyze and ultimately to label or cluster. With the rise of the Internet of Things (IoT) and its smart devices, data is collected in large amounts any given se…
ClassificationTime SeriesTime Series AnalysisTime Series ClassificationSemi-supervised dictionary learning with graph regularization and active points
Supervised Dictionary Learning has gained much interest in the recent decade and has shown significant performance improvements in image classification. However, in general, supervised learning needs a large number of la…
Dictionary LearningGeneral Classificationimage-classificationImage ClassificationDifferentially Private Regression and Classification with Sparse Gaussian Processes
A continuing challenge for machine learning is providing methods to perform computation on data while ensuring the data remains private. In this paper we build on the provable privacy guarantees of differential privacy w…
ClassificationGaussian ProcessesGeneral Classificationregression