Distribution-Specific Auditing For Subgroup Fairness
- URL: http://arxiv.org/abs/2401.16439v2
- Date: Thu, 29 Feb 2024 23:18:38 GMT
- Title: Distribution-Specific Auditing For Subgroup Fairness
- Authors: Daniel Hsu, Jizhou Huang, Brendan Juba
- Abstract summary: Kearns et al.trivial has shown that the problem of auditing subgroup fairness is as hard as agnostic learning.
We show how to audit statistical notions of fairness over homogeneous halfspace subgroups when the features are Gaussian.
- Score: 37.99837688251836
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of auditing classifiers with the notion of statistical
subgroup fairness. Kearns et al. (2018) has shown that the problem of auditing
combinatorial subgroups fairness is as hard as agnostic learning. Essentially
all work on remedying statistical measures of discrimination against subgroups
assumes access to an oracle for this problem, despite the fact that no
efficient algorithms are known for it. If we assume the data distribution is
Gaussian, or even merely log-concave, then a recent line of work has discovered
efficient agnostic learning algorithms for halfspaces. Unfortunately, the
reduction of Kearns et al. was formulated in terms of weak, "distribution-free"
learning, and thus did not establish a connection for families such as
log-concave distributions.
In this work, we give positive and negative results on auditing for Gaussian
distributions: On the positive side, we present an alternative approach to
leverage these advances in agnostic learning and thereby obtain the first
polynomial-time approximation scheme (PTAS) for auditing nontrivial
combinatorial subgroup fairness: we show how to audit statistical notions of
fairness over homogeneous halfspace subgroups when the features are Gaussian.
On the negative side, we find that under cryptographic assumptions, no
polynomial-time algorithm can guarantee any nontrivial auditing, even under
Gaussian feature distributions, for general halfspace subgroups.
Related papers
- Near-Optimal Resilient Aggregation Rules for Distributed Learning Using 1-Center and 1-Mean Clustering with Outliers [24.88026399458157]
Byzantine machine learning has garnered considerable attention in light of the unpredictable faults that can occur.
The key to secure machines in distributed learning is resilient aggregation mechanisms.
arXiv Detail & Related papers (2023-12-20T08:36:55Z) - Correcting Underrepresentation and Intersectional Bias for Classification [49.1574468325115]
We consider the problem of learning from data corrupted by underrepresentation bias.
We show that with a small amount of unbiased data, we can efficiently estimate the group-wise drop-out rates.
We show that our algorithm permits efficient learning for model classes of finite VC dimension.
arXiv Detail & Related papers (2023-06-19T18:25:44Z) - Leveraging Structure for Improved Classification of Grouped Biased Data [8.121462458089143]
We consider semi-supervised binary classification for applications in which data points are naturally grouped.
We derive a semi-supervised algorithm that explicitly leverages the structure to learn an optimal, group-aware, probability-outputd classifier.
arXiv Detail & Related papers (2022-12-07T15:18:21Z) - Individually Fair Learning with One-Sided Feedback [15.713330010191092]
We consider an online learning problem with one-sided feedback, in which the learner is able to observe the true label only for positively predicted instances.
On each round, $k$ instances arrive and receive classification outcomes according to a randomized policy deployed by the learner.
We then construct an efficient reduction from our problem of online learning with one-sided feedback and a panel reporting fairness violations to the contextual semi-bandit problem.
arXiv Detail & Related papers (2022-06-09T12:59:03Z) - Testing distributional assumptions of learning algorithms [5.204779946147061]
We study the design of tester-learner pairs $(mathcalA,mathcalT)$.
We show that if the distribution on examples in the data passes the tester $mathcalT$ then one can safely trust the output of the agnostic $mathcalA$ on the data.
arXiv Detail & Related papers (2022-04-14T19:10:53Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
Clustering is a fundamental primitive in unsupervised learning.
Recent work has established lower bounds against the class of low-degree methods.
We show that, perhaps surprisingly, this particular clustering model textitdoes not exhibit a statistical-to-computational gap.
arXiv Detail & Related papers (2021-12-07T18:50:17Z) - Agnostic Proper Learning of Halfspaces under Gaussian Marginals [56.01192577666607]
We study the problem of agnostically learning halfspaces under the Gaussian.
Our main result is the em first proper learning algorithm for this problem.
arXiv Detail & Related papers (2021-02-10T18:40:44Z) - Non-Convex SGD Learns Halfspaces with Adversarial Label Noise [50.659479930171585]
We show the solution to the problem of learning surrogate learning homogeneous halfspaces in the distribution-specific model.
In any convex distributions, we show that the misclassification error inherently leads to misclassification error of halfspace.
arXiv Detail & Related papers (2020-06-11T18:55:59Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
We study the learnability of halfspaces in the presence of Tsybakov noise.
We give an algorithm that achieves misclassification error $epsilon$ with respect to the true halfspace.
arXiv Detail & Related papers (2020-06-11T14:25:02Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.