Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper looks to extends existing work on fairness-arawe learning with continuous attributes/labels by improving estimation of (ideal) regularizer. It proposes an unbiased estimator of a regularizer based on $\\chi^2$ divergence using a variational formulation. It then proposes a set of experiments to illustrate the performance of the method.
main_review: **Core idea**
* Overall, I like the core idea of using a variational approach to obtain an unbiased estimator of the $\\chi^2$ divergence used in previous works (previous estimators not being unbiased).
* I think the paper could focus more on this aspect, in particular, showing how its estimator converges towards the $\\chi^2$ divergence, versus the previously proposed ones (ex: Mary 2019). And this, independently of its use as a fairness regulariser.

**Exposition and positioning**
* I found the paper tends to oversell its results and would generally be improved by a better and more fair discussion of its limitation and comparaison to SOTA. Few examples of imprecise/misleading things:
  * I don't see the need to define a new notion (ERMI), to then explain it is already existing: the $\\chi^2$ divergence between the joint distribution and the kronecker product of marginals.
  * The *non-binary* label/attribute positioning should be more precise, as it means "discrete" rather than "continuous". Indeed, as main SOTA compared in the experiments are designed for continuous label/attributes (Mary 2019, Cho 2020...), this imprecise naming is *misleading*. I was believing the paper treats about the continuous case until Th. 4 (end of page 5).
  * This is even more confusing when the comment after Lemma 1 compares the resulting estimator (for discrete variables) to the bias introduced by *continuous* density estimation methods introduced in (Mary 2019, Baharlouei 2020).
  * Many methods designed for binary variables have strait-forward extensions to discrete variables.
* Thm 1,2,3 show that the $\\chi^2$ divergence upper-bounds some other existing coefficients that characterize independence.
  * Some are coming from the literature, or are strait-forward.
  * I find the statements "ERMI is stronger than MI/HGR" imprecise. It is unclear what "stronger" means. It is an upper-bound, yes. But MI or HGR also characterize completely independence. So I don't see in what sense it is "stronger".
  * I'm not sure these 3 results bring anything to the paper, as the main contribution is not the use of the $\\chi^2$ divergence but rather the variational form to build an unbiased estimator.
* In Table 1: even "while satisfying eod guarantees satisfying eop [...] we only credit those works that provide/implement algorithms for a given fairness notion" -> That mis-characterizes previous work.

**Experimentation**
* Experiments seems OK overall.
limitations_and_societal_impact: See main review
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper proposes a new characterization of the exponentiated (second-order) Rényi mutual information (ERMI). It then uses an empirical version of this idealized characterization as a fairness regularizer. (Many notions of fairness can be written as conditional independence statements, whose approximation can be expressed using mutual information.) The benefit of the new characterization is that the overall optimization can be written as a min-max optimization where the objective function is sum-decomposable. This allows using stochastic gradient descent-ascent to converge to a stationary point. Experimental evidence is given that shows the new approach achieves better fairness-accuracy tradeoff, even compared to prior methods using a different empirical version of ERMI as a fairness regularizer.
main_review: ### Strengths:

+ The characterization of ERMI in a variational form (Theorem 4, maximizer of a quadratic expression) is interesting and could be useful in other situations too. _(originality)_

+ The experimental results seem quite strong, showing clearly that there is merit in this approach. _(significance)_

### Weaknesses:

- There are a couple of issues with the claims. First, Lemma 1 as stated is not correct. It claims that the proposed ERMI estimator (the empirical version of the variational characterization) is unbiased. This is stated without proof, as an immediate consequence of the characterization itself (Theorem 4), perhaps due to the linear expression within the maximizer (if $P_s$ is indeed assumed known.)  While unbiasedness holds without the max, it’s not obvious at all why it would with the max, and very likely doesn’t. Considering this is one of the repeated selling points, it requires an explanation from the authors. _(quality)_

