Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper investigates the underlying causes of the disparate impact produced by differentially private machine learning methods. To that end, the paper considers the notion of excessive risk gap, which measures the difference between the population-level and subgroup risks. The paper explores how two different differential privacy mechanisms (output perturbation and DP-SGD) affect the excessive risk gap. For output perturbation, the paper relates the excessive risk gap to the absolute difference between the population-level and subgroup trace of the hessian. For DP-SGD, the paper decomposes the expected loss into a non-private term, a private term due to clipping, and a private term due to noise. Finally, the paper leverages these insights to propose a novel formulation of DP-SGD that empirically decreases the excessive risk gap on real-world datasets.
main_review: **Originality:** This paper sheds light on the causes of the disparate impact produced by differentially private machine learning methods. This disparate impact was recently discovered by prior work and has not yet been fully understood. The paper presents novel insights via careful theoretical analysis of the effects of differential privacy methods on excessive risk. 

**Quality:** The submission is technically sound, and the proofs are generally correct. However, there are some (mostly minor) mistakes:
- The term $\nabla_{\theta^*} \mathcal{L}(\theta^*, D_a)$ is missing in the expectation of L506.
- Equations 15b, 15c, 15d, and 16 all mistakenly use $\bar{g}_B$ instead of $\bar{g}_D$.
- You probably also need to assume that $\eta \leq 1$ since $\eta$ is squared in Equation 25d.
- Equation 28c is strictly greater than the right-hand side of Equation 29a.

**Clarity:** The paper is clearly written and well organized. However, certain presentational aspects could be improved (also see questions below). The most critical ambiguity is the paper’s claim on L134 that `groups with larger Hessian traces will have larger excessive risk than groups with smaller Hessian traces`. It is unclear why this statement would make sense since the excessive risk is approximated by the absolute difference of the population-level and subgroup hessian traces. Thus the magnitude of the subgroup Hessian trace is entirely irrelevant if it is close to the population-level Hessian trace. Furthermore, the adjacency relation and range should be defined for the Gaussian mechanism on L083. Finally, there are a couple of errors:
- DP-SGD is frequently misspelled as DP-SDG
- L025 lending instead of landing
- L125 from instead of from
- L140 varying *levels* of
- L322 these instead of this
- L604 it instead of if

**Significance:** The submission advances the understanding of the interplay between differential privacy and fairness in machine learning. The results could be useful to researchers from both fields when designing novel fairness of privacy approaches.

**Questions**

- Section 10 mentions that the proposed mitigation solution negatively affects the training runtime but does not provide any concrete numbers. How much slower is the proposed solution?
- How can the excessive risk gap values in Figure 8 be negative if the excessive risk gap is the absolute difference between two risk functions?
- What happened to the term $- p_a p_b g_{D_a} g_{D_b}$ when going from Equation 27b to Equation 28a?
- Is the global sensitivity in L081 and L118 the same?
- Why is the convexity assumption necessary in Theorem 1? Is this only required for output perturbation?
- Why does the privacy analysis of output perturbation require optimality of the model parameters? Could one not apply output perturbation to non-optimal parameters?

