---
_id: '12495'
abstract:
- lang: eng
  text: "Fairness-aware learning aims at constructing classifiers that not only make
    accurate predictions, but also do not discriminate against specific groups. It
    is a fast-growing area of\r\nmachine learning with far-reaching societal impact.
    However, existing fair learning methods\r\nare vulnerable to accidental or malicious
    artifacts in the training data, which can cause\r\nthem to unknowingly produce
    unfair classifiers. In this work we address the problem of\r\nfair learning from
    unreliable training data in the robust multisource setting, where the\r\navailable
    training data comes from multiple sources, a fraction of which might not be representative
    of the true data distribution. We introduce FLEA, a filtering-based algorithm\r\nthat
    identifies and suppresses those data sources that would have a negative impact
    on\r\nfairness or accuracy if they were used for training. As such, FLEA is not
    a replacement of\r\nprior fairness-aware learning methods but rather an augmentation
    that makes any of them\r\nrobust against unreliable training data. We show the
    effectiveness of our approach by a\r\ndiverse range of experiments on multiple
    datasets. Additionally, we prove formally that\r\n–given enough data– FLEA protects
    the learner against corruptions as long as the fraction of\r\naffected data sources
    is less than half. Our source code and documentation are available at\r\nhttps://github.com/ISTAustria-CVML/FLEA."
acknowledged_ssus:
- _id: ScienComp
acknowledgement: 'The authors would like to thank Bernd Prach, Elias Frantar, Alexandra
  Peste, Mahdi Nikdan, and Peter Súkeník for their helpful feedback. This research
  was supported by the Scientific Service Units (SSU) of IST Austria through resources
  provided by Scientific Computing (SciComp). This publication was made possible by
  an ETH AI Center postdoctoral fellowship granted to Nikola Konstantinov. Eugenia
  Iofinova was supported in part by the FWF DK VGSCO, grant agreement number W1260-N35. '
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Eugenia B
  full_name: Iofinova, Eugenia B
  id: f9a17499-f6e0-11ea-865d-fdf9a3f77117
  last_name: Iofinova
  orcid: 0000-0002-7778-3221
- 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-0001-8622-7887
citation:
  ama: 'Iofinova EB, Konstantinov NH, Lampert C. FLEA: Provably robust fair multisource
    learning from unreliable training data. <i>Transactions on Machine Learning Research</i>.
    2022.'
  apa: 'Iofinova, E. B., Konstantinov, N. H., &#38; Lampert, C. (2022). FLEA: Provably
    robust fair multisource learning from unreliable training data. <i>Transactions
    on Machine Learning Research</i>. ML Research Press.'
  chicago: 'Iofinova, Eugenia B, Nikola H Konstantinov, and Christoph Lampert. “FLEA:
    Provably Robust Fair Multisource Learning from Unreliable Training Data.” <i>Transactions
    on Machine Learning Research</i>. ML Research Press, 2022.'
  ieee: 'E. B. Iofinova, N. H. Konstantinov, and C. Lampert, “FLEA: Provably robust
    fair multisource learning from unreliable training data,” <i>Transactions on Machine
    Learning Research</i>. ML Research Press, 2022.'
  ista: 'Iofinova EB, Konstantinov NH, Lampert C. 2022. FLEA: Provably robust fair
    multisource learning from unreliable training data. Transactions on Machine Learning
    Research.'
  mla: 'Iofinova, Eugenia B., et al. “FLEA: Provably Robust Fair Multisource Learning
    from Unreliable Training Data.” <i>Transactions on Machine Learning Research</i>,
    ML Research Press, 2022.'
  short: E.B. Iofinova, N.H. Konstantinov, C. Lampert, Transactions on Machine Learning
    Research (2022).
corr_author: '1'
date_created: 2023-02-02T20:29:57Z
date_published: 2022-12-22T00:00:00Z
date_updated: 2025-12-30T11:04:31Z
day: '22'
ddc:
- '000'
department:
- _id: ChLa
external_id:
  arxiv:
  - '2106.11732'
file:
- access_level: open_access
  checksum: 97c8a8470759cab597abb973ca137a3b
  content_type: application/pdf
  creator: dernst
  date_created: 2023-02-23T10:30:04Z
  date_updated: 2023-02-23T10:30:04Z
  file_id: '12673'
  file_name: 2022_TMLR_Iofinova.pdf
  file_size: 1948063
  relation: main_file
  success: 1
