A growing body of research has explored the ethical and societal implications of increasingly automateddecision-making.

How to ensure fairness in algorithmic decision making models is an important task in machine learning [12,15]. Over the past years, many researchers have been devoted to the design of fair classification algorithms withrespecttoapre-defined protected attribute,suchasraceorsex,anda decision task/model, such as hiring [1,11,24]. In particular,one line of the work istoincorporate fairness constraints into classic learning algorithms tobuild fair classifiers from potentially biased data [4,13,29,31-33]. Most of previous research generally focuses on a single decision model.

In these cases, protected attributes can be "imputed" [

We study fair classification in the presence of an omniscient adversary that, given an $\eta$, is allowed to choose an arbitrary $\eta$-fraction of the training samples and arbitrarily perturb their protected attributes. The motivation comes from settings in which protected attributes can be incorrect due to strategic misreporting, malicious actors, or errors in imputation; and prior approaches that make stochastic or independence assumptions on errors may not satisfy their guarantees in this adversarial setting. Our main contribution is an optimization framework to learn fair classifiers in this adversarial setting that comes with provable guarantees on accuracy and fairness. Our framework works with multiple and non-binary protected attributes, is designed for the large class of linear-fractional fairness metrics, and can also handle perturbations besides protected attributes. We prove near-tightness of our framework's guarantees for natural hypothesis classes: no algorithm can have significantly better accuracy and any algorithm with better fairness must have lower accuracy. Empirically, we evaluate the classifiers produced by our framework for statistical rate on real-world and synthetic datasets for a family of adversaries.

This poses the question of whether one can still learn fair classifiers given noisy sensitive features.

Machine learning is also increasingly used by law enforcement, where ethical questions become civil rights questions.

Existing theoretical work on Bayes-optimal fair classifiers usually considers a single (binary) sensitive feature. In practice, individuals are often defined by multiple sensitive features. In this paper, we characterize the Bayes-optimal fair classifier for multiple sensitive features under general approximate fairness measures, including mean difference and mean ratio. We show that these approximate measures for existing group fairness notions, including Demographic Parity, Equal Opportunity, Predictive Equality, and Accuracy Parity, are linear transformations of selection rates for specific groups defined by both labels and sensitive features. We then characterize that Bayes-optimal fair classifiers for multiple sensitive features become instance-dependent thresholding rules that rely on a weighted sum of these group membership probabilities. Our framework applies to both attribute-aware and attribute-blind settings and can accommodate composite fairness notions like Equalized Odds. Building on this, we propose two practical algorithms for Bayes-optimal fair classification via in-processing and post-processing. We show empirically that our methods compare favorably to existing methods.

Section 1 describes the set-up of the problem. In particular, the authors emphasize that there are two cases where features might have noise in them: 1) when noise is deliberately added by researchers for privacy purposes and 2) in the "positive and unlabeled" setting where individual participants in the minority group might feel uncomfortable disclosing that, leading to unlabeled data for the sensitive feature in some cases. The case under consideration is binary classification on output Y with a binary sensitive feature A . There are two main assumptions in this paper. The first is that the noise can be described as "mutually contaminated learning".