Meta Optimality for Demographic Parity Constrained Regression via Post-Processing

We appreciate the reviewer’s detailed feedback. Here, we address the main concerns:

W1:

A pertinent example is when $f^*_{\mu,s}$ is a composition of multiple functions, i.e., $f^*_{\mu,s} = g_q \circ ... \circ g_0$, within the Holder class as used by Schmidt-Hieber (2020), and $\vartheta^*_{\mu,s}$ belongs to the Sobolev space. In this scenario, $\mathcal{E}_{n_s}(\mathcal{P}_s) = \Theta(\max_i n_s^{-2\beta^*_i/(2\beta^*_i + t_i)})$, where $\beta^*_i$ represents the cumulative smoothness for $g_q, ..., g_i$, and $t_i$ indicates the dimensionality of the input of $g_i$. For the Sobolev space with smoothness $\gamma > 0$, Definition 3.3 is satisfied with $\alpha = 2\gamma$ and $\beta = 1$ by selecting $\Theta_j$ as a set of functions spanned by the first $j$ wavelet bases. The rate becomes $\max_i n^{-2\beta^*_i/(2\beta^*_i + t_i)} + n^{-2\gamma/(2\gamma + 1)}$, up to logarithmic factors, under the assumption $n_s \ge cw_s n$. If $g_i$ and $\vartheta^* _{\mu,s}$ share the same level of smoothness, i.e., $\beta^* \approx \gamma$, the first term dominates the second if $t_i > 1$ for some $i$. Here, $t_i$ denotes the dimensionality of the essential intermediate data representation. Such an intermediate representation may have multiple dimensions, i.e., $t_i > 1$, causing the first term from the conventional regression problem to dominate the rate.

We will incorporate this example after discussing the implications of the main theorem in the revised version.

W2, W4:

Our results offer significant advantages over the error bounds presented by Chzhen et al. (2020). Firstly, our results are derived under weaker assumptions. Their results necessitate the conventional regression algorithm to have a sub-Gaussian high-probability error bound, whereas our results only require a bound on the expected square error. Additionally, while they demand constant upper and lower bounds on the density of $\nu_i$, we only assume the Poincare-type inequality. This broadens the applicability of our meta-theorem compared to their findings.

Secondly, their results cannot achieve a rate faster than $n^{-1/2}$, as their upper bound on the estimation error of $\vartheta^*_{\mu,:}$ is $n^{-1/2}$ and dominates other terms. However, our results can achieve a rate faster than $n^{-1/2}$ by leveraging the smooth structure of $\vartheta^*_{\mu,:}$.

Thus, our results can demonstrate a faster rate under weaker assumptions compared to those provided by Chzhen et al. (2020). We will include this discussion as an implication of our main theorem in the revised version.

W3:

We wish to clarify that our results do not contradict those of (Woodworth et al., 2017), as their results pertain to equalized odds, not demographic parity. Our findings show that concerning sample size, post-processing can be optimal. However, it may be suboptimal for other parameters, such as the Lipschitz constant $L$ and the number of groups $M$. Analyzing optimality for these parameters is an important direction for our future work.

We appreciate the reviewer's comprehensive feedback and would like to address their main concerns:

W1: Rawlsian Fairness

We wish to clarify that Rawlsian fairness is fundamentally different from equality-based fairness concepts like demographic parity and equalized odds. Rawlsian fairness focuses on minimizing adverse effects on the most disadvantaged group, whereas equality-based fairness aims for equal treatment across groups. Due to these fundamental differences, results from Rawlsian and equality-based fairness approaches are not directly comparable.

Furthermore, we emphasize that minimax optimality is a well-established concept in statistical literature, used to define the best estimator for a statistical estimation problem. In our context, "minimax" involves maximizing over all possible underlying distributions and minimizing over all estimation algorithms. This concept differs from Rawlsian fairness, as we can define a minimax optimal Rawlsian fair learning algorithm that minimizes the worst-case error, considering both underlying distributions and groups.

Regarding data generation models, they represent potential underlying distributions in nature. Considering a specific set of data generation models is not a limitation of the learner's ability but rather reflects prior knowledge about the data. The sample complexity varies based on this prior knowledge. Extensive research in statistical literature has shown how prior knowledge fundamentally influences sample complexity. Our meta-theorem can accommodate various prior knowledge assumptions by leveraging these existing results.

W2: Group-wise Regressor

We use a group-wise predictor because it is commonly employed in fairness literature. Developing an optimal post-processing method for an unaware predictor is an important area for future research.

W3: Classification

In the context of minimax optimality, regression problems are often considered more fundamental than classification problems, as the minimax optimal error for classification is typically derived using regression techniques. Extending our work to classification problems is a significant direction for future research.

We thank the reviewer for their positive feedback and for recognizing the importance of our theoretical contributions in fair regression.