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.

本研究提出了一种新颖的理论框架，用于无监督学习，具有不需要任何生成模型和基于最坏情况性能指标的特点。特别地，本研究测量性能是相对于给定的假设类进行的比较，这有助于避免已知的计算难度结果和基于凸松弛的不当算法。我们展示了如何通过凸优化在我们的框架下有效地学习多个无监督学习模型家族，这些模型家族以前仅在概率假设下进行分析，并且在其他情况下是可以证明棘手的。