Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper considered solving the minimax fair classification by adaptively constructing a training sets, based on the principle of optimism in the face of uncertainty. The authors provide a simple and straightforward analysis on the performance of ERM on constructed training sets, and empirically show the performance on synthetic and real dataset.

main_review: Overall the main idea of the paper is clear to me. However, I have several questions on the algorithm design, theoretical analysis.

General Questions:

1. The algorithm assume we have an access to the oracle $P_z$, but in practice we only have an access to a batch of samples, which cannot guarantee we can always get independent samples from $P_z$ (for example, we requires the amount of samples from $z_i$ larger than the total amount of samples that have attribute $z_i$ from the dataset), how can we deal with such scenario?

2. What’s $\pi$ in the definition of $e_z$ (Line 226)? Is it related to $\pi_z$? I don’t see any of clarification throughout the whole Sec 3.

3. It should be better mentioned that $\mathcal{D}_{z}$ is used for cross-validation in Sec 3 and algorithm box.

4. I would like to ask how general is the Assumption 3. The derivation heavily depends on this Assumption and I don’t feel it quite natural. It assumes a reverse of the triangle inequality, but can there be cases that each component is large but have different signs so the sum is small? Can such assumption be replaced with local smoothness and convexity of $f$ and $l$? Such assumption seems more general to me.

5. I would gonna argue that the lower bound is not “matching”, especially the upper bound is linear in $|\mathcal{Z}|$. The lower bound in $n$ is not surprising, as for generalization an $\Omega(n^{-1/2})$ minimax error is unavoidable. I expect to know whether this $|\mathcal{Z}|$ is unavoidable, or is just an artifact introduced by the proof strategy.

Some questions regarding the proof and proof organization.

6. In Line 602, the authors say that the right inequality is due to Lemma 1, but here  $z$ is in the underrepresented group, while Lemma 1 discuss the $z$ in the overrepresented group (see Line 569 and 592), can the authors make a clarification on that, as it’s critical to the proof?

7. I suggest the authors refine the proof in the Appendix. Its’ pretty hard to check when the proof is not well-organized. For example, in Line 603-610, I don’t quite see why by definition $t_0 \geq \pi_{\min} n$ until I see $t_0\geq N_{z_0, t_0}\geq \pi_{\min} n$ and aware of the final inequality is due to forced exploration. In fact, the authors does not emphasize the need of forced exploration in any place.

8. Also, the introduction of terms in (11) and (12) is not so intuitive and easy to follow. It’s not clear where and why should we introduce $A$ (and $A_i$ in the subsequent part), and why we need $n_0 > \pi_{\min}^{-2}$. It’s better to give more explanation to the potential readers.

9. In Line 640 why $\mathcal{Z}_{u}$ could be empty? Please make the claims as accurate as possible.

10. Is $N$ in Line 687 $N_A$ and no $A$ in the right side?

Minor Questions on Experiments.

11. I feel there are some gaps between theory and experiments. It’s understandable to select some confidence parameters when conducting neural nets experiments as the function class complexity is generally not so applicable, but for me it does not support the theoretical results any more.

12. I would also like to ask when we don’t have the oracle $P_z$,what can we do instead. This is the real scenarios we face in practice. As the authors conduct some experiments with real world dataset, I want to mention that the target for such scenarios is totally different from the problems the authors have described.

Overall, this paper is an adaption of the popular UCB method to the minimax fair classification tasks. The main technical difficulty is that, adding new samples from one attribute will affect the performance on all of the attributes, which is different from the bandit setting. The authors address this issue with several new assumptions to prove the optimism and back to the bandit style proof. Assumption 1 is sound, however, assumption 2 is quite restricted and the authors only provide a heuristic fix without any further theoretical justification. Assumption 3 is quite strong without intuitive clarification. The proof is not well-organized and may have some potential issues. Moreover, the algorithm is somehow idealized in the sense that it assumes the data generating process oracle, which is probably not a good setting in practice. Based on the reasons I mentioned above, I tend to reject this paper.

limitations_and_societal_impact: The authors have properly addressed them.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a sampling algorithm to construct the training dataset adaptively, the goal is to learn a classifier that can attain minimax fairness measured by the predictive loss. The authors show that the proposed algorithm has nice theoretical properties (upper bound on the regret, and this upper bound can not be improved).
main_review: I enjoyed reading the introduction and the problem formulation part of this paper. Nevertheless, I encounter difficulty to digest section 3 which contains the main contribution of this paper:

- The paper lacks some intuition on the sampling algorithm. Can the author provide some intuitive explanation on why Algorithm 1 may work?
- In line 226, why does the expression involve n but not N?
- What is the query budget n so that Theorem 1 is valid (say, for Adult and German dataset and a logistic/SVM classifier)? 
- Empirically, it is difficult to be convinced that A_opt is a better algorithm than the eps-greedy method of Abernerthy et al. (2020). Apart from the theoretical difference in Remark 1, can the authors provide any justification to use A_opt? 


