Adaptive Sampling for Minimax Fair Classification
Authors: Shubhanshu Shekhar
Greg Fields
Mohammad Ghavamzadeh
Tara Javidi
Venue: NeurIPS 2021 Poster (2021)
Keywords: Fairness
deep learning
active sampling

Abstract: Machine learning models trained on uncurated datasets can often end up adversely affecting inputs belonging to underrepresented groups. To address this issue, we consider the problem of adaptively constructing training sets which allow us to learn classifiers that are fair in a {\em minimax} sense. We first propose an adaptive sampling algorithm based on the principle of \emph{optimism}, and derive theoretical bounds on its performance. We also propose heuristic extensions of this algorithm suitable for application to large scale, practical problems. Next, by deriving algorithm independent lower-bounds for a specific class of problems, we show that the performance achieved by our adaptive scheme cannot be improved in general. We then validate the benefits of adaptively constructing training sets via experiments on synthetic tasks with logistic regression classifiers, as well as on several real-world tasks using convolutional neural networks (CNNs).

Adaptive Sampling for Minimax Fair Classification
Shubhanshu Shekhar
Greg Fields
Mohammad Ghavamzadeh
Tara Javidi
Abstract
Machine learning models trained uncurated datasets can often end up adversely affecting inputs belonging to underrepresented groups. To address this issue, we consider the problem of adaptively constructing training sets which allow to learn classifiers that are fair a minimax sense. We first propose an adaptive sampling algorithm based on the principle of optimism, and derive theoretical bounds on its performance. We also propose heuristic extensions of this algorithm suitable for application to large scale, practical problems. Next, by deriving algorithm independent
for specific class of problems, we show that the performance achieved by our adaptive scheme cannot be improved in general. We then validate the benefits of adaptively constructing training sets via experiments on synthetic tasks with logistic regression classifiers, as well on several real-world tasks using convolutional neural networks (CNNs).
Introduction
Machine learning (ML) models are increasingly being applied for automating the secision-makinng process in several sensitive applications, such loan approval and employment screening. However, recent work has demonstrated that discriminatory behaviour might get encoded in the model at various stages of the MI. pipeline, such as data collection, labelling, feature selection, and training, and as a result, adverscly impact members of some protected groups in rather subtle ways (Barocas and Selbst 2016). This is why ML researchers have started to introduce a large number of fairness measures to include the notion of fairness in the design of their algorithms. Some of the important measures of fairness include demographic parity (Zemel et al. 2013), equal odds and opportunity (Hardt et al. 2016; Woodworth et al. (017), individual fairesss (Dwork al.) 2012), and minimax fairness (Feld) man et al. 20155). The minimax fairness is particularly important in scenarios in which is necessary to be close possible to equality without introducing unnecessary harm (Ustun et al.) 2019).
These scenarios are common in areas such as healthcare and predicting domestic violence. A measure that has been explored to achieve this goal is predictive risk disparity (Feldman al. 2015 Chen et al. 2018 Ustun et al. 2019). Instead of using the common approach of putting constraints on the norm of discrimination gaps. Martinez et al. (2020) has recently introduced the notion of minimax Pareto fairnes.. These are minimax classifiers that are on the Pareto frontier of prediction risk, i.c., no decrease the predictive risk of one group is possible without increasing the risk of another one.
In this paper, we are primarily interested in the notion of minimax fairness in terms of the predictive risk. However, instead of studying the training phase of the ML pipeline, our focus is on the data- collection stage, motivated by Do and Gebru (2019) and Holstein et al. (2018). In particular, we study the following question: given finite sampling budget, how should learner construct training set consisting of elements from different protected groups in appropriate proportions to ensure that a classifier trained this dataset achieves minimax fairness?
Our work is motivated by the following scenario: suppose we have to learn ML model for performing a task (e.g., loan approval) for inputs belonging to different groups based protected attributes, such
Electrical and Computer Engineering Department at UCSD ((shstekttagrriildds.avviii @ucsd.edu) 1 Google Research (ghavamza @ @googl..cmm
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

as race or gender. Depending upon the distribution of input-label pairs from different groups, the given task may be statistically harder for some groups. Our goal to ensure that the eventual ML model has optimal predictive accuracy for the worst-off group. We show that, under certain technical conditions, this results in model with comparable predictive accuracy over all groups. One approach for this would be to train separate classifiers for each group. However, this is often not possible as the moou--membrrship information may not be available at the deployment time, or it may be forbidden by law to explicitly use the protected characteristies as an input in the prediction process (Lipton) iet al. 2017]] $ 1). To ensure having a higher proportion of samples from the harder groups without knowing the identity of the hard easy groups apriori, we consider this problem in an active setting, where a learner has to incrementally construct a training set by drawing samples one at a time (or batch at a time) from different groups. Towards this goal, propose and analyze an adaptive sampling scheme based on the principle of optimism, used in bandits literature (e.g., [Auer et al. 2000)) that detects the harder groups and populates the training set with more samples from them in an adaptive manner. We also wish to note that bias in ML has multi-faceted origins and that our work here addresses dataset construction and cannot account for bias introduced by model selection, the underlying data distribution, or other sources as discussed in Hooker (202I). 1). /urrehh and Guttag] (2019). We also endeavor to ensure minimax fairness, but in some contexts another notion of fairness, such as those mentioned above, may be more appropriate or equitable. In general, application of our algorithm is not guarantee that the resulting model is wholly without bias.
Our main contributions are: 1) We first propose an optimistic adaptive sampling strategy, Aopt. for training set construction in Section B] This strategy is suited to smaller problems and admits theoretical guarantees. We then introduce a heuristic variant of Aope in Section that is more suitable to practical problems involving CNNs. 2) We obtain upper bounds the convergence rate of Aopt. and show its minimax near-optimality by constructing a matching lower bound in Section [3.]] 3) Finally, we demonstrate the benefits of our algorithm with empirical results on several synthetic and real-world datasets in Section 5
Related Work. The closest work to ours is by Abernethy et al. (2020), where they propose an e-greedy adaptive sampling strategy. They present theoretical analysis under somewhat restrictive assumptions and also empirically demonstrate the benefits of their strategy over some baselines. We describe their results in more detail in Appendix C.T, and employ the tools we develop to analyze our algorithm perform thorough analysis of the excess risk of their strategy under a much less restrictive set of assumptions and to show some necessary conditions on the value of their exploration parameter, We find comparable empirical results for both algorithms given sufficient tuning of their respective hyperparameters, we report some of these results in Section 5 and compare the algorithms in Appendix C In another related work, Anahideh al. (2020) propose fair adaptive sampling strategy that selects points based on a linear combination of model accuracy and fairness measures, and empirically study its performance. These results, however, do not obtain convergence rates of the excess risk of their respective methods and only offer implementations for small-scale datasets.
The above results study the problem of fair classification in an active setting and target the data- collection stage of the MI. pipeline. There are also works that take a passive approach to this problem and focus of the training phase of the pipeline.AAgarwal Agarwal et al. (2018) design a scheme for learning fair binary classifiers with fairness metrics that can be written as linear constraints involving certain conditional moments, This class of fairness metries, however, do not contain the minimax fairness measure. Diana et al. (202T) propose a method for constructing (randomized) classifiers for minimax fairness w.r.t. the empirical loss calculated on the given training set. Similarly, Martinez et al. 2000) derive an algorithm for learning a Pareto optimal minimax fair classifier, under the assumption that the learner has access the true expected loss functions. Thus, the theoretical guarantees Diana et al.) (2021) and Martinez et al. (2020) hold under the assumption of large training sets. Our work, in contrast, constructs the training set incrementally (active setting) from scratch while carefully taking into account the effects of the finite sample size. Finally, we note that the data-collection strategies proposed in our paper can, in principle, be combined with the training methods presented in Martinez et al.) (2020) and Diana et al. (2021) to further guarantee the (minimax) fairness of the resulting classifier. We leave the investigation of this approach for future work.
Besides data-collection and training, there have been studies in the fair ML literature on other aspects of the ML pipeline, such as pre-processing (Celis et al. 2020), learning feature representations (Zemel et al. 2013). post-procsssing (Hardt et al. 2016)), and model documentation (Mitchell et al. 2018). We refer readers to a recent survey by Cattnn and Haas (020) for detailed description of these results.

