Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper is focused on predictive multiplicity. Predictive multiplicity is when all the models in the Rashomon set (set of models with similar performance statistics on the test set) have different predictions for the same input. The goal is to define a new metric (Rashomon Capacity) for predictive multiplicity that considers the soft probabilistic outputs of the classifier models rather than the one-hot class predictions. This helps to distinguish Rashomon sets where different predictions are a result of highly different predicted probabilities vs  sets where the predictions are different but the come from similar soft outputs. The general idea is to find a prior distribution over members of the Rashomon set such that the divergence from the "center of gravity" of predictions is maximize. The paper continues by computing and approximating the Rashomon capacity metric on various real-world datasets using a several algorithms. 
strengths_and_weaknesses: * The target problem of the paper is important and well-motivated.
* The paper is well-organized and the writing is smooth. The paper would be easier to understand with a step-by-step algorithm box either in the main text rather than referring to the algorithm's name and the provided code.
* The experimental section focuses on useful data set examples but no case study has been discussed to have a better understanding of how Rashomon capacity can be crucial in real-world scenarios. It would be very useful to have an example.
* The paper seems to be an extension of existing work. In order to prove its contribution, there needs to be an either empirical or theoretical comparison with existing work. in the experimental section no comparative analysis is performed to empirically showcase the advantage of using Rashomon capacity versus ambiguity and discrepancy.
* It would be more comprehensive if the greedy algorithm's performance is compared for the other two datasets (CIFAR10 and adult income).
* All in all, the paper does a decent job in motivating and explaining the Rashomon Capacity but does not provide enough empirical evidence on its advantage and utility in order to satisfy the paper's motivation.

questions: - What is the theoretical guarantee for the upper bound on errors of the two AWP and sampling algorithms?
- One approach to address the issue seems to be using an ensemble of models. How does the cardinality of Rashomon set scale vs the number of models in the ensembles?
- Another approach to address the issue is to use several metrics rather than cross-entropy loss (fairness metrics, etc). How does the cardinality of Rashomon set change with this approach?
limitations: * The main algorithm the results in the finding the largest Rashomon Capacity (AWP) is computationally expensive.

------After rebuttal-----

I thank the authors for providing a comprehensive rebuttal. I will take their response to my review and other reviews into consideration throughout the decision process.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper proposes ways to quantify “predictive multiplicity” (the extent to which equally accurate models disagree on individual predictions) for probabilistic classifiers. Specifically, it introduces a quantity called Rashomon Capacity and demonstrates its usage to report predictive multiplicity on different datasets and models.

strengths_and_weaknesses: Strengths:
- The problem of predictive multiplicity is important and timely.
- The paper is written quite clearly.
- The notion of Rashomon capacity is natural & well motivated.

Weakenesses:

- In terms of significance, I found the main argument for extending existing notions for binary classifiers to probabilistic classifiers not completely clear/satisfying. For example, it is mentioned that two scores can be very close (e.g. one example has score 0.49 for class 1, the other 0.51), and the existing methods would report multiplicity when there isn’t “really” any multiplicity. But doesn’t this depend on how the probabilistic classifier ends up being used? E.g. if the probabilistic classifier is the extracted probabilities from a Logistic regression model that will then be used to make binary decisions by thresholding the scores at 0.5, then I *should* treat 0.49 different from 0.51, no? I think this approach would make sense if binary decisions are obtained by randomizing according to the scores (e.g. classifying someone as 1 w.p 0.49), but I don’t think anyone uses ML models this way. 
- In terms of clarity: (1) The paper makes some bold claims which I felt were unjustified, since the claims themselves were not really made formal. For example, it is mentioned in several places that the proposed methodology “resolves” predictive multiplicity. But what does “resolve” even mean in this context? (2) In many places I felt like important details were omitted from the main text. For example, it is mentioned somewhat in passing, “Rashomon Capacity can be computed by standard procedures such as the Blahut-Arimoto algorithm”. The details of the algorithms are fine to omit, but a description of the assumptions is important - for example, it’s not clear to me if this assumes the Rashomon Set itself is already known, and what’s the computational complexity of this procedure. Similarly for the following result (Proposition 2): the statement claims the existence of at most c models, but can they also be found efficiently?
- Finally, in terms of quality: The connection between the definitions and theoretical results to the experimental section was often unclear or lacking. For example, if I understand correctly, the proposed methods (e.g. sampling and AWP) are heuristics, and do not compute “the Rashomon capacity” but some approximation of it. I couldn’t really understand if sampling is a baseline and AWP is the “proposed” approach and whether the claim is that it is better (because the capacities are larger). Also I would have liked to see some semi-synthetic experiments (where the “real” Rashomon capacity is known or can be computed efficiently) so that the performance of the heuristics could be evaluated. E.g., for all we know, the Rashomon capacity is large for every input and we only observe it’s small on some inputs because of optimization issues. 

Overall I think the paper could have high impact, but at its current form I'm left with more questions than answers regarding many of the concepts used and the claims made, hence my current score.

