Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This focus of this paper is a method for the evaluation of Machine Learning models with respect to their worst-case performance over all sufficiently large sub-populations. This has important applications in validating the performance of a model from a fairness perspective and ensuring that its predictions do not adversely affect a disadvantaged group.
The first contribution is to formalise the notion of “performance under worst-case subpopulation”. Here we have a distribution $P$ over random triples $(X,Y,Z)$ where $X$ is a covariate in $\mathcal{X}$, $Y$ is a label in $\mathcal{Y}$ and $Z$ corresponds to a set of protected variables e.g. income, ethnicity, gender etc. Let  $P_Z$ denote the associated marginal distribution with respect to a covariate $Z$. Given a lower-bound on the population $a \in (0,1]$, the associated collection of sub-populations is then given by,
$$\mathcal{Q}_a:=\left\lbrace Q_Z:P_Z= \tilde{a} \cdot Q_Z +(1-\tilde{a}) \cdot Q_Z' \text{ for some }a\geq {a} \text{ and  probability measure }Q_Z'  \right\rbrace$$. Given a predictive model $\theta: \mathcal{Z} \rightarrow \mathcal{Y}$ and a loss function $\ell:\mathcal{Y}^2 \rightarrow [0,\infty)$, the worst-case sub-population performance with lower bound $a$ is then defined by 

$$ W_a(\theta):=sup_{Q_Z \sim \mathcal{Q}_{a}} E[E[\ell(\theta(X),Y)| Z] ] $$

where $Z$ is sampled from $Q_Z$ and $(X,Y)$ is sampled from the conditional distribution of $P$ given $Z$. The next goal is to estimate the worst-case sub-population performance $W_a(\theta)$ based on a data sample.

The second contribution of the paper is to develop an estimator $\hat{W}_a(\theta)$. In essence this proceeds by finding an estimate $\hat{h}$ for the conditional loss $h^*(Z):=E[\ell(\theta(X),Y)| Z]$, and then applying a variational formula.

The third contribution is to provide a finite sample guarantee (Theorem 1) which gives a high-probability bound between  $\hat{W}_a(\theta)$ and $W_a(\theta)$. This first result uses two assumptions: 1) A bounded loss function and 2) the conditional expectation  $h^*(Z):=E[\ell(\theta(X),Y)| Z]$ belongs to a known low-complexity class $\mathcal{H}$. The deviation bound is given in terms of local Rademacher complexity. 

The fourth intended contribution is Theorem 2 which attempts a to give a tight deviation bound on  $\hat{W}_a(\theta)-{W}_a(\theta)$ without relying upon the complexity of the class $\mathcal{H}$..

Up to this point the lower bound $a$ is effectively viewed as a user-specified parameter. Next the authors turn to an alternative framework where the quantity of interest is not  ${W}_a(\theta)$ for a single value of $a$, but rather $a^*$, the smallest value $a$ for which $ {W}_a(\theta)$ is below a user specified upper bound on the loss. The final theoretical contribution is Theorem 3 which gives an estimator $\hat{a}$ for $a^*$ and a high-probability upper bound on the deviation between $\hat{a}$ and $a^*$.
The paper also includes an empirical illustration of the estimator in practice on two data sets for which worst-case performance is of interest.

main_review: Providing Machine Learning methods which perform well for across diverse sub-populations without adversely affect a disadvantaged group is an crucial challenge of great importance to the Machine Learning community, and a potential for significant societal impact. Here, the goal is slightly more modest: The intention is to evaluate the worst-case performance of an existing trained model. Nonetheless, this can be viewed as building block towards learning models which perform well across diverse sub-populations. In this sense the problem is a significant one.

An interesting connection is drawn with the Rawlsian approach to social justice in which social inequalities can only be justified if they improve the situation for the worst-off within society. The direct ML analogue here being that we can justify a heterogenous performance of a predictive model only in so far as this results in a better performance for all sub-populations.

As noted by the authors, the problem has a great deal in common with the recent work of Duchi et al. (2020) [33] on distributionally robust learning which focuses on the more challenging problem of learning rather than evaluation. In light of Duchi et al’s prior the present paper is not quite so original from a conceptual perspective. Nonetheless, the problem of evaluation for existing models is arguably of interest in its own right.  

In terms of quality the paper has potential, but a few significant issues. Let’s address each of the theorems in turn before turning to the experiments.

