A Non-generative Framework and Convex Relaxations for Unsupervised Learning
arXiv:1610.01132
Abstract
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.
NIPS 2016
Cited by in corpus (6)
- Provable benefits of representation learning
- Alternating minimization for dictionary learning: Local Convergence Guarantees
- Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games
- Functional Regularization for Representation Learning: A Unified Theoretical Perspective
- Analytic Manifold Learning: Unifying and Evaluating Representations for Continuous Control
- Distribution free optimality intervals for clustering