Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: ##########################################################################

Summary: 
The authors analyze the space of solutions for worst case fairness beyond demographics, and propose Blind Pareto Fairness (BPF), a method that leverages no-regret dynamics (i.e., Multiplicative Weight Update) to recover a fair minimax classifier that reduces worst-case risk of any potential subgroup of sufficient size (learnt over worst-case partitions, such that the smallest size/density is at least a minimum), and guarantees that the remaining population receives the best possible level of service. They show promising experimental results over three data sets: UCI dataset on Adult Income, Law School dataset, and Compas Dataset. 


##########################################################################

Reasons for score: 
The idea for establishing performance for unknown groups is interesting, simply because the set of protected attributes (e.g., nationality, race, genetic information) is evolving with time. In this regard, I find the premise of the paper interesting. To obtain a minimax classifier, the authors deploy a multiplicative weight update based method, which is somewhat standard.  Their setting is a bit incremental compared to multiple recent papers on minimax Pareto fairness guarantees, and not motivated beyond unknown groups (see cons). I therefore support (weak) acceptance of this work since they move away from "given groups" and show an improvement in the experiments for the worst-off group. 

##########################################################################

Pros: 

BPF addresses fairness beyond demographics, that is, it does not rely on predefined
notions of at-risk groups, neither at train nor at test time. 

Experimental results show that the proposed framework improves worst-case risk in multiple standard datasets, while simultaneously providing better levels of service for the remaining
population, in comparison to competing methods. 


##########################################################################

Cons: 

Comparisons from related work are weak. For example, the authors claim that "In our work
we consider subgroups based not only on all input features but also on outcome, which broadens the
scope to all conceivable subgroups based on the information available to the model." in comparison to Martinez et. al, which already considers minimax pareto fairness, for instance. Why are subgroups based on outcomes relevant? Why would it make sense in any application to consider based on outcomes. 

In comparison to Duchi et. al 2020, and Hashimoto et a. 2018, the authors say that "can be sub-optimal on the population segment that lies below their high-risk threshold (doing unnecessary harm)", however one can imagine that in some applications these high risk samples are in fact more important than the low risk ones. For which applications do the authors argue that distribution independent results are more useful, compared to these recent distributionally robust results? 

##########################################################################

Questions during rebuttal period: 

 
Please address and clarify the cons above 

 
#########################################################################

Typos: 


review_title: Weak acceptance

final_score: rating: 6: Marginally above acceptance threshold
review_content: ## Summary ##

This paper considers the relevant problem of group fairness in ML when there are no predefined groups. They aim to provide an algorithm that outputs a classifier that minimizes the risk of any group (of sufficient size) while at the same time being Pareto efficient. They do this by first showing that this problem is equivalent to the case when there are only two groups and then using no-regret dynamics to provide an algorithm which asymptotically converges to the optimal solution.

They also show empirically, using multiple datasets, that their algorithm is marginally better than the state of the art in terms of fairness and in some cases, efficiency.


## Strengths ##
This is clearly a very relevant problem since (as they mention) in a lot of cases, we may not have the group labels for each point in the dataset. Furthermore, being robust to any subgroup allows for the algorithm to be fair to groups who have not yet been declared as protected groups.

The algorithm asymptotically converges to the optimal solution. This algorithm not only minimizes the risk of the worst case group but also does not do any unnecessary harm to other groups while ensuring fairness.
The experimental section is very comprehensive and compares their algorithm to the state of the art using multiple datasets. It shows that in almost all of them, their algorithm does marginally better than the state of the art. This section also gives us an idea about the trade-off between efficiency and fairness.
Weaknesses:

* The improvement over the current state of the art in this problem (DRO) is very marginal and in some cases (the Compas Dataset), DRO does slightly better than BPF.
* There is no discussion about the result in Lemma 3.3. It is unclear whether this bound is reasonable or whether the loss in efficiency is significant.
* Lastly, in a lot of cases, the accuracy of groups which are not the worst-off group is significantly worse than that of the baseline while the accuracy of the worst off group is only marginally better than that of the baseline. While it is clear that this loss in accuracy is necessary to improve the accuracy of the worst off group, there is very little discussion on why this tradeoff is worth it, or whether there exists another way to address this trade-off. 

## Typos ##
* Unnecessary Parenthesis around Utsun et al (2019) (Introduction)
* $Y$ should be $\mathcal Y$ (Section 3.1, Line 6)
* $\Delta^{|Y| - 1}$ should be $\Delta^{|Y|}$ (Section 3.1)
* $p(A = a) \ge \rho$ should be $p(A = 1) \ge \rho$ (Proof of Lemma 3.1, Line 6)
* There is a typo in the equation $P(Y|A = 0, X) = \dots$ (Proof of Lemma 3.2)
* $a^*$ is not defined (Proof of Lemma 3.3)