- Second, assuming $P_s$  known or easily learnable from the data sounds reasonable, but considering how much the convergence results hinge on the gradient being unbiased, I’m not sure it can be swept under the carpet that easily. This is particularly important because it’s the _inverse_ of $P_s$ that shows up. The problem can be particularly pronounced when there are many sensitive attributes, some of them observed rarely in the data, and inaccuracy near zero can create a large bias and variance in the inverse of the estimated $P_s$. Considering the paper makes claims of unequivocal convergence to distinguish itself from alternatives, this also needs addressing. _(quality)_

- The presentation is often unnecessarily repetitive, with the effect of selling the paper’s results rather than clearly presenting its contributions. _(clarity)_

- Most of the comparison results between Renyi mutual information and other measures of independence are previously known (Theorems 1 through 3). _(originality)_

### Suggestions:

* In the proof of Theorem 4, `line 607` and `line 608` (second equation) the expression for $W^*$ has swapped matrices. In the end everything works out, so it just needs a clean-up. Also at the end of the proof, you get $D_R + 1$.

* In Lemma 1, once clarified, `line 198` needs also a $\frac{1}{N}$ factor.

* Typos: `line 113` product, `line 119` equalized.

[Edit: Thank you authors for the active discussions. Lemma 1 is now correct, although it's not a lemma but rather a corollary to Theorem 4. The flow makes sense, in that if SGDA targets the min-max expected objective, it's true that the max expected-objective is FRMI, and your samples give you access to unbiased gradients of the min-max expected objective. You need to change references to unbiasedness throughout the paper to make sure this change is properly reflected. The strong experimental results that you have show merit, but  I believe a reworking of the theoretical insight with clarity and modesty will make a better case for the paper. I will leave my evaluation unchanged.]
limitations_and_societal_impact: Societal impact has been discussed through the topic of fairness itself.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors examine the demographic parity, equalized odds, and equality of opportunity fairness constraints, and show that the Exponential Rényi Mutual Information of various random variables related to these quantities is a unifying continuous relaxation of these concepts.  Moreover they show that the FERMI upper bounds Shannon Mutual information, Rényi correlation, and Lq fairness violations. Finally, they claim an unbiased estimator for the FERMI, which seems to be the main advantage of FERMI over (non-exponential) Rényi Mutual information, and with it derive a stochastic gradient descent based algorithm for fair machine learning. Finally they close with experiments showing that FERMI controls fairness with similar effectiveness to prior results.
main_review: This is not the first paper to use FERMI in a fairness context, however here we see more technical rigor, and there are certainly new ideas.
I take issue with a technical points regarding unbiasedness that I would like to see addressed.
I also find the sample complexity discussion quite limited and unsatisfying.
I also have concerns over whether ERMI is chosen for its computational convenience, or its inherent value as a fairness concept. This is not an issue of correctness, but rather a criticism of how significant or relevant this concept really is.
Overall, the paper is good, but unless my concerns can be addressed, I do not think it meets the high bar of a NeurIPS publication.

Unbiasedness:

The discussion around theorem 4 and lemma one I find unsatisfying.  The $P_s$ matrix of course can be estimated unbiasedly from a sample, but this does not necessarily lead to an unbiased estimator.
This is rather like claiming one can derive an unbiased estimator for the variance of sums of dependent random variables. Given the expectation, this is rather straightforward, but without it, even though an unbiased expectation estimator is easily derived, it does not translate into an unbiased variance estimator!
At best, it yields an unbiased estimator for the ERMI with respect to the empirical measure of the sample, rather than the underlying distribution over samples.
This is important for the correctness of their stochastic gradient descent model, but does not have the same importance to the analysis of the overfitting of the model, specifically w.r.t. overfitting to fairness.

Furthermore, no proof of lemma 1 is given, and I am skeptical about any kind of unbiased estimator using a max over matrices $W$ (this seems to be a convex nonlinear operator).  This is not impossible (e.g., the Rademacher average or weak variance), but it is not inevitable (e.g. the wimpy variance) for estimators involving suprema to be unbiased.  I would like to see further substantiation of this claim.