Theorem 1 is the strongest result in the paper. An high-probability guarantee is provided for the deviation between $\hat{W}_a(\theta)$ and $W_a(\theta)$. The presence of the square root of the local Rademacher complexity (rather than the standard Rademacher complexity) is of interest. This is a consequence of the difficulty of estimating $h^*(Z):=E[\ell(\theta(X),Y)| Z]$ by ERM on the squared loss, with the square root (and the parametric rate of $n^{-1/2}$ originating from the move from L1 to L2 error via Cauchy-Schwarz (see line 731). The proof proceeds by combining existing results on together in an interesting way. One major limitation of the result is the use of Assumption 2 ie. The assumption that $h^*(Z):=E[\ell(\theta(X),Y)| Z]$ belongs to a pre-specified low-complexity class. Here an oracle type bound would be preferable. That is, rather than include Assumption 2 (which is less interpretable than the corresponding realisability assumption in say classification), the authors could include an approximation error term so that the bound depends upon the deviation between the conditional expectation $E[\ell(\theta(X),Y)| Z]$  and the best approximator in the class.
There are a couple of minor issues surrounding the presentation of Theorem 1. Firstly, it would be good to reference Mendelson near the statement of Lemma 2 (i.e. within the main paper rather than the Appendix). As another minor point, the proof of Theorem 1 seems slightly over-complicated since Assumption 1 asserts boundedness. Hence, the full machinery of Orlicz norms is not really necessary.

In the case of Theorem 2 it would be very useful to include a discussion when we should expect the quantity $\Delta_n$ to be small. Note that in general we would not expect this quantity to converge to zero as $n\rightarrow \infty$. 

Theorem 3 requires further explanation. In particular, it seems that the denominator on the right hand side of the inequality could be arbitrarily close to zero. Indeed, for the bound to be meaningful we require $a^*\geq \underline{a}$ which suggests that the expectation in the denominator is low. Some discussion of optimality would be very helpful here.

There are also some limitations regarding the experimental section. This section demonstrates some potential applications of the method. However, it would be more interesting to see an empirical demonstration of the efficacy of the method. This could be done by evaluating on synthetic data, where the estimated quantity is known. Another potential issue is the confidence intervals in Figure 2. How should we interpret these? If they originate in the bound in Theorem 1 it seems strange that they are not much larger for the more flexible model classes? It would also be good to include confidence intervals in Figure 3. 

Overall, I found the idea to be interesting, with significant promise and potential for valuable impact. 

My remaining concerns with regards to this paper concern the empirical results section and the degree of optimality in the theoretical results. Please see below for more details.

Updates following author response:

Thanks for your careful response which provided a great deal of clarity. Please see below for more details.

1)	Misspecification error in Theorem 1

Thanks for the clarification. I believe dropping Assumption 2 and including this additional term would be a small change that improve the result.

2)	Incorporating heavier-tailed losses

It would indeed be interesting to include these results in the main the text. An alternative would be to adhere to the current boundedness assumption and give the simpler version of the proof accordingly.

3)	Correctness of Theorem 2

Yes! My mistake entirely – Apologies. The proof is indeed correct. Thank you for the clarification.

Here I think its important to underline that we can’t in general expect $\Delta_n$ to be small even if the model class is arbitrarily rich, and the sample size is arbitrarily large. Indeed, we can would only expect this to hold if $l(\theta(X),Y)$ has zero conditional variance given $Z$. 

4)	Discussion on Theorem 3

Thanks for the clarification. The key point here is that there are natural situations where the bound in Theorem 3 is uninformative. For example, we are particularly interested in situations where $\alpha_*$ is small (i.e. the learnt function is fair). However, for sufficiently small $\alpha_*$, the $1-\alpha_*$-quantile will typically be very close (or even equal) to the essential supremum. Whenever this occurs the RHS of the bound will blow-up. Perhaps this is a necessary feature of any bound of this form. 

5)	Confidence intervals and experiments

The main result of the paper (Theorem 1) yields confidence intervals for $W_\alpha$. As such, it is somewhat surprising that these are not used in the simulations (instead of 5 random repeats). 

I also believe it’s strange that only Figure 2 includes confidence intervals (i.e. not Figure 4). In the final version we should see confidence intervals for all experiments.

Overall, with these experiments it remains unclear what conclusions we can draw regarding the efficacy of the method since there is no method-independent standard of correctness. For this reason I would suggest giving greater emphasis to experimental results on synthetic data where the quantity being estimated is known a priori.

The CLT-type asymptotically valid confidence intervals would certainly make for an interesting development. Of course it may be difficult to include these results whilst also providing further clarification on the existing results.


6)	Optimality

