Regression under demographic parity constraints via unlabeled post-processing

We appreciate the reviewer's careful reading and fully agree with the evaluation regarding the strengths and potential directions for future investigation. We will address the questions raised below.

Weaknesses

W1:

• Regarding lipschitzness of $F$. The reviewer feels that some discussions are curt.

A: We will enhance our discussion to better emphasize that the smoothness properties of $F$ are controlled by the regularization parameter $\beta$ (Lemma 3.4). Our final theoretical guarantees also provide practical guidance on selecting this parameter, balancing the regularization error (Lemma 3.3) and ensuring the algorithm's fast convergence.

• The authors introduced the "gradient mapping" $G_\alpha$ in eq. (8), with a hyperparameter $\alpha$. It is not mentioned how $\alpha$ should be chosen, in theory or in practice.

A: In theory, we set $\alpha = 1/M$ and any value of $\alpha \leq 1/M$ would yield exactly the same result. However, the choice of $\alpha$ is not critical for our specific problem, as the bounds on unfairness and risk are valid for any $\alpha > 0$ (see Lemma 3.5, lines 203-204). In practice, there is no $\alpha$ hyperparameter in the final implementation of SGD3 with a black-box optimizer.

• It is not mentioned how exactly SGD3 controls the norm of $G_\alpha$ in the main body.

A: Due to space limitations, we have provided the details of this part in the Appendix C. We would also like to remind that any algorithm designed to minimize the expected squared norm of the gradient mapping can be used. SGD3 is just an example that we included because it is supported by convergence rates.

W2:

• An ablation study would have been appreciated at illustrating the importance of using SGD3 over other optimizers; is it absolutely necessary?

A: We conducted additional experiments to observe the behaviors of simpler algorithms. A figure that illustrates the comparison is included in the attached pdf file. In conclusion, all algorithms perform similarly in the middle to high unfairness regime, while those based on SGD3 are more stable in the low unfairness (high fairness) regime. However, since the stochastic minimization of the norm of the gradient of a convex function is a relatively niche topic, there are only a few algorithms with established convergence rates. As we aim for end-to-end guarantees, we have chosen methods based on SGD3. Nonetheless, other stochastic minimization methods could potentially perform just as well in practice.

• Also, could the authors discuss potential limitations with SGD3?

A: The SGD3 algorithm, as described by Allen-Zhu (2021), serves primarily as a theoretical model that highlights a unique phenomenon in stochastic convex optimization with an unconventional criterion. Between the submission and the rebuttal, we extended and simplified the theory from Foster et al. (2019) to be applicable to our problem. This has enabled us to provide a theoretical guarantee for a simpler algorithm that combines an SGD3-like approach with accelerated stochastic gradient descent. While this improved analysis slightly enhances our fairness and risk guarantees, it does not alter the main message of the paper.

W3: The authors mentioned that there are several hyperparameters associated with SGD3 (line 236), and with discretization (i.e., the number of bins). But it does not seem to be discussed how these are chosen for the experiments in section 6, and whether mis-specification of these hyperparameters would impact performance.

A: In practice, we normalize the target variables to the range $[-1, 1]$, so we set $B = 1$ as our default practical recommendation, which aligns with actual practice. We have found that the other hyperparameters suggested by our theory already produce good empirical results. The exact choices of these parameters are detailed in Appendix G (line 693), and, aside from some multiplicative constants, they closely follow the theoretical values. These will be the default settings in the package we plan to release.

Questions

Q: Does the analysis rely on properties unique to the demographic parity fairness criterion? If not, is there a path to extend to other criteria (potentially taking inspirations from [1, 2])?

A: This is an excellent question. As the reviewer may have noticed, the key feature that ensures everything works is the compatibility of the demographic parity constraint with discretization. This approach can be adapted to any other notion of fairness that is "friendly" to discretization. However, care must be taken when introducing new notions of fairness. The demographic parity constraint is convenient because there are always predictions that satisfy it (e.g., constants), but this may not be true for other fairness notions. Since our algorithm relies heavily on a primal-dual approach, the finiteness of the optimal dual variables can only be guaranteed if certain constraint qualification conditions are met. This is not an issue for the demographic parity constraint but could be a potential obstacle for other fairness definitions.

We appreciate the reviewer's suggestion to include those two references, and they will be added to the final version. We want to emphasize that both references heavily depend on the ability to express the form of the optimal classifier under a given fairness constraint analytically. However, this is not applicable to regression in the unawareness setup as no such formula exists. Nevertheless, combining our discretization approach with the two references could potentially lead to a sensible method, and it is indeed an interesting avenue for future research.

Thank you to the reviewer for the careful reading and evaluation. We agree with the feedback and will correct the suggested typos in the revision. We will also address the question raised below.

Q: In practice, how do we pick algorithm parameters such as L, B and $\beta$?