I don't have a problem claiming that we have a convergent or consistent estimator for ERMI, but I want to see all sources of bias and estimation error fully analyzed.



Sample complexity:

I disagree with the statement on 311: “Furthermore, the sample complexity of estimating Rényi mutual information of order 2 (and consequently that of ERMI) scales as Θ( |S|).”  Composition of unbounded functions with the exponential operator does not preserve any definition of sample complexity of which I am aware, and if the range of RMI is |S|, I would conjecture an increase to roughly Θ( |S| exp(|S|) ) to estimate ERMI (or would appreciate an argument as to why this is not the case).  Furthermore, this is all for a single function, and presumably uniform convergence and related techniques would be required to bound ERMI over an entire family. 


Choice of ERMI:

I find the specific use of ERMI a bit unsatisfying and unmotivated. My inference is that it was selected as it leads to a simple unbiased estimator, which was convenient for the SGD algorithm, rather than for its fundamental fairness properties. The claim “We show that ERMI is a stronger notion of fairness violation than... existing notions” is valid, but not necessarily a positive; one could equally well claim it is a loose bound on existing fairness concepts.
While the authors do relate ERMI to various quantities of interest, the relations are not as sharp as one may desire.

In particular:
From a (pseudo)dimensional analysis (technically it’s all unitless) perspective, I do not find theorems 1, 2, or 3 particularly surprising or interesting. The exponential in the exponential Rényi information Mutual information is very powerful, and it is unsurprising that it allows one to bound the remaining (essentially logarithmic) information quantities.
I suppose the results might be interesting when we consider a small range of possible $\hat{Y}$ and $S$, in which case the exponential can't do too much, but in general I would be much more interested in seeing what can be done with (non-exponential) Rényi mutual informations. Theorem one essentially does this, but similar hold for any RMI, theorem 2, I have little insight on but I would be interested in further exploring the idea behind the $|S| = 2$ special case, and theorem 3 in particular seems like there should be some connection between the $q$ and $\alpha$ parameters, or at least a family of similar results for arbitrary $\alpha$, where the square root is a consequence of the $\alpha=2$ choice in ERMI.


Specifics:



In table 1, you make a point that controlling EOD is stronger than EOP, which may harm accuracy.  I agree with this point, however can it not be applied to FERMI in general, as compared to the “less strong” fairness violation metrics you discuss?

Line 39 is a bit of a non-sequitur: measuring degree is important in and of itself, and these estimates are subject to statistical error as well. For hard properties, null hypothesis testing is perfectly valid way of relating samples to distributions, just as tail bounds and sample complexity analyze the statistics of soft properties.
In fact, I would argue that null hypothesis testing arose to answer questions like whether a particular binary property holds on a distribution given a sample. Developing continuous properties analogues of such discrete properties is of orthogonal interest.

71: This is not necessarily a good thing; again EOD, is “stronger than” EOP.

76 Convergence in samples or convergence in computation? I believe the latter but the writing is unclear.

82: Does large-scale mean large training set? If so what does that have to do with minibatch size?  If you mean the size of individual instances, perhaps, but in the practical world, are we not generally memory-constrained by the size of the model?

Line 115 “for brevity” sentence is unclear.



Thm. 1: Stronger is one way to put it, but one could also refer to it as looser. Is there an argument that one should be more interested in the Rényi information itself rather than the Shannon information?


Line 164 remark: I disagree with this conclusion. While it is true that bounding ERMI is sufficient when possible, it may not always be possible to control the ERMI without huge sacrifices to accuracy. I would either need to be convinced that the gap between ERMI and other fairness concepts is small, or that in situations where other fairness concepts are small but ERMI  is large, the model is, in some sense not captured by alternative fairness concepts, deeply unfair.


171: Why call it FRMI rather than FERMI?


*Score raised from 4 to 6 based on author response.*

