On Elicitation Complexity
Elicitation is the study of statistics or properties which are computable via empirical risk minimization. While several recent papers have approached the general question of which properties are elicitable, we suggest that this is the wrong question-all properties are elicitable by first eliciting the entire distribution or data set, and thus the important question is how elicitable. Specifically, what is the minimum number of regression parameters needed to compute the property? Building on previous work, we introduce a new notion of elicitation complexity and lay the foundations for a calculus of elicitation. We establish several general results and techniques for proving upper and lower bounds on elicitation complexity. These results provide tight bounds for eliciting the Bayes risk of any loss, a large class of properties which includes spectral risk measures and several new properties of interest.
=======POST REBUTTAL AND DISCUSSION COMMENTS: I seem to be in the minority in thinking the paper is too technical for the NIPS crowd. I am raising my score accordingly. =======This paper considers the problem of property elicitation. A property of a probability distribution is simply a (scalar) function of this distribution, and a property G is said to be elicitable if there exists a loss function such that the minimizer of the expected loss for a distribution P coincides with G(P). The authors observe that the ability to elicit a function of a distribution is something of a weak notion, since one can always elicit the full distribution and then return the property value. Instead, the important question is to ask *how many* parameters would need to be elicited in order to produce the property value for all distributions. The paper provides some nice results that help to understand the notion of "elicitation complexity", and the paper gives some applications of these results that connect with recent work. The paper also considers a new notion of "conditional elicitation" and provides some limited exploration of this idea.On the positive side, the paper does seem to provide nice novel results that help to understand elicitation, making nice connections with the estimation of the Bayes risk. The framework the authors put forth is coherent and natural, and builds upon a great deal of previous but recent work on this topic. The paper really does bring out a coherent way to reason about elicitability. There seem to be cool tricks in here too; in particular, I noticed that Theorem 1 characterizes a class of scoring rules that require an increasing function, a tool I've not seen previously.On the negative side, and why I think this paper is really going to be a stretch for NIPS, is that: (a) the work is highly technical, (b) the paper would be readable by only a small subset of the NIPS community, (c) the technical parts are quite dense with very little in the way of examples or helpful discussion, (d) the 8-page format is too small to lay out the framework appropriately, with motivating examples etc. Overall i think the authors really aren't doing justice to this work if they want to sell this to the broader ML community. This paper, after expanding and improving the technical content, would be much more appropriate for COLT or a statistics journal. I'm probably a 5.5 on this paper, but I could be swayed based on the response and the feelings of the other reviewers.More detailed comments: -- The authors use terms like "how much effort is required to compute it via ERM" but I think this confuses the notion of effort. The "complexity" discussed in this paper is more about description length and not about computational complexity or sample complexity. Those are also interesting questions but not really addressed. -- The beginning of Section 2 is way too dense. The reader not familiar with this line of work is going to find this impossible to wade through. -- Why does 'elic' have a subscript of \mathcal{I} but 'iden' does not? -- The reason that elic(\Gamma) >= iden(\Gamma) should be done much more explicitly, I still don't understand why it's obviously true. -- The authors appear to combine properties via {}-notation, but {} are usually used for sets and so this is confusing. -- I found Theorem 2 quite hard to parse. -- footnote 7 has Example 3.1.4 mentioned twice. -- On the one hand, section 4 seems very dense and quite rushed. On the other hand, there's space at the bottom of page 8 which suggests there was room to add more explanation.