file_date_updated: 2023-02-23T10:30:04Z
has_accepted_license: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://openreview.net/forum?id=XsPopigZXV
month: '12'
oa: 1
oa_version: Published Version
project:
- _id: 9B9290DE-BA93-11EA-9121-9846C619BF3A
  grant_number: W1260-N35
  name: Vienna Graduate School on Computational Optimization
publication: Transactions on Machine Learning Research
publication_identifier:
  issn:
  - 2835-8856
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
related_material:
  link:
  - description: source code
    relation: software
    url: https://github.com/ISTAustria-CVML/FLEA
status: public
title: 'FLEA: Provably robust fair multisource learning from unreliable training 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
year: '2022'
...
---
_id: '13241'
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. Many approaches
    for training fair models from data have been developed and an implicit assumption
    about such algorithms is that they are able to recover a fair model, despite potential
    historical biases in the data. In this work we show a number of impossibility
    results that indicate that there is no learning algorithm that can recover a fair
    model when a proportion of the dataset is subject to arbitrary manipulations.
    Specifically, we prove that there are situations in which an adversary can force
    any learner to return a biased classifier, with or without degrading accuracy,
    and that the strength of this bias increases for learning problems with underrepresented
    protected groups in the data. Our results emphasize on the importance of studying
    further data corruption models of various strength and of establishing stricter
    data collection practices for fairness-aware learning.
acknowledgement: "This paper is a shortened, workshop version of Konstantinov and
  Lampert (2021),\r\nhttps://arxiv.org/abs/2102.06004. For further results, including
  an analysis of algorithms achieving the lower bounds from this paper, we refer to
  the full version."
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
- 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, Lampert C. On the impossibility of fairness-aware learning
    from corrupted data. In: <i>Proceedings of Machine Learning Research</i>. Vol
    171. ML Research Press; 2022:59-83.'
  apa: Konstantinov, N. H., &#38; Lampert, C. (2022). On the impossibility of fairness-aware
    learning from corrupted data. In <i>Proceedings of Machine Learning Research</i>
    (Vol. 171, pp. 59–83). ML Research Press.
  chicago: Konstantinov, Nikola H, and Christoph Lampert. “On the Impossibility of
    Fairness-Aware Learning from Corrupted Data.” In <i>Proceedings of Machine Learning
    Research</i>, 171:59–83. ML Research Press, 2022.
  ieee: N. H. Konstantinov and C. Lampert, “On the impossibility of fairness-aware
    learning from corrupted data,” in <i>Proceedings of Machine Learning Research</i>,
    2022, vol. 171, pp. 59–83.
  ista: Konstantinov NH, Lampert C. 2022. On the impossibility of fairness-aware learning
    from corrupted data. Proceedings of Machine Learning Research. vol. 171, 59–83.
  mla: Konstantinov, Nikola H., and Christoph Lampert. “On the Impossibility of Fairness-Aware
    Learning from Corrupted Data.” <i>Proceedings of Machine Learning Research</i>,
    vol. 171, ML Research Press, 2022, pp. 59–83.
  short: N.H. Konstantinov, C. Lampert, in:, Proceedings of Machine Learning Research,
    ML Research Press, 2022, pp. 59–83.
corr_author: '1'
date_created: 2023-07-16T22:01:13Z
date_published: 2022-12-01T00:00:00Z
date_updated: 2024-10-09T21:05:54Z
day: '01'
department:
- _id: ChLa
external_id:
  arxiv:
  - '2102.06004'
intvolume: '       171'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/2102.06004
month: '12'
oa: 1
oa_version: Preprint
page: 59-83
publication: Proceedings of Machine Learning Research
publication_identifier:
  eissn:
  - 2640-3498
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
related_material:
  record:
  - id: '10802'
    relation: extended_version
    status: public
