f-FERM: A Scalable Framework for Robust Fair Empirical Risk Minimization

We appreciate the time you have taken to read our manuscript and provide feedback to us. Below is our point-to-point response to your comments.

Missing a related reference called TERM.

This paper was cited and discussed in the original submission. The proposed fairness notion in that paper is based on equal performance for different sub-groups, which is different from our fairness notions. In contrast to our work, their paper focus is not on finding convergent stochastic algorithms or distributionally robust fair learning.

The main formulation could be simplified. The f-divergence between the joint distribution and the product of marginals is f-mutual information (https://openreview.net/forum?id=ZD03VUZmRx)

Thank you for bringing up this work, which we cited in our revision. While f-mutual information is proposed in the contrastive learning context in the paper you mentioned, their first formulation is exactly equal to our regularization term (for the case of demographic parity). Therefore, though we do not use the same terminology for our regularizer, they are equivalent, and none is simpler than the other. The other developments in the paper are based on assuming the joint feature distribution is proportional to the Gaussian kernel, which we do not rely on. As we explained in our general response, our contribution is the reformulation leading to a stochastic optimization algorithm and its extension to the distributionally robust settings.

SGDA for minmax optimization is inefficient. Theorem 2.2 has a weak convergence result. How is it related to experiments?

Good question! We agree that SGDA can be improved under some additional assumptions (see our general response, the added discussion in the paper after Theorem 2.2, and Appendix G in the revised manuscript). However, SGDA is widely used for minmax optimization due to its simplicity and ease of tuning. There are other double-loop and triple-loop algorithms with overall less iteration complexity, as we included in the paper. However, the underlying condition for using all these algorithms is access to an unbiased gradient estimator with a bounded variance. This condition is satisfied in our formulation and will allow users to choose their own favorite algorithm. In our experiments, we found SGDA dependable because of its single-loop nature and the small number of parameters for tuning.

All the experiments are on small-scale datasets.

We have used all popular benchmark datasets, including Adult, German Credit, and COMPAS datasets. For the DRO section, there are indeed not many available real-world datasets containing natural distribution shifts. The New Adult dataset (which we used in our experiments) is one of the newest and largest datasets available (50 states, with each having its own distribution). We believe our experiments on a wide range of datasets are the reason that some other reviewers found our experiments extensive and comprehensive. Having said that, we would love to include additional experiments in the GitHub repository of our paper if you have any specific dataset suggestions.

The paper didn't discuss which f is the best choice in detail.

This is an important and natural question. As can be seen in our experiments, there is no single divergence that is always better than others in all settings. In the case of binary-sensitive attributes and full batch algorithms, their performance is almost the same. In the case of non-binary sensitive attributes, if the batch size is small, we observe that KL divergence works impressively well (we mentioned this in the analysis of Figure 1). We believe in applications, the choice of the $f$-divergence can be viewed as a hyperparameter that can be tuned by cross-validation. We have clarified this point in our revised manuscript at the beginning of section 4. An interesting theoretical future research direction could be why and when each of these $f$ divergence measures can outperform the others.

The definition of fairness is not clear to me. This paper considers both DP and EO, but which one is what f-FERM approach?

Our formulation can handle any group fairness measure that is based on the [conditional] independence between sensitive attributes and predictions. This fact is explained at the beginning of section 2. Specifically, our framework can handle demographic parity, equalized odds, and equality of opportunity. In the main body, we have focused on demographic parity. However, by a simple conditioning of the probability measures, we can generalize to other notions. For example, if instead of $s$ and $\hat{y}$, we consider $s | y = 1$, and $\hat{y} | y = 1$ in (6), then we obtain f-ferm for equality of opportunity. Please see the discussion in Appendix A.

We appreciate your time and feedback, and we hope our response addresses your concerns. If so, we would appreciate it if you could reflect it in your evaluation of our paper.

We are delighted that your characterization of the strength of our paper aligns with ours. Particularly, we are encouraged that you found our unified framework, algorithm, and robustified versions solid contributions and our numerical experiments extensive and convincing. We appreciate the time you spent reading our paper and providing us feedback to improve our manuscript. Below is our point-to-point response to your concerns:

The proposed unified formulation and its minimax reformulation seem incremental, as similar minimax forms have appeared in many existing works of fair machine learning

You are correct that there exist other min-max formulations in the literature, such as Renyi Fair Inference (Baharlouei et al., 2020) and Fairness-Aware Learning (https://proceedings.mlr.press/v97/mary19a/mary19a.pdf). However, the algorithms they provided only work for full-batch settings. The reason is that it is not straightforward for their formulation to derive an unbiased estimator of the gradient (as a necessary condition for SGDA and other first-order algorithms) for small batches. In addition, there are two other aspects that completely distinguish our work from existing works. First, our framework covers a wide range of divergences (and it is not a single divergence). This will give the practitioner the option to use the most suitable/favorite divergence given their application. Second, our framework can handle settings involving distribution shifts. We believe this step is another major contribution of our work which sets us apart from previous works and should not be overlooked.

The convergence analysis is straightforward from the paper by Lin et al. (2020).

We agree that our main contribution is not the convergence analysis of the algorithm. Our primary contribution is that we provide a formulation leading to an unbiased estimator of the gradient with a bounded variance that can be naturally obtained. Having access to such an estimator enables us to use existing first-order stochastic optimization methods with convergence guarantees to solve the problem. Indeed, for both the iid setting and the distribution shift setting, our novel formulation can be solved with existing optimization algorithms. To clarify this point, we added a discussion in our revised paper explaining existing algorithms that can be used in our problem. Please see the paragraph after Theorem 2.2 and the new Appendix G.

Thank you for your time and for your valuable feedback. We hope our response adequately clarifies our contributions, and we would be greatly thankful if you could consider this in your evaluation of our paper.

We are encouraged that you found our results novel and interesting and that you understood our main contributions. We would also like to thank you for your constructive feedback. Below, please find our point-to-point response to your comments:

I want to ask authors to clarify, how do they obtain classifier $\hat{y}$? Typically, one obtains differentiable probabilities , and then maximising the probability $p_{\theta}(y=j|x)$ yields the classification. However, the expression (4) suggest that the estimator is sampled. This may harm the accuracy in practice. It is ok to use $F_j$ as a proxy, but it is better if you clarify that explicitly for applied people who may potentially use your method.

This is a great point. As you correctly pointed out, our formulation is based on the randomized prediction rule where the label is samples. More specifically, $F_i(x)$ represents the probability of predicting class $i$ for data point $x$. However, as you correctly mentioned, this could harm the accuracy in practice. Thus, in our numerical experiments, we used the standard maximum likelihood decoding based on the output of the softmax layer, i.e., the predicted label is the label with the highest logit value. We have clarified this point in our revision, see page 8 in the revised manuscript.

Secondly, in Theorem 2.2 the stated convergence time is $O(\epsilon^{-8})$ which seems rather slow. Does it affect the amount of epochs you use in the experiments, is it unusually large?

The rate of $O(\epsilon^{-8})$ holds for all the f-divergences and all batch sizes for SGDA algorithm. However, under certain additional conditions or for special choices of f-divergence, this rate can be improved. Please see our general response and the added Appendices in the revised manuscript.

Thirdly, could you please clarify directly in Proposition 2.2. what is the dimension of variables $A_{jk}$?

$\mathbf{A}$ is a $|Y| \times |S|$ matrix where $Y$ is the set of possible labels, and $S$ is the set of sensitive attribute values. $A_{jk}$ represents the entry of matrix A corresponding to the label j and sensitive attribute value k. Therefore, $A_{jk}$ is a scalar. We believe that our use of bold font for that led to the confusion. Hence in our rebuttal, we changed it to regular font.


Thank you again for your detailed and constructive comments. We hope our response answers your question. Particularly, your comments on the randomized nature of our classifier and the rate of convergence of the algorithm are important and we hope our changes in the paper make it clear for future readers.

When the ambiguity set of formulation (8) is small, the authors propose a first-order approximation formula to solve it (see Eq.(10)). Although the authors present the approximation error between formula (8) and (10), the complexity for solving Eq.(10) is not presented in this paper.

Thanks for bringing up this concern. At the end of the day, we apply the SGDA algorithm to Problem (10). We showed how to compute an unbiased estimator of the gradient with respect to each set of parameters. The problem is nonconvex-concave, and thus, all the discussions we had in our general response apply here. In particular, the algorithm converges in $O(\epsilon^{-8})$ iterations with a very small batch size requirement (even batch size of $O(1)$). However, one can obtain faster algorithms under additional assumptions. For example, if the set for $\theta$ is assumed to be compact (e.g., we restrict the norm of the weight of the gradient), then we can accelerate the algorithm to $O(\epsilon^{-6})$, see https://arxiv.org/pdf/1810.02060.pdf. Moreover, if we consider full batch sizes, we can utilize Algorithm 2 in the cited work (Ostrovskii et al 2021). This will give you the rate of convergence of $O(\epsilon^{-2})$; see (Theorem 5.2, Ostrovskii et al 2021). We added these discussions to the paper in Appendix H. Thank you for helping us detect this miscommunicated point and improve the clarity of the paper.

Can the authors add more details regarding the sentence "One can easily see that the optimal $p_j = \min(\hat{p}_j+\delta, 1)$ and $q_j = \max(\hat{q}_j - \delta, 0)$”. It is not obvious for readers to check this point.

Great point! Since the problem is a constrained convex maximization problem (not minimization), the solution will be on the boundary. Since $f$ is a non-decreasing function for the choice of KL-divergence and chi-square, the maximum value with respect to $P$ occurs when $P$ takes the maximum possible value, which is either $p + \delta$ or $1$. Similarly, we can see that the maximum value with respect to $Q$ happens when $Q$ takes the minimum possible value, which is $q - \delta$ or $0$. We added a detailed step-by-step proof of the claim as an Appendix (Appendix I) to the paper to clarify this point.

What is the meaning of the scalar 𝛅>0? It is not introduced. if I remember correctly, in standard f-divergence DRO, it is the Lagrangian multiplier corresponding to the probability simplex constraint that needs to be optimized

$\delta$ represents the uncertainty ball radius (it is usually represented by $\epsilon$. Since we already use $\epsilon$ as the optimality approximation, we use $\delta$ to represent the size of the $L_p$ norm uncertainty set. We analyze the DRO problem for small $\delta$ in Section 3.1. Alternatively, when $\delta$ is large (more robustness), we analyze the problem for the special case of $L_{ \infty}$ norm.


Finally, we would like to thank you for the time you spent reading our paper and providing constructive feedback to us. Your question on the rate of convergence of the algorithm has helped us clarify a main point in our manuscript and improved the overall quality of our paper. We hope our response clarifies our contributions and answers your questions. If so, we would be grateful if you could reflect this in your evaluation score of our paper.

We appreciate your time and valuable feedback. We are glad that you found the formulation novel, the theoretical analysis sound, and the experiments comprehensive. Below, please find our point-to-point response to your comments:

The only novel theoretical part is the convergence analysis of the SGDA for solving the ERM formulation. The corresponding sample complexity for finding -the statariony solution of (f-FERM) is $O(\epsilon^{-8})$. However, I wondered if the authors use the state-of-the-art optimization algorithm for solving nonconvex-concave min-max games and if the sample complexity is currently the optimal one in the literature. If so, the authors should highlight it in the literature.

We agree with you that faster algorithms can be used to solve our problem (under some additional assumptions). As explained in our general response above, the rates can be improved under certain additional assumptions and via using more sophisticated algorithms in the literature. However, we chose the simple SGDA algorithm due to its simple implementation (single loop with much fewer tuning parameters compared to other existing methods). In addition, SGDA may have generalizability benefits as pointed out in the general response. Nevertheless, this is not the major contribution of our work. We clarified these points in our revised manuscript. However, for the sake of completeness and based on your suggestion, we added a detailed and comprehensive discussion on what rates can be achieved using existing algorithms on page 5, Appendix F, and Appendix G. Having said that, we do think that most of these algorithms are less practical than SGDA due to their heavy hyperparameter tuning needs. This has also been observed in the past for much simpler training tasks (such as regular minimization problems), as SGD is still the workhorse for training convex and nonconvex models, while there are theoretically faster available algorithms out there. Regarding the novelty, we agree with your earlier assessment that the formulation of the problem is novel. Our formulation can cover a wide range of divergences and lead to efficient algorithms. Indeed, as explained in our general response, our main contribution to non-robust fair learning is the formulation and the reformulation of it as a min-max optimization with unbiased (and bounded variance) gradient estimator. Once we have this step, the rest would mostly rely on existing literature. Similarly, in the robust fair setting, our main contribution is to reformulate the problem in a form that can be efficiently solved. These are non-trivial contributions, in our opinion, and should not be overlooked.

For the distributionally robust formulation (8), the authors used $\ell_p$-norm to model the ambiguity set, but I am afraid that this usage may not be a novel choice because it is not a flexible choice as Wasserstein, f-divergeces, or MMD, to quantify the difference between distributions. I encourage the authors to consider the extension to other choices of ambiguity sets.

Thank you for your suggestion. This is a theoretically interesting future research direction to pursue. Having said that, we believe this is much less practically relevant in our context. For example, the Wasserstein ball relies on an underlying distance between the random variables. However, the fairness features in our case are mostly categorical (e.g., male vs female) and not easy to define a natural distance on. More specifically, Wasserstein distance is natural for continuous variables or ordinal discrete variables (e.g. movie ratings or age groups). However, it is not natural to consider an order or distance between different races or genders as sensitive attributes. Further, the Fair ERM is studied under the Wasserstein ball in the past for the special case of logistic regression (convex loss) (https://arxiv.org/pdf/2007.09530.pdf). However, even for this simple case, no scalable stochastic algorithm is offered, even in the convex fair ERM. In contrast, our methodology offers scalable algorithms for even nonconvex models. In addition, our extensive experiments show the effectiveness of the proposed method, which is also supported by our theory. Regarding the novelty of using $L_p$ ball, to the best of our knowledge, our work is the first to use $L_p$ uncertainty balls for DRO fair empirical risk minimization. It is shown to be practically effective in the experiments and is backed by a reasonable amount of theory. Hence, we still believe there is novelty in our work.