Evaluating model performance under worst-case subpopulations
Authors: Mike Li
Hongseok Namkoong
Shangzhou Xia
Venue: NeurIPS 2021 Poster (2021)
Keywords: reliability
robustness
safety
distribution shift
subpopulation shift
fairness

Abstract: The performance of ML models degrades when the training population is different from that seen under operation. Towards assessing distributional robustness, we study the worst-case performance of a model over all subpopulations of a given size, defined with respect to core attributes $Z$. This notion of robustness can consider arbitrary (continuous) attributes $Z$, and automatically accounts for complex intersectionality in disadvantaged groups. We develop a scalable yet principled two-stage estimation procedure that can evaluate the robustness of state-of-the-art models. We prove that our procedure enjoys several finite-sample convergence guarantees, including dimension-free convergence. Instead of overly conservative notions based on Rademacher complexities, our evaluation error depends on the dimension of $Z$ only through the out-of-sample error in estimating the performance conditional on $Z$. On real datasets, we demonstrate that our method certifies the robustness of a model and prevents deployment of unreliable models.

Evaluating model performance under worst-case subpopulations
Mike Li
Hongseok Namkoong
Decision, Risk, and Operations Division Columbia Business School
Decision, Risk, and Operations Division
Columbia Business School
New York, NY 10027 cow.ugggb.colmbiiaaa. edu
New York, NY 10027
namkoong@gsb.collug www.://aaooaboooobaa..oo.... edu
Shangzhou Xia
Decision, Risk, and Operations Division
Columbia Business School
New York, NY 10027 SXia240gsb cowumbia. edu
Abstract
The performance of ML models degrades when the training population is different from that seen under operation. Towards assessing distributional robustness, study the worst-case performance size, defined with respect to core attributes Z. This notion of robustness sider arbitrary (continuous) attributes Z, and automatically accounts for complex intersectionality in disadvantaged groups. We develop scalable yet principled two-stage estimation procedure that can evaluate the robustness of state-of-the-al models. We prove that our procedure enjoys several finite-sample convergence guarantees, including dimension-free convergence. Instead of overly conservative notions based on Rademacher complexities, our evaluation error depends on the dimension of Z only through the out-of-sample error in estimating the performance conditional on Z. On real datasets, demonstrate that our method certifies the robustness of model and prevents deployment of unreliable models.
model over all subpopulations of a given
Introduction
The training population typically does accurately represent what the model will encounter under operation. Model performance has been observed to substantially degrade under distribution shift [16] 28
80
53 in speech recognition [52]. automated essay scoring (4, and wildlife Similar trends persist for state-of-the-art NLP and computer vision models [78]74] /74,
conservation
even on new data constructed under a near-identical process [57 66). Heavily engineered commercial
models are no exception [19], performing poorly on rare entities in named entity linking and examples
that require abstraction and distillation in summarization tasks [38
particularly problematic form of distribution shift comes from embedded power structures in data collection. Data forms the infrastructure which build prediction models (00, and they inherit socioeconomic and political inequities against marginalized communities. For example, out of 10,000+ cancer clinical trials the National Cancer Institute funds, less than 5% of participants were non-white (2 Typical models replicate and perpetuate such bias, and their performance drops significantly underrepresentee groups Speech recognition systems work poorly for Blacks (52)
Authors ordered alphabetically.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

and those with minority accents B. More generally, model performance degrades across demographic attributes such as race, gender, or age, facial recognition, video captioning. language identification,
and academic recommender systems
46 17 72
19
Model training typically relies varied engineering practices. It is crucial to rigorously certify model robustness prior to deployment for these heuristic approaches to bear fruit and transform consequential applications. Ensuring that models perform uniformly well across subpopulations is simultaneously critical for reliability, fairness, satisfactory user experience, and long-term business goals. While a natural approach is to evaluate performance across a small set of groups, disadvan- taged subpopulations are hard to define a priori because of intersectionality. The most adversely affected are often determined by a complex combination of variables such as race, income, and gender [19). For example, performance on summarization tasks varies across demographic character- istics and document specific traits such as abstractiveness, distillation, and location and dispersion of information (38]
Motivated by these challenges, we study the worst-case subpopulation performance across all subpopulations of a given size. This conservative notion of performance evaluates robustness to unanticipated distribution shifts in Z, and automatically accounts for complex intersectionality by virtue of being agnostic to demographic groupings. Formally, let Z be a set of core attributes that we wish to guarantee uniform performance over. It may include protected demographic variables such as race, gender, income, age, or susk-specific information such as length of the prompt or metadata on the imput; notably. it can contain any continuous or discrete variables. We let X E X' be the input / covariate, and Y y be the label. In NLP and vision applications, X is high-dimensional and typically dim(2 Z) < dim(X).
We use 0(X) to denote fixed prediction model and consider flexible and abstract losses {(((z); y). Our goal is ensure that the model 0 performs well over all subpopulations defined over Z. We evaluate model losses on a mixture component, which we call a subpopulation. Postulating a lower bound a (0, 1] on the demographic proportion (mixture weight), we consider the set of subpopulations of the data fata-genn distribution Pz
La = {Qz Pz = aQz + aa)Q2z for some a 2 a, and subpopulation 222).
(I)
The demographic proportion (mixture weight) a represents how underrepresented the subpopulation is under the data-generating distribution Pz. Before deploying the model 0, we wish to evaluate the worst-case subpopulation performance
(o(
sup Ez-Qz [E(((((X)))) Z!] QZEQ.
The worst-case subpopulation performance guarantees uniform performance over subpopula- tions (1) and has a clear interpretation that can be communicated to diverse stakeholders. The minority proportion a often be chosen from first principles, e.g., we wish to guarantee uniformly good performance over subpopulations comprising at least a 20% of the collected data. Alternatively, is often informative study the threshold level of a* when a + Wa( crosses the maximum level of acceptable loss. The threshold a provides a certificate of robustness on the model ((-), guaranteeing that all subpopulations large than a* enjoy good performance.
We develop a principled and scalable procedure for estimating the corst-case subpopulation perfor- mance and the certificate of robustness a* A key technical challenge is that for each data point, we observe the loss (()());) but never observe the conditional risk evaluated at the attribute Z
((Z) E[((O(X): Z].
(3)
In Section we propose two-stage estimation approach where we compute an estimate Ty (-) of the conditional risk (u()). Then, we compute a plug-in estimate of the worst-case subpopulation
performance under Ti (.) using a dual reformulation of the worst-case problem 2 We show several theoretical guarantees for estimator of the worst-case subpopulation performance (2). Our first finite-sample result (Section 3.1 shows convergence at the rate o, ( ([omp,,
where Comp,, denotes a notion of complexity for the model class estimating the conditional risk (3).
In some applications, it may be natural to define Z using images or natural languages describing the input and use deep networks to predict the conditional risk (3). As the complexity term Comp,, becomes prohibitively large in this case [10 86), our second result (Section 3.2) shows data-dependent

---

dimension-free concentration of our two-stage estimator: our bound only depends on the complexity of the model class H. through the out-of-sample error for estimating the conditional risk (3) This error can be made small using overparameterized deep networks, allowing us to estimate the condi- tional risk (3) using even the largest deep networks and still obtain theoretically principled upper confidence bound on the worst-case subpopulation performance. Leveraging these guarantees, we develop principled procedures for estimating the certificates of robustness a* in Section 3.3
In Section we demonstrate the effectiveness of our procedure on real data. By evaluating model robustness under subpopulation shifts, our methods allow the selection of robust models before deployment as we illustrate using the recently proposed CLIP model [62].
Related work. The long line of works on distributionally robust optimization (DRO) aims to train models to perform well under distribution shifts. Previous approaches considered finitedimmensinnal
worst-case regions such as constraint sets (29
39
5 and those based notions of distances for
probability measures such as f f-divergences
13 56
55
60
33
32),
Levy-Prokhorov [34),
Wasserstein distances [35] 773 [5] 37 [4 [2). and integral probability metrics based on reproducing kernels 777 87). The distribution shifts considered in these approaches are often contrived and difficult interpret and often result in overly conservative models. Furthermore, these approaches do not currently scale to modern large-scale NLP or vision applications.
Our work is most closely related to Duchi et al. [31, who proposed algorithms for training models with respect to the worst-case subpopulation performance (2) which is a more ambitious goal than our narrower viewpoint of evaluating model performance pre-deployment. Their (full-hatch) training procedure requires solving a convex program with n² variables per gradient step, which is often prohibitively expensive. Furthermore, training with respect to the worst-case conditional risk E[(()(X);Y) Z] do not scale to deep networks that can overfit to the training data [70]. By contrast, our evaluation perspective aims to take advantage of the rapid progress in deep learning. We build scalable evaluation methods that apply to arbitrary models, which allows leveraging state-of-the-art engineered approaches for training ((.). Our narrower focus on evaluation allows to provide convergence rates that scale advantageously with the dimension of Z. compared to the nonparametric Op(n ((/) rates for training (31]. Recently, Jeong and Namkoong 48 studied a similar notion of worst-case subpopulation performance in causal inference.
Our notion of worst-case subpopulation performance is also related to the by now vast literature on fairness in ML. We give necessarily abridged discussion and refer readers to Barocas et al. [ and Corbett-Daviee and Goel [27] for a comprehensive treatment. A large body of work studies equalizing notion of performance over fixed. pre-defined demographic groups for classification tasks [24] 36 (1435551 [8]. Kearns et al. [49 [5], Hébert-Johnson et al. [45] consider finite subgroups defined by a structured class of functions over Z. and study methods of equalizing performance across them. By contrast, our approach instantiates Rawls' theory of distributive justice 664 651 where we consider the allocation of the loss ((::-) as resource. Rawls' difference principle maximizes the welfare of the worst-off group and provides incentives for groups to maintain the status quo (64). Similarly, Hashimoto et al. [44] studied negative feedback loops generated by user retention they use a more conservative notion of worst-case loss than ours-as poor performance on a currently underrepresented user group can have long-term consequences.
Our diagnostics complement the recent approaches to benchmarking under distribution shifts 80, 66 77 7 (78 [57] our procedure does not require -f-toii-bttiitiion data. Since good performance on a particular distribution shift does not necessitate robustness, we evaluate models using the worst-case subpopulation performance
Approach
We begin by contrasting our approach to standard alternatives that consider pre-detined, fixed demo- graphic groups [59]. Identifying disadvantaged subgroups a priori is often challenging as they are determined by intersections of multiple demographic variables. To illustrate such complex intersec- tionality, consider drug dosage prediction problem for Warfarin (26,, common anti- coagulatt (blood thinner). Taking the best prediction model for the optimal dosage on this dataset based on genetic, demographic and clinical factors (26). we present the squared error on the root dosage. In Figure [ when age and race are considered simultaneously instead of separately, subpopulation performance vary significantly across intersectional groups
3

---

2,00
1.75
Conditiona risk
1.50
1.25
1.00
0.75
0.50
0.25
0.00
20
30
40
50
A
W
30A
40U
60U
700
40A
20B
30B
30W
50B
70B
Figure 1. Conditional risk μ(2) E[
Z]. Here Z age the left panel, Z
the center, and Z (age, race) on the right. Asian, B Black, U Unkmown, White.
The worst-case subpopulation performance automatically accounts for latent intersectionaliity is agnostic to demographic groupings and allows considering infinitely many subpopulations that represent least a-fraction of the training population P. By allowing the modeler to select arbitrary protected attributes Z, we are able to consider potentially complex subpopulations. For example, Z can even be defined with respect natural language description of the input X. The choice Z 7nd subsequent worst-case subpopulation performance
2 of the conditional risk
u(Z) [[((((())) Y) 2|-interpolates between the most conservative notion of subpopulations (when - (X, )) and simple counterparts defined over a single variable.
The choice of the subpopulation size should be informed by domain knowledge- desired robustness of the system- and the dataset size relative to the complexity of Often, proxy groups can be used for selecting a. If wish to ensure good performance over patients of all races aged 50 years or older, we can choose a to be the proportion of the least represented (race, age 2 50) group this leads to 5% in the Warfarin data. The corresponding worst-case subpopulation performance guarantees good performance over all groups of similar size.
When it is challenging to commit to specific subpopulation size, it may be natural to postulate maximum level of acceptable loss To measure the robustness of a model, we define the smallest subpopulation size xx (0) for which the worst-case subpopulation performance is acceptable
a0( (0) = inf(a Wa(0) $ E}.
(4)
This provides certificate robustness: if a (0) is large, then 0 is brittle against majority subpopulations; is sufficiently small, then 0 performs well on underrepresented subpopulations.
We now derive estimators for the worst-case subpopulation performance 2 and the certificate of robustness (4), based on i.i.d. observations (X,, Y,, Zz) ~ P. We assume our observations are independent from the data used to train the model 0(-).
Dual reformulation The worst-case subpopulation performance 2 is unwieldy as it involves an infinite dimensional optimization problem over probabilities. Instead, we use its dual reformulation for tractable estimation. We denote [.I,, max(-; 0), and abuse notation by letting W. (h) be the worst-case subpopulation performance for (Z) (so that W, (0) W. (1))).
Lemma (Shapiro et al. [75 Example 6.19] and Rockafellar and Uryasev (67)) If co,
Wg (h) = sup Ez~qz [h(Z)) inf QxEQ.
Ep [M( 7) + 17
(5)
nER
The dual optimum is attained at the (1 -q-unntlle of the h(Z) 168 Theorem 10]. The dual (5)
hence shows (!) tail-average of p()), a popular risk measure known as the conditional
value-at-risk (CVaR) in portfolio optimization (67
Algorithm Two-stage procedure for estimating worst-case subpopulation performance (2)
INPUT: Subpopulation size o, model class H. samples and S₂
2: On S, solve h1 argmin [Si] Eies, (e(0(X;); Y2) - h(Z)))
3: On S2, compute the plug-in estimator (..(h.) = inf,, ক|3 Exss, Ten 1) + +n

---

Two-stage procedure A key remaining challenge in estimating Wa (0) is that we can only observe losses ((0((;);;), and never observe the conditional risk (u()) ( We propose two-stage procedure (Algorithm[) T. where we split the sample into two sets S1 and S2. On the first sample S1, we fit an
estimator h1 (Z) of the conditional risk μu (Z), using any model class H (class of mappings Z + R., by solving an empirical approximation to the loss minimization problem
minimize hEA
(E(O(X); - h(2)))
(6)
We denote by h* a minimizer of (6); for a sufficiently rich model class H. the minimizer is given by mzZ) [(((((():))) Z]. The loss minimization formulation (6) allows the use of any ML estimator, as well as standard tools for model selection (e.g. cross validation). In the second stage, on S2 we construct plug-in estimator for the dual form under the estimated conditional risk ()).) In practice, we switch the roles of S and S2 and average the resulting estimates leverage the entire sample.
To estimate the threshold subpopulation size a (0), simply take the plug-in estimator := inf Wa (h1 s é}.
Since - (ht) is decreasing, the threshold can be efficiently found by simple bisection search.
3 Convergence guarantees
To rigorously verify the robustness of model prior to deployment, present convergence guarantees for our estimator (Algorithm [T) In Section we first give finite-sample convergence at the rate where Comp,, (7() is the localized Rademacher complexity [9] of the model class 7t for estimating the conditional risk y (Z). In some situations, it may be appropriate to define subpopulations (Z) over features of an image, or natural language descriptions. For such high-dimensional variables Z and complex model classes Ht such deep networks, the complexity measure Comp,, is often prohibitively conservative and renders the resulting concentration guarantee meaningless. In Section 3.2 provide finite-sample, data-dependent convergence result that depends only on the out-of-sampii error for estimating u(-). In particular, the out-of-sample error can grow smaller as H gets richer, and result of hyperparameter tuning and model selection, is often very small for overparameterized models such as deep networks, This allows us to construct valid Emite-sample upper confidence bounds for the worst-case subpopulation performance (2) even when Z is defined over nigh-dimensional features and 7. represent deep networks. Finally, in Section 3.3 we provide convergence guarantees for our estimator 7 for the certificate of robustness By building previous guarantees, we are again able to obtain both types of results.
We restrict attention nonnegative and bounded losses. Assumption 1. There is such that {(O(X); Y) E [o, B}, and h(Z) E [0, B] a.s. for all H.
Throughout, we do not stipulate well-specification, meaning that we allow the conditional risk (a()) = EE((((()): not be in the model class H.
3.1
Concentration using the localized Rademacher complexity
To characterize the fnite-sample convergence behavior of our estimator (.) we begin by decom- posing the error into two terms relating the two stages in Algorithm Recalling the notation in Eq. 5
(so that (.( = W..0), we have
Wa (p) W. (h1) Wa(n) Wa (h1) Wa
(8)
(a): first stage
(b): second stage
To bound term (b), we prove concentration guarantees for estimators of the dual 5 (see Proposition
in Appendix A.I. To bound term (a), we use a localized notion of the Rademacher complexity.
Formally, for E En. E and i.i.d. random signs ě 1) (independent of &x), recall the standard notion of (empirical) Rademacher complexity of g C {g = R.
1
n
R., (9) = Eg
sup 9EG
Exg(E))
1
5

---

We say that a function v R + R4 is sub-root 99 if it is nonnegative, nondecreasing, and Any (non-constant) sub-root function continuous,
+ e/rr// /r is nonincreasing for and has a unique positive fixed point. Let thn IR+ - R be sub-root upper bound on the local- ized Rademacher complexity (r)(r) 2 [Rt, egeg G: : I
(The localized Rademacher complexity itself is sub-root.) The fixed point of thn characterizes generalization guarantees ( 54
rr]]-
Let h* be the best model in the model class
h"
argmin [[(( h(Z))²).
NEW
Let (r) be subroot upper bound on the localized Rademacher complexity around ht*
sss (r) 2 2E Ris { E H - =
(9)
We define vis, as the fixed point of (r).
As we show shortly, we bound the estimation error of our procedure using the square root of the excess risk in the first-stage problem (6)
IE (<00
(2)) S E (( h
By using refined analysis offered by localized Rademacher complexities, are able rate of convergence of (P0)),,(())/1)) on the preceding excess risk. In turn, this provides the following Op(v /Cmpp, (H)/n) bound on the estimation error as we prove in Appendix A.2 In the bound, we have made explicit the approximation error term I|A" - plllza- As the model class grows richer, there is tension as the approximation error term will shrink, yet the localized Rademacher complexity of H will grow.
fast
Theorem 1. Let Assumption 7 Thold. For some constant C' with probability least 1 28,
(a( W. (hi) s CB (Viei +
(1/() S
log(2/8) S
+
+
|| All
we let be (1 - 11111k))fraction fraction of the data and S2 be the remaining /kk-fraction for some integer I (e.g. &- = 5), we have |S1] x [Sa] = n. Thus, by controlling the fixed point ris,] of the localized Rademacher complexity, we are able to provide convergence of our estimator (3). For example, when H. is a bounded VC-class [81), is known that its fixed point satisfy ( Corollary 3.7]
is.1 log((S))/VC(7H)) ( (C((H)/1S))
where VC(-) is the VC-dimension.
3.2 Data-dependent dimension-free concentration
In some applications, it may be natural to model Z as a high-dimensional variable. This may include large subsets of (X, Y), or defining Z using unstructured information such as images or natural languages. In these instances,
may wish the conditional risk (3). We now provide an alternative concentration result that depends on the size of model class H only through the out-of-sample error in the first-stage problem (6). We denote for simplicity
deep networks the model class H for estimating
As(
(e(((())::)) 2(Zz))² iES
(10)
|S|
for any function h: 2 R on any data S. We prove the following result in Appendix A.3
Theorem 2. Let Assumption 7 Thold. For some constant C 0. with probability least 1 -35,
(W. - W. (w. (V
( Ass.
CB
log((/0)
1/4
+ 11h" - ull
15
Moreover, if the model class H is convex, then ||A Hlll 1. can be replaced with ||A* -lll 122

---

Linear Regression
Ridge Regression
XGDoost
Random Forest
100%
80%
60%
40%
70%
5%
Subpopulation size &
Figure 2: Worst-case subpopulation performance (O), where W1.0(0) E]e(0(X):)]]
Following convention in learning theory, we refer to our data-dependent concentration guarantee dimension-free. For overparameterized model classes H such as deep networks, the localized Rademacher complexity in l'heorem] becomes prohibitively large [10] 86]. In contrast, the current result can still provide meaningful finite-sample bounds: model selection and hyperparameter tuning provides low out-of- -ut-of-sample performance in practice, and the difference As, (h1) - As, (h*) can be often made very small. Concretely, is possible calculate upper bound this term as As, (h*) lower bounded by mingeH As, (h).
3.3 Certificate of robustness
Instead of estimating the worst-case subpopulation performance for fixed subpopulation size it may be natural to posit level of acceptable performance (upper bound E on the loss) and study a (0). the smallest subpopulation size 4 over which the model 0(-) can guarantee acceptable performance. Our plug-in estimator given in Eq. 7 enjoys similar concentration guarantees as those given in proof we give in Appendix AA.4 statts that the true a" (0) is either close to our estimator & or it is sufficiently small, certifying the robustness
Sections 3.1 3.2 The following theorem-wheee
model against subpopulation shifts.
Theorem 3. Let Assumption 7 hold, let (ő) > 0 be such that for any fixed 10, (. (.) & U66/aa with probability at least 8. Then given any a (0, 1), either (0) < 0. or
(a) â
U(8)
h((z) Pilana
[M(Z))]
with probability at least 1 5, where R.. and P--1 denote the expectation and the (1 ax)-quantile under the empirical probability measure induced by Sz-
Our approach simultancously provides localized Rademacher complexity bounds and dimension free guarantees. Our bound becomes large - 0 and conjecture this to be fundamental difficulty as the worst-case subpopulation performance (2) focuses on a-faction the data.
4 Experiments
On two real datasets, we demonstrate that our diagnostic allows certifying model performance across subpopulations. We first study drug dosage prediction problem, where our procedure ascertains the robustness of a linear regression model over substantially more expressive model classes. Then, we turn to a large-scale computer vision application based on satellite images [25] where natural distribution shifts were recently studied [53]. In both settings, we illustrate how our worst-case subpopulation approach raises awareness on brittle models without knowledge of out-of- distribution samples. Finally, to verify asymptotic convergence of our proposed two-stage estimator, we present simultion experiment on classification task in Appendix C For all experiments, we use gradient boosted decision trees (package XGBoost 22 to estimate the conditional risk u(2) [[((((X))))) 2].

---

4.1 Warfarin
Warfarin is one of the most widely used anticoagulant, often prescribed to prevent strokes [26]. Its optimal dosage varies substantially across geneties, demographics, and existing conditions (up to ten times). We study a Pharmacogenetics and Pharmacogenomics Knowledge Base dataset constructed from optimal dosages found through trial and error by clinicians. The dataset comprises of 4, 4,788 patients (after excluding missing data) alongside features representing demographies, genetic markers, medication history, pre-existing conditions, and reason for treatment. Consortium [26] found that a linear model outperforms number of more complicated modeling approaches (e.g. kernel methods, neural networks, splines, boosting) for predicting the optimal dosage.
Such average- performance needs to translate uniformly to different subpopulations; we need to ensure automated medical models perform well on underrepresented groups (2
63 40 2 We wish to evaluate and compare the worst-case subpopulation performance of different models over Z = X, the entire feature vector. Following Consortium 26].. we take the root-dosage as our outcome Y, and consider the squared loss (((X); Y) = (Y - ((x))² In Figure 2 we observe that the linear model closely matches the performance of more expressive models even over small subpopulations. Moreover, the trend holds over range of different subpopulation sizes (up to 5%). Our finding instills confidence in the linear regression model: addition to being simple and interpretable, diagnostic certifies its advantageous performance even tail subpopulations. However, diagnostic raises some concerns about poor subpopulation performance: on a = 5% of the training population, all models suffer prediction error six times worse than the average-case performance.
4.2 Functional Map of the World (FMoW)
Satellite images can impact economic and environmental policies globally by allowing large-scale measurements on poverty (.. population changes, deforestation, and economic growth [42]. An automated approach allows analyzing data from remote regions at a relatively low cost and provides continuous monitoring of land usage. Towards this goal, it is critical that the models perform reliably across time and space. We study this problem on the Functional Map of the World (FMoW) dataset (25]. where the goal is to predict building/ / land use categories (62 classes) based on satellite images. Across different models, we observe that performance remains similar either temporally or spatially when each dimension is considered separately, but there is substantial variability across intersections of region and year. For a standard DenseNet ERM model [47] (33 that achieves near- thte--ff performance, substantial variability in classwise error rates; there is varying level of difficulty across different classes. (We observed similar patterns for other models.)
present these trends in Figure 3a). In Figure b)) observe
0.8
0.
erfor rate
0.6
0.6
0.4
0.0
Aficc
Europe
Biicc
Afria
Oceania
Africa 2013
Afric 2016
afrcc
2006
2007
2007
2011
2011
2017
0.0
class number
Figure 3: For DenseNer ERM, spatiotemproal intersectionality (left) and performance by class (right)
We take the perspective of an analyst evaluating prediction models for land usage, based on data collected during 2002-2013. The FMoW dataset provides fertile grounds for demonstrating our method it includes natural distribution shifts [53), both spatial and temporal. In particular, we demonstrate model robustness on out-of-distie dist-itiiittiinn samples collected in 2016-2018. On validation data collected during 2002-2013, we first evaluate model performance on subpopulations defined across metadata on satellite image, which consists of (subsets of) (longitude, latitude, cloud cover, region, year) and the label Y. Then, we observe how our procedure selects models that perform well "in the future" without requiring dutto--distrbbutinn data.

---

We examine range of different models trained on the FMoW-WILDS training set (collected in 2002-2013, n =7,,663) which fall into two broad categories. First, we consider models pre-trained on ImageNet and finetuned on the FMoW training set. These include DenseNet models trained using ERM and the recently proposed invariant risk minimization (IRM) framework [6]. We also study the Dual Path Network-68 (DPN-68) model with connection paths that enable feature reusage and feature exploration proposed by Chen et al. [23]. We use DPN-68 trained on FMoW using ERM as reported in [58]. These models all achieve in distribution (ID) accuracy of ~ 60% on a heldout validation set ("ID val", collected in 2002-2013, n 11,483).
Second, we consider models derived from the recently proposed CLIP model [62], which was trained on large and heterogeneous data sources comprising of 40M image-text pairs using natural language supervision and contrastive losses. The pre- pre-training data for CLIP is 400 times bigger than ImageNet, and Radford et al. [2 have observed that zero-shot applications of CLIP exhibits substantial relative robustness gains over other state-of-the-art methods on natural distribution shifts of ImageNet.
However, on the FMoW in-distribution (2002-2013) validation set, zero-shot CLIP only achieves 19.3% accuracy compared to the 60% accuracy of ImageNet pre-trained models. We thus finetune it using satellite images in the FMoW training data. While finetuning substantially improves ID accuracy on FMoW to 70.2%, the relative robustness gains of the zero-shot CLIP model severely degrade. To address this problem, Wortsman al. [85] proposed a weight-space ensembling method (CLIP WTSE-FT) where they average the network weights of the zero-shot CLIP model and its finetuned counterpart. These ensembled networks have been observed to exhibit large Pareto improvements in both in-distribution and cuttof--iitributiin accuracy, including on the FMoW dataset.
Motivated by the observed robustness gains, we average the network weights 9g of the CLIP Zeroshot model and that of CLIP fine-tuned 0, to generate a new network (1 - - + A01, where À E [0. I] controls how much weight given to the task-specific, fine-tuned model (domain expertise). We select A = 0.4 so that the ensembled model (CLIP WiSE-F7) achieves similar performance as ImageNet pre-trained counterparts on the in-distribution validation data. To further make models comparable with respect to the cross entropy loss, we calibrate the CLIP WiSE-FT model by tuning the temperature parameter so that its average loss on the in-distribution validation set matches the worst average loss of ImageNet pre-trained models (DenseNet ERM). See Appendix B for detailed experimental settings and training specifications.
CLIP WISE-FT
CLIP WISE-FT
ImgNet DPN-68
ImgNet
DenseNet ERM
DenseNet ERM
DenseNet IRM
DenseNet IRM
100%
20%
10%
5%
3%
1%
100%
20%
10%
5%
3%
1%
Subpopulation
Subpopulation
Figure 4. Left: Z = (all metadata); Right: Z = (all metadata, Y). Results are averaged over 50 random seeds with error bars corresponding a 95% confidence interval over the random runs.
We compute estimators of W. (Algorithm T the in-distribution validation data (ID val) using the standard cross entropy loss. In Figure we summarize the estimated worst-case subpopulation performances defined over the entire metadata, across different subpopulation sizes First, we note that all models have comparable in-distribution accuracy of ~ 60% and DenseNet IRM has the best average-case cross entropy loss. However, the worst-case subpopulation performance of the ImageNet pre-trained models is substantially worse compared to that of CLIP WiSE-FT. This gap grows larger as the subpopulation size becomes increasingly small. Evaluations on worst-case subpopulations suggest that CLIP WiSE-FT exhibits robustness against subpopulation shifts; in contrast, average-case evaluations will select DenseNet IRM.
We observe a drastic performance deterioration on tail subpopulations. The inclusion of label information in Z significantly deteriorates worst-case performance, raising concerns about the distributional robustness of all models including changes in the label distribution. In Table T] we present model performances on the out-of-distribution ("future") data collected during

---

ID, 2002-2013
OOD, 2016-2018 Africa Accuracy
Models
Accuracy
Loss
Accuracy
Loss
Africa Loss
CLIP WiSE-FT
0.61
2.78
0.56
2.84
0.38
3.08
DenseNet ERM
0.61
2.78
0.53
3.50
0.33
5.41
DenseNet IRM
0.59
2.44
0.51
2,94
0.31
4.46
DPN-68
0.61
2.75
0.53
3.55
0.31
5.61
Table 1. Model performance ID val and OOD test sets. All models suffer a performance drop on the OOD test in both accuracy and average loss. The performance degradation is particularly significant images from Africa. On the OOD data, CLIP WiSE-FT outperforms other models both in average accuracy/loss and worst-region accuracy/loss.
All models suffer a significant performance drop under temporal distribution shift, particularly on images collected in Africa where predictive accuracy drops by up 20 percentage points. CLIP WiSE-FT exhibits the most robustness under spatiotemporal shift than any other model, as presaged by evaluations of worst-case subpopulation performance in Figure 4
key advantage of our method is the flexibility in the choice Z: the modeler can define granular or coarse subpopulations based on this choice. As defining subpopulations over all metadata can be conservative, we present additional results under Z (region, year) and Z =region, year, label Y) in Appendix B Instead of incorporating labels category, it may be more informative to use the semantic meaning of each class label. We generate natural language description of the labels by concatenating each class label with engineered prompts, and pass it to the CLIP text encoder [62] to generate a feature representation for the label. In Appendix [B.]] we present evaluation results where take the feature vector in place of the label Y when definin Z.
5 Discussion
To ensure models perform reliably under operation, we need to rigorously certify their performance under distribution shift prior deployment. We study the worst-case subpopulation performance of model, natural notion of model robustness that is easy to communicate with users. regulators, and business leaders. Our approach allows flexible modeling subpopulations over an arbitrary variable Z and automatically accounts for complex intersectionaliiyy We develop scalable estimation procedures for the worst-case subpopulation performance (2) and the certificate of robustness (4) of model. Our convergence guarantees apply even when we use high-dimensional inputs (e.g. natural language) to defin Z. Our diagnostic may further inform data collection and model improvement by suggesting data collection efforts and model fixes on regions of Z with high conditional risk (3).
The worst-case performance (2) over mixture components subpopulations (I) provides strong guarantee over arbitrary subpopulations, but it may be overly conservative in cases when there is a natural geometry in Z 2. Incorporating such problem-specific structures in defining tailored notion of subpopulation is promising research direction towards operationalizing the concepts put forth this work. As an example, Srivastava al. 766 recently studied similar notions of worst-case performance defined over human annotations.
We focus the narrow question of evaluating model robustness under distribution shift; evalua- tion perspective thus inherently limited. Data collection systems inherit socioeconomic inequities, and reinforce existing political power structures. This affects all aspects of the ML development pipeline, and our diagnostic is no panacea. A notable limitation of our approach is that we do not explicitly consider the power differential that often exists between those who deploy the prediction system and those for whom it gets used on. Systems must be deployed with considered analysis of its adverse impacts, and we advocate for a holistic approach towards addressing its varied implications.
10


Reviews:
[{"review_id": "vk47KHw6Rbr", "reviewer": "Reviewer_jVDR", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThe 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.\n\nI 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.\n- 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. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations and potential societal impact are adequately discussed.  ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "JQgOT_cpOJ6", "reviewer": "Reviewer_KadU", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "$\\textbf{Originality}$\n\nTo 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.\n\n$\\textbf{Quality}$\n\nThe work appears technically sounds and proofs of all results are presented in the supplementary material.\n\n$\\textbf{Clarity}$\n\nOverall, 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? \n\nAdditionally, 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.\n\n$\\textbf{Significance}$\n\nEvaluating 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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Nothing comes to mind.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "9wsOWPxkDH0", "reviewer": "Reviewer_e2UX", "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.\nThe 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,\n$$\\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 \n\n$$ W_a(\\theta):=sup_{Q_Z \\sim \\mathcal{Q}_{a}} E[E[\\ell(\\theta(X),Y)| Z] ] $$\n\nwhere $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.\n\nThe 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.\n\nThe 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. \n\nThe 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}$..\n\nUp 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^*$.\nThe paper also includes an empirical illustration of the estimator in practice on two data sets for which worst-case performance is of interest.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nAn 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.\n\nAs 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.  \n\nIn 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.\n\nTheorem 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.\nThere 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.\n\nIn 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$. \n\nTheorem 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.\n\nThere 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. \n\nOverall, I found the idea to be interesting, with significant promise and potential for valuable impact. \n\nMy 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.\n\nUpdates following author response:\n\nThanks for your careful response which provided a great deal of clarity. Please see below for more details.\n\n1)\tMisspecification error in Theorem 1\n\nThanks for the clarification. I believe dropping Assumption 2 and including this additional term would be a small change that improve the result.\n\n2)\tIncorporating heavier-tailed losses\n\nIt 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.\n\n3)\tCorrectness of Theorem 2\n\nYes! My mistake entirely – Apologies. The proof is indeed correct. Thank you for the clarification.\n\nHere 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$. \n\n4)\tDiscussion on Theorem 3\n\nThanks 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. \n\n5)\tConfidence intervals and experiments\n\nThe 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). \n\nI 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.\n\nOverall, 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.\n\nThe 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.\n\n\n6)\tOptimality\n\nIn 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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As discussed above, the work is promising with a potential for positive societal impact in providing fairer applications of ML.\n\nThere 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. \n", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "52dxoPdpYaY", "reviewer": "Reviewer_3a1D", "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.\n\n", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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:\n\n1. **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.  \n\nIdeally, 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.\n\nOne 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. \n\n2. **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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "003UIf_fMv8", "reviewer": "Reviewer_o544", "summary": "\nThis 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.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n\n\nI 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.\n\n\nI 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.\n\nI 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.\n\n\nI 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.\n\n\n\n\nSpecifics:\n\nA 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.\n\nLine 68: what are the implications of this averaging with respect to various loss functions? This feels a lot like 2-fold cross-validation.\n\n86: all subpopulations large than -> all subpopulations larger than\n\n\n131/133: Klein (not Consortium), is the lead author of [27].\n\n156: 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.\n\nEquation 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.\n\nEquation 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?\n\nIt'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.\n\n\nOverall, 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?\n\nGoing 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.\n\n\n167: “the minimizer is given by” Isn’t this a scalar? Is it the minimum or minimizer?\n\nAlgorithm 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.\n\n\n\n229: This is a bit difficult to read.\n\nSection 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.\n\n\nReferences:\n\n\n[1] An Axiomatic Theory of Provably-Fair Welfare-Centric Machine Learning\nC Cousins\n\n[2] Local rademacher complexity: Sharper risk bounds with and without unlabeled samples\nL Oneto, A Ghio, S Ridella, D Anguita", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

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)