## Other structural feedback ##
The classes of hypothesis functions that can be used is unclear throughout. It would help to discuss it for the readers who have not read Martinez et al (2020)

## After Rebuttal ##

I thank the authors for their clarifications and efforts to improve their work. I still support acceptance.
review_title: The authors explore how group fairness can be maintained when the groups are not predefined. 

final_score: rating: 6: Marginally above acceptance threshold
review_content: ### POST-REVISION
Thanks for revising your algorithm and clarifying its theoretical properties.

I think the changes made to the algorithm do seem substantial: you've changed a complicated combination of multiplicative and best response updates on alpha to a simpler projected gradient update  (I am assuming that the experimental results have also been revised accordingly). The description is now easier to follow and the convergence results now follow directly from Chen et al.

I'm raising my score to 6, but still find the novelty in the formulation to be somewhat limited.

One pending concern is that the algorithm maintains one parameter \alpha_i per training example, which can be prohibitively expensive for large datasets. Of course, one way to alleviate this difficulty would be to replace \alpha_i with a parameterized function of the features, which however, would make your formulation very similar to Lahoti et al. (2020).

Is there a way you could measure the violation in the pareto constraint in your experiments, to showcase how the classifiers learned by your method are different from those learned by the approach of Lahoti et al?
******

The authors seek to learn a classifier which is a pareto-efficient and achieves the min-max risk across different subgroups. They are particularly interested in a setting where neither the group memberships nor the number of groups is known a priori. Prior work by Martinez et al. (2020) propose an approach for learning min-max pareto fair classifier when the group identities are known beforehand. This paper's proposal is to formulate a min-max optimization problem: like Martinez et al. the minimization is over the space of pareto-efficient classifiers, whereas the maximization is over all (soft) partitions of the data into two groups. 

The authors show that the solution to this problem degenerates into a trivial classifier when the size of the smallest group is below a certain threshold. They then propose an algorithm inspired from Chen at al. (NeurIPS 2017) to solve the min-max problem.

I like the problem formulation and find the problem setup to be practically relevant (given that there's an increasing emphasis in the fairness community on addressing scenarios where the protected group information is noisy or unknown).

However, I'm unable to verify correctness of algorithm and guarantee
- The authors say they adapt Algorithm 3 from Chen at al., but I find the proposed algorithm to be different from the one in Chen et al. Unfortunately, the textual description doesn't delve into any of these differences. I am also unable to see how the no-regret guarantee the authors provide in Lemma 4.1 follows from results in Chen et al. They provide a one line proof stating "Immediate application of Theorem 11 in Chen et al. (2017)" but I don't see how Theorem 11 directly applies to the specific problem setup the authors consider.

Below, I elaborate the discrepancy I see with Chen et al.

Algorithm 3 in Chen et al., which the authors adapt, consider the following setup: there's an objective L(x, w) which is possibly non-convex in "x" and is convex in "w", and the goal is to minimize L over x and maximize it over w. They assume access to an oracle that can minimize L(., w) over "x" for a fixed "w", and provide an algorithm which performs gradient ascent updates on "w" and performs full optimization over "x" using the oracle. They show convergence guarantees for this algorithm.

The min-max problem considered in the present paper also has two sets of parameters "alpha" and classifiers "h". The objective is non-convex in alpha (see eq. 6), and convex w.r.t. "h" (Sec 3.1). So the natural analogue of the algorithm of Chen et al. for this setup, would be to perform full optimization over alpha (which the authors do), and to perform (projected) gradient updates on "h". However, instead what the authors use for "h" is some form of a multiplicative weights update, which I find confusing. What you have is a multiplicative update again on alpha, and an invocation of another algorithm by Martinez et al.  to learn a pareto-efficient classifier. Was the idea to perform a multiplicative update on "h" and project it back to the space of pareto-efficient classifiers? 

I agree that like gradient ascent, multiplicative weights (MW) also enjoys no-regret guarantees but to apply MW, won't you need to maintain an explicit weight for each classifier "h"? Instead, why is the MW update applied again to the alpha's?

At the very least, I think authors need to elaborate on how exactly they apply the algorithm from Chen et al. The current discussion is light on the details.
review_title: Interesting problem, but unable to verify correctness of the proposed approach

Meta-review: This paper studies the problem of Pareto fairness without having pre-defined protected groups. The reviewers agree that the problem studied here is interesting and relevant. During the initial review period, reviewers identified a major correctness issue. The authors have then substantially changed the algorithm and experiments in the rebuttal period in order to address the issues. Now the convergence result in the paper follows more directly from the prior work of Chen et al. Overall, the technical novelty of the paper appears to be limited. Even though the authors have also strengthened the related work discussion, they should also consider discussing the comparison between their work with that of Lahoti et al., as suggested by one of the reviewers. 

Decision: Reject