limitations_and_societal_impact: I express concerns as to the looseness of the relationship between fairness violation concepts, and the resulting impact on model quality (and difficulty of satisfying fairness constraints) in the main review.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper explores fair empirical risk minimization through ERMI regularization. In particular, the paper provides an approach a stochastic algorithm to minimize the regularized objective with convergence guarantees.

Main Contributions:
 - Thm. 1-3: Shows that ERMI fairness violation upper bounds Shannon information, Pearson correlation, and $ L_{\infty} $ fairness violation definitions.
 - Thm. 4: Gives an unbiased estimator of ERMI regularization term.
 - Alg 1. + Thm 5.: Method of minimization which converges.
 - A number of experimental test verifying the theoretical results.
main_review: Overall, the provides a good exploration of fair empirical risk minimization through ERMI regulation. The clarity and structure of the paper is very good, with the progression through theoretical results and then the experiments following logically.

Originality & Significance: The work seems to be significant, with Algo. 1 providing convergence guarantees on for fair empirical risk minimization. Furthermore, the results are experimentally compared to a large number of baselines and performs better despite Thm. 1-3 only giving (possibly loose) upper bounds.

Quality & Clarity: The structure and clarity of the paper is very good. Both the theoretical and experimental results seem to be sound.

Strengths:
 - Thm 1-3 motivate (FRMI obj.) nicely.
 - Alg 1. and its guarantee seems significant.
 - The experimental verification seems extensive. 

Weaknesses/Suggestions/Questions:
 - Line 113: "proudct" -> "product"
 - Experiments (including SI) don't seem to include details of the machine used to run the experiments.
 - Furthermore, a rough runtime comparison between baselines and Alg 1. would be useful to add.
 - I think an informal disclaimer for the differentiability, smoothness, and Lipschitz assumption on $ \ell $ should be added to Thm 5.

Edit:
After quite a bit of reviewer discussion, I have come to the conclusion of lowering my score regarding the paper. The following are my main reasons:

  - I believe that I have overestimated the novelty of Thm 1-3 after some discussions with other reviewers. In particular, Thm 1 is only a minor change from well known results (Sason and Verdu, Eq. (94)) and Thm 3 is Pinsker's inequality with Thm 1. Although having these results being completely novel is not necessary for this paper, these results need additional clarification and reframing with respect to their novelty.

  - I missed the missing assumption / known distribution needed for the unbiased estimator, which is a major technical limitation of the work. I would argue that this assumption is not negligible. Although the authors have mentioned in other rebuttals that $ P_{s} $ "[...] in a certain population is usually public knowledge", I find that this is a rather troubling normative assumption to hold given the nature of sensitive attributes. I do believe that there is an improvement from assuming the joint distribution. However, with this, a detailed discussion of the implication of the assumption (+ its improvement from prior work) is warranted.

 - In addition to the clarification of assumption and the additional comments picked up by other reviewers (e.g., precision of large-scale models), I believe there is a non-trivial amount of restructuring which would be required to clarify the above points regarding related work and contributions.

Overall, I would like to note that I am still positive (high 6) about the paper with its unbiased estimator and strong experimental result despite the flaws listed above.

limitations_and_societal_impact: Limitation and societal impact adequately addressed.
review_title: null

Meta-review: All the reviewers like the variational approach in order to obtain an unbiased estimator for ERMI, and (modulo concerns about the assumption that $P_s$ is known), the revised Lemma 1 does fix the issue with unbiasedness that was highlighted in some of the review. Also, there is agreement that the experimental results are impressive. So, from the method and experiments side, this could make for a very strong paper. However, very unfortunately, there are some significant weaknesses when it comes to a key assumption (which is related to a key selling point of the paper), some of the results not being original as a few reviewers had originally thought, and also some important issues with the current presentation. I stress that this paper can be a strong paper, and it was very close to being accepted, but ultimately the concerns are numerous enough to warrant the review of a new, restructured/revised version of the paper prior to the paper being accepted at NeurIPS. The remainder of this review focuses on the various issues that came out in the reviews and the ensuing discussion.

