Sample Complexity of Bias Detection with Subsampled Point-to-Subspace Distances
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916597882421248 |
|---|---|
| author | Matilla, German Martinez Marecek, Jakub |
| author_facet | Matilla, German Martinez Marecek, Jakub |
| contents | Sample complexity of bias estimation is a lower bound on the runtime of any bias detection method. Many regulatory frameworks require the bias to be tested for all subgroups, whose number grows exponentially with the number of protected attributes. Unless one wishes to run a bias detection with a doubly-exponential run-time, one should like to have polynomial complexity of bias detection for a single subgroup. At the same time, the reference data may be based on surveys, and thus come with non-trivial uncertainty.
Here, we reformulate bias detection as a point-to-subspace problem on the space of measures and show that, for supremum norm, it can be subsampled efficiently. In particular, our probabilistically approximately correct (PAC) results are corroborated by tests on well-known instances. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_02623 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Sample Complexity of Bias Detection with Subsampled Point-to-Subspace Distances Matilla, German Martinez Marecek, Jakub Machine Learning Artificial Intelligence Statistics Theory Sample complexity of bias estimation is a lower bound on the runtime of any bias detection method. Many regulatory frameworks require the bias to be tested for all subgroups, whose number grows exponentially with the number of protected attributes. Unless one wishes to run a bias detection with a doubly-exponential run-time, one should like to have polynomial complexity of bias detection for a single subgroup. At the same time, the reference data may be based on surveys, and thus come with non-trivial uncertainty. Here, we reformulate bias detection as a point-to-subspace problem on the space of measures and show that, for supremum norm, it can be subsampled efficiently. In particular, our probabilistically approximately correct (PAC) results are corroborated by tests on well-known instances. |
| title | Sample Complexity of Bias Detection with Subsampled Point-to-Subspace Distances |
| topic | Machine Learning Artificial Intelligence Statistics Theory |
| url | https://arxiv.org/abs/2502.02623 |