---
_id: '14458'
abstract:
- lang: eng
text: 'We show for the first time that large-scale generative pretrained transformer
(GPT) family models can be pruned to at least 50% sparsity in one-shot, without
any retraining, at minimal loss of accuracy. This is achieved via a new pruning
method called SparseGPT, specifically designed to work efficiently and accurately
on massive GPT-family models. We can execute SparseGPT on the largest available
open-source models, OPT-175B and BLOOM-176B, in under 4.5 hours, and can reach
60% unstructured sparsity with negligible increase in perplexity: remarkably,
more than 100 billion weights from these models can be ignored at inference time.
SparseGPT generalizes to semi-structured (2:4 and 4:8) patterns, and is compatible
with weight quantization approaches. The code is available at: https://github.com/IST-DASLab/sparsegpt.'
acknowledged_ssus:
- _id: ScienComp
acknowledgement: The authors gratefully acknowledge funding from the European Research
Council (ERC) under the European Union’s Horizon 2020 programme (grant agreement
No. 805223 ScaleML), as well as experimental support from Eldar Kurtic, and from
the IST Austria IT department, in particular Stefano Elefante, Andrei Hornoiu, and
Alois Schloegl.
alternative_title:
- PMLR
article_processing_charge: No
arxiv: 1
author:
- first_name: Elias
full_name: Frantar, Elias
id: 09a8f98d-ec99-11ea-ae11-c063a7b7fe5f
last_name: Frantar
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
citation:
ama: 'Frantar E, Alistarh D-A. SparseGPT: Massive language models can be accurately
pruned in one-shot. In: Proceedings of the 40th International Conference on
Machine Learning. Vol 202. ML Research Press; 2023:10323-10337.'
apa: 'Frantar, E., & Alistarh, D.-A. (2023). SparseGPT: Massive language models
can be accurately pruned in one-shot. In Proceedings of the 40th International
Conference on Machine Learning (Vol. 202, pp. 10323–10337). Honolulu, Hawaii,
HI, United States: ML Research Press.'
chicago: 'Frantar, Elias, and Dan-Adrian Alistarh. “SparseGPT: Massive Language
Models Can Be Accurately Pruned in One-Shot.” In Proceedings of the 40th International
Conference on Machine Learning, 202:10323–37. ML Research Press, 2023.'
ieee: 'E. Frantar and D.-A. Alistarh, “SparseGPT: Massive language models can be
accurately pruned in one-shot,” in Proceedings of the 40th International Conference
on Machine Learning, Honolulu, Hawaii, HI, United States, 2023, vol. 202,
pp. 10323–10337.'
ista: 'Frantar E, Alistarh D-A. 2023. SparseGPT: Massive language models can be
accurately pruned in one-shot. Proceedings of the 40th International Conference
on Machine Learning. ICML: International Conference on Machine Learning, PMLR,
vol. 202, 10323–10337.'
mla: 'Frantar, Elias, and Dan-Adrian Alistarh. “SparseGPT: Massive Language Models
Can Be Accurately Pruned in One-Shot.” Proceedings of the 40th International
Conference on Machine Learning, vol. 202, ML Research Press, 2023, pp. 10323–37.'
short: E. Frantar, D.-A. Alistarh, in:, Proceedings of the 40th International Conference
on Machine Learning, ML Research Press, 2023, pp. 10323–10337.
conference:
end_date: 2023-07-29
location: Honolulu, Hawaii, HI, United States
name: 'ICML: International Conference on Machine Learning'
start_date: 2023-07-23
corr_author: '1'
date_created: 2023-10-29T23:01:16Z
date_published: 2023-07-30T00:00:00Z
date_updated: 2026-07-29T13:48:39Z
day: '30'
department:
- _id: DaAl
ec_funded: 1
external_id:
arxiv:
- '2301.00774'
intvolume: ' 202'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2301.00774
month: '07'
oa: 1
oa_version: Preprint
page: 10323-10337
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
publication: Proceedings of the 40th International Conference on Machine Learning
publication_identifier:
eissn:
- 2640-3498
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
related_material:
record:
- id: '17485'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: 'SparseGPT: Massive language models can be accurately pruned in one-shot'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 202
year: '2023'
...
---
OA_place: publisher
_id: '13074'
abstract:
- lang: eng
text: "Deep learning has become an integral part of a large number of important
applications, and many of the recent breakthroughs have been enabled by the ability
to train very large models, capable to capture complex patterns and relationships
from the data. At the same time, the massive sizes of modern deep learning models
have made their deployment to smaller devices more challenging; this is particularly
important, as in many applications the users rely on accurate deep learning predictions,
but they only have access to devices with limited memory and compute power. One
solution to this problem is to prune neural networks, by setting as many of their
parameters as possible to zero, to obtain accurate sparse models with lower memory
footprint. Despite the great research progress in obtaining sparse models that
preserve accuracy, while satisfying memory and computational constraints, there
are still many challenges associated with efficiently training sparse models,
as well as understanding their generalization properties.\r\n\r\nThe focus of
this thesis is to investigate how the training process of sparse models can be
made more efficient, and to understand the differences between sparse and dense
models in terms of how well they can generalize to changes in the data distribution.
We first study a method for co-training sparse and dense models, at a lower cost
compared to regular training. With our method we can obtain very accurate sparse
networks, and dense models that can recover the baseline accuracy. Furthermore,
we are able to more easily analyze the differences, at prediction level, between
the sparse-dense model pairs. Next, we investigate the generalization properties
of sparse neural networks in more detail, by studying how well different sparse
models trained on a larger task can adapt to smaller, more specialized tasks,
in a transfer learning scenario. Our analysis across multiple pruning methods
and sparsity levels reveals that sparse models provide features that can transfer
similarly to or better than the dense baseline. However, the choice of the pruning
method plays an important role, and can influence the results when the features
are fixed (linear finetuning), or when they are allowed to adapt to the new task
(full finetuning). Using sparse models with fixed masks for finetuning on new
tasks has an important practical advantage, as it enables training neural networks
on smaller devices. However, one drawback of current pruning methods is that the
entire training cycle has to be repeated to obtain the initial sparse model, for
every sparsity target; in consequence, the entire training process is costly and
also multiple models need to be stored. In the last part of the thesis we propose
a method that can train accurate dense models that are compressible in a single
step, to multiple sparsity levels, without additional finetuning. Our method results
in sparse models that can be competitive with existing pruning methods, and which
can also successfully generalize to new tasks."
acknowledged_ssus:
- _id: ScienComp
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Elena-Alexandra
full_name: Peste, Elena-Alexandra
id: 32D78294-F248-11E8-B48F-1D18A9856A87
last_name: Peste
citation:
ama: Krumes A. Efficiency and generalization of sparse neural networks. 2023. doi:10.15479/at:ista:13074
apa: Krumes, A. (2023). Efficiency and generalization of sparse neural networks.
Institute of Science and Technology Austria. https://doi.org/10.15479/at:ista:13074
chicago: Krumes, Alexandra. “Efficiency and Generalization of Sparse Neural Networks.”
Institute of Science and Technology Austria, 2023. https://doi.org/10.15479/at:ista:13074.
ieee: A. Krumes, “Efficiency and generalization of sparse neural networks,” Institute
of Science and Technology Austria, 2023.
ista: Krumes A. 2023. Efficiency and generalization of sparse neural networks. Institute
of Science and Technology Austria.
mla: Krumes, Alexandra. Efficiency and Generalization of Sparse Neural Networks.
Institute of Science and Technology Austria, 2023, doi:10.15479/at:ista:13074.
short: A. Krumes, Efficiency and Generalization of Sparse Neural Networks, Institute
of Science and Technology Austria, 2023.
corr_author: '1'
date_created: 2023-05-23T17:07:53Z
date_published: 2023-05-23T00:00:00Z
date_updated: 2026-08-12T06:34:07Z
day: '23'
ddc:
- '000'
degree_awarded: PhD
department:
- _id: GradSch
- _id: DaAl
- _id: ChLa
doi: 10.15479/at:ista:13074
ec_funded: 1
file:
- access_level: open_access
checksum: 6b3354968403cb9d48cc5a83611fb571
content_type: application/pdf
creator: epeste
date_created: 2023-05-24T16:11:16Z
date_updated: 2023-05-24T16:11:16Z
file_id: '13087'
file_name: PhD_Thesis_Alexandra_Peste_final.pdf
file_size: 2152072
relation: main_file
success: 1
- access_level: closed
checksum: 8d0df94bbcf4db72c991f22503b3fd60
content_type: application/zip
creator: epeste
date_created: 2023-05-24T16:12:59Z
date_updated: 2023-05-24T16:12:59Z
file_id: '13088'
file_name: PhD_Thesis_APeste.zip
file_size: 1658293
relation: source_file
file_date_updated: 2023-05-24T16:12:59Z
has_accepted_license: '1'
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
page: '147'
project:
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '665385'
name: International IST Doctoral Program
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '13053'
relation: part_of_dissertation
status: public
- id: '11458'
relation: part_of_dissertation
status: public
- id: '12299'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Christoph
full_name: Lampert, Christoph
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0001-8622-7887
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
title: Efficiency and generalization of sparse neural networks
type: dissertation
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2023'
...
---
_id: '14459'
abstract:
- lang: eng
text: Autoencoders are a popular model in many branches of machine learning and
lossy data compression. However, their fundamental limits, the performance of
gradient methods and the features learnt during optimization remain poorly understood,
even in the two-layer setting. In fact, earlier work has considered either linear
autoencoders or specific training regimes (leading to vanishing or diverging compression
rates). Our paper addresses this gap by focusing on non-linear two-layer autoencoders
trained in the challenging proportional regime in which the input dimension scales
linearly with the size of the representation. Our results characterize the minimizers
of the population risk, and show that such minimizers are achieved by gradient
methods; their structure is also unveiled, thus leading to a concise description
of the features obtained via training. For the special case of a sign activation
function, our analysis establishes the fundamental limits for the lossy compression
of Gaussian sources via (shallow) autoencoders. Finally, while the results are
proved for Gaussian data, numerical simulations on standard datasets display the
universality of the theoretical predictions.
acknowledgement: Aleksandr Shevchenko, Kevin Kogler and Marco Mondelli are supported
by the 2019 Lopez-Loreta Prize. Hamed Hassani acknowledges the support by the NSF
CIF award (1910056) and the NSF Institute for CORE Emerging Methods in Data Science
(EnCORE).
alternative_title:
- PMLR
article_processing_charge: No
arxiv: 1
author:
- first_name: Aleksandr
full_name: Shevchenko, Aleksandr
id: F2B06EC2-C99E-11E9-89F0-752EE6697425
last_name: Shevchenko
- first_name: Kevin
full_name: Kögler, Kevin
id: 94ec913c-dc85-11ea-9058-e5051ab2428b
last_name: Kögler
- first_name: Hamed
full_name: Hassani, Hamed
last_name: Hassani
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
citation:
ama: 'Shevchenko A, Kögler K, Hassani H, Mondelli M. Fundamental limits of two-layer
autoencoders, and achieving them with gradient methods. In: Proceedings of
the 40th International Conference on Machine Learning. Vol 202. ML Research
Press; 2023:31151-31209.'
apa: 'Shevchenko, A., Kögler, K., Hassani, H., & Mondelli, M. (2023). Fundamental
limits of two-layer autoencoders, and achieving them with gradient methods. In
Proceedings of the 40th International Conference on Machine Learning (Vol.
202, pp. 31151–31209). Honolulu, Hawaii, HI, United States: ML Research Press.'
chicago: Shevchenko, Alexander, Kevin Kögler, Hamed Hassani, and Marco Mondelli.
“Fundamental Limits of Two-Layer Autoencoders, and Achieving Them with Gradient
Methods.” In Proceedings of the 40th International Conference on Machine Learning,
202:31151–209. ML Research Press, 2023.
ieee: A. Shevchenko, K. Kögler, H. Hassani, and M. Mondelli, “Fundamental limits
of two-layer autoencoders, and achieving them with gradient methods,” in Proceedings
of the 40th International Conference on Machine Learning, Honolulu, Hawaii,
HI, United States, 2023, vol. 202, pp. 31151–31209.
ista: 'Shevchenko A, Kögler K, Hassani H, Mondelli M. 2023. Fundamental limits of
two-layer autoencoders, and achieving them with gradient methods. Proceedings
of the 40th International Conference on Machine Learning. ICML: International
Conference on Machine Learning, PMLR, vol. 202, 31151–31209.'
mla: Shevchenko, Alexander, et al. “Fundamental Limits of Two-Layer Autoencoders,
and Achieving Them with Gradient Methods.” Proceedings of the 40th International
Conference on Machine Learning, vol. 202, ML Research Press, 2023, pp. 31151–209.
short: A. Shevchenko, K. Kögler, H. Hassani, M. Mondelli, in:, Proceedings of the
40th International Conference on Machine Learning, ML Research Press, 2023, pp.
31151–31209.
conference:
end_date: 2023-07-29
location: Honolulu, Hawaii, HI, United States
name: 'ICML: International Conference on Machine Learning'
start_date: 2023-07-23
corr_author: '1'
date_created: 2023-10-29T23:01:17Z
date_published: 2023-07-30T00:00:00Z
date_updated: 2026-09-04T22:30:18Z
day: '30'
department:
- _id: MaMo
- _id: DaAl
external_id:
arxiv:
- '2212.13468'
intvolume: ' 202'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2212.13468
month: '07'
oa: 1
oa_version: Preprint
page: 31151-31209
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: Proceedings of the 40th International Conference on Machine Learning
publication_identifier:
eissn:
- 2640-3498
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
related_material:
record:
- id: '17465'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Fundamental limits of two-layer autoencoders, and achieving them with gradient
methods
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 202
year: '2023'
...
---
_id: '11180'
abstract:
- lang: eng
text: "Designing and implementing efficient parallel priority schedulers is an active
research area. An intriguing proposed design is the Multi-Queue: given n threads
and m ≥ n distinct priority queues, task insertions are performed uniformly at
random, while, to delete, a thread picks two queues uniformly at random, and removes
the observed task of higher priority. This approach scales well, and has probabilistic
rank guarantees: roughly, the rank of each task removed, relative to remaining
tasks in all other queues, is O (m) in expectation. Yet, the performance of this
pattern is below that of well-engineered schedulers, which eschew theoretical
guarantees for practical efficiency.\r\n\r\nWe investigate whether it is possible
to design and implement a Multi-Queue-based task scheduler that is both highly-efficient
and has analytical guarantees. We propose a new variant called the Stealing Multi-Queue
(SMQ), a cache-efficient variant of the Multi-Queue, which leverages both queue
affinity---each thread has a local queue, from which tasks are usually removed;
but, with some probability, threads also attempt to steal higher-priority tasks
from the other queues---and task batching, that is, the processing of several
tasks in a single insert / remove step. These ideas are well-known for task scheduling
without priorities; our theoretical contribution is showing that, despite relaxations,
this design can still provide rank guarantees, which in turn implies bounds on
total work performed. We provide a general SMQ implementation which can surpass
state-of-the-art schedulers such as OBIM and PMOD in terms of performance on popular
graph-processing benchmarks. Notably, the performance improvement comes mainly
from the superior rank guarantees provided by our scheduler, confirming that analytically-reasoned
approaches can still provide performance improvements for priority task scheduling."
acknowledgement: We would like to thank the anonymous reviewers for their useful comments.
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).
article_processing_charge: No
arxiv: 1
author:
- first_name: Anastasiia
full_name: Postnikova, Anastasiia
last_name: Postnikova
- first_name: Nikita
full_name: Koval, Nikita
id: 2F4DB10C-F248-11E8-B48F-1D18A9856A87
last_name: Koval
- first_name: Giorgi
full_name: Nadiradze, Giorgi
id: 3279A00C-F248-11E8-B48F-1D18A9856A87
last_name: Nadiradze
orcid: 0000-0001-5634-0731
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
citation:
ama: 'Postnikova A, Koval N, Nadiradze G, Alistarh D-A. Multi-queues can be state-of-the-art
priority schedulers. In: Proceedings of the 27th ACM SIGPLAN Symposium on Principles
and Practice of Parallel Programming. Association for Computing Machinery;
2022:353-367. doi:10.1145/3503221.3508432'
apa: 'Postnikova, A., Koval, N., Nadiradze, G., & Alistarh, D.-A. (2022). Multi-queues
can be state-of-the-art priority schedulers. In Proceedings of the 27th ACM
SIGPLAN Symposium on Principles and Practice of Parallel Programming (pp.
353–367). Seoul, Republic of Korea: Association for Computing Machinery. https://doi.org/10.1145/3503221.3508432'
chicago: Postnikova, Anastasiia, Nikita Koval, Giorgi Nadiradze, and Dan-Adrian
Alistarh. “Multi-Queues Can Be State-of-the-Art Priority Schedulers.” In Proceedings
of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming,
353–67. Association for Computing Machinery, 2022. https://doi.org/10.1145/3503221.3508432.
ieee: A. Postnikova, N. Koval, G. Nadiradze, and D.-A. Alistarh, “Multi-queues can
be state-of-the-art priority schedulers,” in Proceedings of the 27th ACM SIGPLAN
Symposium on Principles and Practice of Parallel Programming, Seoul, Republic
of Korea, 2022, pp. 353–367.
ista: 'Postnikova A, Koval N, Nadiradze G, Alistarh D-A. 2022. Multi-queues can
be state-of-the-art priority schedulers. Proceedings of the 27th ACM SIGPLAN Symposium
on Principles and Practice of Parallel Programming. PPoPP: Sympopsium on Principles
and Practice of Parallel Programming, 353–367.'
mla: Postnikova, Anastasiia, et al. “Multi-Queues Can Be State-of-the-Art Priority
Schedulers.” Proceedings of the 27th ACM SIGPLAN Symposium on Principles and
Practice of Parallel Programming, Association for Computing Machinery, 2022,
pp. 353–67, doi:10.1145/3503221.3508432.
short: A. Postnikova, N. Koval, G. Nadiradze, D.-A. Alistarh, in:, Proceedings of
the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming,
Association for Computing Machinery, 2022, pp. 353–367.
conference:
end_date: 2022-04-06
location: Seoul, Republic of Korea
name: 'PPoPP: Sympopsium on Principles and Practice of Parallel Programming'
start_date: 2022-04-02
corr_author: '1'
date_created: 2022-04-17T22:01:46Z
date_published: 2022-04-02T00:00:00Z
date_updated: 2025-04-14T07:49:13Z
day: '02'
department:
- _id: DaAl
doi: 10.1145/3503221.3508432
ec_funded: 1
external_id:
arxiv:
- '2109.00657'
isi:
- '000883318200025'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: ' https://doi.org/10.48550/arXiv.2109.00657'
month: '04'
oa: 1
oa_version: Preprint
page: 353-367
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
publication: Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice
of Parallel Programming
publication_identifier:
isbn:
- '9781450392044'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
record:
- id: '13076'
relation: research_data
status: public
scopus_import: '1'
status: public
title: Multi-queues can be state-of-the-art priority schedulers
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
year: '2022'
...
---
_id: '11181'
abstract:
- lang: eng
text: 'To maximize the performance of concurrent data structures, researchers have
often turned to highly complex fine-grained techniques, resulting in efficient
and elegant algorithms, which can however be often difficult to understand and
prove correct. While simpler techniques exist, such as transactional memory, they
can have limited performance or portability relative to their fine-grained counterparts.
Approaches at both ends of this complexity-performance spectrum have been extensively
explored, but relatively less is known about the middle ground: approaches that
are willing to sacrifice some performance for simplicity, while remaining competitive
with state-of-the-art handcrafted designs. In this paper, we explore this middle
ground, and present PathCAS, a primitive that combines ideas from multi-word CAS
(KCAS) and transactional memory approaches, while carefully avoiding overhead.
We show how PathCAS can be used to implement efficient search data structures
relatively simply, using an internal binary search tree as an example, then extending
this to an AVL tree. Our best implementations outperform many handcrafted search
trees: in search-heavy workloads, it rivals the BCCO tree [5], the fastest known
concurrent binary tree in terms of search performance [3]. Our results suggest
that PathCAS can yield concurrent data structures that are relatively easy to
build and prove correct, while offering surprisingly high performance.'
acknowledgement: "This work was supported by: the Natural Sciences and Engineering
Research Council of Canada (NSERC) Collaborative Research and Development grant:
CRDPJ 539431-19, the\r\nCanada Foundation for Innovation John R. Evans Leaders Fund
with equal support from the Ontario Research Fund CFI Leaders Opportunity Fund:
38512, Waterloo Huawei Joint Innovation Lab project “Scalable Infrastructure for
Next Generation Data Management Systems”, NSERC Discovery Launch Supplement: DGECR-2019-00048,
NSERC Discovery\r\nProgram under the grants: RGPIN-2019-04227 and RGPIN04512-2018,
and the University of Waterloo. We would also like to thank the reviewers for their
insightful comments."
article_processing_charge: No
author:
- first_name: Trevor A
full_name: Brown, Trevor A
id: 3569F0A0-F248-11E8-B48F-1D18A9856A87
last_name: Brown
- first_name: William
full_name: Sigouin, William
last_name: Sigouin
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
citation:
ama: 'Brown TA, Sigouin W, Alistarh D-A. PathCAS: An efficient middle ground for
concurrent search data structures. In: Proceedings of the 27th ACM SIGPLAN
Symposium on Principles and Practice of Parallel Programming. Association
for Computing Machinery; 2022:385-399. doi:10.1145/3503221.3508410'
apa: 'Brown, T. A., Sigouin, W., & Alistarh, D.-A. (2022). PathCAS: An efficient
middle ground for concurrent search data structures. In Proceedings of the
27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
(pp. 385–399). Seoul, Republic of Korea: Association for Computing Machinery.
https://doi.org/10.1145/3503221.3508410'
chicago: 'Brown, Trevor A, William Sigouin, and Dan-Adrian Alistarh. “PathCAS: An
Efficient Middle Ground for Concurrent Search Data Structures.” In Proceedings
of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming,
385–99. Association for Computing Machinery, 2022. https://doi.org/10.1145/3503221.3508410.'
ieee: 'T. A. Brown, W. Sigouin, and D.-A. Alistarh, “PathCAS: An efficient middle
ground for concurrent search data structures,” in Proceedings of the 27th ACM
SIGPLAN Symposium on Principles and Practice of Parallel Programming, Seoul,
Republic of Korea, 2022, pp. 385–399.'
ista: 'Brown TA, Sigouin W, Alistarh D-A. 2022. PathCAS: An efficient middle ground
for concurrent search data structures. Proceedings of the 27th ACM SIGPLAN Symposium
on Principles and Practice of Parallel Programming. PPoPP: Sympopsium on Principles
and Practice of Parallel Programming, 385–399.'
mla: 'Brown, Trevor A., et al. “PathCAS: An Efficient Middle Ground for Concurrent
Search Data Structures.” Proceedings of the 27th ACM SIGPLAN Symposium on Principles
and Practice of Parallel Programming, Association for Computing Machinery,
2022, pp. 385–99, doi:10.1145/3503221.3508410.'
short: T.A. Brown, W. Sigouin, D.-A. Alistarh, in:, Proceedings of the 27th ACM
SIGPLAN Symposium on Principles and Practice of Parallel Programming, Association
for Computing Machinery, 2022, pp. 385–399.
conference:
end_date: 2022-04-06
location: Seoul, Republic of Korea
name: 'PPoPP: Sympopsium on Principles and Practice of Parallel Programming'
start_date: 2022-04-02
corr_author: '1'
date_created: 2022-04-17T22:01:46Z
date_published: 2022-04-02T00:00:00Z
date_updated: 2024-10-09T21:02:23Z
day: '02'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1145/3503221.3508410
external_id:
isi:
- '000883318200027'
file:
- access_level: open_access
checksum: 8ceea411fa133795cd4903529498eb6b
content_type: application/pdf
creator: dernst
date_created: 2022-08-05T09:19:29Z
date_updated: 2022-08-05T09:19:29Z
file_id: '11731'
file_name: 2022_PPoPP_Brown.pdf
file_size: 1128343
relation: main_file
success: 1
file_date_updated: 2022-08-05T09:19:29Z
has_accepted_license: '1'
isi: 1
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
page: 385-399
publication: Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice
of Parallel Programming
publication_identifier:
isbn:
- '9781450392044'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'PathCAS: An efficient middle ground for concurrent search data structures'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
year: '2022'
...
---
_id: '11183'
abstract:
- lang: eng
text: "Subgraph detection has recently been one of the most studied problems in
the CONGEST model of distributed computing. In this work, we study the distributed
complexity of problems closely related to subgraph detection, mainly focusing
on induced subgraph detection. The main line of this work presents lower bounds
and parameterized algorithms w.r.t structural parameters of the input graph:\r\n-
On general graphs, we give unconditional lower bounds for induced detection of
cycles and patterns of treewidth 2 in CONGEST. Moreover, by adapting reductions
from centralized parameterized complexity, we prove lower bounds in CONGEST for
detecting patterns with a 4-clique, and for induced path detection conditional
on the hardness of triangle detection in the congested clique.\r\n- On graphs
of bounded degeneracy, we show that induced paths can be detected fast in CONGEST
using techniques from parameterized algorithms, while detecting cycles and patterns
of treewidth 2 is hard.\r\n- On graphs of bounded vertex cover number, we show
that induced subgraph detection is easy in CONGEST for any pattern graph. More
specifically, we adapt a centralized parameterized algorithm for a more general
maximum common induced subgraph detection problem to the distributed setting.
In addition to these induced subgraph detection results, we study various related
problems in the CONGEST and congested clique models, including for multicolored
versions of subgraph-detection-like problems."
acknowledgement: "Amir Nikabadi: Supported by the LABEX MILYON (ANR-10-LABX-0070)
of Université de Lyon, within the program “Investissements d’Avenir” (ANR-11-IDEX-0007)
operated by the French National Research Agency (ANR). Janne H. Korhonen: Supported
by the European Research Council (ERC) under the European Union’s Horizon 2020 research
and innovation programme (grant agreement No 805223 ScaleML).\r\nWe thank François
Le Gall and Masayuki Miyamoto for sharing their work on lower bounds for induced
subgraph detection [36]."
alternative_title:
- LIPIcs
article_number: '15'
article_processing_charge: No
author:
- first_name: Amir
full_name: Nikabadi, Amir
last_name: Nikabadi
- first_name: Janne
full_name: Korhonen, Janne
id: C5402D42-15BC-11E9-A202-CA2BE6697425
last_name: Korhonen
citation:
ama: 'Nikabadi A, Korhonen J. Beyond distributed subgraph detection: Induced subgraphs,
multicolored problems and graph parameters. In: Bramas Q, Gramoli V, Milani A,
eds. 25th International Conference on Principles of Distributed Systems.
Vol 217. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:10.4230/LIPIcs.OPODIS.2021.15'
apa: 'Nikabadi, A., & Korhonen, J. (2022). Beyond distributed subgraph detection:
Induced subgraphs, multicolored problems and graph parameters. In Q. Bramas, V.
Gramoli, & A. Milani (Eds.), 25th International Conference on Principles
of Distributed Systems (Vol. 217). Strasbourg, France: Schloss Dagstuhl -
Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.OPODIS.2021.15'
chicago: 'Nikabadi, Amir, and Janne Korhonen. “Beyond Distributed Subgraph Detection:
Induced Subgraphs, Multicolored Problems and Graph Parameters.” In 25th International
Conference on Principles of Distributed Systems, edited by Quentin Bramas,
Vincent Gramoli, and Alessia Milani, Vol. 217. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2022. https://doi.org/10.4230/LIPIcs.OPODIS.2021.15.'
ieee: 'A. Nikabadi and J. Korhonen, “Beyond distributed subgraph detection: Induced
subgraphs, multicolored problems and graph parameters,” in 25th International
Conference on Principles of Distributed Systems, Strasbourg, France, 2022,
vol. 217.'
ista: 'Nikabadi A, Korhonen J. 2022. Beyond distributed subgraph detection: Induced
subgraphs, multicolored problems and graph parameters. 25th International Conference
on Principles of Distributed Systems. OPODIS, LIPIcs, vol. 217, 15.'
mla: 'Nikabadi, Amir, and Janne Korhonen. “Beyond Distributed Subgraph Detection:
Induced Subgraphs, Multicolored Problems and Graph Parameters.” 25th International
Conference on Principles of Distributed Systems, edited by Quentin Bramas
et al., vol. 217, 15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022,
doi:10.4230/LIPIcs.OPODIS.2021.15.'
short: A. Nikabadi, J. Korhonen, in:, Q. Bramas, V. Gramoli, A. Milani (Eds.), 25th
International Conference on Principles of Distributed Systems, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2022.
conference:
end_date: 2021-12-15
location: Strasbourg, France
name: OPODIS
start_date: 2021-12-13
corr_author: '1'
date_created: 2022-04-17T22:01:47Z
date_published: 2022-02-01T00:00:00Z
date_updated: 2025-04-14T07:49:13Z
day: '01'
ddc:
- '510'
department:
- _id: DaAl
doi: 10.4230/LIPIcs.OPODIS.2021.15
ec_funded: 1
editor:
- first_name: Quentin
full_name: Bramas, Quentin
last_name: Bramas
- first_name: Vincent
full_name: Gramoli, Vincent
last_name: Gramoli
- first_name: Alessia
full_name: Milani, Alessia
last_name: Milani
file:
- access_level: open_access
checksum: 626551c14de5d4091573200ed0535752
content_type: application/pdf
creator: dernst
date_created: 2022-05-02T07:53:00Z
date_updated: 2022-05-02T07:53:00Z
file_id: '11345'
file_name: 2022_LIPICs_Nikabadi.pdf
file_size: 790396
relation: main_file
success: 1
file_date_updated: 2022-05-02T07:53:00Z
has_accepted_license: '1'
intvolume: ' 217'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
publication: 25th International Conference on Principles of Distributed Systems
publication_identifier:
isbn:
- '9783959772198'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Beyond distributed subgraph detection: Induced subgraphs, multicolored problems
and graph parameters'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 217
year: '2022'
...
---
_id: '11184'
abstract:
- lang: eng
text: "Let G be a graph on n nodes. In the stochastic population protocol model,
a collection of n indistinguishable, resource-limited nodes collectively solve
tasks via pairwise interactions. In each interaction, two randomly chosen neighbors
first read each other’s states, and then update their local states. A rich line
of research has established tight upper and lower bounds on the complexity of
fundamental tasks, such as majority and leader election, in this model, when G
is a clique. Specifically, in the clique, these tasks can be solved fast, i.e.,
in n polylog n pairwise interactions, with high probability, using at most polylog
n states per node.\r\nIn this work, we consider the more general setting where
G is an arbitrary regular graph, and present a technique for simulating protocols
designed for fully-connected networks in any connected regular graph. Our main
result is a simulation that is efficient on many interesting graph families: roughly,
the simulation overhead is polylogarithmic in the number of nodes, and quadratic
in the conductance of the graph. As a sample application, we show that, in any
regular graph with conductance φ, both leader election and exact majority can
be solved in φ^{-2} ⋅ n polylog n pairwise interactions, with high probability,
using at most φ^{-2} ⋅ polylog n states per node. This shows that there are fast
and space-efficient population protocols for leader election and exact majority
on graphs with good expansion properties. We believe our results will prove generally
useful, as they allow efficient technology transfer between the well-mixed (clique)
case, and the under-explored spatial setting."
acknowledgement: "Dan Alistarh: This project has received funding from the European
Research Council (ERC)\r\nunder the European Union’s Horizon 2020 research and innovation
programme (grant agreement No.805223 ScaleML).\r\nJoel Rybicki: This project has
received from the European Union’s Horizon 2020 research and\r\ninnovation programme
under the Marie Skłodowska-Curie grant agreement No. 840605.\r\nAcknowledgements
We grateful to Giorgi Nadiradze for pointing out a generalisation of the phase clock
construction to non-regular graphs. We also thank anonymous reviewers for their
useful comments on earlier versions of this manuscript."
alternative_title:
- LIPIcs
article_number: '14'
article_processing_charge: No
arxiv: 1
author:
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
- first_name: Rati
full_name: Gelashvili, Rati
last_name: Gelashvili
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
citation:
ama: 'Alistarh D-A, Gelashvili R, Rybicki J. Fast graphical population protocols.
In: Bramas Q, Gramoli V, Milani A, eds. 25th International Conference on Principles
of Distributed Systems. Vol 217. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2022. doi:10.4230/LIPIcs.OPODIS.2021.14'
apa: 'Alistarh, D.-A., Gelashvili, R., & Rybicki, J. (2022). Fast graphical
population protocols. In Q. Bramas, V. Gramoli, & A. Milani (Eds.), 25th
International Conference on Principles of Distributed Systems (Vol. 217).
Strasbourg, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.OPODIS.2021.14'
chicago: Alistarh, Dan-Adrian, Rati Gelashvili, and Joel Rybicki. “Fast Graphical
Population Protocols.” In 25th International Conference on Principles of Distributed
Systems, edited by Quentin Bramas, Vincent Gramoli, and Alessia Milani, Vol.
217. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. https://doi.org/10.4230/LIPIcs.OPODIS.2021.14.
ieee: D.-A. Alistarh, R. Gelashvili, and J. Rybicki, “Fast graphical population
protocols,” in 25th International Conference on Principles of Distributed Systems,
Strasbourg, France, 2022, vol. 217.
ista: Alistarh D-A, Gelashvili R, Rybicki J. 2022. Fast graphical population protocols.
25th International Conference on Principles of Distributed Systems. OPODIS, LIPIcs,
vol. 217, 14.
mla: Alistarh, Dan-Adrian, et al. “Fast Graphical Population Protocols.” 25th
International Conference on Principles of Distributed Systems, edited by Quentin
Bramas et al., vol. 217, 14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2022, doi:10.4230/LIPIcs.OPODIS.2021.14.
short: D.-A. Alistarh, R. Gelashvili, J. Rybicki, in:, Q. Bramas, V. Gramoli, A.
Milani (Eds.), 25th International Conference on Principles of Distributed Systems,
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
conference:
end_date: 2021-12-15
location: Strasbourg, France
name: OPODIS
start_date: 2021-12-13
corr_author: '1'
date_created: 2022-04-17T22:01:47Z
date_published: 2022-02-01T00:00:00Z
date_updated: 2025-04-14T07:49:13Z
day: '01'
ddc:
- '510'
department:
- _id: DaAl
doi: 10.4230/LIPIcs.OPODIS.2021.14
ec_funded: 1
editor:
- first_name: Quentin
full_name: Bramas, Quentin
last_name: Bramas
- first_name: Vincent
full_name: Gramoli, Vincent
last_name: Gramoli
- first_name: Alessia
full_name: Milani, Alessia
last_name: Milani
external_id:
arxiv:
- '2102.08808'
file:
- access_level: open_access
checksum: 2c7c982174c6f98c4ca6e92539d15086
content_type: application/pdf
creator: dernst
date_created: 2022-05-02T08:06:33Z
date_updated: 2022-05-02T08:06:33Z
file_id: '11346'
file_name: 2022_LIPICs_Alistarh.pdf
file_size: 959406
relation: main_file
success: 1
file_date_updated: 2022-05-02T08:06:33Z
has_accepted_license: '1'
intvolume: ' 217'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
- _id: 26A5D39A-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '840605'
name: Coordination in constrained and natural distributed systems
publication: 25th International Conference on Principles of Distributed Systems
publication_identifier:
isbn:
- '9783959772198'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Fast graphical population protocols
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 217
year: '2022'
...
---
_id: '11707'
abstract:
- lang: eng
text: 'In this work we introduce the graph-theoretic notion of mendability: for
each locally checkable graph problem we can define its mending radius, which captures
the idea of how far one needs to modify a partial solution in order to “patch
a hole.” We explore how mendability is connected to the existence of efficient
algorithms, especially in distributed, parallel, and fault-tolerant settings.
It is easy to see that O(1)-mendable problems are also solvable in O(log∗n) rounds
in the LOCAL model of distributed computing. One of the surprises is that in paths
and cycles, a converse also holds in the following sense: if a problem Π can be
solved in O(log∗n), there is always a restriction Π′⊆Π that is still efficiently
solvable but that is also O(1)-mendable. We also explore the structure of the
landscape of mendability. For example, we show that in trees, the mending radius
of any locally checkable problem is O(1), Θ(logn), or Θ(n), while in general graphs
the structure is much more diverse.'
acknowledgement: This project has received funding from the European Union’s Horizon
2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement
No 840605. This work was supported in part by the Academy of Finland, Grants 314888
and 333837. The authors would also like to thank David Harris, Neven Villani, and
the anonymous reviewers for their very helpful comments and feedback on previous
versions of this work.
article_processing_charge: No
arxiv: 1
author:
- first_name: Alkida
full_name: Balliu, Alkida
last_name: Balliu
- first_name: Juho
full_name: Hirvonen, Juho
last_name: Hirvonen
- first_name: Darya
full_name: Melnyk, Darya
last_name: Melnyk
- first_name: Dennis
full_name: Olivetti, Dennis
last_name: Olivetti
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
- first_name: Jukka
full_name: Suomela, Jukka
last_name: Suomela
citation:
ama: 'Balliu A, Hirvonen J, Melnyk D, Olivetti D, Rybicki J, Suomela J. Local mending.
In: Parter M, ed. International Colloquium on Structural Information and Communication
Complexity. Vol 13298. LNCS. Springer Nature; 2022:1-20. doi:10.1007/978-3-031-09993-9_1'
apa: 'Balliu, A., Hirvonen, J., Melnyk, D., Olivetti, D., Rybicki, J., & Suomela,
J. (2022). Local mending. In M. Parter (Ed.), International Colloquium on Structural
Information and Communication Complexity (Vol. 13298, pp. 1–20). Paderborn,
Germany: Springer Nature. https://doi.org/10.1007/978-3-031-09993-9_1'
chicago: Balliu, Alkida, Juho Hirvonen, Darya Melnyk, Dennis Olivetti, Joel Rybicki,
and Jukka Suomela. “Local Mending.” In International Colloquium on Structural
Information and Communication Complexity, edited by Merav Parter, 13298:1–20.
LNCS. Springer Nature, 2022. https://doi.org/10.1007/978-3-031-09993-9_1.
ieee: A. Balliu, J. Hirvonen, D. Melnyk, D. Olivetti, J. Rybicki, and J. Suomela,
“Local mending,” in International Colloquium on Structural Information and
Communication Complexity, Paderborn, Germany, 2022, vol. 13298, pp. 1–20.
ista: 'Balliu A, Hirvonen J, Melnyk D, Olivetti D, Rybicki J, Suomela J. 2022. Local
mending. International Colloquium on Structural Information and Communication
Complexity. SIROCCO: Structural Information and Communication ComplexityLNCS vol.
13298, 1–20.'
mla: Balliu, Alkida, et al. “Local Mending.” International Colloquium on Structural
Information and Communication Complexity, edited by Merav Parter, vol. 13298,
Springer Nature, 2022, pp. 1–20, doi:10.1007/978-3-031-09993-9_1.
short: A. Balliu, J. Hirvonen, D. Melnyk, D. Olivetti, J. Rybicki, J. Suomela, in:,
M. Parter (Ed.), International Colloquium on Structural Information and Communication
Complexity, Springer Nature, 2022, pp. 1–20.
conference:
end_date: 2022-06-29
location: Paderborn, Germany
name: 'SIROCCO: Structural Information and Communication Complexity'
start_date: 2022-06-27
date_created: 2022-07-31T22:01:49Z
date_published: 2022-06-25T00:00:00Z
date_updated: 2025-04-14T07:50:55Z
day: '25'
department:
- _id: DaAl
doi: 10.1007/978-3-031-09993-9_1
ec_funded: 1
editor:
- first_name: Merav
full_name: Parter, Merav
last_name: Parter
external_id:
arxiv:
- '2102.08703'
isi:
- '000876977400001'
intvolume: ' 13298'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2102.08703
month: '06'
oa: 1
oa_version: Preprint
page: 1-20
project:
- _id: 26A5D39A-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '840605'
name: Coordination in constrained and natural distributed systems
publication: International Colloquium on Structural Information and Communication
Complexity
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031099922'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
series_title: LNCS
status: public
title: Local mending
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 13298
year: '2022'
...
---
_id: '11844'
abstract:
- lang: eng
text: "In the stochastic population protocol model, we are given a connected graph
with n nodes, and in every time step, a scheduler samples an edge of the graph
uniformly at random and the nodes connected by this edge interact. A fundamental
task in this model is stable leader election, in which all nodes start in an identical
state and the aim is to reach a configuration in which (1) exactly one node is
elected as leader and (2) this node remains as the unique leader no matter what
sequence of interactions follows. On cliques, the complexity of this problem has
recently been settled: time-optimal protocols stabilize in Θ(n log n) expected
steps using Θ(log log n) states, whereas protocols that use O(1) states require
Θ(n2) expected steps.\r\n\r\nIn this work, we investigate the complexity of stable
leader election on general graphs. We provide the first non-trivial time lower
bounds for leader election on general graphs, showing that, when moving beyond
cliques, the complexity landscape of leader election becomes very diverse: the
time required to elect a leader can range from O(1) to Θ(n3) expected steps. On
the upper bound side, we first observe that there exists a protocol that is time-optimal
on many graph families, but uses polynomially-many states. In contrast, we give
a near-time-optimal protocol that uses only O(log2n) states that is at most a
factor log n slower. Finally, we show that the constant-state protocol of Beauquier
et al. [OPODIS 2013] is at most a factor n log n slower than the fast polynomial-state
protocol. Moreover, among constant-state protocols, this protocol has near-optimal
average case complexity on dense random graphs."
acknowledgement: We thank the anonymous reviewers for their helpful comments. We gratefully
acknowledge funding from the European Research Council (ERC) under the European
Union’s Horizon 2020 research and innovation programme (grant agreement No 805223
ScaleML).
article_processing_charge: Yes (via OA deal)
arxiv: 1
author:
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
- first_name: Sasha
full_name: Voitovych, Sasha
last_name: Voitovych
citation:
ama: 'Alistarh D-A, Rybicki J, Voitovych S. Near-optimal leader election in population
protocols on graphs. In: Proceedings of the Annual ACM Symposium on Principles
of Distributed Computing. Association for Computing Machinery; 2022:246-256.
doi:10.1145/3519270.3538435'
apa: 'Alistarh, D.-A., Rybicki, J., & Voitovych, S. (2022). Near-optimal leader
election in population protocols on graphs. In Proceedings of the Annual ACM
Symposium on Principles of Distributed Computing (pp. 246–256). Salerno, Italy:
Association for Computing Machinery. https://doi.org/10.1145/3519270.3538435'
chicago: Alistarh, Dan-Adrian, Joel Rybicki, and Sasha Voitovych. “Near-Optimal
Leader Election in Population Protocols on Graphs.” In Proceedings of the Annual
ACM Symposium on Principles of Distributed Computing, 246–56. Association
for Computing Machinery, 2022. https://doi.org/10.1145/3519270.3538435.
ieee: D.-A. Alistarh, J. Rybicki, and S. Voitovych, “Near-optimal leader election
in population protocols on graphs,” in Proceedings of the Annual ACM Symposium
on Principles of Distributed Computing, Salerno, Italy, 2022, pp. 246–256.
ista: 'Alistarh D-A, Rybicki J, Voitovych S. 2022. Near-optimal leader election
in population protocols on graphs. Proceedings of the Annual ACM Symposium on
Principles of Distributed Computing. PODC: Symposium on Principles of Distributed
Computing, 246–256.'
mla: Alistarh, Dan-Adrian, et al. “Near-Optimal Leader Election in Population Protocols
on Graphs.” Proceedings of the Annual ACM Symposium on Principles of Distributed
Computing, Association for Computing Machinery, 2022, pp. 246–56, doi:10.1145/3519270.3538435.
short: D.-A. Alistarh, J. Rybicki, S. Voitovych, in:, Proceedings of the Annual
ACM Symposium on Principles of Distributed Computing, Association for Computing
Machinery, 2022, pp. 246–256.
conference:
end_date: 2022-07-29
location: Salerno, Italy
name: 'PODC: Symposium on Principles of Distributed Computing'
start_date: 2022-07-25
corr_author: '1'
date_created: 2022-08-14T22:01:46Z
date_published: 2022-07-21T00:00:00Z
date_updated: 2025-12-30T09:04:17Z
day: '21'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1145/3519270.3538435
ec_funded: 1
external_id:
arxiv:
- '2205.12597'
isi:
- '001031439100030'
file:
- access_level: open_access
checksum: 4c6b29172b8e355b4fbc364a2e0827b2
content_type: application/pdf
creator: cchlebak
date_created: 2022-08-16T08:05:15Z
date_updated: 2022-08-16T08:05:15Z
file_id: '11854'
file_name: 2022_PODC_Alistarh.pdf
file_size: 1593474
relation: main_file
success: 1
file_date_updated: 2022-08-16T08:05:15Z
has_accepted_license: '1'
isi: 1
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 246-256
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
publication: Proceedings of the Annual ACM Symposium on Principles of Distributed
Computing
publication_identifier:
isbn:
- '9781450392624'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
record:
- id: '19969'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Near-optimal leader election in population protocols on graphs
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2022'
...
---
_id: '12182'
abstract:
- lang: eng
text: 'Online algorithms make decisions based on past inputs, with the goal of being
competitive against an algorithm that sees also future inputs. In this work, we
introduce time-local online algorithms; these are online algorithms in which the
output at any given time is a function of only T latest inputs. Our main observation
is that time-local online algorithms are closely connected to local distributed
graph algorithms: distributed algorithms make decisions based on the local information
in the spatial dimension, while time-local online algorithms make decisions based
on the local information in the temporal dimension. We formalize this connection,
and show how we can directly use the tools developed to study distributed approximability
of graph optimization problems to prove upper and lower bounds on the competitive
ratio achieved with time-local online algorithms. Moreover, we show how to use
computational techniques to synthesize optimal time-local algorithms.'
acknowledgement: "This research has received funding from the German Research Foundation
(DFG), grant\r\n470029389 (FlexNets), 2021-2024, and the Marie Skłodowska-Curie
grant agreement No. 840605."
article_number: '52'
article_processing_charge: No
author:
- first_name: Maciej
full_name: Pacut, Maciej
last_name: Pacut
- first_name: Mahmoud
full_name: Parham, Mahmoud
last_name: Parham
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
- first_name: Jukka
full_name: Suomela, Jukka
last_name: Suomela
- first_name: Aleksandr
full_name: Tereshchenko, Aleksandr
last_name: Tereshchenko
citation:
ama: 'Pacut M, Parham M, Rybicki J, Schmid S, Suomela J, Tereshchenko A. Brief announcement:
Temporal locality in online algorithms. In: 36th International Symposium on
Distributed Computing. Vol 246. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2022. doi:10.4230/LIPIcs.DISC.2022.52'
apa: 'Pacut, M., Parham, M., Rybicki, J., Schmid, S., Suomela, J., & Tereshchenko,
A. (2022). Brief announcement: Temporal locality in online algorithms. In 36th
International Symposium on Distributed Computing (Vol. 246). Augusta, GA,
United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2022.52'
chicago: 'Pacut, Maciej, Mahmoud Parham, Joel Rybicki, Stefan Schmid, Jukka Suomela,
and Aleksandr Tereshchenko. “Brief Announcement: Temporal Locality in Online Algorithms.”
In 36th International Symposium on Distributed Computing, Vol. 246. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2022. https://doi.org/10.4230/LIPIcs.DISC.2022.52.'
ieee: 'M. Pacut, M. Parham, J. Rybicki, S. Schmid, J. Suomela, and A. Tereshchenko,
“Brief announcement: Temporal locality in online algorithms,” in 36th International
Symposium on Distributed Computing, Augusta, GA, United States, 2022, vol.
246.'
ista: 'Pacut M, Parham M, Rybicki J, Schmid S, Suomela J, Tereshchenko A. 2022.
Brief announcement: Temporal locality in online algorithms. 36th International
Symposium on Distributed Computing. DISC: Symposium on Distributed Computing vol.
246, 52.'
mla: 'Pacut, Maciej, et al. “Brief Announcement: Temporal Locality in Online Algorithms.”
36th International Symposium on Distributed Computing, vol. 246, 52, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2022, doi:10.4230/LIPIcs.DISC.2022.52.'
short: M. Pacut, M. Parham, J. Rybicki, S. Schmid, J. Suomela, A. Tereshchenko,
in:, 36th International Symposium on Distributed Computing, Schloss Dagstuhl -
Leibniz-Zentrum für Informatik, 2022.
conference:
end_date: 2022-10-27
location: Augusta, GA, United States
name: 'DISC: Symposium on Distributed Computing'
start_date: 2022-10-25
date_created: 2023-01-13T11:06:28Z
date_published: 2022-10-17T00:00:00Z
date_updated: 2025-04-14T07:50:55Z
day: '17'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.4230/LIPIcs.DISC.2022.52
ec_funded: 1
file:
- access_level: open_access
checksum: 11bbb56f68a00f2cf6bcce6cc7f5c5f9
content_type: application/pdf
creator: dernst
date_created: 2023-01-27T06:58:02Z
date_updated: 2023-01-27T06:58:02Z
file_id: '12409'
file_name: 2022_LIPICs_Pacut.pdf
file_size: 524804
relation: main_file
success: 1
file_date_updated: 2023-01-27T06:58:02Z
has_accepted_license: '1'
intvolume: ' 246'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
project:
- _id: 26A5D39A-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '840605'
name: Coordination in constrained and natural distributed systems
publication: 36th International Symposium on Distributed Computing
publication_identifier:
eisbn:
- '9783959772556'
eissn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Brief announcement: Temporal locality in online algorithms'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 246
year: '2022'
...
---
_id: '12780'
abstract:
- lang: eng
text: "The ability to scale out training workloads has been one of the key performance
enablers of deep learning. The main scaling approach is data-parallel GPU-based
training, which has been boosted by hardware and software support for highly efficient
point-to-point communication, and in particular via hardware bandwidth over-provisioning.
Overprovisioning comes at a cost: there is an order of magnitude price difference
between \"cloud-grade\" servers with such support, relative to their popular \"consumer-grade\"
counterparts, although single server-grade and consumer-grade GPUs can have similar
computational envelopes.\r\n\r\nIn this paper, we show that the costly hardware
overprovisioning approach can be supplanted via algorithmic and system design,
and propose a framework called CGX, which provides efficient software support
for compressed communication in ML applications, for both multi-GPU single-node
training, as well as larger-scale multi-node training. CGX is based on two technical
advances: At the system level, it relies on a re-developed communication stack
for ML frameworks, which provides flexible, highly-efficient support for compressed
communication. At the application level, it provides seamless, parameter-free
integration with popular frameworks, so that end-users do not have to modify training
recipes, nor significant training code. This is complemented by a layer-wise adaptive
compression technique which dynamically balances compression gains with accuracy
preservation. CGX 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."
acknowledgement: The authors sincerely thank Nikoli Dryden, Tal Ben-Nun, Torsten Hoefler
and Bapi Chatterjee for useful discussions throughout the development of this project.
article_processing_charge: Yes (via OA deal)
arxiv: 1
author:
- first_name: Ilia
full_name: Markov, Ilia
id: D0CF4148-C985-11E9-8066-0BDEE5697425
last_name: Markov
- first_name: Hamidreza
full_name: Ramezanikebrya, Hamidreza
last_name: Ramezanikebrya
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
citation:
ama: 'Markov I, Ramezanikebrya H, Alistarh D-A. CGX: Adaptive system support for
communication-efficient deep learning. In: Proceedings of the 23rd ACM/IFIP
International Middleware Conference. Association for Computing Machinery;
2022:241-254. doi:10.1145/3528535.3565248'
apa: 'Markov, I., Ramezanikebrya, H., & Alistarh, D.-A. (2022). CGX: Adaptive
system support for communication-efficient deep learning. In Proceedings of
the 23rd ACM/IFIP International Middleware Conference (pp. 241–254). Quebec,
QC, Canada: Association for Computing Machinery. https://doi.org/10.1145/3528535.3565248'
chicago: 'Markov, Ilia, Hamidreza Ramezanikebrya, and Dan-Adrian Alistarh. “CGX:
Adaptive System Support for Communication-Efficient Deep Learning.” In Proceedings
of the 23rd ACM/IFIP International Middleware Conference, 241–54. Association
for Computing Machinery, 2022. https://doi.org/10.1145/3528535.3565248.'
ieee: 'I. Markov, H. Ramezanikebrya, and D.-A. Alistarh, “CGX: Adaptive system support
for communication-efficient deep learning,” in Proceedings of the 23rd ACM/IFIP
International Middleware Conference, Quebec, QC, Canada, 2022, pp. 241–254.'
ista: 'Markov I, Ramezanikebrya H, Alistarh D-A. 2022. CGX: Adaptive system support
for communication-efficient deep learning. Proceedings of the 23rd ACM/IFIP International
Middleware Conference. Middleware: International Middleware Conference, 241–254.'
mla: 'Markov, Ilia, et al. “CGX: Adaptive System Support for Communication-Efficient
Deep Learning.” Proceedings of the 23rd ACM/IFIP International Middleware Conference,
Association for Computing Machinery, 2022, pp. 241–54, doi:10.1145/3528535.3565248.'
short: I. Markov, H. Ramezanikebrya, D.-A. Alistarh, in:, Proceedings of the 23rd
ACM/IFIP International Middleware Conference, Association for Computing Machinery,
2022, pp. 241–254.
conference:
end_date: 2022-11-11
location: Quebec, QC, Canada
name: 'Middleware: International Middleware Conference'
start_date: 2022-11-07
corr_author: '1'
date_created: 2023-03-31T06:17:00Z
date_published: 2022-11-01T00:00:00Z
date_updated: 2026-04-07T13:00:54Z
day: '01'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1145/3528535.3565248
external_id:
arxiv:
- '2111.08617'
isi:
- '001061556200024'
file:
- access_level: open_access
checksum: 1a397746235f245da5468819247ff663
content_type: application/pdf
creator: dernst
date_created: 2023-04-03T06:17:58Z
date_updated: 2023-04-03T06:17:58Z
file_id: '12795'
file_name: 2022_ACMMiddleware_Markov.pdf
file_size: 1514169
relation: main_file
success: 1
file_date_updated: 2023-04-03T06:17:58Z
has_accepted_license: '1'
isi: 1
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
page: 241-254
publication: Proceedings of the 23rd ACM/IFIP International Middleware Conference
publication_identifier:
isbn:
- '9781450393409'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
record:
- id: '17490'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: 'CGX: Adaptive system support for communication-efficient deep learning'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2022'
...
---
_id: '13076'
abstract:
- lang: eng
text: "The source code for replicating experiments presented in the paper.\r\n\r\nThe
implementation of the designed priority schedulers can be found in Galois-2.2.1/include/Galois/WorkList/:\r\nStealingMultiQueue.h
is the StealingMultiQueue.\r\nMQOptimized/ contains MQ Optimized variants.\r\n\r\nWe
provide images that contain all the dependencies and datasets. Images can be pulled
from npostnikova/mq-based-schedulers repository, or downloaded from Zenodo. See
readme for more detail."
article_processing_charge: No
author:
- first_name: Anastasiia
full_name: Postnikova, Anastasiia
last_name: Postnikova
- first_name: Nikita
full_name: Koval, Nikita
id: 2F4DB10C-F248-11E8-B48F-1D18A9856A87
last_name: Koval
- first_name: Giorgi
full_name: Nadiradze, Giorgi
id: 3279A00C-F248-11E8-B48F-1D18A9856A87
last_name: Nadiradze
orcid: 0000-0001-5634-0731
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
citation:
ama: Postnikova A, Koval N, Nadiradze G, Alistarh D-A. Multi-queues can be state-of-the-art
priority schedulers. 2022. doi:10.5281/ZENODO.5733408
apa: Postnikova, A., Koval, N., Nadiradze, G., & Alistarh, D.-A. (2022). Multi-queues
can be state-of-the-art priority schedulers. Zenodo. https://doi.org/10.5281/ZENODO.5733408
chicago: Postnikova, Anastasiia, Nikita Koval, Giorgi Nadiradze, and Dan-Adrian
Alistarh. “Multi-Queues Can Be State-of-the-Art Priority Schedulers.” Zenodo,
2022. https://doi.org/10.5281/ZENODO.5733408.
ieee: A. Postnikova, N. Koval, G. Nadiradze, and D.-A. Alistarh, “Multi-queues can
be state-of-the-art priority schedulers.” Zenodo, 2022.
ista: Postnikova A, Koval N, Nadiradze G, Alistarh D-A. 2022. Multi-queues can be
state-of-the-art priority schedulers, Zenodo, 10.5281/ZENODO.5733408.
mla: Postnikova, Anastasiia, et al. Multi-Queues Can Be State-of-the-Art Priority
Schedulers. Zenodo, 2022, doi:10.5281/ZENODO.5733408.
short: A. Postnikova, N. Koval, G. Nadiradze, D.-A. Alistarh, (2022).
corr_author: '1'
date_created: 2023-05-23T17:05:40Z
date_published: 2022-01-03T00:00:00Z
date_updated: 2025-04-14T13:51:59Z
day: '03'
ddc:
- '510'
department:
- _id: DaAl
doi: 10.5281/ZENODO.5733408
main_file_link:
- open_access: '1'
url: https://doi.org/10.5281/zenodo.5813846
month: '01'
oa: 1
oa_version: Published Version
publisher: Zenodo
related_material:
link:
- relation: software
url: https://github.com/npostnikova/mq-based-schedulers/tree/v1.1
record:
- id: '11180'
relation: used_in_publication
status: public
status: public
title: Multi-queues can be state-of-the-art priority schedulers
type: research_data_reference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2022'
...
---
_id: '17059'
abstract:
- lang: eng
text: The recent focus on the efficiency of deep neural networks (DNNs) has led
to significant work on model compression approaches, of which weight pruning is
one of the most popular. At the same time, there is rapidly-growing computational
support for efficiently executing the unstructured-sparse models obtained via
pruning. Yet, most existing pruning methods minimize just the number of remaining
weights, i.e. the size of the model, rather than optimizing for inference time.
We address this gap by introducing SPDY, a new compression method which automatically
determines layer-wise sparsity targets achieving a desired inference speedup on
a given system, while minimizing accuracy loss. SPDY is the composition of two
new techniques. The first is an efficient and general dynamic programming algorithm
for solving constrained layer-wise compression problems, given a set of layer-wise
error scores. The second technique is a local search procedure for automatically
determining such scores in an accurate and robust manner. Experiments across popular
vision and language models show that SPDY guarantees speedups while recovering
higher accuracy relative to existing strategies, both for one-shot and gradual
pruning scenarios, and is compatible with most existing pruning approaches. We
also extend our approach to the recently-proposed task of pruning with very little
data, where we achieve the best known accuracy recovery when pruning to the GPU-supported
2:4 sparsity pattern.
acknowledgement: "We gratefully acknowledge funding from the European Research Council
(ERC) under the European Union’s Horizon 2020 programme (grant agreement No 805223
ScaleML),\r\nas well as computational support from AWS EC2. We thank Eldar Kurtic
for code and hyper-parameters for BERT pruning, and the Neural Magic Team, notably
Michael Goin and\r\nMark Kurtz, for support with their software."
alternative_title:
- PMLR
article_processing_charge: Yes
author:
- first_name: Elias
full_name: Frantar, Elias
id: 09a8f98d-ec99-11ea-ae11-c063a7b7fe5f
last_name: Frantar
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
citation:
ama: 'Frantar E, Alistarh D-A. SPDY: Accurate pruning with speedup guarantees. In:
39th International Conference on Machine Learning. Vol 162. ML Research
Press; 2022:6726-6743.'
apa: 'Frantar, E., & Alistarh, D.-A. (2022). SPDY: Accurate pruning with speedup
guarantees. In 39th International Conference on Machine Learning (Vol.
162, pp. 6726–6743). Baltimore, MD, United States: ML Research Press.'
chicago: 'Frantar, Elias, and Dan-Adrian Alistarh. “SPDY: Accurate Pruning with
Speedup Guarantees.” In 39th International Conference on Machine Learning,
162:6726–43. ML Research Press, 2022.'
ieee: 'E. Frantar and D.-A. Alistarh, “SPDY: Accurate pruning with speedup guarantees,”
in 39th International Conference on Machine Learning, Baltimore, MD, United
States, 2022, vol. 162, pp. 6726–6743.'
ista: 'Frantar E, Alistarh D-A. 2022. SPDY: Accurate pruning with speedup guarantees.
39th International Conference on Machine Learning. ICML: International Conference
on Machine Learning, PMLR, vol. 162, 6726–6743.'
mla: 'Frantar, Elias, and Dan-Adrian Alistarh. “SPDY: Accurate Pruning with Speedup
Guarantees.” 39th International Conference on Machine Learning, vol. 162,
ML Research Press, 2022, pp. 6726–43.'
short: E. Frantar, D.-A. Alistarh, in:, 39th International Conference on Machine
Learning, ML Research Press, 2022, pp. 6726–6743.
conference:
end_date: 2022-07-23
location: Baltimore, MD, United States
name: 'ICML: International Conference on Machine Learning'
start_date: 2022-07-17
corr_author: '1'
date_created: 2024-05-28T13:45:20Z
date_published: 2022-07-20T00:00:00Z
date_updated: 2025-04-14T07:49:14Z
day: '20'
ddc:
- '000'
department:
- _id: DaAl
ec_funded: 1
external_id:
isi:
- '000922378801029'
file:
- access_level: open_access
checksum: 5179a1e4dfc0fbfab6674907299e414a
content_type: application/pdf
creator: dernst
date_created: 2024-08-19T06:54:41Z
date_updated: 2024-08-19T06:54:41Z
file_id: '17440'
file_name: 2022_PMLR_Frantar.pdf
file_size: 615916
relation: main_file
success: 1
file_date_updated: 2024-08-19T06:54:41Z
has_accepted_license: '1'
intvolume: ' 162'
isi: 1
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 6726-6743
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
publication: 39th International Conference on Machine Learning
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'SPDY: Accurate pruning with speedup guarantees'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 162
year: '2022'
...
---
_id: '17088'
abstract:
- lang: eng
text: 'In this paper, we consider the problem of sparsifying BERT models, which
are a key building block for natural language processing, in order to reduce their
storage and computational cost. We introduce the Optimal BERT Surgeon (oBERT),
an efficient and accurate pruning method based on approximate second-order information,
which we show to yield state-of-the-art results in both stages of language tasks:
pre-training and fine-tuning. Specifically, oBERT extends existing work on second-order
pruning by allowing for pruning weight blocks, and is the first such method that
is applicable at BERT scale. Second, we investigate compounding compression approaches
to obtain highly compressed but accurate models for deployment on edge devices.
These models significantly push boundaries of the current state-of-the-art sparse
BERT models with respect to all metrics: model size, inference speed and task
accuracy. For example, relative to the dense BERT-base, we obtain 10x model size
compression with < 1% accuracy drop, 10x CPU-inference speedup with < 2% accuracy
drop, and 29x CPU-inference speedup with < 7.5% accuracy drop. Our code, fully
integrated with Transformers and SparseML, is available at https://github.com/neuralmagic/sparseml/tree/main/research/optimal_BERT_surgeon_oBERT.'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Eldar
full_name: Kurtic, Eldar
id: 47beb3a5-07b5-11eb-9b87-b108ec578218
last_name: Kurtic
- first_name: Daniel
full_name: Campos, Daniel
last_name: Campos
- first_name: Tuan
full_name: Nguyen, Tuan
last_name: Nguyen
- first_name: Elias
full_name: Frantar, Elias
id: 09a8f98d-ec99-11ea-ae11-c063a7b7fe5f
last_name: Frantar
- first_name: Mark
full_name: Kurtz, Mark
last_name: Kurtz
- first_name: Benjamin
full_name: Fineran, Benjamin
last_name: Fineran
- first_name: Michael
full_name: Goin, Michael
last_name: Goin
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
citation:
ama: 'Kurtic E, Campos D, Nguyen T, et al. The optimal BERT surgeon: Scalable and
accurate second-order pruning for large language models. In: Proceedings of
the 2022 Conference on Empirical Methods in Natural Language Processing. Association
for Computational Linguistics; 2022:4163-4181. doi:10.18653/v1/2022.emnlp-main.279'
apa: 'Kurtic, E., Campos, D., Nguyen, T., Frantar, E., Kurtz, M., Fineran, B., …
Alistarh, D.-A. (2022). The optimal BERT surgeon: Scalable and accurate second-order
pruning for large language models. In Proceedings of the 2022 Conference on
Empirical Methods in Natural Language Processing (pp. 4163–4181). Abu Dhabi,
United Arab Emirates: Association for Computational Linguistics. https://doi.org/10.18653/v1/2022.emnlp-main.279'
chicago: 'Kurtic, Eldar, Daniel Campos, Tuan Nguyen, Elias Frantar, Mark Kurtz,
Benjamin Fineran, Michael Goin, and Dan-Adrian Alistarh. “The Optimal BERT Surgeon:
Scalable and Accurate Second-Order Pruning for Large Language Models.” In Proceedings
of the 2022 Conference on Empirical Methods in Natural Language Processing,
4163–81. Association for Computational Linguistics, 2022. https://doi.org/10.18653/v1/2022.emnlp-main.279.'
ieee: 'E. Kurtic et al., “The optimal BERT surgeon: Scalable and accurate
second-order pruning for large language models,” in Proceedings of the 2022
Conference on Empirical Methods in Natural Language Processing, Abu Dhabi,
United Arab Emirates, 2022, pp. 4163–4181.'
ista: 'Kurtic E, Campos D, Nguyen T, Frantar E, Kurtz M, Fineran B, Goin M, Alistarh
D-A. 2022. The optimal BERT surgeon: Scalable and accurate second-order pruning
for large language models. Proceedings of the 2022 Conference on Empirical Methods
in Natural Language Processing. EMNLP: Conference on Empirical Methods in Natural
Language Processing, 4163–4181.'
mla: 'Kurtic, Eldar, et al. “The Optimal BERT Surgeon: Scalable and Accurate Second-Order
Pruning for Large Language Models.” Proceedings of the 2022 Conference on Empirical
Methods in Natural Language Processing, Association for Computational Linguistics,
2022, pp. 4163–81, doi:10.18653/v1/2022.emnlp-main.279.'
short: E. Kurtic, D. Campos, T. Nguyen, E. Frantar, M. Kurtz, B. Fineran, M. Goin,
D.-A. Alistarh, in:, Proceedings of the 2022 Conference on Empirical Methods in
Natural Language Processing, Association for Computational Linguistics, 2022,
pp. 4163–4181.
conference:
end_date: 2022-12-11
location: Abu Dhabi, United Arab Emirates
name: 'EMNLP: Conference on Empirical Methods in Natural Language Processing'
start_date: 2022-12-07
corr_author: '1'
date_created: 2024-05-29T06:40:55Z
date_published: 2022-12-01T00:00:00Z
date_updated: 2024-07-31T11:05:32Z
day: '01'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.18653/v1/2022.emnlp-main.279
external_id:
arxiv:
- '2203.07259'
file:
- access_level: open_access
checksum: c47b9edd8a9f743ac77a593de6d2e84a
content_type: application/pdf
creator: dernst
date_created: 2024-07-31T11:03:34Z
date_updated: 2024-07-31T11:03:34Z
file_id: '17354'
file_name: 2022_EMNLP_Kurtic.pdf
file_size: 522563
relation: main_file
success: 1
file_date_updated: 2024-07-31T11:03:34Z
has_accepted_license: '1'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: 4163-4181
publication: Proceedings of the 2022 Conference on Empirical Methods in Natural Language
Processing
publication_status: published
publisher: Association for Computational Linguistics
quality_controlled: '1'
related_material:
link:
- relation: software
url: https://github.com/neuralmagic/sparseml/tree/main/research/optimal_BERT_surgeon_oBERT
scopus_import: '1'
status: public
title: 'The optimal BERT surgeon: Scalable and accurate second-order pruning for large
language models'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2022'
...
---
_id: '8286'
abstract:
- lang: eng
text: "We consider the following dynamic load-balancing process: given an underlying
graph G with n nodes, in each step t≥ 0, one unit of load is created, and placed
at a randomly chosen graph node. In the same step, the chosen node picks a random
neighbor, and the two nodes balance their loads by averaging them. We are interested
in the expected gap between the minimum and maximum loads at nodes as the process
progresses, and its dependence on n and on the graph structure. Variants of the
above graphical balanced allocation process have been studied previously by Peres,
Talwar, and Wieder [Peres et al., 2015], and by Sauerwald and Sun [Sauerwald and
Sun, 2015]. These authors left as open the question of characterizing the gap
in the case of cycle graphs in the dynamic case, where weights are created during
the algorithm’s execution. For this case, the only known upper bound is of \U0001D4AA(n
log n), following from a majorization argument due to [Peres et al., 2015], which
analyzes a related graphical allocation process. In this paper, we provide an
upper bound of \U0001D4AA (√n log n) on the expected gap of the above process
for cycles of length n. We introduce a new potential analysis technique, which
enables us to bound the difference in load between k-hop neighbors on the cycle,
for any k ≤ n/2. We complement this with a \"gap covering\" argument, which bounds
the maximum value of the gap by bounding its value across all possible subsets
of a certain structure, and recursively bounding the gaps within each subset.
We provide analytical and experimental evidence that our upper bound on the gap
is tight up to a logarithmic factor. "
acknowledgement: The authors sincerely thank Thomas Sauerwald and George Giakkoupis
for insightful discussions, and Mohsen Ghaffari, Yuval Peres, and Udi Wieder for
feedback on earlier versions of this draft. We also thank the ICALP anonymous reviewers
for their very useful comments. Open access funding provided by Institute of Science
and Technology (IST Austria). Funding was provided by European Research Council
(Grant No. PR1042ERC01).
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
- first_name: Giorgi
full_name: Nadiradze, Giorgi
id: 3279A00C-F248-11E8-B48F-1D18A9856A87
last_name: Nadiradze
orcid: 0000-0001-5634-0731
- first_name: Amirmojtaba
full_name: Sabour, Amirmojtaba
id: bcc145fd-e77f-11ea-ae8b-80d661dbff67
last_name: Sabour
citation:
ama: Alistarh D-A, Nadiradze G, Sabour A. Dynamic averaging load balancing on cycles.
Algorithmica. 2022;84(4):1007-1029. doi:10.1007/s00453-021-00905-9
apa: 'Alistarh, D.-A., Nadiradze, G., & Sabour, A. (2022). Dynamic averaging
load balancing on cycles. Algorithmica. Virtual, Online; Germany: Springer
Nature. https://doi.org/10.1007/s00453-021-00905-9'
chicago: Alistarh, Dan-Adrian, Giorgi Nadiradze, and Amirmojtaba Sabour. “Dynamic
Averaging Load Balancing on Cycles.” Algorithmica. Springer Nature, 2022.
https://doi.org/10.1007/s00453-021-00905-9.
ieee: D.-A. Alistarh, G. Nadiradze, and A. Sabour, “Dynamic averaging load balancing
on cycles,” Algorithmica, vol. 84, no. 4. Springer Nature, pp. 1007–1029,
2022.
ista: Alistarh D-A, Nadiradze G, Sabour A. 2022. Dynamic averaging load balancing
on cycles. Algorithmica. 84(4), 1007–1029.
mla: Alistarh, Dan-Adrian, et al. “Dynamic Averaging Load Balancing on Cycles.”
Algorithmica, vol. 84, no. 4, Springer Nature, 2022, pp. 1007–29, doi:10.1007/s00453-021-00905-9.
short: D.-A. Alistarh, G. Nadiradze, A. Sabour, Algorithmica 84 (2022) 1007–1029.
conference:
end_date: 2020-07-11
location: Virtual, Online; Germany
name: 'ICALP: Automata, Languages and Programming'
start_date: 2020-07-08
date_created: 2020-08-24T06:24:04Z
date_published: 2022-04-01T00:00:00Z
date_updated: 2025-07-10T11:55:11Z
day: '01'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1007/s00453-021-00905-9
ec_funded: 1
external_id:
arxiv:
- '2003.09297'
isi:
- '000734004600001'
file:
- access_level: open_access
checksum: 21169b25b0c8e17b21e12af22bff9870
content_type: application/pdf
creator: cchlebak
date_created: 2021-12-27T10:36:40Z
date_updated: 2021-12-27T10:36:40Z
file_id: '10577'
file_name: 2021_Algorithmica_Alistarh.pdf
file_size: 525950
relation: main_file
success: 1
file_date_updated: 2021-12-27T10:36:40Z
has_accepted_license: '1'
intvolume: ' 84'
isi: 1
issue: '4'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
page: 1007-1029
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
name: IST Austria Open Access Fund
publication: Algorithmica
publication_identifier:
eissn:
- 1432-0541
issn:
- 0178-4617
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
link:
- relation: earlier_version
url: https://doi.org/10.4230/LIPIcs.ICALP.2020.7
record:
- id: '15077'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Dynamic averaging load balancing on cycles
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 84
year: '2022'
...
---
_id: '17087'
abstract:
- lang: eng
text: We consider the problem of model compression for deep neural networks (DNNs)
in the challenging one-shot/post-training setting, in which we are given an accurate
trained model, and must compress it without any retraining, based only on a small
amount of calibration input data. This problem has become popular in view of the
emerging software and hardware support for executing models compressed via pruning
and/or quantization with speedup, and well-performing solutions have been proposed
independently for both compression approaches.In this paper, we introduce a new
compression framework which covers both weight pruning and quantization in a unified
setting, is time- and space-efficient, and considerably improves upon the practical
performance of existing post-training methods. At the technical level, our approach
is based on an exact and efficient realization of the classical Optimal Brain
Surgeon (OBS) framework of [LeCun, Denker, and Solla, 1990] extended to also cover
weight quantization at the scale of modern DNNs. From the practical perspective,
our experimental results show that it can improve significantly upon the compression-accuracy
trade-offs of existing post-training methods, and that it can enable the accurate
compound application of both pruning and quantization in a post-training setting.
acknowledgement: 'We gratefully acknowledge funding from the European Research Council
(ERC) under the European Union’s Horizon 2020 programme (grant agreement No 805223
ScaleML), as well as computational support from AWS EC2. We thank Eldar Kurtic for
providing us BERT code and pretrained models, and the Neural Magic Team, notably
Michael Goin and Mark Kurtz, for support with their software. '
alternative_title:
- NeurIPS
article_processing_charge: No
arxiv: 1
author:
- first_name: Elias
full_name: Frantar, Elias
id: 09a8f98d-ec99-11ea-ae11-c063a7b7fe5f
last_name: Frantar
- first_name: Sidak Pal
full_name: Singh, Sidak Pal
id: DD138E24-D89D-11E9-9DC0-DEF6E5697425
last_name: Singh
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
citation:
ama: 'Frantar E, Singh SP, Alistarh D-A. Optimal brain compression: A framework
for accurate post-training quantization and pruning. In: 36th Conference on
Neural Information Processing Systems. Vol 35. ML Research Press; 2022.'
apa: 'Frantar, E., Singh, S. P., & Alistarh, D.-A. (2022). Optimal brain compression:
A framework for accurate post-training quantization and pruning. In 36th Conference
on Neural Information Processing Systems (Vol. 35). New Orleans, LA, United
States: ML Research Press.'
chicago: 'Frantar, Elias, Sidak Pal Singh, and Dan-Adrian Alistarh. “Optimal Brain
Compression: A Framework for Accurate Post-Training Quantization and Pruning.”
In 36th Conference on Neural Information Processing Systems, Vol. 35. ML
Research Press, 2022.'
ieee: 'E. Frantar, S. P. Singh, and D.-A. Alistarh, “Optimal brain compression:
A framework for accurate post-training quantization and pruning,” in 36th Conference
on Neural Information Processing Systems, New Orleans, LA, United States,
2022, vol. 35.'
ista: 'Frantar E, Singh SP, Alistarh D-A. 2022. Optimal brain compression: A framework
for accurate post-training quantization and pruning. 36th Conference on Neural
Information Processing Systems. NeurIPS: Neural Information Processing Systems,
NeurIPS, vol. 35.'
mla: 'Frantar, Elias, et al. “Optimal Brain Compression: A Framework for Accurate
Post-Training Quantization and Pruning.” 36th Conference on Neural Information
Processing Systems, vol. 35, ML Research Press, 2022.'
short: E. Frantar, S.P. Singh, D.-A. Alistarh, in:, 36th Conference on Neural Information
Processing Systems, ML Research Press, 2022.
conference:
end_date: 2022-12-09
location: New Orleans, LA, United States
name: 'NeurIPS: Neural Information Processing Systems'
start_date: 2022-11-28
corr_author: '1'
date_created: 2024-05-29T06:38:26Z
date_published: 2022-12-01T00:00:00Z
date_updated: 2026-07-29T13:48:39Z
day: '01'
ddc:
- '000'
department:
- _id: DaAl
ec_funded: 1
external_id:
arxiv:
- '2208.11580'
file:
- access_level: open_access
checksum: 38e7d75f578e8d2e207c81895e09f211
content_type: application/pdf
creator: dernst
date_created: 2024-08-05T09:25:39Z
date_updated: 2024-08-05T09:25:39Z
file_id: '17391'
file_name: 2022_NeurIPS_Frantar.pdf
file_size: 491843
relation: main_file
success: 1
file_date_updated: 2024-08-05T09:25:39Z
has_accepted_license: '1'
intvolume: ' 35'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Submitted Version
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
publication: 36th Conference on Neural Information Processing Systems
publication_identifier:
isbn:
- '9781713871088'
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
related_material:
record:
- id: '17485'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: 'Optimal brain compression: A framework for accurate post-training quantization
and pruning'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 35
year: '2022'
...
---
_id: '12299'
abstract:
- lang: eng
text: 'Transfer learning is a classic paradigm by which models pretrained on large
“upstream” datasets are adapted to yield good results on “downstream” specialized
datasets. Generally, more accurate models on the “upstream” dataset tend to provide
better transfer accuracy “downstream”. In this work, we perform an in-depth investigation
of this phenomenon in the context of convolutional neural networks (CNNs) trained
on the ImageNet dataset, which have been pruned-that is, compressed by sparsifiying
their connections. We consider transfer using unstructured pruned models obtained
by applying several state-of-the-art pruning methods, including magnitude-based,
second-order, regrowth, lottery-ticket, and regularization approaches, in the
context of twelve standard transfer tasks. In a nutshell, our study shows that
sparse models can match or even outperform the transfer performance of dense models,
even at high sparsities, and, while doing so, can lead to significant inference
and even training speedups. At the same time, we observe and analyze significant
differences in the behaviour of different pruning methods. The code is available
at: https://github.com/IST-DASLab/sparse-imagenet-transfer.'
acknowledgement: he authors would like to sincerely thank Christoph Lampert and Nir
Shavit for fruitful discussions during the development of this work, and Eldar Kurtic
for experimental support. EI was supported in part by the FWF DK VGSCO, grant agreement
number W1260-N35, while AP and DA acknowledge generous support by the ERC, via Starting
Grant 805223 ScaleML.
article_processing_charge: No
arxiv: 1
author:
- first_name: Eugenia B
full_name: Iofinova, Eugenia B
id: f9a17499-f6e0-11ea-865d-fdf9a3f77117
last_name: Iofinova
orcid: 0000-0002-7778-3221
- first_name: Elena-Alexandra
full_name: Peste, Elena-Alexandra
id: 32D78294-F248-11E8-B48F-1D18A9856A87
last_name: Peste
- first_name: Mark
full_name: Kurtz, Mark
last_name: Kurtz
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
citation:
ama: 'Iofinova EB, Krumes A, Kurtz M, Alistarh D-A. How well do sparse ImageNet
models transfer? In: 2022 IEEE/CVF Conference on Computer Vision and Pattern
Recognition. IEEE; 2022:12256-12266. doi:10.1109/cvpr52688.2022.01195'
apa: 'Iofinova, E. B., Krumes, A., Kurtz, M., & Alistarh, D.-A. (2022). How
well do sparse ImageNet models transfer? In 2022 IEEE/CVF Conference on Computer
Vision and Pattern Recognition (pp. 12256–12266). New Orleans, LA, United
States: IEEE. https://doi.org/10.1109/cvpr52688.2022.01195'
chicago: Iofinova, Eugenia B, Alexandra Krumes, Mark Kurtz, and Dan-Adrian Alistarh.
“How Well Do Sparse ImageNet Models Transfer?” In 2022 IEEE/CVF Conference
on Computer Vision and Pattern Recognition, 12256–66. IEEE, 2022. https://doi.org/10.1109/cvpr52688.2022.01195.
ieee: E. B. Iofinova, A. Krumes, M. Kurtz, and D.-A. Alistarh, “How well do sparse
ImageNet models transfer?,” in 2022 IEEE/CVF Conference on Computer Vision
and Pattern Recognition, New Orleans, LA, United States, 2022, pp. 12256–12266.
ista: 'Iofinova EB, Krumes A, Kurtz M, Alistarh D-A. 2022. How well do sparse ImageNet
models transfer? 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition.
CVPR: Computer Vision and Pattern Recognition, 12256–12266.'
mla: Iofinova, Eugenia B., et al. “How Well Do Sparse ImageNet Models Transfer?”
2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition, IEEE,
2022, pp. 12256–66, doi:10.1109/cvpr52688.2022.01195.
short: E.B. Iofinova, A. Krumes, M. Kurtz, D.-A. Alistarh, in:, 2022 IEEE/CVF Conference
on Computer Vision and Pattern Recognition, IEEE, 2022, pp. 12256–12266.
conference:
end_date: 2022-06-24
location: New Orleans, LA, United States
name: 'CVPR: Computer Vision and Pattern Recognition'
start_date: 2022-06-18
corr_author: '1'
date_created: 2023-01-16T10:06:00Z
date_published: 2022-09-27T00:00:00Z
date_updated: 2026-08-12T06:34:08Z
day: '27'
department:
- _id: DaAl
- _id: ChLa
doi: 10.1109/cvpr52688.2022.01195
ec_funded: 1
external_id:
arxiv:
- '2111.13445'
isi:
- '000870759105034'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2111.13445
month: '09'
oa: 1
oa_version: Preprint
page: 12256-12266
project:
- _id: 9B9290DE-BA93-11EA-9121-9846C619BF3A
grant_number: W1260-N35
name: Vienna Graduate School on Computational Optimization
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
publication: 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition
publication_identifier:
eissn:
- 2575-7075
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
record:
- id: '13074'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: How well do sparse ImageNet models transfer?
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2022'
...
---
_id: '11420'
abstract:
- lang: eng
text: 'Understanding the properties of neural networks trained via stochastic gradient
descent (SGD) is at the heart of the theory of deep learning. In this work, we
take a mean-field view, and consider a two-layer ReLU network trained via noisy-SGD
for a univariate regularized regression problem. Our main result is that SGD with
vanishingly small noise injected in the gradients is biased towards a simple solution:
at convergence, the ReLU network implements a piecewise linear map of the inputs,
and the number of “knot” points -- i.e., points where the tangent of the ReLU
network estimator changes -- between two consecutive training inputs is at most
three. In particular, as the number of neurons of the network grows, the SGD dynamics
is captured by the solution of a gradient flow and, at convergence, the distribution
of the weights approaches the unique minimizer of a related free energy, which
has a Gibbs form. Our key technical contribution consists in the analysis of the
estimator resulting from this minimizer: we show that its second derivative vanishes
everywhere, except at some specific locations which represent the “knot” points.
We also provide empirical evidence that knots at locations distinct from the data
points might occur, as predicted by our theory.'
acknowledgement: "We would like to thank Mert Pilanci for several exploratory discussions
in the early stage\r\nof the project, Jan Maas for clarifications about Jordan et
al. (1998), and Max Zimmer for\r\nsuggestive numerical experiments. A. Shevchenko
and M. Mondelli are partially supported\r\nby the 2019 Lopez-Loreta Prize. V. Kungurtsev
acknowledges support to the OP VVV\r\nproject CZ.02.1.01/0.0/0.0/16 019/0000765
Research Center for Informatics.\r\n"
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Aleksandr
full_name: Shevchenko, Aleksandr
id: F2B06EC2-C99E-11E9-89F0-752EE6697425
last_name: Shevchenko
- first_name: Vyacheslav
full_name: Kungurtsev, Vyacheslav
last_name: Kungurtsev
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
citation:
ama: Shevchenko A, Kungurtsev V, Mondelli M. Mean-field analysis of piecewise linear
solutions for wide ReLU networks. Journal of Machine Learning Research.
2022;23(130):1-55.
apa: Shevchenko, A., Kungurtsev, V., & Mondelli, M. (2022). Mean-field analysis
of piecewise linear solutions for wide ReLU networks. Journal of Machine Learning
Research. Journal of Machine Learning Research.
chicago: Shevchenko, Alexander, Vyacheslav Kungurtsev, and Marco Mondelli. “Mean-Field
Analysis of Piecewise Linear Solutions for Wide ReLU Networks.” Journal of
Machine Learning Research. Journal of Machine Learning Research, 2022.
ieee: A. Shevchenko, V. Kungurtsev, and M. Mondelli, “Mean-field analysis of piecewise
linear solutions for wide ReLU networks,” Journal of Machine Learning Research,
vol. 23, no. 130. Journal of Machine Learning Research, pp. 1–55, 2022.
ista: Shevchenko A, Kungurtsev V, Mondelli M. 2022. Mean-field analysis of piecewise
linear solutions for wide ReLU networks. Journal of Machine Learning Research.
23(130), 1–55.
mla: Shevchenko, Alexander, et al. “Mean-Field Analysis of Piecewise Linear Solutions
for Wide ReLU Networks.” Journal of Machine Learning Research, vol. 23,
no. 130, Journal of Machine Learning Research, 2022, pp. 1–55.
short: A. Shevchenko, V. Kungurtsev, M. Mondelli, Journal of Machine Learning Research
23 (2022) 1–55.
corr_author: '1'
date_created: 2022-05-29T22:01:54Z
date_published: 2022-04-01T00:00:00Z
date_updated: 2026-09-04T22:30:18Z
day: '01'
ddc:
- '000'
department:
- _id: MaMo
- _id: DaAl
external_id:
arxiv:
- '2111.02278'
file:
- access_level: open_access
checksum: d4ff5d1affb34848b5c5e4002483fc62
content_type: application/pdf
creator: cchlebak
date_created: 2022-05-30T08:22:55Z
date_updated: 2022-05-30T08:22:55Z
file_id: '11422'
file_name: 21-1365.pdf
file_size: 1521701
relation: main_file
success: 1
file_date_updated: 2022-05-30T08:22:55Z
has_accepted_license: '1'
intvolume: ' 23'
issue: '130'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
page: 1-55
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: Journal of Machine Learning Research
publication_identifier:
eissn:
- 1533-7928
issn:
- 1532-4435
publication_status: published
publisher: Journal of Machine Learning Research
quality_controlled: '1'
related_material:
link:
- relation: other
url: https://www.jmlr.org/papers/v23/21-1365.html
record:
- id: '17465'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Mean-field analysis of piecewise linear solutions for wide ReLU networks
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 23
year: '2022'
...
---
_id: '10853'
abstract:
- lang: eng
text: Dynamic Connectivity is a fundamental algorithmic graph problem, motivated
by a wide range of applications to social and communication networks and used
as a building block in various other algorithms, such as the bi-connectivity and
the dynamic minimal spanning tree problems. In brief, we wish to maintain the
connected components of the graph under dynamic edge insertions and deletions.
In the sequential case, the problem has been well-studied from both theoretical
and practical perspectives. However, much less is known about efficient concurrent
solutions to this problem. This is the gap we address in this paper. We start
from one of the classic data structures used to solve this problem, the Euler
Tour Tree. Our first contribution is a non-blocking single-writer implementation
of it. We leverage this data structure to obtain the first truly concurrent generalization
of dynamic connectivity, which preserves the time complexity of its sequential
counterpart, but is also scalable in practice. To achieve this, we rely on three
main techniques. The first is to ensure that connectivity queries, which usually
dominate real-world workloads, are non-blocking. The second non-trivial technique
expands the above idea by making all queries that do not change the connectivity
structure non-blocking. The third ingredient is applying fine-grained locking
for updating the connected components, which allows operations on disjoint components
to occur in parallel. We evaluate the resulting algorithm on various workloads,
executing on both real and synthetic graphs. The results show the efficiency of
each of the proposed optimizations; the most efficient variant improves the performance
of a coarse-grained based implementation on realistic scenarios up to 6x on average
and up to 30x when connectivity queries dominate.
article_processing_charge: No
arxiv: 1
author:
- first_name: Alexander
full_name: Fedorov, Alexander
last_name: Fedorov
- first_name: Nikita
full_name: Koval, Nikita
last_name: Koval
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
citation:
ama: 'Fedorov A, Koval N, Alistarh D-A. A scalable concurrent algorithm for dynamic
connectivity. In: Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms
and Architectures. Association for Computing Machinery; 2021:208-220. doi:10.1145/3409964.3461810'
apa: 'Fedorov, A., Koval, N., & Alistarh, D.-A. (2021). A scalable concurrent
algorithm for dynamic connectivity. In Proceedings of the 33rd ACM Symposium
on Parallelism in Algorithms and Architectures (pp. 208–220). Virtual, Online:
Association for Computing Machinery. https://doi.org/10.1145/3409964.3461810'
chicago: Fedorov, Alexander, Nikita Koval, and Dan-Adrian Alistarh. “A Scalable
Concurrent Algorithm for Dynamic Connectivity.” In Proceedings of the 33rd
ACM Symposium on Parallelism in Algorithms and Architectures, 208–20. Association
for Computing Machinery, 2021. https://doi.org/10.1145/3409964.3461810.
ieee: A. Fedorov, N. Koval, and D.-A. Alistarh, “A scalable concurrent algorithm
for dynamic connectivity,” in Proceedings of the 33rd ACM Symposium on Parallelism
in Algorithms and Architectures, Virtual, Online, 2021, pp. 208–220.
ista: 'Fedorov A, Koval N, Alistarh D-A. 2021. A scalable concurrent algorithm for
dynamic connectivity. Proceedings of the 33rd ACM Symposium on Parallelism in
Algorithms and Architectures. SPAA: Symposium on Parallelism in Algorithms and
Architectures, 208–220.'
mla: Fedorov, Alexander, et al. “A Scalable Concurrent Algorithm for Dynamic Connectivity.”
Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures,
Association for Computing Machinery, 2021, pp. 208–20, doi:10.1145/3409964.3461810.
short: A. Fedorov, N. Koval, D.-A. Alistarh, in:, Proceedings of the 33rd ACM Symposium
on Parallelism in Algorithms and Architectures, Association for Computing Machinery,
2021, pp. 208–220.
conference:
end_date: 2021-07-08
location: Virtual, Online
name: 'SPAA: Symposium on Parallelism in Algorithms and Architectures'
start_date: 2021-07-06
date_created: 2022-03-18T08:21:47Z
date_published: 2021-07-01T00:00:00Z
date_updated: 2022-03-18T08:45:46Z
day: '01'
department:
- _id: DaAl
doi: 10.1145/3409964.3461810
external_id:
arxiv:
- '2105.08098'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2105.08098
month: '07'
oa: 1
oa_version: Preprint
page: 208-220
publication: Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and
Architectures
publication_identifier:
isbn:
- '9781450380706'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: A scalable concurrent algorithm for dynamic connectivity
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...
---
_id: '10854'
abstract:
- lang: eng
text: "Consider a distributed task where the communication network is fixed but
the local inputs given to the nodes of the distributed system may change over
time. In this work, we explore the following question: if some of the local inputs
change, can an existing solution be updated efficiently, in a dynamic and distributed
manner?\r\nTo address this question, we define the batch dynamic CONGEST model
in which we are given a bandwidth-limited communication network and a dynamic
edge labelling defines the problem input. The task is to maintain a solution to
a graph problem on the labelled graph under batch changes. We investigate, when
a batch of alpha edge label changes arrive, - how much time as a function of alpha
we need to update an existing solution, and - how much information the nodes have
to keep in local memory between batches in order to update the solution quickly.\r\nOur
work lays the foundations for the theory of input-dynamic distributed network
algorithms. We give a general picture of the complexity landscape in this model,
design both universal algorithms and algorithms for concrete problems, and present
a general framework for lower bounds. The diverse time complexity of our model
spans from constant time, through time polynomial in alpha, and to alpha time,
which we show to be enough for any task."
acknowledgement: We thank Jukka Suomela for discussions. We also thank our shepherd
Mohammad Hajiesmaili and the reviewers for their time and suggestions on how to
improve the paper. This project has received funding from the European Research
Council (ERC) under the European Union’s Horizon 2020 research and innovation programme
(grant agreement No 805223 ScaleML), from the European Union’s Horizon 2020 research
and innovation programme under the Marie Skłodowska–Curie grant agreement No. 840605,
from the Vienna Science and Technology Fund (WWTF) project WHATIF, ICT19-045, 2020-2024,
and from the Austrian Science Fund (FWF) and netIDEE SCIENCE project P 33775-N.
article_processing_charge: No
arxiv: 1
author:
- first_name: Klaus-Tycho
full_name: Foerster, Klaus-Tycho
last_name: Foerster
- first_name: Janne
full_name: Korhonen, Janne
id: C5402D42-15BC-11E9-A202-CA2BE6697425
last_name: Korhonen
- first_name: Ami
full_name: Paz, Ami
last_name: Paz
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
citation:
ama: 'Foerster K-T, Korhonen J, Paz A, Rybicki J, Schmid S. Input-dynamic distributed
algorithms for communication networks. In: Abstract Proceedings of the 2021
ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer
Systems. Association for Computing Machinery; 2021:71-72. doi:10.1145/3410220.3453923'
apa: 'Foerster, K.-T., Korhonen, J., Paz, A., Rybicki, J., & Schmid, S. (2021).
Input-dynamic distributed algorithms for communication networks. In Abstract
Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement
and Modeling of Computer Systems (pp. 71–72). Virtual, Online: Association
for Computing Machinery. https://doi.org/10.1145/3410220.3453923'
chicago: Foerster, Klaus-Tycho, Janne Korhonen, Ami Paz, Joel Rybicki, and Stefan
Schmid. “Input-Dynamic Distributed Algorithms for Communication Networks.” In
Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference
on Measurement and Modeling of Computer Systems, 71–72. Association for Computing
Machinery, 2021. https://doi.org/10.1145/3410220.3453923.
ieee: K.-T. Foerster, J. Korhonen, A. Paz, J. Rybicki, and S. Schmid, “Input-dynamic
distributed algorithms for communication networks,” in Abstract Proceedings
of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling
of Computer Systems, Virtual, Online, 2021, pp. 71–72.
ista: 'Foerster K-T, Korhonen J, Paz A, Rybicki J, Schmid S. 2021. Input-dynamic
distributed algorithms for communication networks. Abstract Proceedings of the
2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of
Computer Systems. SIGMETRICS: International Conference on Measurement and Modeling
of Computer Systems, 71–72.'
mla: Foerster, Klaus-Tycho, et al. “Input-Dynamic Distributed Algorithms for Communication
Networks.” Abstract Proceedings of the 2021 ACM SIGMETRICS / International
Conference on Measurement and Modeling of Computer Systems, Association for
Computing Machinery, 2021, pp. 71–72, doi:10.1145/3410220.3453923.
short: K.-T. Foerster, J. Korhonen, A. Paz, J. Rybicki, S. Schmid, in:, Abstract
Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement
and Modeling of Computer Systems, Association for Computing Machinery, 2021, pp.
71–72.
conference:
end_date: 2021-06-18
location: Virtual, Online
name: 'SIGMETRICS: International Conference on Measurement and Modeling of Computer
Systems'
start_date: 2021-06-14
date_created: 2022-03-18T08:48:41Z
date_published: 2021-05-01T00:00:00Z
date_updated: 2025-04-14T13:52:09Z
day: '01'
department:
- _id: DaAl
doi: 10.1145/3410220.3453923
ec_funded: 1
external_id:
arxiv:
- '2005.07637'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2005.07637
month: '05'
oa: 1
oa_version: Preprint
page: 71-72
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
- _id: 26A5D39A-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '840605'
name: Coordination in constrained and natural distributed systems
publication: Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference
on Measurement and Modeling of Computer Systems
publication_identifier:
isbn:
- '9781450380720'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
record:
- id: '10855'
relation: extended_version
status: public
scopus_import: '1'
status: public
title: Input-dynamic distributed algorithms for communication networks
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...