Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.

The authors provide a number of contributions:

1. 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.

2. 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
  * alpha-LPBoost
  * Regularized alpha-LPBoost
  * alpha-AdaLPBoost
  * AdaBoost + average

3. For the proposed algorithms, the authors give complexity guarantees that bound the ensemble size as a function of the required accuracy.

4. 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.


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.

Novelty 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.


Clarity, Quality, Technical Soundness: This paper is clearly written and its claims are supported by theoretical results, as well as experimental results.

Regarding 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.

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.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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. 

Below is a list of things I noticed while reading, and some questions that I had:

# Details:
* 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.
* 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, 
I 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? 
* l. 182 The way the problem is formulated here is technically nonlinear, since its objective contains the max function
* 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. 
However, 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.
* 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?
* 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.
* l. 292: Should be "minimum" here I think
* Appendix: In the appendix, it would be nice if the proofs were given together with the full assumptions and claim.

* 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,
the 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)
or 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
$(1/|M|) |M| = 1$ or $1/(\alpha n) |M|$.
* 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$? 

=====
Update

Taking into account the author's comments, I have raised my score to slightly above.
Based 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".
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.

Also, for a practical application towards fairness, some way of determining the value for $\alpha$ would be needed I think.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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.
main_review: Main concerns:

1. 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.
2. 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.

some points:
1. Line 131, "DRO" should be "DRO^\ell"
2. 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.
3. 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.
4. In the proof of Proposition 2, why is the CVaR_alpha loss of F' no greater than 1?

==================================

After 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.
limitations_and_societal_impact: Limitations: see our concerns above

Societal impact: big potential of societal impact through the significant improvement of classification algorithm for machine learning and data science.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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. 

Firstly 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.

The 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). 

The algorithms are validated on classic classification datasets where they do better than standard baselines. 
main_review: The observation of CVaR for randomized classifiers being better is interesting but not surprising or significant. 

The equivalence of LP-Boost to alpha CVaR is very interesting while still being obvious in hindsight and hence deserves credit.

The alpha-LP boost algorithm for CVaR along with AdaLP boost are modestly significant.


Some other comments:

1. 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. 

2. Rename the function ERM[f] to zero-one[f] or similar. (line 113)

3. Make the defintion of CvAR valid for randomised classifiers too, (line 119)

4. 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

5. How is eta chosen in AdaBoost+average?

6. If eta is fixed there is no Adaptiveness in "adaBoost", and hence a better name might be boost by majority.

7. 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.

8. 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.




limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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. 
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. 

My major comments are as follows,

1.  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.

2. 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. 

3. 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.

4. 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'?

5. 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? 

My minor comments are as follows,

1. 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 
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_title: null

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)