scopus_import: '1'
status: public
title: On the impossibility of fairness-aware learning from corrupted data
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 171
year: '2022'
...
---
OA_place: publisher
_id: '10799'
abstract:
- lang: eng
  text: "Because of the increasing popularity of machine learning methods, it is becoming
    important to understand the impact of learned components on automated decision-making
    systems and to guarantee that their consequences are beneficial to society. In
    other words, it is necessary to ensure that machine learning is sufficiently trustworthy
    to be used in real-world applications. This thesis studies two properties of machine
    learning models that are highly desirable for the\r\nsake of reliability: robustness
    and fairness. In the first part of the thesis we study the robustness of learning
    algorithms to training data corruption. Previous work has shown that machine learning
    models are vulnerable to a range\r\nof training set issues, varying from label
    noise through systematic biases to worst-case data manipulations. This is an especially
    relevant problem from a present perspective, since modern machine learning methods
    are particularly data hungry and therefore practitioners often have to rely on
    data collected from various external sources, e.g. from the Internet, from app
    users or via crowdsourcing. Naturally, such sources vary greatly in the quality
    and reliability of the\r\ndata they provide. With these considerations in mind,
    we study the problem of designing machine learning algorithms that are robust
    to corruptions in data coming from multiple sources. We show that, in contrast
    to the case of a single dataset with outliers, successful learning within this
    model is possible both theoretically and practically, even under worst-case data
    corruptions. The second part of this thesis deals with fairness-aware machine
    learning. There are multiple areas where machine learning models have shown promising
    results, but where careful considerations are required, in order to avoid discrimanative
    decisions taken by such learned components. Ensuring fairness can be particularly
    challenging, because real-world training datasets are expected to contain various
    forms of historical bias that may affect the learning process. In this thesis
    we show that data corruption can indeed render the problem of achieving fairness
    impossible, by tightly characterizing the theoretical limits of fair learning
    under worst-case data manipulations. However, assuming access to clean data, we
    also show how fairness-aware learning can be made practical in contexts beyond
    binary classification, in particular in the challenging learning to rank setting."
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Nikola H
  full_name: Konstantinov, Nikola H
  id: 4B9D76E4-F248-11E8-B48F-1D18A9856A87
  last_name: Konstantinov
  orcid: 0009-0009-5204-7621
citation:
  ama: Konstantinov NH. Robustness and fairness in machine learning. 2022. doi:<a
    href="https://doi.org/10.15479/at:ista:10799">10.15479/at:ista:10799</a>
  apa: Konstantinov, N. H. (2022). <i>Robustness and fairness in machine learning</i>.
    Institute of Science and Technology Austria. <a href="https://doi.org/10.15479/at:ista:10799">https://doi.org/10.15479/at:ista:10799</a>
  chicago: Konstantinov, Nikola H. “Robustness and Fairness in Machine Learning.”
    Institute of Science and Technology Austria, 2022. <a href="https://doi.org/10.15479/at:ista:10799">https://doi.org/10.15479/at:ista:10799</a>.
  ieee: N. H. Konstantinov, “Robustness and fairness in machine learning,” Institute
    of Science and Technology Austria, 2022.
  ista: Konstantinov NH. 2022. Robustness and fairness in machine learning. Institute
    of Science and Technology Austria.
  mla: Konstantinov, Nikola H. <i>Robustness and Fairness in Machine Learning</i>.
    Institute of Science and Technology Austria, 2022, doi:<a href="https://doi.org/10.15479/at:ista:10799">10.15479/at:ista:10799</a>.
  short: N.H. Konstantinov, Robustness and Fairness in Machine Learning, Institute
    of Science and Technology Austria, 2022.
corr_author: '1'
date_created: 2022-02-28T13:03:49Z
date_published: 2022-03-08T00:00:00Z
date_updated: 2026-04-07T14:19:48Z
day: '08'
ddc:
- '000'
degree_awarded: PhD
department:
- _id: GradSch
- _id: ChLa
doi: 10.15479/at:ista:10799
ec_funded: 1
file:
- access_level: open_access
  checksum: 626bc523ae8822d20e635d0e2d95182e
  content_type: application/pdf
  creator: nkonstan
  date_created: 2022-03-06T11:42:54Z
  date_updated: 2022-03-06T11:42:54Z
  file_id: '10823'
  file_name: thesis.pdf
  file_size: 4204905
  relation: main_file
  success: 1
- access_level: closed
  checksum: e2ca2b88350ac8ea1515b948885cbcb1
  content_type: application/x-zip-compressed
  creator: nkonstan
  date_created: 2022-03-06T11:42:57Z
  date_updated: 2022-03-10T12:11:48Z
  file_id: '10824'
  file_name: thesis.zip
  file_size: 22841103
  relation: source_file
