# A Non-generative Framework and Convex Relaxations for Unsupervised Learning

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Oct 2016.

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

- [Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games](https://mlsanity.com/paper/2102.01646/) (2021)
- [Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games](https://mlsanity.com/paper/2111.08911/) (2021)
- [Adversarially Robust PAC Learnability of Real-Valued Functions](https://mlsanity.com/paper/2206.12977/) (2022)
- [On the Generalization Ability of Unsupervised Pretraining](https://mlsanity.com/paper/2403.06871/) (2024)
- [Distribution free optimality intervals for clustering](https://mlsanity.com/paper/2107.14442/) (2021)

## Abstract (arXiv)

We give a novel formal theoretical framework for unsupervised learning with two distinctive characteristics. First, it does not assume any generative model and based on a worst-case performance metric. Second, it is comparative, namely performance is measured with respect to a given hypothesis class. This allows to avoid known computational hardness results and improper algorithms based on convex relaxations. We show how several families of unsupervised learning models, which were previously only analyzed under probabilistic assumptions and are otherwise provably intractable, can be efficiently learned in our framework by convex optimization.