---
_id: '8724'
abstract:
- lang: eng
  text: "We study the problem of learning from multiple untrusted data sources, a
    scenario of increasing practical relevance given the recent emergence of crowdsourcing
    and collaborative learning paradigms. Specifically, we analyze the situation in
    which a learning system obtains datasets from multiple sources, some of which
    might be biased or even adversarially perturbed. It is\r\nknown that in the single-source
    case, an adversary with the power to corrupt a fixed fraction of the training
    data can prevent PAC-learnability, that is, even in the limit of infinitely much
    training data, no learning system can approach the optimal test error. In this
    work we show that, surprisingly, the same is not true in the multi-source setting,
    where the adversary can arbitrarily\r\ncorrupt a fixed fraction of the data sources.
    Our main results are a generalization bound that provides finite-sample guarantees
    for this learning setting, as well as corresponding lower bounds. Besides establishing
    PAC-learnability our results also show that in a cooperative learning setting
    sharing data with other parties has provable benefits, even if some\r\nparticipants
    are malicious. "
acknowledged_ssus:
- _id: ScienComp
acknowledgement: Dan Alistarh is supported in part by the European Research Council
  (ERC) under the European Union’s Horizon 2020 research and innovation programme
  (grant agreement No 805223 ScaleML). This research was supported by the Scientific
  Service Units (SSU) of IST Austria through resources provided by Scientific Computing
  (SciComp).
article_processing_charge: No
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: Elias
  full_name: Frantar, Elias
  id: 09a8f98d-ec99-11ea-ae11-c063a7b7fe5f
  last_name: Frantar
- first_name: Dan-Adrian
  full_name: Alistarh, Dan-Adrian
  id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
  last_name: Alistarh
  orcid: 0000-0003-3650-940X
- first_name: Christoph
  full_name: Lampert, Christoph
  id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
  last_name: Lampert
  orcid: 0000-0001-8622-7887
citation:
  ama: 'Konstantinov NH, Frantar E, Alistarh D-A, Lampert C. On the sample complexity
    of adversarial multi-source PAC learning. In: <i>Proceedings of the 37th International
    Conference on Machine Learning</i>. Vol 119. ML Research Press; 2020:5416-5425.'
  apa: 'Konstantinov, N. H., Frantar, E., Alistarh, D.-A., &#38; Lampert, C. (2020).
    On the sample complexity of adversarial multi-source PAC learning. In <i>Proceedings
    of the 37th International Conference on Machine Learning</i> (Vol. 119, pp. 5416–5425).
    Online: ML Research Press.'
  chicago: Konstantinov, Nikola H, Elias Frantar, Dan-Adrian Alistarh, and Christoph
    Lampert. “On the Sample Complexity of Adversarial Multi-Source PAC Learning.”
    In <i>Proceedings of the 37th International Conference on Machine Learning</i>,
    119:5416–25. ML Research Press, 2020.
  ieee: N. H. Konstantinov, E. Frantar, D.-A. Alistarh, and C. Lampert, “On the sample
    complexity of adversarial multi-source PAC learning,” in <i>Proceedings of the
    37th International Conference on Machine Learning</i>, Online, 2020, vol. 119,
    pp. 5416–5425.
  ista: 'Konstantinov NH, Frantar E, Alistarh D-A, Lampert C. 2020. On the sample
    complexity of adversarial multi-source PAC learning. Proceedings of the 37th International
    Conference on Machine Learning. ICML: International Conference on Machine Learning
    vol. 119, 5416–5425.'
  mla: Konstantinov, Nikola H., et al. “On the Sample Complexity of Adversarial Multi-Source
    PAC Learning.” <i>Proceedings of the 37th International Conference on Machine
    Learning</i>, vol. 119, ML Research Press, 2020, pp. 5416–25.
  short: N.H. Konstantinov, E. Frantar, D.-A. Alistarh, C. Lampert, in:, Proceedings
    of the 37th International Conference on Machine Learning, ML Research Press, 2020,
    pp. 5416–5425.
conference:
  end_date: 2020-07-18
  location: Online
  name: 'ICML: International Conference on Machine Learning'
  start_date: 2020-07-12
corr_author: '1'
date_created: 2020-11-05T15:25:58Z
date_published: 2020-07-12T00:00:00Z
date_updated: 2026-04-07T14:19:48Z
day: '12'
ddc:
- '000'
department:
- _id: DaAl
- _id: ChLa
ec_funded: 1
external_id:
  arxiv:
  - '2002.10384'
file:
- access_level: open_access
  checksum: cc755d0054bc4b2be778ea7aa7884d2f
  content_type: application/pdf
  creator: dernst
  date_created: 2021-02-15T09:00:01Z
  date_updated: 2021-02-15T09:00:01Z
  file_id: '9120'
  file_name: 2020_PMLR_Konstantinov.pdf
  file_size: 281286
  relation: main_file
  success: 1
file_date_updated: 2021-02-15T09:00:01Z
has_accepted_license: '1'
intvolume: '       119'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 5416-5425
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '805223'
  name: Elastic Coordination for Scalable Machine Learning
publication: Proceedings of the 37th International Conference on Machine Learning
publication_identifier:
  issn:
  - 2640-3498
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
related_material:
  link:
  - relation: supplementary_material
    url: http://proceedings.mlr.press/v119/konstantinov20a/konstantinov20a-supp.pdf
  record:
  - id: '10799'
    relation: dissertation_contains
    status: public
scopus_import: '1'
status: public
title: On the sample complexity of adversarial multi-source PAC learning
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 119
year: '2020'
...