Balancing Fairness and Accuracy in Data-Restricted Binary Classification

Although the use of VQ is interesting, it is poorly motivated in the introduction. Also, it would help including some references that study the trade-off.

Misuse of terms like score and predictive equality.

I think the method could be stronger as a post-hoc method. Compare to Hardt et al (2016) who make a randomized decision based on (\hat{Y}, A), where $\hat{Y}$ is unconstrained classfier. Essentially, they treat all elements in each of four groups $(\hat{Y} = y, A= a)$ equally. Your method can allow to cheaply push it forward, making the decision depend on $X$ as well.

W1 - The statement 'Law and Adult datasets exhibit a tension in pairings with EA, while pairings with DP are more easily satisfied' calls for a deeper exploration into the underlying reasons. It's essential to investigate the dataset characteristics, including the distribution of class labels and other relevant factors, to understand why this tension arises. Moreover, it's important to analyze the mathematical implications of each fairness notion in the context of these datasets. What does it mean for a dataset to satisfy DP, and what about EA? Furthermore, exploring why certain fairness pairings are more compatible than others is crucial.

In the case of 'For example, strictly satisfying EA+PE causes an accuracy reduction of 3% between the awareness and unawareness situations for the Adult dataset. However, for the Law dataset, strictly satisfying EA+PE leads to an accuracy drop of 10% between the awareness and unawareness situations,' it's imperative to provide an in-depth explanation for these disparities. While you present numerical results stemming from the optimization problem, supplementing this with a detailed rationale is essential. This work can greatly benefit from utilizing the proposed mathematical framework to shed light on these questions. This ability to provide insights into why certain outcomes occur is a key strength of your research.

I firmly believe that the paper should not only present numerical results but should also delve into the reasons behind these results. Offering a comprehensive explanation supported by the mathematical framework is what can truly enhance the quality and depth of this work. This is particularly significant for a paper seeking publication in this conference, and your research indeed possesses the tools to provide such valuable information.

W2 - The authord have overlooked a significant paper that explores the Bayesian-optimal classifier under fairness constraints [1]. It would be beneficial if the authors could consider a comparison between their fair Bayesian oracle and the approach presented in this paper in the experimental section.

W3 - You've omitted the fairness notion that demands parity in positive predictive value, a well-known concept that often conflicts with the notion of equality of odds. It would be of great interest if you would also consider this definition inside your analysis.

W4 - I understand that space constraints can be a challenge, and I believe that the decision to place the cases where S is available in the Appendix, thus prioritizing a robust introduction to provide context and adequately introduce the problem formulation and setting, is a prudent choice. This approach is particularly valuable given that the primary paper addresses the more complex scenarios (when access to S is not available). However, it would be beneficial to provide a brief description of these shorter sections in the main text. In the event of acceptance, the authors could utilize the additional page provided to incorporate these sections into the main text. These could be presented as special cases, which are comparatively simpler, within the framework mentioned in the primary paper.

W5 - The authors opt for $\lambda = 15$ and $\beta = 25$ as parameter values (Section 4.2.), but they do not present alternative results based on different parameter selections. Furthermore, they do not provide an explanation for their choice of these values or an assessment of the impact that varying these values may have on the results. In other words, there is a lack of exploration regarding the sensitivity of the results to changes in these parameter values.

W6 - It remains unclear, and there is a lack of in-depth analysis regarding whether achieving decorrelation consistently results in minimal accuracy trade-offs, or if specific dataset configurations are required for this to hold true.

W7 - Page 4 typo → ‘subscripts (subscripts)’

[1] Zeng, X., Dobriban, E., & Cheng, G. (2022). Bayes-optimal classifiers under group fairness. arXiv preprint arXiv:2202.09724.

1. This paper aims to investigate the tradeoff between accuracy and combinations of fairness criteria, and the study is carried out by plotting the achievable tradeoff on several datasets. However, I fail to grasp the main message from the results.

   • What are the key observations? Are the observations universal or data dependent?
   • Most importantly, in which scenarios would the cost of fairness (i.e., tradeoff) be small/large? I do not think this question can be answered without a theoretical study, e.g., as done in Hardt et al. (2016) and Zhao and Geoffrey (2022).

2. I do not see the practical implications of the results, i.e., how would they "help developers of fair ML models", since the author did not answer the important question of how to achieve the tradeoff in practice.

   How to train a generalizing classifier/score function that attains the plotted tradeoff, not just on the dataset (training set), but on the population (during inference)? Also, how to learn the feature mapping in the "decorrelated setting" without resorting to vector quantization, which introduces approximation error and estimation error that are potentially exponential in the dimension.

3. The use of a generator and vector quantization in the experiments seems ad-hoc and unprincipled.

   • Vector quantization is used to "partition" the input space so that the task of finding a fair representation can be represented as a optimization problem with a finite number of variables (i.e., we are getting rid of complications related to approximation). But quantization introduces approximation error, which means results generated involving VQ do not really capture the fundamental tradeoff. This limitation is also not mentioned.
   • I do not understand the purpose of the generator. Does the generator converge to the true underlying distribution? If not, what is the rate? Also, using the distribution learned by the generator on finite data would introduce estimation error, which is also not discussed.
   • Instead of learning a generator, why not just use simple nonparametric estimators (e.g., KDE)?
   • The authors could have approached this problem from an information-theoretic perspective, see, e.g., "Fundamental Limits and Tradeoffs in Invariant Representation Learning" by Zhao et al. (2022).

Minor: $\mathbf{p}^y$ in eq. (1) is not defined, and the formatting does not conform to ICLR guidelines.

-The first step of the proposed method is forming a discrete approximation of the data distribution using a generator, which is then followed by partitioning the data space. This, in turn, allows the authors to assume that the probability mass on every cell of the partition can be approximated by the probability mass of the centroid of the cell (why?). While I do not quite follow these steps and am confused by it, I don’t even know why these steps are needed in the first place. Standard machine learning approach is to provide guarantees on a data set sampled form a distribution and then appeal to generalization guarantees to get results that hold over the distribution.

-The metric that is used to compare the accuracy of two models (on page 5) seems flawed: according to this metric, if $p^1$ and $p^0$ are equal (all $1/2$ vector), then every two models have the same accuracy, which doesn’t make any sense. The same goes with the way that the fairness notions are formulated. For example, for the case of demographic parity (DP), if $p_a$ and $p_b$ are equal, then the proposed notion suggests that DP is always satisfied. But DP depends on the conditional distribution of classifications, conditioned on group memberships, i.e., we can construct an example for which $p_a$ and $p_b$ are equal but DP is not satisfied. Overall, I am not quite sure if the problem formulation in this paper, in particular notions of accuracy and fairness, are mathematically correct.

-The technical parts of the paper are hard to read mostly because the notations are difficult to parse.

-The discussion of related works is not complete. In particular, Jagielski et al. (2019) (“Differentally Private Fair Learning”) focus on the similar problem of achieving fairness when there is limited access to sensitive attributes. This is a very relevant paper and should be discussed in the related works.