Research map / Label-efficient and robust learning / Semi-supervised learning
Semi-Supervised Sparse Gaussian Classification: Provable Benefits of Unlabeled Data
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies semi-supervised sparse Gaussian two-class classification, deriving information-theoretic and low-degree computational lower bounds and proposing a polynomial-time label-screening PCA method (LSPCA) that succeeds where supervised or unsupervised methods alone fail.
Problem
When can combining few labeled and many unlabeled samples provably help classification and feature selection in high-dimensional sparse Gaussian mixtures, and is there a computational gap in the semi-supervised setting?
Approach
Views SSL as data fusion of two measurement modalities to get information lower bounds, extends the low-degree likelihood framework to a semi-supervised testing problem, and gives a simple screen-then-PCA algorithm (LSPCA) whose labeled screening step makes unlabeled PCA feasible in a regime where neither data source alone suffices.
Key results
- Simulations with p=10^5, k=100, λ=3, L=200 labeled and n unlabeled samples show LSPCA/LS²PCA approach Bayes error (≈0.042) while SL and UL methods have much higher errors.
- Theory: in the blue region (β>1-γα, 1<γ<2) LSPCA recovers the support with overlap→1 and classifier excess risk→0 in polynomial time.
- Low-degree analysis shows SSL detection is hard when β<1/2-α and γ<2, extending UL computational gaps to the semi-supervised setting.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| combine labeled screening with unlabeled PCA | Sparse Gaussian classification in the blue region · Sparse Gaussian classification, blue region | classification accuracy | Helped |
| combine labeled screening with unlabeled PCA | Sparse Gaussian classification in the blue region · Sparse Gaussian classification, blue region | normalized support overlap | Helped |
| add unlabeled samples to labeled training | LSPCA and LS²PCA · Sparse Gaussian classification, fixed n=1000 | classification error | Helped |
| replace PCA with sparse PCA (IPU) after labeled screening (ablation) | LSPCA, yielding LS²PCA · Sparse Gaussian classification simulations | support recovery accuracy | Helped |
| replace PCA with sparse PCA (IPU) after labeled screening (ablation) | LSPCA, yielding LS²PCA · Sparse Gaussian classification simulations | classification error | Helped |
| use labeled and unlabeled data jointly rather than either data source separately | Sparse Gaussian classification in the blue region · Sparse Gaussian classification, blue region | required labeled sample count: (1-alpha)/(1-gamma alpha) | Helped |
Limitations
- Analysis restricted to a two-component mixture of spherical Gaussians with symmetric means.
- White region left as conjecture; computational lower bounds rely on the low-degree conjecture.
Experimental setup
Datasets: synthetic sparse Gaussian mixture data
Metrics: normalized support overlap |S-hat ∩ S|/k classification error excess risk
Baselines: ASPCA IPU LSDF self-training Top-K Labeled
Builds on: low-degree likelihood ratio framework sure independence screening iterative proxy update sparse PCA
Closest papers by meaning
- Out-Of-Domain Unlabeled Data Improves Generalization (ICLR 2024 · similarity 0.88)
- InterLUDE: Interactions between Labeled and Unlabeled Data to Enhance Semi-Supervised Learning (ICML 2024 · similarity 0.87)
- Scaling Up Semi-supervised Learning with Unconstrained Unlabelled Data (AAAI 2024 · similarity 0.86)
- Re-Evaluating the Impact of Unseen-Class Unlabeled Data on Semi-Supervised Learning Model (ICLR 2025 · similarity 0.86)
- Continuous Contrastive Learning for Long-Tailed Semi-Supervised Recognition (NeurIPS 2024 · similarity 0.86)
- CGMatch: A Different Perspective of Semi-supervised Learning (CVPR 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.