---

2
Problem Formulation
Consider a classification problem with the feature (input) space X, label set V and a pro- tected attribute set Z {21,-.., 2m For any = Z, use (2 y) as shorthand for 2xy (X I, Y = y Z = 2) to denote the feature-label joint distribution given that the pro- tected feature value is Z = 2. We also use E.[-] as a shorthand for the expectation w.r.t. P.. A (non-randomized) classifier is mapping f X + V, which assigns label y E y to every feature I E X. For a family of classifiers F c yit, a loss function & F: x X x y + R, and a mixture distribution over the protected attributes E Amm we define the x--pptmal classifter fx as
fx E arg
arg min ET ((( = Σ (2) E. ((f. ZE2
(1)
JEF
When π lies on the corners of the simplex Am. i.c., T(2)
for a z E Z, we use the notation f= instead of s.. For ı in the interior of Am- it is clear that the risk of fr on group 2, i.e., E, [e(ST. X, Y) must be larger than the best possible classification loss for Pxyiz=a- In this paper, our goal is to develop an active sampling scheme to find the fair mixture distribution x' in a minimax sense (minimizing the maximum risk among the groups), i.e.,
πT" E. arg min max L(z, == E, 1L,F, XY)]
(2)
TEAm
SEZ
The active sampling problem that we study in this paper can be formally defined as follows:
Problem 1. Suppose F denotes a family of classifiers, l a loss function, n is sampling budget, and O: + Xx x y an oracle that maps any attribute z E 2 to a feeture-labe pair (X,Y) ~ PxYiz== The learner designs an adaptive sampling scheme A that comprises a sequence of mappings (At)==1 with Ae: (X x -)p=1= + Z to adaptively query O and construct dataset of size n. Let Tn. Am denote the resulting empirical mixture distribution over Z, where Tz) = N2 / and Ns.. is the number of times that A samples from P. in n rounds. Then, the quality of the resulting dataset is measured by the excess risk, or sub-optimality, of the on-ootimal classifier J ie.,
R max L (z, fna) max Lx=, ZEZ
2E2
where x² is the fair mixture distribution defined by 2 Hence, the goal of the learner is to design strategy A which has a small excess risk R. (A).
Informally, the algorithm should adaptively identify the harder groups and dedicate larger portion of the overall budget n to sample from their distributions (see Section 2.2 for an illustrative example).
2.1 Properties of the Fair Mixture
As discussed above, our goal is to derive an active sampling scheme that allocates the overall budget n over the attributes E in a similar manner as the unknown fair mixture x", defined by ( Thus, it is important to better understand the properties of л² and the x-optimal classifiers fu. defined by (.. We state three properties of fr and π in this section. We refer the readers to Martinez et al. (2020) for the definitions of Pareto front and convexity discussed in this section.
Property 1. As discussed in Martinez et al. (2020 Section 4), any fx that solves I for a i with <(=) > 0, Vz E 2, belongs to the Pareto front Pz.r of the risk functions (L(z, x)) Aʃ F.
Property 2. We prove in Proposition (see Appendix for the proof) that under the following two assumptions on the conditional distributions =Pz) function class F, and loss function e, there exists unique fair mixture π², whose classifier fx- has equal risk over all attributes Assumption 1.
Z.
The mapping - T22, fz) is continuous for all attributes E 2. Furthermore, if n, V/ E Am are such that π (2)) > v(2) for an attribute E 2, then [(2 < Lz),
The above assumption indicates that increasing the weight of an attribute 2 in the mixture distribution must lead to an increase in the performance of the resulting classifier on the distribution P..
Assumption 2. For any two distinct altributes z' E Z, we must have L(z, J2) < any ft E arg min L(z,
This assumption requires that any optimal classifier corresponding to distribution P. to have higher may not always
risk w.r.t. the distribution Pa. of any other attribute E 2. Note that Assumption 2 hold, for example, if one attribute is significantly easier classify than another.
3

---

Let Assumptions and hold for the conditional distributions {P=} the loss function E, and the function class F. Then, there exists a unique x Am that achieves the optimal value for problem ② and satisfies (21,, = 122,, fx.
Proposition 1.
[ f M
In other words, Assumptions and define a regime where there exists fair mixture æ², wwhose classifier f-- achieves complete parity in the classification performance across all attributes. More- over, Property 1 indicates that fa- also belongs to the Pareto front Pz,F. Therefore, under these two assumptions, the equal risk classifier not only belongs to the Pareto front, but also the minimax Pareto fair classifier (Lemma 3.1 in Martinez et al. 2020). Note that, in general, without Assumption 1, the classifier that attains equality of risk might have worse performance on all attributes than the minimax Pareto fair classifier (Lemmaa 3.2 in Martinez al. (020).
We may show that when both the function class F and risk functions (L.(2.)) =E are convex, fx- is minimax Pareto fair classifier. As originally derived by Geoofrion (1968) and then restated by Martinez et al. (2020) Theorem 4.1), under these convexity assumptions, the Pareto front Pz, is convex and any classifier on Pz.F is solution to ( This together with Property I indicates that the classifier f.- corresponding to the fair (minimax optimal) mixture " is on the Pareto front, and additionally, minimax Pareto fair classifier.
Property 3.
2.2 Synthetic Models
It is illustrative to consider class of synthetic models which we use running example.
Definition 1 (SyntheticModell) of our synthetic model is defined by the set of distributions Pxyız that satisfy the following: PYIz(Y = 1|Z = 2) = 0.5 for both & E 2, and Px Y=v. = ( I2) for all (y, 2) E y x 2. Thus, each instance of this model can be represented by a mean vector μ = (Pyz : y E y, 2 E 2).
Set X' R², y {0. 1}. and Z {u, v). Each instance
The idea behind this class of models is that the 'hardness' of the classification problem for a value of vectors
E 2 depends the distance between μloz and /11.- The more separated these two are, the easier it is to distinguish the labels. Thus, depending on this distance, it is expected that different protected attributes may require different fractions of samples in the training set to achieve comparable test accuracy. To illustrate this, we consider two instances of the SyntheticModell f40u. = (-,,2), Piu- = (2). pov = (-1, 11), and Pio (1, 1). and II. Mo.. (-1.5, 1.5), Miu (1.5--1.5), p4n (-2, 2), and pi: = 22,
trained logistic regression classifier over training sets with 1001 equally spaced values of T (u) in [0, 1]. Figure [ shows the test accuracy of the learned classifier for both attributes (blue and red curves) well their minimum (black curve) for different values of π (u). Since the pair (Jou. (Mi.) is better separated than (Por. /1w) in the first instance, it is easier to classify inputs with Z = than those with Z u, and thus, it requires fewer training samples from P==u than P:=v to achieve the same accuracy. This reflected Figure (left) that shows the best (min-max) performance is achieved (u) 0.23. An opposite trend is observed in the second instance (right plot in Figure D. where the mean vectors corresponding to the attribute Z = are better separated, and hence, require fewer training samples to achieve the same accuracy.
For both model instances,
Synthetic Example
Synthetic Example II
1.0
1.0
accuracy
accuracy
0.8
0.8
Acc(u) Acc(v) min (Acctu), Acc(v))
Acc(u) Acc(v)
0.6
0.6
(Acc(())) Acc(v))
0.5
rt" (u) = 0.23
0.5
n (u) = 0.64
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
r(())
m(u)
Figure 1: The variation of the minimum prediction accuracy over the two attributes 2 = {u, o} with (u) for Instance on the left, and Instance II, the right, of the SyntheticModell.

---

3 Optimistic Adaptive Sampling Strategy In this section, we present our optimistic adaptive sampling algorithm Aopt for Problem 1 Al- gorithm [
contains a simple pseudo-code for Aopt, see Algorithm 2 for a more detailed, formal pode The algorithm proceeds in the following phases:
Phase I. In the initial phase S m |2|, we draw two independent samples from P= Pxy| for each attribute 2 E Z, and add one to the training dataset Dr and the other one to D=. We use Dr to learn common (over all E Z) classifier ft via empirical risk minimization (ERM), The independent datasets {Da, 1m are used for estimating the performance of fe for each E Z.
Phase In each round > m, we choose an attribute 24 according to the following selection rule: if there exists an attribute 2 whose num- ber of samples in D., denoted by Nt,,t, , is fewer
Algorithm 1: Optimistic Adaptive Sam- pling for Minimax Fair Classification.
Input:
n (budget), F (function class),
than t for some input Ç E (0, 1) (Line 5) we set as 2, (LinelB), else we set 24 as the attribute which has the largest upper confidence bound (UCB) (described below) for the risk of the clas- sifier f. (Line(8). Here Tr denote the empirical mixture distribution (over the attributes 2) of De.
l. (loss function), & (forced exploration term)
1 Initialize: D1 0;
{ = 0;
{N [= j=1 0;
2 for I = I,..., n/2 do
3
if 1 S then
When the attribute 2t is selected in Phase 2, the algorithm draws a pair of inde- pendent samples from Ps,, adds one to Dr and the other to D2., and updates No.,t, Tr, and the uniform deviation bound ez (.) (described below) (Lines] to [2]. The updated dataset Dr is then used to learn new candidate classifier ft (Line 13p. Phases 2 and 3 are repeated until the sampling budget is exhausted, i.e., f = n/2 (note that we sample twice at each round).
Phase 3.
2 = 26:
5
else if minzez No,1 < 1 then
2, E arg min,ga Nz.ti
7
else
= arg max_ez Uz(z. f(): // see Equation 4 end
10
Draw two independent samples from Pz.
11
Add the first one to Dj and the second one Dz,;
Calculating UCB. To construct the UCB, we introduce two additional assumptions:
12
Update Nz..1 TH ez (Ne,,);;
13 Learn classifier fo by ERM using D;;
For stating the next assumption, we will use the notations T.(2, f) = R. [e[f, X, Y)] and [(T, f) = -=Ez [2)) f) for any f E F, E 2 and π E A...
end Output: knf2 and fm/2
Assumption 3. There exist positive constants En. C > 0 such for any function f E F and any Am. with x (2) > O, Az 2, if we have [( f) S [(M, fx) + e, for some O < < cg, then (=)) x f) - L[2,, f=)1 S 2Cc, Vz E 2.
Assumption iis stated in abstract terms, so Example describes a problem for which it holds.
Example 1. Consider the binary classification problem, with X' = [0. 11ah and y = {0. 13 and 2 = fzi..... 3. J. Let F be the given family of classifiers f X - y. and introduce d(fi, u([fi * fe)), where μ is the Lebesgue measure on X. Assume that the marginal distributions Px|z== all x E Z admit densities V2 with respect to satisfying C1 S vz(x)) S for all x E X. Note that this is a version of the strong-density assumption used prior works in classification, such as (Audberrt and T T'yyaakov] 2007 Definition 2.2). Then, for the for loss, we observe that the expected loss between any two F1, J2 satisfies C,d(f1, f2) I J1) 12), S C2).
As a result of this, for any π E Am and f E F. we have fx) < L(TTf)- - - L(T, S C2d(f, fa). Therefore, if it is known that L(T,)) L(T, fx) S 6, then we can conclude that we must have d(f. fn) < c/C,. Hence, by the strong-density assumption on Px z=z we have that x {=2)x x [I(z,)) - T.(2, fx)] < x C=)(f.{=) & (C2/Ci)e = 2Ct.
Our final assumption is standard uniform convergence requirement which is satisfied by many commonly used families of classifiers (several examples are detailed in Remark [].
Assumption 4. Let E [0, 1] be a confidence parameter. For each z E Z. there exists a monotoni- cally non non-increasing sequence, {e,(N, F,8)= N 2 1}. with lim +0o eg (N, F, 8) = 0, such that the following event holds with probability at least 1 0/2:
5

---

= u
f) -) s scNN),
sup
let
ZEZ N=1
where [x( := N Ei= (S, x Y! A2 E 2, with (x!") Y y!") being i.i.d se- quence of input-label pairs from Pz.
N
In what follows, we will drop the and 8 dependence and refer to eg (N, F. 8) as e, (N) for all 2 E 2 and N 2 1. Given an appropriate sequence of ez (N),, we construct the UCB for the risk function L2, f..). defined by Equation (2), with the following expression:
ft)
1
Σ (f,,z, + ea (Na,)) +
2C
Σ ==((')e>>NNN E'EZ
(4)
D=
(2)
(M.9)ED,
Where C' is the constant described in Assumption [ The first term on the RHS is the empirical loss of the learned classifier at round l on attribute = 2, so by Assumption the first two terms of the RHS of Equation 4 give a high probability upper bound on Liz, ft), the expected loss of fr conditioned on Z = 2. The third term then provides an upper bound on the difference [L fx,) L(z, fe)l and so altogether this provides the desired UCB the expected loss of the n, optimal elassifier attribute
Z 2. The form of the third term is due to Assumption 3 and is discussed in detail in Appendix [.]
3.1 Theoretical Analysis
In this section, we derive an apper-bound on the excess risk (Aop)) of Algorithm 2 We also
show that the performance achieved this algorithm cannot in general be improved, by obtaining an algorithm independent lower-bound on the excess risk for particular class of problems.
Upper Bound. We begin by obtaining an upper bound on the convergence rate of the excess risk of Appt. the proof of this result is in Appendix B.1
Theorem 1. Let Assumptions 3 hold and define Tuin == mingez IT" (z). Fix any A such that Tuin 22 < A < Tmin- Suppose the query budget n is sufficiently large, as defined in Equation 19 in
Appendix B. Then, with probability 6, the excess risk of Algorithm Sachhmmmaeec Zean be upper-bounded as
M -²= ( ( IZ|C
Ru(AApp = max [m,, - ZE2
max BE2
(Na))))
(5)
Tiin
where M = fn=, V2 E Z (see Proposition 1 and NA = n (2 - A).
Remark 1. The uniform deviation bounds, e₂ (N), defined in Assumption Aand the bound on the excess risk of Algorithm (see Equation 5) can be instantiated for several commonly used classifiers (function classes F) to obtain an explicit convergence rate in n. If has a finite VC-dimension, dy then a suitable deviation bound is e, (N) = 2 (2dvc log (2a8/dve) + 2 log (2N=x1121/36)) /N, where here is the numerical constant. And F has Rademacher complexity R.,, we can choose ez (N) = 22R + Vlog (N²=²12/36) /N. Furthermore, with these uniform deviation bounds and if Rr is O (n )) for some a > 0, then we obtain excess risk bounds of
(n ( 1 dvc
(Aps)) 0 12|C Tinin
for the VC-dimension and Rademacher cases, respectively. These conditions on F are satisfied by several commonly used classifiers, such as linear, SVM, and llyte perceptron.
Remark 2 (Analysis of c-greedy). Abernethy et al. (002)) only analyze the greedy version (i.e., e = 0) of their e-greedy sampling strategy with [2] = 2, and show that at time n, either the excess risk of O maxxez / (2dvc((oF) log(2/8)/ or the algorithm draws a sample from the attribute with the largest loss. However, due to the greedy nature of the algorithm they analyzed, there are no guarantees that N_,, Mn.), and thus, in the worst case the above excess risk bound is O()). We show in Appendix( employed to study their e- e-greedy strategy. In particular. we obtain sufficient conditions on under which the excess risk of e-greedy converges to zero, and the rate at which this convergence occurs.
the techniques we developed for the analysis of Algorithm 2 can be suitably
Remark (Comparison between Augt and c-greedy). Aops holds two primary advantages over greedy, these are discussed in detail in Appendix but briefty Aopt has superior risk guarantees, by a constant factor. And both algorithms depend on tunable parameters: C for Apgs and e for e-greedy, but Augt is far more robust to the choice of parameter. Figure 9in Appendix([illustriii case where poor choice of can prevent e- greedy from converging to the optimal mixture distribution for any number of samples. This robustness makes Aopt easier to employ in practical settings.

---

Lower Bound. Let Q = (,,F, fo1) denote the class of problems where μ E .M is an instance of the SenthettcModel1 described in Section F is the class of linear classifiers in two dimensions, and for is the 0- 1 loss. For this function class F. ez (NV = O VoV/oo /lg(NN)/N) for E = {u, v). which implies that the excess risk achieved by both Aopt and c-greedy strategies is of O (Vlog()/mm) We prove in Appendix D that this convergence rate (in terms of n) cannot in general be improved by showing that maxqeQ e Eq [Rn (4)] = Ω (1/vn).
4 Heuristic Extensions
We show in Appendix B.I.1 that if the uniform deviation bounds, e. (N), can be chosen decrease to zero sufficiently quickly as N increases, then we can omit the C dependent third term in Equation (4) and still attain the same regret bounds given in Theorem | The resulting two-term UCB is then only the high probability upper bound on L.2,, fe). We will use this UCB as the basis for several practical modifications to our optimistic adaptive sampling strategy. First we note that in UCB based algorithms the confidence bounds necessary to attain theoretical results often do not produce optimal empirical results see, for example, Section 6 in SSiinias et al. (2009). So, following standard practice, we introduce a hyperparameter, co, in Equation (6) below, which we can tune to optimize the exploration/exploitttion trade-off.
Practical applications of our strategy run into two further challenges. As described in Section 3 Aspt requires re- training the classifier in every iteration. While this can be implemented in small problems, it becomes infeasible for problems involving large models, such as CNNs. Also, as noted in Section 2. for data where one attribute is significantly easier than the other, Assumption 2 may not hold. In this case may not be beneficial to continue to sample from the attribute with the largest loss. To address these issues we present a heuristic variant of Algorithm 2
For the first challenge we make the following modifications to Algorithm 2 1) We expand Phase to no rounds, 2) at each subsequent round we draw two batches of size by from the chosen attribute, 3) instead of re-training from scratch each round, we update the previous model, fi-1. and 4) instead of training to convergence, we perform one gradient step over the entire accumulated training set, Dz.
To address the second challenge we modify the UCB by adding a term based on the Mann- Kendall statistic (Mann 1945) (Kendall 1948) which, for time series data (X,) is given by
S S= Σx= 2j= sgn (X, X:) This is designed to identify monotonic upwards or downward trends in time series. We calculate the statistic for each attribute, and denote S... for the accuracy of the classifier, f., on the attribute's validation set, Dz,, over time. Intuitively, this is tracking whether training on additional samples from an attribute is improving the classifier's accuracy on that attribute. We incorporate the statistic into the UCB as follows:
fa) = D.
Σ Eff,,, + VN..1
+
S.. Vvar(S..)
(6)
(R.D)ED.
to incentivize the algorithm to sample attributes on which accuracy is increasing. C1 is a free parameter controlling the importance of per-attribute loss trends. We note that the general ability to modify the UCB in this manner is a strength of our algorithm, as it allows for a great deal of interpretability and adaptability in practical applications.
The parameters co. C1, no. and by are chosen based on the specific problem and available computa- tional resources. We describe our selection of these terms Appendix E In the experiments we will refer to the variant of this algorithm with c = 0 as Aope, and the variant with > 0 as Aope
5 Empirical Results
We evaluate the performance of our proposed active sampling algorithm Aopt on both synthetic and real datasets, and compare it with the following baselines: 1) e-greedy scheme of Abeerethy ctt al. (2020). 2) Greedy scheme, which is equivalent to e-greedy with e = 0, 3) Uniform, where an equal number of samples are drawn for each attribute, and 4) Uncurated, where samples are drawn according to the natural distribution of the dataset. We note that, for some datasets, the natural distribution is uniform, for those we omit the results for the Uncurated scheme.
We will make the code for these experiments available in the supplemental materials. All experiments were run for multiple trials-the number of which is indicated in the results-and we report the average over trials with shaded regions on plots indicating +1 standard deviation. Experiments for image datasets were run on single GPU provided by Google Colab or other shared computing resources.
7

---

Synthetic Model
|
Synthetic Model II
Asp!
0.8
E-Greedy
0.6
Empiiicil
0.4
Anpt
0.2
Grondy
0.0
Empinical
n
Figure 2: The figure shows the convergence of TT(u) ()) for the three algorithms Aogt. c-greedy (with
c= 0.1) and Empirical (i.e., c-greedy with 0), to the optimal value x' of the Syntheti PratheticMode11
x=(2) (u) for the two instances
cModel1 introduced in Section 2.2
Synthetic Dataset. In this experiment, we compare how the (u) returned by the different algo- rithms converge (u) for the two synthetic models introduced in Section 2.2 with JF chosen the family of logistic regression (LR) classifiers. Since the feature space is two dimensional, we use the version of Aopt, f-greedy, and Empirical schemes in which train (from scratch) the classifier in each round. For Aopt. we use UCB given in 6 with on = 0.1 and for e-greedy, we use e = 0.1. These values of co and are selected via grid search. Figure shows how n. (u) changes with for the three algorithms averaged over 100 trials. As ex- pected, the algorithms with an exploration component (i.e., Aopt and e-greedy) eventually converge
to the optimal T (u) value in both cases, whereas the Empirical scheme that acts greedily often gets stuck with wrong mixture distribution, resulting high variability in its performance.
Adult Dataset. For the remaining experiments we find that, for properly tuned values e and co- both Aopz and e-greedy attain comparable minimum the purpose of clarity, see Appendix [C for a detailed comparison of the two algorithms. We now analyze the performance of the remaining algorithms Repository (Dua and Graff] 2017) that is commonly used in the fairness literature: the Adult dataset. low dimensional problem, we use LR classifiers and the exact version of each sampling algorithm, where the optimal classifier is computed with each new sample.
error. So omit the e-greedy results for
dataset from the UCI MI.
We be white men, non-white men, white women, and non-white women. The minimum test accuracy over all attributes at each iteration is displayed in Figure Gal Each sampling scheme approaches 80.5% accuracy as sample size grows, this matches the results achieved under the LR algorithms reported in Table 4a) in Martinez et al. (2020). This is the maximum accuracy an LR classifier can achieve on the white male sub-population in isolation and so additional sampling, or other fairness algorithms, cannot improve this performance in minimax sense. We do note, however, that the adaptive algorithms hold sizable advantage over Unifort at small sample sizes.
Image Datasets. We also compare the performance of the different sampling schemes on larger scale problems and more complex hypothesis classes. To this end we use three image datasets: UTKFace (Zhang et al., 2017). FashionMNIST (Xiao et al.) 2017). and Cifarl0 (Krizhevsky and Hinton 2009) with CNNs. We use the heuristic variants the Aopt, with 0 O, and Greedy algorithms with batch sizes of 50. The CNN architecture, data transforms, and further algorithm parameters are detailed in Appendix
Adult Income
0.80
FashionMNIST
Accuracy
(Tshirt,Shirt)
0.79
(Pullover, Coat)
Greedy
(Trousers, Dress)
Agpe
0.77
Uniform
(Sandals, Bag)
Uncurated
(Sneakers,Boodk Boots)
0.76
1000
2000
3000
4000
5000
0.1
0.4
n
Proportion of samples
Figure 3: Left: Minimum test accuracy over all attributes for Adult dataset as a function of the sampling budget n, averaged over trials for Adult. Right: Mixture distribution learned by Aopt over 500 training rounds on FashionMNIST.

