Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: In this paper authors exploit the use of a restricted encoder to derive a provably fair (group fairness) representation which has the ability to upper bound the unfairness of any down stream classifier. They demonstrate this ability through the use of an optimal adversary, i.e., a classifier which tries to predict the sensitive variable given the representation. Such a bound is computable as the restriction in the encoder leads to a finite set of representations.
strength_and_weaknesses: Strengths
-----------
Clear derivations.
Sufficient experimental validation.
Very clear demonstration of the core concepts even for a casual reader.


Weaknesses
---------------
The classifiers used for empirical validation are fairly simple, which might be suitable for the relatively small datasets being used. However using a diverse set of classifiers for empirical validation might be preferable.

clarity,_quality,_novelty_and_reproducibility: Clarity and quality
--------------------------
The paper clearly introduces the problem, provides extensive literature survey related to different aspects of the paper and clearly separates out these references in section 2.
It provides a demonstrative example in Figure 1 which helps the reader quickly understand the main idea.

The empirical and theoretical validation for the proposed technique are very neatly communicated to the reader. The authors motivate the need for provable guarantees and at the same time demonstrate that these do not come with a significant cost in terms of accuracy.

Novelty
---------
The critical contribution of this paper is in the provability of the fairness guarantees for any down-stream classifier operating on the proposed representations. 


summary_of_the_review: This paper contributes to the very critical area of fair representation learning. The extensive literature survey and the clear description of the contributions of proposed technique in contrast with existing literature can make it a very good introduction paper for readers delving into this topic.

The experimental validation could be strengthened by focussing on tasks (at least simulated tasks) where the data sizes are larger. This can allow for the development of more powerful downstream classifiers which might help provide a stronger estimate of accuracy of an unfair classifier and thus the loss in accuracy due to the fair representation.

It would be also helpful if the authors discuss the impact of balance in the training data on the granularity of the restricted representations. It is not uncommon in many domains to be presented with datasets which are highly imbalanced w.r.t. sensitive variables. In such cases Fairness-aware categorical splits could possibly lead to uninformative representations for classification purposes. Adding a discussion on balance of training data would be helpful to readers dealing with such datasets.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes a method to learn fair representations, where the main focus of fairness is the classic demographic parity condition. Compared with existing methods to achieve this goal, algorithmically, the main difference is that, instead of using rich neural networks as the feature encoders, the authors proposed to use decision trees instead. The features are then encoded as the indices of leaf nodes in the decision tree. Theoretically, the main contribution is to provide a finite sample bound on the probability mass function over the feature space, which is estimated from finite samples. 

strength_and_weaknesses: Strength:
I didn't check the most recent literature extensively, but the idea of using decision trees as the feature encoders in learning fair representations appears new to me. 

Weakness:
Although the application of decision trees as feature encoders in learning fair representations is new, this contribution alone is too incremental to grant acceptance into a major conference like ICLR. Perhaps more importantly, there are quite a few statements in the paper are too strong to be accurate. The authors overclaimed the contributions of this work while missing a lot of closely related works that have already provided fairness guarantees for downstream tasks. Let me elaborate.

-   First of all, apparently, the authors appeared to think that the fairness guarantee of downstream tasks from the learned fair representations could only be obtained using the proposed method, but not from existing encoders with neural networks. This is false. No matter what the encoders are, one can always certify a DP gap for any downstream classifiers based on the learned fair representations. To be more specific, the DP gap for any downstream classifiers is given by the TV distance between Z_0 and Z_1. This is a simple consequence of the data-processing inequality for the TV-distance and the fact that the DP gap is nothing but the TV-distance of the predictions over two groups. See [1] Proposition 3.1 for more details. [1] also discusses the relationship between the TV-distance and the optimal balanced error rate, but is missing from the discussion. 

-   In light of the above argument, the real contribution of this work is Lemma 3 which provides a finite sample analysis for discrete distributions using Hoeffding's inequality. However, it still does not justify the "inherent advantages of decision trees as feature encoders". In fact, for any fixed neural network, one can also obtain such high-probability bounds as well by using non-parametric kernel density estimation. The only difficulty here is instead of estimating the probability mass function, which is easier to do because of the finite support, one needs to work with probability density. But in principle it is still doable, and one can then proceed to compute the TV-distance between the estimated density functions from the two groups, which will provide a DP gap for any downstream classifiers over the learned representations. 

-   A lot of the important and closely related works in theoretical understanding of learning fair representations are missing. I would suggest the authors to check the Related Work section of [2] for more reference. 

More detailed comments:
-   In the abstract, the authors mentioned that "motivated by inherent advantages of decision trees". What are the inherent advantages of decision trees here? Wouldn't any encoder that can provide discrete codes work? For example, consider the approach of Zemel et al.'13, couldn't we just use the deterministic cluster assignment (instead of a probabilistic one) as the codes? 

-   In Section 1, "their claim about fairness of the downstream classifiers holds only for the models they considered during the evaluation, and does not guarantee ...". This statement is false. As I explained above, the fairness guarantee on any downstream tasks is guaranteed, and this is just a simple application of the celebrated data-processing inequality. 

-   In Section 2, Paragraph "Towards fairness guarantees", "...trained on the representations produced by these methods could have arbitrarily bad fairness". Again, this is simply false. See [1] and [2]. 

-   Section 4, the discussion of the optimal balanced accuracy is not very deep. At least, one should point out its connection to the TV distance between the two feature distributions (Z_0 & Z_1). See [2] for more details.


[1].    Conditional Learning of Fair Representations
[2].    Fair Representation: Guaranteeing Approximate Multiple Group Fairness for Unknown Tasks

