# Sharp-SSL: Selective high-dimensional axis-aligned random projections for semi-supervised learning

arXiv: https://arxiv.org/abs/2304.09154 · HTML: https://mlsanity.com/paper/2304.09154/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 96 references that are in the map.
- First posted on arXiv 18 Apr 2023.

## Builds on (most cited first, 30 of 34)

- [GANomaly: Semi-Supervised Anomaly Detection via Adversarial Training](https://mlsanity.com/paper/1805.06725/) (2018)
- [Not-so-supervised: a survey of semi-supervised, multi-instance, and transfer learning in medical image analysis](https://mlsanity.com/paper/1804.06353/) (2018)
- [A Semi-supervised Graph Attentive Network for Financial Fraud Detection](https://mlsanity.com/paper/2003.01171/) (2020)
- [Statistical guarantees for the EM algorithm: From population to sample-based analysis](https://mlsanity.com/paper/1408.2156/) (2014)
- [Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants](https://mlsanity.com/paper/1612.02099/) (2016)
- [Optimality of Spectral Clustering in the Gaussian Mixture Model](https://mlsanity.com/paper/1911.00538/) (2019)
- [Ten Steps of EM Suffice for Mixtures of Two Gaussians](https://mlsanity.com/paper/1609.00368/) (2016)
- [Semi-supervised Inference: General Theory and Estimation of Means](https://mlsanity.com/paper/1606.07268/) (2016)
- [Singularity, Misspecification, and the Convergence Rate of EM](https://mlsanity.com/paper/1810.00828/) (2018)
- [Global analysis of Expectation Maximization for mixtures of two Gaussians](https://mlsanity.com/paper/1608.07630/) (2016)
- [Random-projection ensemble classification](https://mlsanity.com/paper/1504.04595/) (2015)
- [Efficient and Adaptive Linear Regression in Semi-Supervised Settings](https://mlsanity.com/paper/1701.04889/) (2017)
- [Clustering Algorithms: A Comparative Approach](https://mlsanity.com/paper/1612.08388/) (2016)
- [Randomly initialized EM algorithm for two-component Gaussian mixture achieves near optimality in O(√n) iterations](https://mlsanity.com/paper/1908.10935/) (2019)
- [Sharp Analysis of Expectation-Maximization for Weakly Identifiable Models](https://mlsanity.com/paper/1902.00194/) (2019)
- [Local nearest neighbour classification with applications to semi-supervised learning](https://mlsanity.com/paper/1704.00642/) (2017)
- [High-dimensional Linear Discriminant Analysis: Optimality, Adaptive Algorithm, and Missing Data](https://mlsanity.com/paper/1804.03018/) (2018)
- [Recent progress in log-concave density estimation](https://mlsanity.com/paper/1709.03154/) (2017)
- [Leave-one-out Singular Subspace Perturbation Analysis for Spectral Clustering](https://mlsanity.com/paper/2205.14855/) (2022)
- [Influential Feature PCA for high dimensional clustering](https://mlsanity.com/paper/1407.5241/) (2014)
- [Clustering a Mixture of Gaussians with Unknown Covariance](https://mlsanity.com/paper/2110.01602/) (2021)
- [Computationally efficient sparse clustering](https://mlsanity.com/paper/2005.10817/) (2020)
- [Instability, Computational Efficiency and Statistical Accuracy](https://mlsanity.com/paper/2005.11411/) (2020)
- [Statistical and Algorithmic Insights for Semi-supervised Learning with Self-training](https://mlsanity.com/paper/2006.11006/) (2020)
- [Minimax Theory for High-dimensional Gaussian Mixtures with Sparse Mean Separation](https://mlsanity.com/paper/1306.2035/) (2013)
- [Minimax rates in sparse, high-dimensional changepoint detection](https://mlsanity.com/paper/1907.10012/) (2019)
- [Random projections: data perturbation for classification problems](https://mlsanity.com/paper/1911.10800/) (2019)
- [Detection and Feature Selection in Sparse Mixture Models](https://mlsanity.com/paper/1405.1478/) (2014)
- [Efficient Sparse Clustering of High-Dimensional Non-spherical Gaussian Mixtures](https://mlsanity.com/paper/1406.2206/) (2014)
- [Statistical properties of sketching algorithms](https://mlsanity.com/paper/1706.03665/) (2017)

## Built on by (most cited first, 2 of 2)

- [High-dimensional Semi-supervised Classification via the Fermat Distance](https://mlsanity.com/paper/2604.23573/) (2026)
- [Random-projection ensemble dimension reduction](https://mlsanity.com/paper/2410.04922/) (2024)

## Abstract (arXiv)

We propose a new method for high-dimensional semi-supervised learning problems based on the careful aggregation of the results of a low-dimensional procedure applied to many axis-aligned random projections of the data. Our primary goal is to identify important variables for distinguishing between the classes; existing low-dimensional methods can then be applied for final class assignment. Motivated by a generalized Rayleigh quotient, we score projections according to the traces of the estimated whitened between-class covariance matrices on the projected data. This enables us to assign an importance weight to each variable for a given projection, and to select our signal variables by aggregating these weights over high-scoring projections. Our theory shows that the resulting Sharp-SSL algorithm is able to recover the signal coordinates with high probability when we aggregate over sufficiently many random projections and when the base procedure estimates the whitened between-class covariance matrix sufficiently well. The Gaussian EM algorithm is a natural choice as a base procedure, and we provide a new analysis of its performance in semi-supervised settings that controls the parameter estimation error in terms of the proportion of labeled data in the sample. Numerical results on both simulated data and a real colon tumor dataset support the excellent empirical performance of the method.