Boosted CVaR Classification
Authors: Runtian Zhai
Chen Dan
Arun Suggala
J Zico Kolter
Pradeep Kumar Ravikumar
Venue: NeurIPS 2021 Poster (2021)
Keywords: fairness
tail performance
boosting
ensemble methods

Abstract: Many modern machine learning tasks require models with high tail performance, i.e. high performance over the worst-off samples in the dataset. This problem has been widely studied in fields such as algorithmic fairness, class imbalance, and risk-sensitive decision making. A popular approach to maximize the model's tail performance is to minimize the CVaR (Conditional Value at Risk) loss, which computes the average risk over the tails of the loss. However, for classification tasks where models are evaluated by the zero-one loss, we show that if the classifiers are deterministic, then the minimizer of the average zero-one loss also minimizes the CVaR zero-one loss, suggesting that CVaR loss minimization is not helpful without additional assumptions. We circumvent this negative result by minimizing the CVaR loss over randomized classifiers, for which the minimizers of the average zero-one loss and the CVaR zero-one loss are no longer the same, so minimizing the latter can lead to better tail performance. To learn such randomized classifiers, we propose the Boosted CVaR Classification framework which is motivated by a direct relationship between CVaR and a classical boosting algorithm called LPBoost. Based on this framework, we design an algorithm called $\alpha$-AdaLPBoost. We empirically evaluate our proposed algorithm on four benchmark datasets and show that it achieves higher tail performance than deterministic model training methods.

Boosted CVaR Classification
Runtian Zhai, Chen Dan, Arun Sai Suggala, Zico Kolter, Pradeep Ravikumar
School of Computer Science Carnegie Mellon University Pittsburgh, PA, USA 15213
{rzhai, cdan, asuggala, zkolter pradeepr)@cs ptteera...eee....derrr....
cmu edu
Abstract
Many modern machine learning tasks require models with high tail performance, Le. high performance over the worst-off samples in the dataset. This problem has been widely studied in fields such as algorithmic fairness, class imbalance, and risk-sensitive decision making, A popular approach to maximize the model's s tail performance is to minimize the CVaR (Conditional Value Risk) loss, which computes the average risk over the tails of the loss. However, for classification tasks where models are evaluated by the 0/1 loss, we show that the classifiers are deterministic, then the minimizer of the average 0/1 loss also minimizes the CVaR 0/1 loss, suggesting that CVaR loss minimization is not helpful without additional assumptions. We circumvent this negative result by minimizing the CVaR loss over randomized classifiers, for which the minimizers of the average 0/1 loss and the CVaR 0/1 loss are no longer the same, so minimizing the latter can lead to better tail performance. To learn such randomized classifiers, we propose the Boosted CVaR Classification framework which is motivated by direct relationship between CVaR and a classical boosting algorithm called LPBoost. Based on this framework, we design an algorithm called O-AAdLLPBoos We empirically evaluate our proposed algorithm on four benchmark datasets and show that it achieves higher tail performance than deterministic model training methods.
Introduction
As machine learning continues find broader usage, there an increasing understanding of the importance of tail performance of models, in addition to their average performance. For instance, in datasets with highly imbalanced classes, the tail performance the accuracy over the minority classes which have much fewer samples than the others. In the field of algorithmic fairness, where dataset contains several demographic groups, the tail performance is the accuracy over certain underrepresented groups that normal machine learning models often neglect. In all these examples, it crucial to design models with good tail performance that perform well across all parts/groups of the data domain, instead of just performing well on average.
Owing its importance. number of recent works have designed techniques to learn models with high tail performance [HSNLIS 18 SKHL20, SRKL20) Maximizing the tail performance is sometimes referred learning under subpopulation shift, the sense that the testing distribution could consist of just subpopulation of the training distribution. Most of the works on subpopulation shift fall into two categories. In the first. also referred as the domain-an -wware setting, the dataset is divided into several predefined groups, and the goal is to maximize the worst-grout performance, i.e. the minimum performance over all the groups number of methods, such as importance weighting [Shi00] and Group DRO SSHH.20) ( SRKL.20 have been proposed for domain-aware subpopulation shift. However, the domain- aware setting is not always applicable, either because the groups can be hard to define, or because the group labels are not available. Thus, in the second category of
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

work on subpopulation shift, also referred to as the groups, and the goal maximize the model'ss performance over the worst-off samples in the dataset. Most previous work on
setting, there are no pre-defined
subpopulation shift [HSNLI8] DNIS HNSS18 LBC+ 20
MHN21 measure the tail performance using the Distributionally Robust Optimization (DRO) loss, which is defined as the model's 's maximum loss over all distributions within a divergence ball around the training distribution. A popular instance is the a-CVaR loss, defined as the model's average loss over the worst E (0, 1) fraction of the samples incurring the highest losses in the dataset.
Naturally one might think of maximizing a model's tail performance by directly minimizing the DRO loss or the a- VaR loss, which has been used by many previous work [HSNLI8 DNI8 [DKR20] However, [HNSSI8] proved the negative result that for classification tasks where models are evaluated by the zero-one loss, empirical risk minimization (ERM) achieves the lowest possible DRO loss given that the model is deterministic and the DRO loss is defined by some f-divergence function. We extend DRO losses
their result to the o-CVaR loss which can be written as the limit of (with more direct and simpler proof due to the specialized case of CVRR). This is very pessimistic result since it entails that there is no hope to get a better classifier than ERM so long as models are evaluated by a DRO (or CVaR) loss. So some previous work [HNSS]8 8 LBC MHN21] proposed to avoid this issue by making extra assumptions on the testing distribution (specifically, that the testing subpopulation can be represented by a parametric model), and changing the evaluation metric correspondingly to something other than f-divergence DRO loss.
In this work, we take a different approach and show that no extra assumption is needed provided that we use randomized models. While the case of general DRO is more complicated, the reason why ERM achieves the lowest possible CVaR zero-one loss in the deterministic case very simple: there exists a linear relationship between the CVaR zero-one loss and the average zero-one loss, so the former is non-decreasing with the latter. For randomized models, however, such a monotonic relationship no longer exists. Note that for any single test sample, the zero-one loss of the deterministic model is either or 1, while the expected zero-one loss of the randomized model is a real number in [0, 1], so that the randomized model can typically achieve lower c-CVaR loss than the deterministic model. In fact, we can prove that if the two models have the same average accuracy, then the a-CVaR zero-one loss of the randomized model is consistently lower than the deterministic one.
Motivated by the above analysis, we propose the framework of Boosted CVaR Classification to train ensemble models via Boosting. The key observation we make is that minimizing the a- a-CVaR loss is equivalent to maximizing the objective of a-oos,, a subpopulation--prrfoon performaacccee counterpart of a classical boosting variant known as LPBoost [DBSTO2). Thus training with respect to the a-CVaR loss can be related to a goal of boosting an unfair learner, which always produces a model with low average loss on any reweighting of the training set, to obtain a fair ensemble classifier with low a-CVaR loss for a fixed a. Note that this is in contrast to the classical boosting, which boosts a weak learner to produce an ensemble model with better average performance. We can thus show that a-CVaR training is equivalent to a sequential min-max game between a Boosting algorithm and an unfair learner, in which the Boosting algorithm provides the sample weights and the unfair learner provides base models with low average loss with respect to these weights. After all base models are trained, we compute the optimal model weights. At inference time, we first randomly sample base model according to the model weights, and then predict with the model. Thus, the final ensemble model is a linear combination of all the base models.
This paper is organized as follows: In Section 2 we provide the necessary background of subpopula- tion shift and CVaR, and show that ERM achieves the lowest CVaR zero-one loss in classification tasks with deterministic classifiers. In Section we show how to boost an unfair learner: we first show that minimizing the CVaR loss is equivalent to maximizing the LPBoost objective in Section 3.1 based on this observation, we propose the Boosted CVaR Classification framework and implement an algorithm that uses LPBoost for CVaR classification in Section 3.2. Then, in order improve computation efficiency, we implement another algorithm called P-Aoaa in Section Finally, in Section 4 we empirically evaluate the proposed method popular benchmark datasets.
1.1 Related Work
Caveats of DRO. DRO was first applied to domain-oblivious subpopulation shift tasks in [8SLL18), in which the authors proved that the DRO loss is an upper bound of the worst-case loss over K groups (group CVaR) for fairness problems. (DNI8) analyzed the convergence rate of
2

