Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper aims at the task of bounding and approximating intersectional fairness, with a main motivation of cases where multiple protected attributes exist, and a finite training from which such approximation of the statistical fairness criterion could be difficult due to scarcity of datapoints for marginal subsets which are the intersections of such variable values. The paper establishes theoretical bounds, connecting marginal fairness (for varying, single, protected attributes) and intersectional fairness, by using a measure of total correlation. Namely, the idea is to bound how far the product of the marginal measures is from being independent (across the different protected attributes), and use the bound to upper bound the intersectional measure. The paper establishes these bounds as a function of the mutual information between the made predictions and the protected attributes, and as a function of the standard deviation of the total correlation measures. The bounds serve as an inspiration then for a proposed heuristic approach for estimating the intersectional fairness, which is based on greedy selection of groupings of protected attributes, which minimize the distance from independence using the bounds, allowing for better estimation. The paper ends with an evaluation of the proposed scheme on US census data from 1990, as well as on synthetic data.
strengths_and_weaknesses: Originality:
Strengths:
1. The theoretical bounds, connecting intersectional fairness to marginal fairness, decomposing the problem in terms of the dependence between the protected attribute are interesting, and give conceptual insight, as well as estimation (upper) bounds that rely only on the total number of samples (not the marginal).
2. The proposed attribute grouping-based heuristic compares favorably with prior work (using a Dirichlet prior).

Quality:
The results in the paper seem to be well supported, though I have only glanced at the appendix. The relevant related work is mentioned, and code is attached in the supplementary file.

Clarity:
The paper is mostly well-written. The experiments section, and the description of the results were a bit difficult to interpret and could be improved.

Significance:
Strengths:
The problem in question is highly motivated. The ability to give reliable statistical estimation of intersectional fairness with finite data is important and could have practical implications. The proposed greedy heuristic based algorithm of grouping seems to compare favorably with formerly proposed methods.

Weaknesses:
It is, however, still not completely clear to me how useful are the established upper bounds in practical scenarios. Please see "questions" section of my review.
questions: 1. In Theorem 3.2, for the bound on \eps_1^', inside the log parantheses, what are the variables for which the probabilities are taken?

2. I wonder, how effective are the established upper bounds in terms of bounding the intersectional fairness from a finite sample? There is no illustration or provided examples which could be helpful in assessing the significance of such bounds in practice. Should we only expect the upper bounds to be meaningful when protected attributes are very close to being independent?
limitations: 1. There is no discussion of the limitations of the work in the main body of the paper. I would expect to see a more elaborate one in the summary.

2. Effectiveness of theoretical bounds - please see in the "questions" section.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper presents new methods to approximate and bound intersectional unfairness. Intersectional fairness is connected with marginal fairness with the mutual independence and conditional independence of protected attributes given predictions. Then the dependence conditions are relaxed via the quantification of total correlations and their variance. A grouping technique is provided to relax the mutual independence of A to the dependence of groups of A. The experiments compare the approximation gaps and show the effectiveness of proposed approximations.
strengths_and_weaknesses: - The motivation is simple and clear.
- The proposed approximation connects intersectional farness and marginal fairness through independence. The new approximation and relaxed version are easy to calculate with known techniques.
- The grouping technique shows another relaxation direction.

--- 
- The mutual independence and conditional independence imply no more than one protected attribute is correlated with Y. Let one start with A={A_1, A_2, ... A_d} and let \hat{Y} = f(A_1, A_2, ... A_d, X). The graphical representation is A1, A2, ... A_d, X -> Y. Given A are mutually independent and the definition of d-separation, the protected attributes cannot be conditionally independent. In another word, mutual independence, conditional independence, and \hat{Y} = f(A_1, A_2,... A_d, X) cannot be achieved simultaneously. Theorem 3.1 & 3.2, as well as u_{ind}, are based on this independence assumption. It is unclear whether they are affected by the prediction function \hat{Y} = f(A_1, A_2,... A_d, X).  A straightforward impact I see is s^* cannot be zero unless no more than one protected attribute is used for prediction.

- Thm 3.2 connects u* with an upper bound containing u_{ind}. There is an intuitive relationship between u* and u_{ind}, but it is unclear why it seems **natural** to propose u_{ind} as a good approximation in theory. In another word, the relationship between u* and u_{ind} is unclear in general settings.

- Sec 4.2 and Algorithm 1: it is unclear why small s^* leads to small |u^q_{ind} - u^*|. Given that \epsilon_1 is an upper bound of u*, the relationships between u_{ind}, s^* and u* are still unclear.

- The notations are really difficult to follow. I suggest the authors revise the notations and fix typos, e.g. u_k(y, a, a') in Eq (6), A_i in Eq (25).

questions: NA
limitations: - The motivation is very clear. But there are too many uncertainties between u* and u_{ind}. The major concern is that the relationship between u* and u_{ind} is unclear to me in general.

- The work would be complete if it shows how the approximation is used for intersectional unfairness elimination.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies how to estimate intersectional fairness when there are a large number of protected attribute combinations. The paper first show that if the protected attributes are mutually independent and mutually independent conditionally on the prediction, the intersectional fairness can be easily computed from the marginal fairness. Then, the paper relaxes the independent assumptions and provides bounds on probable intersectional fairness. After that, the paper offers a bound directly on the intersectional fairness. The idea is to find a partition in order to get closer to the independence conditions so that the intersectional fairness computed under the independence assumptions could be a good approximation. Experiments using real-world and synthetic data show that the proposed bounds are more reliable than the Bayesian estimator.
strengths_and_weaknesses: Strength

This paper systematically studies the bounding and approximating of intersectional fairness through marginal fairness. It provides a sufficient condition for accurately computing intersectional fairness from marginal fairness. Then, it provides both probabilistic bounds and hard approximations of the intersectional fairness, which are easily computable from the data. 

Weakness

The paper does not provide a convincing example showing why ensuring intersectional fairness for a very large number of subgroups (e.g., 100 subgroups) is a meaningful and practical requirement for decision-makers. Although this paper studies the measurement of fairness not the achievement of fairness, the measurement is meaningful only when we have the requirement to achieve fairness.

There are too many notations, which make the paper difficult to follow.

questions: 1.	Are u^q_ind upper bounds or lower bounds? Or both cases are possible? In that case, why is u_ind in Figure 1 constantly smaller than u*?

2.	Are epsion_1 and epsilon’_1 upper bounds? What is epsilon* in Figure 1? Any explanation of why epsilon* is smaller than u*?

3.	The authors said that the proposed approach will enable the use of the approximations to penalize classifiers in order to train intersectionally fair classifiers. Is that possible to include some discussions about the differentiability of the proposed method that is necessary for the approximations to be integrated into gradient-based optimization? 

limitations: Yes.
review_title: null

Meta-review: metareview: This paper focuses on intersectional fairness in supervised learning, specifically on understanding the relationship between ensuring fairness on one particular sensitive attribute and on the intersection of those attributes.  A largely analytical paper, bounds are given relating the latter to exact guarantees on the former.  Reviewers took minor issue with the experimental validation and with the applicability of these bounds; I agree with the former, but do not agree with the latter.  This work adds a nice building block to the foundations of fair ML research.
confidence: Less certain
Decision: Accept