[{"author":[{"full_name":"Iofinova, Eugenia B","first_name":"Eugenia B","last_name":"Iofinova","id":"f9a17499-f6e0-11ea-865d-fdf9a3f77117","orcid":"0000-0002-7778-3221"},{"id":"4B9D76E4-F248-11E8-B48F-1D18A9856A87","first_name":"Nikola H","last_name":"Konstantinov","full_name":"Konstantinov, Nikola H"},{"first_name":"Christoph","last_name":"Lampert","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8622-7887","full_name":"Lampert, Christoph"}],"related_material":{"link":[{"relation":"software","description":"source code","url":"https://github.com/ISTAustria-CVML/FLEA"}]},"date_created":"2023-02-02T20:29:57Z","date_updated":"2023-02-23T10:30:54Z","year":"2022","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. ","publication_status":"published","publisher":"ML Research Press","department":[{"_id":"ChLa"}],"file_date_updated":"2023-02-23T10:30:04Z","acknowledged_ssus":[{"_id":"ScienComp"}],"language":[{"iso":"eng"}],"external_id":{"arxiv":["2106.11732"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"main_file_link":[{"open_access":"1","url":"https://openreview.net/forum?id=XsPopigZXV"}],"quality_controlled":"1","project":[{"grant_number":" W1260-N35","_id":"9B9290DE-BA93-11EA-9121-9846C619BF3A","name":"Vienna Graduate School on Computational Optimization"}],"month":"12","publication_identifier":{"issn":["2835-8856"]},"oa_version":"Published Version","file":[{"access_level":"open_access","file_name":"2022_TMLR_Iofinova.pdf","file_size":1948063,"content_type":"application/pdf","creator":"dernst","relation":"main_file","file_id":"12673","checksum":"97c8a8470759cab597abb973ca137a3b","success":1,"date_updated":"2023-02-23T10:30:04Z","date_created":"2023-02-23T10:30:04Z"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"12495","ddc":["000"],"status":"public","title":"FLEA: Provably robust fair multisource learning from unreliable training data","abstract":[{"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.","lang":"eng"}],"type":"journal_article","date_published":"2022-12-22T00:00:00Z","publication":"Transactions on Machine Learning Research","citation":{"ista":"Iofinova EB, Konstantinov NH, Lampert C. 2022. FLEA: Provably robust fair multisource learning from unreliable training data. Transactions on Machine Learning Research.","apa":"Iofinova, E. B., Konstantinov, N. H., & Lampert, C. (2022). FLEA: Provably robust fair multisource learning from unreliable training data. Transactions on Machine Learning Research. ML Research Press.","ieee":"E. B. Iofinova, N. H. Konstantinov, and C. Lampert, “FLEA: Provably robust fair multisource learning from unreliable training data,” Transactions on Machine Learning Research. ML Research Press, 2022.","ama":"Iofinova EB, Konstantinov NH, Lampert C. FLEA: Provably robust fair multisource learning from unreliable training data. Transactions on Machine Learning Research. 2022.","chicago":"Iofinova, Eugenia B, Nikola H Konstantinov, and Christoph Lampert. “FLEA: Provably Robust Fair Multisource Learning from Unreliable Training Data.” Transactions on Machine Learning Research. ML Research Press, 2022.","mla":"Iofinova, Eugenia B., et al. “FLEA: Provably Robust Fair Multisource Learning from Unreliable Training Data.” Transactions on Machine Learning Research, ML Research Press, 2022.","short":"E.B. Iofinova, N.H. Konstantinov, C. Lampert, Transactions on Machine Learning Research (2022)."},"article_type":"original","day":"22","article_processing_charge":"No","has_accepted_license":"1"},{"month":"05","publication_identifier":{"issn":["1532-4435"],"eissn":["1533-7928"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"external_id":{"arxiv":["2102.06004"]},"oa":1,"quality_controlled":"1","language":[{"iso":"eng"}],"file_date_updated":"2022-07-12T15:08:28Z","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.","year":"2022","publication_status":"published","publisher":"ML Research Press","department":[{"_id":"ChLa"}],"author":[{"full_name":"Konstantinov, Nikola H","first_name":"Nikola H","last_name":"Konstantinov","id":"4B9D76E4-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Lampert, Christoph","first_name":"Christoph","last_name":"Lampert","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"}],"related_material":{"record":[{"id":"10799","relation":"dissertation_contains","status":"public"},{"id":"13241","status":"public","relation":"shorter_version"}]},"date_updated":"2023-09-26T10:44:37Z","date_created":"2022-02-28T14:05:42Z","volume":23,"scopus_import":"1","keyword":["Fairness","robustness","data poisoning","trustworthy machine learning","PAC learning"],"day":"01","article_processing_charge":"No","has_accepted_license":"1","publication":"Journal of Machine Learning Research","citation":{"short":"N.H. Konstantinov, C. Lampert, Journal of Machine Learning Research 23 (2022) 1–60.","mla":"Konstantinov, Nikola H., and Christoph Lampert. “Fairness-Aware PAC Learning from Corrupted Data.” Journal of Machine Learning Research, vol. 23, ML Research Press, 2022, pp. 1–60.","chicago":"Konstantinov, Nikola H, and Christoph Lampert. “Fairness-Aware PAC Learning from Corrupted Data.” Journal of Machine Learning Research. ML Research Press, 2022.","ama":"Konstantinov NH, Lampert C. Fairness-aware PAC learning from corrupted data. Journal of Machine Learning Research. 2022;23:1-60.","apa":"Konstantinov, N. H., & Lampert, C. (2022). Fairness-aware PAC learning from corrupted data. Journal of Machine Learning Research. ML Research Press.","ieee":"N. H. Konstantinov and C. Lampert, “Fairness-aware PAC learning from corrupted data,” Journal of Machine Learning Research, 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."},"article_type":"original","page":"1-60","date_published":"2022-05-01T00:00:00Z","type":"journal_article","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."}],"_id":"10802","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","ddc":["004"],"title":"Fairness-aware PAC learning from corrupted data","intvolume":" 23","file":[{"access_level":"open_access","file_name":"2022_JournalMachineLearningResearch_Konstantinov.pdf","creator":"kschuh","file_size":551862,"content_type":"application/pdf","file_id":"11570","relation":"main_file","success":1,"checksum":"9cac897b54a0ddf3a553a2c33e88cfda","date_created":"2022-07-12T15:08:28Z","date_updated":"2022-07-12T15:08:28Z"}],"oa_version":"Published Version"},{"abstract":[{"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.","lang":"eng"}],"type":"conference","oa_version":"Preprint","_id":"13241","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":" 171","status":"public","title":"On the impossibility of fairness-aware learning from corrupted data","article_processing_charge":"No","day":"01","scopus_import":"1","date_published":"2022-12-01T00:00:00Z","citation":{"chicago":"Konstantinov, Nikola H, and Christoph Lampert. “On the Impossibility of Fairness-Aware Learning from Corrupted Data.” In Proceedings of Machine Learning Research, 171:59–83. ML Research Press, 2022.","short":"N.H. Konstantinov, C. Lampert, in:, Proceedings of Machine Learning Research, ML Research Press, 2022, pp. 59–83.","mla":"Konstantinov, Nikola H., and Christoph Lampert. “On the Impossibility of Fairness-Aware Learning from Corrupted Data.” Proceedings of Machine Learning Research, vol. 171, ML Research Press, 2022, pp. 59–83.","ieee":"N. H. Konstantinov and C. Lampert, “On the impossibility of fairness-aware learning from corrupted data,” in Proceedings of Machine Learning Research, 2022, vol. 171, pp. 59–83.","apa":"Konstantinov, N. H., & Lampert, C. (2022). On the impossibility of fairness-aware learning from corrupted data. In Proceedings of Machine Learning Research (Vol. 171, pp. 59–83). ML Research Press.","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.","ama":"Konstantinov NH, Lampert C. On the impossibility of fairness-aware learning from corrupted data. In: Proceedings of Machine Learning Research. Vol 171. ML Research Press; 2022:59-83."},"publication":"Proceedings of Machine Learning Research","page":"59-83","related_material":{"record":[{"id":"10802","relation":"extended_version","status":"public"}]},"author":[{"last_name":"Konstantinov","first_name":"Nikola H","id":"4B9D76E4-F248-11E8-B48F-1D18A9856A87","full_name":"Konstantinov, Nikola H"},{"first_name":"Christoph","last_name":"Lampert","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8622-7887","full_name":"Lampert, Christoph"}],"volume":171,"date_updated":"2023-09-26T10:44:37Z","date_created":"2023-07-16T22:01:13Z","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.","year":"2022","publisher":"ML Research Press","department":[{"_id":"ChLa"}],"publication_status":"published","publication_identifier":{"eissn":["2640-3498"]},"month":"12","language":[{"iso":"eng"}],"external_id":{"arxiv":["2102.06004"]},"oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/2102.06004","open_access":"1"}],"quality_controlled":"1"},{"doi":"10.15479/at:ista:10799","language":[{"iso":"eng"}],"supervisor":[{"full_name":"Lampert, Christoph","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8622-7887","first_name":"Christoph","last_name":"Lampert"}],"degree_awarded":"PhD","oa":1,"project":[{"call_identifier":"H2020","name":"International IST Doctoral Program","grant_number":"665385","_id":"2564DBCA-B435-11E9-9278-68D0E5697425"}],"publication_identifier":{"isbn":["978-3-99078-015-2"],"issn":["2663-337X"]},"month":"03","related_material":{"record":[{"id":"8724","relation":"part_of_dissertation","status":"public"},{"id":"10803","relation":"part_of_dissertation","status":"public"},{"status":"public","relation":"part_of_dissertation","id":"10802"},{"id":"6590","status":"public","relation":"part_of_dissertation"}]},"author":[{"id":"4B9D76E4-F248-11E8-B48F-1D18A9856A87","first_name":"Nikola H","last_name":"Konstantinov","full_name":"Konstantinov, Nikola H"}],"date_created":"2022-02-28T13:03:49Z","date_updated":"2023-10-17T12:31:54Z","year":"2022","department":[{"_id":"GradSch"},{"_id":"ChLa"}],"publisher":"Institute of Science and Technology Austria","publication_status":"published","ec_funded":1,"file_date_updated":"2022-03-10T12:11:48Z","date_published":"2022-03-08T00:00:00Z","citation":{"ieee":"N. H. Konstantinov, “Robustness and fairness in machine learning,” Institute of Science and Technology Austria, 2022.","apa":"Konstantinov, N. H. (2022). Robustness and fairness in machine learning. Institute of Science and Technology Austria. https://doi.org/10.15479/at:ista:10799","ista":"Konstantinov NH. 2022. Robustness and fairness in machine learning. Institute of Science and Technology Austria.","ama":"Konstantinov NH. Robustness and fairness in machine learning. 2022. doi:10.15479/at:ista:10799","chicago":"Konstantinov, Nikola H. “Robustness and Fairness in Machine Learning.” Institute of Science and Technology Austria, 2022. https://doi.org/10.15479/at:ista:10799.","short":"N.H. Konstantinov, Robustness and Fairness in Machine Learning, Institute of Science and Technology Austria, 2022.","mla":"Konstantinov, Nikola H. Robustness and Fairness in Machine Learning. Institute of Science and Technology Austria, 2022, doi:10.15479/at:ista:10799."},"page":"176","has_accepted_license":"1","article_processing_charge":"No","day":"08","keyword":["robustness","fairness","machine learning","PAC learning","adversarial learning"],"oa_version":"Published Version","file":[{"relation":"main_file","file_id":"10823","date_updated":"2022-03-06T11:42:54Z","date_created":"2022-03-06T11:42:54Z","checksum":"626bc523ae8822d20e635d0e2d95182e","success":1,"file_name":"thesis.pdf","access_level":"open_access","content_type":"application/pdf","file_size":4204905,"creator":"nkonstan"},{"creator":"nkonstan","content_type":"application/x-zip-compressed","file_size":22841103,"access_level":"closed","file_name":"thesis.zip","checksum":"e2ca2b88350ac8ea1515b948885cbcb1","date_created":"2022-03-06T11:42:57Z","date_updated":"2022-03-10T12:11:48Z","file_id":"10824","relation":"source_file"}],"_id":"10799","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","title":"Robustness and fairness in machine learning","ddc":["000"],"status":"public","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."}],"type":"dissertation","alternative_title":["ISTA Thesis"]},{"day":"07","month":"06","article_processing_charge":"No","doi":"10.48550/arXiv.2102.05996","date_published":"2021-06-07T00:00:00Z","language":[{"iso":"eng"}],"publication":"arXiv","citation":{"chicago":"Konstantinov, Nikola H, and Christoph Lampert. “Fairness through Regularization for Learning to Rank.” ArXiv, n.d. https://doi.org/10.48550/arXiv.2102.05996.","mla":"Konstantinov, Nikola H., and Christoph Lampert. “Fairness through Regularization for Learning to Rank.” ArXiv, 2102.05996, doi:10.48550/arXiv.2102.05996.","short":"N.H. Konstantinov, C. Lampert, ArXiv (n.d.).","ista":"Konstantinov NH, Lampert C. Fairness through regularization for learning to rank. arXiv, 2102.05996.","ieee":"N. H. Konstantinov and C. Lampert, “Fairness through regularization for learning to rank,” arXiv. .","apa":"Konstantinov, N. H., & Lampert, C. (n.d.). Fairness through regularization for learning to rank. arXiv. https://doi.org/10.48550/arXiv.2102.05996","ama":"Konstantinov NH, Lampert C. Fairness through regularization for learning to rank. arXiv. doi:10.48550/arXiv.2102.05996"},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2102.05996"}],"oa":1,"external_id":{"arxiv":["2102.05996"]},"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","type":"preprint","author":[{"full_name":"Konstantinov, Nikola H","first_name":"Nikola H","last_name":"Konstantinov","id":"4B9D76E4-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Lampert","first_name":"Christoph","orcid":"0000-0002-4561-241X","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","full_name":"Lampert, Christoph"}],"related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"10799"}]},"date_created":"2022-02-28T14:13:59Z","date_updated":"2023-09-07T13:42:08Z","oa_version":"Preprint","_id":"10803","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2021","title":"Fairness through regularization for learning to rank","status":"public","publication_status":"submitted","department":[{"_id":"ChLa"}]},{"date_created":"2020-11-05T15:25:58Z","date_updated":"2023-09-07T13:42:08Z","volume":119,"author":[{"full_name":"Konstantinov, Nikola H","first_name":"Nikola H","last_name":"Konstantinov","id":"4B9D76E4-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Elias","last_name":"Frantar","id":"09a8f98d-ec99-11ea-ae11-c063a7b7fe5f","full_name":"Frantar, Elias"},{"last_name":"Alistarh","first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian"},{"id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8622-7887","first_name":"Christoph","last_name":"Lampert","full_name":"Lampert, Christoph"}],"related_material":{"record":[{"id":"10799","status":"public","relation":"dissertation_contains"}],"link":[{"relation":"supplementary_material","url":"http://proceedings.mlr.press/v119/konstantinov20a/konstantinov20a-supp.pdf"}]},"publication_status":"published","publisher":"ML Research Press","department":[{"_id":"DaAl"},{"_id":"ChLa"}],"year":"2020","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).","file_date_updated":"2021-02-15T09:00:01Z","ec_funded":1,"acknowledged_ssus":[{"_id":"ScienComp"}],"language":[{"iso":"eng"}],"conference":{"end_date":"2020-07-18","location":"Online","start_date":"2020-07-12","name":"ICML: International Conference on Machine Learning"},"quality_controlled":"1","project":[{"grant_number":"805223","_id":"268A44D6-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Elastic Coordination for Scalable Machine Learning"}],"external_id":{"arxiv":["2002.10384"]},"oa":1,"month":"07","publication_identifier":{"issn":["2640-3498"]},"file":[{"content_type":"application/pdf","file_size":281286,"creator":"dernst","file_name":"2020_PMLR_Konstantinov.pdf","access_level":"open_access","date_updated":"2021-02-15T09:00:01Z","date_created":"2021-02-15T09:00:01Z","checksum":"cc755d0054bc4b2be778ea7aa7884d2f","success":1,"relation":"main_file","file_id":"9120"}],"oa_version":"Published Version","status":"public","title":"On the sample complexity of adversarial multi-source PAC learning","ddc":["000"],"intvolume":" 119","_id":"8724","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","abstract":[{"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. ","lang":"eng"}],"type":"conference","date_published":"2020-07-12T00:00:00Z","page":"5416-5425","publication":"Proceedings of the 37th International Conference on Machine Learning","citation":{"chicago":"Konstantinov, Nikola H, Elias Frantar, Dan-Adrian Alistarh, and Christoph Lampert. “On the Sample Complexity of Adversarial Multi-Source PAC Learning.” In Proceedings of the 37th International Conference on Machine Learning, 119:5416–25. ML Research Press, 2020.","mla":"Konstantinov, Nikola H., et al. “On the Sample Complexity of Adversarial Multi-Source PAC Learning.” Proceedings of the 37th International Conference on Machine Learning, 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.","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.","ieee":"N. H. Konstantinov, E. Frantar, D.-A. Alistarh, and C. Lampert, “On the sample complexity of adversarial multi-source PAC learning,” in Proceedings of the 37th International Conference on Machine Learning, Online, 2020, vol. 119, pp. 5416–5425.","apa":"Konstantinov, N. H., Frantar, E., Alistarh, D.-A., & Lampert, C. (2020). On the sample complexity of adversarial multi-source PAC learning. In Proceedings of the 37th International Conference on Machine Learning (Vol. 119, pp. 5416–5425). Online: ML Research Press.","ama":"Konstantinov NH, Frantar E, Alistarh D-A, Lampert C. On the sample complexity of adversarial multi-source PAC learning. In: Proceedings of the 37th International Conference on Machine Learning. Vol 119. ML Research Press; 2020:5416-5425."},"day":"12","has_accepted_license":"1","article_processing_charge":"No","scopus_import":"1"},{"month":"06","conference":{"name":"ICML: International Conference on Machine Learning","end_date":"2919-06-15","start_date":"2019-06-10","location":"Long Beach, CA, USA"},"language":[{"iso":"eng"}],"oa":1,"external_id":{"arxiv":["1901.10310"]},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1901.10310"}],"quality_controlled":"1","project":[{"grant_number":"308036","_id":"2532554C-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Lifelong Learning of Visual Scene Understanding"},{"grant_number":"665385","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"International IST Doctoral Program"}],"ec_funded":1,"author":[{"last_name":"Konstantinov","first_name":"Nikola H","id":"4B9D76E4-F248-11E8-B48F-1D18A9856A87","full_name":"Konstantinov, Nikola H"},{"full_name":"Lampert, Christoph","first_name":"Christoph","last_name":"Lampert","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8622-7887"}],"related_material":{"record":[{"id":"10799","status":"public","relation":"dissertation_contains"}]},"date_created":"2019-06-27T14:18:23Z","date_updated":"2023-10-17T12:31:55Z","volume":97,"year":"2019","publication_status":"published","publisher":"ML Research Press","department":[{"_id":"ChLa"}],"day":"01","article_processing_charge":"No","scopus_import":"1","date_published":"2019-06-01T00:00:00Z","publication":"Proceedings of the 36th International Conference on Machine Learning","citation":{"chicago":"Konstantinov, Nikola H, and Christoph Lampert. “Robust Learning from Untrusted Sources.” In Proceedings of the 36th International Conference on Machine Learning, 97:3488–98. ML Research Press, 2019.","short":"N.H. Konstantinov, C. Lampert, in:, Proceedings of the 36th International Conference on Machine Learning, ML Research Press, 2019, pp. 3488–3498.","mla":"Konstantinov, Nikola H., and Christoph Lampert. “Robust Learning from Untrusted Sources.” Proceedings of the 36th International Conference on Machine Learning, vol. 97, ML Research Press, 2019, pp. 3488–98.","apa":"Konstantinov, N. H., & Lampert, C. (2019). Robust learning from untrusted sources. In Proceedings of the 36th International Conference on Machine Learning (Vol. 97, pp. 3488–3498). Long Beach, CA, USA: ML Research Press.","ieee":"N. H. Konstantinov and C. Lampert, “Robust learning from untrusted sources,” in Proceedings of the 36th International Conference on Machine Learning, 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.","ama":"Konstantinov NH, Lampert C. Robust learning from untrusted sources. In: Proceedings of the 36th International Conference on Machine Learning. Vol 97. ML Research Press; 2019:3488-3498."},"page":"3488-3498","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. "}],"type":"conference","oa_version":"Preprint","_id":"6590","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","title":"Robust learning from untrusted sources","intvolume":" 97"},{"article_processing_charge":"No","day":"23","scopus_import":"1","date_published":"2018-07-23T00:00:00Z","citation":{"apa":"Alistarh, D.-A., De Sa, C., & Konstantinov, N. H. (2018). The convergence of stochastic gradient descent in asynchronous shared memory. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing - PODC ’18 (pp. 169–178). Egham, United Kingdom: ACM Press. https://doi.org/10.1145/3212734.3212763","ieee":"D.-A. Alistarh, C. De Sa, and N. H. Konstantinov, “The convergence of stochastic gradient descent in asynchronous shared memory,” in Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing - PODC ’18, 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.","ama":"Alistarh D-A, De Sa C, Konstantinov NH. The convergence of stochastic gradient descent in asynchronous shared memory. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing - PODC ’18. ACM Press; 2018:169-178. doi:10.1145/3212734.3212763","chicago":"Alistarh, Dan-Adrian, Christopher De Sa, and Nikola H Konstantinov. “The Convergence of Stochastic Gradient Descent in Asynchronous Shared Memory.” In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing - PODC ’18, 169–78. ACM Press, 2018. https://doi.org/10.1145/3212734.3212763.","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 Press, 2018, pp. 169–178.","mla":"Alistarh, Dan-Adrian, et al. “The Convergence of Stochastic Gradient Descent in Asynchronous Shared Memory.” Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing - PODC ’18, ACM Press, 2018, pp. 169–78, doi:10.1145/3212734.3212763."},"publication":"Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing - PODC '18","page":"169-178","abstract":[{"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.","lang":"eng"}],"type":"conference","oa_version":"Preprint","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","_id":"5962","status":"public","title":"The convergence of stochastic gradient descent in asynchronous shared memory","publication_identifier":{"isbn":["9781450357951"]},"month":"07","doi":"10.1145/3212734.3212763","conference":{"name":"PODC: Principles of Distributed Computing","location":"Egham, United Kingdom","start_date":"2018-07-23","end_date":"2018-07-27"},"language":[{"iso":"eng"}],"oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1803.08841"}],"external_id":{"isi":["000458186900022"],"arxiv":["1803.08841"]},"isi":1,"quality_controlled":"1","author":[{"orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","last_name":"Alistarh","first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian"},{"full_name":"De Sa, Christopher","first_name":"Christopher","last_name":"De Sa"},{"first_name":"Nikola H","last_name":"Konstantinov","id":"4B9D76E4-F248-11E8-B48F-1D18A9856A87","full_name":"Konstantinov, Nikola H"}],"date_created":"2019-02-13T09:58:58Z","date_updated":"2023-09-19T10:42:53Z","year":"2018","publisher":"ACM Press","department":[{"_id":"DaAl"}],"publication_status":"published"},{"date_published":"2018-12-01T00:00:00Z","publication":"Advances in Neural Information Processing Systems 31","citation":{"mla":"Alistarh, Dan-Adrian, et al. “The Convergence of Sparsified Gradient Methods.” Advances in Neural Information Processing Systems 31, 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.","chicago":"Alistarh, Dan-Adrian, Torsten Hoefler, Mikael Johansson, Nikola H Konstantinov, Sarit Khirirat, and Cedric Renggli. “The Convergence of Sparsified Gradient Methods.” In Advances in Neural Information Processing Systems 31, Volume 2018:5973–83. Neural Information Processing Systems Foundation, 2018.","ama":"Alistarh D-A, Hoefler T, Johansson M, Konstantinov NH, Khirirat S, Renggli C. The convergence of sparsified gradient methods. In: Advances in Neural Information Processing Systems 31. Vol Volume 2018. Neural Information Processing Systems Foundation; 2018: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.","ieee":"D.-A. Alistarh, T. Hoefler, M. Johansson, N. H. Konstantinov, S. Khirirat, and C. Renggli, “The convergence of sparsified gradient methods,” in Advances in Neural Information Processing Systems 31, Montreal, Canada, 2018, vol. Volume 2018, pp. 5973–5983.","apa":"Alistarh, D.-A., Hoefler, T., Johansson, M., Konstantinov, N. H., Khirirat, S., & Renggli, C. (2018). The convergence of sparsified gradient methods. In Advances in Neural Information Processing Systems 31 (Vol. Volume 2018, pp. 5973–5983). Montreal, Canada: Neural Information Processing Systems Foundation."},"page":"5973-5983","day":"01","article_processing_charge":"No","scopus_import":"1","oa_version":"Preprint","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"6589","status":"public","title":"The convergence of sparsified gradient methods","abstract":[{"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.","lang":"eng"}],"type":"conference","conference":{"end_date":"2018-12-08","location":"Montreal, Canada","start_date":"2018-12-02","name":"NeurIPS: Conference on Neural Information Processing Systems"},"language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1809.10505"}],"oa":1,"external_id":{"arxiv":["1809.10505"],"isi":["000461852000047"]},"quality_controlled":"1","isi":1,"project":[{"_id":"2564DBCA-B435-11E9-9278-68D0E5697425","grant_number":"665385","name":"International IST Doctoral Program","call_identifier":"H2020"}],"month":"12","author":[{"first_name":"Dan-Adrian","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian"},{"full_name":"Hoefler, Torsten","last_name":"Hoefler","first_name":"Torsten"},{"last_name":"Johansson","first_name":"Mikael","full_name":"Johansson, Mikael"},{"full_name":"Konstantinov, Nikola H","first_name":"Nikola H","last_name":"Konstantinov","id":"4B9D76E4-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Sarit","last_name":"Khirirat","full_name":"Khirirat, Sarit"},{"first_name":"Cedric","last_name":"Renggli","full_name":"Renggli, Cedric"}],"date_updated":"2023-10-17T11:47:20Z","date_created":"2019-06-27T09:32:55Z","volume":"Volume 2018","year":"2018","publication_status":"published","department":[{"_id":"DaAl"},{"_id":"ChLa"}],"publisher":"Neural Information Processing Systems Foundation","ec_funded":1}]