In each of the theoretical results – Theorems 1,2,3 a discussion of optimality would greatly improve the paper. In the case of Theorem 1 it seems highly plausible that the $O(n^{-1/2})$ rate is optimal. Still, it would be useful to provide some argument for this in the text. In the case of Theorem 2 the $O(n^{-1/4})$ is unusual and some discussion of optimality would be especially valuable. Similarly, the denominator in the bound of Theorem 3 can be expected to be very small under natural settings, and again a discussion of optimality would be really valuable here.

limitations_and_societal_impact: As discussed above, the work is promising with a potential for positive societal impact in providing fairer applications of ML.

There are a few limitations to the present evaluation, also discussed above. One issue with the paper is that there is little discussion of the optimality of the bounds. It seems very likely that the $n^{-1/2}$ rate in Theorem 1 is optimal. The optimality of Theorem 3 is much less clear.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper focuses on evaluating the performance of a supervised learning model $\theta: X \to Y$ over a set of subpopulations $Z \sim Q$. The authors consider a setting with "subpopulation" shift -- i.e., where the training data under/over samples data from a particular group. In this setting, they propose to bound the ``worst-case" group performance defined as: $$W_{\alpha}(\theta) := \max_{Q \in \mathcal{Q}_alpha} \mathbb{E}_Q[l(\theta(X),Y|Z)].$$ The authors present a new technique to estimate this quantity, and characterize its convergence in finite-sample settings. The authors apply their measures to determine the "worst-case" group-specific performance of models in 2 real-world prediction tasks: Warfarin dosage prediction, and land use from satellite images.


main_review: My overall impression is that this is promising work, but that it that requires some additional development to have long-term impact. The two most pressing weaknesses that I believe should be addressed include:

1. **Guidance for General-Purpose Applications**: The proposed performance evaluation framework requires that domain experts make difficult decisions – e.g., setting the value or $\alpha$ or the maximum level of acceptable loss. The paper would be stronger if the it included guidance for how to set these values. In particular, we need worked-out examples so that non-experts can use choose these values in an informed manner – ideally in Section 2 (Approach) and Section 4 (Experiments). The experiments in Section 4 focus on real-world datasets, but lack the type of guidance that would help real-world practitioners.  

Ideally, I would recommend the authors provide this guidance for "common" machine learning applications. For example, if are using a binary classification task, then I would consider a setting where you are building a logistic regression model and where you measure performance in terms of AUROC or Expected Calibration Error (c.f. Squared Loss). These choices reflect the most common standards in clinical prediction models.

One related issue is to adapt the existing experiments to settings that are not "vacuous."For example, the "worst-case" 0-1 loss for all models in Table 1 currently exceed 50%. This result, which arises in the "worst-case," means that for subgroups larger than 1\% we might be better off using a coin-flip. The result is not wrong, but rather irrelevant. In a setting like this, we would ideally present practitioners with a meaningful guarantee (e.g., for $\alpha = 5%$) and a result stating the range of $alpha$ for which results are non-trivial. 

2. **Comparisons to Simple Alternatives**: I enjoyed the fact that the current work focuses on the less "ambitious" scope of model evaluation. That being said, the paper needs to motivate and illustrate why we would want to use this machinery for evaluation as compared to existing alternatives to evaluate model performance. This could include: CV / Bootstrap / Parametric Bounds and the performance measurement approaches of Kearns/Herbert-Johnson. 
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: 
This paper poses the problem of evaluating the worst-case risk over subpopulations, which is an important way to quantify the fairness of a learning algorithm. Unfortunately they do not consider the learning aspect of this problem, but rather treat the model as fixed, however they do make substantial contributions, and show that even evaluating worst-case subpopulation risk is challenging in full generality.  It seems the future work could address this shortcoming. In particular, in their model, they allow for a sophisticated and abstract notion of subpopulations, defined by a function family $\cal H$ applied to a random variable $Z$, usually representing protected information. The authors explore an approach based on localized Rademacher averages, and one using a 2-fold cross-validation strategy, to control for the multiple comparisons aspect of considering many subpopulations in the worst-case.

main_review: 


I found the problem to be appealing, though I would have preferred to see some analysis of the learning aspects of the question, since as it stands only the statistical estimation aspect of the problem is really handled. In particular, as the authors already consider bisecting the sample to evaluate worst-case population risk, it stands to reason that one could trisect it to train a model on the first fold, and use the next two folds to evaluate worst-case risk, though it would be more satisfying if all of these tasks could be accomplished on a single sample.  Unfortunately I found the paper rather difficult to follow for several reasons, not the least of which was the lingering persistent surprise that the learned function was fixed, and the hypothesis class is only over subpopulations. In particular, further exposition of the hypothesis class $\cal H$, and how it can be used to model various subpopulation categories, would have been greatly appreciated.