I am happy to increase my score if the authors can resolve my concerns.
limitations_and_societal_impact: The paper fails to discuss potential negative societal impacts within the page limit (as required by the [NeurIPS blog](https://neuripsconf.medium.com/introducing-the-neurips-2021-paper-checklist-3220d6df500b)).
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The goal of the paper is to study the disparate impact that differential privacy can have across different groups. The authors do so within an ERM framework, and aim to equalize (or minimize the difference in) the excessive risk across groups.
main_review: Strengths: 
- the excessive risk gap is a natural fairness metric here: it measures how far each group is from its optimal outcome, and compares this excess error/risk across groups. Low excessive risk gap means that all groups are *additively* as close to the best model as each other.
- It is nice that the results of the paper go beyond the classical understanding that different group sizes lead to different amount of noise added to the data, hence leading to disparate impact. 
- Some of the insights in the paper are interesting: for example, the authors were able to “show” that the unfairness level is proportional to the amount of noise added for privacy
- The decomposition of Theorem 2 is really nice. It explicitly points out which part of the loss comes from the non-private loss, from clipping the gradients, and from the noise added for privacy.
- The experiments of Figure 3 shed some interesting insights as to how the choice of gradient clipping affects fairness/excessive risk. 

Weaknesses:
i) The major weakness of the paper is that the math is hand-wavy and not rigorous. The results of the authors are approximations, and are not complemented with confidence intervals or some understanding of the order of magnitude of the higher order terms that are being ignored. In turn, this weakens the theoretical insights of the paper.
ii) More minor, but some of the insights of the paper are a bit hard to understand: 
- Page 4 mentions the effect of the magnitude of Hessian traces on the excessive risk, but what does having a large Hessian trace means with respect to the data and the loss function? There are a few examples in the paper, but I am still having a hard time parsing what this means.
- Theorem 3 gives a sufficient condition on the magnitude of the average non-private gradient norm of the groups and the clipping value to cause unfairness, but the average gradients is something that is hard to understand theoretically, making this condition hard to use.  

Question:
What happens when using different clipping values for different groups? Is it possible to intervene there to guarantee better fairness at the cost of possibly lower clipping values in some groups. This would also lead to lower sensitivity hence amount of noise to add to the gradients?

limitations_and_societal_impact: The authors acknowledge the limitations of their paper. In terms of societal impact, this paper is directly relevant as it aims to understand the social and disparate impact of differential privacy across groups.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper tries to solve the problem that ML models with DP tend to excerbate bias and unfairness. Particularly, it focuses on two well-studied DP algorithms: output perturbation and DP-SGD. The paper shows that the unfairness is caused by gradient clipping and noise addition. Based on the observations,  it further proposes a solution and its effectiveness has been tested experimentally. 
main_review: Originality:  The observations that both gradient clipping and noise addition cause unfairness, and the proposed mitigation solution are new and the related works are adequately cited. 

Quality:  Claims are well supported by theoretical analysis and the the analyses are used appropriate. The current work includes two well-known DP algorithms and their theoretical results, demonstrations are included; Hence it is complete. 

Clarity: The submission is clearly written and well organized.

Significance: The developed notion of fairness is important and interesting and other researches are likely to use the concept to build the fairness of their methods in the future.  The work narrows the gap between the unfairness of ML models and differential privacy. 

limitations_and_societal_impact: 1 Why does Theorem 2 only show a second-order Taylor expansion of the excessive risk for group a, rather than similar result showing in Theorem 1? Since the unfairness defined in line 107 is based on excessive risk gap $\xi_a$, it is more meaningful and consistant to see the theoretical results with respect to $\xi_a$ for DP-SGD in section 6.

2  In Section 9, the paper proposes a mitigation solution with extra terms. So how to determin appropriate values for $\gamma_1$ and $\gamma_2$? How do different values of $\gamma_1$ and $\gamma_2$ affect the performance of original tasks, such as the MSE or prediction accuracy? 

3 Can authors explain more about the definition of  excessive risk in line 103 and how to calculate in practice, in terms of expectation?  Since the optimal solution $\theta^*$ is not the optimal solution for the loss function w.r.t. data of group a. It can be negative values, right? But I see all excessive risk values in Figure 3 and Figure 7 are positive.  What's more, are values of excessive risk comparable among different groups? If not,  can authors explain why excessive risk is a good representation for fairness?
review_title: null

Meta-review: The paper studies impact of various DP algorithms on fairness. The paper is well written and easy to follow.  I encourage authors to incorporate reviewer suggestions and make the analysis more rigorous in the final version of the paper e.g., change Theorem 1 to include higher order error terms via O() notation. 
Decision: Accept (Poster)