---

DRO for the Cressie-Read family of f f-divergence. However, [HNSSI8] showed that minimizing f-divergence DRO over deterministic function classes, with respect the zero-one classification loss. yields the same minimizer that of ERM, provided that the former has loss less than one. [SKHL220) further showed that for highly flexible classifiers (such as many modern neural models) that achieve zero error on each training sample, both empirical average risks and DRO risks are zero, so that the model is not specifically focusing on population DRO objective. [SRKL20] made the related point that the Group DRO objective with respect to the zero one loss is prone to overfit.
Boosting. Boosting is classic algorithm in machine learning dating back to AdaBoost proposed in [Sch90]. See [Sch03] for a survey of the early works. Motivated by the success of AdaBoost, many later works proposed variants of Boosting, such as AdaBoost, [RWSTO5), AdaBooste, (SL09], LPBoost [DBST02]. SoftBoost [RWG07] and entropy regularized LPBoost [WGV08]. There are some previous works that apply ensemble methods to tasks related to subpopulation shift: see [GFB 11] for survey of Bagging, Boosting and hybrid methods for the class imbalance problem, while [IN19 BHL.19 used AdaBoost to improve algorithmic fairness.
2 Preliminaries
In this section we provide the necessary background on subpopulation shift, DRO and CVaR, in the context of classification, which is the focus of the paper. Particularly, will demonstrate that in classification tasks, ERM achieves the lowest CVaR loss, so there is no gain in using CVaR compared to ERM. Then, show that using randomized models can circumvent this problem.
Denote the input space by X, the label space by V, and the data domain by Z = X' x V. We are given dataset { = (Ii.2:)) 1.))) )= that i.i.d. sampled from some underlying data distribution. We assume that any input æ has only one true label y, i.e. for any æ E X there exists E y such that Ply z) 1. Given family of classifiers F, the goal of subpopulation shift task is to train classifier F : X + y E F with high tail performance. Given a loss function E y x y + R. the standard training algorithm is empirical risk minimization (ERM) which minimizes the empirical risk defined as
n R((F= - n Σ ((F(x)))
(1)
Denote the set of minimizers of the empirical risk by F = arg regmingee Rs RF). For classification tasks, the model performance is evaluated by the zero-one loss l0/1(0, y) = 1 (z Although we can use different surrogate loss functions during training, at test time we always use the zero-one loss because we care about the accuracy, and the zero-one loss is equal to one minus the accuracy.
To quantitatively measure the tail performance of model F, we can use the a-CVaR (Conditional Value at Risk) loss. For a fixed a E (0, 1). the a- a-CVaR loss is defined as
CVaR =
max we AEA., 200
w, (,((F(()).)) y:)
where A,, ( ,xx) : x4 2 0.
13 is the unit simplex in R". The a-CVaR loss measures how well a model performs over the worst a fraction of the dataset. For instance, if m on an integer, then the a-CVaR loss is the average loss over the m samples that incur the highest losses. We use CVaR classification to refer to classification tasks where models are evaluated by the CVaR loss. Denote the set of minimizers of the a a-CVaR loss by FCVRR = arg min CVaR", (F).
The CVaR loss can be written as the limit of DRO (Distributional Robust Optimization) losses. For some divergence function D between distributions, the DRO loss measures the model's performance over the worst-case distribution Q & FD within ball w.r.t. divergence D around the training distribution P. Formally, the DRO loss of model F defined as
DRO (F) sup (Eo(
QEr
If we denote the Rényi-divergence by D3 P || Q) = उー log [( s dQ then the a-CVAR loss is
equal to the limit of DRO D,, - log as B > oo (see Example 3 in DN18 Many previous works
Q is absolute continuous 1' (i.e. Q < P) if for any event A, P(A) 0 Q(A) 0.
3

---

proposed to train a model with high tail performance by minimizing the CVaR loss or the DRO loss. However, the following result shows that for classification tasks, any model in F FRM is also the minimizer of the CVaR loss if F only contains deterministic models, i.e. every E Fis is deterministic mapping F X y (all proofs can be found in Appendix [A]:
Proposition 1. If IF only contains deterministic models, then for any model F E F and any FRM we have CVaaaa fa/1 (F) 2 CVaRa fo!! (F*). Moreover, if minner (Ron(F) < a,
F E Ft
then we have Fx ERM/0/1
= FF f9/1"
CVaR,
HNSSI8 showed that a counterpart of the above result holds for any f f-divergence DRO loss. As noted earlier, we can write the a-CVaR loss as the limit of the Rényi family of f-divergence DRO losses. However our proof is much more direct and simple, and proceeds by showing the following simple monotonic relationship between the average zero-one loss and the a-CVaR zero-one loss:
CVaR, for (F) min {1, a fo/1 (F) }. so the o-CVaR loss is non-decreasing with the ERM loss. This is a very pessimistic result, since it entails that there is no hope to obtain a better model than ERM no matter what learning algorithm we use for CVaR classification.
For the DRO context, some previous papers [HNSS18] LBC MHN21 propose to avoid this issue by making extra assumptions the testing distribution, so change the evaluation metric to some function other than the f-divergence DRO loss. In this work, however, we take a completely different approach: we show that the above difficulty can be circumvented without any extra assumptions by using randomized models" For a randomized model F, its empirical risk and Q-CVaR loss is defined as the expectation of T and 2 where the expectation taken over the randomness of F. For randomized models, the monotonic relationship in Proposition| [ does not exist, and they can achieve lower a- a-CV zero-one loss than deterministic models. For example, if we have deterministic model with average accuracy 90%, then the 10%-CVab zero-one loss of this model is 1. However, we have deterministic models with average accuracy 90%, such that each sample is classified correctly by at least 4 of the 5 models, then the (VRR zero-one loss of the average of the 5 models only 0.2, though its average accuracy is still 90%. Furthermore, we can prove that:
Proposition 2. Let F be deterministic model, and F' be any randomized model whose average zero-one loss is the same as that of F. Then, for any E (0, 1), CVaR fo/s (F") S CVaR fors (F).
This result implies that the tail performance of a randomized model is consistently higher than a deterministic model with the same average performance. In a nutshell, we have proved that for CVaR classification, ERM is the best deterministic model learning algorithm, and randomized models can achieve higher performance than deterministic models.
3 Boosted CVaR Classification
In this section, we propose the framework of Boosted CVaR Classification, which learns ensemble models with high tail performance via Boosting. An ensemble model consists of T base models f²,... -T : x + y and a distribution À = (X* .... X²) E AT over the models. À is called the model weight vector. At inference time, we first sample model f* according to X, and then predict with the model. Denote the zero-one loss of base model f over sample 24 by f. Then, the a-CVaR
zero-one loss of the ensemble model F = (f),.... fT.
n
T
CVaR (a/ CVaR fo/L forl(f)
(f), (fl.....
f A)
max WEA,, W
Σ
W
X
(4)
t=1
The motivation of this framework comes from a direct relationship between the CVaR loss and the objective of a variant of Boosting we call a- a-LPBoost, which shows that training with respect to the o-CVaR loss can be related the goal of boosting an unfair learner (Section B.T). Thus in Section 3.2 we present the Boosted CVaR Classification framework which formulates the training
II I' is randomized model, then for any x, F(x) is random variable over y, i.e. for any x. y. P(F(2) = v) a real number in [0. 1] instead binary. 'The notion F = (f (f'...., f A) means that the ensemble model F' consists of base models fl,...
and model weight vector X.

---

process sequential game between the training algorithm and the unfair learner, and implement an algorithm that uses (Regularized) LPBoost for CVaR classification. Finally, Section 3.3 we implement another algorithm which we name
that is computationally more efficient.
3.1
Q- a-LPBoost
Suppose have already obtained base models { JE(t) and the s-th function I incurs losses { he(m)] the samples (2ihie(n)- Consider the following primal/dual linear programs:
Dual:
Primal:
min
7
max
Σ lp
1
Σ 8=1
s.t.
(w,, L)) 2
Vs E
(5)
X,P
am
(6)
1
s.t.
AEA
w E An w
an
where (a:)+ max (x. 0}. Note that the primal problem can be written linear program by X,(f)++ Ein See the full derivation of this primal-dual introducing slack variables t/ = = (p-1+
linear program in Appendix A.3 Let us denote the optimal dual objective by 7f and the optimal primal objective by P'. For this linear program, strong duality holds, i.e. p = = We refer to these primal/dual linear programs as a-LPBoost, since it can be seen as calpoppulation-peffrrmancce counterpart of a classical variant Boosting called LPBoost [BSTO2).
Intuitively, the dual problem is trying to find a w such that every S has a high weighted average loss (w, (*) with respect to w. One might wonder what the primal problem is doing. The magical thing that the primal problem is in fact searching for the model weight vector À that minimizes the a- o-CVaR zero-one loss of the ensemble model consisting of ft. f1..... ff, as shown by the following proposition:
Proposition 3. For any f'...,f''. we have the following relationship between the a-LPBoost objective and the a-CVaR zero-one loss:
- min CVaR fo/s (f), J',
XED.
and the optimal solution of the primal problem X achieves the minimum
This result also shows a direct relationship between CVaR and LPBoost: minimizing the Q-CVaR loss is equivalent maximizing the a-LPBoost objective. Thus, the problem now becomes how to maximize 7h- Note that we can rewrite the first constraint of the dual problem as 2 - -(w, l*) for all 8, so y the accuracy of the best f". Therefore, we can increase 7 by training a new model ft+1 whose weighted average loss with respect to w, i.e. (w, e(+1), is small. We can repeat this process until we have obtained sufficient base models so that there no such w that makes 7 small. Then, we can obtain the optimal model weight vector A by solving the primal problem of a-LPBoost.
3.2 The Boosted CVaR Classification Framework
Motivated by the above analysis, we design the Boosted CVaR Classification framework that formu- lates the training process outlined in the previous section as a sequential game between a boosting algorithm and an unfair learner L. We make the following assumption on L:
Assumption 1. We have access to an unfair learner L that takes any sample weight vector w E An as input, and always outputs a base model whose weighted average zero-one loss with respect to w at most (0, 1). g is called the guarantee of the learner L.
In each round, the boosting algorithm picks a sample weight vector w (wf.... w and feeds it to the learner L which outputs base model I" whose average loss w.r.t. w" is at most g. The boosting algorithm goes as the following:
For t = 1......77
Pick a sample weight vector w' = (wf. ... ... w()) E A, and feed it to L
-
Receive a base model f² from L such that E w Z
At the end of training, pick model weight vector À Ar and return F (ft,..,,f ,A.))
5

---

Algorithm 1 (Regularized) a-LPBoost for CVaR Classification
Input: Density of the test subpopulation a, regularization coefficient 3, number of base models T Initialization: w² .........
2: for = 1, 1.... , , do
3: Run learner L with weight vector wt
4: C outputs model ft with sample losses L' = (fi..... ,
5: Solve the dual a-LPBoosst problem (5) or regularized version over the training set to
get the sample weights w²+1
6: Solve the primal a-LPBoost problem 6 over the validation set to get the optimal A
7:
return F ( ...
To study the worst-case performance of the boosting algorithm, we can view L as an adversary: The boosting algorithm picks w' and À in order to minimize (4), while & picks le = (Li, lg under the constraint (w² e S g in order to maximize (4).
Based on this framework, we implement Algorithm|] ! which uses LPBoost to pick sample weights and model weights. For solving linear programs, there are number of convex optimization solvers available. Now we prove a convergence rate theorem for this algorithm. To show that Algorithm D converges, need prove that with sufficiently large T, the worst-case o-CVaR loss of the ensemble model can be as close to we wan Ideally we would like T to be in the order of log 1. However, [RWG07] presented counterexample its Theorem where a-LPBoost requires = ) base models to converge. To make T logarithmic +. [WGV08] proposed (Entropy) Regularized a-LPBoost, which adds regularization to the dual problem. At each iteration it solves following convex problem for some regularization coefficient /3 > 0 to pick w:
min 7 H(w)
B
(8)
(w, 0) - (s E [4]), w An, z
on
where H(w) = - Wa log w; the entropy function. With the regularization, we can prove the following theorem:
Theorem 4 (Theorem in [WV088] ). For any > 0, if we run Regularized a-LPPoosst with
=max(3 3 log 1. 1), then we have CVaR fo/ (F) S g + 5 with T base models where
32
8 82 a
T max
log
Connection to AdaBoost.
proved that classical Regularized LPBoost (i.e. a-LPBoost with 1/n) is equivalent to MaaBoostFSS7 with regularization (see its Section 3.2).
SL.9
3.3
P-oosLPBoost
We have proved that the a-CVaR loss achieved by Regularized a-LPBoost can be arbitrarily close to g with 7 Olog 4). However, one disadvantage of Algorithm is that needs train a different set of 7 base models for each a. On the other hand, since a controls the trade-off between fairness and average performance, in practice we might want change from time to time. For example, we might want to tune down a to make the model fairer. Thus, it would be more efficient if we could train only one of 'T' base models for all a. and by adjusting the model weight vector for different we could still achieve tail performance comparable to Regularized a-LPBoost.
To this end, first the classical Regularized LPBoost (with a 1/n) to pick wi train the base models, since the resulting base models would also be suitable for more general a > 1/n. Following (SL09, we solve this step using variant of AdaBoost. We then pick the model weights by solving the a-oott primal problem after all base models are trained. The method, which we
'The C-CVaR loss is lower bounded by because L can always output model whose average loss over the uniform distribution of 21, 2n is at least g. so that the average loss is at least g.

---

Algorithm 2 ar- a--AaLLPBoos
Input: Step size density of the test subpopulation a, number of base models T I: Initialization: w-
..,..... ...
2: for /= 1,... , , do
3: Run learner L with weight vector wt
4: C outputs model ft with sample losses L' (-.,... (n)
5: Pick w²+1 A. such that w x exp(n exp(nE..1 1
6: Solve the a-L.PBoost primal problem (6) over the validation set to get the optimal
7: return ,', and X
denote by a-AdaLPBoost, is listed in Algorithm 2 The difference between Algorithm 2 and the original AdaBoost that AdaBoost picks wit1 x 5 where B. = I-c, and 6, = Σi= wff is the weighted average loss, whereas Algorithm 2 picks w w exp(n()) for a constant 17, which we find achieves better performance than AdaBoost in our experiments.
The advantage of using our two-step approach is that when a changes, we only need to adjust the model weight vector À without training an entirely new set base models. We next show that the two-step approach is not just intuitively reasonable, but comes with strong theoretical guarantees. To begin with, we consider a mixed algorithm called "AdaBoost + Average", where we train the based models with AdaBoost (as in Algorithm 2 and output the average of the base models (such that For AdaBoost + Average, we have the following result:
= ( "
+)). ((,,,
Theorem 5. For any
and T O 53"h ), the training a- -VRR zero-one loss of the ensemble model given by AdaBoost + Average is at most + ō if we set v 8 loggn//? n//T.
The theorem guarantees that AdaBoost Average can achieve low a-CVaR zero-one loss. Next, note that the a- e-CVaR zero-one loss of 1-AAdLPBoooss is upper bounded by the minimum of those of ERM and AdaBoost + Average, because a-LPBoost ensures that the À picks achieves the lowest a-CVaR zero-one loss, while ERM corresponds to À (1, 0, ... 0) and AdaBoost + Average corresponds to (T: T: .... )). In other words, the theorem ensures that the tail performance of AdaBoost + Average is high, and a-AdaL achieves tail performance no lower than that.
3.4 Discussion
Generalization Bound for the CVaR Loss. our analysis, we only provide theoretical guarantees on the training o-CVaR zero-one loss for the methods we propose. One might be curious about the generalization capability of boosting with respect to the CVaR loss. A recent work [KLPR20 proved generalization bound for the CVaR loss under the assumption that the hypothesis set JF has finite VC-dimension, and it well-known that if F has a finite VC-dimension, then the set of ensemble models based upon FF also has finite VC-dimension (see e.g. Section 6.3.1 in [RTT88). However, in the VC-dimension based analysis, the generalization error increases with T, while in practice usually decreases with T. Thus, people use the margin- masgen- analysis to obtain tighter bound. We leave the margin-base based analysis of Boosted CVaR Classification to future work.
Sensitivity to Outliers. An algorithm that maximizes the tail performance of model can be very sensitive to outliers. This is because such an algorithm puts more weight on samples on which the model has high losses, while intuitively outliers tend to incur high losses. Consequently. the algorithm puts more weight on outliers. A recent work [ZDKR2I] proposed to solve this problem with an algorithm called DORO, which ignores a fraction of the samples with the highest losses within the minibatch for each iteration. DORO can also be combined with our Boosting algorithms.
Connection (Domain-Aware) Group DRO. Our algorithm has a strong connection to Group DRO proposed in [SKHL20] for domain-aware subpopulation tasks. Group DRO assumes that the dataset divided into K groups and minimizes the model's maximum loss over the K groups with AdaBoost. We can obtain Group DRO from AdaBoost Average by choosing defining é as the loss of model f over group i. Our algorithm suggests that we can improve Group DRO if we choose the model weights with LPBoost.
K, 1 and
7

---

Experiments
4.1 Setup
Datasets. We conduct our experiments on four datasets: COMPAS [MKAT6]. CelehA [LWT15),
CIFAR-10 and CIFAR-100 [KH+ The first, COMPAS, is tabular recidivism dataset widely used in fairness research. The second, CelebA, with the target label as whether a person's hair is blond or not, was used in [SKHL200] evaluate their proposed Group DRO algorithm. And finally, CIFAR-10 10 and DIFAR-100 are two widely used image datasets. Both COMPAS and CelebA are binary classification tasks, while CIFAR-10
10-class and CIFAR- 1000 is 100-class classification. On COMPAS we use the training set as the validation set because the dataset is very small. CelebA has its official vain-validation split. On CIFAR- 10 and CIFAR- 100 we take out 10% of the training samples and use them for validation. Our selection of datasets covers different types, complexity, and both binary and multi-class classification.
Learner L. We implement the unfair learner C as follows: given a sample weight vector w (WI,..., wn) E An. for each iteration we sample a minibatch with replacement according to the probability distribution w, and then update the model parameters with ERM over the minibatch (by minimizing the cross- cross-entropy loss). The learner stops and returns the model after fixed number of iterations, with the learning rate decayed twice during training. See our code for training details.
Training. We use a three-layer feed-forward neural network with ReLU activations on COMPAS, ResNet-18 [HZRS16] on CelebA, a WRN-28-1 [6 on CIFAR- 10 and WRN-28- 10 on CIFAR- 100. On each dataset, we first warmup the model with few epochs of ERM, and then train T 100 base models on COMPAS and CIFAR-10, 10, and T = 50 base models on CelebA and CIFAR- 100 from the warmup model with the sample weights given by the boosting algorithms. We train our models with CPU on COMPAS and with one NVIDIA GTX 1080ti GPU on other datasets. We solve linear which its core invokes MOSEK ApSS1
programs with the CVXPY package [DB6 AVDB18
and ECOS [CB13 for optimization
On each dataset, we run ERM and a-AdaLPBoost with differrntt values of a. Here ERM refers to the deterministic version, in which single base model is trained and used as the final model. For a-AdaL we choose 7) = 1.0 on all datasets which is close the theoretical optimal value n /8 log n/TT. We also compare P-oosLLBBoost with AdaBoost + Average order to demonstrate the effectiveness of selecting À with LPBoost. To simultaneously compare the performances under different a, we plot the c--CaaR zero-one loss vs a curve for each method on every dataset.
4.2 Results
We plot the experimental results in Figure Each experiment is repeated five times with different random seeds, and we plot the 95% confidence interval for each experiment. From the figure, we can see that the results are very consistent across different random seeds. It is also remarkable that on every dataset, the o-CVaR loss curve of o-Adal .Poost almost overlaps with the minimum of ERM and AdaBoost + Average. From the plots we can make the following observations:
When a is large, the a-CVaaR loss is close the average loss, and can see that the o-CVaR loss of o-Adal .PoostlPBooost
PBoost is very close to that of ERM. We also plot the test average loss of the three methods on CIFAR-10 and CIFAR- in Figure [ from which that there is a gap between the ERM line and AdaBoost + Average line, and the average loss curve of a-AdaLPBoost mostly lies between them.
When is small, the a-CV loss of a-AdaLPBoost is close to that of AdaBoost + Average, which is much lower than that of ERM. Recall our initial theoretical results on the equiva- lence of minimizers of the average loss and the CVaR loss for deterministic models, ERM achieves the lowest a Q-C loss among all deterministic models, so the results demonstrate that the ensemble model achieves higher tail performance than any deterministic model.
Overall, we find that P-oosLBBoost can automatically choose between high average performance (when a is big) and high tail performance (when is small).
'Please refer to their official websites for license information.
8

---

2.0
1.0
0.120
a-Vvait 7om-ore
0.8
Adalicost Average a-AddaPBoostt
Nverage Zero-ane
0.115
D.voi 75m.ore
0.100
AdaBcost: Averago
0.6
0.135
DvAdaLFBoost
0.4
0.100
0.2
0.095
0.4
0.2
0.0
0.3
0.4
(a) COMPAS
(h) CIFAR-10
(a) CIFAR-10
1.0
1.0
g
0.30
0.9
9cCvoN Zere-one
#<CVoR Zemoone
0.30
0.8
0.6
0.4
0.7
Avergge
0.6
0.28
0.7
0.28
0.5
0.1
0.2
0.3
0.1
0.2
0.0
0.3
0.5
(c) CelchA
(d) CIFAR-100
(b) CIFAR-100
Figure 1: Test V-C zero-one loss.
Figure 2: Test average loss.
One might ask why a-AdaLPBoost does not achieve lower average loss than ERM in our experiments, given that the model class of the ensemble models is larger than that of the deterministic models. The reason is that the model class we use for deterministic models (e.g. ResNet) is already very complex, so the average performance of ERM is high enough, and its loss mainly comes from the generalization gap instead of insufficient capacity of representation. In fact, we find that when is big, the model weight vector produced by LPBoost very close to 01,0,0.... 0), i.e. almost the weight is put on the first ERM model. That is why the a-AdaL curve and the ERM curve overlap when a big.
Comparison with Regularized LPBoost. Now we empirically show that a-AdaLPBoost can achieve performance comparable to Regularized LPBoost. In Figure 3 we plot the o-CVaR loss of ERM, a-AdaLPBoost and Regularized LPBoost (3 100) on CIFAR-10. The plot clearly shows that there is almost no gap between the performance of o- AddaLLBooss and Regularized LPBoost, so we can safely replace the latter with the former for computational efficiency.
Convergence. Finally, empirically examine the convergence rate of a-AdaLPBooost by studying how the a-CVaR loss changes with T. In Figure 4 we plot the results on CIFAR-10 and CIFAR-100, which show that AdaLPBoost converges slowly after T 30. Theoretically, for dataset with n 50000 samples, in order to acheive 5 < 0.1 in Theorem 5 we need T to be at least 500, which would take huge amount of time. Note that T 30 does not mean that the training time is 30 times more, because we can train each base model for fewer iterations since it initialized from warmup model and only needs finetune. our experiments, the training time of AdaBoost 3-6 times the training time of ERM if 30.
5 Conclusion
In this work, we addressed an issue raised by previous work that no deterministic model learning algorithm could be better than ERM for DRO classification (which we show formally also extends to C'VR) by learning randomized models. Specifically we proposed the Boosted CVaR Classification framework which is motivated by the direct relationship between c-CVaR and a-LPBoost, which sub-population variant of the classical LPBoost algorithm for classification.. To further improve the computational efficiency, we implemented the -e-Adal.Boooo algorithm. our experiments, showed that the ensemble models produced by G-AdaLPBoost achieved higher tail performance

---

Zeneane Love
1.0
ERM
e-CVAR Zaro-one Lass
1.0
1.0
Regulrrodd
0.8
adAdalPBostt
0.8
60
0.2
0.6
0.6
100
COOR Zoc
T-4
10
0.4
0.4
0.6
0.2
0.2
100
0.0
0.2
0.2
0.3
Figure Comparing between a-AdaLPBoost and Regularized a-LPBoost on CIFAR-10.
(a) CIFAR-10
(b) CIFAR-100
Figure Test a-CVaR zero-one loss of a-Adal wad..al.Paaaa PBoost under different values of
than deterministic models, and the algorithm could automatically choose between high average performance and high tail performance under different values of
One caveat of using randomized model is that one might able to game the model via repeatedly using it. For example, when applying for credit card, one can submit the application repeatedly until it gets approved if the decision given by a randomized model. is important to study how to improve the tail performance in this scenario where the model can be used repeatedly, which leave as an open question.
One future direction is the application of ensemble methods to the fairness without demographics problem, in which the dataset is divided into several groups which are unknown during training. and the goal is to minimize the model's worst-group loss, i.e. its maximum loss over all the groups. The worst-group loss can be upper bounded by the CVaR loss or certain families of DRO loss, but the bound is loose, and the model with the lowest CVaR loss is not guaranteed to achieve the lowest worst-group loss. Due to the difficulty of the problem, some recent works considered the scenario where small set of samples with group labels is provided after training and before testing. Ensemble methods can be useful in this scenario: we can train base models, and then solve a linear program to obtain the optimal model weight vector with the provided validation set with need of training new models. We leave the design such algorithms to future work.
Social Impact. Subpopulation shift has been widely studied to improve the fairness of machine learning, which is of great social importance. Models with high tail performance are considered fair because they perform well on all parts of the data domain. In this work we show how to improve the tail performance by learning ensemble models, which is great contribution to the area of fair machine learning. However, we also observe that ensemble methods improve the tail performance by lowering the accuracy over samples in the majority group. Such trade-offs nonetheless inevitable under the assumption that the average accuracy does not increase. It is an interesting sociological question to what extent it is just to improve fairness by sacrificing the majority group.
Code.
Codes for this paper can be found at: http//ghhh....ommtiiiiaa//otoooo
Acknowledgments and Disclosure of Funding
This research is supported by DARPA Guaranteeing AI Robustness against Deception (GARD) under the cooperative agreement number HR001 12020006 and the official title "Provably Robust Deep Learning".
References
[ApS21] MOSEK ApS. MOSEK Optimizer for Python. Version 9.2.44, 2021.
[AVDB18] Akshay Agrawal, Robin Verschueren, Steven Diamond, and Stephen Boyd. A rewriting system for convex optimization problems. Journal of Control and Decision, 5(1):42-60, 2018.
10

---

[BHL19] Dheeraj Bhaskaruni. Hui Hu, and Chao Lan. Improving prediction faimess via model en- semble. In 2019 IEEE s1 International Conference on Tools with Artificcal Intelligence (ICTAI), pages 1810-1814, 2019.
[DB16] Steven Diamond and Stephen Boyd. CVXPY: A Python-embedded modeling language for convex optimization. Journal of Machine Learning Research, 17(83)11-5, 2016.
[DBST02] Ayhan Demiriz, Kristin P Bennett, and John Shawe-Taylor. Linear programming boosting via column generation. Machine Learning, 46(1):225-254, 2002.
[DCB13] A. Domahidi, E. Chu, and S. Boyd. ECOS: An SOCP solver for embedded systems, In European Control Conference (ECC), pages 3071-3076, 2013.
[DN18] John Duchi and Hongseok Namkoong. Learning models with uniform performance via distributionally robust optimization. arXiv preprint arXiv:1/800.88750, 2018.
[FS97] Yoav Freund and Robert Schapire. A decision-theoretie generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1):119-15) 139, 1997.
[GFB+11] Mikel Galar, Alberto Fernandez, Edurne Barrenechea, Humberto Bustince, and Fran- cisco Herrera. A review on ensembles for the class imbalance problem: bagging- boosting-, and hybrid-based approaches. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 42(4):463-484, 2011.
[NSS188] Weihua Hu, Gang Niu, Issei Sato, and Masashi Sugiyama. Does distributionally robust supervised learning give robust classifiers? In International Conference Machine Learning, pages 2029 2037.. PMLR, 2018
(HSNL18) Tatsunori Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang. Fair- ness without demographics in repeated loss minimization. In Jennifer Dy and Andreas Krause, editors, International Conference on Machine Learning, volume 80 of Proceed- ings of Machine Learning Research, pages 1929-1938, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR.
[HZRS16] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[IN19] Vasilcios Iosifidis and Eirini Ntoutsi. Adafair: Cumulative fairness adaptive boosting.
CoRR, 9999999922......... 2019.
[K]+09] Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
[KLPR20] Justin Khim, Liu Leqi, Adarsh Prasad, and Pradeep Ravikumar. Uniform convergence of rank-weighted learning. In International Conference on Machine Learning, pages 5254-5263. PMLR, 2020.
[LBC+20] Preethi Lahoti, Alex Beutel, Jilin Chen, Kang Lee, Flavien Prost, Nithum Thain, Xuezhi Wang, and Ed Chi. Fairness without demographics through adversarially reweighted learning. Advances in Neural Information Processing Systems, 33, 2020.
[LLWT15] Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of the IEEE international conference on computer vision, pages 3730-3738, 2015.
[LMKA16] Jeff Larson, Surya Mattu, Lauren Kirchner, and Julia Angwin. How analyzed the compas recidivism algorithm. ProPublica (5 2016), 9(), 2016.
[MHN21] Paul Michel, Tatsunori Hashimoto, and Graham Neubig. Modeling the second player in distributionally robust optimization. In International Conference on Learning Represen- tations, 2021.

---

[MRT18] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
[RWG07] Gunnar Rätsch, Manfred K Warmuth, and Karen A Glocer. Boosting algorithms for max- imizing the soft margin. Advances in neural information processing systems, 20: 1585- 1592, 2007.
[RWSTO5] Gunnar Rätsch, Manfred K Warmuth, and John Shawe-Taylor, Efficient margin maxi- mizing with boosting. Journal of Machine Learning Research, 6(12), 2005.
[Sch90] Robert E Schapire, The strength of weak learnability. Machine learning, 5(2):197-227, 1990.
[Sch03] Robert E Schapire. The boosting approach to machine learning: An overview. Nonlinear estimation and classification, pages 149-171, 2003.
[Shi00] Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the bog-liieldhoo function. Journal of statistical planning and inference, 90(2):227-244 2000.
[SKHL20] Shiori Sagawa, Pang Wei Koh, Tatsunori B. Hashimoto, and Percy Liang. Distribution- ally robust neural networks for group shifts: On the importance of regularization for worst-case generalization. In International Conference on Learming Representations, 2020.
[SL09] Chunhua Shen and Hanxi Li. A duality view of boosting algorithms. CoRR, abs/0901.3590, 2009.
[SRKL220] Shiori Sagawa, Aditi Raghunathan, Pang Wei Koh, and Percy Liang. An investigation of why overparameterization exacerbates spurious correlations. Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 8346-8356. PMLR, 13-18 Jul 2020.
[WGV08] Manfred K Warmuth, Karen A Glocer, and SVN Vishwanathan. Entropy regularized Ipboost. In International Conference on Algorithmic Learning Theory, pages 256-271. Springer, 2008
[XDKR20] Ziyu Xu, Chen Dan, Justin Khim, and Pradeep Ravikumar. Class-weighted classifi- cation: Trade-off's and robust approaches. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning. volume 119 of Proceedings of Machine Learning Research, pages 2020.
PMLR, 13 18 Jul
[ZDKR21] Runtian Zhai, Chen Dan, Zico Kolter, and Pradeep Ravikumar. Doro: Distributional and outlier robust optimization. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 2335-12355.. PMLR, 18 24 Jul 2021.
[ZK16] Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. arXiv preprint a60iv: 07 1466,, 2016.
12


Reviews:
[{"review_id": "wrtcESQW2vf", "reviewer": "Reviewer_h6bZ", "summary": "This paper studies the boosting framework for classification. Weak classifiers are produced sequentially by an abstract learner. The popular α-CVaR (Conditional Value at Risk) is adopted. The 0/1 loss is considered. First, it is proved that the optimizer (among all the deterministic models) of ERM is also the optimizer of α-CVaR, and vice versa if α-CVaR could be smaller than α by some deterministic model. The authors also prove that with the same 0/1 loss, the randomized model achieves smaller α-CVaR. The optimization structures of α-LPBoost and α-AdaLPBoost are studied to construct randomized classifiers.", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "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": "Main concerns:\n\n1. Evidently the generalization ability of boosting depends on the richness of weak classifiers. The link between learner and generalization power is not discussed. In particular, we believe that with the 0/1 loss, such a learner would not be computationally tractable.\n2. How does the proposed Boosted CVaR Classification framework learn randomized classifier? We note that in remark 2 at the end of page 4, F is defined as a function; however, F is defined as a tuple before Equation (4), which is unlikely to produce a number.\n\nsome points:\n1. Line 131, \"DRO\" should be \"DRO^\\ell\"\n2. We are not certain about the claim \"... then the α-CVAR loss is equal to the limit of ...\" in lines 130--131. Apparently, the α-CVAR loss is defined in (2) based on n sample points and the unit simplex of R^n, but the limit discussed here has no relation with n.\n3. What is the definition of \"deterministic model\"? In particular, is it more than a map in the general sense? If so, is there any example of a map that is a model but not deterministic? Moreover, what is a \"randomized model\"? We note footmark 2 on page 4 on the randomized model, but that is a description of its property, and it is not a rigorous definition.\n4. In the proof of Proposition 2, why is the CVaR_alpha loss of F' no greater than 1?\n\n==================================\n\nAfter reading the Author's/Authors' response, I think that all of my technical concerns have well been addressed. I appreciate the careful and comprehensive response by the Author/Authors. I would like to raise my rating.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations: see our concerns above\n\nSocietal impact: big potential of societal impact through the significant improvement of classification algorithm for machine learning and data science.", "review_text": "", "extra_scores": {"ethical_concerns": "N.A.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "amt4gBwrGSd", "reviewer": "Reviewer_xo9P", "summary": "The authors of this paper propose robust boosting algorithms for minimzing the \"CVaR_{alpha} 0/1-loss\", defined as the worse case 0/1 loss over all alpha-sized sub-populations of the entire population. Models with low \"CVaR_{alpha} 0/1-loss\" help ensure fairness by not performing too poorly on any individual subpopulation.\n\nThe authors provide a number of contributions:\n\n1. They show that while optimizing \"CVaR_{alpha} 0/1-loss\" is equivalent to minimizing average 0/1 loss when one is restricted to using deterministic classifiers, this is not the case if one is allowed to use randomized classifiers. And in fact, randomized classifiers can in principle always perform at least as well on CVaR_{alpha} 0/1 loss as deterministic ones.\n\n2. They use the observation in #1 to motivate boosting algorithms that explicitly optimize the CVaR_{alpha} 0/1 loss. Here they provide 4 related learning algorithms\n  * alpha-LPBoost\n  * Regularized alpha-LPBoost\n  * alpha-AdaLPBoost\n  * AdaBoost + average\n\n3. For the proposed algorithms, the authors give complexity guarantees that bound the ensemble size as a function of the required accuracy.\n\n4. The authors compare their CVaR-optimizing, robust boosting algorithms to the baselines of stanard boosting with empirical risk minimization (ERM and \"AdaBoost + average\". Their experiments show that alpha-AdaLPBoost performs well on CVaR_{alpha} 0/1 loss across all values of alpha, in contrast to ERM which performs well when alpha is large and alpha-AdaLPBoost which performs well when alpha is small.\n\n", "questions": "", "limitations": "", "rating": 7, "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": "This paper's main contribution is to show that randomized classifiers perform better than deterministic ones on CVaR_{alpha} 0/1 loss. And the authors capitialize on this observation by developing boosting algorithms which learn mixed strategies (randomized classifiers) for this loss function, and which have guarantees.\n\nNovelty and Originality: The finding that randomized classifiers outperform deterministic ones on CVaR_{alpha} 0/1 loss is a novel and solid finding, and it allows the authors to derive a new algorithm which directly optimizes CVaR_{alpha} 0/1 loss. So this paper provides a solid step forward by developing fair classifiers that are guaranteed not to peform too poorly on any sub-population. That said, the observation that randomized classifiers can do better in this setting than deterministic ones seems like something that would be apparent to researchers familiar with game theory and certain areas of learning theory. And the algorithms developed are built by combining and adapting previously existing boosting algorithms.\n\n\nClarity, Quality, Technical Soundness: This paper is clearly written and its claims are supported by theoretical results, as well as experimental results.\n\nRegarding the experiments, the authors cite previous work on optimizing CVaR_{alpha} loss which they do not compare against in their experiments. For instance, the paper cites work by Hashimoto et al. 2018 on optimizing the related \"DRO\" loss for handling subpopulation shift. However, the paper does state that that CVaR_alpha 0/1 loss is a certain limit of the \"DRO\" loss. So it's not clear whether adding these comparisons would yield further insights.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors address the societal limitations and potential of this work, and it is a pro-social contribution to begin with.\n", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "RZefl4Tb_Y8", "reviewer": "Reviewer_6kwQ", "summary": "The paper first shows that for deterministic models, optimizing for tail performance (in terms of 0/1 loss) is in fact equivalent to optimizing for average performance, and thus doesn't actually improve fairness of a model. As a mitigation, it is proposed to switch to non-deterministic classifiers, for which this property no longer holds. A boosting algorithm that can construct such a $\\alpha$-CVaR optimized non-deterministic classifier based on training weighted deterministic unfair classifiers is proposed and demonstrated to provide good results.", "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": "The first part of the paper is to motivate the use of non-deterministic classifiers (or equivalently a scorer that outputs probabilities) because on deterministic classifiers any ERM minimizer also minimizes the CVaR and as such minimizing for CVaR would not actually get fairer classifier. This is a special case that follows from a known more general result, but the paper provides a simple direct proof for the statement. It is then shown that when going to non-deterministic classifiers, 1) this equivalence no longer holds [Prop 2] and 2) the classifier can be learned using a variation of LP boosting [Prop 3], which is demonstrated to be effective. The ability to train classifiers that perform well on minority subgroups is an important problem nowadays, so I think that the contribution of the paper is significant. \n\nBelow is a list of things I noticed while reading, and some questions that I had:\n\n# Details:\n* l. 137 maybe explicity put the words \"it holds that\" or similar into the sentence. Right now, it is only clear that the CVaR statements are the claim once you've reached the period at the end of the sentence.\n* Section 3.1 I think a bit more detail would be helpful here, i.e. an explanation where the primal/dual problems come from -- what are they trying to optimize. The formulas look a bit different from LPBoost, \nI guess because of the switch from {-1, 1} to [0, 1]. Any intuition, besides that this is what is needed to match the expression against CVar in the proof of Prop 3? \n* l. 182 The way the problem is formulated here is technically nonlinear, since its objective contains the max function\n* l. 187 I think the statement as it is written here is not as strong as it should, as (7) just states that there exists a $\\lambda$ such that the optimal value coincides with 1 minus minimum CVar. \nHowever, the proof in the appendix seems to show that the lambdas are actually the same, I think, so that works out in the end and your statement in line 198 is actually true.\n* l. 278 How did you train to minimize the empirical risk? Minimizing categorical cross entropy? If so, are the ERM values in Figure 1/2 corresponding to a thresholded model, or to the probabilities learned by cross-entropy?\n* Figure 1/2 As the theory is based on the losses on training data, it would be nice to have (at least in the appendix) these graphs also for training losses.\n* l. 292: Should be \"minimum\" here I think\n* Appendix: In the appendix, it would be nice if the proofs were given together with the full assumptions and claim.\n\n* A1:Given that this is in the appendix and thus space is not such a pressing concern, maybe add one or two intermediate steps. For example,\nthe min in line 4 appears to come from whether there are more than $\\alpha n$ misclassified examples (then we can just put all weight on them)\nor less (then we can only put $1/(\\alpha n)$ on each). If you define $M$ as the set of misclassified examples, then the CVaR is either\n$(1/|M|) |M| = 1$ or $1/(\\alpha n) |M|$.\n* l. 6 I don't get the implication here? If the minimum is less than one, than clearly there exists an $F$ for which the statement is true, but why is it true for all $F$? \n\n=====\nUpdate\n\nTaking into account the author's comments, I have raised my score to slightly above.\nBased purely on the content, I might have given a higher rating, but I think that the clarity of the writing in the paper should be improved more before qualifying as \"Good paper, accept\".", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think one limitation is that without knowing anything about the subgroups, it is impossible to determine whether a data point comes from an underrepresented subgroup, or is just a mistake in the ground-truth labeling.\n\nAlso, for a practical application towards fairness, some way of determining the value for $\\alpha$ would be needed I think.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "P6ZayYqzqrq", "reviewer": "Reviewer_7rtp", "summary": "In this paper, the authors proposed two boosting algorithms named the $\\alpha$-LPBoost method and the $\\alpha$-AdaLPBoost (an efficient model) to solve the CVaR problem under the zero-one loss condition. Through the experiments and theoretical analysis, they claim that the minimization of the CVaR problem with randomized models under the 0-1 loss condition can achieve a lower loss than using the deterministic model. ", "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": "In general, the proposed method, which modifies the CVaR problem to an LPboosting problem is new. The authors demonstrate the difference between their work and existing works. This submission is technically sound. Some claims are well supported by theoretical analysis and experiments. The paper is well-written in several sections. However, the experiment part is not clear enough and contains many typos. \n\nMy major comments are as follows,\n\n1.  In the abstract (lines 17-18), the authors mentioned the proposed method can improve the tail performance by a large margin compared to the deterministic model. However, in the experiment part, the authors only compare the losses in different $\\alpha$ conditions. The only conclusion is the proposed method has a lower loss than the compared methods. How can the authors get a high tail performance conclusion from the experiment?  There are no numerical results (i.e., accuracy) that we can refer to.\n\n2. In the experiment part, there is missing some initial setting information about the proposed method and the compared methods. Specifically, in Figures 1 and 2, can we get the best performance from ERM or AdaBoost+Average method if we tune the hyperparameters or setting different initial weights? In Figure 3,  can the regularized $\\alpha$-LPBoost method better than the $\\alpha$-AdaLPBoost if we use the average performance from setting several random seeds or we set a different $\\beta$ parameter? Therefore, the sensitivity experiments in this paper are missing. Furthermore, 0-1 loss is a non-differentiable loss. Without large sensitivity experiments, it is hard to judge your model performance and experiment results. \n\n3. Some significant proofs are missing in the main paper or in the appendix. For example,  in line 131, how to derive $\\alpha$-CVaR from the limit of DRO with Renyi-divergence? In line 180, how to derivative dual formulation from the primal formulation? Since your dual and primal formulations are different from LPBoost, you cannot just provide a citation in line 184.\n\n4. In line 143, the $\\alpha$-CVaR loss is bounded by 1 and ERM. According to your formulation, we can only say $\\alpha$-CVaR loss is non-decreasing with the ERM loss. How can you say 'monotonically increases'?\n\n5. Since this paper focus on the CVaR, why the authors do not design an obvious baseline method, which optimizes CVaR directly? If directly optimize CVaR achieves the best performance, why we need to use the boosting method? \n\nMy minor comments are as follows,\n\n1. Experimental part is not well-written. There are some typos. For example, in line 266, 'we too adopt' should be 'we adopt'. In line 168 and line 269, ' Cifar' should be 'CIFAR', '100-class classification' should be '100-class', 'On COMPAS' should be 'On COMPAS, '. The authors should do several proofreadings ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper only considers 0-1 loss. In practice, we usually apply some surrogate losses for 0-1 loss because it is non-differentiable. The methods and results in this paper are hard to be generalized. I suggest the authors should discuss this limitation in this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "6hGG8Pdjyb", "reviewer": "Reviewer_aDDc", "summary": "The paper attacks the problem of \"fair classification\", where the goal is to train a classifier that is \"good\" on any small fraction of the samples. Obviously, any deterministic classifier having less than 100% accuracy is arbitrarily bad on a small fraction of the distribution. The authors propose the usage of randomised classifiers to bypass this. i.e we prefer a classifier that is correct on all samples 80% of the time over a classifier that is correct on 80% of the samples wrong on the rest 20% all the time. \n\nFirstly the authors observe the superiority of randomised classifiers for the CVaR loss over deterministic classifiers.  Then they propse the usage of a boosting framework to aggregate individual \"good but unfair\" classifiers into \"equally good but fair\" classifiers. In particular, the classic LP-boost algorithm is observed to be a good fit for this problem.\n\nThe authors then propose a more efficient version of the LP-boost algorithm where classifiers need not be trained for different levels of fairness (the worst fraction of samples being optimised for). \n\nThe algorithms are validated on classic classification datasets where they do better than standard baselines. ", "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": "The observation of CVaR for randomized classifiers being better is interesting but not surprising or significant. \n\nThe equivalence of LP-Boost to alpha CVaR is very interesting while still being obvious in hindsight and hence deserves credit.\n\nThe alpha-LP boost algorithm for CVaR along with AdaLP boost are modestly significant.\n\n\nSome other comments:\n\n1. The usage of randomised classifiers for fairness has technical issues. A classifier often needs to perform in the same way when applied repeatedly. E.g. Otherwise in a loan application classifier, the individual can just apply repeatedly until he gets through. \n\n2. Rename the function ERM[f] to zero-one[f] or similar. (line 113)\n\n3. Make the defintion of CvAR valid for randomised classifiers too, (line 119)\n\n4. Give a better example in lines 150 to 156, such that a CVaR  of less than 0.5 can be achieved. As a simple coin toss can achieve 0.5\n\n5. How is eta chosen in AdaBoost+average?\n\n6. If eta is fixed there is no Adaptiveness in \"adaBoost\", and hence a better name might be boost by majority.\n\n7. By the theorems the the CvAR loss should l=never go above g, the guaranteed performance of the unfair learner. The NN learners surely contain the constant function which would predict all classes with equal probability. So why does AdaBoost+average and AdaLPboost have losses greater than 0.5 in figure 1c, and loss greater than 0.9 in Figure 1b for alpha<0.1?  0.5 and 0.9 are the performance of a random classifier for 2-class and 10-class problem respectively.\n\n8. Are there standard bounds linking the train CVaR loss to the test loss, similar to the margin bounds for standard zero-one loss? If so, references to these would be helpful.\n\n\n\n", "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": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper showed in Proposition 1 that optimizing CVaR 0/1-lossis equivalent to minimizing average 0/1 loss when one is restricted to using deterministic classifiers which motivates the usage of randomized classifiers. Although the observation is interesting but not entirely new in light of the related work [HNSS18] and other ones in learning theory, the proof given here is simpler and easier to follow.  Motivated by this, the authors proposed an efficient LP boost algorithm for optimizing CVaR with theoretical convergence analysis. 

Overall, the paper presented an interesting framework based on LP-boost algorithms to build more fair classifiers with theoretical supports, although the key observation on the superior performance of randomized classifiers over deterministic is not surprising.  The revised version should take into account sensitivity analysis of hyper-parameters, the precise derivation of dual formulation, and the detailed discussion of deriving generalization bounds, and other comments made by the reviewers. 
Decision: Accept (Poster)