Minor comments:
- In line 199, xi is in (0, 1) but in line 218, xi is in (0.5, 1)?

limitations_and_societal_impact: This paper is on fairness, so I encourage the authors to discuss some risk, limitations and promise of the A_opt sampling algorithm.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper exploits active sampling methods to construct a training dataset that yields fair classifiers in a minimax sense: minimising the maximum risk of any of the groups of interest. The proposed method constructs a dataset iteratively by drawing samples from the group with highest upper confidence bound (UCB) for the predictive risk of the current classifier. At each iteration, the classifier is retrained (updated) on the extended dataset, and the process is repeated until a sampling budget is exhausted. The authors provide theoretical bounds for the convergence of the algorithm, which are proven to be tighter than those of previous $\epsilon$-greedy approaches.
main_review: [Overall]
- *Originality*: The proposed methods and theoretical results are, to the best of my knowledge, novel.
- *Quality*: The paper seems technically sound, and the theoretical analysis is thorough with interesting results. The experimental results, however, are less encouraging. 
- *Clarity*: While the paper is well written, the main contributions are not made immediately obvious. Most of the promising results are hidden in the appendix.
- *Significance*: Fairness is a topic of great interest in the machine learning community, and I believe the proposed active sampling approach is a promising avenue to tackle it.

[Strengths]
- I find the idea of combining minimax Pareto fairness with active sampling quite promising.
- The theoretical analysis is thorough and the convergence results are a valuable contribution to the community.
- I appreciate that the authors provided their code in a fairly accessible format.

[Weaknesses]
- The experimental results seem weak. The proposed method does not seem to outperform the previous simpler $\epsilon$-greedy approach and the other baselines, uncurated and uniform, are rather weak.
- The text is well written but not particularly easy to follow. Given the interesting theoretical results, I think the paper would read much better if the focus was put in the theoretical development—with at least sketches of the proofs in the main text—rather than on the experimental results which are not as promising or revealing.

[Further Comments and Questions]
- In Figure 7, the performance of $\mathcal A^+_{opt}$ seems quite promising. Why is it not included in the other experiments?
- I think Assumption 3 should also be stated on the main text.
- I believe there is a typo in line 232 that probably should read '[...] the performance achieved *by* this algorithm cannot in general be improved [...]'.
limitations_and_societal_impact: The authors did not address any potential negative societal impact in their paper. However, given that their methods strive to achieve fairness, I would imagine the societal impact would be mostly positive. The authors do address some of the limitations of their approach, and I do not have anything to add to their considerations.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper proposes an adaptive sampling scheme to construct the training dataset which allows us to learn classifiers that are fair in a minimax sense. They proved theoretical results on the excess risk of their algorithm, and also proposed heuristic extensions of the algorithm to be applicable to real-world large scale problems. They validate their algorithm on a series of synthetic and real-world datasets, showing an improved performance over empirical/uniform sampling schemes, which also verified their theoretical findings. 
main_review: Overall this is a very well-written paper. I especially like the results that the minimax optimal mixture distribution yields a classifier that has equal risk among all attributes. The theoretical analysis is convincing, showing the quality of the solution from Algorithm 1 via the excess risk measure. The supporting examples well illustrate the validity of the assumptions. They also give practical suggestions on what to do when certain assumption is violated, and how to properly modify the algorithm to be suitable for real-world large-scale problems. 

I have a question on Theorem 1, where eq. (5) has this term e_z(N_A). Since A could be any value between \pi_{min}/2 and \pi_{min}, can we choose an optimal A such that the term e_z(N_A) will be the smallest for all z? Also in practical implementations, what is the form of e_z(N) that is used in the UCB (4)?

In Eq. (6), is S_{z_t} calculated as the Mann-Kendall statistic of the accuracy of f_t? That is, replacing the terms X_i, X_j in the expression of S by Acc(f_t)? Does the c_0 term of Eq. (6) account for the uniform deviation term e_z of Eq. (4)? Having var(S_{z_t}) in the denominator suggests that we should draw more samples for attributes whose var(S_{z_t})  is small. But if the accuracy for a certain attribute is already very good (cannot be further improved by drawing more samples), in which case var(S) would be small, drawing more samples for such attributes seems to be counterintuitive?

My major concern in the experimental section is that the performance of \epsilon-greedy seems to be very close to A_{opt}. In Fig. 2 (left), \epsilon-greedy converges even faster (much faster). In Figs. 3 and 4 the greedy algorithm also has a similar performance to A_{opt}. Do these results suggest that \epsilon-greedy and A_{opt} have comparable performance in reality? Can you provide guidance on which one to use?
limitations_and_societal_impact: No. This work is mostly theoretical work on how to design a sampling scheme to drive fair classification. I do not think it is related to any negative societal impact.
review_title: null

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

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

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