[{"oa":1,"page":"9037-9045","citation":{"ama":"Nadiradze G, Markov I, Chatterjee B, Kungurtsev V, Alistarh D-A. Elastic consistency: A practical consistency model for distributed stochastic gradient descent. In: <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>. Vol 35. ; 2021:9037-9045.","ista":"Nadiradze G, Markov I, Chatterjee B, Kungurtsev V, Alistarh D-A. 2021. Elastic consistency: A practical consistency model for distributed stochastic gradient descent. Proceedings of the AAAI Conference on Artificial Intelligence. AAAI: Association for the Advancement of Artificial Intelligence vol. 35, 9037–9045.","ieee":"G. Nadiradze, I. Markov, B. Chatterjee, V. Kungurtsev, and D.-A. Alistarh, “Elastic consistency: A practical consistency model for distributed stochastic gradient descent,” in <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>, Virtual, 2021, vol. 35, no. 10, pp. 9037–9045.","short":"G. Nadiradze, I. Markov, B. Chatterjee, V. Kungurtsev, D.-A. Alistarh, in:, Proceedings of the AAAI Conference on Artificial Intelligence, 2021, pp. 9037–9045.","mla":"Nadiradze, Giorgi, et al. “Elastic Consistency: A Practical Consistency Model for Distributed Stochastic Gradient Descent.” <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>, vol. 35, no. 10, 2021, pp. 9037–45.","apa":"Nadiradze, G., Markov, I., Chatterjee, B., Kungurtsev, V., &#38; Alistarh, D.-A. (2021). Elastic consistency: A practical consistency model for distributed stochastic gradient descent. In <i>Proceedings of the AAAI Conference on Artificial Intelligence</i> (Vol. 35, pp. 9037–9045). Virtual.","chicago":"Nadiradze, Giorgi, Ilia Markov, Bapi Chatterjee, Vyacheslav  Kungurtsev, and Dan-Adrian Alistarh. “Elastic Consistency: A Practical Consistency Model for Distributed Stochastic Gradient Descent.” In <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>, 35:9037–45, 2021."},"external_id":{"arxiv":["2001.05918"]},"issue":"10","publication":"Proceedings of the AAAI Conference on Artificial Intelligence","intvolume":"        35","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","related_material":{"record":[{"relation":"dissertation_contains","id":"10429","status":"public"}]},"main_file_link":[{"url":"https://ojs.aaai.org/index.php/AAAI/article/view/17092","open_access":"1"}],"date_published":"2021-05-18T00:00:00Z","article_processing_charge":"No","project":[{"name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425"},{"grant_number":"805223","call_identifier":"H2020","name":"Elastic Coordination for Scalable Machine Learning","_id":"268A44D6-B435-11E9-9278-68D0E5697425"}],"_id":"10432","day":"18","department":[{"_id":"DaAl"}],"date_updated":"2023-09-07T13:31:39Z","language":[{"iso":"eng"}],"conference":{"name":"AAAI: Association for the Advancement of Artificial Intelligence","location":"Virtual","end_date":"2021-02-09","start_date":"2021-02-02"},"abstract":[{"text":"One key element behind the recent progress of machine learning has been the ability to train machine learning models in large-scale distributed shared-memory and message-passing environments. Most of these models are trained employing variants of stochastic gradient descent (SGD) based optimization, but most methods involve some type of consistency relaxation relative to sequential SGD, to mitigate its large communication or synchronization costs at scale. In this paper, we introduce a general consistency condition covering communication-reduced and asynchronous distributed SGD implementations. Our framework, called elastic consistency, decouples the system-specific aspects of the implementation from the SGD convergence requirements, giving a general way to obtain convergence bounds for a wide variety of distributed SGD methods used in practice. Elastic consistency can be used to re-derive or improve several previous convergence bounds in message-passing and shared-memory settings, but also to analyze new models and distribution schemes. As a direct application, we propose and analyze a new synchronization-avoiding scheduling scheme for distributed SGD, and show that it can be used to efficiently train deep convolutional models for image classification.","lang":"eng"}],"author":[{"first_name":"Giorgi","orcid":"0000-0001-5634-0731","last_name":"Nadiradze","full_name":"Nadiradze, Giorgi","id":"3279A00C-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Ilia","last_name":"Markov","full_name":"Markov, Ilia","id":"D0CF4148-C985-11E9-8066-0BDEE5697425"},{"first_name":"Bapi","id":"3C41A08A-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Bapi","last_name":"Chatterjee","orcid":"0000-0002-2742-4028"},{"first_name":"Vyacheslav ","full_name":"Kungurtsev, Vyacheslav ","last_name":"Kungurtsev"},{"first_name":"Dan-Adrian","last_name":"Alistarh","full_name":"Alistarh, Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X"}],"volume":35,"quality_controlled":"1","ec_funded":1,"status":"public","acknowledgement":"We would like to thank Christopher De Sa for his feedback on an earlier draft of this paper, as well as the anonymous AAAI reviewers for their useful comments. This project has received\r\nfunding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML). Bapi\r\nChatterjee was supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No. 754411 (ISTPlus).","arxiv":1,"title":"Elastic consistency: A practical consistency model for distributed stochastic gradient descent","date_created":"2021-12-09T09:21:35Z","year":"2021","month":"05","oa_version":"Published Version","type":"conference","publication_status":"published"},{"oa":1,"citation":{"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.","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.","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.","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.","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.","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."},"publication":"35th Conference on Neural Information Processing Systems","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["1910.12308"]},"main_file_link":[{"open_access":"1","url":"https://papers.nips.cc/paper/2021/hash/362c99307cdc3f2d8b410652386a9dd1-Abstract.html"}],"date_published":"2021-12-01T00:00:00Z","related_material":{"record":[{"id":"10429","relation":"dissertation_contains","status":"public"}]},"department":[{"_id":"DaAl"}],"date_updated":"2023-10-17T11:48:56Z","language":[{"iso":"eng"}],"article_processing_charge":"No","project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020"},{"_id":"268A44D6-B435-11E9-9278-68D0E5697425","name":"Elastic Coordination for Scalable Machine Learning","call_identifier":"H2020","grant_number":"805223"}],"day":"01","_id":"10435","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."}],"author":[{"first_name":"Giorgi","id":"3279A00C-F248-11E8-B48F-1D18A9856A87","last_name":"Nadiradze","full_name":"Nadiradze, Giorgi","orcid":"0000-0001-5634-0731"},{"first_name":"Amirmojtaba","last_name":"Sabour","full_name":"Sabour, Amirmojtaba","id":"bcc145fd-e77f-11ea-ae8b-80d661dbff67"},{"first_name":"Peter","orcid":"0000-0002-5646-9524","id":"11396234-BB50-11E9-B24C-90FCE5697425","last_name":"Davies","full_name":"Davies, Peter"},{"first_name":"Shigang","full_name":"Li, Shigang","last_name":"Li"},{"first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh"}],"publisher":"Neural Information Processing Systems Foundation","conference":{"name":"NeurIPS: Neural Information Processing Systems","end_date":"2021-12-14","location":"Sydney, Australia","start_date":"2021-12-06"},"ec_funded":1,"status":"public","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","quality_controlled":"1","year":"2021","month":"12","arxiv":1,"title":"Asynchronous decentralized SGD with quantized and local updates","date_created":"2021-12-09T10:59:12Z","type":"conference","publication_status":"published","oa_version":"Published Version"},{"oa_version":"Submitted Version","type":"journal_article","publication_status":"published","article_type":"original","arxiv":1,"title":"Graph sparsification for derandomizing massively parallel computation with low space","has_accepted_license":"1","date_created":"2021-06-10T19:31:05Z","year":"2021","month":"06","isi":1,"doi":"10.1145/3451992","quality_controlled":"1","volume":17,"ddc":["000"],"ec_funded":1,"status":"public","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.","publication_identifier":{"eissn":["1549-6333"],"issn":["1549-6325"]},"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"}],"publisher":"Association for Computing Machinery","article_number":"16","author":[{"first_name":"Artur","last_name":"Czumaj","full_name":"Czumaj, Artur"},{"first_name":"Peter","id":"11396234-BB50-11E9-B24C-90FCE5697425","last_name":"Davies","full_name":"Davies, Peter","orcid":"0000-0002-5646-9524"},{"first_name":"Merav","full_name":"Parter, Merav","last_name":"Parter"}],"article_processing_charge":"No","project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships"}],"_id":"9541","day":"01","department":[{"_id":"DaAl"}],"date_updated":"2024-02-28T12:53:09Z","language":[{"iso":"eng"}],"file":[{"access_level":"open_access","checksum":"a21c627683890c309a68f6389302c408","date_created":"2021-06-10T19:33:56Z","file_id":"9542","file_name":"MISMM-arxiv.pdf","creator":"pdavies","success":1,"content_type":"application/pdf","relation":"main_file","date_updated":"2021-06-10T19:33:56Z","file_size":587404}],"related_material":{"record":[{"relation":"earlier_version","id":"7802","status":"public"}]},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1912.05390"}],"date_published":"2021-06-01T00:00:00Z","external_id":{"isi":["000661311300006"],"arxiv":["1912.05390"]},"issue":"2","publication":"ACM Transactions on Algorithms","intvolume":"        17","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2021-06-10T19:33:56Z","oa":1,"citation":{"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>.","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>.","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.","short":"A. Czumaj, P. Davies, M. Parter, ACM Transactions on Algorithms 17 (2021).","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>","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."}},{"year":"2021","main_file_link":[{"url":"https://openreview.net/pdf?id=t86MwoUCCNe","open_access":"1"}],"month":"05","date_published":"2021-05-01T00:00:00Z","arxiv":1,"date_created":"2021-06-10T19:46:08Z","title":"New bounds for distributed mean estimation and variance reduction","language":[{"iso":"eng"}],"department":[{"_id":"DaAl"}],"date_updated":"2023-02-23T14:00:40Z","type":"conference","publication_status":"published","article_processing_charge":"No","day":"01","_id":"9543","oa_version":"Published Version","project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411"}],"abstract":[{"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.","lang":"eng"}],"author":[{"first_name":"Peter","orcid":"0000-0002-5646-9524","id":"11396234-BB50-11E9-B24C-90FCE5697425","full_name":"Davies, Peter","last_name":"Davies"},{"first_name":"Vijaykrishna","full_name":"Gurunanthan, Vijaykrishna","last_name":"Gurunanthan"},{"first_name":"Niusha ","full_name":"Moshrefi, Niusha ","last_name":"Moshrefi","id":"4db776ff-ce15-11eb-96e3-bc2b90b01c16"},{"first_name":"Saleh","full_name":"Ashkboos, Saleh","last_name":"Ashkboos","id":"0D0A9058-257B-11EA-A937-9341C3D8BC8A"},{"first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"}],"conference":{"location":"Virtual","name":" ICLR: International Conference on Learning Representations","end_date":"2021-05-07","start_date":"2021-05-03"},"citation":{"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.","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.","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.","short":"P. Davies, V. Gurunanthan, N. Moshrefi, S. Ashkboos, D.-A. Alistarh, in:, 9th International Conference on Learning Representations, 2021.","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.","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."},"oa":1,"ec_funded":1,"user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","publication":"9th International Conference on Learning Representations","status":"public","external_id":{"arxiv":["2002.09268"]},"quality_controlled":"1"},{"department":[{"_id":"DaAl"}],"date_updated":"2024-03-06T12:22:07Z","language":[{"iso":"eng"}],"_id":"9571","day":"01","article_processing_charge":"No","date_published":"2021-04-01T00:00:00Z","main_file_link":[{"url":"https://www.jmlr.org/papers/v22/20-255.html","open_access":"1"}],"file":[{"relation":"main_file","date_updated":"2021-06-23T07:09:41Z","file_size":11237154,"date_created":"2021-06-23T07:09:41Z","checksum":"6428aa8bcb67768b6949c99b55d5281d","access_level":"open_access","creator":"asandaue","file_name":"2021_JournalOfMachineLearningResearch_Ramezani-Kebrya.pdf","file_id":"9595","success":1,"content_type":"application/pdf"}],"intvolume":"        22","publication":"Journal of Machine Learning Research","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","issue":"114","external_id":{"arxiv":["1908.06077"]},"oa":1,"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"citation":{"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.","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.","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.","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.","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.","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."},"page":"1−43","file_date_updated":"2021-06-23T07:09:41Z","publication_status":"published","type":"journal_article","oa_version":"Published Version","month":"04","year":"2021","has_accepted_license":"1","date_created":"2021-06-20T22:01:33Z","title":"NUQSGD: Provably communication-efficient data-parallel SGD via nonuniform quantization","article_type":"original","arxiv":1,"status":"public","quality_controlled":"1","volume":22,"ddc":["000"],"author":[{"full_name":"Ramezani-Kebrya, Ali","last_name":"Ramezani-Kebrya","first_name":"Ali"},{"first_name":"Fartash","last_name":"Faghri","full_name":"Faghri, Fartash"},{"first_name":"Ilya","full_name":"Markov, Ilya","last_name":"Markov"},{"first_name":"Vitalii","full_name":"Aksenov, Vitalii","last_name":"Aksenov","id":"2980135A-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X","first_name":"Dan-Adrian"},{"first_name":"Daniel M.","full_name":"Roy, Daniel M.","last_name":"Roy"}],"publisher":"Journal of Machine Learning Research","abstract":[{"lang":"eng","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."}],"publication_identifier":{"eissn":["15337928"],"issn":["15324435"]},"scopus_import":"1"},{"quality_controlled":"1","volume":12810,"doi":"10.1007/978-3-030-79527-6_1","ddc":["000"],"status":"public","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.","ec_funded":1,"publication_identifier":{"eissn":["1611-3349"],"isbn":["9783030795269"],"eisbn":["9783030795276"],"issn":["0302-9743"]},"conference":{"start_date":"2021-06-28","end_date":"2021-07-01","name":" SIROCCO: International Colloquium on Structural Information and Communication Complexity","location":"Wrocław, Poland"},"publisher":"Springer Nature","author":[{"first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh"},{"orcid":"0000-0002-5646-9524","id":"11396234-BB50-11E9-B24C-90FCE5697425","last_name":"Davies","full_name":"Davies, Peter","first_name":"Peter"}],"abstract":[{"lang":"eng","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."}],"oa_version":"Preprint","publication_status":"published","type":"conference","title":"Collecting coupons is faster with friends","has_accepted_license":"1","date_created":"2021-07-01T11:04:43Z","month":"06","year":"2021","alternative_title":["LNCS"],"publication":"Structural Information and Communication Complexity","intvolume":"     12810","user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","oa":1,"page":"3-12","citation":{"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>","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.","short":"D.-A. Alistarh, P. Davies, in:, Structural Information and Communication Complexity, Springer Nature, 2021, pp. 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>","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>."},"file_date_updated":"2021-07-01T11:21:40Z","project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020"}],"day":"20","_id":"9620","article_processing_charge":"No","date_updated":"2023-02-23T14:02:46Z","department":[{"_id":"DaAl"}],"language":[{"iso":"eng"}],"file":[{"date_updated":"2021-07-01T11:21:40Z","relation":"main_file","file_size":319728,"creator":"pdavies","file_name":"Population_Coupon_Collector.pdf","file_id":"9621","content_type":"application/pdf","date_created":"2021-07-01T11:21:40Z","checksum":"fe37fb9af3f5016c1084af9d6e7109bd","access_level":"open_access"}],"date_published":"2021-06-20T00:00:00Z"},{"publication_status":"published","type":"conference","oa_version":"Preprint","month":"07","year":"2021","date_created":"2021-07-18T22:01:22Z","title":"Efficient load-balancing through distributed token dropping","arxiv":1,"acknowledgement":"We thank Orr Fischer, Juho Hirvonen, and Tuomo Lempiäinen for valuable discussions. 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.","status":"public","ec_funded":1,"quality_controlled":"1","doi":"10.1145/3409964.3461785","author":[{"full_name":"Brandt, Sebastian","last_name":"Brandt","first_name":"Sebastian"},{"first_name":"Barbara","full_name":"Keller, Barbara","last_name":"Keller"},{"last_name":"Rybicki","full_name":"Rybicki, Joel","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6432-6646","first_name":"Joel"},{"last_name":"Suomela","full_name":"Suomela, Jukka","first_name":"Jukka"},{"last_name":"Uitto","full_name":"Uitto, Jara","first_name":"Jara"}],"abstract":[{"lang":"eng","text":"We introduce a new graph problem, the token dropping game, and we show how to solve it efficiently in a distributed setting. We use the token dropping game as a tool to design an efficient distributed algorithm for stable orientations and more generally for locally optimal semi-matchings. The prior work by Czygrinow et al. (DISC 2012) finds a stable orientation in O(Δ^5) rounds in graphs of maximum degree Δ, while we improve it to O(Δ^4) and also prove a lower bound of Ω(Δ). For the more general problem of locally optimal semi-matchings, the prior upper bound is O(S^5) and our new algorithm runs in O(C · S^4) rounds, which is an improvement for C = o(S); here C and S are the maximum degrees of customers and servers, respectively."}],"scopus_import":"1","publication_identifier":{"isbn":["9781450380706"]},"conference":{"start_date":"2021-07-06","location":" Virtual Event, United States","name":"SPAA: Symposium on Parallelism in Algorithms and Architectures ","end_date":"2021-07-08"},"language":[{"iso":"eng"}],"department":[{"_id":"DaAl"}],"date_updated":"2024-03-05T07:13:12Z","_id":"9678","day":"06","project":[{"_id":"26A5D39A-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Coordination in constrained and natural distributed systems","grant_number":"840605"}],"article_processing_charge":"No","date_published":"2021-07-06T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2005.07761"}],"related_material":{"record":[{"status":"public","id":"15074","relation":"earlier_version"}]},"user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","publication":"Annual ACM Symposium on Parallelism in Algorithms and Architectures","external_id":{"arxiv":["2005.07761"]},"page":"129-139","citation":{"ista":"Brandt S, Keller B, Rybicki J, Suomela J, Uitto J. 2021. Efficient load-balancing through distributed token dropping. Annual ACM Symposium on Parallelism in Algorithms and Architectures. SPAA: Symposium on Parallelism in Algorithms and Architectures , 129–139.","ama":"Brandt S, Keller B, Rybicki J, Suomela J, Uitto J. Efficient load-balancing through distributed token dropping. In: <i>Annual ACM Symposium on Parallelism in Algorithms and Architectures</i>. ; 2021:129-139. doi:<a href=\"https://doi.org/10.1145/3409964.3461785\">10.1145/3409964.3461785</a>","short":"S. Brandt, B. Keller, J. Rybicki, J. Suomela, J. Uitto, in:, Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2021, pp. 129–139.","ieee":"S. Brandt, B. Keller, J. Rybicki, J. Suomela, and J. Uitto, “Efficient load-balancing through distributed token dropping,” in <i>Annual ACM Symposium on Parallelism in Algorithms and Architectures</i>,  Virtual Event, United States, 2021, pp. 129–139.","mla":"Brandt, Sebastian, et al. “Efficient Load-Balancing through Distributed Token Dropping.” <i>Annual ACM Symposium on Parallelism in Algorithms and Architectures</i>, 2021, pp. 129–39, doi:<a href=\"https://doi.org/10.1145/3409964.3461785\">10.1145/3409964.3461785</a>.","apa":"Brandt, S., Keller, B., Rybicki, J., Suomela, J., &#38; Uitto, J. (2021). Efficient load-balancing through distributed token dropping. In <i>Annual ACM Symposium on Parallelism in Algorithms and Architectures</i> (pp. 129–139).  Virtual Event, United States. <a href=\"https://doi.org/10.1145/3409964.3461785\">https://doi.org/10.1145/3409964.3461785</a>","chicago":"Brandt, Sebastian, Barbara Keller, Joel Rybicki, Jukka Suomela, and Jara Uitto. “Efficient Load-Balancing through Distributed Token Dropping.” In <i>Annual ACM Symposium on Parallelism in Algorithms and Architectures</i>, 129–39, 2021. <a href=\"https://doi.org/10.1145/3409964.3461785\">https://doi.org/10.1145/3409964.3461785</a>."},"oa":1},{"status":"public","volume":12810,"quality_controlled":"1","doi":"10.1007/978-3-030-79527-6_6","abstract":[{"lang":"eng","text":"Approximate agreement is one of the few variants of consensus that can be solved in a wait-free manner in asynchronous systems where processes communicate by reading and writing to shared memory. In this work, we consider a natural generalisation of approximate agreement on arbitrary undirected connected graphs. Each process is given a vertex of the graph as input and, if non-faulty, must output a vertex such that\r\nall the outputs are within distance 1 of one another, and\r\n\r\neach output value lies on a shortest path between two input values.\r\n\r\nFrom prior work, it is known that there is no wait-free algorithm among   𝑛≥3  processes for this problem on any cycle of length   𝑐≥4 , by reduction from 2-set agreement (Castañeda et al. 2018).\r\n\r\nIn this work, we investigate the solvability and complexity of this task on general graphs. We give a new, direct proof of the impossibility of approximate agreement on cycles of length   𝑐≥4 , via a generalisation of Sperner’s Lemma to convex polygons. We also extend the reduction from 2-set agreement to a larger class of graphs, showing that approximate agreement on these graphs is unsolvable. On the positive side, we present a wait-free algorithm for a class of graphs that properly contains the class of chordal graphs."}],"author":[{"first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh"},{"first_name":"Faith","full_name":"Ellen, Faith","last_name":"Ellen"},{"orcid":"0000-0002-6432-6646","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","full_name":"Rybicki, Joel","last_name":"Rybicki","first_name":"Joel"}],"publisher":"Springer Nature","conference":{"start_date":"2021-06-28","location":"Wrocław, Poland","name":"SIROCCO: Structural Information and Communication Complexity","end_date":"2021-07-01"},"scopus_import":"1","publication_identifier":{"isbn":["9783030795269"],"eissn":["16113349"],"issn":["03029743"]},"type":"conference","publication_status":"published","oa_version":"Preprint","year":"2021","month":"06","arxiv":1,"title":"Wait-free approximate agreement on graphs","date_created":"2021-08-08T22:01:29Z","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","intvolume":"     12810","publication":"Structural Information and Communication Complexity","external_id":{"arxiv":["2103.08949"]},"alternative_title":["LNCS"],"page":"87-105","citation":{"mla":"Alistarh, Dan-Adrian, et al. “Wait-Free Approximate Agreement on Graphs.” <i>Structural Information and Communication Complexity</i>, vol. 12810, Springer Nature, 2021, pp. 87–105, doi:<a href=\"https://doi.org/10.1007/978-3-030-79527-6_6\">10.1007/978-3-030-79527-6_6</a>.","apa":"Alistarh, D.-A., Ellen, F., &#38; Rybicki, J. (2021). Wait-free approximate agreement on graphs. In <i>Structural Information and Communication Complexity</i> (Vol. 12810, pp. 87–105). Wrocław, Poland: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-79527-6_6\">https://doi.org/10.1007/978-3-030-79527-6_6</a>","chicago":"Alistarh, Dan-Adrian, Faith Ellen, and Joel Rybicki. “Wait-Free Approximate Agreement on Graphs.” In <i>Structural Information and Communication Complexity</i>, 12810:87–105. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-79527-6_6\">https://doi.org/10.1007/978-3-030-79527-6_6</a>.","ista":"Alistarh D-A, Ellen F, Rybicki J. 2021. Wait-free approximate agreement on graphs. Structural Information and Communication Complexity. SIROCCO: Structural Information and Communication Complexity, LNCS, vol. 12810, 87–105.","ama":"Alistarh D-A, Ellen F, Rybicki J. Wait-free approximate agreement on graphs. In: <i>Structural Information and Communication Complexity</i>. Vol 12810. Springer Nature; 2021:87-105. doi:<a href=\"https://doi.org/10.1007/978-3-030-79527-6_6\">10.1007/978-3-030-79527-6_6</a>","ieee":"D.-A. Alistarh, F. Ellen, and J. Rybicki, “Wait-free approximate agreement on graphs,” in <i>Structural Information and Communication Complexity</i>, Wrocław, Poland, 2021, vol. 12810, pp. 87–105.","short":"D.-A. Alistarh, F. Ellen, J. Rybicki, in:, Structural Information and Communication Complexity, Springer Nature, 2021, pp. 87–105."},"oa":1,"language":[{"iso":"eng"}],"department":[{"_id":"DaAl"}],"date_updated":"2023-02-23T14:09:49Z","article_processing_charge":"No","day":"20","_id":"9823","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2103.08949"}],"date_published":"2021-06-20T00:00:00Z"},{"citation":{"chicago":"Chatterjee, Bapi, Ivan Walulya, and Philippas Tsigas. “Concurrent Linearizable Nearest Neighbour Search in LockFree-KD-Tree.” <i>Theoretical Computer Science</i>. Elsevier, 2021. <a href=\"https://doi.org/10.1016/j.tcs.2021.06.041\">https://doi.org/10.1016/j.tcs.2021.06.041</a>.","mla":"Chatterjee, Bapi, et al. “Concurrent Linearizable Nearest Neighbour Search in LockFree-KD-Tree.” <i>Theoretical Computer Science</i>, vol. 886, Elsevier, 2021, pp. 27–48, doi:<a href=\"https://doi.org/10.1016/j.tcs.2021.06.041\">10.1016/j.tcs.2021.06.041</a>.","apa":"Chatterjee, B., Walulya, I., &#38; Tsigas, P. (2021). Concurrent linearizable nearest neighbour search in LockFree-kD-tree. <i>Theoretical Computer Science</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.tcs.2021.06.041\">https://doi.org/10.1016/j.tcs.2021.06.041</a>","ieee":"B. Chatterjee, I. Walulya, and P. Tsigas, “Concurrent linearizable nearest neighbour search in LockFree-kD-tree,” <i>Theoretical Computer Science</i>, vol. 886. Elsevier, pp. 27–48, 2021.","short":"B. Chatterjee, I. Walulya, P. Tsigas, Theoretical Computer Science 886 (2021) 27–48.","ista":"Chatterjee B, Walulya I, Tsigas P. 2021. Concurrent linearizable nearest neighbour search in LockFree-kD-tree. Theoretical Computer Science. 886, 27–48.","ama":"Chatterjee B, Walulya I, Tsigas P. Concurrent linearizable nearest neighbour search in LockFree-kD-tree. <i>Theoretical Computer Science</i>. 2021;886:27-48. doi:<a href=\"https://doi.org/10.1016/j.tcs.2021.06.041\">10.1016/j.tcs.2021.06.041</a>"},"page":"27-48","oa":1,"external_id":{"isi":["000694718900004"]},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","keyword":["Concurrent data structure","kD-tree","Nearest neighbor search","Similarity search","Lock-free","Linearizability"],"intvolume":"       886","publication":"Theoretical Computer Science","date_published":"2021-09-13T00:00:00Z","main_file_link":[{"url":"https://publications.lib.chalmers.se/records/fulltext/232185/232185.pdf","open_access":"1"}],"day":"13","_id":"9827","article_processing_charge":"No","language":[{"iso":"eng"}],"date_updated":"2023-08-10T14:27:43Z","department":[{"_id":"DaAl"}],"publication_identifier":{"issn":["0304-3975"]},"scopus_import":"1","publisher":"Elsevier","author":[{"first_name":"Bapi","last_name":"Chatterjee","full_name":"Chatterjee, Bapi","id":"3C41A08A-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-2742-4028"},{"last_name":"Walulya","full_name":"Walulya, Ivan","first_name":"Ivan"},{"first_name":"Philippas","full_name":"Tsigas, Philippas","last_name":"Tsigas"}],"abstract":[{"text":"The Nearest neighbour search (NNS) is a fundamental problem in many application domains dealing with multidimensional data. In a concurrent setting, where dynamic modifications are allowed, a linearizable implementation of the NNS is highly desirable.This paper introduces the LockFree-kD-tree (LFkD-tree ): a lock-free concurrent kD-tree, which implements an abstract data type (ADT) that provides the operations Add, Remove, Contains, and NNS. Our implementation is linearizable. The operations in the LFkD-tree use single-word read and compare-and-swap (Image 1 ) atomic primitives, which are readily supported on available multi-core processors. We experimentally evaluate the LFkD-tree using several benchmarks comprising real-world and synthetic datasets. The experiments show that the presented design is scalable and achieves significant speed-up compared to the implementations of an existing sequential kD-tree and a recently proposed multidimensional indexing structure, PH-tree.","lang":"eng"}],"doi":"10.1016/j.tcs.2021.06.041","quality_controlled":"1","volume":886,"status":"public","title":"Concurrent linearizable nearest neighbour search in LockFree-kD-tree","date_created":"2021-08-08T22:01:31Z","article_type":"original","month":"09","isi":1,"year":"2021","oa_version":"Submitted Version","publication_status":"published","type":"journal_article"},{"title":"Component stability in low-space massively parallel computation","date_created":"2021-08-17T18:11:16Z","arxiv":1,"month":"07","isi":1,"year":"2021","oa_version":"Submitted Version","publication_status":"published","type":"conference","publication_identifier":{"isbn":["9781450385480"]},"conference":{"name":"PODC: Principles of Distributed Computing","end_date":"2021-07-30","location":"Virtual, Italy","start_date":"2021-07-26"},"publisher":"Association for Computing Machinery","author":[{"first_name":"Artur","full_name":"Czumaj, Artur","last_name":"Czumaj"},{"first_name":"Peter","full_name":"Davies, Peter","last_name":"Davies","id":"11396234-BB50-11E9-B24C-90FCE5697425","orcid":"0000-0002-5646-9524"},{"first_name":"Merav","full_name":"Parter, Merav","last_name":"Parter"}],"abstract":[{"lang":"eng","text":"In this paper, we study the power and limitations of component-stable algorithms in the low-space model of Massively Parallel Computation (MPC). Recently Ghaffari, Kuhn and Uitto (FOCS 2019) introduced the class of component-stable low-space MPC algorithms, which are, informally, defined as algorithms for which the outputs reported by the nodes in different connected components are required to be independent. This very natural notion was introduced to capture most (if not all) of the known efficient MPC algorithms to date, and it was the first general class of MPC algorithms for which one can show non-trivial conditional lower bounds. In this paper we enhance the framework of component-stable algorithms and investigate its effect on the complexity of randomized and deterministic low-space MPC. Our key contributions include: 1) We revise and formalize the lifting approach of Ghaffari, Kuhn and Uitto. This requires a very delicate amendment of the notion of component stability, which allows us to fill in gaps in the earlier arguments. 2) We also extend the framework to obtain conditional lower bounds for deterministic algorithms and fine-grained lower bounds that depend on the maximum degree Δ. 3) We demonstrate a collection of natural graph problems for which non-component-stable algorithms break the conditional lower bound obtained for component-stable algorithms. This implies that, for both deterministic and randomized algorithms, component-stable algorithms are conditionally weaker than the non-component-stable ones.\r\n\r\nAltogether our results imply that component-stability might limit the computational power of the low-space MPC model, paving the way for improved upper bounds that escape the conditional lower bound setting of Ghaffari, Kuhn, and Uitto."}],"quality_controlled":"1","doi":"10.1145/3465084.3467903","acknowledgement":"This work is partially supported by a Weizmann-UK Making Connections Grant, the Centre for Discrete Mathematics and its Applications (DIMAP), IBM Faculty Award, EPSRC award EP/V01305X/1, European Research Council (ERC) Grant No. 949083, the Minerva foundation with funding from the Federal German Ministry for Education and Research No. 713238, and the European Union’s Horizon 2020 programme under the Marie Skłodowska-Curie grant agreement No 754411.","status":"public","ec_funded":1,"date_published":"2021-07-21T00:00:00Z","main_file_link":[{"url":"https://arxiv.org/abs/2106.01880","open_access":"1"}],"_id":"9933","day":"21","project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411"}],"article_processing_charge":"No","language":[{"iso":"eng"}],"department":[{"_id":"DaAl"}],"date_updated":"2023-08-17T07:11:32Z","page":"481–491","citation":{"ama":"Czumaj A, Davies P, Parter M. Component stability in low-space massively parallel computation. In: <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2021:481–491. doi:<a href=\"https://doi.org/10.1145/3465084.3467903\">10.1145/3465084.3467903</a>","ista":"Czumaj A, Davies P, Parter M. 2021. Component stability in low-space massively parallel computation. Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. PODC: Principles of Distributed Computing, 481–491.","short":"A. Czumaj, P. Davies, M. Parter, in:, Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2021, pp. 481–491.","ieee":"A. Czumaj, P. Davies, and M. Parter, “Component stability in low-space massively parallel computation,” in <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>, Virtual, Italy, 2021, pp. 481–491.","mla":"Czumaj, Artur, et al. “Component Stability in Low-Space Massively Parallel Computation.” <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2021, pp. 481–491, doi:<a href=\"https://doi.org/10.1145/3465084.3467903\">10.1145/3465084.3467903</a>.","apa":"Czumaj, A., Davies, P., &#38; Parter, M. (2021). Component stability in low-space massively parallel computation. In <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i> (pp. 481–491). Virtual, Italy: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3465084.3467903\">https://doi.org/10.1145/3465084.3467903</a>","chicago":"Czumaj, Artur, Peter Davies, and Merav Parter. “Component Stability in Low-Space Massively Parallel Computation.” In <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>, 481–491. Association for Computing Machinery, 2021. <a href=\"https://doi.org/10.1145/3465084.3467903\">https://doi.org/10.1145/3465084.3467903</a>."},"oa":1,"external_id":{"arxiv":["2106.01880"],"isi":["000744439800049"]},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publication":"Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing"},{"oa":1,"page":"469–479","citation":{"ista":"Czumaj A, Davies P, Parter M. 2021. Improved deterministic (Δ+1) coloring in low-space MPC. Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 469–479.","ama":"Czumaj A, Davies P, Parter M. Improved deterministic (Δ+1) coloring in low-space MPC. In: <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2021:469–479. doi:<a href=\"https://doi.org/10.1145/3465084.3467937\">10.1145/3465084.3467937</a>","ieee":"A. Czumaj, P. Davies, and M. Parter, “Improved deterministic (Δ+1) coloring in low-space MPC,” in <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>, Virtual, Italy, 2021, pp. 469–479.","short":"A. Czumaj, P. Davies, M. Parter, in:, Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2021, pp. 469–479.","mla":"Czumaj, Artur, et al. “Improved Deterministic (Δ+1) Coloring in Low-Space MPC.” <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2021, pp. 469–479, doi:<a href=\"https://doi.org/10.1145/3465084.3467937\">10.1145/3465084.3467937</a>.","apa":"Czumaj, A., Davies, P., &#38; Parter, M. (2021). Improved deterministic (Δ+1) coloring in low-space MPC. In <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i> (pp. 469–479). Virtual, Italy: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3465084.3467937\">https://doi.org/10.1145/3465084.3467937</a>","chicago":"Czumaj, Artur, Peter Davies, and Merav Parter. “Improved Deterministic (Δ+1) Coloring in Low-Space MPC.” In <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>, 469–479. Association for Computing Machinery, 2021. <a href=\"https://doi.org/10.1145/3465084.3467937\">https://doi.org/10.1145/3465084.3467937</a>."},"external_id":{"isi":["000744439800048"]},"publication":"Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","main_file_link":[{"url":"http://wrap.warwick.ac.uk/153753","open_access":"1"}],"date_published":"2021-07-21T00:00:00Z","article_processing_charge":"No","project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships"}],"day":"21","_id":"9935","date_updated":"2023-08-17T07:11:03Z","department":[{"_id":"DaAl"}],"language":[{"iso":"eng"}],"conference":{"start_date":"2021-07-26","name":"PODC: Symposium on Principles of Distributed Computing","end_date":"2021-07-30","location":"Virtual, Italy"},"publication_identifier":{"isbn":["978-1-4503-8548-0"]},"abstract":[{"text":"We present a deterministic O(log log log n)-round low-space Massively Parallel Computation (MPC) algorithm for the classical problem of (Δ+1)-coloring on n-vertex graphs. In this model, every machine has sublinear local space of size n^φ for any arbitrary constant φ \\in (0,1). Our algorithm works under the relaxed setting where each machine is allowed to perform exponential local computations, while respecting the n^φ space and bandwidth limitations.\r\n\r\nOur key technical contribution is a novel derandomization of the ingenious (Δ+1)-coloring local algorithm by Chang-Li-Pettie (STOC 2018, SIAM J. Comput. 2020). The Chang-Li-Pettie algorithm runs in T_local =poly(loglog n) rounds, which sets the state-of-the-art randomized round complexity for the problem in the local model. Our derandomization employs a combination of tools, notably pseudorandom generators (PRG) and bounded-independence hash functions.\r\n\r\nThe achieved round complexity of O(logloglog n) rounds matches the bound of log(T_local ), which currently serves an upper bound barrier for all known randomized algorithms for locally-checkable problems in this model. Furthermore, no deterministic sublogarithmic low-space MPC algorithms for the (Δ+1)-coloring problem have been known before.","lang":"eng"}],"author":[{"first_name":"Artur","last_name":"Czumaj","full_name":"Czumaj, Artur"},{"id":"11396234-BB50-11E9-B24C-90FCE5697425","last_name":"Davies","full_name":"Davies, Peter","orcid":"0000-0002-5646-9524","first_name":"Peter"},{"first_name":"Merav","last_name":"Parter","full_name":"Parter, Merav"}],"publisher":"Association for Computing Machinery","quality_controlled":"1","doi":"10.1145/3465084.3467937","ec_funded":1,"status":"public","acknowledgement":"This work is partially supported by a Weizmann-UK Making Connections Grant, the Centre for Discrete Mathematics and its Applications (DIMAP), IBM Faculty Award, EPSRC award EP/V01305X/1, European Research Council (ERC) Grant No. 949083, the Minerva foundation with funding from the Federal German Ministry for Education and Research No. 713238, and the European Union’s Horizon 2020 programme under the Marie Skłodowska-Curie grant agreement No 754411.","title":"Improved deterministic (Δ+1) coloring in low-space MPC","date_created":"2021-08-17T18:14:15Z","year":"2021","month":"07","isi":1,"oa_version":"Submitted Version","type":"conference","publication_status":"published"},{"scopus_import":"1","publication_identifier":{"isbn":["9781450385480"]},"citation":{"ama":"Alistarh D-A, Töpfer M, Uznański P. Comparison dynamics in population protocols. In: <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2021:55-65. doi:<a href=\"https://doi.org/10.1145/3465084.3467915\">10.1145/3465084.3467915</a>","ista":"Alistarh D-A, Töpfer M, Uznański P. 2021. Comparison dynamics in population protocols. Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 55–65.","ieee":"D.-A. Alistarh, M. Töpfer, and P. Uznański, “Comparison dynamics in population protocols,” in <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>, Virtual, Italy, 2021, pp. 55–65.","short":"D.-A. Alistarh, M. Töpfer, P. Uznański, in:, Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2021, pp. 55–65.","apa":"Alistarh, D.-A., Töpfer, M., &#38; Uznański, P. (2021). Comparison dynamics in population protocols. In <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i> (pp. 55–65). Virtual, Italy: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3465084.3467915\">https://doi.org/10.1145/3465084.3467915</a>","mla":"Alistarh, Dan-Adrian, et al. “Comparison Dynamics in Population Protocols.” <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2021, pp. 55–65, doi:<a href=\"https://doi.org/10.1145/3465084.3467915\">10.1145/3465084.3467915</a>.","chicago":"Alistarh, Dan-Adrian, Martin Töpfer, and Przemysław Uznański. “Comparison Dynamics in Population Protocols.” In <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>, 55–65. Association for Computing Machinery, 2021. <a href=\"https://doi.org/10.1145/3465084.3467915\">https://doi.org/10.1145/3465084.3467915</a>."},"page":"55-65","conference":{"end_date":"2021-07-30","location":"Virtual, Italy","name":"PODC: Symposium on Principles of Distributed Computing","start_date":"2021-07-26"},"author":[{"orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian"},{"id":"4B865388-F248-11E8-B48F-1D18A9856A87","full_name":"Töpfer, Martin","last_name":"Töpfer","first_name":"Martin"},{"first_name":"Przemysław","last_name":"Uznański","full_name":"Uznański, Przemysław"}],"publisher":"Association for Computing Machinery","abstract":[{"text":"There has recently been a surge of interest in the computational and complexity properties of the population model, which assumes n anonymous, computationally-bounded nodes, interacting at random, with the goal of jointly computing global predicates. Significant work has gone towards investigating majority or consensus dynamics in this model: that is, assuming that every node is initially in one of two states X or Y, determine which state had higher initial count.\r\n\r\nIn this paper, we consider a natural generalization of majority/consensus, which we call comparison : in its simplest formulation, we are given two baseline states, X and Y, present in any initial configuration in fixed, but possibly small counts. One of these states has higher count than the other: we will assume |X_0| > C |Y_0| for some constant C > 1. The challenge is to design a protocol by which nodes can quickly and reliably decide on which of the baseline states X_0 and Y_0 has higher initial count. We begin by analyzing a simple and general dynamics solving the above comparison problem, which uses O( log n ) states per node, and converges in O(log n) (parallel) time, with high probability, to a state where the whole population votes on opinions X or Y at rates proportional to the initial concentrations of |X_0| vs. |Y_0|. We then describe how this procedure can be bootstrapped to solve comparison, i.e. have every node in the population reach the \"correct'' decision, with probability 1 - o(1), at the cost of O (log log n) additional states. Further, we prove that this dynamics is self-stabilizing, in the sense that it converges to the correct decision from arbitrary initial states, and leak-robust, in the sense that it can withstand spurious faulty reactions, which are known to occur in practical implementations of population protocols. Our analysis is based on a new martingale concentration result relating the discrete-time evolution of a population protocol to its expected (steady-state) analysis, which should be a useful tool when analyzing opinion dynamics and epidemic dissemination in the population model.","lang":"eng"}],"quality_controlled":"1","external_id":{"isi":["000744439800005"]},"doi":"10.1145/3465084.3467915","status":"public","acknowledgement":"We would like to thank Rati Gelashvili for very useful discussions, and the PODC anonymous reviewers for their careful reading of our paper, and for their useful remarks. This work is partially supported by the Polish National Science Center (NCN) grant UMO2017/25/B/ST6/02010.","publication":"Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","date_created":"2021-08-22T22:01:20Z","title":"Comparison dynamics in population protocols","date_published":"2021-07-21T00:00:00Z","month":"07","isi":1,"year":"2021","oa_version":"None","_id":"9951","day":"21","article_processing_charge":"No","publication_status":"published","department":[{"_id":"DaAl"}],"type":"conference","date_updated":"2023-08-11T10:56:04Z","language":[{"iso":"eng"}]},{"main_file_link":[{"url":"https://arxiv.org/abs/2105.08098","open_access":"1"}],"date_published":"2021-07-01T00:00:00Z","department":[{"_id":"DaAl"}],"date_updated":"2022-03-18T08:45:46Z","language":[{"iso":"eng"}],"article_processing_charge":"No","day":"01","_id":"10853","oa":1,"citation":{"ieee":"A. Fedorov, N. Koval, and D.-A. Alistarh, “A scalable concurrent algorithm for dynamic connectivity,” in <i>Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures</i>, Virtual, Online, 2021, pp. 208–220.","short":"A. Fedorov, N. Koval, D.-A. Alistarh, in:, Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures, Association for Computing Machinery, 2021, pp. 208–220.","ista":"Fedorov A, Koval N, Alistarh D-A. 2021. A scalable concurrent algorithm for dynamic connectivity. Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures. SPAA: Symposium on Parallelism in Algorithms and Architectures, 208–220.","ama":"Fedorov A, Koval N, Alistarh D-A. A scalable concurrent algorithm for dynamic connectivity. In: <i>Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures</i>. Association for Computing Machinery; 2021:208-220. doi:<a href=\"https://doi.org/10.1145/3409964.3461810\">10.1145/3409964.3461810</a>","chicago":"Fedorov, Alexander, Nikita Koval, and Dan-Adrian Alistarh. “A Scalable Concurrent Algorithm for Dynamic Connectivity.” In <i>Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures</i>, 208–20. Association for Computing Machinery, 2021. <a href=\"https://doi.org/10.1145/3409964.3461810\">https://doi.org/10.1145/3409964.3461810</a>.","apa":"Fedorov, A., Koval, N., &#38; Alistarh, D.-A. (2021). A scalable concurrent algorithm for dynamic connectivity. In <i>Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures</i> (pp. 208–220). Virtual, Online: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3409964.3461810\">https://doi.org/10.1145/3409964.3461810</a>","mla":"Fedorov, Alexander, et al. “A Scalable Concurrent Algorithm for Dynamic Connectivity.” <i>Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures</i>, Association for Computing Machinery, 2021, pp. 208–20, doi:<a href=\"https://doi.org/10.1145/3409964.3461810\">10.1145/3409964.3461810</a>."},"page":"208-220","publication":"Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["2105.08098"]},"year":"2021","month":"07","arxiv":1,"title":"A scalable concurrent algorithm for dynamic connectivity","date_created":"2022-03-18T08:21:47Z","type":"conference","publication_status":"published","oa_version":"Preprint","abstract":[{"lang":"eng","text":"Dynamic Connectivity is a fundamental algorithmic graph problem, motivated by a wide range of applications to social and communication networks and used as a building block in various other algorithms, such as the bi-connectivity and the dynamic minimal spanning tree problems. In brief, we wish to maintain the connected components of the graph under dynamic edge insertions and deletions. In the sequential case, the problem has been well-studied from both theoretical and practical perspectives. However, much less is known about efficient concurrent solutions to this problem. This is the gap we address in this paper. We start from one of the classic data structures used to solve this problem, the Euler Tour Tree. Our first contribution is a non-blocking single-writer implementation of it. We leverage this data structure to obtain the first truly concurrent generalization of dynamic connectivity, which preserves the time complexity of its sequential counterpart, but is also scalable in practice. To achieve this, we rely on three main techniques. The first is to ensure that connectivity queries, which usually dominate real-world workloads, are non-blocking. The second non-trivial technique expands the above idea by making all queries that do not change the connectivity structure non-blocking. The third ingredient is applying fine-grained locking for updating the connected components, which allows operations on disjoint components to occur in parallel. We evaluate the resulting algorithm on various workloads, executing on both real and synthetic graphs. The results show the efficiency of each of the proposed optimizations; the most efficient variant improves the performance of a coarse-grained based implementation on realistic scenarios up to 6x on average and up to 30x when connectivity queries dominate."}],"publisher":"Association for Computing Machinery","author":[{"last_name":"Fedorov","full_name":"Fedorov, Alexander","first_name":"Alexander"},{"full_name":"Koval, Nikita","last_name":"Koval","first_name":"Nikita"},{"first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","orcid":"0000-0003-3650-940X"}],"conference":{"start_date":"2021-07-06","end_date":"2021-07-08","location":"Virtual, Online","name":"SPAA: Symposium on Parallelism in Algorithms and Architectures"},"scopus_import":"1","publication_identifier":{"isbn":["9781450380706"]},"status":"public","quality_controlled":"1","doi":"10.1145/3409964.3461810"},{"language":[{"iso":"eng"}],"date_updated":"2023-09-26T10:40:55Z","department":[{"_id":"DaAl"}],"_id":"10854","day":"01","project":[{"_id":"268A44D6-B435-11E9-9278-68D0E5697425","grant_number":"805223","call_identifier":"H2020","name":"Elastic Coordination for Scalable Machine Learning"},{"grant_number":"840605","name":"Coordination in constrained and natural distributed systems","call_identifier":"H2020","_id":"26A5D39A-B435-11E9-9278-68D0E5697425"}],"article_processing_charge":"No","date_published":"2021-05-01T00:00:00Z","main_file_link":[{"url":"https://arxiv.org/abs/2005.07637","open_access":"1"}],"related_material":{"record":[{"relation":"extended_version","id":"10855","status":"public"}]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems","external_id":{"arxiv":["2005.07637"]},"page":"71-72","citation":{"chicago":"Foerster, Klaus-Tycho, Janne Korhonen, Ami Paz, Joel Rybicki, and Stefan Schmid. “Input-Dynamic Distributed Algorithms for Communication Networks.” In <i>Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems</i>, 71–72. Association for Computing Machinery, 2021. <a href=\"https://doi.org/10.1145/3410220.3453923\">https://doi.org/10.1145/3410220.3453923</a>.","apa":"Foerster, K.-T., Korhonen, J., Paz, A., Rybicki, J., &#38; Schmid, S. (2021). Input-dynamic distributed algorithms for communication networks. In <i>Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems</i> (pp. 71–72). Virtual, Online: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3410220.3453923\">https://doi.org/10.1145/3410220.3453923</a>","mla":"Foerster, Klaus-Tycho, et al. “Input-Dynamic Distributed Algorithms for Communication Networks.” <i>Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems</i>, Association for Computing Machinery, 2021, pp. 71–72, doi:<a href=\"https://doi.org/10.1145/3410220.3453923\">10.1145/3410220.3453923</a>.","short":"K.-T. Foerster, J. Korhonen, A. Paz, J. Rybicki, S. Schmid, in:, Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, Association for Computing Machinery, 2021, pp. 71–72.","ieee":"K.-T. Foerster, J. Korhonen, A. Paz, J. Rybicki, and S. Schmid, “Input-dynamic distributed algorithms for communication networks,” in <i>Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems</i>, Virtual, Online, 2021, pp. 71–72.","ama":"Foerster K-T, Korhonen J, Paz A, Rybicki J, Schmid S. Input-dynamic distributed algorithms for communication networks. In: <i>Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems</i>. Association for Computing Machinery; 2021:71-72. doi:<a href=\"https://doi.org/10.1145/3410220.3453923\">10.1145/3410220.3453923</a>","ista":"Foerster K-T, Korhonen J, Paz A, Rybicki J, Schmid S. 2021. Input-dynamic distributed algorithms for communication networks. Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems. SIGMETRICS: International Conference on Measurement and Modeling of Computer Systems, 71–72."},"oa":1,"publication_status":"published","type":"conference","oa_version":"Preprint","month":"05","year":"2021","title":"Input-dynamic distributed algorithms for communication networks","date_created":"2022-03-18T08:48:41Z","arxiv":1,"acknowledgement":"We thank Jukka Suomela for discussions. We also thank our shepherd Mohammad Hajiesmaili and the reviewers for their time and suggestions on how to improve the paper. 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), from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska–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.","status":"public","ec_funded":1,"doi":"10.1145/3410220.3453923","quality_controlled":"1","author":[{"first_name":"Klaus-Tycho","last_name":"Foerster","full_name":"Foerster, Klaus-Tycho"},{"last_name":"Korhonen","full_name":"Korhonen, Janne","id":"C5402D42-15BC-11E9-A202-CA2BE6697425","first_name":"Janne"},{"first_name":"Ami","last_name":"Paz","full_name":"Paz, Ami"},{"first_name":"Joel","full_name":"Rybicki, Joel","last_name":"Rybicki","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6432-6646"},{"first_name":"Stefan","last_name":"Schmid","full_name":"Schmid, Stefan"}],"publisher":"Association for Computing Machinery","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?\r\nTo 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 labelled graph under batch changes. We investigate, when a batch of alpha edge label changes arrive, - how much time as a function of alpha we need to update an existing solution, and - how much information the nodes have to keep in local memory between batches in order to update the solution quickly.\r\nOur 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. The diverse time complexity of our model spans from constant time, through time polynomial in alpha, and to alpha time, which we show to be enough for any task.","lang":"eng"}],"scopus_import":"1","publication_identifier":{"isbn":["9781450380720"]},"conference":{"start_date":"2021-06-14","name":"SIGMETRICS: International Conference on Measurement and Modeling of Computer Systems","end_date":"2021-06-18","location":"Virtual, Online"}},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":"         5","publication":"Proceedings of the ACM on Measurement and Analysis of Computing Systems","keyword":["Computer Networks and Communications","Hardware and Architecture","Safety","Risk","Reliability and Quality","Computer Science (miscellaneous)"],"issue":"1","external_id":{"arxiv":["2005.07637"]},"page":"1-33","citation":{"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>.","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>","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>.","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.","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.","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."},"oa":1,"language":[{"iso":"eng"}],"date_updated":"2023-09-26T10:40:55Z","department":[{"_id":"DaAl"}],"day":"01","_id":"10855","project":[{"name":"Coordination in constrained and natural distributed systems","call_identifier":"H2020","grant_number":"840605","_id":"26A5D39A-B435-11E9-9278-68D0E5697425"},{"_id":"268A44D6-B435-11E9-9278-68D0E5697425","grant_number":"805223","call_identifier":"H2020","name":"Elastic Coordination for Scalable Machine Learning"}],"article_processing_charge":"No","date_published":"2021-03-01T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2005.07637"}],"related_material":{"record":[{"relation":"shorter_version","id":"10854","status":"public"}]},"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.","status":"public","ec_funded":1,"doi":"10.1145/3447384","volume":5,"quality_controlled":"1","publisher":"Association for Computing Machinery","author":[{"first_name":"Klaus-Tycho","last_name":"Foerster","full_name":"Foerster, Klaus-Tycho"},{"first_name":"Janne","id":"C5402D42-15BC-11E9-A202-CA2BE6697425","last_name":"Korhonen","full_name":"Korhonen, Janne"},{"first_name":"Ami","full_name":"Paz, Ami","last_name":"Paz"},{"id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","full_name":"Rybicki, Joel","last_name":"Rybicki","orcid":"0000-0002-6432-6646","first_name":"Joel"},{"last_name":"Schmid","full_name":"Schmid, Stefan","first_name":"Stefan"}],"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"}],"publication_identifier":{"issn":["2476-1249"]},"scopus_import":"1","publication_status":"published","type":"journal_article","oa_version":"Preprint","month":"03","year":"2021","date_created":"2022-03-18T09:10:27Z","title":"Input-dynamic distributed algorithms for communication networks","arxiv":1,"article_type":"original"},{"article_processing_charge":"No","_id":"11436","day":"18","project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020"},{"_id":"268A44D6-B435-11E9-9278-68D0E5697425","grant_number":"805223","name":"Elastic Coordination for Scalable Machine Learning","call_identifier":"H2020"}],"language":[{"iso":"eng"}],"date_updated":"2022-06-07T06:53:36Z","department":[{"_id":"DaAl"}],"main_file_link":[{"open_access":"1","url":" https://doi.org/10.48550/arXiv.1905.11845"}],"date_published":"2021-05-18T00:00:00Z","external_id":{"arxiv":["1905.11845"]},"issue":"9B","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":"        35","publication":"35th AAAI Conference on Artificial Intelligence, AAAI 2021","page":"8209-8216","citation":{"chicago":"Kungurtsev, Vyacheslav, Malcolm Egan, Bapi Chatterjee, and Dan-Adrian Alistarh. “Asynchronous Optimization Methods for Efficient Training of Deep Neural Networks with Guarantees.” In <i>35th AAAI Conference on Artificial Intelligence, AAAI 2021</i>, 35:8209–16. AAAI Press, 2021.","apa":"Kungurtsev, V., Egan, M., Chatterjee, B., &#38; Alistarh, D.-A. (2021). Asynchronous optimization methods for efficient training of deep neural networks with guarantees. In <i>35th AAAI Conference on Artificial Intelligence, AAAI 2021</i> (Vol. 35, pp. 8209–8216). Virtual, Online: AAAI Press.","mla":"Kungurtsev, Vyacheslav, et al. “Asynchronous Optimization Methods for Efficient Training of Deep Neural Networks with Guarantees.” <i>35th AAAI Conference on Artificial Intelligence, AAAI 2021</i>, vol. 35, no. 9B, AAAI Press, 2021, pp. 8209–16.","short":"V. Kungurtsev, M. Egan, B. Chatterjee, D.-A. Alistarh, in:, 35th AAAI Conference on Artificial Intelligence, AAAI 2021, AAAI Press, 2021, pp. 8209–8216.","ieee":"V. Kungurtsev, M. Egan, B. Chatterjee, and D.-A. Alistarh, “Asynchronous optimization methods for efficient training of deep neural networks with guarantees,” in <i>35th AAAI Conference on Artificial Intelligence, AAAI 2021</i>, Virtual, Online, 2021, vol. 35, no. 9B, pp. 8209–8216.","ista":"Kungurtsev V, Egan M, Chatterjee B, Alistarh D-A. 2021. Asynchronous optimization methods for efficient training of deep neural networks with guarantees. 35th AAAI Conference on Artificial Intelligence, AAAI 2021. AAAI: Conference on Artificial Intelligence vol. 35, 8209–8216.","ama":"Kungurtsev V, Egan M, Chatterjee B, Alistarh D-A. Asynchronous optimization methods for efficient training of deep neural networks with guarantees. In: <i>35th AAAI Conference on Artificial Intelligence, AAAI 2021</i>. Vol 35. AAAI Press; 2021:8209-8216."},"oa":1,"oa_version":"Preprint","type":"conference","publication_status":"published","arxiv":1,"title":"Asynchronous optimization methods for efficient training of deep neural networks with guarantees","date_created":"2022-06-05T22:01:52Z","year":"2021","month":"05","quality_controlled":"1","volume":35,"ec_funded":1,"acknowledgement":"Vyacheslav Kungurtsev was supported by the OP VVV project CZ.02.1.01/0.0/0.0/16 019/0000765 “Research Center for Informatics. Bapi Chatterjee was supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No. 754411 (ISTPlus). Dan Alistarh 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).","status":"public","conference":{"location":"Virtual, Online","end_date":"2021-02-09","name":"AAAI: Conference on Artificial Intelligence","start_date":"2021-02-02"},"publication_identifier":{"eissn":["2374-3468"],"isbn":["9781713835974"],"issn":["2159-5399"]},"scopus_import":"1","abstract":[{"text":"Asynchronous distributed algorithms are a popular way to reduce synchronization costs in large-scale optimization, and in particular for neural network training. However, for nonsmooth and nonconvex objectives, few convergence guarantees exist beyond cases where closed-form proximal operator solutions are available. As training most popular deep neural networks corresponds to optimizing nonsmooth and nonconvex objectives, there is a pressing need for such convergence guarantees. In this paper, we analyze for the first time the convergence of stochastic asynchronous optimization for this general class of objectives. In particular, we focus on stochastic subgradient methods allowing for block variable partitioning, where the shared model is asynchronously updated by concurrent processes. To this end, we use a probabilistic model which captures key features of real asynchronous scheduling between concurrent processes. Under this model, we establish convergence with probability one to an invariant set for stochastic subgradient methods with momentum. From a practical perspective, one issue with the family of algorithms that we consider is that they are not efficiently supported by machine learning frameworks, which mostly focus on distributed data-parallel strategies. To address this, we propose a new implementation strategy for shared-memory based training of deep neural networks for a partitioned but shared model in single- and multi-GPU settings. Based on this implementation, we achieve on average1.2x speed-up in comparison to state-of-the-art training methods for popular image classification tasks, without compromising accuracy.","lang":"eng"}],"publisher":"AAAI Press","author":[{"last_name":"Kungurtsev","full_name":"Kungurtsev, Vyacheslav","first_name":"Vyacheslav"},{"last_name":"Egan","full_name":"Egan, Malcolm","first_name":"Malcolm"},{"id":"3C41A08A-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Bapi","last_name":"Chatterjee","first_name":"Bapi"},{"first_name":"Dan-Adrian","last_name":"Alistarh","full_name":"Alistarh, Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X"}]},{"oa_version":"Published Version","publication_status":"published","type":"conference","title":"Distributed principal component analysis with limited communication","date_created":"2022-06-19T22:01:58Z","arxiv":1,"month":"12","year":"2021","volume":4,"quality_controlled":"1","acknowledgement":"We would like to thank the anonymous reviewers for helpful comments and suggestions. We also thank Aurelien Lucchi and Antonio Orvieto for fruitful discussions at an early stage of this work. FA is partially supported by the SNSF under research project No. 192363 and conducted part of this work while at IST Austria 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.","status":"public","ec_funded":1,"publication_identifier":{"issn":["1049-5258"],"isbn":["9781713845393"]},"scopus_import":"1","conference":{"start_date":"2021-12-06","location":"Virtual, Online","end_date":"2021-12-14","name":"NeurIPS: Neural Information Processing Systems"},"author":[{"full_name":"Alimisis, Foivos","last_name":"Alimisis","first_name":"Foivos"},{"last_name":"Davies","full_name":"Davies, Peter","id":"11396234-BB50-11E9-B24C-90FCE5697425","orcid":"0000-0002-5646-9524","first_name":"Peter"},{"first_name":"Bart","full_name":"Vandereycken, Bart","last_name":"Vandereycken"},{"orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian"}],"publisher":"Neural Information Processing Systems Foundation","abstract":[{"lang":"eng","text":"We study efficient distributed algorithms for the fundamental problem of principal component analysis and leading eigenvector computation on the sphere, when the data are randomly distributed among a set of computational nodes. We propose a new quantized variant of Riemannian gradient descent to solve this problem, and prove that the algorithm converges with high probability under a set of necessary spherical-convexity properties. We give bounds on the number of bits transmitted by the algorithm under common initialization schemes, and investigate the dependency on the problem dimension in each case."}],"_id":"11452","day":"01","project":[{"_id":"268A44D6-B435-11E9-9278-68D0E5697425","grant_number":"805223","name":"Elastic Coordination for Scalable Machine Learning","call_identifier":"H2020"},{"call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"article_processing_charge":"No","language":[{"iso":"eng"}],"date_updated":"2022-06-20T08:31:52Z","department":[{"_id":"DaAl"}],"date_published":"2021-12-01T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://proceedings.neurips.cc/paper/2021/file/1680e9fa7b4dd5d62ece800239bb53bd-Paper.pdf"}],"external_id":{"arxiv":["2110.14391"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"Advances in Neural Information Processing Systems - 35th Conference on Neural Information Processing Systems","intvolume":"         4","page":"2823-2834","citation":{"ama":"Alimisis F, Davies P, Vandereycken B, Alistarh D-A. Distributed principal component analysis with limited communication. In: <i>Advances in Neural Information Processing Systems - 35th Conference on Neural Information Processing Systems</i>. Vol 4. Neural Information Processing Systems Foundation; 2021:2823-2834.","ista":"Alimisis F, Davies P, Vandereycken B, Alistarh D-A. 2021. Distributed principal component analysis with limited communication. Advances in Neural Information Processing Systems - 35th Conference on Neural Information Processing Systems. NeurIPS: Neural Information Processing Systems vol. 4, 2823–2834.","ieee":"F. Alimisis, P. Davies, B. Vandereycken, and D.-A. Alistarh, “Distributed principal component analysis with limited communication,” in <i>Advances in Neural Information Processing Systems - 35th Conference on Neural Information Processing Systems</i>, Virtual, Online, 2021, vol. 4, pp. 2823–2834.","short":"F. Alimisis, P. Davies, B. Vandereycken, D.-A. Alistarh, in:, Advances in Neural Information Processing Systems - 35th Conference on Neural Information Processing Systems, Neural Information Processing Systems Foundation, 2021, pp. 2823–2834.","apa":"Alimisis, F., Davies, P., Vandereycken, B., &#38; Alistarh, D.-A. (2021). Distributed principal component analysis with limited communication. In <i>Advances in Neural Information Processing Systems - 35th Conference on Neural Information Processing Systems</i> (Vol. 4, pp. 2823–2834). Virtual, Online: Neural Information Processing Systems Foundation.","mla":"Alimisis, Foivos, et al. “Distributed Principal Component Analysis with Limited Communication.” <i>Advances in Neural Information Processing Systems - 35th Conference on Neural Information Processing Systems</i>, vol. 4, Neural Information Processing Systems Foundation, 2021, pp. 2823–34.","chicago":"Alimisis, Foivos, Peter Davies, Bart Vandereycken, and Dan-Adrian Alistarh. “Distributed Principal Component Analysis with Limited Communication.” In <i>Advances in Neural Information Processing Systems - 35th Conference on Neural Information Processing Systems</i>, 4:2823–34. Neural Information Processing Systems Foundation, 2021."},"oa":1},{"date_published":"2021-12-06T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://proceedings.neurips.cc/paper/2021/file/48000647b315f6f00f913caa757a70b3-Paper.pdf"}],"related_material":{"record":[{"relation":"dissertation_contains","id":"13074","status":"public"}]},"language":[{"iso":"eng"}],"department":[{"_id":"GradSch"},{"_id":"DaAl"}],"date_updated":"2023-06-01T12:54:45Z","day":"6","_id":"11458","project":[{"_id":"268A44D6-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Elastic Coordination for Scalable Machine Learning","grant_number":"805223"}],"acknowledged_ssus":[{"_id":"ScienComp"}],"article_processing_charge":"No","citation":{"ama":"Peste E-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. Curran Associates; 2021:8557-8570.","ista":"Peste E-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 vol. 34, 8557–8570.","ieee":"E.-A. Peste, 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.","short":"E.-A. Peste, E.B. Iofinova, A. Vladu, D.-A. Alistarh, in:, 35th Conference on Neural Information Processing Systems, Curran Associates, 2021, pp. 8557–8570.","apa":"Peste, E.-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: Curran Associates.","mla":"Peste, Elena-Alexandra, et al. “AC/DC: Alternating Compressed/DeCompressed Training of Deep Neural Networks.” <i>35th Conference on Neural Information Processing Systems</i>, vol. 34, Curran Associates, 2021, pp. 8557–70.","chicago":"Peste, Elena-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. Curran Associates, 2021."},"page":"8557-8570","oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"35th Conference on Neural Information Processing Systems","intvolume":"        34","external_id":{"arxiv":["2106.12379"]},"month":"12","year":"2021","date_created":"2022-06-20T12:11:53Z","title":"AC/DC: Alternating Compressed/DeCompressed training of deep neural networks","arxiv":1,"publication_status":"published","type":"conference","oa_version":"Published Version","author":[{"first_name":"Elena-Alexandra","id":"32D78294-F248-11E8-B48F-1D18A9856A87","last_name":"Peste","full_name":"Peste, Elena-Alexandra"},{"full_name":"Iofinova, Eugenia B","last_name":"Iofinova","id":"f9a17499-f6e0-11ea-865d-fdf9a3f77117","orcid":"0000-0002-7778-3221","first_name":"Eugenia B"},{"last_name":"Vladu","full_name":"Vladu, Adrian","first_name":"Adrian"},{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","last_name":"Alistarh","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","first_name":"Dan-Adrian"}],"publisher":"Curran Associates","abstract":[{"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.","lang":"eng"}],"scopus_import":"1","publication_identifier":{"isbn":["9781713845393"],"issn":["1049-5258"]},"conference":{"name":"NeurIPS: Neural Information Processing Systems","end_date":"2021-12-14","location":"Virtual, Online","start_date":"2021-12-06"},"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.","status":"public","ec_funded":1,"quality_controlled":"1","volume":34},{"status":"public","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.","ec_funded":1,"quality_controlled":"1","volume":34,"author":[{"last_name":"Frantar","full_name":"Frantar, Elias","id":"09a8f98d-ec99-11ea-ae11-c063a7b7fe5f","first_name":"Elias"},{"first_name":"Eldar","id":"47beb3a5-07b5-11eb-9b87-b108ec578218","full_name":"Kurtic, Eldar","last_name":"Kurtic"},{"full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X","first_name":"Dan-Adrian"}],"publisher":"Curran Associates","abstract":[{"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].","lang":"eng"}],"publication_identifier":{"issn":["1049-5258"],"isbn":["9781713845393"]},"scopus_import":"1","conference":{"start_date":"2021-12-06","name":"NeurIPS: Neural Information Processing Systems","location":"Virtual, Online","end_date":"2021-12-14"},"publication_status":"published","type":"conference","oa_version":"Published Version","month":"12","year":"2021","title":"M-FAC: Efficient matrix-free approximations of second-order information","date_created":"2022-06-26T22:01:35Z","arxiv":1,"publication":"35th Conference on Neural Information Processing Systems","intvolume":"        34","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["2010.08222"]},"oa":1,"citation":{"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 vol. 34, 14873–14886.","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. Curran Associates; 2021: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.","short":"E. Frantar, E. Kurtic, D.-A. Alistarh, in:, 35th Conference on Neural Information Processing Systems, Curran Associates, 2021, pp. 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: Curran Associates.","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, Curran Associates, 2021, pp. 14873–86.","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. Curran Associates, 2021."},"page":"14873-14886","date_updated":"2022-06-27T07:05:12Z","department":[{"_id":"DaAl"}],"language":[{"iso":"eng"}],"project":[{"_id":"268A44D6-B435-11E9-9278-68D0E5697425","name":"Elastic Coordination for Scalable Machine Learning","call_identifier":"H2020","grant_number":"805223"}],"day":"06","_id":"11463","article_processing_charge":"No","date_published":"2021-12-06T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://proceedings.neurips.cc/paper/2021/file/7cfd5df443b4eb0d69886a583b33de4c-Paper.pdf"}]},{"department":[{"_id":"DaAl"}],"date_updated":"2022-06-27T06:54:31Z","language":[{"iso":"eng"}],"project":[{"grant_number":"805223","name":"Elastic Coordination for Scalable Machine Learning","call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425"}],"day":"06","_id":"11464","article_processing_charge":"No","date_published":"2021-12-06T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://proceedings.neurips.cc/paper/2021/file/3b92d18aa7a6176dd37d372bc2f1eb71-Paper.pdf"}],"intvolume":"        34","publication":"35th Conference on Neural Information Processing Systems","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["2010.08222"]},"oa":1,"citation":{"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. Curran Associates; 2021:7254-7266.","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 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.","short":"D.-A. Alistarh, J. Korhonen, in:, 35th Conference on Neural Information Processing Systems, Curran Associates, 2021, pp. 7254–7266.","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: Curran Associates.","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, Curran Associates, 2021, pp. 7254–66.","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. Curran Associates, 2021."},"page":"7254-7266","publication_status":"published","type":"conference","oa_version":"Published Version","month":"12","year":"2021","date_created":"2022-06-26T22:01:35Z","title":"Towards tight communication lower bounds for distributed optimisation","arxiv":1,"status":"public","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).","ec_funded":1,"volume":34,"quality_controlled":"1","author":[{"first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh"},{"id":"C5402D42-15BC-11E9-A202-CA2BE6697425","full_name":"Korhonen, Janne","last_name":"Korhonen","first_name":"Janne"}],"publisher":"Curran Associates","abstract":[{"lang":"eng","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."}],"publication_identifier":{"isbn":["9781713845393"],"issn":["1049-5258"]},"scopus_import":"1","conference":{"start_date":"2021-12-06","end_date":"2021-12-14","location":"Virtual, Online","name":"NeurIPS: Neural Information Processing Systems"}}]