Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper aims to design a fair representation learning method. To achieve this goal, the authors have proposed a normalization flow-based method, where an adversarial-based strategy is leveraged to train the model. In the experiments, the authors conducted extensive experiments to demonstrate the effectiveness of the proposed methods. 
main_review: In general, I think the paper is well presented and the organization is good. My major concern is the motivation of this paper, I would like to see why normalization flow is the necessary technique to be the solution to the drawbacks mentioned in existing fair representation learning methods. In addition, the theory seems to be quite straightforward based on PAC learning. If more tailored theoretical analysis can be provided, I think the paper can be more interesting. While I have the above concerns, the technique part in this paper is sound, and I cannot find large mistakes, thus I vote for a weak acceptance.
summary_of_the_review: Interesting paper, which however can be further improved.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors propose fair representation learning using normalizing flows. The basic idea is to learn a separate normalizing flow for each protected group. These flow distributions are equalized and hence cannot be used to determine the protected group. The authors argue that improved fairness guarantees can be achieved compared to adversarially fair learning.
main_review: [Strengths]
- Normalizing flows are a flexible tool to disentangle the predictive information and sensitive attributes from the data.
- The idea of using normalizing flows for fair representation learning is interesting. The formulation of the learning problem is natural and practical.
- The presentation of the paper is clear.

[Weaknesses]
- The proposed method applies to only a binary protected attribute. To generalize to a discrete protected attribute, we would need to learn a separate flow for each value. However, equalizing all these distributions is not straightforward as the symmetric KL can no longer be used.
- I think the proposed method can sacrifice accuracy for fairness. Suppose that the label is a function of the input distribution, normalizing the input distribution could also remove the predictive information. The authors use a parameter \gamma in the loss function to balance fairness and classifier utility; however, this is not sufficient to attain a good tradeoff in terms of Pareto optimality.
- In the empirical evaluation, the authors used different density functions, i.e., RealNVP, MADE, and GMMs, for different datasets. This led me wonder if some of the densities do not perform well on certain datasets. For a fair comparison, it could be helpful to provide results for all the densities.

summary_of_the_review: The idea of the paper is clear and interesting. It appears that the proposed approach only supports a binary protected attribute. The empirical evaluation could be strengthened by providing results for all the density functions.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This work proposes using normalising flows to obtain a latent representation of the data that is trained to minimise a surrogate of an MMD [3] based statistical distance used to measure adversarial accuracy when classifying protected features. All this whilst preserving the desired properties of the original features. The authors motivate using normalising flows arguing it allows to compute an empirical estimate of the aforementioned statistical distance which they claim has strong convergence guarantees. 
main_review: 
General Suggestion:

It feels like the type of estimation results you are trying to obtain are very similar to prior works in non-vacuous generalisation bounds for DL. I think the authors work would benefit a lot from reading prior works done for DL/Generalisation such as [1,2] and use these to obtain a correct and computable alternative to that of theorem 5.1. Which as it stands is incorrect. I would be happy to modify my score subject to obtaining a valid result here and recomputing the estimate of the statistical distance across all experiments. 

Questions to the Authors:
1. Where do you use $p(z)$ explicitly in your proofs/ algorithms ? There seems to be a big selling point on this; however besides theorem 5.3 I don't see a need for explicitly needing $p(z)$ , most of the other two claims 5.1 and 5.2 just require its existence but not its closed form.
2. As I mentioned the theory seems to be mostly estimation guarantees, you don't seem to be making a theoretical claim on bounding the fairness metrics themselves. Please clarify this.

Detailed Comments/Corrections: 

