# Finite-Sample and Distribution-Free Fair Classification: Optimal Trade-off Between Excess Risk and Fairness, and the Cost of Group-Blindness

arXiv: https://arxiv.org/abs/2410.16477 · HTML: https://mlsanity.com/paper/2410.16477/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Oct 2024.

## Built on by (most cited first, 3 of 3)

- [Randomized multi-class classification under system constraints: a unified approach via post-processing](https://mlsanity.com/paper/2512.14246/) (2025)
- [Federated fairness-aware classification under differential privacy](https://mlsanity.com/paper/2603.24392/) (2026)
- [A Comprehensive View of Fairness through Distributional Stability](https://mlsanity.com/paper/2609.37061/) (2026)

## Abstract (arXiv)

Algorithmic fairness has become a central concern in modern machine learning and AI applications. However, two pressing challenges remain: (1) The fairness guarantees of existing methods often rely on specific data distributional assumptions and large sample sizes, which can lead to fairness violations in practice. (2) Due to legal and societal considerations, using sensitive group attributes during decision-making (referred to as the group-blind setting) may not always be feasible. In this work, we quantify the impact of enforcing algorithmic fairness and group-blindness/awareness in binary classification under group fairness constraints. Specifically, we propose a unified framework for fair classification that provides distribution-free and finite-sample fairness guarantees with controlled excess risk. This framework is applicable to various group fairness notions in both group-aware and group-blind scenarios. Our approach is based on a post-processing procedure that can be applied to arbitrary black-box models, making it directly compatible with modern machine learning pipelines. Furthermore, we establish a minimax lower bound showing the minimax rate-optimality of our proposed algorithm up to logarithmic factors. Through extensive synthetic and real data studies, we further demonstrate the competitive or superior performance of our algorithm compared to existing methods, and provide empirical support for our theoretical findings.