clarity,_quality,_novelty_and_reproducibility: Overall the paper is clear and easy to follow. 

summary_of_the_review: As mentioned in my detailed comments above, due to the limited technical contribution and the missing discussion with closely related works, I would recommend rejection.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: 1. The motivation is to tackle the accuracy-fairness tradeoffs of fair representation learning (FRL), indicating the need of providing provable upper bounds on unfairness of downstream classifiers.
2. They propose Fairness with Restricted Encoders (FARE), the first FRL method with provable fairness guarantees. They restrict the representation space ( i.e., limiting possible representations to a finite set {z 1 , . . . , z k } ) of the (upstream) decision-tree-based encoder.
3. Experiment results on various datasets demonstrate FARE can produce tight upper bounds.

strength_and_weaknesses: 1. Providing provably fairness is significant and useful.
2. The evaluation part is sound.

clarity,_quality,_novelty_and_reproducibility: 1. They claim to be the first to provide provable fairness guarantees for FRL.
2. How tight is the provable upper bound of unfairness compared with maximum unfairness of a given dataset?
3. Could you explain how equation (2) is obtained?
4. For the fairness-aware categorical splits, is rotating the order of categories affecting the split results hence the fairness?

summary_of_the_review: Updated response after the second round discussion: the concern is the likelihood of missing literature of provable FRL and evaluation against such work. I am convinced after the discussion that the paper could be improved with the revision addressing this concern.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: Fair representation learning (FRL) is a popular class of methods aiming to produce
fair classifiers via data preprocessing, but accuracy-fairness tradeoffs are challenging to achieve using the current toolbox.  To this end, the authors develop

- a practical statistical procedure that, for restricted encoders, upper bounds the unfairness of any downstream classifier trained on their representations.
- an end-to-end FRL method, FARE, that instantiates this approach with a fair decision tree
encoder and applies it to augment the representations with a tight provable upper bound on the unfairness of any downstream classifier.

The theoretical results are validated using many comparative experiments.
strength_and_weaknesses: This paper provides an excellent overview of the prior work on FRL, highlighting their strength and weakness.  The FARE procedure is practical and is backed by theoretical guarantees. The numerical experiments confirm its superiority over the competitors.
clarity,_quality,_novelty_and_reproducibility: The authors' contribution is clear and novel.
summary_of_the_review: The authors have developed a practical procedure for FRL, called FARE, with strong theoretical guarantees.  The numerical experiments confirm its promise relative to the alternatives.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes a tree-based encoder for fair representation learning (FRL). The encoder transforms the input data such that downstream classifiers using the transformed data achieve some fairness guarantees. The authors focus on demographic parity as the fairness criterion in binary classification settings.



strength_and_weaknesses: [Strengthes]
1. The proposed restricted encoder is conceptually flexible and could potentially generalize to a large family of models.
2. The objective based on optimal adversary could be useful for several other fair learning problems.
3. Empirical results show that the proposed method attains improved fairness-accuracy tradeoffs than several popular approaches.

[Weaknesses]
- Novelty: the authors claim to provide the first provable FRL upper bound; however, provable FRL has been widely studied in literature:

[1] Donini et al.,  Empirical risk minimization under fairness constraints, NeurIPS 2018

[2] Tan et al., Learning Fair Representations for Kernel Models, AISTATS 2020

[3] Grünewälder et al., Oblivious Data for Fairness with Kernels, JMLR 2021.

The problem setup of the paper is very similar to those considered in the above papers. Thus, novelty of the paper may not be justified without a comparison with the above related work.

- Soundness: the proposed approach makes implicit  i.i.d. assumption for the data and sensitive attributes, and the results rely on the specific choice of the encoder. While the approach conceptually makes sense, the function class of the encoder is typically unknown for deep architectures. Thus, the results, which rely on a perfect encoder, may not hold in general. 

clarity,_quality,_novelty_and_reproducibility: Quality: the theoretical results rely on the choice of the encoder. Theoretical soundness can be improved by explicitly stating those implicit assumptions.

Novelty: comparison with the related work mentioned above is needed to justify the novelty.

summary_of_the_review: I have some doubts regarding the novelty and soundness of the proposed approach (see the comments above).

Questions:
- The related work [1] provides provable guarantees on the demographic parity. How does the result presented in the paper differ from those?
- The restricted encoder is similar to the SDR approach (or sliced inverse regression) described in [2]. What are the advantages of the tree encoder?
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Reviewers were initially split on this paper, but after discussion, it was clear that some of the initial reviews were overly optimistic. Two experts on fair representation learning (RL) were critical of the characterization of this work as "the first provably fair algorithm", and provided several references to support this claim.

For the sake of the authors, I will try to summarize the issue here: This submission is about finite-sample guarantees for a particular algorithm for fair RL. While the authors have (perhaps cleverly) **defined** "provably fair" in this sense, this is not the common interpretation of the word "provable". Other papers about other approaches to fairness have provable guarantees, although they may not be finite sample or about representation learning specifically. It is also unclear if this is the "first", since it is clear that there is existing work with guarantees. I would suggest avoiding this claim altogether given the amount of work in this rapidly growing area. The results are sufficiently interesting without these (over)claims.

Ultimately, I agree that the paper needs another round of major revision before it can be accepted to a top ML conference. At the very least, the framing of this paper needs revision and a detailed comparison against existing work added to the main paper. Adding experiments against existing methods (whether RL-based or not) would also improve the paper significantly.
justification_for_why_not_higher_score: Overclaiming and framing of the paper in light of existing work; needs major revision
Decision: Reject