file_date_updated: 2022-03-10T12:11:48Z
has_accepted_license: '1'
keyword:
- robustness
- fairness
- machine learning
- PAC learning
- adversarial learning
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
page: '176'
project:
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '665385'
  name: International IST Doctoral Program
publication_identifier:
  isbn:
  - 978-3-99078-015-2
  issn:
  - 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
  record:
  - id: '10802'
    relation: part_of_dissertation
    status: public
  - id: '10803'
    relation: part_of_dissertation
    status: public
  - id: '6590'
    relation: part_of_dissertation
    status: public
  - id: '8724'
    relation: part_of_dissertation
    status: public
status: public
supervisor:
- first_name: Christoph
  full_name: Lampert, Christoph
  id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
  last_name: Lampert
  orcid: 0000-0001-8622-7887
title: Robustness and fairness in machine learning
type: dissertation
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2022'
...
---
_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'
...
---
_id: '10803'
abstract:
- lang: eng
  text: Given the abundance of applications of ranking in recent years, addressing
    fairness concerns around automated ranking systems becomes necessary for increasing
    the trust among end-users. Previous work on fair ranking has mostly focused on
    application-specific fairness notions, often tailored to online advertising, and
    it rarely considers learning as part of the process. In this work, we show how
    to transfer numerous fairness notions from binary classification to a learning
    to rank setting. Our formalism allows us to design methods for incorporating fairness
    objectives with provable generalization guarantees. An extensive experimental
    evaluation shows that our method can improve ranking fairness substantially with
    no or only little loss of model quality.
article_number: '2102.05996'
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: 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 through regularization for learning to
    rank. <i>arXiv</i>. doi:<a href="https://doi.org/10.48550/arXiv.2102.05996">10.48550/arXiv.2102.05996</a>
  apa: Konstantinov, N. H., &#38; Lampert, C. (n.d.). Fairness through regularization
    for learning to rank. <i>arXiv</i>. <a href="https://doi.org/10.48550/arXiv.2102.05996">https://doi.org/10.48550/arXiv.2102.05996</a>
  chicago: Konstantinov, Nikola H, and Christoph Lampert. “Fairness through Regularization
    for Learning to Rank.” <i>ArXiv</i>, n.d. <a href="https://doi.org/10.48550/arXiv.2102.05996">https://doi.org/10.48550/arXiv.2102.05996</a>.
  ieee: N. H. Konstantinov and C. Lampert, “Fairness through regularization for learning
    to rank,” <i>arXiv</i>. .
  ista: Konstantinov NH, Lampert C. Fairness through regularization for learning to
    rank. arXiv, 2102.05996.
  mla: Konstantinov, Nikola H., and Christoph Lampert. “Fairness through Regularization
    for Learning to Rank.” <i>ArXiv</i>, 2102.05996, doi:<a href="https://doi.org/10.48550/arXiv.2102.05996">10.48550/arXiv.2102.05996</a>.
  short: N.H. Konstantinov, C. Lampert, ArXiv (n.d.).
corr_author: '1'
date_created: 2022-02-28T14:13:59Z
date_published: 2021-06-07T00:00:00Z
date_updated: 2026-04-07T14:19:48Z
day: '07'
department:
- _id: ChLa
doi: 10.48550/arXiv.2102.05996
external_id:
  arxiv:
  - '2102.05996'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/2102.05996
month: '06'
oa: 1
oa_version: Preprint
publication: arXiv
publication_status: draft
related_material:
  record:
  - id: '10799'
    relation: dissertation_contains
    status: public
status: public
title: Fairness through regularization for learning to rank
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...
---
_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'
...
---
_id: '6590'
abstract:
- lang: eng
  text: 'Modern machine learning methods often require more data for training than
    a single expert can provide. Therefore, it has become a standard procedure to
    collect data from external sources, e.g. via crowdsourcing. Unfortunately, the
    quality of these sources is not always guaranteed. As additional complications,
    the data might be stored in a distributed way, or might even have to remain private.
    In this work, we address the question of how to learn robustly in such scenarios.
    Studying the problem through the lens of statistical learning theory, we derive
    a procedure that allows for learning from all available sources, yet automatically
    suppresses irrelevant or corrupted data. We show by extensive experiments that
    our method provides significant improvements over alternative approaches from
    robust statistics and distributed optimization. '
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: Christoph
  full_name: Lampert, Christoph
  id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
  last_name: Lampert
  orcid: 0000-0001-8622-7887
