Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper looks at convex surrogates of supervised loss functions and tries to obtain lower bounds for the convex consistency dimension which is the lowest prediction dimension with a consistent convex surrogate. They look at two variants of the problem, namely target loss and target statistic and separately for discrete and continuous cases. They define a tool called d-flat which can be used to bound the convex consistency dimension. The work largely relies on the condition of property elicitation, which is a weaker condition than calibration and is defined on a variety of domains such that the convex elicitation complexity lower bounds the convex consistency dimension. They also use the idea to find solutions to two open problems, one related to lower bounds of risk measures and the other for mode and modal interval.
main_review: This paper looks at convex surrogates of supervised loss functions and tries to obtain lower bounds for the convex consistency dimension which is the lowest prediction dimension with a consistent convex surrogate. They look at two variants of the problem, namely target loss and target statistic and separately for discrete and continuous cases. They define a tool called d-flat which can be used to bound the convex consistency dimension. The work largely relies on the condition of property elicitation, which is a weaker condition than calibration and is defined on a variety of domains such that the convex elicitation complexity lower bounds the convex consistency dimension. They also use the idea to find solutions to two open problems, one related to lower bounds of risk measures and the other for mode and modal interval.

The paper has a lot of involved concepts, particularly for a reader not familiar with the area, but the authors provide enough context and links to related work to form a broad idea of the general principle of both convex consistency dimension and the idea of d-flats/property elicitation. I am also curious whether understanding about the lower bound of the convex consistency dimension necessarily means attainability (the lower bound always is reached for some convex surrogate) and also whether it would be possible to estimate such a surrogate given the understanding of the prediction dimension. 
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors introduced a new tool for proving lower bounds on the convex consistency dimension, which is defined as the smallest dimension d such that there exists a link function and convex loss function L of dimension d that are consistent. They showed a connection between the convex consistency dimension and the existence of d-flat. The result can be applied to a wide range of tasks, such as classification, regression and variance estimation. In particular, they apply the tool on risk measure (4.1) and mode and modal interval (4.2) and obtain new lower bounds in these settings.

main_review: Questions:
1.What are the practical implications of this result? Will the theory here provide guidance on how to select a surrogate loss function?
2.The paper never defined consistency in the main text despite using the term frequently. I would suggest moving Definition 7 and 8 to the main text.

I apologize that I have no expertise in this area and don’t know anything about the relevant literature, and therefore my confidence is low. The paper seems to provide a nice tool for proving convex consistency dimension lower bound. Though I don’t know about the impact and significance of the result in the area. Therefore I will vote weak accept for now.

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper presents a new tool to generate lower bounds on the convex consistency dimension of continuous and discrete prediction tasks. The authors apply this tool, called $d$-flats, to yield new bounds on convex consistency dimension for risk measures, mode and modal interval. They show that d-flats recover and tighten the feasible subspace dimension result in discrete prediction settings.
main_review: The new tool used in this paper is based on property elicitation, which is a widely studied area in statistics and economics. Compared with calibration, indirect elicitation is a weaker and simpler condition for consistency. It’s interesting that newer bounds obtained based on indirect elicitation are as tight as calibration-based bounds. 

The authors give the first prediction dimension bounds for risk measures with respect to convex surrogates via d-flats. 

The authors refer to the four cases–target loss vs. target statistic, and discrete vs. continuous predictions–as the “four quadrans” of supervised learning problems. Using property elicitation, they are able to yield lower bounds on prediction dimension of any convex surrogates. Moreover, these bounds apply across all four quadrants.

This is a well written paper and I recommend its acceptance. The theory in this paper will be helpful to understand how to construct consistent convex surrogates for target losses or properties. 

I have some (minor) comments listed below.

1.	This paper considers examples like classification and regression problems, I was wondering if d-flats could be used to study the subset ranking losses.
2.	In the first two paragraphs of the “Setting” section, some notations are not clearly defined, like $\mathcal{B}(\reals^d)$ and $\Delta_{\Y'}$.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper introduces the notion of d-flats for lower bounding the convex elicitation complexity of a property, which also lower bounds the convex consistency dimension of the property. These quantities are studied in the design and analysis of loss functions to accomplish prediction tasks. 

The authors use d-flats to establish lower bounds on the convex elicitation complexity of a variety of properties, such as classification with an abstain option, variance, CVaR, mode, and modal interval. 
main_review: The paper is exposited clearly and has a clear narrative: the proposed method of lower bounding convex consistency dimension by using d-flats to lower bound a smaller quantity, convex elicitation complexity, is a useful technique which unifies previous results and provides lower bounds for some properties which were not previously known. The technique itself appears natural and elegant, derived by writing the subgradient condition for optimality and deducing from it using elementary properties that there exists a subspace in the probability set of codimension at most d. The approach demonstrates novelty, as the most prominent previous approach for lower bounding convex consistency dimension was the feasible subspace dimension approach provided by Ramaswamy and Agarwal [33], which the authors show is weaker than the method of d-flats (the d-flat result derives the feasible subspace result in the appendix). Furthermore, the new lower bounds on the complexities of classification with an abstain option, variance, CVaR, mode, and modal interval also demonstrate the novelty.

A question that I have is whether the method of d-flats can be applied to the multiclass version of the classification with abstain option problem; can a corresponding lower bound be proved without drawing the level sets and visually observing that no lines through a point fit in the level set.

Another question is, what is the significance of lower bounding the prediction dimension of a property? Does this have any bearing on how people normally predict properties in practice? Unless stated otherwise, it feels like most of the time, people know what loss function to use to obtain a property, and the lower bound isn't necessarily adding anything to the practice. 

(minor typo in line 83, "prediction dimension of d")
limitations_and_societal_impact: Yes.
review_title: null

Meta-review: This paper considers the problem of constructing convex surrogates for supervised learning tasks, and provides lower bounds for the convex consistency dimension, which is the lowest prediction dimension with a consistent convex surrogate. Reviewers felt that paper was well-written, and that the techniques are novel and generally interesting. In particular, the authors use their framework to resolve open questions of Frongillo and Kash (2015) and Dearborn and Frongillo (2020). However, given that the topic is somewhat niche for the NeurIPS community, the authors are encouraged to incorporate the reviewers' suggestions to better convey the significance of their results to the broader community.
Decision: Accept (Poster)