We theoretically study how differential privacy interacts with both
individual and group fairness in binary linear classification. More precisely,
we focus on the output perturbation mechanism, a classic approach in
privacy-preserving machine learning. We derive high-probability bounds on the
level of individual and group fairness that the perturbed models can achieve
compared to the original model. Hence, for individual fairness, we prove that
the impact of output perturbation on the level of fairness is bounded but grows
with the dimension of the model. For group fairness, we show that this impact
is determined by the distribution of so-called angular margins, that is signed
margins of the non-private model re-scaled by the norm of each example.

我们在二元线性分类中理论上研究了差分隐私如何与个体公平性和群体公平性相互作用。具体来说，我们关注输出扰动机制，这是一种隐私保护机器学习的经典方法。我们导出了对扰动模型相对于原始模型可以实现的个体和群体公平性水平的高概率界限。因此，对于个体公平性，我们证明了输出扰动对公平性水平的影响是有界的，但随着模型维度增长而增长。对于群体公平性，我们表明这种影响取决于所谓的角余量的分布，即非私有模型的带符号余量通过每个示例的范数重新缩放。

关于输出扰动对二元线性分类中公平性的影响

On the Impact of Output Perturbation on Fairness in Binary Linear  Classification

We investigate how pair-wise data augmentation techniques like Mixup affect
the sample complexity of finding optimal decision boundaries in a binary linear
classification problem. For a family of data distributions with a separability
constant $\kappa$, we analyze how well the optimal classifier in terms of
training loss aligns with the optimal one in test accuracy (i.e., Bayes optimal
classifier). For vanilla training without augmentation, we uncover an
interesting phenomenon named the curse of separability. As we increase $\kappa$
to make the data distribution more separable, the sample complexity of vanilla
training increases exponentially in $\kappa$; perhaps surprisingly, the task of
finding optimal decision boundaries becomes harder for more separable
distributions. For Mixup training, we show that Mixup mitigates this problem by
significantly reducing the sample complexity. To this end, we develop new
concentration results applicable to $n^2$ pair-wise augmented data points
constructed from $n$ independent data, by carefully dealing with dependencies
between overlapping pairs. Lastly, we study other masking-based Mixup-style
techniques and show that they can distort the training loss and make its
minimizer converge to a suboptimal classifier in terms of test accuracy.

本文研究了一种名为 Mixup 的数据增广技术，发现它可以显著地降低寻找最优决策边界的样本复杂度，而不同的掩蔽 Mixup 风格技术有可能扭曲训练损失和导致其最小化器收敛到考虑测试精度的次优分类器。