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.
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.