Set to Be Fair: Demographic Parity Constraints for Set-Valued Classification

• URL: http://arxiv.org/abs/2510.04926v1
• Date: Mon, 06 Oct 2025 15:36:45 GMT
• Title: Set to Be Fair: Demographic Parity Constraints for Set-Valued Classification
• Authors: Eyal Cohen, Christophe Denis, Mohamed Hebiri,
• Abstract summary: We address the problem of set-valued classification under demographic parity and expected size constraints.<n>We propose two complementary strategies: an oracle-based method that minimizes classification risk while satisfying both constraints, and a computationally efficient proxy that prioritizes constraint satisfaction.
• Score: 5.085064777896467
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Set-valued classification is used in multiclass settings where confusion between classes can occur and lead to misleading predictions. However, its application may amplify discriminatory bias motivating the development of set-valued approaches under fairness constraints. In this paper, we address the problem of set-valued classification under demographic parity and expected size constraints. We propose two complementary strategies: an oracle-based method that minimizes classification risk while satisfying both constraints, and a computationally efficient proxy that prioritizes constraint satisfaction. For both strategies, we derive closed-form expressions for the (optimal) fair set-valued classifiers and use these to build plug-in, data-driven procedures for empirical predictions. We establish distribution-free convergence rates for violations of the size and fairness constraints for both methods, and under mild assumptions we also provide excess-risk bounds for the oracle-based approach. Empirical results demonstrate the effectiveness of both strategies and highlight the efficiency of our proxy method.

Related papers

• Empirical Likelihood-Based Fairness Auditing: Distribution-Free Certification and Flagging [18.71249153088185]
  Machine learning models in high-stakes applications, such as recidivism prediction and automated personnel selection, often exhibit systematic performance disparities.<n>We propose a novel empirical likelihood-based (EL) framework that constructs robust statistical measures for model performance disparities.
  arXiv  Detail & Related papers  (2026-01-28T05:36:19Z)
• Fair Classification by Direct Intervention on Operating Characteristics [16.692307869326395]
  We develop new classifiers under group fairness in the attribute-aware setting for binary classification with multiple group fairness constraints.<n>We propose a novel approach, applicable to linear fractional constraints, based on directly intervening on the operating characteristics of a pre-trained base classifier.<n>On standard datasets, our methods simultaneously satisfy approximate DP, EO, and PP with few interventions and a near-oracle drop in accuracy.
  arXiv  Detail & Related papers  (2025-09-29T20:36:32Z)
• Learning from Similarity-Confidence and Confidence-Difference [0.07646713951724009]
  We propose a novel Weakly Supervised Learning (WSL) framework that leverages complementary weak supervision signals from multiple perspectives.<n>Specifically, we introduce SconfConfDiff Classification, a method that integrates two distinct forms of weaklabels.<n>We prove that both estimators achieve optimal convergence rates with respect to estimation error bounds.
  arXiv  Detail & Related papers  (2025-08-07T07:42:59Z)
• Finite-Sample and Distribution-Free Fair Classification: Optimal Trade-off Between Excess Risk and Fairness, and the Cost of Group-Blindness [14.421493372559762]
  We quantify the impact of enforcing algorithmic fairness and group-blindness in binary classification under group fairness constraints. We propose a unified framework for fair classification that provides distribution-free and finite-sample fairness guarantees with controlled excess risk.
  arXiv  Detail & Related papers  (2024-10-21T20:04:17Z)
• On Regularization and Inference with Label Constraints [62.60903248392479]
  We compare two strategies for encoding label constraints in a machine learning pipeline, regularization with constraints and constrained inference. For regularization, we show that it narrows the generalization gap by precluding models that are inconsistent with the constraints. For constrained inference, we show that it reduces the population risk by correcting a model's violation, and hence turns the violation into an advantage.
  arXiv  Detail & Related papers  (2023-07-08T03:39:22Z)
• Addressing Strategic Manipulation Disparities in Fair Classification [15.032416453073086]
  We show that individuals from minority groups often pay a higher cost to update their features. We propose a constrained optimization framework that constructs classifiers that lower the strategic manipulation cost for minority groups. Empirically, we show the efficacy of this approach over multiple real-world datasets.
  arXiv  Detail & Related papers  (2022-05-22T14:59:40Z)
• Risk Consistent Multi-Class Learning from Label Proportions [64.0125322353281]
  This study addresses a multiclass learning from label proportions (MCLLP) setting in which training instances are provided in bags. Most existing MCLLP methods impose bag-wise constraints on the prediction of instances or assign them pseudo-labels. A risk-consistent method is proposed for instance classification using the empirical risk minimization framework.
  arXiv  Detail & Related papers  (2022-03-24T03:49:04Z)
• Self-Certifying Classification by Linearized Deep Assignment [65.0100925582087]
  We propose a novel class of deep predictors for classifying metric data on graphs within PAC-Bayes risk certification paradigm. Building on the recent PAC-Bayes literature and data-dependent priors, this approach enables learning posterior distributions on the hypothesis space.
  arXiv  Detail & Related papers  (2022-01-26T19:59:14Z)
• Contrastive Learning for Fair Representations [50.95604482330149]
  Trained classification models can unintentionally lead to biased representations and predictions. Existing debiasing methods for classification models, such as adversarial training, are often expensive to train and difficult to optimise. We propose a method for mitigating bias by incorporating contrastive learning, in which instances sharing the same class label are encouraged to have similar representations.
  arXiv  Detail & Related papers  (2021-09-22T10:47:51Z)
• Selective Classification via One-Sided Prediction [54.05407231648068]
  One-sided prediction (OSP) based relaxation yields an SC scheme that attains near-optimal coverage in the practically relevant high target accuracy regime. We theoretically derive bounds generalization for SC and OSP, and empirically we show that our scheme strongly outperforms state of the art methods in coverage at small error levels.
  arXiv  Detail & Related papers  (2020-10-15T16:14:27Z)
• Towards Model-Agnostic Post-Hoc Adjustment for Balancing Ranking Fairness and Algorithm Utility [54.179859639868646]
  Bipartite ranking aims to learn a scoring function that ranks positive individuals higher than negative ones from labeled data. There have been rising concerns on whether the learned scoring function can cause systematic disparity across different protected groups. We propose a model post-processing framework for balancing them in the bipartite ranking scenario.
  arXiv  Detail & Related papers  (2020-06-15T10:08:39Z)

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.