# Random Matrix Analysis to Balance between Supervised and Unsupervised Learning under the Low Density Separation Assumption

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 92 references that are in the map.
- First posted on arXiv 20 Oct 2023.

## Builds on (most cited first, 26 of 26)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [MixMatch: A Holistic Approach to Semi-Supervised Learning](https://mlsanity.com/paper/1905.02249/) (2019)
- [Image-based Recommendations on Styles and Substitutes](https://mlsanity.com/paper/1506.04757/) (2015)
- [Ups and Downs: Modeling the Visual Evolution of Fashion Trends with One-Class Collaborative Filtering](https://mlsanity.com/paper/1602.01585/) (2016)
- [High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representation](https://mlsanity.com/paper/2205.01445/) (2022)
- [Learning curves of generic features maps for realistic datasets with a teacher-student model](https://mlsanity.com/paper/2102.08127/) (2021)
- [Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime](https://mlsanity.com/paper/2105.15004/) (2021)
- [Double Trouble in Double Descent : Bias and Variance(s) in the Lazy Regime](https://mlsanity.com/paper/2003.01054/) (2020)
- [Graph-based Semi-supervised Learning: A Comprehensive Review](https://mlsanity.com/paper/2102.13303/) (2021)
- [Generalization error in high-dimensional perceptrons: Approaching Bayes error with convex optimization](https://mlsanity.com/paper/2006.06560/) (2020)
- [Poisson Learning: Graph Based Semi-Supervised Learning At Very Low Label Rates](https://mlsanity.com/paper/2006.11184/) (2020)
- [Random Matrix Theory Proves that Deep Learning Representations of GAN-data Behave as Gaussian Mixtures](https://mlsanity.com/paper/2001.08370/) (2020)
- [Theoretical Insights Into Multiclass Classification: A High-dimensional Asymptotic View](https://mlsanity.com/paper/2011.07729/) (2020)
- [Asymptotic Errors for Teacher-Student Convex Generalized Linear Models (or : How to Prove Kabashima's Replica Formula)](https://mlsanity.com/paper/2006.06581/) (2020)
- [Mutual Exclusivity Loss for Semi-Supervised Deep Learning](https://mlsanity.com/paper/1606.03141/) (2016)
- [How does unlabeled data improve generalization in self-training? A one-hidden-layer theoretical analysis](https://mlsanity.com/paper/2201.08514/) (2022)
- [Asymptotic Bayes risk for Gaussian mixture in a semi-supervised setting](https://mlsanity.com/paper/1907.03792/) (2019)
- [Partly Supervised Multitask Learning](https://mlsanity.com/paper/2005.02523/) (2020)
- [A random matrix analysis and improvement of semi-supervised learning for large dimensional data](https://mlsanity.com/paper/1711.03404/) (2017)
- [Consistent Semi-Supervised Graph Regularization for High Dimensional Data](https://mlsanity.com/paper/2006.07575/) (2020)
- [A Large Dimensional Analysis of Least Squares Support Vector Machines](https://mlsanity.com/paper/1701.02967/) (2017)
- [Random matrices in service of ML footprint: ternary random features with no performance loss](https://mlsanity.com/paper/2110.01899/) (2021)
- [PCA-based Multi Task Learning: a Random Matrix Approach](https://mlsanity.com/paper/2111.00924/) (2021)
- [A Concentration of Measure and Random Matrix Approach to Large Dimensional Robust Statistics](https://mlsanity.com/paper/2006.09728/) (2020)
- [Multi-class Probabilistic Bounds for Self-learning](https://mlsanity.com/paper/2109.14422/) (2021)
- [Weight Vector Tuning and Asymptotic Analysis of Binary Linear Classifiers](https://mlsanity.com/paper/2110.00567/) (2021)

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

- [MANO: Exploiting Matrix Norm for Unsupervised Accuracy Estimation Under Distribution Shifts](https://mlsanity.com/paper/2405.18979/) (2024)
- [Analysing Multi-Task Regression via Random Matrix Theory with Application to Time Series Forecasting](https://mlsanity.com/paper/2406.10327/) (2024)
- [Leveraging Ensemble Diversity for Robust Self-Training in the Presence of Sample Selection Bias](https://mlsanity.com/paper/2310.14814/) (2023)
- [Evaluating multiple models using labeled and unlabeled data](https://mlsanity.com/paper/2501.11866/) (2025)
- [A Random Matrix Theory Perspective on the Learning Dynamics of Multi-head Latent Attention](https://mlsanity.com/paper/2507.09394/) (2025)
- [CLID-MU: Cross-Layer Information Divergence Based Meta Update Strategy for Learning with Noisy Labels](https://mlsanity.com/paper/2507.11807/) (2025)

## Abstract (arXiv)

We propose a theoretical framework to analyze semi-supervised classification under the low density separation assumption in a high-dimensional regime. In particular, we introduce QLDS, a linear classification model, where the low density separation assumption is implemented via quadratic margin maximization. The algorithm has an explicit solution with rich theoretical properties, and we show that particular cases of our algorithm are the least-square support vector machine in the supervised case, the spectral clustering in the fully unsupervised regime, and a class of semi-supervised graph-based approaches. As such, QLDS establishes a smooth bridge between these supervised and unsupervised learning methods. Using recent advances in the random matrix theory, we formally derive a theoretical evaluation of the classification error in the asymptotic regime. As an application, we derive a hyperparameter selection policy that finds the best balance between the supervised and the unsupervised terms of our learning criterion. Finally, we provide extensive illustrations of our framework, as well as an experimental study on several benchmarks to demonstrate that QLDS, while being computationally more efficient, improves over cross-validation for hyperparameter selection, indicating a high promise of the usage of random matrix theory for semi-supervised model selection.