[{"title":"Input-dynamic distributed algorithms for communication networks","status":"public","_id":"10855","oa":1,"date_created":"2022-03-18T09:10:27Z","abstract":[{"text":"Consider a distributed task where the communication network is fixed but the local inputs given to the nodes of the distributed system may change over time. In this work, we explore the following question: if some of the local inputs change, can an existing solution be updated efficiently, in a dynamic and distributed manner? To address this question, we define the batch dynamic \\congest model in which we are given a bandwidth-limited communication network and a dynamic edge labelling defines the problem input. The task is to maintain a solution to a graph problem on the labeled graph under batch changes. We investigate, when a batch of α edge label changes arrive, \\beginitemize \\item how much time as a function of α we need to update an existing solution, and \\item how much information the nodes have to keep in local memory between batches in order to update the solution quickly. \\enditemize Our work lays the foundations for the theory of input-dynamic distributed network algorithms. We give a general picture of the complexity landscape in this model, design both universal algorithms and algorithms for concrete problems, and present a general framework for lower bounds. In particular, we derive non-trivial upper bounds for two selected, contrasting problems: maintaining a minimum spanning tree and detecting cliques.","lang":"eng"}],"project":[{"_id":"26A5D39A-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"840605","name":"Coordination in constrained and natural distributed systems"},{"_id":"268A44D6-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"805223","name":"Elastic Coordination for Scalable Machine Learning"}],"year":"2021","page":"1-33","publication_status":"published","oa_version":"Preprint","scopus_import":"1","date_updated":"2025-04-14T13:52:09Z","publication_identifier":{"issn":["2476-1249"]},"month":"03","quality_controlled":"1","article_type":"original","external_id":{"arxiv":["2005.07637"]},"type":"journal_article","volume":5,"doi":"10.1145/3447384","citation":{"ista":"Foerster K-T, Korhonen J, Paz A, Rybicki J, Schmid S. 2021. Input-dynamic distributed algorithms for communication networks. Proceedings of the ACM on Measurement and Analysis of Computing Systems. 5(1), 1–33.","ieee":"K.-T. Foerster, J. Korhonen, A. Paz, J. Rybicki, and S. Schmid, “Input-dynamic distributed algorithms for communication networks,” <i>Proceedings of the ACM on Measurement and Analysis of Computing Systems</i>, vol. 5, no. 1. Association for Computing Machinery, pp. 1–33, 2021.","chicago":"Foerster, Klaus-Tycho, Janne Korhonen, Ami Paz, Joel Rybicki, and Stefan Schmid. “Input-Dynamic Distributed Algorithms for Communication Networks.” <i>Proceedings of the ACM on Measurement and Analysis of Computing Systems</i>. Association for Computing Machinery, 2021. <a href=\"https://doi.org/10.1145/3447384\">https://doi.org/10.1145/3447384</a>.","ama":"Foerster K-T, Korhonen J, Paz A, Rybicki J, Schmid S. Input-dynamic distributed algorithms for communication networks. <i>Proceedings of the ACM on Measurement and Analysis of Computing Systems</i>. 2021;5(1):1-33. doi:<a href=\"https://doi.org/10.1145/3447384\">10.1145/3447384</a>","short":"K.-T. Foerster, J. Korhonen, A. Paz, J. Rybicki, S. Schmid, Proceedings of the ACM on Measurement and Analysis of Computing Systems 5 (2021) 1–33.","apa":"Foerster, K.-T., Korhonen, J., Paz, A., Rybicki, J., &#38; Schmid, S. (2021). Input-dynamic distributed algorithms for communication networks. <i>Proceedings of the ACM on Measurement and Analysis of Computing Systems</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3447384\">https://doi.org/10.1145/3447384</a>","mla":"Foerster, Klaus-Tycho, et al. “Input-Dynamic Distributed Algorithms for Communication Networks.” <i>Proceedings of the ACM on Measurement and Analysis of Computing Systems</i>, vol. 5, no. 1, Association for Computing Machinery, 2021, pp. 1–33, doi:<a href=\"https://doi.org/10.1145/3447384\">10.1145/3447384</a>."},"publisher":"Association for Computing Machinery","intvolume":"         5","issue":"1","article_processing_charge":"No","main_file_link":[{"url":"https://arxiv.org/abs/2005.07637","open_access":"1"}],"day":"01","date_published":"2021-03-01T00:00:00Z","ec_funded":1,"author":[{"last_name":"Foerster","first_name":"Klaus-Tycho","full_name":"Foerster, Klaus-Tycho"},{"full_name":"Korhonen, Janne","last_name":"Korhonen","first_name":"Janne","id":"C5402D42-15BC-11E9-A202-CA2BE6697425"},{"first_name":"Ami","last_name":"Paz","full_name":"Paz, Ami"},{"full_name":"Rybicki, Joel","last_name":"Rybicki","first_name":"Joel","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6432-6646"},{"last_name":"Schmid","first_name":"Stefan","full_name":"Schmid, Stefan"}],"department":[{"_id":"DaAl"}],"related_material":{"record":[{"id":"10854","status":"public","relation":"shorter_version"}]},"acknowledgement":"We thank Jukka Suomela for discussions. We also thank our shepherd Mohammad Hajiesmaili\r\nand the reviewers for their time and suggestions on how to improve the paper. This project\r\nhas received funding from the European Research Council (ERC) under the European Union’s\r\nHorizon 2020 research and innovation programme (grant agreement No 805223 ScaleML), from the European Union’s Horizon 2020 research and innovation programme under the Marie\r\nSk lodowska–Curie grant agreement No. 840605, from the Vienna Science and Technology Fund (WWTF) project WHATIF, ICT19-045, 2020-2024, and from the Austrian Science Fund (FWF) and netIDEE SCIENCE project P 33775-N.","arxiv":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"Proceedings of the ACM on Measurement and Analysis of Computing Systems","language":[{"iso":"eng"}],"keyword":["Computer Networks and Communications","Hardware and Architecture","Safety","Risk","Reliability and Quality","Computer Science (miscellaneous)"]},{"external_id":{"arxiv":["2106.12379"]},"type":"conference","volume":34,"publication_identifier":{"isbn":["9781713845393"],"issn":["1049-5258"]},"alternative_title":["Advances in Neural Information Processing Systems"],"month":"12","quality_controlled":"1","acknowledged_ssus":[{"_id":"ScienComp"}],"ec_funded":1,"author":[{"full_name":"Peste, Elena-Alexandra","first_name":"Elena-Alexandra","last_name":"Peste","id":"32D78294-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0002-7778-3221","id":"f9a17499-f6e0-11ea-865d-fdf9a3f77117","first_name":"Eugenia B","last_name":"Iofinova","full_name":"Iofinova, Eugenia B"},{"full_name":"Vladu, Adrian","last_name":"Vladu","first_name":"Adrian"},{"first_name":"Dan-Adrian","last_name":"Alistarh","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"}],"department":[{"_id":"GradSch"},{"_id":"DaAl"}],"related_material":{"record":[{"id":"13074","status":"public","relation":"dissertation_contains"}]},"acknowledgement":"This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML), and a CNRS PEPS grant. This research was supported by the Scientific Service Units (SSU) of IST Austria through resources provided by Scientific Computing (SciComp). We would also like to thank Christoph Lampert for his feedback on an earlier version of this work, as well as for providing hardware for the Transformer-XL experiments.","arxiv":1,"ddc":["000"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"35th Conference on Neural Information Processing Systems","language":[{"iso":"eng"}],"citation":{"apa":"Krumes, A., Iofinova, E. B., Vladu, A., &#38; Alistarh, D.-A. (2021). AC/DC: Alternating Compressed/DeCompressed training of deep neural networks. In <i>35th Conference on Neural Information Processing Systems</i> (Vol. 34, pp. 8557–8570). Virtual, Online: Neural Information Processing Systems Foundation.","mla":"Krumes, Alexandra, et al. “AC/DC: Alternating Compressed/DeCompressed Training of Deep Neural Networks.” <i>35th Conference on Neural Information Processing Systems</i>, vol. 34, Neural Information Processing Systems Foundation, 2021, pp. 8557–70.","short":"A. Krumes, E.B. Iofinova, A. Vladu, D.-A. Alistarh, in:, 35th Conference on Neural Information Processing Systems, Neural Information Processing Systems Foundation, 2021, pp. 8557–8570.","ista":"Krumes A, Iofinova EB, Vladu A, Alistarh D-A. 2021. AC/DC: Alternating Compressed/DeCompressed training of deep neural networks. 35th Conference on Neural Information Processing Systems. NeurIPS: Neural Information Processing Systems, Advances in Neural Information Processing Systems, vol. 34, 8557–8570.","ieee":"A. Krumes, E. B. Iofinova, A. Vladu, and D.-A. Alistarh, “AC/DC: Alternating Compressed/DeCompressed training of deep neural networks,” in <i>35th Conference on Neural Information Processing Systems</i>, Virtual, Online, 2021, vol. 34, pp. 8557–8570.","chicago":"Krumes, Alexandra, Eugenia B Iofinova, Adrian Vladu, and Dan-Adrian Alistarh. “AC/DC: Alternating Compressed/DeCompressed Training of Deep Neural Networks.” In <i>35th Conference on Neural Information Processing Systems</i>, 34:8557–70. Neural Information Processing Systems Foundation, 2021.","ama":"Krumes A, Iofinova EB, Vladu A, Alistarh D-A. AC/DC: Alternating Compressed/DeCompressed training of deep neural networks. In: <i>35th Conference on Neural Information Processing Systems</i>. Vol 34. Neural Information Processing Systems Foundation; 2021:8557-8570."},"publisher":"Neural Information Processing Systems Foundation","intvolume":"        34","article_processing_charge":"No","day":"06","main_file_link":[{"open_access":"1","url":"https://proceedings.neurips.cc/paper/2021/file/48000647b315f6f00f913caa757a70b3-Paper.pdf"}],"date_published":"2021-12-06T00:00:00Z","corr_author":"1","title":"AC/DC: Alternating Compressed/DeCompressed training of deep neural networks","status":"public","_id":"11458","date_created":"2022-06-20T12:11:53Z","oa":1,"abstract":[{"lang":"eng","text":"The increasing computational requirements of deep neural networks (DNNs) have led to significant interest in obtaining DNN models that are sparse, yet accurate. Recent work has investigated the even harder case of sparse training, where the DNN weights are, for as much as possible, already sparse to reduce computational costs during training. Existing sparse training methods are often empirical and can have lower accuracy relative to the dense baseline. In this paper, we present a general approach called Alternating Compressed/DeCompressed (AC/DC) training of DNNs, demonstrate convergence for a variant of the algorithm, and show that AC/DC outperforms existing sparse training methods in accuracy at similar computational budgets; at high sparsity levels, AC/DC even outperforms existing methods that rely on accurate pre-trained dense models. An important property of AC/DC is that it allows co-training of dense and sparse models, yielding accurate sparse–dense model pairs at the end of the training process. This is useful in practice, where compressed variants may be desirable for deployment in resource-constrained settings without re-doing the entire training flow, and also provides us with insights into the accuracy gap between dense and compressed models. The code is available at: https://github.com/IST-DASLab/ACDC."}],"scopus_import":"1","oa_version":"Published Version","date_updated":"2026-06-18T17:18:20Z","conference":{"start_date":"2021-12-06","location":"Virtual, Online","end_date":"2021-12-14","name":"NeurIPS: Neural Information Processing Systems"},"project":[{"name":"Elastic Coordination for Scalable Machine Learning","grant_number":"805223","call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425"}],"year":"2021","publication_status":"published","page":"8557-8570"},{"main_file_link":[{"url":"https://proceedings.neurips.cc/paper/2021/file/7cfd5df443b4eb0d69886a583b33de4c-Paper.pdf","open_access":"1"}],"day":"06","date_published":"2021-12-06T00:00:00Z","article_processing_charge":"No","intvolume":"        34","publisher":"Neural Information Processing Systems Foundation","citation":{"short":"E. Frantar, E. Kurtic, D.-A. Alistarh, in:, 35th Conference on Neural Information Processing Systems, Neural Information Processing Systems Foundation, 2021, pp. 14873–14886.","ista":"Frantar E, Kurtic E, Alistarh D-A. 2021. M-FAC: Efficient matrix-free approximations of second-order information. 35th Conference on Neural Information Processing Systems. NeurIPS: Neural Information Processing Systems, Advances in Neural Information Processing Systems, vol. 34, 14873–14886.","ieee":"E. Frantar, E. Kurtic, and D.-A. Alistarh, “M-FAC: Efficient matrix-free approximations of second-order information,” in <i>35th Conference on Neural Information Processing Systems</i>, Virtual, Online, 2021, vol. 34, pp. 14873–14886.","chicago":"Frantar, Elias, Eldar Kurtic, and Dan-Adrian Alistarh. “M-FAC: Efficient Matrix-Free Approximations of Second-Order Information.” In <i>35th Conference on Neural Information Processing Systems</i>, 34:14873–86. Neural Information Processing Systems Foundation, 2021.","ama":"Frantar E, Kurtic E, Alistarh D-A. M-FAC: Efficient matrix-free approximations of second-order information. In: <i>35th Conference on Neural Information Processing Systems</i>. Vol 34. Neural Information Processing Systems Foundation; 2021:14873-14886.","apa":"Frantar, E., Kurtic, E., &#38; Alistarh, D.-A. (2021). M-FAC: Efficient matrix-free approximations of second-order information. In <i>35th Conference on Neural Information Processing Systems</i> (Vol. 34, pp. 14873–14886). Virtual, Online: Neural Information Processing Systems Foundation.","mla":"Frantar, Elias, et al. “M-FAC: Efficient Matrix-Free Approximations of Second-Order Information.” <i>35th Conference on Neural Information Processing Systems</i>, vol. 34, Neural Information Processing Systems Foundation, 2021, pp. 14873–86."},"publication":"35th Conference on Neural Information Processing Systems","language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000"],"arxiv":1,"acknowledgement":"We gratefully acknowledge funding the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML), as well as computational support from Amazon Web Services (AWS) EC2.","department":[{"_id":"DaAl"}],"author":[{"first_name":"Elias","last_name":"Frantar","full_name":"Frantar, Elias","id":"09a8f98d-ec99-11ea-ae11-c063a7b7fe5f"},{"id":"47beb3a5-07b5-11eb-9b87-b108ec578218","first_name":"Eldar","last_name":"Kurtic","full_name":"Kurtic, Eldar"},{"last_name":"Alistarh","first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"}],"ec_funded":1,"quality_controlled":"1","month":"12","alternative_title":["Advances in Neural Information Processing Systems"],"publication_identifier":{"issn":["1049-5258"],"isbn":["9781713845393"]},"volume":34,"type":"conference","external_id":{"arxiv":["2010.08222"]},"page":"14873-14886","publication_status":"published","year":"2021","project":[{"call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425","name":"Elastic Coordination for Scalable Machine Learning","grant_number":"805223"}],"conference":{"start_date":"2021-12-06","location":"Virtual, Online","end_date":"2021-12-14","name":"NeurIPS: Neural Information Processing Systems"},"date_updated":"2026-06-18T17:18:44Z","oa_version":"Published Version","scopus_import":"1","abstract":[{"lang":"eng","text":"Efficiently approximating local curvature information of the loss function is a key tool for optimization and compression of deep neural networks. Yet, most existing methods to approximate second-order information have high computational\r\nor storage costs, which limits their practicality. In this work, we investigate matrix-free, linear-time approaches for estimating Inverse-Hessian Vector Products (IHVPs) for the case when the Hessian can be approximated as a sum of rank-one matrices, as in the classic approximation of the Hessian by the empirical Fisher matrix. We propose two new algorithms: the first is tailored towards network compression and can compute the IHVP for dimension d, if the Hessian is given as a sum of m rank-one matrices, using O(dm2) precomputation, O(dm) cost for computing the IHVP, and query cost O(m) for any single element of the inverse Hessian. The second algorithm targets an optimization setting, where we wish to compute the product between the inverse Hessian, estimated over a sliding window of optimization steps, and a given gradient direction, as required for preconditioned SGD. We give an algorithm with cost O(dm + m2) for computing the IHVP and O(dm + m3) for adding or removing any gradient from the sliding window. These\r\ntwo algorithms yield state-of-the-art results for network pruning and optimization with lower computational overhead relative to existing second-order methods. Implementations are available at [9] and [17]."}],"oa":1,"date_created":"2022-06-26T22:01:35Z","status":"public","_id":"11463","title":"M-FAC: Efficient matrix-free approximations of second-order information","corr_author":"1"},{"ec_funded":1,"author":[{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","first_name":"Dan-Adrian"},{"id":"C5402D42-15BC-11E9-A202-CA2BE6697425","full_name":"Korhonen, Janne","last_name":"Korhonen","first_name":"Janne"}],"department":[{"_id":"DaAl"}],"acknowledgement":"We thank the NeurIPS reviewers for insightful comments that helped us improve the positioning of our results, as well as for pointing out the subsampling approach for complementing the randomised lower bound. We also thank Foivos Alimisis and Peter Davies for useful discussions. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML).","arxiv":1,"publication":"35th Conference on Neural Information Processing Systems","ddc":["000"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"citation":{"mla":"Alistarh, Dan-Adrian, and Janne Korhonen. “Towards Tight Communication Lower Bounds for Distributed Optimisation.” <i>35th Conference on Neural Information Processing Systems</i>, vol. 34, Neural Information Processing Systems Foundation, 2021, pp. 7254–66.","apa":"Alistarh, D.-A., &#38; Korhonen, J. (2021). Towards tight communication lower bounds for distributed optimisation. In <i>35th Conference on Neural Information Processing Systems</i> (Vol. 34, pp. 7254–7266). Virtual, Online: Neural Information Processing Systems Foundation.","short":"D.-A. Alistarh, J. Korhonen, in:, 35th Conference on Neural Information Processing Systems, Neural Information Processing Systems Foundation, 2021, pp. 7254–7266.","ama":"Alistarh D-A, Korhonen J. Towards tight communication lower bounds for distributed optimisation. In: <i>35th Conference on Neural Information Processing Systems</i>. Vol 34. Neural Information Processing Systems Foundation; 2021:7254-7266.","chicago":"Alistarh, Dan-Adrian, and Janne Korhonen. “Towards Tight Communication Lower Bounds for Distributed Optimisation.” In <i>35th Conference on Neural Information Processing Systems</i>, 34:7254–66. Neural Information Processing Systems Foundation, 2021.","ista":"Alistarh D-A, Korhonen J. 2021. Towards tight communication lower bounds for distributed optimisation. 35th Conference on Neural Information Processing Systems. NeurIPS: Neural Information Processing Systems, Advances in Neural Information Processing Systems, vol. 34, 7254–7266.","ieee":"D.-A. Alistarh and J. Korhonen, “Towards tight communication lower bounds for distributed optimisation,” in <i>35th Conference on Neural Information Processing Systems</i>, Virtual, Online, 2021, vol. 34, pp. 7254–7266."},"publisher":"Neural Information Processing Systems Foundation","intvolume":"        34","article_processing_charge":"No","date_published":"2021-12-06T00:00:00Z","main_file_link":[{"url":"https://proceedings.neurips.cc/paper/2021/file/3b92d18aa7a6176dd37d372bc2f1eb71-Paper.pdf","open_access":"1"}],"day":"06","external_id":{"arxiv":["2010.08222"]},"type":"conference","volume":34,"alternative_title":["Advances in Neural Information Processing Systems"],"publication_identifier":{"isbn":["9781713845393"],"issn":["1049-5258"]},"month":"12","quality_controlled":"1","scopus_import":"1","oa_version":"Published Version","date_updated":"2026-06-18T17:19:18Z","conference":{"start_date":"2021-12-06","location":"Virtual, Online","name":"NeurIPS: Neural Information Processing Systems","end_date":"2021-12-14"},"project":[{"call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425","grant_number":"805223","name":"Elastic Coordination for Scalable Machine Learning"}],"year":"2021","publication_status":"published","page":"7254-7266","corr_author":"1","title":"Towards tight communication lower bounds for distributed optimisation","_id":"11464","status":"public","oa":1,"date_created":"2022-06-26T22:01:35Z","abstract":[{"text":"We consider a standard distributed optimisation setting where N machines, each holding a d-dimensional function\r\nfi, aim to jointly minimise the sum of the functions ∑Ni=1fi(x). This problem arises naturally in large-scale distributed optimisation, where a standard solution is to apply variants of (stochastic) gradient descent. We focus on the communication complexity of this problem: our main result provides the first fully unconditional bounds on total number of bits which need to be sent and received by the N machines to solve this problem under point-to-point communication, within a given error-tolerance. Specifically, we show that Ω(Ndlogd/Nε) total bits need to be communicated between the machines to find an additive ϵ-approximation to the minimum of ∑Ni=1fi(x). The result holds for both deterministic and randomised algorithms, and, importantly, requires no assumptions on the algorithm structure. The lower bound is tight under certain restrictions on parameter values, and is matched within constant factors for quadratic objectives by a new variant of quantised gradient descent, which we describe and analyse. Our results bring over tools from communication complexity to distributed optimisation, which has potential for further applications.","lang":"eng"}]},{"volume":139,"has_accepted_license":"1","external_id":{"arxiv":["2102.07214"]},"type":"conference","month":"07","quality_controlled":"1","publication_identifier":{"eissn":["2640-3498"],"isbn":["9781713845065"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"arxiv":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000"],"language":[{"iso":"eng"}],"publication":"Proceedings of the 38th International Conference on Machine Learning","department":[{"_id":"DaAl"}],"acknowledgement":"The authors would like to thank Janne Korhonen, Aurelien Lucchi, Celestine MendlerDunner and Antonio Orvieto for helpful discussions. FA ¨and DA were supported during this work by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML). PD was supported by the European Union’s Horizon 2020 programme under the Marie Skłodowska-Curie grant agreement No. 754411.","author":[{"full_name":"Alimisis, Foivos","first_name":"Foivos","last_name":"Alimisis"},{"orcid":"0000-0002-5646-9524","id":"11396234-BB50-11E9-B24C-90FCE5697425","first_name":"Peter","last_name":"Davies","full_name":"Davies, Peter"},{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","first_name":"Dan-Adrian"}],"ec_funded":1,"article_processing_charge":"No","date_published":"2021-07-01T00:00:00Z","day":"01","file_date_updated":"2023-06-19T10:41:05Z","intvolume":"       139","citation":{"mla":"Alimisis, Foivos, et al. “Communication-Efficient Distributed Optimization with Quantized Preconditioners.” <i>Proceedings of the 38th International Conference on Machine Learning</i>, vol. 139, ML Research Press, 2021, pp. 196–206.","apa":"Alimisis, F., Davies, P., &#38; Alistarh, D.-A. (2021). Communication-efficient distributed optimization with quantized preconditioners. In <i>Proceedings of the 38th International Conference on Machine Learning</i> (Vol. 139, pp. 196–206). Virtual: ML Research Press.","short":"F. Alimisis, P. Davies, D.-A. Alistarh, in:, Proceedings of the 38th International Conference on Machine Learning, ML Research Press, 2021, pp. 196–206.","ama":"Alimisis F, Davies P, Alistarh D-A. Communication-efficient distributed optimization with quantized preconditioners. In: <i>Proceedings of the 38th International Conference on Machine Learning</i>. Vol 139. ML Research Press; 2021:196-206.","ista":"Alimisis F, Davies P, Alistarh D-A. 2021. Communication-efficient distributed optimization with quantized preconditioners. Proceedings of the 38th International Conference on Machine Learning. ICML: International Conference on Machine Learning vol. 139, 196–206.","chicago":"Alimisis, Foivos, Peter Davies, and Dan-Adrian Alistarh. “Communication-Efficient Distributed Optimization with Quantized Preconditioners.” In <i>Proceedings of the 38th International Conference on Machine Learning</i>, 139:196–206. ML Research Press, 2021.","ieee":"F. Alimisis, P. Davies, and D.-A. Alistarh, “Communication-efficient distributed optimization with quantized preconditioners,” in <i>Proceedings of the 38th International Conference on Machine Learning</i>, Virtual, 2021, vol. 139, pp. 196–206."},"publisher":"ML Research Press","file":[{"file_id":"13154","file_name":"2021_PMLR_Alimisis.pdf","creator":"dernst","date_created":"2023-06-19T10:41:05Z","relation":"main_file","checksum":"7ec0d59bac268b49c76bf2e036dedd7a","success":1,"date_updated":"2023-06-19T10:41:05Z","content_type":"application/pdf","file_size":429087,"access_level":"open_access"}],"corr_author":"1","oa":1,"date_created":"2023-06-18T22:00:48Z","abstract":[{"lang":"eng","text":"We investigate fast and communication-efficient algorithms for the classic problem of minimizing a sum of strongly convex and smooth functions that are distributed among n\r\n different nodes, which can communicate using a limited number of bits. Most previous communication-efficient approaches for this problem are limited to first-order optimization, and therefore have \\emph{linear} dependence on the condition number in their communication complexity. We show that this dependence is not inherent: communication-efficient methods can in fact have sublinear dependence on the condition number. For this, we design and analyze the first communication-efficient distributed variants of preconditioned gradient descent for Generalized Linear Models, and for Newton’s method. Our results rely on a new technique for quantizing both the preconditioner and the descent direction at each step of the algorithms, while controlling their convergence rate. We also validate our findings experimentally, showing faster convergence and reduced communication relative to previous methods."}],"status":"public","_id":"13147","title":"Communication-efficient distributed optimization with quantized preconditioners","conference":{"end_date":"2021-07-24","name":"ICML: International Conference on Machine Learning","start_date":"2021-07-18","location":"Virtual"},"date_updated":"2025-07-10T11:50:37Z","oa_version":"Published Version","scopus_import":"1","page":"196-206","publication_status":"published","year":"2021","project":[{"name":"Elastic Coordination for Scalable Machine Learning","grant_number":"805223","_id":"268A44D6-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"},{"call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411"}]},{"abstract":[{"text":"We develop a new Riemannian descent algorithm that relies on momentum to improve over existing first-order methods for geodesically convex optimization. In contrast, accelerated convergence rates proved in prior work have only been shown to hold for geodesically strongly-convex objective functions. We further extend our algorithm to geodesically weakly-quasi-convex objectives. Our proofs of convergence rely on a novel estimate sequence that illustrates the dependency of the convergence rate on the curvature of the manifold. We validate our theoretical results empirically on several optimization problems defined on the sphere and on the manifold of positive definite matrices.","lang":"eng"}],"oa":1,"date_created":"2024-04-03T07:29:49Z","status":"public","_id":"15263","title":"Momentum improves optimization on Riemannian manifolds","conference":{"start_date":"2021-04-13","location":"San Diego, CA, United States; Virtual","name":"AISTATS: Conference on Artificial Intelligence and Statistics","end_date":"2021-04-15"},"date_updated":"2026-06-18T17:47:19Z","oa_version":"Published Version","publication_status":"published","page":"1351-1359","year":"2021","volume":130,"type":"conference","external_id":{"arxiv":["2002.04144"]},"quality_controlled":"1","month":"04","alternative_title":["PMLR"],"publication":"Proceedings of the 24th International Conference on Artificial Intelligence and Statistics","language":[{"iso":"eng"}],"ddc":["000"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","arxiv":1,"acknowledgement":"The authors would like to thank professors Nicolas Boumal and Suvrit Sra for helpful discussions on the content of this paper. Gary Bécigneul was funded by the Max Planck ETH Center for Learning Systems during the course of this work.","department":[{"_id":"DaAl"}],"author":[{"id":"19430a34-05f6-11ef-890d-c079cfc60ae2","first_name":"Foivos","last_name":"Alimisis","full_name":"Alimisis, Foivos"},{"first_name":"Antonio","last_name":"Orvieto","full_name":"Orvieto, Antonio"},{"last_name":"Becigneul","first_name":"Gary","full_name":"Becigneul, Gary"},{"last_name":"Lucchi","first_name":"Aurelien","full_name":"Lucchi, Aurelien"}],"main_file_link":[{"url":"https://proceedings.mlr.press/v130/alimisis21a.html","open_access":"1"}],"day":"15","date_published":"2021-04-15T00:00:00Z","article_processing_charge":"No","intvolume":"       130","publisher":"ML Research Press","citation":{"mla":"Alimisis, Foivos, et al. “Momentum Improves Optimization on Riemannian Manifolds.” <i>Proceedings of the 24th International Conference on Artificial Intelligence and Statistics</i>, vol. 130, ML Research Press, 2021, pp. 1351–59.","apa":"Alimisis, F., Orvieto, A., Becigneul, G., &#38; Lucchi, A. (2021). Momentum improves optimization on Riemannian manifolds. In <i>Proceedings of the 24th International Conference on Artificial Intelligence and Statistics</i> (Vol. 130, pp. 1351–1359). San Diego, CA, United States; Virtual: ML Research Press.","ama":"Alimisis F, Orvieto A, Becigneul G, Lucchi A. Momentum improves optimization on Riemannian manifolds. In: <i>Proceedings of the 24th International Conference on Artificial Intelligence and Statistics</i>. Vol 130. ML Research Press; 2021:1351-1359.","ista":"Alimisis F, Orvieto A, Becigneul G, Lucchi A. 2021. Momentum improves optimization on Riemannian manifolds. Proceedings of the 24th International Conference on Artificial Intelligence and Statistics. AISTATS: Conference on Artificial Intelligence and Statistics, PMLR, vol. 130, 1351–1359.","ieee":"F. Alimisis, A. Orvieto, G. Becigneul, and A. Lucchi, “Momentum improves optimization on Riemannian manifolds,” in <i>Proceedings of the 24th International Conference on Artificial Intelligence and Statistics</i>, San Diego, CA, United States; Virtual, 2021, vol. 130, pp. 1351–1359.","chicago":"Alimisis, Foivos, Antonio Orvieto, Gary Becigneul, and Aurelien Lucchi. “Momentum Improves Optimization on Riemannian Manifolds.” In <i>Proceedings of the 24th International Conference on Artificial Intelligence and Statistics</i>, 130:1351–59. ML Research Press, 2021.","short":"F. Alimisis, A. Orvieto, G. Becigneul, A. Lucchi, in:, Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, ML Research Press, 2021, pp. 1351–1359."}},{"citation":{"apa":"Czumaj, A., Davies, P., &#38; Parter, M. (2021). Simple, deterministic, constant-round coloring in congested clique and MPC. <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/20m1366502\">https://doi.org/10.1137/20m1366502</a>","mla":"Czumaj, Artur, et al. “Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC.” <i>SIAM Journal on Computing</i>, vol. 50, no. 5, Society for Industrial and Applied Mathematics, 2021, pp. 1603–26, doi:<a href=\"https://doi.org/10.1137/20m1366502\">10.1137/20m1366502</a>.","ieee":"A. Czumaj, P. Davies, and M. Parter, “Simple, deterministic, constant-round coloring in congested clique and MPC,” <i>SIAM Journal on Computing</i>, vol. 50, no. 5. Society for Industrial and Applied Mathematics, pp. 1603–1626, 2021.","ista":"Czumaj A, Davies P, Parter M. 2021. Simple, deterministic, constant-round coloring in congested clique and MPC. SIAM Journal on Computing. 50(5), 1603–1626.","chicago":"Czumaj, Artur, Peter Davies, and Merav Parter. “Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC.” <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics, 2021. <a href=\"https://doi.org/10.1137/20m1366502\">https://doi.org/10.1137/20m1366502</a>.","ama":"Czumaj A, Davies P, Parter M. Simple, deterministic, constant-round coloring in congested clique and MPC. <i>SIAM Journal on Computing</i>. 2021;50(5):1603-1626. doi:<a href=\"https://doi.org/10.1137/20m1366502\">10.1137/20m1366502</a>","short":"A. Czumaj, P. Davies, M. Parter, SIAM Journal on Computing 50 (2021) 1603–1626."},"publisher":"Society for Industrial and Applied Mathematics","intvolume":"        50","issue":"5","article_processing_charge":"No","date_published":"2021-01-01T00:00:00Z","day":"01","ec_funded":1,"author":[{"full_name":"Czumaj, Artur","last_name":"Czumaj","first_name":"Artur"},{"id":"11396234-BB50-11E9-B24C-90FCE5697425","orcid":"0000-0002-5646-9524","full_name":"Davies, Peter","first_name":"Peter","last_name":"Davies"},{"full_name":"Parter, Merav","first_name":"Merav","last_name":"Parter"}],"department":[{"_id":"DaAl"}],"acknowledgement":"The  first  author  was  partially  supported  by  the  Centre  for  Discrete  Mathematics and its Applications, by the IBM Faculty Award, and by the EPSRC award EP/N011163/1.  The second author was partially supported by the European Union’s Horizon 2020 research and innovation program under the Marie Sklodowska-Curie grant agreement 754411.  The first and third authors were partially supported by a Weizmann-UK Making Connections grant.","language":[{"iso":"eng"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","publication":"SIAM Journal on Computing","keyword":["General Mathematics","General Computer Science"],"publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"month":"01","quality_controlled":"1","article_type":"original","external_id":{"isi":["000713008600004"]},"type":"journal_article","volume":50,"doi":"10.1137/20m1366502","project":[{"name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"year":"2021","publication_status":"published","page":"1603-1626","scopus_import":"1","oa_version":"None","date_updated":"2025-09-10T10:14:11Z","title":"Simple, deterministic, constant-round coloring in congested clique and MPC","status":"public","_id":"15271","date_created":"2024-04-03T07:53:22Z","abstract":[{"text":"We settle the complexity of the (∆ + 1)-coloring and (∆ + 1)-list coloring problems intheCONGESTED CLIQUEmodel by presenting a simpledeterministicalgorithm for both problemsrunning in a constant number of rounds.  This matches the complexity of the recent breakthroughrandomizedconstant-round (∆ + 1)-list coloring algorithm due to Chang et al.  [Proceedings of the38th  ACM  Symposium  on  Principles  of  Distributed  Computing,  2019]  and  significantly  improvesupon the state-of-the-artO(log ∆)-round deterministic (∆ + 1)-coloring bound of Parter [Proceed-ings of the 45th Annual International Colloquium on Automata, Languages and Programming].  Aremarkable property of our algorithm is its simplicity.  Whereas the state-of-the-artrandomizedal-gorithms for this problem are based on the quite involved local coloring algorithm of Chang, Li, andPettie [Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018],our algorithm can be described in just a few lines.  At a high level, it applies a careful derandomiza-tion of a recursive procedure which partitions the nodes and their respective palettes into separatebins.  We show that afterO(1) recursion steps, the remaining uncolored subgraph within each bin haslinear size and thus can be solved locally by collecting it to a single node.  This algorithm can alsobe implemented in the massively parallel computation (MPC) model provided that each machine haslinear (inn, the number of nodes in the input graph) space.  We also show an extension of our algo-rithm to theMPCregime, in which machines havesublinearspace:  we present the first deterministic(∆ + 1)-list coloring algorithm designed for sublinear-spaceMPC, which runs inO(log ∆ + log logn)rounds.","lang":"eng"}],"isi":1},{"abstract":[{"text":"While messaging systems with strong security guarantees are widely used in practice, designing a protocol that scales efficiently to large groups and enjoys similar security guarantees remains largely open. The two existing proposals to date are ART (Cohn-Gordon et al., CCS18) and TreeKEM (IETF, The Messaging Layer Security Protocol, draft). TreeKEM is the currently considered candidate by the IETF MLS working group, but dynamic group operations (i.e. adding and removing users) can cause efficiency issues. In this paper we formalize and analyze a variant of TreeKEM which we term Tainted TreeKEM (TTKEM for short). The basic idea underlying TTKEM was suggested by Millican (MLS mailing list, February 2018). This version is more efficient than TreeKEM for some natural distributions of group operations, we quantify this through simulations.Our second contribution is two security proofs for TTKEM which establish post compromise and forward secrecy even against adaptive attackers. The security loss (to the underlying PKE) in the Random Oracle Model is a polynomial factor, and a quasipolynomial one in the Standard Model. Our proofs can be adapted to TreeKEM as well. Before our work no security proof for any TreeKEM-like protocol establishing tight security against an adversary who can adaptively choose the sequence of operations was known. We also are the first to prove (or even formalize) active security where the server can arbitrarily deviate from the protocol specification. Proving fully active security – where also the users can arbitrarily deviate – remains open.","lang":"eng"}],"date_created":"2021-09-27T13:46:27Z","oa":1,"title":"Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement","_id":"10049","status":"public","corr_author":"1","isi":1,"publication_status":"published","page":"268-284","project":[{"_id":"2564DBCA-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"665385","name":"International IST Doctoral Program"},{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"year":"2021","date_updated":"2026-04-08T07:01:44Z","conference":{"end_date":"2021-05-27","name":"SP: Symposium on Security and Privacy","location":"San Francisco, CA, United States","start_date":"2021-05-24"},"oa_version":"Preprint","scopus_import":"1","quality_controlled":"1","month":"08","doi":"10.1109/sp40001.2021.00035","type":"conference","external_id":{"isi":["001316065000016"]},"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2019/1489"}],"date_published":"2021-08-26T00:00:00Z","day":"26","article_processing_charge":"No","publisher":"IEEE","citation":{"mla":"Klein, Karen, et al. “Keep the Dirt: Tainted TreeKEM, Adaptively and Actively Secure Continuous Group Key Agreement.” <i>2021 IEEE Symposium on Security and Privacy </i>, IEEE, 2021, pp. 268–84, doi:<a href=\"https://doi.org/10.1109/sp40001.2021.00035\">10.1109/sp40001.2021.00035</a>.","apa":"Klein, K., Pascual Perez, G., Walter, M., Kamath Hosdurg, C., Capretto, M., Cueto Noval, M., … Pietrzak, K. Z. (2021). Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement. In <i>2021 IEEE Symposium on Security and Privacy </i> (pp. 268–284). San Francisco, CA, United States: IEEE. <a href=\"https://doi.org/10.1109/sp40001.2021.00035\">https://doi.org/10.1109/sp40001.2021.00035</a>","ama":"Klein K, Pascual Perez G, Walter M, et al. Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement. In: <i>2021 IEEE Symposium on Security and Privacy </i>. IEEE; 2021:268-284. doi:<a href=\"https://doi.org/10.1109/sp40001.2021.00035\">10.1109/sp40001.2021.00035</a>","chicago":"Klein, Karen, Guillermo Pascual Perez, Michael Walter, Chethan Kamath Hosdurg, Margarita Capretto, Miguel Cueto Noval, Ilia Markov, Michelle X Yeo, Joel F Alwen, and Krzysztof Z Pietrzak. “Keep the Dirt: Tainted TreeKEM, Adaptively and Actively Secure Continuous Group Key Agreement.” In <i>2021 IEEE Symposium on Security and Privacy </i>, 268–84. IEEE, 2021. <a href=\"https://doi.org/10.1109/sp40001.2021.00035\">https://doi.org/10.1109/sp40001.2021.00035</a>.","ieee":"K. Klein <i>et al.</i>, “Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement,” in <i>2021 IEEE Symposium on Security and Privacy </i>, San Francisco, CA, United States, 2021, pp. 268–284.","ista":"Klein K, Pascual Perez G, Walter M, Kamath Hosdurg C, Capretto M, Cueto Noval M, Markov I, Yeo MX, Alwen JF, Pietrzak KZ. 2021. Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement. 2021 IEEE Symposium on Security and Privacy . SP: Symposium on Security and Privacy, 268–284.","short":"K. Klein, G. Pascual Perez, M. Walter, C. Kamath Hosdurg, M. Capretto, M. Cueto Noval, I. Markov, M.X. Yeo, J.F. Alwen, K.Z. Pietrzak, in:, 2021 IEEE Symposium on Security and Privacy , IEEE, 2021, pp. 268–284."},"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","language":[{"iso":"eng"}],"publication":"2021 IEEE Symposium on Security and Privacy ","author":[{"id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","full_name":"Klein, Karen","last_name":"Klein","first_name":"Karen"},{"full_name":"Pascual Perez, Guillermo","last_name":"Pascual Perez","first_name":"Guillermo","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8630-415X"},{"orcid":"0000-0003-3186-2482","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","first_name":"Michael","last_name":"Walter","full_name":"Walter, Michael"},{"full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan","last_name":"Kamath Hosdurg","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","orcid":"0009-0006-6812-7317"},{"full_name":"Capretto, Margarita","first_name":"Margarita","last_name":"Capretto"},{"full_name":"Cueto Noval, Miguel","first_name":"Miguel","last_name":"Cueto Noval","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","orcid":"0000-0002-2505-4246"},{"id":"D0CF4148-C985-11E9-8066-0BDEE5697425","full_name":"Markov, Ilia","last_name":"Markov","first_name":"Ilia"},{"full_name":"Yeo, Michelle X","last_name":"Yeo","first_name":"Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","orcid":"0009-0001-3676-4809"},{"id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","full_name":"Alwen, Joel F","first_name":"Joel F","last_name":"Alwen"},{"full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654"}],"ec_funded":1,"acknowledgement":"The first three authors contributed equally to this work. Funded by the European Research Council (ERC) under the European Union’s Horizon2020 research and innovation programme (682815-TOCNeT). Funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No.665385.","related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"18088"},{"id":"10035","status":"public","relation":"dissertation_contains"}]},"department":[{"_id":"KrPi"},{"_id":"DaAl"}]},{"publisher":"ML Research Press","file":[{"creator":"cziletti","file_name":"2021_JMachLearnRes_Hoefler.pdf","file_id":"10192","date_created":"2021-10-27T15:34:18Z","checksum":"3389d9d01fc58f8fb4c1a53e14a8abbf","relation":"main_file","content_type":"application/pdf","date_updated":"2021-10-27T15:34:18Z","success":1,"access_level":"open_access","file_size":3527521}],"citation":{"short":"T. Hoefler, D.-A. Alistarh, T. Ben-Nun, N. Dryden, A. Krumes, Journal of Machine Learning Research 22 (2021) 1–124.","ieee":"T. Hoefler, D.-A. Alistarh, T. Ben-Nun, N. Dryden, and A. Krumes, “Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks,” <i>Journal of Machine Learning Research</i>, vol. 22, no. 241. ML Research Press, pp. 1–124, 2021.","ista":"Hoefler T, Alistarh D-A, Ben-Nun T, Dryden N, Krumes A. 2021. Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks. Journal of Machine Learning Research. 22(241), 1–124.","chicago":"Hoefler, Torsten, Dan-Adrian Alistarh, Tal Ben-Nun, Nikoli Dryden, and Alexandra Krumes. “Sparsity in Deep Learning: Pruning and Growth for Efficient Inference and Training in Neural Networks.” <i>Journal of Machine Learning Research</i>. ML Research Press, 2021.","ama":"Hoefler T, Alistarh D-A, Ben-Nun T, Dryden N, Krumes A. Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks. <i>Journal of Machine Learning Research</i>. 2021;22(241):1-124.","apa":"Hoefler, T., Alistarh, D.-A., Ben-Nun, T., Dryden, N., &#38; Krumes, A. (2021). Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks. <i>Journal of Machine Learning Research</i>. ML Research Press.","mla":"Hoefler, Torsten, et al. “Sparsity in Deep Learning: Pruning and Growth for Efficient Inference and Training in Neural Networks.” <i>Journal of Machine Learning Research</i>, vol. 22, no. 241, ML Research Press, 2021, pp. 1–124."},"issue":"241","intvolume":"        22","file_date_updated":"2021-10-27T15:34:18Z","main_file_link":[{"open_access":"1","url":"https://www.jmlr.org/papers/v22/21-0366.html"}],"day":"01","date_published":"2021-09-01T00:00:00Z","article_processing_charge":"No","author":[{"last_name":"Hoefler","first_name":"Torsten","full_name":"Hoefler, Torsten"},{"last_name":"Alistarh","first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Tal","last_name":"Ben-Nun","full_name":"Ben-Nun, Tal"},{"full_name":"Dryden, Nikoli","last_name":"Dryden","first_name":"Nikoli"},{"first_name":"Elena-Alexandra","last_name":"Peste","full_name":"Peste, Elena-Alexandra","id":"32D78294-F248-11E8-B48F-1D18A9856A87"}],"OA_place":"publisher","acknowledgement":"We thank Doug Burger, Steve Scott, Marco Heddes, and the respective teams at Microsoft for inspiring discussions on the topic. We thank Angelika Steger for uplifting debates about the connections to biological brains, Sidak Pal Singh for his support regarding experimental results, and Utku Evci as well as Xin Wang for comments on previous versions of this\r\nwork. Special thanks go to Bernhard Schölkopf, our JMLR editor Samy Bengio, and the three anonymous reviewers who provided excellent comprehensive, pointed, and deep review comments that improved the quality of our manuscript significantly.","department":[{"_id":"DaAl"}],"publication":"Journal of Machine Learning Research","ddc":["000"],"language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","arxiv":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"publication_identifier":{"eissn":["1533-7928"],"issn":["1532-4435"]},"quality_controlled":"1","month":"09","article_type":"original","type":"journal_article","external_id":{"arxiv":["2102.00554"]},"volume":22,"has_accepted_license":"1","year":"2021","page":"1-124","publication_status":"published","scopus_import":"1","oa_version":"Published Version","date_updated":"2025-06-26T11:53:12Z","title":"Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks","_id":"10180","status":"public","abstract":[{"text":"The growing energy and performance costs of deep learning have driven the community to reduce the size of neural networks by selectively pruning components. Similarly to their biological counterparts, sparse networks generalize just as well, sometimes even better than, the original dense networks. Sparsity promises to reduce the memory footprint of regular networks to fit mobile devices, as well as shorten training time for ever growing networks. In this paper, we survey prior work on sparsity in deep learning and provide an extensive tutorial of sparsification for both inference and training. We describe approaches to remove and add elements of neural networks, different training strategies to achieve model sparsity, and mechanisms to exploit sparsity in practice. Our work distills ideas from more than 300 research papers and provides guidance to practitioners who wish to utilize sparsity today, as well as to researchers whose goal is to push the frontier forward. We include the necessary background on mathematical methods in sparsification, describe phenomena such as early structure adaptation, the intricate relations between sparsity and the training process, and show techniques for achieving acceleration on real hardware. We also define a metric of pruned parameter efficiency that could serve as a baseline for comparison of different sparse networks. We close by speculating on how sparsity can improve future workloads and outline major open problems in the field.","lang":"eng"}],"oa":1,"date_created":"2021-10-24T22:01:34Z","corr_author":"1"},{"date_updated":"2025-05-14T10:54:39Z","conference":{"name":"DISC: Distributed Computing","end_date":"2021-10-08","start_date":"2021-10-04","location":"Freiburg, Germany"},"scopus_import":"1","oa_version":"Published Version","publication_status":"published","year":"2021","abstract":[{"text":"This paper reports a new concurrent graph data structure that supports updates of both edges and vertices and queries: Breadth-first search, Single-source shortest-path, and Betweenness centrality. The operations are provably linearizable and non-blocking.","lang":"eng"}],"oa":1,"date_created":"2021-11-07T23:01:23Z","title":"Brief announcement: Non-blocking dynamic unbounded graphs with worst-case amortized bounds","status":"public","_id":"10216","language":[{"iso":"eng"}],"publication":"35th International Symposium on Distributed Computing","ddc":["000"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","arxiv":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"author":[{"id":"3C41A08A-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-2742-4028","full_name":"Chatterjee, Bapi","last_name":"Chatterjee","first_name":"Bapi"},{"first_name":"Sathya","last_name":"Peri","full_name":"Peri, Sathya"},{"full_name":"Sa, Muktikanta","last_name":"Sa","first_name":"Muktikanta"}],"acknowledgement":"This work was partially funded by National Supercomputing Mission, Govt. of India under the project “Concurrent and Distributed Programming primitives and algorithms for Temporal Graphs”(DST/NSM/R&D_Exascale/2021/16).\r\n","department":[{"_id":"DaAl"}],"article_number":"52","file_date_updated":"2021-11-12T09:23:22Z","day":"04","date_published":"2021-10-04T00:00:00Z","article_processing_charge":"No","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","file":[{"date_updated":"2021-11-12T09:23:22Z","content_type":"application/pdf","success":1,"file_size":795860,"access_level":"open_access","checksum":"76546df112a0ba1166c864d33d7834e2","relation":"main_file","date_created":"2021-11-12T09:23:22Z","file_id":"10276","file_name":"2021_LIPIcsDISC_BChatterjee.pdf","creator":"cchlebak"}],"citation":{"short":"B. Chatterjee, S. Peri, M. Sa, in:, 35th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.","ama":"Chatterjee B, Peri S, Sa M. Brief announcement: Non-blocking dynamic unbounded graphs with worst-case amortized bounds. In: <i>35th International Symposium on Distributed Computing</i>. Vol 209. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.52\">10.4230/LIPIcs.DISC.2021.52</a>","chicago":"Chatterjee, Bapi, Sathya Peri, and Muktikanta Sa. “Brief Announcement: Non-Blocking Dynamic Unbounded Graphs with Worst-Case Amortized Bounds.” In <i>35th International Symposium on Distributed Computing</i>, Vol. 209. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.52\">https://doi.org/10.4230/LIPIcs.DISC.2021.52</a>.","ieee":"B. Chatterjee, S. Peri, and M. Sa, “Brief announcement: Non-blocking dynamic unbounded graphs with worst-case amortized bounds,” in <i>35th International Symposium on Distributed Computing</i>, Freiburg, Germany, 2021, vol. 209.","ista":"Chatterjee B, Peri S, Sa M. 2021. Brief announcement: Non-blocking dynamic unbounded graphs with worst-case amortized bounds. 35th International Symposium on Distributed Computing. DISC: Distributed Computing, LIPIcs, vol. 209, 52.","mla":"Chatterjee, Bapi, et al. “Brief Announcement: Non-Blocking Dynamic Unbounded Graphs with Worst-Case Amortized Bounds.” <i>35th International Symposium on Distributed Computing</i>, vol. 209, 52, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.52\">10.4230/LIPIcs.DISC.2021.52</a>.","apa":"Chatterjee, B., Peri, S., &#38; Sa, M. (2021). Brief announcement: Non-blocking dynamic unbounded graphs with worst-case amortized bounds. In <i>35th International Symposium on Distributed Computing</i> (Vol. 209). Freiburg, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.52\">https://doi.org/10.4230/LIPIcs.DISC.2021.52</a>"},"intvolume":"       209","doi":"10.4230/LIPIcs.DISC.2021.52","has_accepted_license":"1","volume":209,"type":"conference","external_id":{"arxiv":["2003.01697"]},"quality_controlled":"1","month":"10","publication_identifier":{"isbn":["9-783-9597-7210-5"],"issn":["1868-8969"]},"alternative_title":["LIPIcs"]},{"department":[{"_id":"DaAl"}],"acknowledgement":"Dan Alistarh: 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). Giorgi Nadiradze: 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). The authors would like to thank the DISC anonymous reviewers for their useful\r\nfeedback and comments.","ec_funded":1,"author":[{"last_name":"Alistarh","first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Gelashvili, Rati","last_name":"Gelashvili","first_name":"Rati"},{"full_name":"Nadiradze, Giorgi","first_name":"Giorgi","last_name":"Nadiradze","id":"3279A00C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-5634-0731"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"ddc":["000"],"publication":"35th International Symposium on Distributed Computing","language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":"       209","citation":{"short":"D.-A. Alistarh, R. Gelashvili, G. Nadiradze, in:, 35th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.","chicago":"Alistarh, Dan-Adrian, Rati Gelashvili, and Giorgi Nadiradze. “Lower Bounds for Shared-Memory Leader Election under Bounded Write Contention.” In <i>35th International Symposium on Distributed Computing</i>, Vol. 209. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.4\">https://doi.org/10.4230/LIPIcs.DISC.2021.4</a>.","ieee":"D.-A. Alistarh, R. Gelashvili, and G. Nadiradze, “Lower bounds for shared-memory leader election under bounded write contention,” in <i>35th International Symposium on Distributed Computing</i>, Freiburg, Germany, 2021, vol. 209.","ista":"Alistarh D-A, Gelashvili R, Nadiradze G. 2021. Lower bounds for shared-memory leader election under bounded write contention. 35th International Symposium on Distributed Computing. DISC: Distributed Computing, LIPIcs, vol. 209, 4.","ama":"Alistarh D-A, Gelashvili R, Nadiradze G. Lower bounds for shared-memory leader election under bounded write contention. In: <i>35th International Symposium on Distributed Computing</i>. Vol 209. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.4\">10.4230/LIPIcs.DISC.2021.4</a>","apa":"Alistarh, D.-A., Gelashvili, R., &#38; Nadiradze, G. (2021). Lower bounds for shared-memory leader election under bounded write contention. In <i>35th International Symposium on Distributed Computing</i> (Vol. 209). Freiburg, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.4\">https://doi.org/10.4230/LIPIcs.DISC.2021.4</a>","mla":"Alistarh, Dan-Adrian, et al. “Lower Bounds for Shared-Memory Leader Election under Bounded Write Contention.” <i>35th International Symposium on Distributed Computing</i>, vol. 209, 4, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.4\">10.4230/LIPIcs.DISC.2021.4</a>."},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","file":[{"file_id":"10277","creator":"cchlebak","file_name":"2021_LIPIcsDISC_Alistarh.pdf","date_created":"2021-11-12T09:33:26Z","checksum":"b4cdc6668c899a601c5e6a96b8ca54d9","relation":"main_file","success":1,"date_updated":"2021-11-12T09:33:26Z","content_type":"application/pdf","file_size":706791,"access_level":"open_access"}],"article_processing_charge":"No","day":"04","date_published":"2021-10-04T00:00:00Z","article_number":"4","file_date_updated":"2021-11-12T09:33:26Z","type":"conference","volume":209,"has_accepted_license":"1","doi":"10.4230/LIPIcs.DISC.2021.4","publication_identifier":{"isbn":["9-783-9597-7210-5"],"issn":["1868-8969"]},"alternative_title":["LIPIcs"],"month":"10","quality_controlled":"1","oa_version":"Published Version","scopus_import":"1","conference":{"end_date":"2021-10-08","name":"DISC: Distributed Computing","location":"Freiburg, Germany","start_date":"2021-10-04"},"date_updated":"2025-05-14T10:54:30Z","year":"2021","project":[{"grant_number":"805223","name":"Elastic Coordination for Scalable Machine Learning","call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425"}],"publication_status":"published","_id":"10217","status":"public","title":"Lower bounds for shared-memory leader election under bounded write contention","oa":1,"date_created":"2021-11-07T23:01:23Z","abstract":[{"lang":"eng","text":"This paper gives tight logarithmic lower bounds on the solo step complexity of leader election in an asynchronous shared-memory model with single-writer multi-reader (SWMR) registers, for both deterministic and randomized obstruction-free algorithms. The approach extends to lower bounds for deterministic and randomized obstruction-free algorithms using multi-writer registers under bounded write concurrency, showing a trade-off between the solo step complexity of a leader election algorithm, and the worst-case number of stalls incurred by a processor in an execution."}]},{"publication_identifier":{"issn":["1868-8969"],"isbn":["9-783-9597-7210-5"]},"alternative_title":["LIPIcs"],"month":"10","quality_controlled":"1","external_id":{"arxiv":["2102.08808"]},"type":"conference","has_accepted_license":"1","volume":209,"doi":"10.4230/LIPIcs.DISC.2021.43","citation":{"ama":"Alistarh D-A, Gelashvili R, Rybicki J. Brief announcement: Fast graphical population protocols. In: <i>35th International Symposium on Distributed Computing</i>. Vol 209. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.43\">10.4230/LIPIcs.DISC.2021.43</a>","ista":"Alistarh D-A, Gelashvili R, Rybicki J. 2021. Brief announcement: Fast graphical population protocols. 35th International Symposium on Distributed Computing. DISC: Distributed Computing , LIPIcs, vol. 209, 43.","ieee":"D.-A. Alistarh, R. Gelashvili, and J. Rybicki, “Brief announcement: Fast graphical population protocols,” in <i>35th International Symposium on Distributed Computing</i>, Freiburg, Germany, 2021, vol. 209.","chicago":"Alistarh, Dan-Adrian, Rati Gelashvili, and Joel Rybicki. “Brief Announcement: Fast Graphical Population Protocols.” In <i>35th International Symposium on Distributed Computing</i>, Vol. 209. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.43\">https://doi.org/10.4230/LIPIcs.DISC.2021.43</a>.","short":"D.-A. Alistarh, R. Gelashvili, J. Rybicki, in:, 35th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.","mla":"Alistarh, Dan-Adrian, et al. “Brief Announcement: Fast Graphical Population Protocols.” <i>35th International Symposium on Distributed Computing</i>, vol. 209, 43, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.43\">10.4230/LIPIcs.DISC.2021.43</a>.","apa":"Alistarh, D.-A., Gelashvili, R., &#38; Rybicki, J. (2021). Brief announcement: Fast graphical population protocols. In <i>35th International Symposium on Distributed Computing</i> (Vol. 209). Freiburg, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.43\">https://doi.org/10.4230/LIPIcs.DISC.2021.43</a>"},"file":[{"file_size":534219,"access_level":"open_access","success":1,"content_type":"application/pdf","date_updated":"2021-11-12T08:16:44Z","relation":"main_file","checksum":"fd2a690f6856d21247e9aa952b0e2885","date_created":"2021-11-12T08:16:44Z","creator":"cchlebak","file_name":"2021_LIPIcsDISC_Alistarh.pdf","file_id":"10274"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","intvolume":"       209","article_number":"43","file_date_updated":"2021-11-12T08:16:44Z","article_processing_charge":"No","date_published":"2021-10-04T00:00:00Z","day":"04","ec_funded":1,"author":[{"full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X"},{"last_name":"Gelashvili","first_name":"Rati","full_name":"Gelashvili, Rati"},{"orcid":"0000-0002-6432-6646","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","first_name":"Joel","last_name":"Rybicki","full_name":"Rybicki, Joel"}],"department":[{"_id":"DaAl"}],"acknowledgement":"This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 840605.","arxiv":1,"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","ddc":["000"],"language":[{"iso":"eng"}],"publication":"35th International Symposium on Distributed Computing","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"title":"Brief announcement: Fast graphical population protocols","_id":"10218","status":"public","oa":1,"date_created":"2021-11-07T23:01:24Z","abstract":[{"lang":"eng","text":"Let G be a graph on n nodes. In the stochastic population protocol model, a collection of n indistinguishable, resource-limited nodes collectively solve tasks via pairwise interactions. In each interaction, two randomly chosen neighbors first read each other’s states, and then update their local states. A rich line of research has established tight upper and lower bounds on the complexity of fundamental tasks, such as majority and leader election, in this model, when G is a clique. Specifically, in the clique, these tasks can be solved fast, i.e., in n polylog n pairwise interactions, with high probability, using at most polylog n states per node. In this work, we consider the more general setting where G is an arbitrary graph, and present a technique for simulating protocols designed for fully-connected networks in any connected regular graph. Our main result is a simulation that is efficient on many interesting graph families: roughly, the simulation overhead is polylogarithmic in the number of nodes, and quadratic in the conductance of the graph. As an example, this implies that, in any regular graph with conductance φ, both leader election and exact majority can be solved in φ^{-2} ⋅ n polylog n pairwise interactions, with high probability, using at most φ^{-2} ⋅ polylog n states per node. This shows that there are fast and space-efficient population protocols for leader election and exact majority on graphs with good expansion properties."}],"project":[{"name":"Coordination in constrained and natural distributed systems","grant_number":"840605","_id":"26A5D39A-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"year":"2021","publication_status":"published","scopus_import":"1","oa_version":"Published Version","date_updated":"2025-04-14T07:50:55Z","conference":{"end_date":"2021-10-08","name":"DISC: Distributed Computing ","start_date":"2021-10-04","location":"Freiburg, Germany"}},{"title":"Brief announcement: Sinkless orientation is hard also in the supported LOCAL model","_id":"10219","status":"public","abstract":[{"lang":"eng","text":"We show that any algorithm that solves the sinkless orientation problem in the supported LOCAL model requires Ω(log n) rounds, and this is tight. The supported LOCAL is at least as strong as the usual LOCAL model, and as a corollary this also gives a new, short and elementary proof that shows that the round complexity of the sinkless orientation problem in the deterministic LOCAL model is Ω(log n)."}],"oa":1,"date_created":"2021-11-07T23:01:24Z","project":[{"name":"Elastic Coordination for Scalable Machine Learning","grant_number":"805223","_id":"268A44D6-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"year":"2021","publication_status":"published","scopus_import":"1","oa_version":"Published Version","date_updated":"2025-05-14T10:54:13Z","conference":{"start_date":"2021-10-04","location":"Freiburg, Germany","end_date":"2021-10-08","name":"DISC: Distributed Computing "},"publication_identifier":{"issn":["1868-8969"],"isbn":["9-783-9597-7210-5"]},"alternative_title":["LIPIcs"],"quality_controlled":"1","month":"10","type":"conference","external_id":{"arxiv":["2108.02655"]},"doi":"10.4230/LIPIcs.DISC.2021.58","volume":209,"has_accepted_license":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","file":[{"file_size":474242,"access_level":"open_access","content_type":"application/pdf","date_updated":"2021-11-12T08:27:42Z","success":1,"relation":"main_file","checksum":"c43188dc2070bbd2bf5fd6fdaf9ce36d","date_created":"2021-11-12T08:27:42Z","file_name":"2021_LIPIcsDISC_Korhonen.pdf","creator":"cchlebak","file_id":"10275"}],"citation":{"ama":"Korhonen J, Paz A, Rybicki J, Schmid S, Suomela J. Brief announcement: Sinkless orientation is hard also in the supported LOCAL model. In: <i>35th International Symposium on Distributed Computing</i>. Vol 209. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.58\">10.4230/LIPIcs.DISC.2021.58</a>","ista":"Korhonen J, Paz A, Rybicki J, Schmid S, Suomela J. 2021. Brief announcement: Sinkless orientation is hard also in the supported LOCAL model. 35th International Symposium on Distributed Computing. DISC: Distributed Computing , LIPIcs, vol. 209, 58.","ieee":"J. Korhonen, A. Paz, J. Rybicki, S. Schmid, and J. Suomela, “Brief announcement: Sinkless orientation is hard also in the supported LOCAL model,” in <i>35th International Symposium on Distributed Computing</i>, Freiburg, Germany, 2021, vol. 209.","chicago":"Korhonen, Janne, Ami Paz, Joel Rybicki, Stefan Schmid, and Jukka Suomela. “Brief Announcement: Sinkless Orientation Is Hard Also in the Supported LOCAL Model.” In <i>35th International Symposium on Distributed Computing</i>, Vol. 209. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.58\">https://doi.org/10.4230/LIPIcs.DISC.2021.58</a>.","short":"J. Korhonen, A. Paz, J. Rybicki, S. Schmid, J. Suomela, in:, 35th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.","mla":"Korhonen, Janne, et al. “Brief Announcement: Sinkless Orientation Is Hard Also in the Supported LOCAL Model.” <i>35th International Symposium on Distributed Computing</i>, vol. 209, 58, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.58\">10.4230/LIPIcs.DISC.2021.58</a>.","apa":"Korhonen, J., Paz, A., Rybicki, J., Schmid, S., &#38; Suomela, J. (2021). Brief announcement: Sinkless orientation is hard also in the supported LOCAL model. In <i>35th International Symposium on Distributed Computing</i> (Vol. 209). Freiburg, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.58\">https://doi.org/10.4230/LIPIcs.DISC.2021.58</a>"},"intvolume":"       209","article_number":"58","file_date_updated":"2021-11-12T08:27:42Z","day":"04","date_published":"2021-10-04T00:00:00Z","article_processing_charge":"No","ec_funded":1,"author":[{"full_name":"Korhonen, Janne","last_name":"Korhonen","first_name":"Janne","id":"C5402D42-15BC-11E9-A202-CA2BE6697425"},{"last_name":"Paz","first_name":"Ami","full_name":"Paz, Ami"},{"full_name":"Rybicki, Joel","last_name":"Rybicki","first_name":"Joel","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6432-6646"},{"last_name":"Schmid","first_name":"Stefan","full_name":"Schmid, Stefan"},{"full_name":"Suomela, Jukka","last_name":"Suomela","first_name":"Jukka"}],"acknowledgement":"Janne H. Korhonen: Project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML). Ami Paz: We acknowledge the Austrian Science Fund (FWF) and netIDEE SCIENCE project P 33775-N. Stefan Schmid: Research supported by the Austrian Science Fund (FWF) project ADVISE, I 4800-N, 2020-2023.\r\n","department":[{"_id":"DaAl"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"35th International Symposium on Distributed Computing","ddc":["000"],"language":[{"iso":"eng"}],"arxiv":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"}},{"type":"conference","external_id":{"arxiv":["1910.12308"]},"quality_controlled":"1","month":"12","acknowledgement":"We gratefully acknowledge funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML). PD partly conducted this work while at IST Austria and was supported by the European Union’s Horizon 2020 programme under the Marie Skłodowska-Curie grant agreement No. 754411. SL was funded in part by European Research Council (ERC) under the European Union’s Horizon 2020 programme (grant agreement DAPP, No. 678880, and EPiGRAM-HS, No. 801039).\r\n","related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"10429"}]},"department":[{"_id":"DaAl"}],"ec_funded":1,"author":[{"full_name":"Nadiradze, Giorgi","last_name":"Nadiradze","first_name":"Giorgi","id":"3279A00C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-5634-0731"},{"id":"bcc145fd-e77f-11ea-ae8b-80d661dbff67","first_name":"Amirmojtaba","last_name":"Sabour","full_name":"Sabour, Amirmojtaba"},{"last_name":"Davies","first_name":"Peter","full_name":"Davies, Peter","orcid":"0000-0002-5646-9524","id":"11396234-BB50-11E9-B24C-90FCE5697425"},{"full_name":"Li, Shigang","last_name":"Li","first_name":"Shigang"},{"first_name":"Dan-Adrian","last_name":"Alistarh","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"}],"language":[{"iso":"eng"}],"ddc":["000"],"publication":"35th Conference on Neural Information Processing Systems","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","arxiv":1,"publisher":"Neural Information Processing Systems Foundation","citation":{"chicago":"Nadiradze, Giorgi, Amirmojtaba Sabour, Peter Davies, Shigang Li, and Dan-Adrian Alistarh. “Asynchronous Decentralized SGD with Quantized and Local Updates.” In <i>35th Conference on Neural Information Processing Systems</i>. Neural Information Processing Systems Foundation, 2021.","ista":"Nadiradze G, Sabour A, Davies P, Li S, Alistarh D-A. 2021. Asynchronous decentralized SGD with quantized and local updates. 35th Conference on Neural Information Processing Systems. NeurIPS: Neural Information Processing Systems.","ieee":"G. Nadiradze, A. Sabour, P. Davies, S. Li, and D.-A. Alistarh, “Asynchronous decentralized SGD with quantized and local updates,” in <i>35th Conference on Neural Information Processing Systems</i>, Sydney, Australia, 2021.","ama":"Nadiradze G, Sabour A, Davies P, Li S, Alistarh D-A. Asynchronous decentralized SGD with quantized and local updates. In: <i>35th Conference on Neural Information Processing Systems</i>. Neural Information Processing Systems Foundation; 2021.","short":"G. Nadiradze, A. Sabour, P. Davies, S. Li, D.-A. Alistarh, in:, 35th Conference on Neural Information Processing Systems, Neural Information Processing Systems Foundation, 2021.","apa":"Nadiradze, G., Sabour, A., Davies, P., Li, S., &#38; Alistarh, D.-A. (2021). Asynchronous decentralized SGD with quantized and local updates. In <i>35th Conference on Neural Information Processing Systems</i>. Sydney, Australia: Neural Information Processing Systems Foundation.","mla":"Nadiradze, Giorgi, et al. “Asynchronous Decentralized SGD with Quantized and Local Updates.” <i>35th Conference on Neural Information Processing Systems</i>, Neural Information Processing Systems Foundation, 2021."},"main_file_link":[{"url":"https://papers.nips.cc/paper/2021/hash/362c99307cdc3f2d8b410652386a9dd1-Abstract.html","open_access":"1"}],"date_published":"2021-12-01T00:00:00Z","day":"01","article_processing_charge":"No","_id":"10435","status":"public","title":"Asynchronous decentralized SGD with quantized and local updates","abstract":[{"lang":"eng","text":"Decentralized optimization is emerging as a viable alternative for scalable distributed machine learning, but also introduces new challenges in terms of synchronization costs. To this end, several communication-reduction techniques, such as non-blocking communication, quantization, and local steps, have been explored in the decentralized setting. Due to the complexity of analyzing optimization in such a relaxed setting, this line of work often assumes \\emph{global} communication rounds, which require additional synchronization. In this paper, we consider decentralized optimization in the simpler, but harder to analyze, \\emph{asynchronous gossip} model, in which communication occurs in discrete, randomly chosen pairings among nodes. Perhaps surprisingly, we show that a variant of SGD called \\emph{SwarmSGD} still converges in this setting, even if \\emph{non-blocking communication}, \\emph{quantization}, and \\emph{local steps} are all applied \\emph{in conjunction}, and even if the node data distributions and underlying graph topology are both \\emph{heterogenous}. Our analysis is based on a new connection with multi-dimensional load-balancing processes. We implement this algorithm and deploy it in a super-computing environment, showing that it can outperform previous decentralized methods in terms of end-to-end training time, and that it can even rival carefully-tuned large-batch SGD for certain tasks."}],"date_created":"2021-12-09T10:59:12Z","oa":1,"oa_version":"Published Version","conference":{"name":"NeurIPS: Neural Information Processing Systems","end_date":"2021-12-14","location":"Sydney, Australia","start_date":"2021-12-06"},"date_updated":"2026-06-18T08:41:40Z","year":"2021","project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships"},{"grant_number":"805223","name":"Elastic Coordination for Scalable Machine Learning","_id":"268A44D6-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"publication_status":"published"},{"volume":34,"doi":"10.1007/s00446-020-00380-5","external_id":{"isi":["000556444600001"],"arxiv":["1903.05956"]},"type":"journal_article","month":"12","quality_controlled":"1","article_type":"original","publication_identifier":{"issn":["0178-2770"],"eissn":["1432-0452"]},"arxiv":1,"language":[{"iso":"eng"}],"publication":"Distributed Computing","ddc":["000"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Censor-Hillel, Keren","last_name":"Censor-Hillel","first_name":"Keren"},{"last_name":"Dory","first_name":"Michal","full_name":"Dory, Michal"},{"first_name":"Janne","last_name":"Korhonen","full_name":"Korhonen, Janne","id":"C5402D42-15BC-11E9-A202-CA2BE6697425"},{"full_name":"Leitersdorf, Dean","first_name":"Dean","last_name":"Leitersdorf"}],"department":[{"_id":"DaAl"}],"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"6933"}]},"acknowledgement":"Open access funding provided by Institute of Science and Technology (IST Austria). We thank Mohsen Ghaffari, Michael Elkin and Merav Parter for fruitful discussions. This project has received funding from the European Union’s Horizon 2020 Research And Innovation Program under Grant Agreement No. 755839.","article_processing_charge":"Yes (via OA deal)","date_published":"2021-12-01T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1007/s00446-020-00380-5"}],"day":"01","citation":{"apa":"Censor-Hillel, K., Dory, M., Korhonen, J., &#38; Leitersdorf, D. (2021). Fast approximate shortest paths in the congested clique. <i>Distributed Computing</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00446-020-00380-5\">https://doi.org/10.1007/s00446-020-00380-5</a>","mla":"Censor-Hillel, Keren, et al. “Fast Approximate Shortest Paths in the Congested Clique.” <i>Distributed Computing</i>, vol. 34, Springer Nature, 2021, pp. 463–87, doi:<a href=\"https://doi.org/10.1007/s00446-020-00380-5\">10.1007/s00446-020-00380-5</a>.","ieee":"K. Censor-Hillel, M. Dory, J. Korhonen, and D. Leitersdorf, “Fast approximate shortest paths in the congested clique,” <i>Distributed Computing</i>, vol. 34. Springer Nature, pp. 463–487, 2021.","chicago":"Censor-Hillel, Keren, Michal Dory, Janne Korhonen, and Dean Leitersdorf. “Fast Approximate Shortest Paths in the Congested Clique.” <i>Distributed Computing</i>. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/s00446-020-00380-5\">https://doi.org/10.1007/s00446-020-00380-5</a>.","ista":"Censor-Hillel K, Dory M, Korhonen J, Leitersdorf D. 2021. Fast approximate shortest paths in the congested clique. Distributed Computing. 34, 463–487.","ama":"Censor-Hillel K, Dory M, Korhonen J, Leitersdorf D. Fast approximate shortest paths in the congested clique. <i>Distributed Computing</i>. 2021;34:463-487. doi:<a href=\"https://doi.org/10.1007/s00446-020-00380-5\">10.1007/s00446-020-00380-5</a>","short":"K. Censor-Hillel, M. Dory, J. Korhonen, D. Leitersdorf, Distributed Computing 34 (2021) 463–487."},"publisher":"Springer Nature","intvolume":"        34","isi":1,"corr_author":"1","oa":1,"date_created":"2020-06-07T22:00:54Z","abstract":[{"lang":"eng","text":"We design fast deterministic algorithms for distance computation in the Congested Clique model. Our key contributions include:\r\n    A (2+ϵ)-approximation for all-pairs shortest paths in O(log2n/ϵ) rounds on unweighted undirected graphs. With a small additional additive factor, this also applies for weighted graphs. This is the first sub-polynomial constant-factor approximation for APSP in this model.\r\n    A (1+ϵ)-approximation for multi-source shortest paths from O(n−−√) sources in O(log2n/ϵ) rounds on weighted undirected graphs. This is the first sub-polynomial algorithm obtaining this approximation for a set of sources of polynomial size.\r\n\r\nOur main techniques are new distance tools that are obtained via improved algorithms for sparse matrix multiplication, which we leverage to construct efficient hopsets and shortest paths. Furthermore, our techniques extend to additional distance problems for which we improve upon the state-of-the-art, including diameter approximation, and an exact single-source shortest paths algorithm for weighted undirected graphs in O~(n1/6) rounds. "}],"title":"Fast approximate shortest paths in the congested clique","_id":"7939","status":"public","date_updated":"2026-06-18T19:28:41Z","oa_version":"Published Version","scopus_import":"1","page":"463-487","publication_status":"published","project":[{"name":"IST Austria Open Access Fund","_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854"}],"year":"2021"},{"title":"Breaking (global) barriers in parallel stochastic optimization with wait-avoiding group averaging","_id":"8723","status":"public","date_created":"2020-11-05T15:25:43Z","oa":1,"abstract":[{"lang":"eng","text":"Deep learning at scale is dominated by communication time. Distributing samples across nodes usually yields the best performance, but poses scaling challenges due to global information dissemination and load imbalance across uneven sample lengths. State-of-the-art decentralized optimizers mitigate the problem, but require more iterations to achieve the same accuracy as their globally-communicating counterparts. We present Wait-Avoiding Group Model Averaging (WAGMA) SGD, a wait-avoiding stochastic optimizer that reduces global communication via subgroup weight exchange. The key insight is a combination of algorithmic changes to the averaging scheme and the use of a group allreduce operation. We prove the convergence of WAGMA-SGD, and empirically show that it retains convergence rates similar to Allreduce-SGD. For evaluation, we train ResNet-50 on ImageNet; Transformer for machine translation; and deep reinforcement learning for navigation at scale. Compared with state-of-the-art decentralized SGD variants, WAGMA-SGD significantly improves training throughput (e.g., 2.1× on 1,024 GPUs for reinforcement learning), and achieves the fastest time-to-solution (e.g., the highest score using the shortest training time for Transformer)."}],"isi":1,"project":[{"call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425","name":"Elastic Coordination for Scalable Machine Learning","grant_number":"805223"}],"year":"2021","publication_status":"published","scopus_import":"1","oa_version":"Preprint","date_updated":"2025-07-10T12:01:23Z","publication_identifier":{"issn":["1045-9219"]},"month":"07","quality_controlled":"1","article_type":"original","external_id":{"arxiv":["2005.00124"],"isi":["000621405200019"]},"type":"journal_article","volume":32,"doi":"10.1109/TPDS.2020.3040606","citation":{"short":"S. Li, T.B.-N. Tal Ben-Nun, G. Nadiradze, S.D. Girolamo, N. Dryden, D.-A. Alistarh, T. Hoefler, IEEE Transactions on Parallel and Distributed Systems 32 (2021).","ista":"Li S, Tal Ben-Nun TB-N, Nadiradze G, Girolamo SD, Dryden N, Alistarh D-A, Hoefler T. 2021. Breaking (global) barriers in parallel stochastic optimization with wait-avoiding group averaging. IEEE Transactions on Parallel and Distributed Systems. 32(7), 9271898.","ieee":"S. Li <i>et al.</i>, “Breaking (global) barriers in parallel stochastic optimization with wait-avoiding group averaging,” <i>IEEE Transactions on Parallel and Distributed Systems</i>, vol. 32, no. 7. IEEE, 2021.","chicago":"Li, Shigang, Tal Ben-Nun Tal Ben-Nun, Giorgi Nadiradze, Salvatore Di Girolamo, Nikoli Dryden, Dan-Adrian Alistarh, and Torsten Hoefler. “Breaking (Global) Barriers in Parallel Stochastic Optimization with Wait-Avoiding Group Averaging.” <i>IEEE Transactions on Parallel and Distributed Systems</i>. IEEE, 2021. <a href=\"https://doi.org/10.1109/TPDS.2020.3040606\">https://doi.org/10.1109/TPDS.2020.3040606</a>.","ama":"Li S, Tal Ben-Nun TB-N, Nadiradze G, et al. Breaking (global) barriers in parallel stochastic optimization with wait-avoiding group averaging. <i>IEEE Transactions on Parallel and Distributed Systems</i>. 2021;32(7). doi:<a href=\"https://doi.org/10.1109/TPDS.2020.3040606\">10.1109/TPDS.2020.3040606</a>","apa":"Li, S., Tal Ben-Nun, T. B.-N., Nadiradze, G., Girolamo, S. D., Dryden, N., Alistarh, D.-A., &#38; Hoefler, T. (2021). Breaking (global) barriers in parallel stochastic optimization with wait-avoiding group averaging. <i>IEEE Transactions on Parallel and Distributed Systems</i>. IEEE. <a href=\"https://doi.org/10.1109/TPDS.2020.3040606\">https://doi.org/10.1109/TPDS.2020.3040606</a>","mla":"Li, Shigang, et al. “Breaking (Global) Barriers in Parallel Stochastic Optimization with Wait-Avoiding Group Averaging.” <i>IEEE Transactions on Parallel and Distributed Systems</i>, vol. 32, no. 7, 9271898, IEEE, 2021, doi:<a href=\"https://doi.org/10.1109/TPDS.2020.3040606\">10.1109/TPDS.2020.3040606</a>."},"publisher":"IEEE","intvolume":"        32","issue":"7","article_number":"9271898","article_processing_charge":"No","date_published":"2021-07-01T00:00:00Z","day":"01","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2005.00124"}],"ec_funded":1,"author":[{"full_name":"Li, Shigang","first_name":"Shigang","last_name":"Li"},{"full_name":"Tal Ben-Nun, Tal Ben-Nun","first_name":"Tal Ben-Nun","last_name":"Tal Ben-Nun"},{"full_name":"Nadiradze, Giorgi","first_name":"Giorgi","last_name":"Nadiradze","id":"3279A00C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-5634-0731"},{"first_name":"Salvatore Di","last_name":"Girolamo","full_name":"Girolamo, Salvatore Di"},{"full_name":"Dryden, Nikoli","first_name":"Nikoli","last_name":"Dryden"},{"full_name":"Alistarh, Dan-Adrian","first_name":"Dan-Adrian","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X"},{"full_name":"Hoefler, Torsten","first_name":"Torsten","last_name":"Hoefler"}],"department":[{"_id":"DaAl"}],"acknowledgement":"This project has received funding from the European Research Council (ERC) under the European Union’s Hori-\r\nzon 2020 programme under Grant DAPP, Grant 678880; EPi-GRAM-HS, Grant 801039; and ERC Starting Grant ScaleML, Grant 805223. The work of Tal Ben-Nun is supported by the Swiss National Science Foundation (Ambizione Project No. 185778). The work of Nikoli Dryden is supported by the ETH Postdoctoral Fellowship. The authors would like to thank the Swiss National Supercomputing Center for providing the computing resources and technical support.","arxiv":1,"publication":"IEEE Transactions on Parallel and Distributed Systems","language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"month":"06","quality_controlled":"1","article_type":"original","publication_identifier":{"eissn":["1549-6333"],"issn":["1549-6325"]},"has_accepted_license":"1","volume":17,"doi":"10.1145/3451992","external_id":{"isi":["000661311300006"],"arxiv":["1912.05390"]},"type":"journal_article","article_number":"16","file_date_updated":"2021-06-10T19:33:56Z","article_processing_charge":"No","date_published":"2021-06-01T00:00:00Z","main_file_link":[{"url":"https://arxiv.org/abs/1912.05390","open_access":"1"}],"day":"01","citation":{"short":"A. Czumaj, P. Davies, M. Parter, ACM Transactions on Algorithms 17 (2021).","ieee":"A. Czumaj, P. Davies, and M. Parter, “Graph sparsification for derandomizing massively parallel computation with low space,” <i>ACM Transactions on Algorithms</i>, vol. 17, no. 2. Association for Computing Machinery, 2021.","chicago":"Czumaj, Artur, Peter Davies, and Merav Parter. “Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space.” <i>ACM Transactions on Algorithms</i>. Association for Computing Machinery, 2021. <a href=\"https://doi.org/10.1145/3451992\">https://doi.org/10.1145/3451992</a>.","ista":"Czumaj A, Davies P, Parter M. 2021. Graph sparsification for derandomizing massively parallel computation with low space. ACM Transactions on Algorithms. 17(2), 16.","ama":"Czumaj A, Davies P, Parter M. Graph sparsification for derandomizing massively parallel computation with low space. <i>ACM Transactions on Algorithms</i>. 2021;17(2). doi:<a href=\"https://doi.org/10.1145/3451992\">10.1145/3451992</a>","apa":"Czumaj, A., Davies, P., &#38; Parter, M. (2021). Graph sparsification for derandomizing massively parallel computation with low space. <i>ACM Transactions on Algorithms</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3451992\">https://doi.org/10.1145/3451992</a>","mla":"Czumaj, Artur, et al. “Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space.” <i>ACM Transactions on Algorithms</i>, vol. 17, no. 2, 16, Association for Computing Machinery, 2021, doi:<a href=\"https://doi.org/10.1145/3451992\">10.1145/3451992</a>."},"publisher":"Association for Computing Machinery","file":[{"date_created":"2021-06-10T19:33:56Z","file_id":"9542","file_name":"MISMM-arxiv.pdf","creator":"pdavies","date_updated":"2021-06-10T19:33:56Z","success":1,"content_type":"application/pdf","access_level":"open_access","file_size":587404,"relation":"main_file","checksum":"a21c627683890c309a68f6389302c408"}],"intvolume":"        17","issue":"2","arxiv":1,"ddc":["000"],"language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"ACM Transactions on Algorithms","ec_funded":1,"author":[{"full_name":"Czumaj, Artur","last_name":"Czumaj","first_name":"Artur"},{"first_name":"Peter","last_name":"Davies","full_name":"Davies, Peter","orcid":"0000-0002-5646-9524","id":"11396234-BB50-11E9-B24C-90FCE5697425"},{"full_name":"Parter, Merav","first_name":"Merav","last_name":"Parter"}],"department":[{"_id":"DaAl"}],"acknowledgement":"Institute of Science and Technology Austria (IST Austria). Email: peter.davies@ist.ac.at. Work partially\r\ndone at the Department of Computer Science and Centre for Discrete Mathematics and its Applications (DIMAP),University of Warwick. Research partially supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 754411, the Centre for Discrete Mathematics and its Applications, a Weizmann-UK Making Connections Grant, and EPSRC award EP/N011163/1.","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"7802"}]},"oa":1,"date_created":"2021-06-10T19:31:05Z","abstract":[{"text":"The Massively Parallel Computation (MPC) model is an emerging model that distills core aspects of distributed and parallel computation, developed as a tool to solve combinatorial (typically graph) problems in systems of many machines with limited space. Recent work has focused on the regime in which machines have sublinear (in n, the number of nodes in the input graph) space, with randomized algorithms presented for the fundamental problems of Maximal Matching and Maximal Independent Set. However, there have been no prior corresponding deterministic algorithms. A major challenge underlying the sublinear space setting is that the local space of each machine might be too small to store all edges incident to a single node. This poses a considerable obstacle compared to classical models in which each node is assumed to know and have easy access to its incident edges. To overcome this barrier, we introduce a new graph sparsification technique that deterministically computes a low-degree subgraph, with the additional property that solving the problem on this subgraph provides significant progress towards solving the problem for the original input graph. Using this framework to derandomize the well-known algorithm of Luby [SICOMP’86], we obtain O(log Δ + log log n)-round deterministic MPC algorithms for solving the problems of Maximal Matching and Maximal Independent Set with O(nɛ) space on each machine for any constant ɛ > 0. These algorithms also run in O(log Δ) rounds in the closely related model of CONGESTED CLIQUE, improving upon the state-of-the-art bound of O(log 2Δ) rounds by Censor-Hillel et al. [DISC’17].","lang":"eng"}],"title":"Graph sparsification for derandomizing massively parallel computation with low space","status":"public","_id":"9541","isi":1,"publication_status":"published","project":[{"call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411"}],"year":"2021","date_updated":"2025-04-15T06:54:47Z","oa_version":"Submitted Version","scopus_import":"1"},{"conference":{"start_date":"2021-05-03","location":"Virtual","end_date":"2021-05-07","name":"ICLR: International Conference on Learning Representations"},"arxiv":1,"date_updated":"2026-06-18T19:53:18Z","publication":"9th International Conference on Learning Representations","ddc":["000"],"language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"DaAl"}],"oa_version":"Published Version","ec_funded":1,"author":[{"orcid":"0000-0002-5646-9524","id":"11396234-BB50-11E9-B24C-90FCE5697425","last_name":"Davies","first_name":"Peter","full_name":"Davies, Peter"},{"full_name":"Gurunanthan, Vijaykrishna","first_name":"Vijaykrishna","last_name":"Gurunanthan"},{"full_name":"Moshrefi, Niusha ","last_name":"Moshrefi","first_name":"Niusha ","id":"4db776ff-ce15-11eb-96e3-bc2b90b01c16"},{"id":"0D0A9058-257B-11EA-A937-9341C3D8BC8A","full_name":"Ashkboos, Saleh","first_name":"Saleh","last_name":"Ashkboos"},{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","first_name":"Dan-Adrian"}],"article_processing_charge":"No","day":"01","main_file_link":[{"open_access":"1","url":"https://openreview.net/pdf?id=t86MwoUCCNe"}],"date_published":"2021-05-01T00:00:00Z","publication_status":"published","year":"2021","citation":{"mla":"Davies, Peter, et al. “New Bounds for Distributed Mean Estimation and Variance Reduction.” <i>9th International Conference on Learning Representations</i>, 2021.","apa":"Davies, P., Gurunanthan, V., Moshrefi, N., Ashkboos, S., &#38; Alistarh, D.-A. (2021). New bounds for distributed mean estimation and variance reduction. In <i>9th International Conference on Learning Representations</i>. Virtual.","short":"P. Davies, V. Gurunanthan, N. Moshrefi, S. Ashkboos, D.-A. Alistarh, in:, 9th International Conference on Learning Representations, 2021.","ama":"Davies P, Gurunanthan V, Moshrefi N, Ashkboos S, Alistarh D-A. New bounds for distributed mean estimation and variance reduction. In: <i>9th International Conference on Learning Representations</i>. ; 2021.","ista":"Davies P, Gurunanthan V, Moshrefi N, Ashkboos S, Alistarh D-A. 2021. New bounds for distributed mean estimation and variance reduction. 9th International Conference on Learning Representations. ICLR: International Conference on Learning Representations.","chicago":"Davies, Peter, Vijaykrishna Gurunanthan, Niusha  Moshrefi, Saleh Ashkboos, and Dan-Adrian Alistarh. “New Bounds for Distributed Mean Estimation and Variance Reduction.” In <i>9th International Conference on Learning Representations</i>, 2021.","ieee":"P. Davies, V. Gurunanthan, N. Moshrefi, S. Ashkboos, and D.-A. Alistarh, “New bounds for distributed mean estimation and variance reduction,” in <i>9th International Conference on Learning Representations</i>, Virtual, 2021."},"project":[{"name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"corr_author":"1","external_id":{"arxiv":["2002.09268"]},"type":"conference","oa":1,"date_created":"2021-06-10T19:46:08Z","month":"05","quality_controlled":"1","abstract":[{"lang":"eng","text":"We consider the problem ofdistributed mean estimation (DME), in which n machines are each given a local d-dimensional vector xv∈Rd, and must cooperate to estimate the mean of their inputs μ=1n∑nv=1xv, while minimizing total communication cost. DME is a fundamental construct in distributed machine learning, and there has been considerable work on variants of this problem, especially in the context of distributed variance reduction for stochastic gradients in parallel SGD. Previous work typically assumes an upper bound on the norm of the input vectors, and achieves an error bound in terms of this norm. However, in many real applications, the input vectors are concentrated around the correct output μ, but μ itself has large norm. In such cases, previous output error bounds perform poorly. In this paper, we show that output error bounds need not depend on input norm. We provide a method of quantization which allows distributed mean estimation to be performed with solution quality dependent only on the distance between inputs, not on input norm, and show an analogous result for distributed variance reduction. The technique is based on a new connection with lattice theory. We also provide lower bounds showing that the communication to error trade-off of our algorithms is asymptotically optimal. As the lattices achieving optimal bounds under l2-norm can be computationally impractical, we also present an extension which leverages easy-to-use cubic lattices, and is loose only up to a logarithmic factor ind. We show experimentally that our method yields practical improvements for common applications, relative to prior approaches."}],"_id":"9543","status":"public","title":"New bounds for distributed mean estimation and variance reduction"},{"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"arxiv":1,"ddc":["000"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"Journal of Machine Learning Research","language":[{"iso":"eng"}],"department":[{"_id":"DaAl"}],"author":[{"last_name":"Ramezani-Kebrya","first_name":"Ali","full_name":"Ramezani-Kebrya, Ali"},{"first_name":"Fartash","last_name":"Faghri","full_name":"Faghri, Fartash"},{"first_name":"Ilya","last_name":"Markov","full_name":"Markov, Ilya"},{"full_name":"Aksenov, Vitalii","first_name":"Vitalii","last_name":"Aksenov","id":"2980135A-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X"},{"last_name":"Roy","first_name":"Daniel M.","full_name":"Roy, Daniel M."}],"article_processing_charge":"No","day":"01","main_file_link":[{"open_access":"1","url":"https://www.jmlr.org/papers/v22/20-255.html"}],"date_published":"2021-04-01T00:00:00Z","file_date_updated":"2021-06-23T07:09:41Z","intvolume":"        22","issue":"114","citation":{"mla":"Ramezani-Kebrya, Ali, et al. “NUQSGD: Provably Communication-Efficient Data-Parallel SGD via Nonuniform Quantization.” <i>Journal of Machine Learning Research</i>, vol. 22, no. 114, Journal of Machine Learning Research, 2021, p. 1−43.","apa":"Ramezani-Kebrya, A., Faghri, F., Markov, I., Aksenov, V., Alistarh, D.-A., &#38; Roy, D. M. (2021). NUQSGD: Provably communication-efficient data-parallel SGD via nonuniform quantization. <i>Journal of Machine Learning Research</i>. Journal of Machine Learning Research.","short":"A. Ramezani-Kebrya, F. Faghri, I. Markov, V. Aksenov, D.-A. Alistarh, D.M. Roy, Journal of Machine Learning Research 22 (2021) 1−43.","ama":"Ramezani-Kebrya A, Faghri F, Markov I, Aksenov V, Alistarh D-A, Roy DM. NUQSGD: Provably communication-efficient data-parallel SGD via nonuniform quantization. <i>Journal of Machine Learning Research</i>. 2021;22(114):1−43.","ista":"Ramezani-Kebrya A, Faghri F, Markov I, Aksenov V, Alistarh D-A, Roy DM. 2021. NUQSGD: Provably communication-efficient data-parallel SGD via nonuniform quantization. Journal of Machine Learning Research. 22(114), 1−43.","chicago":"Ramezani-Kebrya, Ali, Fartash Faghri, Ilya Markov, Vitalii Aksenov, Dan-Adrian Alistarh, and Daniel M. Roy. “NUQSGD: Provably Communication-Efficient Data-Parallel SGD via Nonuniform Quantization.” <i>Journal of Machine Learning Research</i>. Journal of Machine Learning Research, 2021.","ieee":"A. Ramezani-Kebrya, F. Faghri, I. Markov, V. Aksenov, D.-A. Alistarh, and D. M. Roy, “NUQSGD: Provably communication-efficient data-parallel SGD via nonuniform quantization,” <i>Journal of Machine Learning Research</i>, vol. 22, no. 114. Journal of Machine Learning Research, p. 1−43, 2021."},"file":[{"date_updated":"2021-06-23T07:09:41Z","content_type":"application/pdf","success":1,"file_size":11237154,"access_level":"open_access","relation":"main_file","checksum":"6428aa8bcb67768b6949c99b55d5281d","date_created":"2021-06-23T07:09:41Z","file_name":"2021_JournalOfMachineLearningResearch_Ramezani-Kebrya.pdf","creator":"asandaue","file_id":"9595"}],"publisher":"Journal of Machine Learning Research","volume":22,"has_accepted_license":"1","external_id":{"arxiv":["1908.06077"]},"type":"journal_article","article_type":"original","month":"04","quality_controlled":"1","publication_identifier":{"eissn":["1533-7928"],"issn":["1532-4435"]},"date_updated":"2025-07-10T12:01:54Z","oa_version":"Published Version","scopus_import":"1","publication_status":"published","page":"1−43","year":"2021","corr_author":"1","oa":1,"date_created":"2021-06-20T22:01:33Z","abstract":[{"text":"As the size and complexity of models and datasets grow, so does the need for communication-efficient variants of stochastic gradient descent that can be deployed to perform parallel model training. One popular communication-compression method for data-parallel SGD is QSGD (Alistarh et al., 2017), which quantizes and encodes gradients to reduce communication costs. The baseline variant of QSGD provides strong theoretical guarantees, however, for practical purposes, the authors proposed a heuristic variant which we call QSGDinf, which demonstrated impressive empirical gains for distributed training of large neural networks. In this paper, we build on this work to propose a new gradient quantization scheme, and show that it has both stronger theoretical guarantees than QSGD, and matches and exceeds the empirical performance of the QSGDinf heuristic and of other compression methods.","lang":"eng"}],"status":"public","_id":"9571","title":"NUQSGD: Provably communication-efficient data-parallel SGD via nonuniform quantization"},{"language":[{"iso":"eng"}],"publication":"Structural Information and Communication Complexity","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","ddc":["000"],"acknowledgement":"Peter Davies is supported by the European Union’s Horizon2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 754411.","department":[{"_id":"DaAl"}],"author":[{"orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","last_name":"Alistarh","full_name":"Alistarh, Dan-Adrian"},{"orcid":"0000-0002-5646-9524","id":"11396234-BB50-11E9-B24C-90FCE5697425","first_name":"Peter","last_name":"Davies","full_name":"Davies, Peter"}],"ec_funded":1,"date_published":"2021-06-20T00:00:00Z","day":"20","article_processing_charge":"No","file_date_updated":"2021-07-01T11:21:40Z","intvolume":"     12810","file":[{"relation":"main_file","checksum":"fe37fb9af3f5016c1084af9d6e7109bd","file_size":319728,"access_level":"open_access","date_updated":"2021-07-01T11:21:40Z","content_type":"application/pdf","file_name":"Population_Coupon_Collector.pdf","creator":"pdavies","file_id":"9621","date_created":"2021-07-01T11:21:40Z"}],"publisher":"Springer Nature","citation":{"short":"D.-A. Alistarh, P. Davies, in:, Structural Information and Communication Complexity, Springer Nature, 2021, pp. 3–12.","ama":"Alistarh D-A, Davies P. Collecting coupons is faster with friends. In: <i>Structural Information and Communication Complexity</i>. Vol 12810. Springer Nature; 2021:3-12. doi:<a href=\"https://doi.org/10.1007/978-3-030-79527-6_1\">10.1007/978-3-030-79527-6_1</a>","chicago":"Alistarh, Dan-Adrian, and Peter Davies. “Collecting Coupons Is Faster with Friends.” In <i>Structural Information and Communication Complexity</i>, 12810:3–12. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-79527-6_1\">https://doi.org/10.1007/978-3-030-79527-6_1</a>.","ista":"Alistarh D-A, Davies P. 2021. Collecting coupons is faster with friends. Structural Information and Communication Complexity. SIROCCO: International Colloquium on Structural Information and Communication Complexity, LNCS, vol. 12810, 3–12.","ieee":"D.-A. Alistarh and P. Davies, “Collecting coupons is faster with friends,” in <i>Structural Information and Communication Complexity</i>, Wrocław, Poland, 2021, vol. 12810, pp. 3–12.","mla":"Alistarh, Dan-Adrian, and Peter Davies. “Collecting Coupons Is Faster with Friends.” <i>Structural Information and Communication Complexity</i>, vol. 12810, Springer Nature, 2021, pp. 3–12, doi:<a href=\"https://doi.org/10.1007/978-3-030-79527-6_1\">10.1007/978-3-030-79527-6_1</a>.","apa":"Alistarh, D.-A., &#38; Davies, P. (2021). Collecting coupons is faster with friends. In <i>Structural Information and Communication Complexity</i> (Vol. 12810, pp. 3–12). Wrocław, Poland: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-79527-6_1\">https://doi.org/10.1007/978-3-030-79527-6_1</a>"},"doi":"10.1007/978-3-030-79527-6_1","volume":12810,"has_accepted_license":"1","type":"conference","external_id":{"isi":["001292788400001"]},"quality_controlled":"1","month":"06","publication_identifier":{"eisbn":["9783030795276"],"isbn":["9783030795269"],"eissn":["1611-3349"],"issn":["0302-9743"]},"alternative_title":["LNCS"],"conference":{"location":"Wrocław, Poland","start_date":"2021-06-28","end_date":"2021-07-01","name":"SIROCCO: International Colloquium on Structural Information and Communication Complexity"},"date_updated":"2025-09-10T10:04:46Z","oa_version":"Preprint","scopus_import":"1","page":"3-12","publication_status":"published","year":"2021","project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships"}],"isi":1,"abstract":[{"text":"In this note, we introduce a distributed twist on the classic coupon collector problem: a set of m collectors wish to each obtain a set of n coupons; for this, they can each sample coupons uniformly at random, but can also meet in pairwise interactions, during which they can exchange coupons. By doing so, they hope to reduce the number of coupons that must be sampled by each collector in order to obtain a full set. This extension is natural when considering real-world manifestations of the coupon collector phenomenon, and has been remarked upon and studied empirically (Hayes and Hannigan 2006, Ahmad et al. 2014, Delmarcelle 2019).\r\n\r\nWe provide the first theoretical analysis for such a scenario. We find that “coupon collecting with friends” can indeed significantly reduce the number of coupons each collector must sample, and raises interesting connections to the more traditional variants of the problem. While our analysis is in most cases asymptotically tight, there are several open questions raised, regarding finer-grained analysis of both “coupon collecting with friends,” and of a long-studied variant of the original problem in which a collector requires multiple full sets of coupons.","lang":"eng"}],"date_created":"2021-07-01T11:04:43Z","oa":1,"_id":"9620","status":"public","title":"Collecting coupons is faster with friends"}]