citation:
  ama: 'Konstantinov NH, Lampert C. Robust learning from untrusted sources. In: <i>Proceedings
    of the 36th International Conference on Machine Learning</i>. Vol 97. ML Research
    Press; 2019:3488-3498.'
  apa: 'Konstantinov, N. H., &#38; Lampert, C. (2019). Robust learning from untrusted
    sources. In <i>Proceedings of the 36th International Conference on Machine Learning</i>
    (Vol. 97, pp. 3488–3498). Long Beach, CA, USA: ML Research Press.'
  chicago: Konstantinov, Nikola H, and Christoph Lampert. “Robust Learning from Untrusted
    Sources.” In <i>Proceedings of the 36th International Conference on Machine Learning</i>,
    97:3488–98. ML Research Press, 2019.
  ieee: N. H. Konstantinov and C. Lampert, “Robust learning from untrusted sources,”
    in <i>Proceedings of the 36th International Conference on Machine Learning</i>,
    Long Beach, CA, USA, 2019, vol. 97, pp. 3488–3498.
  ista: 'Konstantinov NH, Lampert C. 2019. Robust learning from untrusted sources.
    Proceedings of the 36th International Conference on Machine Learning. ICML: International
    Conference on Machine Learning vol. 97, 3488–3498.'
  mla: Konstantinov, Nikola H., and Christoph Lampert. “Robust Learning from Untrusted
    Sources.” <i>Proceedings of the 36th International Conference on Machine Learning</i>,
    vol. 97, ML Research Press, 2019, pp. 3488–98.
  short: N.H. Konstantinov, C. Lampert, in:, Proceedings of the 36th International
    Conference on Machine Learning, ML Research Press, 2019, pp. 3488–3498.
conference:
  end_date: 2919-06-15
  location: Long Beach, CA, USA
  name: 'ICML: International Conference on Machine Learning'
  start_date: 2019-06-10
date_created: 2019-06-27T14:18:23Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2026-04-07T14:19:48Z
day: '01'
department:
- _id: ChLa
ec_funded: 1
external_id:
  arxiv:
  - '1901.10310'
intvolume: '        97'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1901.10310
month: '06'
oa: 1
oa_version: Preprint
page: 3488-3498
project:
- _id: 2532554C-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '308036'
  name: Lifelong Learning of Visual Scene Understanding
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '665385'
  name: International IST Doctoral Program
publication: Proceedings of the 36th International Conference on Machine Learning
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
related_material:
  record:
  - id: '10799'
    relation: dissertation_contains
    status: public
scopus_import: '1'
status: public
title: Robust learning from untrusted sources
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 97
year: '2019'
...
---
_id: '5962'
abstract:
- lang: eng
  text: Stochastic Gradient Descent (SGD) is a fundamental algorithm in machine learning,
    representing the optimization backbone for training several classic models, from
    regression to neural networks. Given the recent practical focus on distributed
    machine learning, significant work has been dedicated to the convergence properties
    of this algorithm under the inconsistent and noisy updates arising from execution
    in a distributed environment. However, surprisingly, the convergence properties
    of this classic algorithm in the standard shared-memory model are still not well-understood.
    In this work, we address this gap, and provide new convergence bounds for lock-free
    concurrent stochastic gradient descent, executing in the classic asynchronous
    shared memory model, against a strong adaptive adversary. Our results give improved
    upper and lower bounds on the "price of asynchrony'' when executing the fundamental
    SGD algorithm in a concurrent setting. They show that this classic optimization
    tool can converge faster and with a wider range of parameters than previously
    known under asynchronous iterations. At the same time, we exhibit a fundamental
    trade-off between the maximum delay in the system and the rate at which SGD can
    converge, which governs the set of parameters under which this algorithm can still
    work efficiently.
article_processing_charge: No
arxiv: 1
author:
- 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: Christopher
  full_name: De Sa, Christopher
  last_name: De Sa
- first_name: Nikola H
  full_name: Konstantinov, Nikola H
  id: 4B9D76E4-F248-11E8-B48F-1D18A9856A87
  last_name: Konstantinov
