On Elicitation Complexity

Rafael M. Frongillo, Ian A. KashNeurIPS 2015 · OpenReview

Abstract

This paper shifts the focus of property elicitation from a binary question ("Is this statistic elicitable?") to a quantitative one ("How many parameters are needed to compute it?"). By introducing the concept of elicitation complexity, the authors provide a framework demonstrating that even "non-elicitable" statistics—such as variance or Expected Shortfall—are computationally tractable within Empirical Risk Minimization (ERM) if models track just one or two auxiliary parameters.

Introduction: The Problem with Elicitability

In machine learning and statistics, practitioners frequently need to find a specific "property" of a distribution (like the mean or median) by minimizing a loss function. This process is known as Empirical Risk Minimization (ERM). A property is formally considered elicitable if there exists a loss function such that the property is the unique minimizer of the expected loss.

Historically, research focused on a binary question: Which properties are elicitable? Unfortunately, the answers were often restrictive. Many highly useful statistics, such as variance or the financial risk metric "Expected Shortfall," are not elicitable. This theoretical limitation suggested they could not be directly "learned" via standard regression techniques.

Frongillo and Kash argue that this binary framing is fundamentally flawed. Technically, any property can be elicited if one is willing to elicit the entire underlying probability distribution first. The real challenge isn't "if" a property can be elicited, but "how much" information is required to do so. They bridge the gap between theory and practice by asking: What is the minimum number of parameters an ERM procedure must track to eventually compute the desired property?

Methodology

To formalize this approach, the authors introduce elicitation complexity. This metric is defined as the minimum dimension $k$ required to represent a target property as a "link" (a simple function) of a $k$-dimensional elicitable property.

Key methodological contributions include:

  • A Calculus of Elicitation: The authors establish mathematical rules for how complexities aggregate when evaluating multiple properties or handling redundant information.
  • Bayes Risk Bounds: The paper focuses heavily on "Bayes risk"—the minimum possible expected loss for a given problem. The authors prove that if a property is $k$-dimensional, its Bayes risk is at most $(k+1)$-elicitable.
  • Identification Functions: To ensure their complexity estimates are tight, the authors utilize identification functions (where the expected value is zero exactly at the true property value) to establish rigorous lower bounds.

(Note: As a theoretical paper focused on the foundations of statistical learning and decision theory, the results are derived via mathematical proofs applicable to any distribution where the relevant expectations exist, rather than empirical datasets.)

Key Insights

The "Indirect" Path to Non-Elicitable Properties

The paper formalizes the intuition that if a property isn't directly elicitable, it can be "embedded" into a higher-dimensional property that is. For example, while you cannot elicit variance directly, you can easily elicit the pair (mean, second moment) and then compute the variance by subtracting the square of the mean from the second moment.

The Complexity of Financial Risk

One of the most impactful insights applies to quantitative finance. "Expected Shortfall," a standard regulatory risk measure, was previously known to be non-elicitable, causing significant theoretical and practical headaches. This paper demonstrates that its elicitation complexity is merely 2. A model simply needs to track the "Value at Risk" (a quantile) alongside it to make it computable via ERM.

Identifiability vs. Elicitability

The authors highlight a crucial distinction: being able to identify a property (knowing if a specific guess is correct) is a weaker requirement than eliciting it (having a mathematical path to find the correct guess via loss minimization). They leverage the gap between these two concepts to define and bound their complexity metric.

Main Results

The framework yields several concrete complexity bounds for widely used statistics:

  • Variance: Confirmed to have an elicitation complexity of exactly 2.
  • Spectral Risk Measures: For a risk measure involving $k$ distinct quantiles, the elicitation complexity is exactly $k+1$. This provides a tight, practical bound for a large class of financial risk tools.
  • General Bayes Risk: The Bayes risk of a $k$-dimensional property has a complexity of either $k$ or $k+1$. It is $k$ only if the Bayes risk is already a simple function of the property itself; otherwise, it requires exactly one additional parameter.
  • Occupying the Spectrum: The authors prove that elicitation complexity is not just 1 or $\infty$. For any integer $k$, there exists a real-valued property with an elicitation complexity of exactly $k$, establishing a full hierarchy of complexity.

Limitations and Future Work

While the paper establishes a robust foundation for elicitation complexity, the authors note several areas for future exploration:

  • The Identifiability Assumption: Most of the paper's lower bounds rely on the property being "identifiable." However, some natural properties (like the "mode" or the "argmax" of a distribution) might have an identification complexity higher than their elicitation complexity, presenting an open puzzle.
  • Computational Efficiency (Convexity): The current framework dictates how many parameters are needed, but it does not guarantee that the resulting loss function is easy to optimize (e.g., strictly convex). The authors propose "eliccvx" (complexity specifically with respect to convex losses) as a critical next step for practical machine learning applications.
  • Characterizing Complexity Classes: Fully characterizing which properties fall into which complexity class (e.g., defining the complete set of all 2-elicitable properties) remains an ongoing mathematical challenge.

Summary updated

Abstract

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.
BibTeX
@inproceedings{frongillo2015elicitation,
  author = {Rafael M. Frongillo and Ian A. Kash},
  title = {{On Elicitation Complexity}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2015},
  url = {https://openreview.net/forum?id=ByVWNDZO-B},
}

Loading related content...

Figure