I've been learning a little bit about generalization theory, and in particular, the PAC (and PAC-Bayes) approach to thinking about this problem.
So, I started to wonder if there is an analogous version of "generalization" in Unsupervised Learning? I.e., is there a general framework that encapsulates how "good" an unsupervised learning method is? There's reconstruction error for learning lower dimensional representations, but what about unsupervised clustering?
Any ideas?
In the paper Generalization in Unsupervised Learning (2015), Abou-Moustafa and Schuurmans develop an approach to assess the generalization of an unsupervised learning algorithm $A$ on a given dataset $S$ and how to compare the generalization ability of two unsupervised learning algorithms $A_1$ and $A_2$, for the same learning task.
They first provide a more abstract and general definition of an unsupervised learning algorithm and loss function. Then they define the expected risk, empirical risk and generalization gap in a similar way to the case of supervised learning. Finally, they derive an upper bound on $A$'s expected loss.
Of course, you should read the paper for more details. Specifically, section 2 (page 3) describes their setting in detail.