1. Aesthetic: Maybe it's common in this community but using mathcal on a capital letter typically denotes a set\space (for example a set of functions) it's distracting\unhelpful to see it being used for a distribution.
2. Missing a $dz$ in Eq 4, \mu is a function not a measure. I would also suggest using f or g rather than \mu as in [3], since mu is incredibly commonly used for mesures, again this makes Eq 4 distracting/confusing at a glance.
3. Page 5: “However, for such models, given densities $p_0(x)$ and $p_1(x)$ over the input space, it is intractable to compute the densities $p_{Z0} (z)$ and $p_{Z1} (z)$ in the latent space as many inputs $x$ can be mapped to the same latent $z$”  . It could help the reader if you could be more explicit here, it seems the claim is that you can't carry out a change of variables to compute $p(z)$ because the inverse function theorem does not hold for most NN encoders and the Jacobian is not defined. 
4. The Pinsker inequality bounds total variation not MMD. Please revisit MMD literature and use the appropriate bound / connections to KL/OT etc. If you can correct this (or correct me) I am happy to take this point back. Atm it really questions the KL motivation in Algorithm 1, you yet haven't shown that you are minimising a surrogate of the statistical distance. Additionally please translate this into a remark or a lemma so it stands out, as you can see from some of the reviews its easy to miss.
5. Why train a symmetrised KL while Pinsker's inequality is regarding KL ? there's no explanation for this when it is introduced. This needs justification why a symmetrised KL?.
6. Second instance of $\mu=1$ is a typo on the discussion of optimal adversary at the end of page 1 should be mu=0.
7. Lemma 5.1 : If we assumed the claim was right it would be a very vanilla concentration / CLT like type argument simply arguing that your empirical estimator of the statistical distance has nice convergence properties. This does not rely on flows and it doesn't give any theoretical arguments on how the authors approach results in a small adversarial accuracy. It does allow for empirical arguments of the adversarial accuracy to be made in probability but the authors would have to provide a delta column in all their experiments + estimated confidence bounds on their delta error too, which they haven't, this would give theoretically backed empirical estimators of the adversarial accuracy which would be a good contribution on its own , however this is currently lacking..
8. Lemma 5.1 should be written in a form similar to this for all  $\delta>0, P\left(\mathrm{err } < \frac{1}{\sqrt{n}} * \sqrt{\ln(2/\delta)} \right) \geq 1 - \delta$ so that it is clear to the reader what type of convergence rate you are showing. See theorem 1.1 in [2] for example.
9. Proof of Lemma 5.1 is abusing notation interchanging densities and measures (distributions). Again I would like to highlight that I am not sure what purpose the calligraphic Z notation has.
10. The proof for 5.1 has a misstep. Detail on the misstep : After applying the triangle inequality you distribute the sup over the 3 terms. You then use the definition of MMD and substitute the sup/expression in the middle term. However you also remove the sups from the 2 other terms leaving $\mu$ completely undefined. This does not even compile / type check as a proof. To apply a Hoeffding type bound on a sup you need to have the size of the hypothesis space and apply it via a union bound, as your inputs are real and your hypothesis space infinite this does not work so you go into VC-dimension type of bounds which are vacuous for neural nets. In the end what you need here is a PAC Bayes (e.g. [1,2] ) style of bound which has significant interpretation. In short you cannot apply Hoeffding's inequality over a sup like this. You could rectify this but it will be a different theorem. I think this could be done within a week so I would be happy to rectify my score if this + points 4 and 7 are rectified.
11. Looking at the proofs for Lemmas 5.1 and 5.3 I am really unconvinced that the flows are a necessary part of the proof ? All you require for these is to assume that the p(z) densities exist but at no point are flow properties used. In short the two provable guarantees you have provided apply to normal NN encoders too, the difference being that using flows will allow computing these statistical distances ?
12. The notation  $(..)dx = (..)dz$ is a bad heuristic and prone to errors please rectify this by carrying out the change of variables on $\int |p(x) - \hat{p}(x) | dx$ explicitly  pushing the jacobian determinant into the abs and applying the definition of p(z). Whilst the step/result is correct its very prone to mistake using heuristics with infinitesimals (imagine if we were looking at TV between $p_{N_1}(z)$ and $p_{N_0}(z)$ we wouldn't be able to apply the same heuristic here). Please correct this.    
13. Lemma 5.2 seems to be used to motivate the weighting with gamma in Algorithm 1. That is: minimising the statistical distance (which is minimised surrogately so by minimising sym-KL) can lead to this “shuffling” which in turn will decrease classification accuracy and thus we have this gamma-tradeoff heuristic. I feel this lacks clarity. It's important to emphasize that this has nothing to do with the “provable guarantees” . I would argue it's more of a remark/observation that informs/motivates a sound heuristic. Please clarify.



[1] Dziugaite, G.K. and Roy, D.M., 2017. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv:1703.11008.

[2] Dziugaite, G.K. and Roy, D.M., 2018. Data-dependent PAC-Bayes priors via differential privacy. arXiv preprint arXiv:1802.09583.

[3] Gretton, A., Borgwardt, K., Rasch, M., Schölkopf, B. and Smola, A., 2006. A kernel method for the two-sample-problem. Advances in neural information processing systems, 19, pp.513-520.


summary_of_the_review: Pros:
1. The goal of this work is very well motivated and much needed.
2. The authors provide a very nice illustrative example clarifying and motivating the need for these methods.
3. In general the authors do aim to motivate every algorithmic choice with some backing from theory which is a very nice structure/writing style.
4. Overall I do think the general direction the authors aimed to go in is very exciting and has a lot of promise. However in this current iteration it is lacking technical strength (both experimentally and theoretically).

Cons:

1.Unfortunately much of the theory the authors use to motivate design choices seem to have mistakes (Proof of Theorem 5.1 is incorrect, the usage of Pinsker’s inequality also seems wrong)

2. Because of the aforementioned error with Pinsker’s inequality  (it bounds TV not MMD) it's not clear if the KL based objective (as a surrogate to the statistical distance) is well motivated.

3. Not very safe heuristics are used in proofs (e.g. equating infinitesimals) ; this is prone to mistakes.

4. The use of normalising flows seems to be only used in theorem 5.3 ? 

5. Finally the claimed theoretical results are “estimation guarantees” the way the introduction and abstract are worded seem to indicate that the theoretical results guarantee fairness for a given family of models, that is the way this work is selling itself seems to claim a bound on the true statistical distance. However that is far from the case, instead this work tries to prove that said distance can be estimated “very well” empirically. Thus all experiments in this work should be estimating this quantity as any success statements regarding fairness rely on such empirical estimates and there are really no theoretical guarantees on the fairness aspect of the method itself, it's more like there are theoretical guarantees on the evaluation of the method.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: Given input data $x$, target $y$, and a binary sensitive attribute $a$, this work undertakes the task of learning a representation of $x$, call it $z$, such that a classifier $h$ can perform well using $z$ while at the same time no adversary $g$ can predict $a$ well from $z$. 

This is accomplished by minimizing, see Algorithm 1,  
$$
\gamma \frac{1}{2} D_{KL}(p_{Z_0} || p_{Z_1}) + (1-\gamma) \mathcal L_{clf}.
$$
This operation is possible because 1) $p_0$ and $p_1$, the distributions of $x$ for $a=0$ and $a=1$, respectively, are presumed to be given or readily estimable, and 2) the latent $z$ is obtained by normalizing flows $f_0$ and $f_1$ applied to $p_0$ and $p_1$, respectively. 

