---
_id: '10802'
abstract:
- lang: eng
  text: "Addressing fairness concerns about machine learning models is a crucial step
    towards their long-term adoption in real-world automated systems. While many approaches
    have been developed for training fair models from data, little is known about
    the robustness of these methods to data corruption. In this work we consider fairness-aware
    learning under worst-case data manipulations. We show that an adversary can in
    some situations force any learner to return an overly biased classifier, regardless
    of the sample size and with or without degrading\r\naccuracy, and that the strength
    of the excess bias increases for learning problems with underrepresented protected
    groups in the data. We also prove that our hardness results are tight up to constant
    factors. To this end, we study two natural learning algorithms that optimize for
    both accuracy and fairness and show that these algorithms enjoy guarantees that
    are order-optimal in terms of the corruption ratio and the protected groups frequencies
    in the large data\r\nlimit."
acknowledgement: The authors thank Eugenia Iofinova and Bernd Prach for providing
  feedback on early versions of this paper. This publication was made possible by
  an ETH AI Center postdoctoral fellowship to Nikola Konstantinov.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Nikola H
  full_name: Konstantinov, Nikola H
  id: 4B9D76E4-F248-11E8-B48F-1D18A9856A87
  last_name: Konstantinov
  orcid: 0009-0009-5204-7621
- first_name: Christoph
  full_name: Lampert, Christoph
  id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
  last_name: Lampert
  orcid: 0000-0002-4561-241X
citation:
  ama: Konstantinov NH, Lampert C. Fairness-aware PAC learning from corrupted data.
    <i>Journal of Machine Learning Research</i>. 2022;23:1-60.
  apa: Konstantinov, N. H., &#38; Lampert, C. (2022). Fairness-aware PAC learning
    from corrupted data. <i>Journal of Machine Learning Research</i>. ML Research
    Press.
  chicago: Konstantinov, Nikola H, and Christoph Lampert. “Fairness-Aware PAC Learning
    from Corrupted Data.” <i>Journal of Machine Learning Research</i>. ML Research
    Press, 2022.
  ieee: N. H. Konstantinov and C. Lampert, “Fairness-aware PAC learning from corrupted
    data,” <i>Journal of Machine Learning Research</i>, vol. 23. ML Research Press,
    pp. 1–60, 2022.
  ista: Konstantinov NH, Lampert C. 2022. Fairness-aware PAC learning from corrupted
    data. Journal of Machine Learning Research. 23, 1–60.
  mla: Konstantinov, Nikola H., and Christoph Lampert. “Fairness-Aware PAC Learning
    from Corrupted Data.” <i>Journal of Machine Learning Research</i>, vol. 23, ML
    Research Press, 2022, pp. 1–60.
  short: N.H. Konstantinov, C. Lampert, Journal of Machine Learning Research 23 (2022)
    1–60.
corr_author: '1'
date_created: 2022-02-28T14:05:42Z
date_published: 2022-05-01T00:00:00Z
date_updated: 2026-04-07T14:19:48Z
day: '01'
ddc:
- '004'
department:
- _id: ChLa
external_id:
  arxiv:
  - '2102.06004'
file:
- access_level: open_access
  checksum: 9cac897b54a0ddf3a553a2c33e88cfda
  content_type: application/pdf
  creator: kschuh
  date_created: 2022-07-12T15:08:28Z
  date_updated: 2022-07-12T15:08:28Z
  file_id: '11570'
  file_name: 2022_JournalMachineLearningResearch_Konstantinov.pdf
  file_size: 551862
  relation: main_file
  success: 1
file_date_updated: 2022-07-12T15:08:28Z
has_accepted_license: '1'
intvolume: '        23'
keyword:
- Fairness
- robustness
- data poisoning
- trustworthy machine learning
- PAC learning
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
page: 1-60
publication: Journal of Machine Learning Research
publication_identifier:
  eissn:
  - 1533-7928
  issn:
  - 1532-4435
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
related_material:
  record:
  - id: '13241'
    relation: shorter_version
    status: public
  - id: '10799'
    relation: dissertation_contains
    status: public
scopus_import: '1'
status: public
title: Fairness-aware PAC learning from corrupted data
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 23
year: '2022'
...