I also wonder whether the localized Rademacher average methods were only loose due to poor constants in the cited analyses; I believe [2] substantially improves the earlier results of Bartlett, Koltchinskii, and others. Furthermore, the decision to use localized Rademacher averages, rather than, e.g., global Rademacher averages was not well-explained.  I suspect this decision was made quite consciously, as the authors seem very knowledgeable in statistical learning theory, but to a layreader, it could easily come across as somewhat arbitrary (and thus somewhat uninteresting).  To clarify, in my understanding, localized bounds are very appropriate for this purpose, as they are more sensitive to low-frequency (low raw-variance) events, and behave essentially like relative bounds, as opposed to uniform additive bounds. Some comparison to methods using global Rademacher averages and an explanation of how this is relevant to fairness w.r.t. small subpopulations, would help connect this section better to the overall themes of the paper, and to ideas in statistical learning.

I believe a minor technical error is to be found below, though it does not significantly impact the work (I don’t believe localized Rademacher averages were used in the experiments anyway).  On line 201: “The localized Rademacher complexity itself is sub-root.” Doesn’t the function family need to be closed under absolute convex combination (a.k.a., take the star convex hull with 0), for the localized Rademacher complexity to be sub-root? I'm reasonably confident that this is the case, otherwise localized Rademacher averages are 0 or undefined for sufficiently small $r$, as the class may become empty.


I would also have liked to see some experiments with simpler hypothesis classes (like threshold families), using the localized Rademacher average bounds as well. Even if they were vacuous or not very sharp, it would have been interesting, and they could have been compared to the cross-validation results. Simpler hypothesis classes would have also nicely bridged this work to earlier results based on, e.g., demographic groups, as per the example of figure 1.




Specifics:

A comparison to [1] would be quite interesting. In the parlance of that work, it seems the authors wish to compute the egalitarian malfare, and their proof techniques revolves around subpopulation Rademacher averages, which may be relevant.  They also consider other power-means, which may be possible in this framework as well.

Line 68: what are the implications of this averaging with respect to various loss functions? This feels a lot like 2-fold cross-validation.

86: all subpopulations large than -> all subpopulations larger than


131/133: Klein (not Consortium), is the lead author of [27].

156: I followed $h^*(Z)$ and $\hat{h}(Z)$, but it took quite some time to understand $h(Z)$. It's really not clear what the model class here is doing. Is it just that $\cal H$ needs to be able to predict conditional risk of values given $Z$? This is in dire need of more exposition and explanation.

Equation 6: This was quite difficult to follow how this translates to worst-case subpopulation risk.  More explanation would be appreciated as this is a crucial detail.

Equation 6: Of note is that if we minimize over $\theta$ instead of $\cal{h}$, it seems we are trying to minimize the weighted average of conditional variances over losses, conditioned on each $Z$? This seems quite related to maximizing within-group fairness (while completely neglecting between group fairness).  Is there an interesting connection to be made here?

It's clear to me that the objective (6) is a standard square loss minimisation problem, but what I don't understand is how large is the error due to using the plug-in estimator (lemma 1), and in particular, in the comment on 167, “for a sufficiently rich model class $\cal H$”, what happens if $\cal H$ is not sufficiently rich.


Overall, why are we not simply maximizing conditional risk values given $Z$? I get that that becomes statistically intractable for a large $Z$, but if $Z$ is too large, then presumably we don't have a sufficiently rich $\cal H$ class, so the relationship between this minimizer and worst-case subpopulation risk breaks down anyway. What am I missing here, how do we overcome that issue?

Going into algorithm 1 on my first read, I really thought we were talking about minimization over the model. Some more explanation of how the class of $\cal H$ is a class over subpopulations, and we're just trying to estimate the worst case risk for a fixed model would be very helpful.


167: “the minimizer is given by” Isn’t this a scalar? Is it the minimum or minimizer?

Algorithm 1 line 3: without some parentheses, the $\eta$ may be read as though it is inside the sum, which is of course foolish, and I believe inconsistent with equation 5.  This should be written more clearly.



229: This is a bit difficult to read.

Section 3.2: I struggle to see how we can get any kind of guarantee using a large deep network for $\cal H$, unless we're assuming we can train the network to optimality. It looks to me like the gap is measured between the selected $\hat{h}$ and the worst-case subpopulation, but it feels like it should be that the estimate on S1 of $\hat{h}$ should roughly be an upper bound, and the estimate on S2 of $\hat{h}$ should roughly be a lower bound on the true worst-case subpopulation risk.  I don’t really see why localization assumptions 1, 2 are needed in theorem 2.