Supposedly this optimization problem results in latent representations $z$ that ensures the statistical distance/MMD $\Delta(p_{Z_0}, p_{Z_1})$ is small so that in turn the maximum adversarial accuracy is small.
main_review: Strengths of the paper
+ The paper considers the relevant task of learning fair representations
+ The issues with learning fair representation via adversarial training are explained well

Weaknesses of the paper
+ Algorithm 1 is incomplete. No details are given about $\mathcal L_{clf}$. Shouldn't we be updating the parameters of the classifier $h$ in Algorithm 1? 
+ There is no connection between Algorithm 1 and the various theoretical results given in the paper. You must show that minimizing $\mathcal L$ in Algorithm 1 ensures that $\Delta(p_{Z_0}, p_{Z_1})$ is small so that in turn the maximum adversarial accuracy is small. This is not obvious since $\mathcal L$ in Algorithm 1 also contains $\mathcal L_{clf}$.
+ The scalarization scheme employed in Algorithm 1's loss function $\mathcal L = \gamma (L_0 + L_1) + (1-\gamma) L_{clf}$ is well known to be the most naive, and ineffective scalarization technique in multi-objective optimization. A proper application of multi-objective optimization techniques will produce far more interesting trade-off curves than what's seen in Figure 4. Good references are "The Fairness-Accuracy Pareto Front" by Wei and Niethammer and "Pareto Multi-Task Learning" by Xin et al.
+I won't be the only one pointing this out, but here goes: a big weakness of the paper is the assumption that $p_0$ and $p_1$ are known. I do note that you reference several fairness papers at the end of Section 5 that have apparently "successfully" employed density estimation. But this isn't even my biggest concern. Again, I am afraid that too many uncontrolled approximations are made along the way. It is worth highlighting that $\mathcal L$ in Algorithm 1 does not even contain $\Delta(p_{Z_0}, p_{Z_1})$, but rather the symmetrized KL-Divergence between $Z_0$ and $Z_1$ which is simply not the same as the statistical distance between $Z_0$ and $Z_1$. 