A: In practice, we normalize the target variables to the range $[-1, 1]$, so we set $B = 1$ as our default practical recommendation, which aligns with actual practice. We have found that the other hyperparameters suggested by our theory already produce good empirical results. The exact choices of these parameters are detailed in Appendix G (line 693), and, aside from some multiplicative constants, they closely follow the theoretical values. These will be the default settings in the package we plan to release.

We appreciate the reviewer's time and effort in reviewing our work, but we respectfully disagree with the evaluation.

Weaknesses

The reviewer has criticized several stylistic choices in our paper. While we recognize that these choices may not align with the reviewer's preferences, it is worth noting that neither of the other two reviewers raised similar concerns. Our approach is driven by theory and is based on a carefully developed methodology rooted in mathematical reasoning, rather than common sense. Given this theoretical foundation, we believe our stylistic choices are justified and aid the reader in understanding our thought process. Below, we address the specific stylistic comments raised:

1. "Remark 2.1". We disagree with the assessment that Remark 2.1 is tangential. On the contrary, clearly defining the joint distribution of every random variable involved is crucial for understanding the problem. Including Remark 2.1 helps prevent potential misconceptions, such as assuming that $\hat{Y} = Y$ is a valid prediction function for any distribution of $(X, S, Y)$. Remark 2.1 explicitly clarifies that $\hat{Y} = Y$ is not a valid prediction function unless $Y$ is measurable with respect to $X$.

2. "Remark 2.2". Remark 2.2 anticipates potential questions from readers about possible extensions of our methodology. While we do not insist on keeping this remark in the main body, we believe it could be useful for some readers.

3. "Remark 3.1". We do not see any issue in abuse of notation as it is extremely common in mathematical science. Yet, we find it equally important to be extremely clear when such an abuse happens so that the reader is aware and could easily understand the logic behind our choice. The reviewer suggests providing clear definitions, but we would appreciate more specific guidance: which quantities are not clearly defined in our paper?

4. "There is excessive use of sub-titles or mini-sections". This is a stylistic choice we made to clarify the purpose of each paragraph. We believe it helps in setting the context clearly. We prefer to keep this as is unless the reviewer can provide a clearly better alternative.

Questions

Q1: The paper focuses on demographic parity as a fairness metric. Are there impacts on other fairness metrics like Equalized Odds and Equal Opportunity when using the proposed algorithm? Does it improve these metrics, or could it potentially worsen them?

A1: Equalized Odds and Equal Opportunity typically refer to fairness conditions in binary classification, while our work addresses fairness in the context of regression. While extensions of these notions to regression are possible, our approach focuses on demographic parity. As such, it might improve, worsen, or maintain fairness under other definitions. Since we have not claimed to address all definitions of fairness simultaneously, studying the trade-offs between different fairness notions is beyond the scope of this work. However, we will include a discussion emphasizing that our algorithm is tailored for a specific fairness definition as it is highlighted by the title.

Q2: Regarding the risks plot in Figure 1, could you clarify its purpose given there are no comparative benchmarks provided? How should the unfairness score presented in the plot be interpreted?

A2: The purpose of Figure 1 is to illustrate the post-processing dynamics of our proposed method, not to compare it with other algorithms, which are based on different approaches. A comparison with other algorithms is shown in Figure 2. Additional details on the implementation are provided in Appendix G, and the code is available via the link provided in the paper.

Q3: Reference [1] addresses a similar topic with a minimax approach. Is this minimax result applicable or relevant to the methodology used in your paper?

A3: The paper suggested by the reviewer has little in common with our contribution. Firstly, it deals with the scenario where sensitive attributes are available for prediction (the awareness setup) and relies on an explicit form of the optimal prediction provided by Chzhen et al. (2020b) and by Le Gouic et al. (2020). Such an explicit form is not yet available for regression in the unawareness setup, which remains an open question in the field. Secondly, that paper focuses exclusively on linear regression and provides a minimax statistical analysis for this case. In contrast, our work presents a versatile, theoretically grounded post-processing algorithm that can be applied to any pre-trained model in the unawareness setup for regression.

Q4: In Algorithm 1, "DP" is mentioned in the name. Could you specify what "DP" stands for?

A4: DP in the name of Algorithm 1 "DP post-processing" stands for demographic parity. We have indeed not introduced this term in the main body and will include it in the revision.

Q5: The algorithm "fairname" appears in line 305 without a prior definition. Could you explain what this term means within the context of your study?

A5: The name "fairname" in $`FairName`(L, T, \beta, \boldsymbol{p}, B, \hat\eta, \hat{\boldsymbol{\tau}})$ in the section of extension to unknown $\eta$ and $\tau$ is an unfortunate typo. It should be $`DP post-processing`$ and it will be corrected upon revision.