On Separability of Loss Functions, and Revisiting Discriminative Vs Generative Models
We revisit the classical analysis of generative vs discriminative models for general exponential families, and high-dimensional settings. Towards this, we develop novel technical machinery, including a notion of separability of general loss functions, which allow us to provide a general framework to obtain`1 convergence rates for general M -estimators. We use this machinery to analyze`1 and`2 convergence rates of generative and discriminative models, and provide insights into their nuanced behaviors in high-dimensions. Our results are also applicable to differential parameter estimation, where the quantity of interest is the difference between generative model parameters.
The paper compares generative and discriminative models for general exponential families, also in the high-dimensional setting. It develops a notion of separability of general loss functions, and provides a framework for obtaining l_{infty} convergence rates for M-estimators. This machinery is used to analyze convergence rates (both in l_{infty} and l_2) of generative and discriminative models.
I found the paper quite hard to follow, but this might potentially be also due to my lack of expertise in high dimensional estimation. While the introduction, as well as background and setup (Section 2) are accessible and quite easy to follow, in the following sections the paper becomes quite dense with equations and technical results, sometimes given without much guidance to the reader. Sometimes authors' comments made me quite confused; for instance, in lines 215-218, Corollary 4 and 3 are compared (for discriminative and generative models) and it is stated that "both the discriminative and generative approach achieve the same convergence rate, but the generative approach does so with only a logarithmic dependence on the dimension", whereas from what I can see, the dependence on the dimension in both Corollary 3 and 4 is the same (sqrt(log p))?
The core idea in the paper is the notion of separability of the loss. The motivating example in the introduction is that in the generative model with conditional independence assumption, the corresponding log-likelihood loss is fully separable into multiple components, each of which can be estimated separately. In case of the corresponding discriminative model (e.g. logistic regression), the loss is much less separable. This motivates the need to introduce a more flexible notion of separability in Section 3. It turns out that more separable losses require fewer samples to converge.
Unfortunately, I am unable see this motivation behind the definition of separability (Definition 1 and 2), which states that the error in the first order approximation of the gradient is upper bounded by the error in the parameters. I think it would improve the readability of the paper if the authors could motivate why is this particular definition used here and how is it related to the intuitive notion of separability of the loss into multiple components.
Starting from Corollary 3, the authors use notation "\succsim" without explanation. What does it mean?
It is hard for me to judge the significance of the paper, as I not familiar with previous work in this setup (apart from the work by Ng & Jordan), but I found the results quite interesting, if they were only presented more clearly. Nevertheless, I evaluate the theoretical contribution to be quite strong. What I found missing is a clear message about when to use generative vs. discriminative methods in high dimension (similar to the message given by Ng & Jordan in their paper). 
Small remarks:
36: "could be shown to separable" -> "could be shown to be separable"
65: n -> in
87: : and j should be in the subscript
259: bayes -> Bayes
254-265: the "Notation and Assumptions" paragraph -- the Bayes classifier is defined only after its error was already mentioned.