Unsupervised Risk Estimation Using Only Conditional Independence Structure
We show how to estimate a model's test error from unlabeled data, on distributions very different from the training distribution, while assuming only that certain conditional independencies are preserved between train and test. We do not need to assume that the optimal predictor is the same between train and test, or that the true distribution lies in any parametric family. We can also efficiently compute gradients of the estimated error and hence perform unsupervised discriminative learning. Our technical tool is the method of moments, which allows us to exploit conditional independencies in the absence of a fully-specified model. Our framework encompasses a large family of losses including the log and exponential loss, and extends to structured output settings such as conditional random fields.
The paper proposes a means to estimate the risk of a model on unlabeled data, and to optimise a model on the same. The approach relies on making a structural assumption of the underlying generating distribution, namely that it decomposes into label independent views. Preliminary experimental results show promise for the method.       
  I found the paper very well presented and enjoyable to read. The basic problem is interesting, and the approach presented as some salient features, notably the fact that one does not have to make parametric assumption on the underlying distribution. The high-level idea of imposing structural assumptions but nonetheless relying on discriminative models was quite elegant.   The basic insight in estimating the risk from unlabelled data is that by encoding a certain structural assumption - namely, that the data comprises three independent views - one implicitly gets information about the class-conditional risks by considering the first three moments of the label vectors. This leads to a system of equations which may be solved to infer the class-conditional risks. One applies a similar trick in order to estimate the gradient of the risk from unlabelled data, allowing one to optimise models such as logistic regression without labels. The fact that one is able to do so under somewhat mild assumptions is quite surprising.   The mechanics of the proposed approach, as well as the overall inspiration for considering higher-order moments, derive from the tensor decomposition framework for latent variable models, e.g. Anandkumar et al. 2012, a literature that I am not familiar with. I am thus unable to confidently proclaim the novelty of the presented approach. However, from some preliminary reading, it does not appear as though existing work in the literature has use such methods for unsupervised risk estimation. It seems a nice conceptual insight that one can use the three view assumption to aid in estimating classification error.   The technical content is fairly clearly presented in the main body, with some high-level intuition for the proofs of the main theorems. The proofs of Theorem 1 and 2 to rely on Theorem 7 of Anandkumar et al. 2012, but I wasn't quite able to discern how much of the heavy lifting is accomplished by the latter. I also do not have much intuition on how good the precise form of the sample complexity is, in terms of dependence on various parameters, but the paper makes an attempt to explain why each of these is intuitively necessary.    I view the contribution of the paper as primarily theoretical, but appreciate that some preliminary experiments are presented. They indicate that the proposed method can be useful in covariate shift scenarios. The performance for semi-supervised learning is a little more erratic, but there are likely many practical extensions possible.   Overall, I found this an interesting, well-written paper that solves a non-trivial problem. Given that I am not an expert in the field, I cannot however specifically assess the novelty of the work.   Minor comments:   - the assumption that the last decomposes as a sum over the three views is intuitive. In the specific example of logistic regression, it was a little unclear why the feature maps for the three views have the same dimensionality. In general does one simply partition the ambient feature space three separate components for the view?    - I didn't quite follow the statement that assumption one doesn't hold for the hinge loss. Which specific version of multiclass hinge are you referring to?    - in equation 1 and elsewhere, maybe it would be good to make explicit that M depends on theta.    - for the extension to hidden Markov models, it might be worth adding a line explaining the difference to what is done in e.g. Anandkumar et al. 2012, which also considers estimating parameters for such models.    - the seed model in assumption 2 doesn't appear to be explicitly referred to beyond its definition in the body of the paper (i.e. it isn't said in the body what one actually does with it), which could be confusing.    - isn't the domain adaptation experiment more specifically one of covariate shift?    - it wasn't clear why the proposed model performed worse than the seed for small values of a in the domain adaptation experiments. Is this a finite sample effect?    - citation for Anandkumar et al. 2013 could be for the JMLR version.    - some citations in the main body only appear in the complete list of references in the supplementary. I suggest perhaps reducing spacing or font size for the references in the body to accommodate everything.