citation:
  ama: 'Alistarh D-A, De Sa C, Konstantinov NH. The convergence of stochastic gradient
    descent in asynchronous shared memory. In: <i>Proceedings of the 2018 ACM Symposium
    on Principles of Distributed Computing  - PODC ’18</i>. ACM; 2018:169-178. doi:<a
    href="https://doi.org/10.1145/3212734.3212763">10.1145/3212734.3212763</a>'
  apa: 'Alistarh, D.-A., De Sa, C., &#38; Konstantinov, N. H. (2018). The convergence
    of stochastic gradient descent in asynchronous shared memory. In <i>Proceedings
    of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18</i>
    (pp. 169–178). Egham, United Kingdom: ACM. <a href="https://doi.org/10.1145/3212734.3212763">https://doi.org/10.1145/3212734.3212763</a>'
  chicago: Alistarh, Dan-Adrian, Christopher De Sa, and Nikola H Konstantinov. “The
    Convergence of Stochastic Gradient Descent in Asynchronous Shared Memory.” In
    <i>Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing 
    - PODC ’18</i>, 169–78. ACM, 2018. <a href="https://doi.org/10.1145/3212734.3212763">https://doi.org/10.1145/3212734.3212763</a>.
  ieee: D.-A. Alistarh, C. De Sa, and N. H. Konstantinov, “The convergence of stochastic
    gradient descent in asynchronous shared memory,” in <i>Proceedings of the 2018
    ACM Symposium on Principles of Distributed Computing  - PODC ’18</i>, Egham, United
    Kingdom, 2018, pp. 169–178.
  ista: 'Alistarh D-A, De Sa C, Konstantinov NH. 2018. The convergence of stochastic
    gradient descent in asynchronous shared memory. Proceedings of the 2018 ACM Symposium
    on Principles of Distributed Computing  - PODC ’18. PODC: Principles of Distributed
    Computing, 169–178.'
  mla: Alistarh, Dan-Adrian, et al. “The Convergence of Stochastic Gradient Descent
    in Asynchronous Shared Memory.” <i>Proceedings of the 2018 ACM Symposium on Principles
    of Distributed Computing  - PODC ’18</i>, ACM, 2018, pp. 169–78, doi:<a href="https://doi.org/10.1145/3212734.3212763">10.1145/3212734.3212763</a>.
  short: D.-A. Alistarh, C. De Sa, N.H. Konstantinov, in:, Proceedings of the 2018
    ACM Symposium on Principles of Distributed Computing  - PODC ’18, ACM, 2018, pp.
    169–178.
conference:
  end_date: 2018-07-27
  location: Egham, United Kingdom
  name: 'PODC: Principles of Distributed Computing'
  start_date: 2018-07-23
date_created: 2019-02-13T09:58:58Z
date_published: 2018-07-23T00:00:00Z
date_updated: 2025-06-03T11:56:41Z
day: '23'
department:
- _id: DaAl
doi: 10.1145/3212734.3212763
external_id:
  arxiv:
  - '1803.08841'
  isi:
  - '000458186900022'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1803.08841
month: '07'
oa: 1
oa_version: Preprint
page: 169-178
publication: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  -
  PODC '18
publication_identifier:
  isbn:
  - '9781450357951'
publication_status: published
publisher: ACM
quality_controlled: '1'
scopus_import: '1'
status: public
title: The convergence of stochastic gradient descent in asynchronous shared memory
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2018'
...
---
_id: '6589'
abstract:
- lang: eng
  text: Distributed training of massive machine learning models, in particular deep
    neural networks, via Stochastic Gradient Descent (SGD) is becoming commonplace.
    Several families of communication-reduction methods, such as quantization, large-batch
    methods, and gradient sparsification, have been proposed. To date, gradient sparsification
    methods--where each node sorts gradients by magnitude, and only communicates a
    subset of the components, accumulating the rest locally--are known to yield some
    of the largest practical gains. Such methods can reduce the amount of communication
    per step by up to \emph{three orders of magnitude}, while preserving model accuracy.
    Yet, this family of methods currently has no theoretical justification. This is
    the question we address in this paper. We prove that, under analytic assumptions,
    sparsifying gradients by magnitude with local error correction provides convergence
    guarantees, for both convex and non-convex smooth objectives, for data-parallel
    SGD. The main insight is that sparsification methods implicitly maintain bounds
    on the maximum impact of stale updates, thanks to selection by magnitude. Our
    analysis and empirical validation also reveal that these methods do require analytical
    conditions to converge well, justifying existing heuristics.
