Learning Fair Representations with High-Confidence Guarantees

1. The overall framework seems quite similar to the Seldonian algorithm design of Thomas et al. (2019), e.g., see Fig. 1 of Thomas et al. (2019)). Although it is true that Thomas et al. (2019) only considered fair classification experiments, as mentioned in this paper's related works, the proposed FRG also has an objective function related to the expressiveness of the representation, and some of the details even match; for instance, the discussions on "$1 - \delta$ confidence upper bound" on pg. 4 are quite similar to the caption of Fig. 1 of Thomas et al. (2019). Then, the question boils down to what is the novel contribution of this work, and my current understanding is that this is a simple application of Thomas et al. (2019) to fair representation learning. Of course, there are theoretical analysis, practical considerations and good experimental results that are specific to fair representation learning, but I believe that (as I will elaborate below) there are some problems that need to be addressed. Lastly, I believe that Thomas et al. (2019) should be given much more credit than the current draft.
2. Although the paper focuses on the high-probability fair representation construction (which should be backed theoretically in a solid way, IMHO), there are too many components (for "practicality") that are theoretically unjustified. There are three such main components: doubling the width of the confidence interval to "avoid" overfitting, introducing the hyperparameters $\gamma$ and $v$ for upper bounding $\Delta_{DP}$, and approximating the candidate optimization.
3. Also, the theoretical discussions can use some improvements. Although directly related to fair representation, the current theorems follow directly from the algorithm design itself and the well-known property of mutual information to $\Delta_{DP}$. For instance, I was expecting some sample complexity-type results for not returning NSF, e.g., given confidence levels, what is the sufficient amount of training data points that would not return NSF.
4. Lastly, if the authors meant for this paper to be a practical paper, then it should be clearly positioned that way. For instance, the paper should allocate much more space to the experimental verifications and do more experiments. Right now, the experiments are only done for two datasets, both of which consider binary sensitive attributes. In order to show the proposed FRG's versatility, the paper should do a more thorough experimental evaluation of various datasets of different characteristics with multiple group and/or nonbinary sensitive attributes, trade-off (Pareto front) between fairness and performance (or any of such kind), even maybe controlled synthetic experiments.

Summary. Although the framework is simple and has promising experiments, I believe that there is still much to be done. In its current form, the paper's contribution seems to be incremental and not clear.

Unfortunately, in its current state the paper falls short both (partially) on the experimental and, especially, on the theoretical side; this is why I cannot recommend acceptance now (and I think that too significant of a revision would be necessary to shift this opinion in this submission cycle).

(1) The paper prominently promises to conduct a theoretical analysis of their framework. Now, the framework itself is nothing but the proposal to take a bound recently proved in Gupta et al (2021), which bounds a certain function of the demographic parity error by the mutual information between the sensitive attributes and the representation, and reformulate it into a PAC-style guarantee on the demographic parity. After that, the authors note that since the bound of Gupta et al (2021) would be hard to estimate head-on (since estimating the mutual information term I(Z; S) is hard), it should be estimated in a surrogate, more conservative way, at which point they summarize several proposals for how to do that from recent literature and pick their favorite ones to be implemented in code.

Thus, given that the entire theory behind the framework has already been developed --- the main bound on the demographic parity over all downstream tasks in Gupta et al (excluding reformulating their guarantees in a PAC-style way), and the surrogate bounds on the mutual information in Song et al (2019) --- the current paper does not bring anything to the table in that regard: neither any novel surrogate bounding approaches nor any tighter theoretical guarantees that, like Gupta et al, would hold for all downstream tasks. Also, the discussion is purely restricted to demographic parity, and does not consider any other measures of unfairness, simply because that is where Gupta et al's bound applies.

(2) Given the above, the paper cannot be considered as providing a theoretical contribution to the field, so in that case it should have provided a fairly comprehensive set of experiments; if that was the case, then the abstract to the paper could have potentially stated, "We provide a set of experiments verifying the empirical usefulness of the bounds in Gupta et al in settings X, Y, Z, ..." However, the set of experimental tasks is too far from comprehensive: it consists only of two datasets; with representations generated only through a specific natural VAE-based approach; and compares to only 4 baselines (three that promise fairness and a vanilla no-fairness VAE representation).

In particular, the authors (see Appendix J) exclude methods with clearly related goals --- such as Jovanovic et al (2023) --- on the basis, eg, that while the proposed framework gives guarantees for varied representation models and all downstream tasks, these other models include additional restrictions. Despite these additional restrictions --- often quite benign, such as, eg in the case of Jovanovic et al, requiring the representation to be discrete-valued --- the several related works listed by the authors in Appendix J are in my view quite pertinent, and should be examined, to at least give confidence that the proposed framework does not suffer losses that are too significant in exchange for "provable guarantees", and that, conversely, there are settings where these other works' proposed methods do in fact fail to provide similar fairness guarantees to the proposed method.

But also, of course, it is important to consider other representation learning models than VAEs, as well as significantly more varied/nontrivial tasks than just Adult (e.g. Folktables, and other datasets), to test the robustness of this paper's empirical conclusions.

3. The paper's writing level is overall minimally sufficient, but not quite there --- simple points like defining PAC-style guarantees and converting existing bounds into them are dwelled on for quite long in the main part, but meanwhile, important considerations such as which surrogate bounds to use, as well as experimental details, are only to be found (in scattered fashion) throughout the appendices. Moreover, some important quantities are not even formally spelled out --- eg the first surrogate bound of Song et al, which is prominently used by the authors, is just denoted by I_1 and never defined in detail in the scope of the paper.

The central component of this framework relies on the result by Gupta et al. (2021), where the authors utilize existing upper bounds. This makes the evaluation of the paper necessarily focused on (a) the specifics of the framework, (b) the theoretical results, and (c) the downstream outcomes.

While I attach my questions below on both (a) and (c), my main criticism is as follows. The authors build a framework on an upper bound of an upper bound of the quantity of interest, which is further adjusted in the opposite direction with a multi-parameterized and data-dependent constant. They employ a representation checking system in which quantile estimation is arbitrarily doubled to prevent overfitting. Consequently, FRG yields downstream models with minimal predictive power (0.5 AUC, akin to random algorithms), raising concerns about its practical applicability. Given that the paper is primarily presented as a practical tool, I view these issues as potentially significant obstacles.