References:


[1] An Axiomatic Theory of Provably-Fair Welfare-Centric Machine Learning
C Cousins

[2] Local rademacher complexity: Sharper risk bounds with and without unlabeled samples
L Oneto, A Ghio, S Ridella, D Anguita
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper provides a method for evaluating the performance of a learned model on worst-case subpopulations of the data. The method is highly scalable and can handle continuous variables.
main_review: $\textbf{Originality}$

To my awareness the presented method is novel. In addition, as pointed out by the authors, the method is highly scalable, unlike previous distributionally robust algorithms.

$\textbf{Quality}$

The work appears technically sounds and proofs of all results are presented in the supplementary material.

$\textbf{Clarity}$

Overall, the paper is well-written, however my main concerns are related to the lack of explicit data generation model and to the notion of worst-case subpopulation risk. In particular, in the introduction the objective (2) is presented, but several important aspects remain unclear to me, also throughout the paper. In particular, what is the distribution $P_Z$ and how does it relate to the data generating distribution? Is it the marginal distribution of $Z$? In this case, how is the distribution $(X,Y)|Z$ defined when the distribution of $Z$ changes? 

Additionally, while the notion of subpopulation used is relatively natural, I wonder if equation (1) can be accompanied by some example (e.g. specific application with specified $X,Y,Z, Q_Z$ etc.), to improve readability.

$\textbf{Significance}$

Evaluating model performance under worst-case subpopulations is certainly important for the sake of both robustness and fairness of ML algorithms. In its current form, the method only addresses the problem of estimating whether a given model has a good subpopulation performance. It will be interesting to know if the method can also be used iteratively at training time to help learning a distributionally robust model.

limitations_and_societal_impact: Nothing comes to mind.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors developed the evaluation method for the worst-case loss of a given predictor over all the subpopulations. The method is motivated to evaluate how a given predictor is robust against population change of the random variable Z.  The authors theoretically investigate the estimation error of the proposed method and show two high probability bounds on the estimation error. One of the bound depends on the complexity of the model to estimate the conditional mean of loss; however, we can achieve a convergence rate faster than $1/n^{1/4}$ if the model complexity is low. Another one is the data-dependent bound and is independent of the model complexity; however, the convergence rate is $1/n^{1/4}$. They also provide some showcases to utilize the proposed methods.
main_review: This paper is well-written, technically sound, and interesting. The data-dependent bound in Theorem 2 is very surprising for me because it is independent of the model complexity and is only dependent on the learned model. This is quite nice as we can employ an arbitrary complex model. Therefore, my current decision is acceptance.

The paper may be improved by providing a more detailed comparison between the obtained bounds, i.e., those in Theorem 1 and Theorem 2. Specifically, it is better to clarify when the sample complexity obtained from Theorem 2 is better than that obtained from Theorem 1. The authors already mentioned that Theorem 2 is better when the model is too complex. However, it is better to clarify when the model is too complex to make the bound in Theorem 1 loose. It helps readers to understand why the authors provide two bounds.

I checked all the proofs provided in the supplementary material and only found a minor flaw that may be fixed easily. See the following for the detail.
- The right-hand side of Eq. 17 in the appendix might be incorrect but can be fixed easily. The first term should be multiplied by 2, and in the second term, \hat{h} and h^* should be exchanged. 

limitations_and_societal_impact: The limitations and potential societal impact are adequately discussed.
review_title: null

Meta-review: The paper provides some interesting theoretical results on estimating the worst-case performance of a model over all subpopulations of a given size, and has supporting experimental evaluations. The reviews generated a detailed back-and-forth discussion with the authors. The main concerns raised by the reviewers are about the lack of sufficient experimental results demonstrating the efficacy of the proposed method and the lack of practical guidance for choice of the group size parameter $\alpha$. 

My impression of the paper is that the results presented would be of interest to the ML fairness community, and so I would recommend accepting it. However, it's very important that the authors do a thorough job of incorporating the following changes in the final version of the paper (in addition to the other changes that they have promised to make in their response):
- Simulation study analyzing the asymptotic convergence of the proposed estimator
- Experiments illustrating how the parameter $\alpha$ should be set

I would also like to emphasize that the reviewers were chosen from diverse backgrounds within ML to assess both the theoretical and practical aspects of the work, and I think they have done a thorough job of reviewing the paper. I understand that there were some initial questions about the correctness of Theorem 2 (which, to be honest, I too had during my initial reading of the paper), and I am glad that the authors were able to satisfactory resolve them. I trust that the authors will use all the feedback provided and make all the changes they have promised in their response.
Decision: Accept (Poster)