article_processing_charge: No
arxiv: 1
author:
- 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: Torsten
  full_name: Hoefler, Torsten
  last_name: Hoefler
- first_name: Mikael
  full_name: Johansson, Mikael
  last_name: Johansson
- first_name: Nikola H
  full_name: Konstantinov, Nikola H
  id: 4B9D76E4-F248-11E8-B48F-1D18A9856A87
  last_name: Konstantinov
- first_name: Sarit
  full_name: Khirirat, Sarit
  last_name: Khirirat
- first_name: Cedric
  full_name: Renggli, Cedric
  last_name: Renggli
citation:
  ama: 'Alistarh D-A, Hoefler T, Johansson M, Konstantinov NH, Khirirat S, Renggli
    C. The convergence of sparsified gradient methods. In: <i>Advances in Neural Information
    Processing Systems 31</i>. Vol Volume 2018. Neural Information Processing Systems
    Foundation; 2018:5973-5983.'
  apa: 'Alistarh, D.-A., Hoefler, T., Johansson, M., Konstantinov, N. H., Khirirat,
    S., &#38; Renggli, C. (2018). The convergence of sparsified gradient methods.
    In <i>Advances in Neural Information Processing Systems 31</i> (Vol. Volume 2018,
    pp. 5973–5983). Montreal, Canada: Neural Information Processing Systems Foundation.'
  chicago: Alistarh, Dan-Adrian, Torsten Hoefler, Mikael Johansson, Nikola H Konstantinov,
    Sarit Khirirat, and Cedric Renggli. “The Convergence of Sparsified Gradient Methods.”
    In <i>Advances in Neural Information Processing Systems 31</i>, Volume 2018:5973–83.
    Neural Information Processing Systems Foundation, 2018.
  ieee: D.-A. Alistarh, T. Hoefler, M. Johansson, N. H. Konstantinov, S. Khirirat,
    and C. Renggli, “The convergence of sparsified gradient methods,” in <i>Advances
    in Neural Information Processing Systems 31</i>, Montreal, Canada, 2018, vol.
    Volume 2018, pp. 5973–5983.
  ista: 'Alistarh D-A, Hoefler T, Johansson M, Konstantinov NH, Khirirat S, Renggli
    C. 2018. The convergence of sparsified gradient methods. Advances in Neural Information
    Processing Systems 31. NeurIPS: Conference on Neural Information Processing Systems
    vol. Volume 2018, 5973–5983.'
  mla: Alistarh, Dan-Adrian, et al. “The Convergence of Sparsified Gradient Methods.”
    <i>Advances in Neural Information Processing Systems 31</i>, vol. Volume 2018,
    Neural Information Processing Systems Foundation, 2018, pp. 5973–83.
  short: D.-A. Alistarh, T. Hoefler, M. Johansson, N.H. Konstantinov, S. Khirirat,
    C. Renggli, in:, Advances in Neural Information Processing Systems 31, Neural
    Information Processing Systems Foundation, 2018, pp. 5973–5983.
conference:
  end_date: 2018-12-08
  location: Montreal, Canada
  name: 'NeurIPS: Conference on Neural Information Processing Systems'
  start_date: 2018-12-02
corr_author: '1'
date_created: 2019-06-27T09:32:55Z
date_published: 2018-12-01T00:00:00Z
date_updated: 2025-06-26T12:23:06Z
day: '01'
department:
- _id: DaAl
- _id: ChLa
ec_funded: 1
external_id:
  arxiv:
  - '1809.10505'
  isi:
  - '000461852000047'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1809.10505
month: '12'
oa: 1
oa_version: Preprint
page: 5973-5983
project:
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '665385'
  name: International IST Doctoral Program
publication: Advances in Neural Information Processing Systems 31
publication_status: published
publisher: Neural Information Processing Systems Foundation
quality_controlled: '1'
scopus_import: '1'
status: public
title: The convergence of sparsified gradient methods
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: Volume 2018
year: '2018'
...