First — and this was not the most major factor in the decision on this paper — it seems that Theorems 1 and 3 are not novel (I acknowledge that the authors did cite Theorem 2 from Mary et al.). In the discussion phase, some reviewers gave pointers to where these results can be essentially found. For pointers for Theorems 1 and 3, please see the review of 4DYT. For Theorem 2, one reviewer mentioned that it "is already stated in Mary et al. (2019) and derives from Witsenhausen's characterization of Renyi correlation." They also mentioned that the part of the theorem stating that Renyi's coefficient upper bounds Pearson is imprecise, because Pearson's definition does not hold when $S$ is multi-dimensional (which is the case of interest here), and in 1 dimension, the inequality is by definition of Renyi's coefficient. Overall, the lack of novelty of Theorems 1 through 3 is not a severe weakness, but in light of what was already known, some changes to the presentation are in order.

One of the major criticisms is the assumption that $P_s$ is known; there was consensus among the reviewers that this is an important limitation. I especially see this as problematic since (as mentioned by Reviewer 4DYT) this can be a troubling normative assumption and (as Reviewer VsBW mentions) the inverse of $P_s$ is what we need to deal with, and so one needs to be very careful with estimation errors for $P_s$. Still, as the authors mention, previous important related works assumed the joint, and so the authors do operate under weaker assumptions. At a minimum, a detailed discussion regarding assumptions is in order. With so much of this work focusing on unbiasedness and convergence, the assumption of what is known (rather than estimated) deserves higher scrutiny and needs serious discussion in the main text of the paper.

The last point I discuss is a significant issue (whether or not the authors realize it), but I stress that this issue was not in isolation the reason for the paper not being accepted. The issue is best summarized by the following line from Reviewer VsBW (also essentially conveyed by Reviewer JwMW): "The presentation is often unnecessarily repetitive, with the effect of selling the paper’s results rather than clearly presenting its contributions." From my detailed read, there is significant repetitiveness and also some overselling is very apparent to me. Given that two reviewers and I independently came to this conclusion, I really do think this is an important issue. I urge the authors to solicit feedback from their peers if the authors are unable to see what parts of their paper are repetitive and to also consider reducing the overselling; this is an exercise that overall will benefit the authors by improving their scientific writing in the future and also which will allow them more space to present their contributions. One reviewer lamented that there was not much precision in what is being estimated, and there also was a lack of precision when discussing sample complexity in the paper. Having more space will allow you to properly discuss these important points.

I will now provide some guidance here about the repetition that I found and the overselling I found (again, in isolation the below is not the reason for the paper not being accepted, and also, it is not the major reason either, but it is also not a minor one).

Regarding overselling: The authors often mention that ERMI is stronger than other fairness measures (see Theorems 1 through 3). However, stronger here just means that if ERMI is small, the other measures are small. Basically, ERMI can be viewed as a looser upper bound. Saying "stronger" in many places, as the authors do, give the connotation that ERMI is better, while a more scientific presentation would mention how it's simply looser (yet, the authors can highlight the benefit of ERMI in their experiments, so all is not lost).

Regarding repetitiveness: In three different places, the authors mention that Mary et al. (2019) has an estimator that is biased, and they repeatedly mention that theirs is unbiased. Also, they mention exactly once that the estimator of Mary et al. is biased but consistent (which, of course, means asymptotically unbiased). The scholarly way to say this would be that the method of Mary et al. is asymptotically unbiased (not saying it this way is, to me, mild overselling, so this should also be included in the "overselling" paragraph above). They also mention 4 times in the paper, even before the experiments section, that their methods outperform those of Mary et al. (2019). This amount of repetition seems less than scholarly.
    
In conclusion, this paper definitely has strong merit, but it needs a serious rewriting/restructuring though in order to appear at venue of the caliber of NeurIPS. As one reviewer stated, "The strong experimental results that you have show merit, but I believe a reworking of the theoretical insight with clarity and modesty will make a better case for the paper". 
Decision: Reject