---

FashionMNIST
UTKFace
0.95
0.95
0.90
0.90
Accuracy
Accuracy
0.85
0.85
0.80
Greedy
0.80
Greedy
0.75
Appt
0.75
Appt
Uniform
0.70
Uniform
Uncurated
0.70
50
100
150
200
250
300
350
400
450
500
0.65
70
140
210
260
350
420
490
560
630
700
t
t
Figure 4: Minimum test accuracy, over all attributes, for both FashionMNIST and UTKFace as a function of the time step I, averaged over 10 trials.
The UTKFace dataset consists of face images annotated with age, gender, and ethnicity. We choose = (Male, [Male,,emale and set 2 to the five ethnicities. The minimum test accuracy. over all attributes, shown in Figure 4b and demonstrates clear separation between the adaptive algorithms and both Uniform and Uncurated sampling. Uncurated does particularly poorly in the low sample regime here, in contrast with the Adult dataset, where Uncurated performed comparably to the adaptive algorithms. This is because, for Adult dataset, the lowest accuracy attribute is over-represented in the dataset with white men 63% of all samples. Whereas, for UTK Face, the accuracy was lowest for Asian people, who are under-represented in the available data at only 14% of all samples.
The other two datasets, FasSionMNIST and Cifar10, were chosen to provide controlled setting to demonstrate the existence of hard and easy attributes on real-world data. For both, we divide the labels into pairs and assign each "attribute". The pairs were chosen according to existing confusion matrices to have pairs that are both easy and hard to distinguish from each other, see Appendix
B for more details.
For FashionMNIST, each pair in Figure Bblis is one attribute and within each pair one item is assigned Y 0 and the other Y = 1. Then single binary CNN classifier is learned simultancously over all 5 pairs. Figure 3b shows the mixture distribution generated by the Aopt sampling scheme, which allocated the vast majority of samples to the (Tshirt, Shirt) and (Pullover, Coat) pairs. This makes intuitive sense, since both pairs of items are qualitatively very similar to each other, and aligns with common confusion matrices which indicate that those items frequently misclassified each other by standard classifiers. Figure (agure/4addipliie dippaass the worst case accuracy for each scheme on FashionMNIST function of time step and shows that both adaptive algorithms outperform Uniform sampling throughout the training process. Finally, Figure 5 shoows the test accuracy on each attribute for both Aspt and Unif orm sampling schemes. Aopt maintains a much smaller spread between the accuracy over different attributes. This equity is particularly desirable from fairness perspective as it ensures no attribute has a large advantage over any other in the sense of expected accuracy. It also validates our assumption that the optimal distribution will tend to equalize the losses across attributes in real world data.
Final accuracy for all experiments, per-attribute accuracy for UTKFace, all results for CIFARIO, and details of the Adult dataset are included in Appendix E. along with results for the German dataset, another UCI ML Repository dataset.
FashionMNIST,
Appt
FashionMNIST, Uniform
1.00
0.95
0.95
Accuracy
Accuracy
0.90
0.90
0.85
(Tshirt, Shirt)
0.85
(Tahirt Shirt)
(Pulloeer, Coat)
(Pulover, Coal)
0.80
0.80
(Trousers, Dress)
(Trousers, Dress)
0.75
(Sandals, Bag) (Sneakers, Boots)
0.75
(Sandals, Bag) (Sneakers, Boots)
0.70
100
150
200
250
300
350 400 450 500
0.70
50
100
150
200
250 300 350 400 450 500
Figure 5: Test accuracy for each attribute in FashionMNIST function of the time step, t, for both Aspt and Uniform sampling schemes, averaged over 10 trials.

---

Attribute
Attribute
0.95
0.56
0.90
0.55
Accuracy
0.54
Accuracy
0.80
0.53
0.75
0.52
Aope+
Aapt+
0.51
0.65
Aopt
Aopt
0.50
0.60
Greedy
Greedy
0.49
0
40
80
120
160
200
120
160
200
n
n
Figure 6: Test accuracy as a function of sampling budget for both attributes from the dataset shown in Fig. averaged over 100 trials.
Empirical results when Assumption 2 is violated.
Finally, we consider the case where our assumption unique, risk equalizing mixture distribution may not hold. The practical effects of this situation be seen in the Adult dataset where additional samples of the white male attribute show diminishing returns, while other attributes can attain higher accuracy given more samples. In such scenario, each adaptive algorithm will continue to select samples mainly from the worst case group despite this granting little improvement performance.
To evaluate this scenario we introduce second syn- thetic data model: an instance of Syntheti cMode12 is illustrated in Figure 7 and specified in detail in Definition 4 in Appendix E In this model we create one attribute, shown in red, which allows relatively small maximal accuracy that can be attained with few samples. In contrast, the blue attribute can be classi- fied with high accuracy given few sample, as the bulk of its mass is in the central, separable clusters shown in the figure. But classification of this attribute also benefits from many additional samples the sparser regions in the top left and bottom right are explored. In this setting, constantly sampling from the attribute with the lowest empirical accuracy is inadvisable as additional samples of the red attribute cannot increase its accuracy. while additional samples of the blue attribute can increase its accuracy.
Synthetic Model II
2
-4
-3
2
1
2
4
Figure
An instance of SyntheticModel 12wth attribute Z shown in red and Z = v shown in blue.
7:
We compared the performance of Aop the heuristic variation of our algorithm with a trend-based statistic included, Aept. and Greedy on portheetcModelle Figure shows three algorithms achieves similar minimax accuracy and performs worst attribute Z u, shown in red in Figure 7 But Aope + achieves points higher average accuracy than both Greedy and Aope with the original UCB on the other attribute, Z = This demonstrates that the additional term in the A + UCB is effective at recognizing when the hardest group is not benefiting from additional training samples and redistributing them more effectively.
shows the results, each the
Conclusion
We considered the problem of actively constructing training set in order to learn classifier that achieves minimax fairness in terms of predictive loss. We proposed a new strategy for this problem (Aapz) and obtained theoretical guarantees on its performance. We then showed that the theoretical performance achieved by Appt. and e-greedy (Abernethy et al. (020)) cannot be improved in general, by obtaining algorithm independent lower-bounds for the problem.
Our experiments demonstrated that adaptive sampling schemes can achieve superior minimax risk [Fig. 3al Fig. and smaller disparity between per-attribute risks [Fig. 5) compared both uniform and uncurated schemes. The results in Fig. 2 show the necessity of exploration, as purely greedy algorithms can converge sub-optimal mixture distributions. And finally Fig. shows the versatility of our general UCB- based strategy in its ability to readily incorporate new terms to accommodate the practical challenges posed by Our theoretical results rely on the existence of a unique risk equalizing mixture distribution x², condition that may not always hold. Thus, an important future work relax this assumption, and to design and analyze algorithms that identify pareto optimal mixture distributions that achieve minimax fairness. Another important direction to derive and analyze active sampling strategies for other fairness measures.
problems.
10


Reviews:
[{"review_id": "mH8Hvds_Eed", "reviewer": "Reviewer_3tnc", "summary": "This paper considered solving the minimax fair classification by adaptively constructing a training sets, based on the principle of optimism in the face of uncertainty. The authors provide a simple and straightforward analysis on the performance of ERM on constructed training sets, and empirically show the performance on synthetic and real dataset.\n", "questions": "", "limitations": "", "rating": 4, "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": "Overall the main idea of the paper is clear to me. However, I have several questions on the algorithm design, theoretical analysis.\n\nGeneral Questions:\n\n1. The algorithm assume we have an access to the oracle $P_z$, but in practice we only have an access to a batch of samples, which cannot guarantee we can always get independent samples from $P_z$ (for example, we requires the amount of samples from $z_i$ larger than the total amount of samples that have attribute $z_i$ from the dataset), how can we deal with such scenario?\n\n2. What’s $\\pi$ in the definition of $e_z$ (Line 226)? Is it related to $\\pi_z$? I don’t see any of clarification throughout the whole Sec 3.\n\n3. It should be better mentioned that $\\mathcal{D}_{z}$ is used for cross-validation in Sec 3 and algorithm box.\n\n4. I would like to ask how general is the Assumption 3. The derivation heavily depends on this Assumption and I don’t feel it quite natural. It assumes a reverse of the triangle inequality, but can there be cases that each component is large but have different signs so the sum is small? Can such assumption be replaced with local smoothness and convexity of $f$ and $l$? Such assumption seems more general to me.\n\n5. I would gonna argue that the lower bound is not “matching”, especially the upper bound is linear in $|\\mathcal{Z}|$. The lower bound in $n$ is not surprising, as for generalization an $\\Omega(n^{-1/2})$ minimax error is unavoidable. I expect to know whether this $|\\mathcal{Z}|$ is unavoidable, or is just an artifact introduced by the proof strategy.\n\nSome questions regarding the proof and proof organization.\n\n6. In Line 602, the authors say that the right inequality is due to Lemma 1, but here  $z$ is in the underrepresented group, while Lemma 1 discuss the $z$ in the overrepresented group (see Line 569 and 592), can the authors make a clarification on that, as it’s critical to the proof?\n\n7. I suggest the authors refine the proof in the Appendix. Its’ pretty hard to check when the proof is not well-organized. For example, in Line 603-610, I don’t quite see why by definition $t_0 \\geq \\pi_{\\min} n$ until I see $t_0\\geq N_{z_0, t_0}\\geq \\pi_{\\min} n$ and aware of the final inequality is due to forced exploration. In fact, the authors does not emphasize the need of forced exploration in any place.\n\n8. Also, the introduction of terms in (11) and (12) is not so intuitive and easy to follow. It’s not clear where and why should we introduce $A$ (and $A_i$ in the subsequent part), and why we need $n_0 > \\pi_{\\min}^{-2}$. It’s better to give more explanation to the potential readers.\n\n9. In Line 640 why $\\mathcal{Z}_{u}$ could be empty? Please make the claims as accurate as possible.\n\n10. Is $N$ in Line 687 $N_A$ and no $A$ in the right side?\n\nMinor Questions on Experiments.\n\n11. I feel there are some gaps between theory and experiments. It’s understandable to select some confidence parameters when conducting neural nets experiments as the function class complexity is generally not so applicable, but for me it does not support the theoretical results any more.\n\n12. I would also like to ask when we don’t have the oracle $P_z$,what can we do instead. This is the real scenarios we face in practice. As the authors conduct some experiments with real world dataset, I want to mention that the target for such scenarios is totally different from the problems the authors have described.\n\nOverall, this paper is an adaption of the popular UCB method to the minimax fair classification tasks. The main technical difficulty is that, adding new samples from one attribute will affect the performance on all of the attributes, which is different from the bandit setting. The authors address this issue with several new assumptions to prove the optimism and back to the bandit style proof. Assumption 1 is sound, however, assumption 2 is quite restricted and the authors only provide a heuristic fix without any further theoretical justification. Assumption 3 is quite strong without intuitive clarification. The proof is not well-organized and may have some potential issues. Moreover, the algorithm is somehow idealized in the sense that it assumes the data generating process oracle, which is probably not a good setting in practice. Based on the reasons I mentioned above, I tend to reject this paper.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have properly addressed them.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "XN85Y-AanyI", "reviewer": "Reviewer_Br95", "summary": "The paper exploits active sampling methods to construct a training dataset that yields fair classifiers in a minimax sense: minimising the maximum risk of any of the groups of interest. The proposed method constructs a dataset iteratively by drawing samples from the group with highest upper confidence bound (UCB) for the predictive risk of the current classifier. At each iteration, the classifier is retrained (updated) on the extended dataset, and the process is repeated until a sampling budget is exhausted. The authors provide theoretical bounds for the convergence of the algorithm, which are proven to be tighter than those of previous $\\epsilon$-greedy approaches.", "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": "[Overall]\n- *Originality*: The proposed methods and theoretical results are, to the best of my knowledge, novel.\n- *Quality*: The paper seems technically sound, and the theoretical analysis is thorough with interesting results. The experimental results, however, are less encouraging. \n- *Clarity*: While the paper is well written, the main contributions are not made immediately obvious. Most of the promising results are hidden in the appendix.\n- *Significance*: Fairness is a topic of great interest in the machine learning community, and I believe the proposed active sampling approach is a promising avenue to tackle it.\n\n[Strengths]\n- I find the idea of combining minimax Pareto fairness with active sampling quite promising.\n- The theoretical analysis is thorough and the convergence results are a valuable contribution to the community.\n- I appreciate that the authors provided their code in a fairly accessible format.\n\n[Weaknesses]\n- The experimental results seem weak. The proposed method does not seem to outperform the previous simpler $\\epsilon$-greedy approach and the other baselines, uncurated and uniform, are rather weak.\n- The text is well written but not particularly easy to follow. Given the interesting theoretical results, I think the paper would read much better if the focus was put in the theoretical development—with at least sketches of the proofs in the main text—rather than on the experimental results which are not as promising or revealing.\n\n[Further Comments and Questions]\n- In Figure 7, the performance of $\\mathcal A^+_{opt}$ seems quite promising. Why is it not included in the other experiments?\n- I think Assumption 3 should also be stated on the main text.\n- I believe there is a typo in line 232 that probably should read '[...] the performance achieved *by* this algorithm cannot in general be improved [...]'.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors did not address any potential negative societal impact in their paper. However, given that their methods strive to achieve fairness, I would imagine the societal impact would be mostly positive. The authors do address some of the limitations of their approach, and I do not have anything to add to their considerations.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "WR28aC5OY83", "reviewer": "Reviewer_iKc6", "summary": "This paper proposes an adaptive sampling scheme to construct the training dataset which allows us to learn classifiers that are fair in a minimax sense. They proved theoretical results on the excess risk of their algorithm, and also proposed heuristic extensions of the algorithm to be applicable to real-world large scale problems. They validate their algorithm on a series of synthetic and real-world datasets, showing an improved performance over empirical/uniform sampling schemes, which also verified their theoretical findings. ", "questions": "", "limitations": "", "rating": 8, "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": "Overall this is a very well-written paper. I especially like the results that the minimax optimal mixture distribution yields a classifier that has equal risk among all attributes. The theoretical analysis is convincing, showing the quality of the solution from Algorithm 1 via the excess risk measure. The supporting examples well illustrate the validity of the assumptions. They also give practical suggestions on what to do when certain assumption is violated, and how to properly modify the algorithm to be suitable for real-world large-scale problems. \n\nI have a question on Theorem 1, where eq. (5) has this term e_z(N_A). Since A could be any value between \\pi_{min}/2 and \\pi_{min}, can we choose an optimal A such that the term e_z(N_A) will be the smallest for all z? Also in practical implementations, what is the form of e_z(N) that is used in the UCB (4)?\n\nIn Eq. (6), is S_{z_t} calculated as the Mann-Kendall statistic of the accuracy of f_t? That is, replacing the terms X_i, X_j in the expression of S by Acc(f_t)? Does the c_0 term of Eq. (6) account for the uniform deviation term e_z of Eq. (4)? Having var(S_{z_t}) in the denominator suggests that we should draw more samples for attributes whose var(S_{z_t})  is small. But if the accuracy for a certain attribute is already very good (cannot be further improved by drawing more samples), in which case var(S) would be small, drawing more samples for such attributes seems to be counterintuitive?\n\nMy major concern in the experimental section is that the performance of \\epsilon-greedy seems to be very close to A_{opt}. In Fig. 2 (left), \\epsilon-greedy converges even faster (much faster). In Figs. 3 and 4 the greedy algorithm also has a similar performance to A_{opt}. Do these results suggest that \\epsilon-greedy and A_{opt} have comparable performance in reality? Can you provide guidance on which one to use?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No. This work is mostly theoretical work on how to design a sampling scheme to drive fair classification. I do not think it is related to any negative societal impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "Hv1_uk-mqOf", "reviewer": "Reviewer_LCx4", "summary": "This paper proposes a sampling algorithm to construct the training dataset adaptively, the goal is to learn a classifier that can attain minimax fairness measured by the predictive loss. The authors show that the proposed algorithm has nice theoretical properties (upper bound on the regret, and this upper bound can not be improved).", "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": "I enjoyed reading the introduction and the problem formulation part of this paper. Nevertheless, I encounter difficulty to digest section 3 which contains the main contribution of this paper:\n\n- The paper lacks some intuition on the sampling algorithm. Can the author provide some intuitive explanation on why Algorithm 1 may work?\n- In line 226, why does the expression involve n but not N?\n- What is the query budget n so that Theorem 1 is valid (say, for Adult and German dataset and a logistic/SVM classifier)? \n- Empirically, it is difficult to be convinced that A_opt is a better algorithm than the eps-greedy method of Abernerthy et al. (2020). Apart from the theoretical difference in Remark 1, can the authors provide any justification to use A_opt? \n\n\nMinor comments:\n- In line 199, xi is in (0, 1) but in line 218, xi is in (0.5, 1)?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper is on fairness, so I encourage the authors to discuss some risk, limitations and promise of the A_opt sampling algorithm.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: While the review scores are a bit divergent (one reviewer scored 4 while others gave greater than or equal to 6), the reviews are overall positive, and some of the major concerns regarding the organization of theoretical guarantee and the advantage of ${\cal A}_{opt}$ are properly addressed during the discussion period. 

Re. the access to the oracle: I believe this assumption is not very strong in light of practical scenarios, although it would definitely be better if the algorithm does not depend on it. Also, the authors explained in the rebuttal how to react to such challenging scenarios properly. 

Overall I believe this paper is worth being published, given that the theoretical result is further elaborated in the main text as well as the advantage of ${\cal A}_{opt}$ is highlighted with sufficient experimental supports, as the authors promised. 
Decision: Accept (Poster)