[{"main_file_link":[{"url":"https://proceedings.mlsys.org/paper_files/paper/2024/hash/c74b624843218d9b6713fcf299d6d5e4-Abstract-Conference.html","open_access":"1"}],"department":[{"_id":"DaAl"}],"citation":{"short":"E. Frantar, D.-A. Alistarh, in:, Proceedings of Machine Learning and Systems, 2024.","apa":"Frantar, E., &#38; Alistarh, D.-A. (2024). QMoE: Sub-1-bit compression of trillion parameter models. In <i>Proceedings of Machine Learning and Systems</i> (Vol. 6). Santa Clara, CA, United States.","chicago":"Frantar, Elias, and Dan-Adrian Alistarh. “QMoE: Sub-1-Bit Compression of Trillion Parameter Models.” In <i>Proceedings of Machine Learning and Systems</i>, Vol. 6, 2024.","ieee":"E. Frantar and D.-A. Alistarh, “QMoE: Sub-1-bit compression of trillion parameter models,” in <i>Proceedings of Machine Learning and Systems</i>, Santa Clara, CA, United States, 2024, vol. 6.","ama":"Frantar E, Alistarh D-A. QMoE: Sub-1-bit compression of trillion parameter models. In: <i>Proceedings of Machine Learning and Systems</i>. Vol 6. ; 2024.","ista":"Frantar E, Alistarh D-A. 2024. QMoE: Sub-1-bit compression of trillion parameter models. Proceedings of Machine Learning and Systems. MLSys: Machine Learning and Systems vol. 6.","mla":"Frantar, Elias, and Dan-Adrian Alistarh. “QMoE: Sub-1-Bit Compression of Trillion Parameter Models.” <i>Proceedings of Machine Learning and Systems</i>, vol. 6, 2024."},"status":"public","oa_version":"Published Version","language":[{"iso":"eng"}],"intvolume":"         6","date_created":"2024-09-13T10:01:38Z","researchdata_availability":"yes","quality_controlled":"1","_id":"18061","date_updated":"2026-10-02T11:19:46Z","das_tickbox":"0","title":"QMoE: Sub-1-bit compression of trillion parameter models","date_published":"2024-05-01T00:00:00Z","author":[{"full_name":"Frantar, Elias","last_name":"Frantar","id":"09a8f98d-ec99-11ea-ae11-c063a7b7fe5f","first_name":"Elias"},{"full_name":"Alistarh, Dan-Adrian","first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","last_name":"Alistarh","orcid":"0000-0003-3650-940X"}],"publication_status":"published","oa":1,"article_processing_charge":"No","publication":"Proceedings of Machine Learning and Systems","related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"17485"}]},"month":"05","abstract":[{"lang":"eng","text":"Mixture-of-Experts (MoE) architectures offer a general solution to the high inference costs of large language models (LLMs) via sparse routing, bringing faster and more accurate models, at the cost of massive parameter counts. For example, the SwitchTransformer-c2048 model has 1.6 trillion parameters, requiring 3.2TB of accelerator memory to run efficiently, which makes practical deployment challenging and expensive. In this paper, we present a solution to this memory problem, in form of a new compression and execution framework called QMoE. Specifically, QMoE consists of a scalable algorithm which accurately compresses trillion-parameter MoEs to less than 1 bit per parameter, in a custom format co-designed with bespoke GPU decoding kernels to facilitate efficient end-to-end compressed inference, with minor runtime overheads relative to uncompressed execution. Concretely, QMoE can compress the 1.6 trillion parameter SwitchTransformer-c2048 model to less than 160GB (20x compression, 0.8 bits per parameter) at only minor accuracy loss, in less than a day on a single GPU. This enables, for the first time, the execution of a trillion-parameter model on affordable commodity hardware, like a single server with 4x NVIDIA A6000 or 8x NVIDIA 3090 GPUs, at less than 5% runtime overhead relative to ideal uncompressed inference. The anonymized code is available at: github.com/mlsys24-qmoe/qmoe."}],"day":"01","volume":6,"ddc":["000"],"corr_author":"1","supplementarymaterial":"no","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","conference":{"start_date":"2024-05-13","end_date":"2024-05-16","name":"MLSys: Machine Learning and Systems","location":"Santa Clara, CA, United States"},"year":"2024","type":"conference"},{"corr_author":"1","publisher":"Institute of Science and Technology Austria","has_accepted_license":"1","ddc":["000"],"day":"04","abstract":[{"lang":"eng","text":"Deep learning is essential in numerous applications nowadays, with many recent advancements made possible by training very large models. Despite their broad applicability, training neural networks is often time-intensive, and it is usually impractical to manage large models and datasets on a single machine. To address these issues, distributed deep learning training has become increasingly important. However, distributed training requires synchronization among nodes, and the mini-batch stochastic gradient descent algorithm places a significant load on network connections. A possible solution to tackle the synchronization bottleneck is to reduce a message size by lossy compression.\r\n\r\nIn this thesis, we investigate systems and algorithmic approaches to communication compression during training. From the systems perspective, we demonstrate that a common approach of expensive hardware overprovisioning can be replaced through a thorough system design. We introduce a framework that introduces efficient software support for compressed communication in machine learning applications, applicable to both multi-GPU single-node training and larger-scale multi-node training. Our framework integrates with popular ML frameworks, providing up to 3x speedups for multi-GPU nodes based on commodity hardware and order-of-magnitude improvements in the multi-node setting, with negligible impact on accuracy.\r\n\r\nAlso, we consider an application of our framework to different communication schemes, such as Fully Sharded Data Parallel. We provide strong convergence guarantees for the compression in such a setup. Empirical validation shows that our method preserves model accuracy for GPT-family models with up to 1.3 billion parameters, while completely removing the communication bottlenecks of non-compressed alternatives, providing up to 2.2x speedups end-to-end.\r\n\r\nFrom the algorithmic side, we propose a general framework that dynamically adjusts the degree of compression across a model's layers during training. This approach enhances overall compression and results in significant speedups without compromising accuracy. Our algorithm utilizes an adaptive algorithm that automatically selects the optimal compression parameters for model layers, ensuring the best compression ratio while adhering to an error constraint. Our method is effective across all existing families of compression methods. It achieves up to 2.5x faster training and up to a 5x improvement in compression compared to efficient implementations of current approaches. Additionally, LGreCo can complement existing adaptive algorithms.\r\n"}],"publication_identifier":{"issn":["2663-337X"]},"month":"09","related_material":{"record":[{"relation":"part_of_dissertation","status":"public","id":"14461"},{"relation":"part_of_dissertation","status":"public","id":"12780"},{"id":"17456","relation":"part_of_dissertation","status":"public"}]},"OA_place":"publisher","doi_confirm":"1","article_processing_charge":"No","oa":1,"acknowledged_ssus":[{"_id":"ScienComp"}],"type":"dissertation","year":"2024","fulldoi":"https://doi.org/10.15479/at:ista:17490","supervisor":[{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","last_name":"Alistarh","orcid":"0000-0003-3650-940X","first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian"}],"project":[{"grant_number":"805223","call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425","name":"Elastic Coordination for Scalable Machine Learning"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","supplementarymaterial":"no","license":"https://creativecommons.org/licenses/by-nc-sa/4.0/","alternative_title":["ISTA Thesis"],"tmp":{"image":"/images/cc_by_nc_sa.png","legal_code_url":"https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode","name":"Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)","short":"CC BY-NC-SA (4.0)"},"_id":"17490","date_updated":"2026-10-02T11:20:06Z","researchdata_availability":"no","date_created":"2024-09-04T08:51:11Z","language":[{"iso":"eng"}],"oa_version":"Published Version","ec_funded":1,"status":"public","degree_awarded":"PhD","citation":{"ieee":"I. Markov, “Communication-efficient distributed training of deep neural networks : An algorithms and systems perspective,” Institute of Science and Technology Austria, 2024.","mla":"Markov, Ilia. <i>Communication-Efficient Distributed Training of Deep Neural Networks : An Algorithms and Systems Perspective</i>. Institute of Science and Technology Austria, 2024, doi:<a href=\"https://doi.org/10.15479/at:ista:17490\">10.15479/at:ista:17490</a>.","ama":"Markov I. Communication-efficient distributed training of deep neural networks : An algorithms and systems perspective. 2024. doi:<a href=\"https://doi.org/10.15479/at:ista:17490\">10.15479/at:ista:17490</a>","ista":"Markov I. 2024. Communication-efficient distributed training of deep neural networks : An algorithms and systems perspective. Institute of Science and Technology Austria.","short":"I. Markov, Communication-Efficient Distributed Training of Deep Neural Networks : An Algorithms and Systems Perspective, Institute of Science and Technology Austria, 2024.","chicago":"Markov, Ilia. “Communication-Efficient Distributed Training of Deep Neural Networks : An Algorithms and Systems Perspective.” Institute of Science and Technology Austria, 2024. <a href=\"https://doi.org/10.15479/at:ista:17490\">https://doi.org/10.15479/at:ista:17490</a>.","apa":"Markov, I. (2024). <i>Communication-efficient distributed training of deep neural networks : An algorithms and systems perspective</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/at:ista:17490\">https://doi.org/10.15479/at:ista:17490</a>"},"department":[{"_id":"GradSch"},{"_id":"DaAl"}],"page":"102","publication_status":"published","date_published":"2024-09-04T00:00:00Z","file":[{"file_name":"Thesis.zip","file_id":"17491","access_level":"closed","file_size":43327753,"content_type":"application/x-zip-compressed","creator":"imarkov","date_created":"2024-09-04T08:35:35Z","relation":"source_file","checksum":"77609f4835d2730e46fa0d42d9134ed9","date_updated":"2024-09-04T08:35:35Z"},{"file_id":"17492","access_level":"open_access","file_name":"Thesis_final_version_pdfa2.pdf","creator":"imarkov","date_created":"2024-09-04T08:36:06Z","success":1,"relation":"main_file","checksum":"9e68f7217570f756ceb8f70b980938cd","date_updated":"2024-09-04T08:36:06Z","file_size":2756082,"content_type":"application/pdf"}],"author":[{"full_name":"Markov, Ilia","last_name":"Markov","id":"D0CF4148-C985-11E9-8066-0BDEE5697425","first_name":"Ilia"}],"doi":"10.15479/at:ista:17490","title":"Communication-efficient distributed training of deep neural networks : An algorithms and systems perspective","das_tickbox":"0","file_date_updated":"2024-09-04T08:36:06Z"},{"day":"01","volume":6,"abstract":[{"text":"Data-parallel distributed training of deep neural networks (DNN) has gained very widespread adoption, but can still experience communication bottlenecks. To address this issue, entire families of compression mechanisms have been developed, including quantization, sparsification, and low-rank approximation, some of which are seeing significant practical adoption. Despite this progress, almost all known compression schemes apply compression uniformly across DNN layers, although layers are heterogeneous in terms of parameter count and their impact on model accuracy.In this work, we provide a general framework for adapting the degree of compression across the model's layers dynamically during training, improving the overall compression, while leading to substantial speedups, without sacrificing accuracy. Our framework, called L-GreCo, is based on an adaptive algorithm, which automatically picks the optimal compression parameters for model layers guaranteeing the best compression ratio while satisfying an error constraint. Extensive experiments over image classification and language modeling tasks shows that L-GreCo is effective across all existing families of compression methods, and achieves up to 2.5\r\n×\r\n training speedup and up to 5\r\n×\r\n compression improvement over efficient implementations of existing approaches, while recovering full accuracy. Moreover, L-GreCo is complementary to existing adaptive algorithms, improving their compression ratio by 50\\% and practical throughput by 66\\%. An anonymized implementation is available at https://github.com/LGrCo/L-GreCo.","lang":"eng"}],"publisher":"Association for Computing Machinery","corr_author":"1","ddc":["000"],"external_id":{"arxiv":["2210.17357"]},"publication":"Proceedings of Machine Learning and Systems ","oa":1,"article_processing_charge":"No","arxiv":1,"related_material":{"record":[{"id":"17490","status":"public","relation":"dissertation_contains"}]},"month":"04","type":"conference","supplementarymaterial":"no","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","conference":{"start_date":"2024-04-22","end_date":"2024-04-22","location":"Athens, Greece","name":"MLSys: Machine Learning and Systems"},"year":"2024","quality_controlled":"1","_id":"17456","date_updated":"2026-10-02T11:20:05Z","intvolume":"         6","date_created":"2024-08-22T08:29:25Z","researchdata_availability":"no","status":"public","department":[{"_id":"DaAl"}],"main_file_link":[{"open_access":"1","url":"https://proceedings.mlsys.org/paper_files/paper/2024/hash/9069a8976ff06f6443e7f4172990a580-Abstract-Conference.html"}],"citation":{"ieee":"I. Markov, K. Alimohammadi, E. Frantar, and D.-A. Alistarh, “L-GreCo: Layerwise-adaptive gradient compression for efficient data-parallel deep learning,” in <i>Proceedings of Machine Learning and Systems </i>, Athens, Greece, 2024, vol. 6.","ama":"Markov I, Alimohammadi K, Frantar E, Alistarh D-A. L-GreCo: Layerwise-adaptive gradient compression for efficient data-parallel deep learning. In: Gibbons P, Pekhimenko G, De Sa C, eds. <i>Proceedings of Machine Learning and Systems </i>. Vol 6. Association for Computing Machinery; 2024.","ista":"Markov I, Alimohammadi K, Frantar E, Alistarh D-A. 2024. L-GreCo: Layerwise-adaptive gradient compression for efficient data-parallel deep learning. Proceedings of Machine Learning and Systems . MLSys: Machine Learning and Systems vol. 6.","mla":"Markov, Ilia, et al. “L-GreCo: Layerwise-Adaptive Gradient Compression for Efficient Data-Parallel Deep Learning.” <i>Proceedings of Machine Learning and Systems </i>, edited by P. Gibbons et al., vol. 6, Association for Computing Machinery, 2024.","short":"I. Markov, K. Alimohammadi, E. Frantar, D.-A. Alistarh, in:, P. Gibbons, G. Pekhimenko, C. De Sa (Eds.), Proceedings of Machine Learning and Systems , Association for Computing Machinery, 2024.","apa":"Markov, I., Alimohammadi, K., Frantar, E., &#38; Alistarh, D.-A. (2024). L-GreCo: Layerwise-adaptive gradient compression for efficient data-parallel deep learning. In P. Gibbons, G. Pekhimenko, &#38; C. De Sa (Eds.), <i>Proceedings of Machine Learning and Systems </i> (Vol. 6). Athens, Greece: Association for Computing Machinery.","chicago":"Markov, Ilia, Kaveh Alimohammadi, Elias Frantar, and Dan-Adrian Alistarh. “L-GreCo: Layerwise-Adaptive Gradient Compression for Efficient Data-Parallel Deep Learning.” In <i>Proceedings of Machine Learning and Systems </i>, edited by P. Gibbons, G. Pekhimenko, and C. De Sa, Vol. 6. Association for Computing Machinery, 2024."},"editor":[{"full_name":"Gibbons, P.","last_name":"Gibbons","first_name":"P."},{"first_name":"G.","last_name":"Pekhimenko","full_name":"Pekhimenko, G."},{"last_name":"De Sa","first_name":"C.","full_name":"De Sa, C."}],"language":[{"iso":"eng"}],"oa_version":"Published Version","title":"L-GreCo: Layerwise-adaptive gradient compression for efficient data-parallel deep learning","das_tickbox":"0","date_published":"2024-04-01T00:00:00Z","publication_status":"published","author":[{"last_name":"Markov","id":"D0CF4148-C985-11E9-8066-0BDEE5697425","first_name":"Ilia","full_name":"Markov, Ilia"},{"first_name":"Kaveh","last_name":"Alimohammadi","full_name":"Alimohammadi, Kaveh"},{"full_name":"Frantar, Elias","last_name":"Frantar","id":"09a8f98d-ec99-11ea-ae11-c063a7b7fe5f","first_name":"Elias"},{"first_name":"Dan-Adrian","last_name":"Alistarh","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian"}]},{"OA_type":"green","date_published":"2024-12-20T00:00:00Z","author":[{"full_name":"Modoranu, Ionut-Vlad","last_name":"Modoranu","id":"449f7a18-f128-11eb-9611-9b430c0c6333","first_name":"Ionut-Vlad"},{"full_name":"Safaryan, Mher","id":"dd546b39-0804-11ed-9c55-ef075c39778d","last_name":"Safaryan","first_name":"Mher"},{"last_name":"Malinovsky","first_name":"Grigory","full_name":"Malinovsky, Grigory"},{"full_name":"Kurtic, Eldar","last_name":"Kurtic","id":"47beb3a5-07b5-11eb-9b87-b108ec578218","first_name":"Eldar"},{"first_name":"Thomas","id":"de632733-1457-11f0-ae22-b5914b8c1c41","last_name":"Robert","full_name":"Robert, Thomas"},{"full_name":"Richtárik, Peter","last_name":"Richtárik","first_name":"Peter"},{"last_name":"Alistarh","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian"}],"publication_status":"published","title":"MICROADAM: Accurate adaptive optimization with low space overhead and provable convergence","doi":"10.52202/079017-0001","ec_funded":1,"oa_version":"Preprint","language":[{"iso":"eng"}],"department":[{"_id":"DaAl"}],"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2405.15593","open_access":"1"}],"citation":{"ama":"Modoranu I-V, Safaryan M, Malinovsky G, et al. MICROADAM: Accurate adaptive optimization with low space overhead and provable convergence. In: <i>38th Conference on Neural Information Processing Systems</i>. Vol 37. Neural Information Processing Systems Foundation; 2024. doi:<a href=\"https://doi.org/10.52202/079017-0001\">10.52202/079017-0001</a>","ista":"Modoranu I-V, Safaryan M, Malinovsky G, Kurtic E, Robert T, Richtárik P, Alistarh D-A. 2024. MICROADAM: Accurate adaptive optimization with low space overhead and provable convergence. 38th Conference on Neural Information Processing Systems. , Advances in Neural Information Processing Systems, vol. 37.","mla":"Modoranu, Ionut-Vlad, et al. “MICROADAM: Accurate Adaptive Optimization with Low Space Overhead and Provable Convergence.” <i>38th Conference on Neural Information Processing Systems</i>, vol. 37, Neural Information Processing Systems Foundation, 2024, doi:<a href=\"https://doi.org/10.52202/079017-0001\">10.52202/079017-0001</a>.","ieee":"I.-V. Modoranu <i>et al.</i>, “MICROADAM: Accurate adaptive optimization with low space overhead and provable convergence,” in <i>38th Conference on Neural Information Processing Systems</i>, 2024, vol. 37.","apa":"Modoranu, I.-V., Safaryan, M., Malinovsky, G., Kurtic, E., Robert, T., Richtárik, P., &#38; Alistarh, D.-A. (2024). MICROADAM: Accurate adaptive optimization with low space overhead and provable convergence. In <i>38th Conference on Neural Information Processing Systems</i> (Vol. 37). Neural Information Processing Systems Foundation. <a href=\"https://doi.org/10.52202/079017-0001\">https://doi.org/10.52202/079017-0001</a>","chicago":"Modoranu, Ionut-Vlad, Mher Safaryan, Grigory Malinovsky, Eldar Kurtic, Thomas Robert, Peter Richtárik, and Dan-Adrian Alistarh. “MICROADAM: Accurate Adaptive Optimization with Low Space Overhead and Provable Convergence.” In <i>38th Conference on Neural Information Processing Systems</i>, Vol. 37. Neural Information Processing Systems Foundation, 2024. <a href=\"https://doi.org/10.52202/079017-0001\">https://doi.org/10.52202/079017-0001</a>.","short":"I.-V. Modoranu, M. Safaryan, G. Malinovsky, E. Kurtic, T. Robert, P. Richtárik, D.-A. Alistarh, in:, 38th Conference on Neural Information Processing Systems, Neural Information Processing Systems Foundation, 2024."},"status":"public","alternative_title":["Advances in Neural Information Processing Systems"],"intvolume":"        37","date_created":"2025-04-06T22:01:32Z","quality_controlled":"1","_id":"19510","date_updated":"2026-10-15T09:49:27Z","fulldoi":"https://doi.org/10.52202/079017-0001","project":[{"grant_number":"101034413","name":"IST-BRIDGE: International postdoctoral program","call_identifier":"H2020","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c"}],"year":"2024","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledged_ssus":[{"_id":"CampIT"}],"type":"conference","related_material":{"link":[{"url":"https://github.com/IST-DASLab/MicroAdam","relation":"software"}]},"month":"12","oa":1,"article_processing_charge":"No","arxiv":1,"OA_place":"repository","publication":"38th Conference on Neural Information Processing Systems","external_id":{"arxiv":["2405.15593"]},"acknowledgement":"The authors thank Razvan Pascanu, Mahdi Nikdan and Soroush Tabesh for their valuable feedback, the IT department from Institute of Science and Technology Austria for the hardware support and Weights and Biases for the infrastructure to track all our experiments. Mher Safaryan has received funding from the European Union’s Horizon 2020 research and innovation program under the Marie Sklodowska-Curie grant agreement No 101034413.","publisher":"Neural Information Processing Systems Foundation","corr_author":"1","publication_identifier":{"issn":["1049-5258"]},"abstract":[{"lang":"eng","text":"We propose a new variant of the Adam optimizer [Kingma and Ba, 2014] called\r\nMICROADAM that specifically minimizes memory overheads, while maintaining\r\ntheoretical convergence guarantees. We achieve this by compressing the gradient\r\ninformation before it is fed into the optimizer state, thereby reducing its memory\r\nfootprint significantly. We control the resulting compression error via a novel\r\ninstance of the classical error feedback mechanism from distributed optimization [Seide et al., 2014, Alistarh et al., 2018, Karimireddy et al., 2019] in which\r\nthe error correction information is itself compressed to allow for practical memory\r\ngains. We prove that the resulting approach maintains theoretical convergence\r\nguarantees competitive to those of AMSGrad, while providing good practical performance. Specifically, we show that MICROADAM can be implemented efficiently\r\non GPUs: on both million-scale (BERT) and billion-scale (LLaMA) models, MICROADAM provides practical convergence competitive to that of the uncompressed\r\nAdam baseline, with lower memory usage and similar running time. Our code is\r\navailable at https://github.com/IST-DASLab/MicroAdam."}],"scopus_import":"1","day":"20","volume":37},{"publisher":"Neural Information Processing Systems Foundation","day":"20","volume":37,"publication_identifier":{"issn":["1049-5258"]},"scopus_import":"1","abstract":[{"text":"We introduce QuaRot, a new Quantization scheme based on Rotations, which is able to quantize LLMs end-to-end, including all weights, activations, and KV cache in 4 bits. QuaRot rotates LLMs in a way that removes outliers from the hidden state without changing the output, making quantization easier. This computational invariance is applied to the hidden state (residual) of the LLM, as well as to the activations of the feed-forward components, aspects of the attention mechanism, and to the KV cache. The result is a quantized model where all matrix multiplications are performed in 4 bits, without any channels identified for retention in higher precision. Our 4-bit quantized LLAMA2-70B model has losses of at most 0.47 WikiText-2 perplexity and retains 99% of the zero-shot performance. We also show that QuaRot can provide lossless 6 and 8 bit LLAMA-2 models without any calibration data using round-to-nearest quantization. Code is available at github.com/spcl/QuaRot.","lang":"eng"}],"related_material":{"link":[{"url":"https://github.com/spcl/QuaRot","relation":"software"}]},"month":"12","external_id":{"arxiv":["2404.00456"]},"publication":"38th Conference on Neural Information Processing Systems","OA_place":"repository","oa":1,"arxiv":1,"article_processing_charge":"No","type":"conference","fulldoi":"https://doi.org/10.52202/079017-3180","conference":{"end_date":"2024-12-15","location":"Vancouver, Canada","name":"NeurIPS: Neural Information Processing Systems","start_date":"2024-12-09"},"year":"2024","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","alternative_title":["Advances in Neural Information Processing Systems"],"quality_controlled":"1","_id":"19511","date_updated":"2026-10-15T09:50:27Z","intvolume":"        37","date_created":"2025-04-06T22:01:32Z","language":[{"iso":"eng"}],"oa_version":"Preprint","status":"public","department":[{"_id":"DaAl"}],"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2404.00456","open_access":"1"}],"citation":{"apa":"Ashkboos, S., Mohtashami, A., Croci, M. L., Li, B., Cameron, P., Jaggi, M., … Hensman, J. (2024). QuaRot: Outlier-free 4-bit inference in rotated LLMs. In <i>38th Conference on Neural Information Processing Systems</i> (Vol. 37). Vancouver, Canada: Neural Information Processing Systems Foundation. <a href=\"https://doi.org/10.52202/079017-3180\">https://doi.org/10.52202/079017-3180</a>","chicago":"Ashkboos, Saleh, Amirkeivan Mohtashami, Maximilian L. Croci, Bo Li, Pashmina Cameron, Martin Jaggi, Dan-Adrian Alistarh, Torsten Hoefler, and James Hensman. “QuaRot: Outlier-Free 4-Bit Inference in Rotated LLMs.” In <i>38th Conference on Neural Information Processing Systems</i>, Vol. 37. Neural Information Processing Systems Foundation, 2024. <a href=\"https://doi.org/10.52202/079017-3180\">https://doi.org/10.52202/079017-3180</a>.","short":"S. Ashkboos, A. Mohtashami, M.L. Croci, B. Li, P. Cameron, M. Jaggi, D.-A. Alistarh, T. Hoefler, J. Hensman, in:, 38th Conference on Neural Information Processing Systems, Neural Information Processing Systems Foundation, 2024.","mla":"Ashkboos, Saleh, et al. “QuaRot: Outlier-Free 4-Bit Inference in Rotated LLMs.” <i>38th Conference on Neural Information Processing Systems</i>, vol. 37, Neural Information Processing Systems Foundation, 2024, doi:<a href=\"https://doi.org/10.52202/079017-3180\">10.52202/079017-3180</a>.","ista":"Ashkboos S, Mohtashami A, Croci ML, Li B, Cameron P, Jaggi M, Alistarh D-A, Hoefler T, Hensman J. 2024. QuaRot: Outlier-free 4-bit inference in rotated LLMs. 38th Conference on Neural Information Processing Systems. NeurIPS: Neural Information Processing Systems, Advances in Neural Information Processing Systems, vol. 37.","ama":"Ashkboos S, Mohtashami A, Croci ML, et al. QuaRot: Outlier-free 4-bit inference in rotated LLMs. In: <i>38th Conference on Neural Information Processing Systems</i>. Vol 37. Neural Information Processing Systems Foundation; 2024. doi:<a href=\"https://doi.org/10.52202/079017-3180\">10.52202/079017-3180</a>","ieee":"S. Ashkboos <i>et al.</i>, “QuaRot: Outlier-free 4-bit inference in rotated LLMs,” in <i>38th Conference on Neural Information Processing Systems</i>, Vancouver, Canada, 2024, vol. 37."},"publication_status":"published","author":[{"full_name":"Ashkboos, Saleh","last_name":"Ashkboos","first_name":"Saleh"},{"first_name":"Amirkeivan","last_name":"Mohtashami","full_name":"Mohtashami, Amirkeivan"},{"full_name":"Croci, Maximilian L.","last_name":"Croci","first_name":"Maximilian L."},{"full_name":"Li, Bo","first_name":"Bo","last_name":"Li"},{"full_name":"Cameron, Pashmina","first_name":"Pashmina","last_name":"Cameron"},{"last_name":"Jaggi","first_name":"Martin","full_name":"Jaggi, Martin"},{"first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X","last_name":"Alistarh","full_name":"Alistarh, Dan-Adrian"},{"first_name":"Torsten","last_name":"Hoefler","full_name":"Hoefler, Torsten"},{"full_name":"Hensman, James","last_name":"Hensman","first_name":"James"}],"date_published":"2024-12-20T00:00:00Z","title":"QuaRot: Outlier-free 4-bit inference in rotated LLMs","doi":"10.52202/079017-3180","OA_type":"green"},{"OA_place":"repository","oa":1,"article_processing_charge":"No","doi_confirm":"1","related_material":{"record":[{"relation":"part_of_dissertation","status":"public","id":"11420"},{"id":"14459","relation":"part_of_dissertation","status":"public"},{"relation":"part_of_dissertation","status":"public","id":"9198"},{"relation":"part_of_dissertation","status":"public","id":"17469"}]},"month":"08","day":"29","publication_identifier":{"issn":["2663-337X"]},"abstract":[{"text":"In the modern age of machine learning, artificial neural networks have become an integral part\r\nof many practical systems. One of the key ingredients of the success of the deep learning\r\napproach is recent computational advances which allowed the training of models with billions\r\nof parameters on large-scale data. Such over-parameterized and data-hungry regimes pose a\r\nchallenge for the theoretical analysis of modern models since “classical” statistical wisdom\r\nis no longer applicable. In this view, it is paramount to extend or develop new machinery\r\nthat will allow tackling the neural network analysis under new challenging asymptotic regimes,\r\nwhich is the focus of this thesis.\r\nLarge neural network systems are usually optimized via “local” search algorithms, such\r\nas stochastic gradient descent (SGD). However, given the high-dimensional nature of the\r\nparameter space, it is a priori not clear why such a crude “local” approach works so remarkably\r\nwell in practice. We take a step towards demystifying this phenomenon by showing that\r\nthe landscape of the SGD training dynamics exhibits a few beneficial properties for the\r\noptimization. First, we show that along the SGD trajectory an over-parameterized network\r\nis dropout stable. The emergence of dropout stability allows to conclude that the minima\r\nfound by SGD are connected via a continuous path of small loss. This in turn means that\r\nthe high-dimensional landscape of the neural network optimization problem is provably not so\r\nunfavourable to gradient-based training, due to mode connectivity. Next, we show that SGD\r\nfor an over-parameterized network tends to find solutions that are functionally more “simple”.\r\nThis in turn means that the SGD minima are more robust, since a less complicated solution\r\nwill less likely overfit the data. More formally, for a prototypical example of a wide two-layer\r\nReLU network on a 1d regression task we show that the SGD algorithm is implicitly selective in\r\nits choice of an interpolating solution. Namely, at convergence the neural network implements\r\na piece-wise linear function with the number of linear regions depending only on the amount\r\nof training data. This is in contrast to a “smooth”-like behaviour which one would expect\r\ngiven such a severe over-parameterization of the model.\r\nDiverging from the generic supervised setting of classification and regression problems, we\r\nanalyze an auto-encoder model that is commonly used for representation learning and data\r\ncompression. Despite the wide applicability of the auto-encoding paradigm, the theoretical\r\nunderstanding of their behaviour is limited even in the simplistic shallow case. The related\r\nwork is restricted to extreme asymptotic regimes in which the auto-encoder is either severely\r\nover-parameterized or under-parameterized. In contrast, we provide a tight characterization\r\nfor the 1-bit compression of Gaussian signals in the challenging proportional regime, i.e., the\r\ninput dimension and the size of the compressed representation obey the same asymptotics.\r\nWe also show that gradient-based methods are able to find a globally optimal solution and\r\nthat the predictions made for Gaussian data extrapolate beyond - to the case of compression\r\nof natural images. Next, we relax the Gaussian assumption and study more structured input\r\nsources. We show that the shallow model is sometimes agnostic to the structure of the data\r\nvii\r\nwhich results in a Gaussian-like behaviour. We prove that making the decoding component\r\nslightly less shallow is already enough to escape the “curse” of Gaussian performance.\r\n","lang":"eng"}],"corr_author":"1","publisher":"Institute of Science and Technology Austria","has_accepted_license":"1","ddc":["519"],"supplementarymaterial":"no","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","project":[{"_id":"059876FA-7A3F-11EA-A408-12923DDC885E","name":"Prix Lopez-Loretta 2019 - Marco Mondelli"},{"name":"Vienna Graduate School on Computational Optimization","_id":"9B9290DE-BA93-11EA-9121-9846C619BF3A","grant_number":"W1260-N35"}],"fulldoi":"https://doi.org/10.15479/at:ista:17465","supervisor":[{"id":"27EB676C-8706-11E9-9510-7717E6697425","last_name":"Mondelli","orcid":"0000-0002-3242-7020","first_name":"Marco","full_name":"Mondelli, Marco"},{"full_name":"Alistarh, Dan-Adrian","first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","last_name":"Alistarh","orcid":"0000-0003-3650-940X"}],"year":"2024","type":"dissertation","acknowledged_ssus":[{"_id":"ScienComp"}],"degree_awarded":"PhD","status":"public","department":[{"_id":"GradSch"},{"_id":"DaAl"},{"_id":"MaMo"}],"citation":{"ieee":"A. Shevchenko, “High-dimensional limits in artificial neural networks,” Institute of Science and Technology Austria, 2024.","mla":"Shevchenko, Alexander. <i>High-Dimensional Limits in Artificial Neural Networks</i>. Institute of Science and Technology Austria, 2024, doi:<a href=\"https://doi.org/10.15479/at:ista:17465\">10.15479/at:ista:17465</a>.","ama":"Shevchenko A. High-dimensional limits in artificial neural networks. 2024. doi:<a href=\"https://doi.org/10.15479/at:ista:17465\">10.15479/at:ista:17465</a>","ista":"Shevchenko A. 2024. High-dimensional limits in artificial neural networks. Institute of Science and Technology Austria.","short":"A. Shevchenko, High-Dimensional Limits in Artificial Neural Networks, Institute of Science and Technology Austria, 2024.","chicago":"Shevchenko, Alexander. “High-Dimensional Limits in Artificial Neural Networks.” Institute of Science and Technology Austria, 2024. <a href=\"https://doi.org/10.15479/at:ista:17465\">https://doi.org/10.15479/at:ista:17465</a>.","apa":"Shevchenko, A. (2024). <i>High-dimensional limits in artificial neural networks</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/at:ista:17465\">https://doi.org/10.15479/at:ista:17465</a>"},"language":[{"iso":"eng"}],"oa_version":"Published Version","date_updated":"2026-10-02T11:20:32Z","_id":"17465","researchdata_availability":"no","date_created":"2024-08-28T15:14:25Z","alternative_title":["ISTA Thesis"],"title":"High-dimensional limits in artificial neural networks","file_date_updated":"2024-10-05T22:30:05Z","das_tickbox":"0","doi":"10.15479/at:ista:17465","date_published":"2024-08-29T00:00:00Z","file":[{"file_id":"17482","access_level":"open_access","file_name":"thesis_a2b.pdf","date_created":"2024-09-02T09:23:32Z","creator":"ashevche","checksum":"da6dd3166078934577f6af93d27000e2","date_updated":"2024-10-05T22:30:05Z","relation":"main_file","file_size":4468610,"content_type":"application/pdf","embargo":"2024-10-04"},{"file_id":"17483","access_level":"closed","file_name":"Thesis Alex - ISTA.zip","date_created":"2024-09-02T09:23:46Z","creator":"ashevche","checksum":"76a39ef252239560923cdda4ce0a31a4","embargo_to":"open_access","date_updated":"2024-10-05T22:30:05Z","relation":"source_file","content_type":"application/zip","file_size":15930999}],"author":[{"full_name":"Shevchenko, Aleksandr","first_name":"Aleksandr","id":"F2B06EC2-C99E-11E9-89F0-752EE6697425","last_name":"Shevchenko"}],"publication_status":"published","page":"232"},{"type":"conference","year":"2024","conference":{"name":"ICML: International Conference on Machine Learning","location":"Vienna, Austria","end_date":"2024-07-27","start_date":"2024-07-21"},"project":[{"name":"Prix Lopez-Loretta 2019 - Marco Mondelli","_id":"059876FA-7A3F-11EA-A408-12923DDC885E"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","supplementarymaterial":"no","publisher":"ML Research Press","corr_author":"1","ddc":["000"],"acknowledgement":"Kevin Kogler, Alexander Shevchenko and Marco Mondelli are supported by the 2019 Lopez-Loreta Prize. Hamed\r\nHassani acknowledges the support by the NSF CIF award (1910056) and the NSF Institute for CORE Emerging Methods in Data Science (EnCORE).","volume":235,"day":"01","abstract":[{"lang":"eng","text":"Autoencoders are a prominent model in many empirical branches of machine learning and lossy data compression. However, basic theoretical questions remain unanswered even in a shallow two-layer setting. In particular, to what degree does a shallow autoencoder capture the structure of the underlying data distribution? For the prototypical case of the 1-bit compression of sparse Gaussian data, we prove that gradient descent converges to a solution that completely disregards the sparse structure of the input. Namely, the performance of the algorithm is the same as if it was compressing a Gaussian source - with no sparsity. For general data distributions, we give evidence of a phase transition phenomenon in the shape of the gradient descent minimizer, as a function of the data sparsity: below the critical sparsity level, the minimizer is a rotation taken uniformly at random (just like in the compression of non-sparse data); above the critical sparsity, the minimizer is the identity (up to a permutation). Finally, by exploiting a connection with approximate message passing algorithms, we show how to improve upon Gaussian performance for the compression of sparse data: adding a denoising function to a shallow architecture already reduces the loss provably, and a suitable multi-layer decoder leads to a further improvement. We validate our findings on image datasets, such as CIFAR-10 and MNIST."}],"scopus_import":"1","month":"07","related_material":{"record":[{"id":"23072","status":"public","relation":"dissertation_contains"},{"id":"17465","relation":"dissertation_contains","status":"public"}]},"publication":"Proceedings of the 41st International Conference on Machine Learning","external_id":{"arxiv":["2402.05013"]},"article_processing_charge":"No","arxiv":1,"oa":1,"page":"24964-25015","publication_status":"published","date_published":"2024-07-01T00:00:00Z","author":[{"last_name":"Kögler","id":"94ec913c-dc85-11ea-9058-e5051ab2428b","first_name":"Kevin","full_name":"Kögler, Kevin"},{"first_name":"Aleksandr","last_name":"Shevchenko","id":"F2B06EC2-C99E-11E9-89F0-752EE6697425","full_name":"Shevchenko, Aleksandr"},{"full_name":"Hassani, Hamed","last_name":"Hassani","first_name":"Hamed"},{"first_name":"Marco","last_name":"Mondelli","orcid":"0000-0002-3242-7020","id":"27EB676C-8706-11E9-9510-7717E6697425","full_name":"Mondelli, Marco"}],"title":"Compression of structured data with autoencoders: Provable benefit of nonlinearities and depth","das_tickbox":"0","alternative_title":["PMLR"],"_id":"17469","date_updated":"2026-11-02T23:31:00Z","quality_controlled":"1","date_created":"2024-08-29T11:47:57Z","researchdata_availability":"no","intvolume":"       235","language":[{"iso":"eng"}],"oa_version":"Published Version","status":"public","citation":{"ieee":"K. Kögler, A. Shevchenko, H. Hassani, and M. Mondelli, “Compression of structured data with autoencoders: Provable benefit of nonlinearities and depth,” in <i>Proceedings of the 41st International Conference on Machine Learning</i>, Vienna, Austria, 2024, vol. 235, pp. 24964–25015.","mla":"Kögler, Kevin, et al. “Compression of Structured Data with Autoencoders: Provable Benefit of Nonlinearities and Depth.” <i>Proceedings of the 41st International Conference on Machine Learning</i>, vol. 235, ML Research Press, 2024, pp. 24964–5015.","ista":"Kögler K, Shevchenko A, Hassani H, Mondelli M. 2024. Compression of structured data with autoencoders: Provable benefit of nonlinearities and depth. Proceedings of the 41st International Conference on Machine Learning. ICML: International Conference on Machine Learning, PMLR, vol. 235, 24964–25015.","ama":"Kögler K, Shevchenko A, Hassani H, Mondelli M. Compression of structured data with autoencoders: Provable benefit of nonlinearities and depth. In: <i>Proceedings of the 41st International Conference on Machine Learning</i>. Vol 235. ML Research Press; 2024:24964-25015.","short":"K. Kögler, A. Shevchenko, H. Hassani, M. Mondelli, in:, Proceedings of the 41st International Conference on Machine Learning, ML Research Press, 2024, pp. 24964–25015.","apa":"Kögler, K., Shevchenko, A., Hassani, H., &#38; Mondelli, M. (2024). Compression of structured data with autoencoders: Provable benefit of nonlinearities and depth. In <i>Proceedings of the 41st International Conference on Machine Learning</i> (Vol. 235, pp. 24964–25015). Vienna, Austria: ML Research Press.","chicago":"Kögler, Kevin, Alexander Shevchenko, Hamed Hassani, and Marco Mondelli. “Compression of Structured Data with Autoencoders: Provable Benefit of Nonlinearities and Depth.” In <i>Proceedings of the 41st International Conference on Machine Learning</i>, 235:24964–15. ML Research Press, 2024."},"main_file_link":[{"url":"https://proceedings.mlr.press/v235/kogler24a.html","open_access":"1"}],"department":[{"_id":"DaAl"},{"_id":"MaMo"}]},{"volume":36,"day":"01","abstract":[{"lang":"eng","text":"The design and implementation of efficient concurrent data structures has seen significant attention. However, most of this work has focused on concurrent data structures providing good worst-case guarantees, although, in real workloads, objects are often accessed at different rates. Efficient distribution-adaptive data structures, such as splay-trees, are known in the sequential case; however, they often are hard to translate efficiently to the concurrent case. We investigate distribution-adaptive concurrent data structures, and propose a new design called the splay-list. At a high level, the splay-list is similar to a standard skip-list, with the key distinction that the height of each element adapts dynamically to its access rate: popular elements “move up,” whereas rarely-accessed elements decrease in height. We show that the splay-list provides order-optimal amortized complexity bounds for a subset of operations, while being amenable to efficient concurrent implementation. Experiments show that the splay-list can leverage distribution-adaptivity for performance, and can outperform the only previously-known distribution-adaptive concurrent design in certain workloads."}],"scopus_import":"1","publication_identifier":{"issn":["0178-2770"],"eissn":["1432-0452"]},"publisher":"Springer Nature","publication":"Distributed Computing","external_id":{"arxiv":["2008.01009"],"isi":["000913424000001"]},"article_processing_charge":"No","arxiv":1,"oa":1,"month":"09","type":"journal_article","article_type":"original","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2023","fulldoi":"https://doi.org/10.1007/s00446-022-00441-x","date_updated":"2023-08-14T12:54:32Z","_id":"12330","quality_controlled":"1","date_created":"2023-01-22T23:00:55Z","intvolume":"        36","status":"public","citation":{"mla":"Aksenov, Vitalii, et al. “The Splay-List: A Distribution-Adaptive Concurrent Skip-List.” <i>Distributed Computing</i>, vol. 36, Springer Nature, 2023, pp. 395–418, doi:<a href=\"https://doi.org/10.1007/s00446-022-00441-x\">10.1007/s00446-022-00441-x</a>.","ama":"Aksenov V, Alistarh D-A, Drozdova A, Mohtashami A. The splay-list: A distribution-adaptive concurrent skip-list. <i>Distributed Computing</i>. 2023;36:395-418. doi:<a href=\"https://doi.org/10.1007/s00446-022-00441-x\">10.1007/s00446-022-00441-x</a>","ista":"Aksenov V, Alistarh D-A, Drozdova A, Mohtashami A. 2023. The splay-list: A distribution-adaptive concurrent skip-list. Distributed Computing. 36, 395–418.","ieee":"V. Aksenov, D.-A. Alistarh, A. Drozdova, and A. Mohtashami, “The splay-list: A distribution-adaptive concurrent skip-list,” <i>Distributed Computing</i>, vol. 36. Springer Nature, pp. 395–418, 2023.","apa":"Aksenov, V., Alistarh, D.-A., Drozdova, A., &#38; Mohtashami, A. (2023). The splay-list: A distribution-adaptive concurrent skip-list. <i>Distributed Computing</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00446-022-00441-x\">https://doi.org/10.1007/s00446-022-00441-x</a>","chicago":"Aksenov, Vitalii, Dan-Adrian Alistarh, Alexandra Drozdova, and Amirkeivan Mohtashami. “The Splay-List: A Distribution-Adaptive Concurrent Skip-List.” <i>Distributed Computing</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s00446-022-00441-x\">https://doi.org/10.1007/s00446-022-00441-x</a>.","short":"V. Aksenov, D.-A. Alistarh, A. Drozdova, A. Mohtashami, Distributed Computing 36 (2023) 395–418."},"department":[{"_id":"DaAl"}],"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2008.01009","open_access":"1"}],"language":[{"iso":"eng"}],"oa_version":"Preprint","doi":"10.1007/s00446-022-00441-x","isi":1,"title":"The splay-list: A distribution-adaptive concurrent skip-list","page":"395-418","author":[{"full_name":"Aksenov, Vitalii","first_name":"Vitalii","last_name":"Aksenov","id":"2980135A-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Alistarh","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian"},{"full_name":"Drozdova, Alexandra","last_name":"Drozdova","first_name":"Alexandra"},{"last_name":"Mohtashami","first_name":"Amirkeivan","full_name":"Mohtashami, Amirkeivan"}],"date_published":"2023-09-01T00:00:00Z","publication_status":"published"},{"month":"02","publication":"Theoretical Computer Science","external_id":{"isi":["000934262700001"]},"oa":1,"article_processing_charge":"Yes (via OA deal)","publisher":"Elsevier","corr_author":"1","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 under the Marie Skłodowska-Curie grant agreement No. 840605 and from the Natural Sciences and Engineering Research Council of Canada grant RGPIN-2020-04178. Part of this work was done while Faith Ellen was visiting IST Austria.","has_accepted_license":"1","ddc":["000"],"day":"28","volume":948,"publication_identifier":{"issn":["0304-3975"]},"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 node of the graph as input and, if non-faulty, must output a node such that\r\n– all the outputs are within distance 1 of one another, and\r\n– each output value lies on a shortest path between two input values.\r\nFrom prior work, it is known that there is no wait-free algorithm among  processes for this problem on any cycle of length , by reduction from 2-set agreement (Castañeda et al., 2018).\r\n\r\nIn this work, we investigate the solvability of this task on general graphs. We give a new, direct proof of the impossibility of approximate agreement on cycles of length , 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 different class of graphs, which properly contains the class of chordal graphs."}],"scopus_import":"1","fulldoi":"https://doi.org/10.1016/j.tcs.2023.113733","project":[{"_id":"268A44D6-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Elastic Coordination for Scalable Machine Learning","grant_number":"805223"},{"grant_number":"840605","name":"Coordination in constrained and natural distributed systems","_id":"26A5D39A-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"year":"2023","issue":"2","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","article_type":"original","type":"journal_article","language":[{"iso":"eng"}],"ec_funded":1,"oa_version":"Published Version","status":"public","department":[{"_id":"DaAl"}],"citation":{"apa":"Alistarh, D.-A., Ellen, F., &#38; Rybicki, J. (2023). Wait-free approximate agreement on graphs. <i>Theoretical Computer Science</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.tcs.2023.113733\">https://doi.org/10.1016/j.tcs.2023.113733</a>","chicago":"Alistarh, Dan-Adrian, Faith Ellen, and Joel Rybicki. “Wait-Free Approximate Agreement on Graphs.” <i>Theoretical Computer Science</i>. Elsevier, 2023. <a href=\"https://doi.org/10.1016/j.tcs.2023.113733\">https://doi.org/10.1016/j.tcs.2023.113733</a>.","short":"D.-A. Alistarh, F. Ellen, J. Rybicki, Theoretical Computer Science 948 (2023).","ama":"Alistarh D-A, Ellen F, Rybicki J. Wait-free approximate agreement on graphs. <i>Theoretical Computer Science</i>. 2023;948(2). doi:<a href=\"https://doi.org/10.1016/j.tcs.2023.113733\">10.1016/j.tcs.2023.113733</a>","ista":"Alistarh D-A, Ellen F, Rybicki J. 2023. Wait-free approximate agreement on graphs. Theoretical Computer Science. 948(2), 113733.","mla":"Alistarh, Dan-Adrian, et al. “Wait-Free Approximate Agreement on Graphs.” <i>Theoretical Computer Science</i>, vol. 948, no. 2, 113733, Elsevier, 2023, doi:<a href=\"https://doi.org/10.1016/j.tcs.2023.113733\">10.1016/j.tcs.2023.113733</a>.","ieee":"D.-A. Alistarh, F. Ellen, and J. Rybicki, “Wait-free approximate agreement on graphs,” <i>Theoretical Computer Science</i>, vol. 948, no. 2. Elsevier, 2023."},"article_number":"113733","quality_controlled":"1","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"},"_id":"12566","date_updated":"2025-04-14T07:49:16Z","intvolume":"       948","date_created":"2023-02-19T23:00:55Z","publication_status":"published","author":[{"full_name":"Alistarh, Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","last_name":"Alistarh","orcid":"0000-0003-3650-940X","first_name":"Dan-Adrian"},{"first_name":"Faith","last_name":"Ellen","full_name":"Ellen, Faith"},{"id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","last_name":"Rybicki","orcid":"0000-0002-6432-6646","first_name":"Joel","full_name":"Rybicki, Joel"}],"file":[{"access_level":"open_access","file_id":"12570","file_name":"2023_TheoreticalCompScience_Alistarh.pdf","date_updated":"2023-02-20T07:30:20Z","checksum":"b27c5290f2f1500c403494364ee39c9f","relation":"main_file","success":1,"date_created":"2023-02-20T07:30:20Z","creator":"dernst","file_size":602333,"content_type":"application/pdf"}],"date_published":"2023-02-28T00:00:00Z","file_date_updated":"2023-02-20T07:30:20Z","isi":1,"title":"Wait-free approximate agreement on graphs","doi":"10.1016/j.tcs.2023.113733"},{"status":"public","department":[{"_id":"DaAl"}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2211.04986"}],"citation":{"short":"N. Koval, D.-A. Alistarh, R. Elizarov, in:, Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Association for Computing Machinery, 2023, pp. 107–118.","apa":"Koval, N., Alistarh, D.-A., &#38; Elizarov, R. (2023). Fast and scalable channels in Kotlin Coroutines. In <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i> (pp. 107–118). Montreal, QC, Canada: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3572848.3577481\">https://doi.org/10.1145/3572848.3577481</a>","chicago":"Koval, Nikita, Dan-Adrian Alistarh, and Roman Elizarov. “Fast and Scalable Channels in Kotlin Coroutines.” In <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>, 107–18. Association for Computing Machinery, 2023. <a href=\"https://doi.org/10.1145/3572848.3577481\">https://doi.org/10.1145/3572848.3577481</a>.","ieee":"N. Koval, D.-A. Alistarh, and R. Elizarov, “Fast and scalable channels in Kotlin Coroutines,” in <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>, Montreal, QC, Canada, 2023, pp. 107–118.","mla":"Koval, Nikita, et al. “Fast and Scalable Channels in Kotlin Coroutines.” <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>, Association for Computing Machinery, 2023, pp. 107–18, doi:<a href=\"https://doi.org/10.1145/3572848.3577481\">10.1145/3572848.3577481</a>.","ama":"Koval N, Alistarh D-A, Elizarov R. Fast and scalable channels in Kotlin Coroutines. In: <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>. Association for Computing Machinery; 2023:107-118. doi:<a href=\"https://doi.org/10.1145/3572848.3577481\">10.1145/3572848.3577481</a>","ista":"Koval N, Alistarh D-A, Elizarov R. 2023. Fast and scalable channels in Kotlin Coroutines. Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. PPoPP: Sympopsium on Principles and Practice of Parallel Programming, 107–118."},"language":[{"iso":"eng"}],"oa_version":"Preprint","quality_controlled":"1","_id":"12735","date_updated":"2023-03-20T07:29:28Z","date_created":"2023-03-19T23:00:58Z","title":"Fast and scalable channels in Kotlin Coroutines","doi":"10.1145/3572848.3577481","author":[{"full_name":"Koval, Nikita","first_name":"Nikita","id":"2F4DB10C-F248-11E8-B48F-1D18A9856A87","last_name":"Koval"},{"full_name":"Alistarh, Dan-Adrian","first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X","last_name":"Alistarh"},{"first_name":"Roman","last_name":"Elizarov","full_name":"Elizarov, Roman"}],"publication_status":"published","date_published":"2023-02-25T00:00:00Z","page":"107-118","publication":"Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming","external_id":{"arxiv":["2211.04986"]},"oa":1,"arxiv":1,"article_processing_charge":"No","month":"02","day":"25","publication_identifier":{"isbn":["9798400700156"]},"scopus_import":"1","abstract":[{"text":"Asynchronous programming has gained significant popularity over the last decade: support for this programming pattern is available in many popular languages via libraries and native language implementations, typically in the form of coroutines or the async/await construct. Instead of programming via shared memory, this concept assumes implicit synchronization through message passing. The key data structure enabling such communication is the rendezvous channel. Roughly, a rendezvous channel is a blocking queue of size zero, so both send(e) and receive() operations wait for each other, performing a rendezvous when they meet. To optimize the message passing pattern, channels are usually equipped with a fixed-size buffer, so sends do not suspend and put elements into the buffer until its capacity is exceeded. This primitive is known as a buffered channel.\r\n\r\nThis paper presents a fast and scalable algorithm for both rendezvous and buffered channels. Similarly to modern queues, our solution is based on an infinite array with two positional counters for send(e) and receive() operations, leveraging the unconditional Fetch-And-Add instruction to update them. Yet, the algorithm requires non-trivial modifications of this classic pattern, in order to support the full channel semantics, such as buffering and cancellation of waiting requests. We compare the performance of our solution to that of the Kotlin implementation, as well as against other academic proposals, showing up to 9.8× speedup. To showcase its expressiveness and performance, we also integrated the proposed algorithm into the standard Kotlin Coroutines library, replacing the previous channel implementations.","lang":"eng"}],"publisher":"Association for Computing Machinery","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"start_date":"2023-02-25","end_date":"2023-03-01","location":"Montreal, QC, Canada","name":"PPoPP: Sympopsium on Principles and Practice of Parallel Programming"},"fulldoi":"https://doi.org/10.1145/3572848.3577481","year":"2023","type":"conference"},{"page":"438-440","author":[{"full_name":"Aksenov, Vitaly","first_name":"Vitaly","last_name":"Aksenov"},{"first_name":"Trevor A","last_name":"Brown","id":"3569F0A0-F248-11E8-B48F-1D18A9856A87","full_name":"Brown, Trevor A"},{"first_name":"Alexander","id":"2e711909-896a-11ed-bdf8-eb0f5a2984c6","last_name":"Fedorov","full_name":"Fedorov, Alexander"},{"first_name":"Ilya","last_name":"Kokorin","full_name":"Kokorin, Ilya"}],"publication_status":"published","date_published":"2023-02-25T00:00:00Z","doi":"10.1145/3572848.3577512","title":"Unexpected scaling in path copying trees","date_created":"2023-03-19T23:00:58Z","_id":"12736","date_updated":"2026-06-18T17:29:03Z","quality_controlled":"1","oa_version":"Published Version","language":[{"iso":"eng"}],"citation":{"short":"V. Aksenov, T.A. Brown, A. Fedorov, I. Kokorin, Unexpected Scaling in Path Copying Trees, Association for Computing Machinery, 2023.","apa":"Aksenov, V., Brown, T. A., Fedorov, A., &#38; Kokorin, I. (2023). <i>Unexpected scaling in path copying trees</i>. <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i> (pp. 438–440). Montreal, QB, Canada: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3572848.3577512\">https://doi.org/10.1145/3572848.3577512</a>","chicago":"Aksenov, Vitaly, Trevor A Brown, Alexander Fedorov, and Ilya Kokorin. <i>Unexpected Scaling in Path Copying Trees</i>. <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>. Association for Computing Machinery, 2023. <a href=\"https://doi.org/10.1145/3572848.3577512\">https://doi.org/10.1145/3572848.3577512</a>.","ieee":"V. Aksenov, T. A. Brown, A. Fedorov, and I. Kokorin, <i>Unexpected scaling in path copying trees</i>. Association for Computing Machinery, 2023, pp. 438–440.","mla":"Aksenov, Vitaly, et al. “Unexpected Scaling in Path Copying Trees.” <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>, Association for Computing Machinery, 2023, pp. 438–40, doi:<a href=\"https://doi.org/10.1145/3572848.3577512\">10.1145/3572848.3577512</a>.","ista":"Aksenov V, Brown TA, Fedorov A, Kokorin I. 2023. Unexpected scaling in path copying trees, Association for Computing Machinery,p.","ama":"Aksenov V, Brown TA, Fedorov A, Kokorin I. <i>Unexpected Scaling in Path Copying Trees</i>. Association for Computing Machinery; 2023:438-440. doi:<a href=\"https://doi.org/10.1145/3572848.3577512\">10.1145/3572848.3577512</a>"},"main_file_link":[{"open_access":"1","url":"https://doi.org/10.1145/3572848.3577512"}],"department":[{"_id":"DaAl"},{"_id":"GradSch"}],"status":"public","type":"conference_poster","year":"2023","fulldoi":"https://doi.org/10.1145/3572848.3577512","conference":{"location":"Montreal, QB, Canada","name":"PPoPP: Sympopsium on Principles and Practice of Parallel Programming","end_date":"2023-03-01","start_date":"2023-02-25"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000"],"acknowledgement":"This work was supported by: the Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery Program grant: RGPIN-2019-04227, and the Canada Foundation for Innovation John R. Evans Leaders Fund (CFI-JELF) with equal support from the Ontario Research Fund CFI Leaders Opportunity Fund: 38512.","publisher":"Association for Computing Machinery","scopus_import":"1","abstract":[{"text":"Although a wide variety of handcrafted concurrent data structures have been proposed, there is considerable interest in universal approaches (Universal Constructions or UCs) for building concurrent data structures. UCs (semi-)automatically convert a sequential data structure into a concurrent one. The simplest approach uses locks [3, 6] that protect a sequential data structure and allow only one process to access it at a time. However, the resulting data structure is blocking. Most work on UCs instead focuses on obtaining non-blocking progress guarantees such as obstruction-freedom, lock-freedom or wait-freedom. Many non-blocking UCs have appeared. Key examples include the seminal wait-free UC [2] by Herlihy, a NUMA-aware UC [10] by Yi et al., and an efficient UC for large objects [1] by Fatourou et al.","lang":"eng"}],"publication_identifier":{"isbn":["9798400700156"]},"day":"25","month":"02","article_processing_charge":"No","oa":1,"publication":"Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming"},{"oa":1,"article_processing_charge":"No","arxiv":1,"external_id":{"arxiv":["2207.14200"]},"publication":"11th International Conference on Learning Representations ","related_material":{"record":[{"id":"13074","status":"public","relation":"dissertation_contains"}],"link":[{"relation":"software","url":"https://github.com/IST-DASLab/CrAM"}]},"month":"05","abstract":[{"text":"Deep neural networks (DNNs) often have to be compressed, via pruning and/or quantization, before they can be deployed in practical settings. In this work we propose a new compression-aware minimizer dubbed CrAM that modifies the optimization step in a principled way, in order to produce models whose local loss behavior is stable under compression operations such as pruning. Thus, dense models trained via CrAM should be compressible post-training, in a single step, without significant accuracy loss. Experimental results on standard benchmarks, such as residual networks for ImageNet classification and BERT models for language modelling, show that CrAM produces dense models that can be more accurate than the standard SGD/Adam-based baselines, but which are stable under weight pruning: specifically, we can prune models in one-shot to 70-80% sparsity with almost no accuracy loss, and to 90% with reasonable (∼1%) accuracy loss, which is competitive with gradual compression methods. Additionally, CrAM can produce sparse models which perform well for transfer learning, and it also works for semi-structured 2:4 pruning patterns supported by GPU hardware. The code for reproducing the results is available at this https URL .","lang":"eng"}],"day":"01","acknowledgement":"AP, EK, DA received funding from the European Research Council (ERC) under the European\r\nUnion’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML). AV acknowledges the support of the French Agence Nationale de la Recherche (ANR), under grant ANR-21-CE48-0016 (project COMCOPT). We further acknowledge the support from the Scientific Service Units (SSU) of ISTA through resources provided by Scientific Computing (SciComp).","ddc":["000"],"has_accepted_license":"1","corr_author":"1","publisher":"OpenReview","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","project":[{"name":"Elastic Coordination for Scalable Machine Learning","call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425","grant_number":"805223"}],"conference":{"name":"ICLR: International Conference on Learning Representations","location":"Kigali, Rwanda ","end_date":"2023-05-05","start_date":"2023-05-01"},"year":"2023","type":"conference","acknowledged_ssus":[{"_id":"ScienComp"}],"main_file_link":[{"url":"https://openreview.net/pdf?id=_eTZBs-yedr","open_access":"1"}],"department":[{"_id":"GradSch"},{"_id":"DaAl"},{"_id":"ChLa"}],"citation":{"ieee":"A. Krumes, A. Vladu, E. Kurtic, C. Lampert, and D.-A. Alistarh, “CrAM: A Compression-Aware Minimizer,” in <i>11th International Conference on Learning Representations </i>, Kigali, Rwanda , 2023.","mla":"Krumes, Alexandra, et al. “CrAM: A Compression-Aware Minimizer.” <i>11th International Conference on Learning Representations </i>, OpenReview, 2023.","ama":"Krumes A, Vladu A, Kurtic E, Lampert C, Alistarh D-A. CrAM: A Compression-Aware Minimizer. In: <i>11th International Conference on Learning Representations </i>. OpenReview; 2023.","ista":"Krumes A, Vladu A, Kurtic E, Lampert C, Alistarh D-A. 2023. CrAM: A Compression-Aware Minimizer. 11th International Conference on Learning Representations . ICLR: International Conference on Learning Representations.","short":"A. Krumes, A. Vladu, E. Kurtic, C. Lampert, D.-A. Alistarh, in:, 11th International Conference on Learning Representations , OpenReview, 2023.","chicago":"Krumes, Alexandra, Adrian Vladu, Eldar Kurtic, Christoph Lampert, and Dan-Adrian Alistarh. “CrAM: A Compression-Aware Minimizer.” In <i>11th International Conference on Learning Representations </i>. OpenReview, 2023.","apa":"Krumes, A., Vladu, A., Kurtic, E., Lampert, C., &#38; Alistarh, D.-A. (2023). CrAM: A Compression-Aware Minimizer. In <i>11th International Conference on Learning Representations </i>. Kigali, Rwanda : OpenReview."},"status":"public","ec_funded":1,"oa_version":"Published Version","language":[{"iso":"eng"}],"date_created":"2023-05-23T11:36:18Z","quality_controlled":"1","_id":"13053","date_updated":"2026-04-07T13:30:19Z","file_date_updated":"2024-07-22T09:09:45Z","title":"CrAM: A Compression-Aware Minimizer","author":[{"id":"32D78294-F248-11E8-B48F-1D18A9856A87","last_name":"Peste","first_name":"Elena-Alexandra","full_name":"Peste, Elena-Alexandra"},{"first_name":"Adrian","last_name":"Vladu","full_name":"Vladu, Adrian"},{"id":"47beb3a5-07b5-11eb-9b87-b108ec578218","last_name":"Kurtic","first_name":"Eldar","full_name":"Kurtic, Eldar"},{"id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8622-7887","last_name":"Lampert","first_name":"Christoph","full_name":"Lampert, Christoph"},{"orcid":"0000-0003-3650-940X","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian"}],"publication_status":"published","file":[{"date_updated":"2024-07-22T09:09:45Z","checksum":"a6eec897e13a91cdc3eeaf309801752c","relation":"main_file","success":1,"date_created":"2024-07-22T09:09:45Z","creator":"dernst","content_type":"application/pdf","file_size":458201,"access_level":"open_access","file_id":"17294","file_name":"2023_ICLR_Peste.pdf"}],"date_published":"2023-05-01T00:00:00Z"},{"title":"Provably-efficient and internally-deterministic parallel Union-Find","file_date_updated":"2023-07-31T10:53:08Z","isi":1,"doi":"10.1145/3558481.3591082","file":[{"content_type":"application/pdf","file_size":2087937,"checksum":"72e312aabf0c5248c99b5cd3a88e4c88","date_updated":"2023-07-31T10:53:08Z","relation":"main_file","date_created":"2023-07-31T10:53:08Z","success":1,"creator":"dernst","file_name":"2023_SPAA_Fedorov.pdf","access_level":"open_access","file_id":"13334"}],"publication_status":"published","date_published":"2023-06-17T00:00:00Z","author":[{"last_name":"Fedorov","id":"2e711909-896a-11ed-bdf8-eb0f5a2984c6","first_name":"Alexander","full_name":"Fedorov, Alexander"},{"full_name":"Hashemi, Diba","last_name":"Hashemi","id":"ed9595ea-2f8f-11ee-ba95-d2b546540783","first_name":"Diba"},{"first_name":"Giorgi","id":"3279A00C-F248-11E8-B48F-1D18A9856A87","last_name":"Nadiradze","orcid":"0000-0001-5634-0731","full_name":"Nadiradze, Giorgi"},{"full_name":"Alistarh, Dan-Adrian","first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","last_name":"Alistarh","orcid":"0000-0003-3650-940X"}],"page":"261-271","quality_controlled":"1","date_updated":"2025-09-09T12:43:18Z","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"},"_id":"13262","date_created":"2023-07-23T22:01:12Z","status":"public","department":[{"_id":"DaAl"},{"_id":"GradSch"}],"citation":{"ieee":"A. Fedorov, D. Hashemi, G. Nadiradze, and D.-A. Alistarh, “Provably-efficient and internally-deterministic parallel Union-Find,” in <i>Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures</i>, Orlando, FL, United States, 2023, pp. 261–271.","ista":"Fedorov A, Hashemi D, Nadiradze G, Alistarh D-A. 2023. Provably-efficient and internally-deterministic parallel Union-Find. Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures. SPAA: Symposium on Parallelism in Algorithms and Architectures, 261–271.","ama":"Fedorov A, Hashemi D, Nadiradze G, Alistarh D-A. Provably-efficient and internally-deterministic parallel Union-Find. In: <i>Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures</i>. Association for Computing Machinery; 2023:261-271. doi:<a href=\"https://doi.org/10.1145/3558481.3591082\">10.1145/3558481.3591082</a>","mla":"Fedorov, Alexander, et al. “Provably-Efficient and Internally-Deterministic Parallel Union-Find.” <i>Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures</i>, Association for Computing Machinery, 2023, pp. 261–71, doi:<a href=\"https://doi.org/10.1145/3558481.3591082\">10.1145/3558481.3591082</a>.","short":"A. Fedorov, D. Hashemi, G. Nadiradze, D.-A. Alistarh, in:, Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, Association for Computing Machinery, 2023, pp. 261–271.","chicago":"Fedorov, Alexander, Diba Hashemi, Giorgi Nadiradze, and Dan-Adrian Alistarh. “Provably-Efficient and Internally-Deterministic Parallel Union-Find.” In <i>Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures</i>, 261–71. Association for Computing Machinery, 2023. <a href=\"https://doi.org/10.1145/3558481.3591082\">https://doi.org/10.1145/3558481.3591082</a>.","apa":"Fedorov, A., Hashemi, D., Nadiradze, G., &#38; Alistarh, D.-A. (2023). Provably-efficient and internally-deterministic parallel Union-Find. In <i>Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures</i> (pp. 261–271). Orlando, FL, United States: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3558481.3591082\">https://doi.org/10.1145/3558481.3591082</a>"},"language":[{"iso":"eng"}],"oa_version":"Published Version","type":"conference","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","fulldoi":"https://doi.org/10.1145/3558481.3591082","conference":{"name":"SPAA: Symposium on Parallelism in Algorithms and Architectures","location":"Orlando, FL, United States","end_date":"2023-06-19","start_date":"2023-06-17"},"year":"2023","day":"17","publication_identifier":{"isbn":["9781450395458"]},"scopus_import":"1","abstract":[{"text":"Determining the degree of inherent parallelism in classical sequential algorithms and leveraging it for fast parallel execution is a key topic in parallel computing, and detailed analyses are known for a wide range of classical algorithms. In this paper, we perform the first such analysis for the fundamental Union-Find problem, in which we are given a graph as a sequence of edges, and must maintain its connectivity structure under edge additions. We prove that classic sequential algorithms for this problem are well-parallelizable under reasonable assumptions, addressing a conjecture by [Blelloch, 2017]. More precisely, we show via a new potential argument that, under uniform random edge ordering, parallel union-find operations are unlikely to interfere: T concurrent threads processing the graph in parallel will encounter memory contention O(T2 · log |V| · log |E|) times in expectation, where |E| and |V| are the number of edges and nodes in the graph, respectively. We leverage this result to design a new parallel Union-Find algorithm that is both internally deterministic, i.e., its results are guaranteed to match those of a sequential execution, but also work-efficient and scalable, as long as the number of threads T is O(|E|1 over 3 - ε), for an arbitrarily small constant ε > 0, which holds for most large real-world graphs. We present lower bounds which show that our analysis is close to optimal, and experimental results suggesting that the performance cost of internal determinism is limited.","lang":"eng"}],"publisher":"Association for Computing Machinery","corr_author":"1","ddc":["000"],"has_accepted_license":"1","external_id":{"isi":["001108889000024"],"arxiv":["2304.09331"]},"publication":"Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures","oa":1,"arxiv":1,"article_processing_charge":"Yes (via OA deal)","month":"06"},{"article_type":"original","type":"journal_article","year":"2023","project":[{"grant_number":"805223","name":"Elastic Coordination for Scalable Machine Learning","_id":"268A44D6-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"fulldoi":"https://doi.org/10.1137/20M1375851","issue":"4","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Society for Industrial and Applied Mathematics","acknowledgement":"We would like to thank Valerie King, Toniann Pitassi, and Michael Saks for helpful discussions and Shi Hao Liu for his useful feedback.\r\nThis research was supported by the Natural Science and Engineering Research Council of Canada under grants RGPIN-2015-05080 and RGPIN-2020-04178, a postgraduate scholarship, and a postdoctoral fellowship; a University of Toronto postdoctoral fellowship; the National Science Foundation under grants CCF-1217921, CCF-1301926, CCF-1637385, CCF-1650596, and IIS-1447786; the U.S. Department of Energy under grant ER26116/DE-SC0008923; the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme grant agreement 805223 ScaleML; and the Oracle and Intel corporations. Some of the work on this paper was done while Faith Ellen was visiting IST Austria.","volume":52,"day":"25","scopus_import":"1","abstract":[{"text":"We introduce extension-based proofs, a class of impossibility proofs that includes valency arguments. They are modelled as an interaction between a prover and a protocol. Using proofs based on combinatorial topology, it has been shown that it is impossible to deterministically solve -set agreement among  processes or approximate agreement on a cycle of length 4 among  processes in a wait-free manner in asynchronous models where processes communicate using objects that can be constructed from shared registers. However, it was unknown whether proofs based on simpler techniques were possible. We show that these impossibility results cannot be obtained by extension-based proofs in the iterated snapshot model and, hence, extension-based proofs are limited in power.","lang":"eng"}],"publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"month":"07","related_material":{"record":[{"id":"6676","status":"public","relation":"earlier_version"}]},"publication":"SIAM Journal on Computing","external_id":{"arxiv":["1811.01421"],"isi":["001082972300004"]},"arxiv":1,"article_processing_charge":"No","oa":1,"page":"913-944","date_published":"2023-07-25T00:00:00Z","publication_status":"published","author":[{"full_name":"Alistarh, Dan-Adrian","first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X","last_name":"Alistarh"},{"first_name":"James","last_name":"Aspnes","full_name":"Aspnes, James"},{"full_name":"Ellen, Faith","last_name":"Ellen","first_name":"Faith"},{"last_name":"Gelashvili","first_name":"Rati","full_name":"Gelashvili, Rati"},{"id":"a2117c59-cee4-11ed-b9d0-874ecf0f8ac5","last_name":"Zhu","first_name":"Leqi","full_name":"Zhu, Leqi"}],"doi":"10.1137/20M1375851","title":"Why extension-based proofs fail","isi":1,"_id":"14364","date_updated":"2025-05-14T11:26:06Z","quality_controlled":"1","date_created":"2023-09-24T22:01:11Z","intvolume":"        52","language":[{"iso":"eng"}],"oa_version":"Preprint","ec_funded":1,"status":"public","citation":{"short":"D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, L. Zhu, SIAM Journal on Computing 52 (2023) 913–944.","apa":"Alistarh, D.-A., Aspnes, J., Ellen, F., Gelashvili, R., &#38; Zhu, L. (2023). Why extension-based proofs fail. <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/20M1375851\">https://doi.org/10.1137/20M1375851</a>","chicago":"Alistarh, Dan-Adrian, James Aspnes, Faith Ellen, Rati Gelashvili, and Leqi Zhu. “Why Extension-Based Proofs Fail.” <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics, 2023. <a href=\"https://doi.org/10.1137/20M1375851\">https://doi.org/10.1137/20M1375851</a>.","ieee":"D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, and L. Zhu, “Why extension-based proofs fail,” <i>SIAM Journal on Computing</i>, vol. 52, no. 4. Society for Industrial and Applied Mathematics, pp. 913–944, 2023.","mla":"Alistarh, Dan-Adrian, et al. “Why Extension-Based Proofs Fail.” <i>SIAM Journal on Computing</i>, vol. 52, no. 4, Society for Industrial and Applied Mathematics, 2023, pp. 913–44, doi:<a href=\"https://doi.org/10.1137/20M1375851\">10.1137/20M1375851</a>.","ista":"Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. 2023. Why extension-based proofs fail. SIAM Journal on Computing. 52(4), 913–944.","ama":"Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. Why extension-based proofs fail. <i>SIAM Journal on Computing</i>. 2023;52(4):913-944. doi:<a href=\"https://doi.org/10.1137/20M1375851\">10.1137/20M1375851</a>"},"department":[{"_id":"DaAl"}],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1811.01421"}]},{"status":"public","citation":{"apa":"Nikdan, M., Pegolotti, T., Iofinova, E. B., Kurtic, E., &#38; Alistarh, D.-A. (2023). SparseProp: Efficient sparse backpropagation for faster training of neural networks at the edge. In <i>Proceedings of the 40th International Conference on Machine Learning</i> (Vol. 202, pp. 26215–26227). Honolulu, Hawaii, HI, United States: ML Research Press.","chicago":"Nikdan, Mahdi, Tommaso Pegolotti, Eugenia B Iofinova, Eldar Kurtic, and Dan-Adrian Alistarh. “SparseProp: Efficient Sparse Backpropagation for Faster Training of Neural Networks at the Edge.” In <i>Proceedings of the 40th International Conference on Machine Learning</i>, 202:26215–27. ML Research Press, 2023.","short":"M. Nikdan, T. Pegolotti, E.B. Iofinova, E. Kurtic, D.-A. Alistarh, in:, Proceedings of the 40th International Conference on Machine Learning, ML Research Press, 2023, pp. 26215–26227.","mla":"Nikdan, Mahdi, et al. “SparseProp: Efficient Sparse Backpropagation for Faster Training of Neural Networks at the Edge.” <i>Proceedings of the 40th International Conference on Machine Learning</i>, vol. 202, ML Research Press, 2023, pp. 26215–27.","ista":"Nikdan M, Pegolotti T, Iofinova EB, Kurtic E, Alistarh D-A. 2023. SparseProp: Efficient sparse backpropagation for faster training of neural networks at the edge. Proceedings of the 40th International Conference on Machine Learning. ICML: International Conference on Machine Learning, PMLR, vol. 202, 26215–26227.","ama":"Nikdan M, Pegolotti T, Iofinova EB, Kurtic E, Alistarh D-A. SparseProp: Efficient sparse backpropagation for faster training of neural networks at the edge. In: <i>Proceedings of the 40th International Conference on Machine Learning</i>. Vol 202. ML Research Press; 2023:26215-26227.","ieee":"M. Nikdan, T. Pegolotti, E. B. Iofinova, E. Kurtic, and D.-A. Alistarh, “SparseProp: Efficient sparse backpropagation for faster training of neural networks at the edge,” in <i>Proceedings of the 40th International Conference on Machine Learning</i>, Honolulu, Hawaii, HI, United States, 2023, vol. 202, pp. 26215–26227."},"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2302.04852"}],"department":[{"_id":"DaAl"}],"language":[{"iso":"eng"}],"oa_version":"Preprint","ec_funded":1,"_id":"14460","date_updated":"2025-04-14T07:49:12Z","quality_controlled":"1","date_created":"2023-10-29T23:01:17Z","intvolume":"       202","alternative_title":["PMLR"],"title":"SparseProp: Efficient sparse backpropagation for faster training of neural networks at the edge","page":"26215-26227","author":[{"id":"66374281-f394-11eb-9cf6-869147deecc0","last_name":"Nikdan","first_name":"Mahdi","full_name":"Nikdan, Mahdi"},{"last_name":"Pegolotti","first_name":"Tommaso","full_name":"Pegolotti, Tommaso"},{"full_name":"Iofinova, Eugenia B","first_name":"Eugenia B","last_name":"Iofinova","orcid":"0000-0002-7778-3221","id":"f9a17499-f6e0-11ea-865d-fdf9a3f77117"},{"full_name":"Kurtic, Eldar","first_name":"Eldar","last_name":"Kurtic","id":"47beb3a5-07b5-11eb-9b87-b108ec578218"},{"full_name":"Alistarh, Dan-Adrian","first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X","last_name":"Alistarh"}],"publication_status":"published","date_published":"2023-07-30T00:00:00Z","publication":"Proceedings of the 40th International Conference on Machine Learning","external_id":{"arxiv":["2302.04852"]},"article_processing_charge":"No","arxiv":1,"oa":1,"month":"07","volume":202,"day":"30","abstract":[{"text":"We provide an efficient implementation of the backpropagation algorithm, specialized to the case where the weights of the neural network being trained are sparse. Our algorithm is general, as it applies to arbitrary (unstructured) sparsity and common layer types (e.g., convolutional or linear). We provide a fast vectorized implementation on commodity CPUs, and show that it can yield speedups in end-to-end runtime experiments, both in transfer learning using already-sparsified networks, and in training sparse networks from scratch. Thus, our results provide the first support for sparse training on commodity hardware.","lang":"eng"}],"scopus_import":"1","publication_identifier":{"eissn":["2640-3498"]},"publisher":"ML Research Press","corr_author":"1","acknowledgement":"We would like to thank Elias Frantar for his valuable assistance and support at the outset of this project, and the anonymous ICML and SNN reviewers for very constructive feedback. EI was supported in part by the FWF DK VGSCO, grant agreement number W1260-N35. DA acknowledges generous ERC support, via Starting Grant 805223 ScaleML. ","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2023","conference":{"name":"ICML: International Conference on Machine Learning","location":"Honolulu, Hawaii, HI, United States","end_date":"2023-07-29","start_date":"2023-07-23"},"project":[{"_id":"268A44D6-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Elastic Coordination for Scalable Machine Learning","grant_number":"805223"}],"type":"conference"},{"quality_controlled":"1","_id":"14815","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"},"date_updated":"2024-10-09T21:07:52Z","intvolume":"        24","date_created":"2024-01-16T12:13:36Z","language":[{"iso":"eng"}],"oa_version":"Published Version","status":"public","department":[{"_id":"DaAl"}],"citation":{"apa":"Beznosikov, A., Horvath, S., Richtarik, P., &#38; Safaryan, M. (2023). On biased compression for distributed learning. <i>Journal of Machine Learning Research</i>. Journal of Machine Learning Research.","chicago":"Beznosikov, Aleksandr, Samuel Horvath, Peter Richtarik, and Mher Safaryan. “On Biased Compression for Distributed Learning.” <i>Journal of Machine Learning Research</i>. Journal of Machine Learning Research, 2023.","short":"A. Beznosikov, S. Horvath, P. Richtarik, M. Safaryan, Journal of Machine Learning Research 24 (2023) 1–50.","ama":"Beznosikov A, Horvath S, Richtarik P, Safaryan M. On biased compression for distributed learning. <i>Journal of Machine Learning Research</i>. 2023;24:1-50.","ista":"Beznosikov A, Horvath S, Richtarik P, Safaryan M. 2023. On biased compression for distributed learning. Journal of Machine Learning Research. 24, 1–50.","mla":"Beznosikov, Aleksandr, et al. “On Biased Compression for Distributed Learning.” <i>Journal of Machine Learning Research</i>, vol. 24, Journal of Machine Learning Research, 2023, pp. 1–50.","ieee":"A. Beznosikov, S. Horvath, P. Richtarik, and M. Safaryan, “On biased compression for distributed learning,” <i>Journal of Machine Learning Research</i>, vol. 24. Journal of Machine Learning Research, pp. 1–50, 2023."},"date_published":"2023-10-01T00:00:00Z","file":[{"access_level":"open_access","file_id":"14816","file_name":"2023_JMLR_Beznosikov.pdf","relation":"main_file","date_updated":"2024-01-16T12:13:27Z","checksum":"c50f2b9db53938b755e30a085f464059","creator":"dernst","success":1,"date_created":"2024-01-16T12:13:27Z","file_size":1510993,"content_type":"application/pdf"}],"publication_status":"published","author":[{"full_name":"Beznosikov, Aleksandr","last_name":"Beznosikov","first_name":"Aleksandr"},{"full_name":"Horvath, Samuel","first_name":"Samuel","last_name":"Horvath"},{"full_name":"Richtarik, Peter","last_name":"Richtarik","first_name":"Peter"},{"full_name":"Safaryan, Mher","first_name":"Mher","id":"dd546b39-0804-11ed-9c55-ef075c39778d","last_name":"Safaryan"}],"page":"1-50","title":"On biased compression for distributed learning","file_date_updated":"2024-01-16T12:13:27Z","isi":1,"publisher":"Journal of Machine Learning Research","corr_author":"1","acknowledgement":"The work in Sections 1-5 was conducted while A. Beznosikov was a research intern in the Optimizationand Machine Learning Lab of Peter Richtárik at KAUST; this visit was funded by the KAUST Baseline Research Funding Scheme. The work of A. Beznosikov in Section 6 was conducted in Skoltech and was supported by Ministry of Science and Higher Education grant No. 075-10-2021-068. ","has_accepted_license":"1","ddc":["000"],"day":"01","volume":24,"publication_identifier":{"eissn":["1533-7928"]},"abstract":[{"lang":"eng","text":"In the last few years, various communication compression techniques have emerged as an indispensable tool helping to alleviate the communication bottleneck in distributed learning. However, despite the fact biased compressors often show superior performance in practice when compared to the much more studied and understood unbiased compressors, very little is known about them. In this work we study three classes of biased compression operators, two of which are new, and their performance when applied to (stochastic) gradient descent and distributed (stochastic) gradient descent. We show for the first time that biased compressors can lead to linear convergence rates both in the single node and distributed settings. We prove that distributed compressed SGD method, employed with error feedback mechanism, enjoys the ergodic rate O(δLexp[−μKδL]+(C+δD)Kμ), where δ≥1 is a compression parameter which grows when more compression is applied, L and μ are the smoothness and strong convexity constants, C captures stochastic gradient noise (C=0 if full gradients are computed on each node) and D captures the variance of the gradients at the optimum (D=0 for over-parameterized models). Further, via a theoretical study of several synthetic and empirical distributions of communicated gradients, we shed light on why and by how much biased compressors outperform their unbiased variants. Finally, we propose several new biased compressors with promising theoretical guarantees and practical performance."}],"month":"10","external_id":{"isi":["001111578500001"],"arxiv":["2002.12410"]},"publication":"Journal of Machine Learning Research","oa":1,"arxiv":1,"article_processing_charge":"Yes (in subscription journal)","article_type":"original","type":"journal_article","year":"2023","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"article_type":"original","type":"journal_article","year":"2023","fulldoi":"https://doi.org/10.1145/3591230","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000"],"has_accepted_license":"1","publisher":"Association for Computing Machinery","corr_author":"1","scopus_import":"1","abstract":[{"lang":"eng","text":"Writing concurrent code that is both correct and efficient is notoriously difficult. Thus, programmers often prefer to use synchronization abstractions, which render code simpler and easier to reason about. Despite a wealth of work on this topic, there is still a gap between the rich semantics provided by synchronization abstractions in modern programming languages—specifically, fair FIFO ordering of synchronization requests and support for abortable operations—and frameworks for implementing it correctly and efficiently. Supporting such semantics is critical given the rising popularity of constructs for asynchronous programming, such as coroutines, which abort frequently and are cheaper to suspend and resume compared to native threads.\r\n\r\nThis paper introduces a new framework called CancellableQueueSynchronizer (CQS), which enables simple yet efficient implementations of a wide range of fair and abortable synchronization primitives: mutexes, semaphores, barriers, count-down latches, and blocking pools. Our main contribution is algorithmic, as implementing both fairness and abortability efficiently at this level of generality is non-trivial. Importantly, all our algorithms, including the CQS framework and the primitives built on top of it, come with formal proofs in the Iris framework for Coq for many of their properties. These proofs are modular, so it is easy to show correctness for new primitives implemented on top of CQS. From a practical perspective, implementation of CQS for native threads on the JVM improves throughput by up to two orders of magnitude over Java’s AbstractQueuedSynchronizer, the only practical abstraction offering similar semantics. Further, we successfully integrated CQS as a core component of the popular Kotlin Coroutines library, validating the framework’s practical impact and expressiveness in a real-world environment. In sum, CancellableQueueSynchronizer is the first framework to combine expressiveness with formal guarantees and solid practical performance. Our approach should be extensible to other languages and families of synchronization primitives."}],"publication_identifier":{"eissn":["2475-1421"]},"volume":7,"day":"06","month":"06","article_processing_charge":"No","oa":1,"publication":"Proceedings of the ACM on Programming Languages","author":[{"first_name":"Nikita","id":"2F4DB10C-F248-11E8-B48F-1D18A9856A87","last_name":"Koval","full_name":"Koval, Nikita"},{"first_name":"Dmitry","last_name":"Khalanskiy","full_name":"Khalanskiy, Dmitry"},{"full_name":"Alistarh, Dan-Adrian","first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","last_name":"Alistarh","orcid":"0000-0003-3650-940X"}],"file":[{"creator":"alisjak","success":1,"date_created":"2023-07-03T13:09:39Z","relation":"main_file","date_updated":"2023-07-03T13:09:39Z","checksum":"5dba6e73f0ed79adbdae14d165bc2f68","content_type":"application/pdf","file_size":1266773,"file_id":"13187","access_level":"open_access","file_name":"2023_ACMProgram.Lang._Koval.pdf"}],"date_published":"2023-06-06T00:00:00Z","publication_status":"published","doi":"10.1145/3591230","das_tickbox":"1","title":"CQS: A formally-verified framework for fair and abortable synchronization","file_date_updated":"2023-07-03T13:09:39Z","date_created":"2023-07-02T22:00:43Z","intvolume":"         7","_id":"13179","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"},"date_updated":"2026-07-06T12:12:08Z","quality_controlled":"1","article_number":"116","oa_version":"Published Version","language":[{"iso":"eng"}],"citation":{"chicago":"Koval, Nikita, Dmitry Khalanskiy, and Dan-Adrian Alistarh. “CQS: A Formally-Verified Framework for Fair and Abortable Synchronization.” <i>Proceedings of the ACM on Programming Languages</i>. Association for Computing Machinery, 2023. <a href=\"https://doi.org/10.1145/3591230\">https://doi.org/10.1145/3591230</a>.","apa":"Koval, N., Khalanskiy, D., &#38; Alistarh, D.-A. (2023). CQS: A formally-verified framework for fair and abortable synchronization. <i>Proceedings of the ACM on Programming Languages</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3591230\">https://doi.org/10.1145/3591230</a>","short":"N. Koval, D. Khalanskiy, D.-A. Alistarh, Proceedings of the ACM on Programming Languages 7 (2023).","mla":"Koval, Nikita, et al. “CQS: A Formally-Verified Framework for Fair and Abortable Synchronization.” <i>Proceedings of the ACM on Programming Languages</i>, vol. 7, 116, Association for Computing Machinery, 2023, doi:<a href=\"https://doi.org/10.1145/3591230\">10.1145/3591230</a>.","ista":"Koval N, Khalanskiy D, Alistarh D-A. 2023. CQS: A formally-verified framework for fair and abortable synchronization. Proceedings of the ACM on Programming Languages. 7, 116.","ama":"Koval N, Khalanskiy D, Alistarh D-A. CQS: A formally-verified framework for fair and abortable synchronization. <i>Proceedings of the ACM on Programming Languages</i>. 2023;7. doi:<a href=\"https://doi.org/10.1145/3591230\">10.1145/3591230</a>","ieee":"N. Koval, D. Khalanskiy, and D.-A. Alistarh, “CQS: A formally-verified framework for fair and abortable synchronization,” <i>Proceedings of the ACM on Programming Languages</i>, vol. 7. Association for Computing Machinery, 2023."},"department":[{"_id":"DaAl"}],"status":"public"},{"publication_identifier":{"eisbn":["9781611977585"]},"abstract":[{"text":"The sinkless orientation problem plays a key role in understanding the foundations of distributed computing. The problem can be used to separate two fundamental models of distributed graph algorithms, LOCAL and SLOCAL: the locality of sinkless orientation is Ω(log n) in the deterministic LOCAL model and O(log log n) in the deterministic SLOCAL model. Both of these results are known by prior work, but here we give new simple, self-contained proofs for them.","lang":"eng"}],"day":"12","acknowledgement":"We thank the anonymous reviewers for their helpful feedback on previous versions of this work. Parts ofthis work appeared in DISC 2021 as a brief announcement [ 21]. This work was supported in part by theEuropean Research Council (ERC) under the European Union’s Horizon 2020 research and innovationprogramme (grant agreement No 805223 ScaleML), the Academy of Finland (grant agreement No 333837),the Austrian Science Fund (FWF) and netIDEE (grant agreement No P 33775-N), and the AustrianScience Fund (FWF) project DELTA (grant agreement No I 5025-N).","publisher":"Society for Industrial and Applied Mathematics","oa":1,"article_processing_charge":"No","arxiv":1,"external_id":{"arxiv":["2108.02655"]},"OA_place":"repository","publication":"Symposium on Simplicity in Algorithms","month":"01","type":"book_chapter","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","fulldoi":"https://doi.org/10.1137/1.9781611977585.ch17","conference":{"start_date":"2023-01-23","name":"SOSA: Symposium on Simplicity in Algorithms","location":"Florence, Italy","end_date":"2023-01-25"},"project":[{"grant_number":"805223","name":"Elastic Coordination for Scalable Machine Learning","call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425"},{"grant_number":"P33775","name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe"}],"year":"2023","date_created":"2025-07-10T13:11:47Z","quality_controlled":"1","_id":"19983","date_updated":"2026-07-06T11:57:38Z","department":[{"_id":"DaAl"}],"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2108.02655","open_access":"1"}],"citation":{"ieee":"A. Balliu <i>et al.</i>, “Sinkless Orientation Made Simple,” in <i>Symposium on Simplicity in Algorithms</i>, Society for Industrial and Applied Mathematics, 2023, pp. 175–191.","mla":"Balliu, Alkida, et al. “Sinkless Orientation Made Simple.” <i>Symposium on Simplicity in Algorithms</i>, Society for Industrial and Applied Mathematics, 2023, pp. 175–91, doi:<a href=\"https://doi.org/10.1137/1.9781611977585.ch17\">10.1137/1.9781611977585.ch17</a>.","ama":"Balliu A, Korhonen J, Kuhn F, et al. Sinkless Orientation Made Simple. In: <i>Symposium on Simplicity in Algorithms</i>. Society for Industrial and Applied Mathematics; 2023:175-191. doi:<a href=\"https://doi.org/10.1137/1.9781611977585.ch17\">10.1137/1.9781611977585.ch17</a>","ista":"Balliu A, Korhonen J, Kuhn F, Lievonen H, Olivetti D, Pai S, Paz A, Rybicki J, Schmid S, Studený J, Suomela J, Uitto J. 2023.Sinkless Orientation Made Simple. In: Symposium on Simplicity in Algorithms. , 175–191.","short":"A. Balliu, J. Korhonen, F. Kuhn, H. Lievonen, D. Olivetti, S. Pai, A. Paz, J. Rybicki, S. Schmid, J. Studený, J. Suomela, J. Uitto, in:, Symposium on Simplicity in Algorithms, Society for Industrial and Applied Mathematics, 2023, pp. 175–191.","chicago":"Balliu, Alkida, Janne Korhonen, Fabian Kuhn, Henrik Lievonen, Dennis Olivetti, Shreyas Pai, Ami Paz, et al. “Sinkless Orientation Made Simple.” In <i>Symposium on Simplicity in Algorithms</i>, 175–91. Society for Industrial and Applied Mathematics, 2023. <a href=\"https://doi.org/10.1137/1.9781611977585.ch17\">https://doi.org/10.1137/1.9781611977585.ch17</a>.","apa":"Balliu, A., Korhonen, J., Kuhn, F., Lievonen, H., Olivetti, D., Pai, S., … Uitto, J. (2023). Sinkless Orientation Made Simple. In <i>Symposium on Simplicity in Algorithms</i> (pp. 175–191). Florence, Italy: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611977585.ch17\">https://doi.org/10.1137/1.9781611977585.ch17</a>"},"status":"public","ec_funded":1,"oa_version":"Preprint","language":[{"iso":"eng"}],"title":"Sinkless Orientation Made Simple","das_tickbox":"1","doi":"10.1137/1.9781611977585.ch17","publication_status":"published","author":[{"full_name":"Balliu, Alkida","first_name":"Alkida","last_name":"Balliu"},{"full_name":"Korhonen, Janne","last_name":"Korhonen","id":"C5402D42-15BC-11E9-A202-CA2BE6697425","first_name":"Janne"},{"last_name":"Kuhn","first_name":"Fabian","full_name":"Kuhn, Fabian"},{"last_name":"Lievonen","first_name":"Henrik","full_name":"Lievonen, Henrik"},{"full_name":"Olivetti, Dennis","first_name":"Dennis","last_name":"Olivetti"},{"full_name":"Pai, Shreyas","first_name":"Shreyas","last_name":"Pai"},{"first_name":"Ami","last_name":"Paz","full_name":"Paz, Ami"},{"full_name":"Rybicki, Joel","first_name":"Joel","orcid":"0000-0002-6432-6646","last_name":"Rybicki","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Schmid","first_name":"Stefan","full_name":"Schmid, Stefan"},{"full_name":"Studený, Jan","last_name":"Studený","first_name":"Jan"},{"full_name":"Suomela, Jukka","last_name":"Suomela","first_name":"Jukka"},{"first_name":"Jara","last_name":"Uitto","full_name":"Uitto, Jara"}],"date_published":"2023-01-12T00:00:00Z","page":"175-191","OA_type":"green"},{"file_date_updated":"2024-05-22T08:08:08Z","das_tickbox":"1","title":"Knowledge distillation performs partial variance reduction","author":[{"full_name":"Safaryan, Mher","first_name":"Mher","id":"dd546b39-0804-11ed-9c55-ef075c39778d","last_name":"Safaryan"},{"first_name":"Elena-Alexandra","last_name":"Peste","id":"32D78294-F248-11E8-B48F-1D18A9856A87","full_name":"Peste, Elena-Alexandra"},{"full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian"}],"file":[{"access_level":"open_access","file_id":"15417","file_name":"2023_Neurips_Safaryan.pdf","relation":"main_file","checksum":"288c5148a85abf24ad5e22a6b1183655","date_updated":"2024-05-22T08:08:08Z","creator":"dernst","success":1,"date_created":"2024-05-22T08:08:08Z","content_type":"application/pdf","file_size":672571}],"publication_status":"published","date_published":"2023-12-15T00:00:00Z","intvolume":"        36","date_created":"2024-05-05T22:01:04Z","quality_controlled":"1","date_updated":"2026-07-07T06:37:28Z","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"},"_id":"15363","alternative_title":["Advances in Neural Information Processing Systems"],"department":[{"_id":"DaAl"}],"citation":{"chicago":"Safaryan, Mher, Alexandra Krumes, and Dan-Adrian Alistarh. “Knowledge Distillation Performs Partial Variance Reduction.” In <i>36th Conference on Neural Information Processing Systems</i>, Vol. 36. Neural Information Processing Systems Foundation, 2023.","apa":"Safaryan, M., Krumes, A., &#38; Alistarh, D.-A. (2023). Knowledge distillation performs partial variance reduction. In <i>36th Conference on Neural Information Processing Systems</i> (Vol. 36). New Orleans, LA, United States: Neural Information Processing Systems Foundation.","short":"M. Safaryan, A. Krumes, D.-A. Alistarh, in:, 36th Conference on Neural Information Processing Systems, Neural Information Processing Systems Foundation, 2023.","mla":"Safaryan, Mher, et al. “Knowledge Distillation Performs Partial Variance Reduction.” <i>36th Conference on Neural Information Processing Systems</i>, vol. 36, Neural Information Processing Systems Foundation, 2023.","ama":"Safaryan M, Krumes A, Alistarh D-A. Knowledge distillation performs partial variance reduction. In: <i>36th Conference on Neural Information Processing Systems</i>. Vol 36. Neural Information Processing Systems Foundation; 2023.","ista":"Safaryan M, Krumes A, Alistarh D-A. 2023. Knowledge distillation performs partial variance reduction. 36th Conference on Neural Information Processing Systems. NeurIPS: Neural Information Processing Systems, Advances in Neural Information Processing Systems, vol. 36.","ieee":"M. Safaryan, A. Krumes, and D.-A. Alistarh, “Knowledge distillation performs partial variance reduction,” in <i>36th Conference on Neural Information Processing Systems</i>, New Orleans, LA, United States, 2023, vol. 36."},"status":"public","ec_funded":1,"oa_version":"Published Version","language":[{"iso":"eng"}],"type":"conference","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","project":[{"_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","call_identifier":"H2020","name":"IST-BRIDGE: International postdoctoral program","grant_number":"101034413"}],"conference":{"end_date":"2023-12-16","location":"New Orleans, LA, United States","name":"NeurIPS: Neural Information Processing Systems","start_date":"2023-12-10"},"year":"2023","publication_identifier":{"issn":["1049-5258"]},"abstract":[{"lang":"eng","text":"Knowledge distillation is a popular approach for enhancing the performance of \"student\" models, with lower representational capacity, by taking advantage of more powerful \"teacher\" models. Despite its apparent simplicity, the underlying mechanics behind knowledge distillation (KD) are not yet fully understood. In this work, we shed new light on the inner workings of this method, by examining it from an optimization perspective. Specifically, we show that, in the context of linear and deep linear models, KD can be interpreted as a novel type of stochastic variance reduction mechanism. We provide a detailed convergence analysis of the resulting dynamics, which hold under standard assumptions for both strongly-convex and non-convex losses, showing that KD acts as a form of \\emph{partial variance reduction}, which can reduce the stochastic gradient noise, but may not eliminate it completely, depending on the properties of the teacher'' model. Our analysis puts further emphasis on the need for careful parametrization of KD, in particular w.r.t. the weighting of the distillation loss, and is validated empirically on both linear models and deep neural networks."}],"scopus_import":"1","day":"15","volume":36,"acknowledgement":"MS has received funding from the European Union’s Horizon 2020 research and innovation programme\r\nunder the Marie Skłodowska-Curie grant agreement No 101034413.","ddc":["000"],"has_accepted_license":"1","corr_author":"1","publisher":"Neural Information Processing Systems Foundation","oa":1,"arxiv":1,"article_processing_charge":"Yes","publication":"36th Conference on Neural Information Processing Systems","external_id":{"arxiv":["2305.17581"]},"month":"12"},{"type":"conference","year":"2023","conference":{"end_date":"2023-07-22","name":"CAV: Computer Aided Verification","location":"Paris, France","start_date":"2023-07-17"},"fulldoi":"https://doi.org/10.1007/978-3-031-37706-8_8","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000"],"has_accepted_license":"1","publisher":"Springer Nature","scopus_import":"1","abstract":[{"lang":"eng","text":"This paper presents Lincheck, a new practical and user-friendly framework for testing concurrent algorithms on the Java Virtual Machine (JVM). Lincheck provides a simple and declarative way to write concurrent tests: instead of describing how to perform the test, users specify what to test by declaring all the operations to examine; the framework automatically handles the rest. As a result, tests written with Lincheck are concise and easy to understand. The framework automatically generates a set of concurrent scenarios, examines them using stress-testing or bounded model checking, and verifies that the results of each invocation are correct. Notably, if an error is detected via model checking, Lincheck provides an easy-to-follow trace to reproduce it, significantly simplifying the bug investigation.\r\n\r\nTo the best of our knowledge, Lincheck is the first production-ready tool on the JVM that offers such a simple way of writing concurrent tests, without requiring special skills or expertise. We successfully integrated Lincheck in the development process of several large projects, such as Kotlin Coroutines, and identified new bugs in popular concurrency libraries, such as a race in Java’s standard ConcurrentLinkedDeque and a liveliness bug in Java’s AbstractQueuedSynchronizer framework, which is used in most of the synchronization primitives. We believe that Lincheck can significantly improve the quality and productivity of concurrent algorithms research and development and become the state-of-the-art tool for checking their correctness."}],"publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9783031377051"]},"volume":13964,"day":"17","month":"07","related_material":{"record":[{"id":"14995","status":"public","relation":"research_data"}]},"article_processing_charge":"Yes (in subscription journal)","oa":1,"external_id":{"isi":["001310786500008"]},"publication":"35th International Conference on Computer Aided Verification","page":"156-169","file":[{"date_updated":"2023-09-06T08:16:25Z","checksum":"c346016393123a0a2338ad4d976f61bc","relation":"main_file","date_created":"2023-09-06T08:16:25Z","success":1,"creator":"dernst","content_type":"application/pdf","file_size":421408,"access_level":"open_access","file_id":"14275","file_name":"2023_LNCS_Koval.pdf"}],"date_published":"2023-07-17T00:00:00Z","author":[{"first_name":"Nikita","id":"2F4DB10C-F248-11E8-B48F-1D18A9856A87","last_name":"Koval","full_name":"Koval, Nikita"},{"first_name":"Alexander","id":"2e711909-896a-11ed-bdf8-eb0f5a2984c6","last_name":"Fedorov","full_name":"Fedorov, Alexander"},{"full_name":"Sokolova, Maria","first_name":"Maria","last_name":"Sokolova"},{"first_name":"Dmitry","last_name":"Tsitelov","full_name":"Tsitelov, Dmitry"},{"full_name":"Alistarh, Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X","last_name":"Alistarh","first_name":"Dan-Adrian"}],"publication_status":"published","doi":"10.1007/978-3-031-37706-8_8","title":"Lincheck: A practical framework for testing concurrent data structures on JVM","das_tickbox":"1","isi":1,"file_date_updated":"2023-09-06T08:16:25Z","alternative_title":["LNCS"],"date_created":"2023-09-03T22:01:16Z","intvolume":"     13964","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"},"date_updated":"2026-07-07T13:39:36Z","_id":"14260","quality_controlled":"1","oa_version":"Published Version","language":[{"iso":"eng"}],"citation":{"chicago":"Koval, Nikita, Alexander Fedorov, Maria Sokolova, Dmitry Tsitelov, and Dan-Adrian Alistarh. “Lincheck: A Practical Framework for Testing Concurrent Data Structures on JVM.” In <i>35th International Conference on Computer Aided Verification</i>, 13964:156–69. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/978-3-031-37706-8_8\">https://doi.org/10.1007/978-3-031-37706-8_8</a>.","apa":"Koval, N., Fedorov, A., Sokolova, M., Tsitelov, D., &#38; Alistarh, D.-A. (2023). Lincheck: A practical framework for testing concurrent data structures on JVM. In <i>35th International Conference on Computer Aided Verification</i> (Vol. 13964, pp. 156–169). Paris, France: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-37706-8_8\">https://doi.org/10.1007/978-3-031-37706-8_8</a>","short":"N. Koval, A. Fedorov, M. Sokolova, D. Tsitelov, D.-A. Alistarh, in:, 35th International Conference on Computer Aided Verification, Springer Nature, 2023, pp. 156–169.","ista":"Koval N, Fedorov A, Sokolova M, Tsitelov D, Alistarh D-A. 2023. Lincheck: A practical framework for testing concurrent data structures on JVM. 35th International Conference on Computer Aided Verification. CAV: Computer Aided Verification, LNCS, vol. 13964, 156–169.","ama":"Koval N, Fedorov A, Sokolova M, Tsitelov D, Alistarh D-A. Lincheck: A practical framework for testing concurrent data structures on JVM. In: <i>35th International Conference on Computer Aided Verification</i>. Vol 13964. Springer Nature; 2023:156-169. doi:<a href=\"https://doi.org/10.1007/978-3-031-37706-8_8\">10.1007/978-3-031-37706-8_8</a>","mla":"Koval, Nikita, et al. “Lincheck: A Practical Framework for Testing Concurrent Data Structures on JVM.” <i>35th International Conference on Computer Aided Verification</i>, vol. 13964, Springer Nature, 2023, pp. 156–69, doi:<a href=\"https://doi.org/10.1007/978-3-031-37706-8_8\">10.1007/978-3-031-37706-8_8</a>.","ieee":"N. Koval, A. Fedorov, M. Sokolova, D. Tsitelov, and D.-A. Alistarh, “Lincheck: A practical framework for testing concurrent data structures on JVM,” in <i>35th International Conference on Computer Aided Verification</i>, Paris, France, 2023, vol. 13964, pp. 156–169."},"department":[{"_id":"DaAl"},{"_id":"GradSch"}],"status":"public"}]