Minor questions
+ Why use the term statistical distance and not MMD?
+ According to the Background (Section 3), $y$ is binary. Consider replacing throughout the expression $E(y=h(x))$ with simply $P(y=h(x))$. 
+ In the left panel of Figure 2, consider adding different symbols to illustrate the two classes $y=0$ and $y=1$. Also consider coloring the $(x_1,x_2)$ region according to the classifier $h(z)$ where $z$ is as given in Section 4. 
+ In figures such as Fig 4a and 4b, consider adding the value of $\gamma$ above each point.
summary_of_the_review: Much fuss is made about controlling the statistical distance between the latent representations $z_0$ and $z_1$. This is justified because controlling the statistical distance amounts to controlling the maximum adversarial accuracy and additionally gives guarantees on demographic parity and equalised odds for any downstream classifier $h$ that uses $z$. 

However what is actually implemented in Algorithm 1 has no clear connection to controlling the statistical distance between $z_0$ and $z_1$. This feels like a sleight of hand to me. Certainly none of the theory supports Algorithm 1's ability to control the statistical distance. Furthermore no careful thinking is given to the tradeoff value of $\gamma$ in Algorithm 1.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a representation learning technique for fairness called Fair Normalization Flows (FNF) with theoretical guarantees on the maximum-possible unfairness. The key idea is to train encoders that map input samples of two sensitive groups into a space where the two groups become indistinguishable in terms of statistic distance (=maximum mean discrepancy) without significantly sacrificing accuracy. FNF minimizes the KL divergence between the converted distributions of the groups, which is an upper bound of statistic distance. In comparison to previous approaches that use adversarial training, FNF does not have instability issues when solving a non-convex problem. In addition, FNF has interpretability and transfer learning functionalities, which other fair representation learning techniques lack. Experiments show that FNF ensures fairness while retaining high accuracy for various real datasets and outperforms other adversarial training baselines.
main_review: Strengths

* Fair representation learning with theoretical guarantees for fairness is a significant contribution.
* The algorithm for training the encoders and minimizing the KL divergence is straightforward and practical.
* Even if the probability distribution of the input data is not known, density estimation can be used.
* The invertible encoders can be used for interpretation and transfer learning purposes.
* Experiments are extensive and show how FNF outperforms adversarial training baselines and suggests upper-bound performances of any adversary.

Weaknesses

* Most of the analyses focus on the fairness guarantee, but there is not much explanation on why the accuracy does not degrade much. The experiments are extensive enough (including the ones in the supplementary), but it is still not clear why FNF should have less accuracy tradeoffs than adversarial training baselines in general. I suggest the authors also show the Figure 4 results for adversarial training.
* In Section 2, Gupta et al. (2021) is mentioned as a relevant work, but is considered inferior due to its monotonic nature of bounds. However, it would be interesting to also see any experiments whether FNF actually outperforms this approach.
* In Page 6, how tight is the bound of the square root of KL divergence for statistical distance? FNF's performance seems to largely rely on this tightness. 
* In Algorithm 1, there should be some discussion on when to stop the learning. That is, how can one set $N$?
* Minor comments
   * In Page 7, Figure 4 seems to appear too early. The description is in the next Page 8, which is confusing. In Page 8, Table 1 also appears a bit too early.
   * The experimental setting for Table 1 is not clear. Which datasets were used and were the results averaged?


summary_of_the_review: The paper makes significant contributions by proposing a fair representation learning technique with theoretical bounds. The paper can also be improved by better explaining the accuracy results and adding some more details of its techniques and experiments.
review_title: null

Meta-review: This paper addresses fair representation learning, with the aim of obstructing the recovery of sensitive features from the learned representation, hence enforcing the fairness of subsequent prediction tasks.  In the setting where probability density can be estimated for sensitive groups, Fair Normalizing Flows (FNF) tries to minimize the statistical distance between group-wise latent representations, thereby providing theoretical fairness guarantees.  Experimental confirm the effectiveness of FNF in fairness, transferrability, and interpretability.

The paper received extensive and in-depth discussion.  The rebuttal did an excellent job in clarification.  Although there are still some concerns on the theoretical properties of the optimal solution, overall the reviewers and myself find this paper interesting and worth publishing.
Decision: Accept (Poster)