questions: - I would like to see the authors strengthen the claim that we need to model predictive multiplicity at the score level (as opposed to the decision level).  
- Some questions/comments regarding the definition of the Rashomon set: first, I would distinguish the true Rashomon set (computed w.r.t the true risk) and the empirical Rashomon set (computed w.r.t the empirical risk). E.g. I would denote them $R(H,\epsilon)$ and $\hat{R}(H, \epsilon)$, respectively. More importantly, I don’t understand why the $\epsilon$-level set is one sided - i.e., consists of all the classifiers in $H$ that have loss at most $\epsilon$ as opposed to loss approximately $\epsilon$ . I understand that for a specific choice of $\epsilon$  (close to the loss of the ERM, as mentioned in the footnote) the two notions coincide, but (a) on a definitional level, it’s not clear to me why this is the definition, (b) in the experiments, a range of values of $\epsilon$  is considered. I find this weird because if the best loss achievable in $H$ is 0.1 (e.g. by $h1$) then the Rashomon set w.r.t $\epsilon = 0.2$ will naturally will have different predictions for some inputs (when $h1$ disagrees with the predictions of $h2$, a classifier with loss $0.2$), but it’s not clear to me that this falls under the “predictive multiplicity” phenomena (because $h1$ and $h2$ are clearly distinguishable). 
- In the definition of desirable properties for a metric $m(\cdot)$, is it important that there is a classifier that assigns the one-hot vector $e_j$ as opposed to that the argmax is $j$?

limitations: Yes
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: 
This paper proposes a new metric to measure predictive multiplicity, called Rashomon Capacity (RC).  Unlike previous metrics, RC depends on the probability prediction instead of the discrete predictions. To compute RC, the authors propose to perform AWP, which is more efficient and random initializations.
strengths_and_weaknesses: 
Strengths:

The problem of predictive multiplicity seems important. Proposition 2 makes reporting RC possible in practice. This paper is well-written and easy to follow. The introduction lays a good background of this area.

Weaknesses:

1. RC seems very expensive. Computing RC for one data point requires performing $c$ optimizations. While random initializations can be shared for different data samples and save time, from Fig 3 it is clearly (greatly) underestimating RC.

2. The motivation seems weak, given the cost of computation and the unclear message it conveys without as specific $\epsilon$. It could probably be used to measure model robustness, but I think that's just [31]? Can the authors briefly explain how RC will be used in a decision marking process? My question 4 is also related to motivation.

3. As an evaluation metric, RC (AWP) requires running multiple optimizations. It seems like unlike metrics like accuracy, it is unclear how to compare RC across different $\mathcal{H}$ (or even within the same $\mathcal{H}$ but with different optimization methods) if the optimization is not finding global optima. 
questions: 1. How is this paper related to model calibration? If the predicted probability is not calibrated, it seems pointless to use it in the definition/computation of RC.

2. How to choose $\epsilon$ in practice, or how to interpret it? Obviously, the value of RC is critically dependent on $\epsilon$, but it seems like a quantity that's hard to interpret and it's thus not clear to me how to incorporate RC in the decision making process. This is not related to Section 2.3 in the Appendix. (I should mention I'm not generally familiar with how people use Rashomon sets either.)

3. It is not clear whether this paper actually computes a good RC or not. There is a huge gap between AWP and sampling in Fig 3., but does AWP measures RC well or is it still underestimating? Can (and if so how) we tell?


4. Following 1, why avoiding discrete/binary predictions and measuring Rashomon effect in a continuous space is a good thing? Let's say 1000 models all agree a sample $x_i$ has $0.5\pm\epsilon$ probability of being a cat (i.e. a hard example). If we consider the thresholded prediction, then maybe we get high predictive multiplicity due to the high variance around $0.5$. RC will say there is no divergence here really. It seems to me in practice this $x_i$, when used with any of these 1000 models, is still worth a lot of attention from the decision maker, so it should be considered as a high multiplicity input?
limitations: 
See Weaknesses above. In general I think the motivation is the major limitation.


Minor issues:
1. typo @L145: "Given" -> "given"
review_title: null

Meta-review: metareview: The paper presents a new metric for “predictive multiplicity”, which is the tendency of different models from a hypothesis class with similar overall performance to make different predictions on individual samples; predictive multiplicity is relevant to fairness and interpretability of ML models. The paper also presents analysis and algorithms for computing the metric. 

The three reviewers generally agreed in their characterization of the paper: the high-level goal was well motivated and timely, the paper was very well written, and technically solid. They raised concerns/questions about motivation and connection to other ideas (e.g., ensembles, calibration), as well as specific suggestions for the experiments and writing. The authors made substantive changes in response to suggestions (especially those of Reviewer hCae) and wrote very detailed responses to questions. Overall, the remaining hesitation from reviewers centers on the significance and usefulness of these ideas in practice. This left the paper as borderline in its ratings. To the meta-reviewer (who also looked at the paper), some skepticism about whether this is the final solution for characterizing the reliability of ML model predictions is certainly warranted; however, the paper appears to be a solid contribution to a nascent area that provides a starting point and is likely to provoke discussion and follow-on work.

confidence: Less certain
Decision: Accept