---
_id: '17469'
abstract:
- lang: eng
text: 'Autoencoders are a prominent model in many empirical branches of machine
learning and lossy data compression. However, basic theoretical questions remain
unanswered even in a shallow two-layer setting. In particular, to what degree
does a shallow autoencoder capture the structure of the underlying data distribution?
For the prototypical case of the 1-bit compression of sparse Gaussian data, we
prove that gradient descent converges to a solution that completely disregards
the sparse structure of the input. Namely, the performance of the algorithm is
the same as if it was compressing a Gaussian source - with no sparsity. For general
data distributions, we give evidence of a phase transition phenomenon in the shape
of the gradient descent minimizer, as a function of the data sparsity: below the
critical sparsity level, the minimizer is a rotation taken uniformly at random
(just like in the compression of non-sparse data); above the critical sparsity,
the minimizer is the identity (up to a permutation). Finally, by exploiting a
connection with approximate message passing algorithms, we show how to improve
upon Gaussian performance for the compression of sparse data: adding a denoising
function to a shallow architecture already reduces the loss provably, and a suitable
multi-layer decoder leads to a further improvement. We validate our findings on
image datasets, such as CIFAR-10 and MNIST.'
acknowledgement: "Kevin Kogler, Alexander Shevchenko and Marco Mondelli are supported
by the 2019 Lopez-Loreta Prize. Hamed\r\nHassani acknowledges the support by the
NSF CIF award (1910056) and the NSF Institute for CORE Emerging Methods in Data
Science (EnCORE)."
alternative_title:
- PMLR
article_processing_charge: No
arxiv: 1
author:
- first_name: Kevin
full_name: Kögler, Kevin
id: 94ec913c-dc85-11ea-9058-e5051ab2428b
last_name: Kögler
- first_name: Aleksandr
full_name: Shevchenko, Aleksandr
id: F2B06EC2-C99E-11E9-89F0-752EE6697425
last_name: Shevchenko
- 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: 'Kögler K, Shevchenko A, Hassani H, Mondelli M. Compression of structured data
with autoencoders: Provable benefit of nonlinearities and depth. In: Proceedings
of the 41st International Conference on Machine Learning. Vol 235. ML Research
Press; 2024:24964-25015.'
apa: 'Kögler, K., Shevchenko, A., Hassani, H., & Mondelli, M. (2024). Compression
of structured data with autoencoders: Provable benefit of nonlinearities and depth.
In Proceedings of the 41st International Conference on Machine Learning
(Vol. 235, pp. 24964–25015). Vienna, Austria: ML Research Press.'
chicago: 'Kögler, Kevin, Alexander Shevchenko, Hamed Hassani, and Marco Mondelli.
“Compression of Structured Data with Autoencoders: Provable Benefit of Nonlinearities
and Depth.” In Proceedings of the 41st International Conference on Machine
Learning, 235:24964–15. ML Research Press, 2024.'
ieee: 'K. Kögler, A. Shevchenko, H. Hassani, and M. Mondelli, “Compression of structured
data with autoencoders: Provable benefit of nonlinearities and depth,” in Proceedings
of the 41st International Conference on Machine Learning, Vienna, Austria,
2024, vol. 235, pp. 24964–25015.'
ista: 'Kögler K, Shevchenko A, Hassani H, Mondelli M. 2024. Compression of structured
data with autoencoders: Provable benefit of nonlinearities and depth. Proceedings
of the 41st International Conference on Machine Learning. ICML: International
Conference on Machine Learning, PMLR, vol. 235, 24964–25015.'
mla: 'Kögler, Kevin, et al. “Compression of Structured Data with Autoencoders: Provable
Benefit of Nonlinearities and Depth.” Proceedings of the 41st International
Conference on Machine Learning, vol. 235, ML Research Press, 2024, pp. 24964–5015.'
short: K. Kögler, A. Shevchenko, H. Hassani, M. Mondelli, in:, Proceedings of the
41st International Conference on Machine Learning, ML Research Press, 2024, pp.
24964–25015.
conference:
end_date: 2024-07-27
location: Vienna, Austria
name: 'ICML: International Conference on Machine Learning'
start_date: 2024-07-21
corr_author: '1'
date_created: 2024-08-29T11:47:57Z
date_published: 2024-07-01T00:00:00Z
date_updated: 2026-05-30T22:30:05Z
day: '01'
department:
- _id: DaAl
- _id: MaMo
external_id:
arxiv:
- '2402.05013'
intvolume: ' 235'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://proceedings.mlr.press/v235/kogler24a.html
month: '07'
oa: 1
oa_version: Published Version
page: 24964-25015
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: Proceedings of the 41st International Conference on Machine Learning
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: 'Compression of structured data with autoencoders: Provable benefit of nonlinearities
and depth'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 235
year: '2024'
...
---
_id: '14260'
abstract:
- lang: eng
text: "This paper presents Lincheck, a new practical and user-friendly framework
for testing concurrent algorithms on the Java Virtual Machine (JVM). Lincheck
provides a simple and declarative way to write concurrent tests: instead of describing
how to perform the test, users specify what to test by declaring all the operations
to examine; the framework automatically handles the rest. As a result, tests written
with Lincheck are concise and easy to understand. The framework automatically
generates a set of concurrent scenarios, examines them using stress-testing or
bounded model checking, and verifies that the results of each invocation are correct.
Notably, if an error is detected via model checking, Lincheck provides an easy-to-follow
trace to reproduce it, significantly simplifying the bug investigation.\r\n\r\nTo
the best of our knowledge, Lincheck is the first production-ready tool on the
JVM that offers such a simple way of writing concurrent tests, without requiring
special skills or expertise. We successfully integrated Lincheck in the development
process of several large projects, such as Kotlin Coroutines, and identified new
bugs in popular concurrency libraries, such as a race in Java’s standard ConcurrentLinkedDeque
and a liveliness bug in Java’s AbstractQueuedSynchronizer framework, which is
used in most of the synchronization primitives. We believe that Lincheck can significantly
improve the quality and productivity of concurrent algorithms research and development
and become the state-of-the-art tool for checking their correctness."
alternative_title:
- LNCS
article_processing_charge: Yes (in subscription journal)
author:
- first_name: Nikita
full_name: Koval, Nikita
id: 2F4DB10C-F248-11E8-B48F-1D18A9856A87
last_name: Koval
- first_name: Alexander
full_name: Fedorov, Alexander
id: 2e711909-896a-11ed-bdf8-eb0f5a2984c6
last_name: Fedorov
- first_name: Maria
full_name: Sokolova, Maria
last_name: Sokolova
- first_name: Dmitry
full_name: Tsitelov, Dmitry
last_name: Tsitelov
- 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: 'Koval N, Fedorov A, Sokolova M, Tsitelov D, Alistarh D-A. Lincheck: A practical
framework for testing concurrent data structures on JVM. In: 35th International
Conference on Computer Aided Verification . Vol 13964. Springer Nature; 2023:156-169.
doi:10.1007/978-3-031-37706-8_8'
apa: 'Koval, N., Fedorov, A., Sokolova, M., Tsitelov, D., & Alistarh, D.-A.
(2023). Lincheck: A practical framework for testing concurrent data structures
on JVM. In 35th International Conference on Computer Aided Verification
(Vol. 13964, pp. 156–169). Paris, France: Springer Nature. https://doi.org/10.1007/978-3-031-37706-8_8'
chicago: 'Koval, Nikita, Alexander Fedorov, Maria Sokolova, Dmitry Tsitelov, and
Dan-Adrian Alistarh. “Lincheck: A Practical Framework for Testing Concurrent Data
Structures on JVM.” In 35th International Conference on Computer Aided Verification
, 13964:156–69. Springer Nature, 2023. https://doi.org/10.1007/978-3-031-37706-8_8.'
ieee: 'N. Koval, A. Fedorov, M. Sokolova, D. Tsitelov, and D.-A. Alistarh, “Lincheck:
A practical framework for testing concurrent data structures on JVM,” in 35th
International Conference on Computer Aided Verification , Paris, France, 2023,
vol. 13964, pp. 156–169.'
ista: 'Koval N, Fedorov A, Sokolova M, Tsitelov D, Alistarh D-A. 2023. Lincheck:
A practical framework for testing concurrent data structures on JVM. 35th International
Conference on Computer Aided Verification . CAV: Computer Aided Verification,
LNCS, vol. 13964, 156–169.'
mla: 'Koval, Nikita, et al. “Lincheck: A Practical Framework for Testing Concurrent
Data Structures on JVM.” 35th International Conference on Computer Aided Verification
, vol. 13964, Springer Nature, 2023, pp. 156–69, doi:10.1007/978-3-031-37706-8_8.'
short: N. Koval, A. Fedorov, M. Sokolova, D. Tsitelov, D.-A. Alistarh, in:, 35th
International Conference on Computer Aided Verification , Springer Nature, 2023,
pp. 156–169.
conference:
end_date: 2023-07-22
location: Paris, France
name: 'CAV: Computer Aided Verification'
start_date: 2023-07-17
date_created: 2023-09-03T22:01:16Z
date_published: 2023-07-17T00:00:00Z
date_updated: 2025-09-09T12:51:52Z
day: '17'
ddc:
- '000'
department:
- _id: DaAl
- _id: GradSch
doi: 10.1007/978-3-031-37706-8_8
external_id:
isi:
- '001310786500008'
file:
- access_level: open_access
checksum: c346016393123a0a2338ad4d976f61bc
content_type: application/pdf
creator: dernst
date_created: 2023-09-06T08:16:25Z
date_updated: 2023-09-06T08:16:25Z
file_id: '14275'
file_name: 2023_LNCS_Koval.pdf
file_size: 421408
relation: main_file
success: 1
file_date_updated: 2023-09-06T08:16:25Z
has_accepted_license: '1'
intvolume: ' 13964'
isi: 1
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '07'
oa: 1
oa_version: Published Version
page: 156-169
publication: '35th International Conference on Computer Aided Verification '
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031377051'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '14995'
relation: research_data
status: public
scopus_import: '1'
status: public
title: 'Lincheck: A practical framework for testing concurrent data structures on JVM'
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
volume: 13964
year: '2023'
...
---
_id: '14364'
abstract:
- lang: eng
text: We introduce extension-based proofs, a class of impossibility proofs that
includes valency arguments. They are modelled as an interaction between a prover
and a protocol. Using proofs based on combinatorial topology, it has been shown
that it is impossible to deterministically solve -set agreement among processes
or approximate agreement on a cycle of length 4 among processes in a wait-free
manner in asynchronous models where processes communicate using objects that can
be constructed from shared registers. However, it was unknown whether proofs based
on simpler techniques were possible. We show that these impossibility results
cannot be obtained by extension-based proofs in the iterated snapshot model and,
hence, extension-based proofs are limited in power.
acknowledgement: "We would like to thank Valerie King, Toniann Pitassi, and Michael
Saks for helpful discussions and Shi Hao Liu for his useful feedback.\r\nThis research
was supported by the Natural Science and Engineering Research Council of Canada
under grants RGPIN-2015-05080 and RGPIN-2020-04178, a postgraduate scholarship,
and a postdoctoral fellowship; a University of Toronto postdoctoral fellowship;
the National Science Foundation under grants CCF-1217921, CCF-1301926, CCF-1637385,
CCF-1650596, and IIS-1447786; the U.S. Department of Energy under grant ER26116/DE-SC0008923;
the European Research Council (ERC) under the European Union’s Horizon 2020 research
and innovation programme grant agreement 805223 ScaleML; and the Oracle and Intel
corporations. Some of the work on this paper was done while Faith Ellen was visiting
IST Austria."
article_processing_charge: No
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: James
full_name: Aspnes, James
last_name: Aspnes
- first_name: Faith
full_name: Ellen, Faith
last_name: Ellen
- first_name: Rati
full_name: Gelashvili, Rati
last_name: Gelashvili
- first_name: Leqi
full_name: Zhu, Leqi
id: a2117c59-cee4-11ed-b9d0-874ecf0f8ac5
last_name: Zhu
citation:
ama: Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. Why extension-based proofs
fail. SIAM Journal on Computing. 2023;52(4):913-944. doi:10.1137/20M1375851
apa: Alistarh, D.-A., Aspnes, J., Ellen, F., Gelashvili, R., & Zhu, L. (2023).
Why extension-based proofs fail. SIAM Journal on Computing. Society for
Industrial and Applied Mathematics. https://doi.org/10.1137/20M1375851
chicago: Alistarh, Dan-Adrian, James Aspnes, Faith Ellen, Rati Gelashvili, and Leqi
Zhu. “Why Extension-Based Proofs Fail.” SIAM Journal on Computing. Society
for Industrial and Applied Mathematics, 2023. https://doi.org/10.1137/20M1375851.
ieee: D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, and L. Zhu, “Why extension-based
proofs fail,” SIAM Journal on Computing, vol. 52, no. 4. Society for Industrial
and Applied Mathematics, pp. 913–944, 2023.
ista: Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. 2023. Why extension-based
proofs fail. SIAM Journal on Computing. 52(4), 913–944.
mla: Alistarh, Dan-Adrian, et al. “Why Extension-Based Proofs Fail.” SIAM Journal
on Computing, vol. 52, no. 4, Society for Industrial and Applied Mathematics,
2023, pp. 913–44, doi:10.1137/20M1375851.
short: D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, L. Zhu, SIAM Journal
on Computing 52 (2023) 913–944.
date_created: 2023-09-24T22:01:11Z
date_published: 2023-07-25T00:00:00Z
date_updated: 2025-05-14T11:26:06Z
day: '25'
department:
- _id: DaAl
doi: 10.1137/20M1375851
ec_funded: 1
external_id:
arxiv:
- '1811.01421'
isi:
- '001082972300004'
intvolume: ' 52'
isi: 1
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1811.01421
month: '07'
oa: 1
oa_version: Preprint
page: 913-944
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
publication: SIAM Journal on Computing
publication_identifier:
eissn:
- 1095-7111
issn:
- 0097-5397
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
related_material:
record:
- id: '6676'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Why extension-based proofs fail
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 52
year: '2023'
...
---
_id: '14460'
abstract:
- lang: eng
text: We provide an efficient implementation of the backpropagation algorithm, specialized
to the case where the weights of the neural network being trained are sparse.
Our algorithm is general, as it applies to arbitrary (unstructured) sparsity and
common layer types (e.g., convolutional or linear). We provide a fast vectorized
implementation on commodity CPUs, and show that it can yield speedups in end-to-end
runtime experiments, both in transfer learning using already-sparsified networks,
and in training sparse networks from scratch. Thus, our results provide the first
support for sparse training on commodity hardware.
acknowledgement: 'We would like to thank Elias Frantar for his valuable assistance
and support at the outset of this project, and the anonymous ICML and SNN reviewers
for very constructive feedback. EI was supported in part by the FWF DK VGSCO, grant
agreement number W1260-N35. DA acknowledges generous ERC support, via Starting Grant
805223 ScaleML. '
alternative_title:
- PMLR
article_processing_charge: No
arxiv: 1
author:
- first_name: Mahdi
full_name: Nikdan, Mahdi
id: 66374281-f394-11eb-9cf6-869147deecc0
last_name: Nikdan
- first_name: Tommaso
full_name: Pegolotti, Tommaso
last_name: Pegolotti
- 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: Eldar
full_name: Kurtic, Eldar
id: 47beb3a5-07b5-11eb-9b87-b108ec578218
last_name: Kurtic
- 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: 'Nikdan M, Pegolotti T, Iofinova EB, Kurtic E, Alistarh D-A. SparseProp: Efficient
sparse backpropagation for faster training of neural networks at the edge. In:
Proceedings of the 40th International Conference on Machine Learning. Vol
202. ML Research Press; 2023:26215-26227.'
apa: 'Nikdan, M., Pegolotti, T., Iofinova, E. B., Kurtic, E., & Alistarh, D.-A.
(2023). SparseProp: Efficient sparse backpropagation for faster training of neural
networks at the edge. In Proceedings of the 40th International Conference on
Machine Learning (Vol. 202, pp. 26215–26227). Honolulu, Hawaii, HI, United
States: ML Research Press.'
chicago: 'Nikdan, Mahdi, Tommaso Pegolotti, Eugenia B Iofinova, Eldar Kurtic, and
Dan-Adrian Alistarh. “SparseProp: Efficient Sparse Backpropagation for Faster
Training of Neural Networks at the Edge.” In Proceedings of the 40th International
Conference on Machine Learning, 202:26215–27. ML Research Press, 2023.'
ieee: 'M. Nikdan, T. Pegolotti, E. B. Iofinova, E. Kurtic, and D.-A. Alistarh, “SparseProp:
Efficient sparse backpropagation for faster training of neural networks at the
edge,” in Proceedings of the 40th International Conference on Machine Learning,
Honolulu, Hawaii, HI, United States, 2023, vol. 202, pp. 26215–26227.'
ista: 'Nikdan M, Pegolotti T, Iofinova EB, Kurtic E, Alistarh D-A. 2023. SparseProp:
Efficient sparse backpropagation for faster training of neural networks at the
edge. Proceedings of the 40th International Conference on Machine Learning. ICML:
International Conference on Machine Learning, PMLR, vol. 202, 26215–26227.'
mla: 'Nikdan, Mahdi, et al. “SparseProp: Efficient Sparse Backpropagation for Faster
Training of Neural Networks at the Edge.” Proceedings of the 40th International
Conference on Machine Learning, vol. 202, ML Research Press, 2023, pp. 26215–27.'
short: M. Nikdan, T. Pegolotti, E.B. Iofinova, E. Kurtic, D.-A. Alistarh, in:, Proceedings
of the 40th International Conference on Machine Learning, ML Research Press, 2023,
pp. 26215–26227.
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: 2025-04-14T07:49:12Z
day: '30'
department:
- _id: DaAl
ec_funded: 1
external_id:
arxiv:
- '2302.04852'
intvolume: ' 202'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2302.04852
month: '07'
oa: 1
oa_version: Preprint
page: 26215-26227
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'
scopus_import: '1'
status: public
title: 'SparseProp: Efficient sparse backpropagation for faster training of neural
networks at the edge'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 202
year: '2023'
...
---
_id: '12330'
abstract:
- lang: eng
text: 'The design and implementation of efficient concurrent data structures has
seen significant attention. However, most of this work has focused on concurrent
data structures providing good worst-case guarantees, although, in real workloads,
objects are often accessed at different rates. Efficient distribution-adaptive
data structures, such as splay-trees, are known in the sequential case; however,
they often are hard to translate efficiently to the concurrent case. We investigate
distribution-adaptive concurrent data structures, and propose a new design called
the splay-list. At a high level, the splay-list is similar to a standard skip-list,
with the key distinction that the height of each element adapts dynamically to
its access rate: popular elements “move up,” whereas rarely-accessed elements
decrease in height. We show that the splay-list provides order-optimal amortized
complexity bounds for a subset of operations, while being amenable to efficient
concurrent implementation. Experiments show that the splay-list can leverage distribution-adaptivity
for performance, and can outperform the only previously-known distribution-adaptive
concurrent design in certain workloads.'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Vitalii
full_name: Aksenov, Vitalii
id: 2980135A-F248-11E8-B48F-1D18A9856A87
last_name: Aksenov
- 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: Alexandra
full_name: Drozdova, Alexandra
last_name: Drozdova
- first_name: Amirkeivan
full_name: Mohtashami, Amirkeivan
last_name: Mohtashami
citation:
ama: 'Aksenov V, Alistarh D-A, Drozdova A, Mohtashami A. The splay-list: A distribution-adaptive
concurrent skip-list. Distributed Computing. 2023;36:395-418. doi:10.1007/s00446-022-00441-x'
apa: 'Aksenov, V., Alistarh, D.-A., Drozdova, A., & Mohtashami, A. (2023). The
splay-list: A distribution-adaptive concurrent skip-list. Distributed Computing.
Springer Nature. https://doi.org/10.1007/s00446-022-00441-x'
chicago: 'Aksenov, Vitalii, Dan-Adrian Alistarh, Alexandra Drozdova, and Amirkeivan
Mohtashami. “The Splay-List: A Distribution-Adaptive Concurrent Skip-List.” Distributed
Computing. Springer Nature, 2023. https://doi.org/10.1007/s00446-022-00441-x.'
ieee: 'V. Aksenov, D.-A. Alistarh, A. Drozdova, and A. Mohtashami, “The splay-list:
A distribution-adaptive concurrent skip-list,” Distributed Computing, vol.
36. Springer Nature, pp. 395–418, 2023.'
ista: 'Aksenov V, Alistarh D-A, Drozdova A, Mohtashami A. 2023. The splay-list:
A distribution-adaptive concurrent skip-list. Distributed Computing. 36, 395–418.'
mla: 'Aksenov, Vitalii, et al. “The Splay-List: A Distribution-Adaptive Concurrent
Skip-List.” Distributed Computing, vol. 36, Springer Nature, 2023, pp.
395–418, doi:10.1007/s00446-022-00441-x.'
short: V. Aksenov, D.-A. Alistarh, A. Drozdova, A. Mohtashami, Distributed Computing
36 (2023) 395–418.
date_created: 2023-01-22T23:00:55Z
date_published: 2023-09-01T00:00:00Z
date_updated: 2023-08-14T12:54:32Z
day: '01'
department:
- _id: DaAl
doi: 10.1007/s00446-022-00441-x
external_id:
arxiv:
- '2008.01009'
isi:
- '000913424000001'
intvolume: ' 36'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2008.01009
month: '09'
oa: 1
oa_version: Preprint
page: 395-418
publication: Distributed Computing
publication_identifier:
eissn:
- 1432-0452
issn:
- 0178-2770
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'The splay-list: A distribution-adaptive concurrent skip-list'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 36
year: '2023'
...
---
_id: '12566'
abstract:
- lang: eng
text: "Approximate agreement is one of the few variants of consensus that can be
solved in a wait-free manner in asynchronous systems where processes communicate
by reading and writing to shared memory. In this work, we consider a natural generalisation
of approximate agreement on arbitrary undirected connected graphs. Each process
is given a node of the graph as input and, if non-faulty, must output a node such
that\r\n– all the outputs are within distance 1 of one another, and\r\n– each
output value lies on a shortest path between two input values.\r\nFrom prior work,
it is known that there is no wait-free algorithm among processes for this problem
on any cycle of length , by reduction from 2-set agreement (Castañeda et al.,
2018).\r\n\r\nIn this work, we investigate the solvability of this task on general
graphs. We give a new, direct proof of the impossibility of approximate agreement
on cycles of length , via a generalisation of Sperner's Lemma to convex polygons.
We also extend the reduction from 2-set agreement to a larger class of graphs,
showing that approximate agreement on these graphs is unsolvable. On the positive
side, we present a wait-free algorithm for a different class of graphs, which
properly contains the class of chordal graphs."
acknowledgement: This project has received funding from the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation programme
(grant agreement No. 805223 ScaleML) and under the Marie Skłodowska-Curie grant
agreement No. 840605 and from the Natural Sciences and Engineering Research Council
of Canada grant RGPIN-2020-04178. Part of this work was done while Faith Ellen was
visiting IST Austria.
article_number: '113733'
article_processing_charge: Yes (via OA deal)
article_type: original
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: Faith
full_name: Ellen, Faith
last_name: Ellen
- 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, Ellen F, Rybicki J. Wait-free approximate agreement on graphs.
Theoretical Computer Science. 2023;948(2). doi:10.1016/j.tcs.2023.113733
apa: Alistarh, D.-A., Ellen, F., & Rybicki, J. (2023). Wait-free approximate
agreement on graphs. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2023.113733
chicago: Alistarh, Dan-Adrian, Faith Ellen, and Joel Rybicki. “Wait-Free Approximate
Agreement on Graphs.” Theoretical Computer Science. Elsevier, 2023. https://doi.org/10.1016/j.tcs.2023.113733.
ieee: D.-A. Alistarh, F. Ellen, and J. Rybicki, “Wait-free approximate agreement
on graphs,” Theoretical Computer Science, vol. 948, no. 2. Elsevier, 2023.
ista: Alistarh D-A, Ellen F, Rybicki J. 2023. Wait-free approximate agreement on
graphs. Theoretical Computer Science. 948(2), 113733.
mla: Alistarh, Dan-Adrian, et al. “Wait-Free Approximate Agreement on Graphs.” Theoretical
Computer Science, vol. 948, no. 2, 113733, Elsevier, 2023, doi:10.1016/j.tcs.2023.113733.
short: D.-A. Alistarh, F. Ellen, J. Rybicki, Theoretical Computer Science 948 (2023).
corr_author: '1'
date_created: 2023-02-19T23:00:55Z
date_published: 2023-02-28T00:00:00Z
date_updated: 2025-04-14T07:49:16Z
day: '28'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1016/j.tcs.2023.113733
ec_funded: 1
external_id:
isi:
- '000934262700001'
file:
- access_level: open_access
checksum: b27c5290f2f1500c403494364ee39c9f
content_type: application/pdf
creator: dernst
date_created: 2023-02-20T07:30:20Z
date_updated: 2023-02-20T07:30:20Z
file_id: '12570'
file_name: 2023_TheoreticalCompScience_Alistarh.pdf
file_size: 602333
relation: main_file
success: 1
file_date_updated: 2023-02-20T07:30:20Z
has_accepted_license: '1'
intvolume: ' 948'
isi: 1
issue: '2'
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: Theoretical Computer Science
publication_identifier:
issn:
- 0304-3975
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Wait-free approximate agreement 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: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 948
year: '2023'
...
---
_id: '12735'
abstract:
- lang: eng
text: "Asynchronous programming has gained significant popularity over the last
decade: support for this programming pattern is available in many popular languages
via libraries and native language implementations, typically in the form of coroutines
or the async/await construct. Instead of programming via shared memory, this concept
assumes implicit synchronization through message passing. The key data structure
enabling such communication is the rendezvous channel. Roughly, a rendezvous channel
is a blocking queue of size zero, so both send(e) and receive() operations wait
for each other, performing a rendezvous when they meet. To optimize the message
passing pattern, channels are usually equipped with a fixed-size buffer, so sends
do not suspend and put elements into the buffer until its capacity is exceeded.
This primitive is known as a buffered channel.\r\n\r\nThis paper presents a fast
and scalable algorithm for both rendezvous and buffered channels. Similarly to
modern queues, our solution is based on an infinite array with two positional
counters for send(e) and receive() operations, leveraging the unconditional Fetch-And-Add
instruction to update them. Yet, the algorithm requires non-trivial modifications
of this classic pattern, in order to support the full channel semantics, such
as buffering and cancellation of waiting requests. We compare the performance
of our solution to that of the Kotlin implementation, as well as against other
academic proposals, showing up to 9.8× speedup. To showcase its expressiveness
and performance, we also integrated the proposed algorithm into the standard Kotlin
Coroutines library, replacing the previous channel implementations."
article_processing_charge: No
arxiv: 1
author:
- first_name: Nikita
full_name: Koval, Nikita
id: 2F4DB10C-F248-11E8-B48F-1D18A9856A87
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
- first_name: Roman
full_name: Elizarov, Roman
last_name: Elizarov
citation:
ama: 'Koval N, Alistarh D-A, Elizarov R. Fast and scalable channels in Kotlin Coroutines.
In: Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of
Parallel Programming. Association for Computing Machinery; 2023:107-118. doi:10.1145/3572848.3577481'
apa: 'Koval, N., Alistarh, D.-A., & Elizarov, R. (2023). Fast and scalable channels
in Kotlin Coroutines. In Proceedings of the ACM SIGPLAN Symposium on Principles
and Practice of Parallel Programming (pp. 107–118). Montreal, QC, Canada:
Association for Computing Machinery. https://doi.org/10.1145/3572848.3577481'
chicago: Koval, Nikita, Dan-Adrian Alistarh, and Roman Elizarov. “Fast and Scalable
Channels in Kotlin Coroutines.” In Proceedings of the ACM SIGPLAN Symposium
on Principles and Practice of Parallel Programming, 107–18. Association for
Computing Machinery, 2023. https://doi.org/10.1145/3572848.3577481.
ieee: N. Koval, D.-A. Alistarh, and R. Elizarov, “Fast and scalable channels in
Kotlin Coroutines,” in Proceedings of the ACM SIGPLAN Symposium on Principles
and Practice of Parallel Programming, Montreal, QC, Canada, 2023, pp. 107–118.
ista: 'Koval N, Alistarh D-A, Elizarov R. 2023. Fast and scalable channels in Kotlin
Coroutines. Proceedings of the ACM SIGPLAN Symposium on Principles and Practice
of Parallel Programming. PPoPP: Sympopsium on Principles and Practice of Parallel
Programming, 107–118.'
mla: Koval, Nikita, et al. “Fast and Scalable Channels in Kotlin Coroutines.” Proceedings
of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming,
Association for Computing Machinery, 2023, pp. 107–18, doi:10.1145/3572848.3577481.
short: N. Koval, D.-A. Alistarh, R. Elizarov, in:, Proceedings of the ACM SIGPLAN
Symposium on Principles and Practice of Parallel Programming, Association for
Computing Machinery, 2023, pp. 107–118.
conference:
end_date: 2023-03-01
location: Montreal, QC, Canada
name: 'PPoPP: Sympopsium on Principles and Practice of Parallel Programming'
start_date: 2023-02-25
date_created: 2023-03-19T23:00:58Z
date_published: 2023-02-25T00:00:00Z
date_updated: 2023-03-20T07:29:28Z
day: '25'
department:
- _id: DaAl
doi: 10.1145/3572848.3577481
external_id:
arxiv:
- '2211.04986'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2211.04986
month: '02'
oa: 1
oa_version: Preprint
page: 107-118
publication: Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of
Parallel Programming
publication_identifier:
isbn:
- '9798400700156'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Fast and scalable channels in Kotlin Coroutines
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...
---
_id: '12736'
abstract:
- lang: eng
text: Although a wide variety of handcrafted concurrent data structures have been
proposed, there is considerable interest in universal approaches (Universal Constructions
or UCs) for building concurrent data structures. UCs (semi-)automatically convert
a sequential data structure into a concurrent one. The simplest approach uses
locks [3, 6] that protect a sequential data structure and allow only one process
to access it at a time. However, the resulting data structure is blocking. Most
work on UCs instead focuses on obtaining non-blocking progress guarantees such
as obstruction-freedom, lock-freedom or wait-freedom. Many non-blocking UCs have
appeared. Key examples include the seminal wait-free UC [2] by Herlihy, a NUMA-aware
UC [10] by Yi et al., and an efficient UC for large objects [1] by Fatourou et
al.
acknowledgement: 'This work was supported by: the Natural Sciences and Engineering
Research Council of Canada (NSERC) Discovery Program grant: RGPIN-2019-04227, and
the Canada Foundation for Innovation John R. Evans Leaders Fund (CFI-JELF) with
equal support from the Ontario Research Fund CFI Leaders Opportunity Fund: 38512.'
article_processing_charge: No
author:
- first_name: Vitaly
full_name: Aksenov, Vitaly
last_name: Aksenov
- first_name: Trevor A
full_name: Brown, Trevor A
id: 3569F0A0-F248-11E8-B48F-1D18A9856A87
last_name: Brown
- first_name: Alexander
full_name: Fedorov, Alexander
id: 2e711909-896a-11ed-bdf8-eb0f5a2984c6
last_name: Fedorov
- first_name: Ilya
full_name: Kokorin, Ilya
last_name: Kokorin
citation:
ama: Aksenov V, Brown TA, Fedorov A, Kokorin I. Unexpected Scaling in Path Copying
Trees. Association for Computing Machinery; 2023:438-440. doi:10.1145/3572848.3577512
apa: 'Aksenov, V., Brown, T. A., Fedorov, A., & Kokorin, I. (2023). Unexpected
scaling in path copying trees. Proceedings of the ACM SIGPLAN Symposium
on Principles and Practice of Parallel Programming (pp. 438–440). Montreal,
QB, Canada: Association for Computing Machinery. https://doi.org/10.1145/3572848.3577512'
chicago: Aksenov, Vitaly, Trevor A Brown, Alexander Fedorov, and Ilya Kokorin. Unexpected
Scaling in Path Copying Trees. Proceedings of the ACM SIGPLAN Symposium
on Principles and Practice of Parallel Programming. Association for Computing
Machinery, 2023. https://doi.org/10.1145/3572848.3577512.
ieee: V. Aksenov, T. A. Brown, A. Fedorov, and I. Kokorin, Unexpected scaling
in path copying trees. Association for Computing Machinery, 2023, pp. 438–440.
ista: Aksenov V, Brown TA, Fedorov A, Kokorin I. 2023. Unexpected scaling in path
copying trees, Association for Computing Machinery,p.
mla: Aksenov, Vitaly, et al. “Unexpected Scaling in Path Copying Trees.” Proceedings
of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming,
Association for Computing Machinery, 2023, pp. 438–40, doi:10.1145/3572848.3577512.
short: V. Aksenov, T.A. Brown, A. Fedorov, I. Kokorin, Unexpected Scaling in Path
Copying Trees, Association for Computing Machinery, 2023.
conference:
end_date: 2023-03-01
location: Montreal, QB, Canada
name: 'PPoPP: Sympopsium on Principles and Practice of Parallel Programming'
start_date: 2023-02-25
date_created: 2023-03-19T23:00:58Z
date_published: 2023-02-25T00:00:00Z
date_updated: 2024-10-21T06:01:21Z
day: '25'
department:
- _id: DaAl
- _id: GradSch
doi: 10.1145/3572848.3577512
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1145/3572848.3577512
month: '02'
oa: 1
oa_version: Published Version
page: 438-440
publication: Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of
Parallel Programming
publication_identifier:
isbn:
- '9798400700156'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Unexpected scaling in path copying trees
type: conference_poster
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...
---
_id: '13179'
abstract:
- lang: eng
text: "Writing concurrent code that is both correct and efficient is notoriously
difficult. Thus, programmers often prefer to use synchronization abstractions,
which render code simpler and easier to reason about. Despite a wealth of work
on this topic, there is still a gap between the rich semantics provided by synchronization
abstractions in modern programming languages—specifically, fair FIFO ordering
of synchronization requests and support for abortable operations—and frameworks
for implementing it correctly and efficiently. Supporting such semantics is critical
given the rising popularity of constructs for asynchronous programming, such as
coroutines, which abort frequently and are cheaper to suspend and resume compared
to native threads.\r\n\r\nThis paper introduces a new framework called CancellableQueueSynchronizer
(CQS), which enables simple yet efficient implementations of a wide range of fair
and abortable synchronization primitives: mutexes, semaphores, barriers, count-down
latches, and blocking pools. Our main contribution is algorithmic, as implementing
both fairness and abortability efficiently at this level of generality is non-trivial.
Importantly, all our algorithms, including the CQS framework and the primitives
built on top of it, come with formal proofs in the Iris framework for Coq for
many of their properties. These proofs are modular, so it is easy to show correctness
for new primitives implemented on top of CQS. From a practical perspective, implementation
of CQS for native threads on the JVM improves throughput by up to two orders of
magnitude over Java’s AbstractQueuedSynchronizer, the only practical abstraction
offering similar semantics. Further, we successfully integrated CQS as a core
component of the popular Kotlin Coroutines library, validating the framework’s
practical impact and expressiveness in a real-world environment. In sum, CancellableQueueSynchronizer
is the first framework to combine expressiveness with formal guarantees and solid
practical performance. Our approach should be extensible to other languages and
families of synchronization primitives."
article_number: '116'
article_processing_charge: No
article_type: original
author:
- first_name: Nikita
full_name: Koval, Nikita
id: 2F4DB10C-F248-11E8-B48F-1D18A9856A87
last_name: Koval
- first_name: Dmitry
full_name: Khalanskiy, Dmitry
last_name: Khalanskiy
- 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: 'Koval N, Khalanskiy D, Alistarh D-A. CQS: A formally-verified framework for
fair and abortable synchronization. Proceedings of the ACM on Programming Languages.
2023;7. doi:10.1145/3591230'
apa: 'Koval, N., Khalanskiy, D., & Alistarh, D.-A. (2023). CQS: A formally-verified
framework for fair and abortable synchronization. Proceedings of the ACM on
Programming Languages. Association for Computing Machinery . https://doi.org/10.1145/3591230'
chicago: 'Koval, Nikita, Dmitry Khalanskiy, and Dan-Adrian Alistarh. “CQS: A Formally-Verified
Framework for Fair and Abortable Synchronization.” Proceedings of the ACM on
Programming Languages. Association for Computing Machinery , 2023. https://doi.org/10.1145/3591230.'
ieee: 'N. Koval, D. Khalanskiy, and D.-A. Alistarh, “CQS: A formally-verified framework
for fair and abortable synchronization,” Proceedings of the ACM on Programming
Languages, vol. 7. Association for Computing Machinery , 2023.'
ista: 'Koval N, Khalanskiy D, Alistarh D-A. 2023. CQS: A formally-verified framework
for fair and abortable synchronization. Proceedings of the ACM on Programming
Languages. 7, 116.'
mla: 'Koval, Nikita, et al. “CQS: A Formally-Verified Framework for Fair and Abortable
Synchronization.” Proceedings of the ACM on Programming Languages, vol.
7, 116, Association for Computing Machinery , 2023, doi:10.1145/3591230.'
short: N. Koval, D. Khalanskiy, D.-A. Alistarh, Proceedings of the ACM on Programming
Languages 7 (2023).
corr_author: '1'
date_created: 2023-07-02T22:00:43Z
date_published: 2023-06-06T00:00:00Z
date_updated: 2024-10-09T21:05:51Z
day: '06'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1145/3591230
file:
- access_level: open_access
checksum: 5dba6e73f0ed79adbdae14d165bc2f68
content_type: application/pdf
creator: alisjak
date_created: 2023-07-03T13:09:39Z
date_updated: 2023-07-03T13:09:39Z
file_id: '13187'
file_name: 2023_ACMProgram.Lang._Koval.pdf
file_size: 1266773
relation: main_file
success: 1
file_date_updated: 2023-07-03T13:09:39Z
has_accepted_license: '1'
intvolume: ' 7'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
publication: Proceedings of the ACM on Programming Languages
publication_identifier:
eissn:
- 2475-1421
publication_status: published
publisher: 'Association for Computing Machinery '
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'CQS: A formally-verified framework for fair and abortable synchronization'
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: 7
year: '2023'
...
---
_id: '13262'
abstract:
- lang: eng
text: 'Determining the degree of inherent parallelism in classical sequential algorithms
and leveraging it for fast parallel execution is a key topic in parallel computing,
and detailed analyses are known for a wide range of classical algorithms. In this
paper, we perform the first such analysis for the fundamental Union-Find problem,
in which we are given a graph as a sequence of edges, and must maintain its connectivity
structure under edge additions. We prove that classic sequential algorithms for
this problem are well-parallelizable under reasonable assumptions, addressing
a conjecture by [Blelloch, 2017]. More precisely, we show via a new potential
argument that, under uniform random edge ordering, parallel union-find operations
are unlikely to interfere: T concurrent threads processing the graph in parallel
will encounter memory contention O(T2 · log |V| · log |E|) times in expectation,
where |E| and |V| are the number of edges and nodes in the graph, respectively.
We leverage this result to design a new parallel Union-Find algorithm that is
both internally deterministic, i.e., its results are guaranteed to match those
of a sequential execution, but also work-efficient and scalable, as long as the
number of threads T is O(|E|1 over 3 - ε), for an arbitrarily small constant ε
> 0, which holds for most large real-world graphs. We present lower bounds which
show that our analysis is close to optimal, and experimental results suggesting
that the performance cost of internal determinism is limited.'
article_processing_charge: Yes (via OA deal)
arxiv: 1
author:
- first_name: Alexander
full_name: Fedorov, Alexander
id: 2e711909-896a-11ed-bdf8-eb0f5a2984c6
last_name: Fedorov
- first_name: Diba
full_name: Hashemi, Diba
id: ed9595ea-2f8f-11ee-ba95-d2b546540783
last_name: Hashemi
- 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: 'Fedorov A, Hashemi D, Nadiradze G, Alistarh D-A. Provably-efficient and internally-deterministic
parallel Union-Find. In: Proceedings of the 35th ACM Symposium on Parallelism
in Algorithms and Architectures. Association for Computing Machinery; 2023:261-271.
doi:10.1145/3558481.3591082'
apa: 'Fedorov, A., Hashemi, D., Nadiradze, G., & Alistarh, D.-A. (2023). Provably-efficient
and internally-deterministic parallel Union-Find. In Proceedings of the 35th
ACM Symposium on Parallelism in Algorithms and Architectures (pp. 261–271).
Orlando, FL, United States: Association for Computing Machinery. https://doi.org/10.1145/3558481.3591082'
chicago: Fedorov, Alexander, Diba Hashemi, Giorgi Nadiradze, and Dan-Adrian Alistarh.
“Provably-Efficient and Internally-Deterministic Parallel Union-Find.” In Proceedings
of the 35th ACM Symposium on Parallelism in Algorithms and Architectures,
261–71. Association for Computing Machinery, 2023. https://doi.org/10.1145/3558481.3591082.
ieee: A. Fedorov, D. Hashemi, G. Nadiradze, and D.-A. Alistarh, “Provably-efficient
and internally-deterministic parallel Union-Find,” in Proceedings of the 35th
ACM Symposium on Parallelism in Algorithms and Architectures, Orlando, FL,
United States, 2023, pp. 261–271.
ista: 'Fedorov A, Hashemi D, Nadiradze G, Alistarh D-A. 2023. Provably-efficient
and internally-deterministic parallel Union-Find. Proceedings of the 35th ACM
Symposium on Parallelism in Algorithms and Architectures. SPAA: Symposium on Parallelism
in Algorithms and Architectures, 261–271.'
mla: Fedorov, Alexander, et al. “Provably-Efficient and Internally-Deterministic
Parallel Union-Find.” Proceedings of the 35th ACM Symposium on Parallelism
in Algorithms and Architectures, Association for Computing Machinery, 2023,
pp. 261–71, doi:10.1145/3558481.3591082.
short: A. Fedorov, D. Hashemi, G. Nadiradze, D.-A. Alistarh, in:, Proceedings of
the 35th ACM Symposium on Parallelism in Algorithms and Architectures, Association
for Computing Machinery, 2023, pp. 261–271.
conference:
end_date: 2023-06-19
location: Orlando, FL, United States
name: 'SPAA: Symposium on Parallelism in Algorithms and Architectures'
start_date: 2023-06-17
corr_author: '1'
date_created: 2023-07-23T22:01:12Z
date_published: 2023-06-17T00:00:00Z
date_updated: 2025-09-09T12:43:18Z
day: '17'
ddc:
- '000'
department:
- _id: DaAl
- _id: GradSch
doi: 10.1145/3558481.3591082
external_id:
arxiv:
- '2304.09331'
isi:
- '001108889000024'
file:
- access_level: open_access
checksum: 72e312aabf0c5248c99b5cd3a88e4c88
content_type: application/pdf
creator: dernst
date_created: 2023-07-31T10:53:08Z
date_updated: 2023-07-31T10:53:08Z
file_id: '13334'
file_name: 2023_SPAA_Fedorov.pdf
file_size: 2087937
relation: main_file
success: 1
file_date_updated: 2023-07-31T10:53:08Z
has_accepted_license: '1'
isi: 1
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 261-271
publication: Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and
Architectures
publication_identifier:
isbn:
- '9781450395458'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Provably-efficient and internally-deterministic parallel Union-Find
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: '2023'
...
---
OA_place: repository
OA_type: green
_id: '19983'
abstract:
- lang: eng
text: 'The sinkless orientation problem plays a key role in understanding the foundations
of distributed computing. The problem can be used to separate two fundamental
models of distributed graph algorithms, LOCAL and SLOCAL: the locality of sinkless
orientation is Ω(log n) in the deterministic LOCAL model and O(log log n) in the
deterministic SLOCAL model. Both of these results are known by prior work, but
here we give new simple, self-contained proofs for them.'
acknowledgement: We thank the anonymous reviewers for their helpful feedback on previous
versions of this work. Parts ofthis work appeared in DISC 2021 as a brief announcement
[ 21]. This work was supported in part by theEuropean Research Council (ERC) under
the European Union’s Horizon 2020 research and innovationprogramme (grant agreement
No 805223 ScaleML), the Academy of Finland (grant agreement No 333837),the Austrian
Science Fund (FWF) and netIDEE (grant agreement No P 33775-N), and the AustrianScience
Fund (FWF) project DELTA (grant agreement No I 5025-N).
article_processing_charge: No
arxiv: 1
author:
- first_name: Alkida
full_name: Balliu, Alkida
last_name: Balliu
- first_name: Janne
full_name: Korhonen, Janne
id: C5402D42-15BC-11E9-A202-CA2BE6697425
last_name: Korhonen
- first_name: Fabian
full_name: Kuhn, Fabian
last_name: Kuhn
- first_name: Henrik
full_name: Lievonen, Henrik
last_name: Lievonen
- first_name: Dennis
full_name: Olivetti, Dennis
last_name: Olivetti
- first_name: Shreyas
full_name: Pai, Shreyas
last_name: Pai
- 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
- first_name: Jan
full_name: Studený, Jan
last_name: Studený
- first_name: Jukka
full_name: Suomela, Jukka
last_name: Suomela
- first_name: Jara
full_name: Uitto, Jara
last_name: Uitto
citation:
ama: 'Balliu A, Korhonen J, Kuhn F, et al. Sinkless Orientation Made Simple. In:
Symposium on Simplicity in Algorithms. 2023 Society for Industrial and
Applied Mathematics; 2023:175-191. doi:10.1137/1.9781611977585.ch17'
apa: 'Balliu, A., Korhonen, J., Kuhn, F., Lievonen, H., Olivetti, D., Pai, S., …
Uitto, J. (2023). Sinkless Orientation Made Simple. In Symposium on Simplicity
in Algorithms (pp. 175–191). Florence, Italy: 2023 Society for Industrial
and Applied Mathematics. https://doi.org/10.1137/1.9781611977585.ch17'
chicago: Balliu, Alkida, Janne Korhonen, Fabian Kuhn, Henrik Lievonen, Dennis Olivetti,
Shreyas Pai, Ami Paz, et al. “Sinkless Orientation Made Simple.” In Symposium
on Simplicity in Algorithms, 175–91. 2023 Society for Industrial and Applied
Mathematics, 2023. https://doi.org/10.1137/1.9781611977585.ch17.
ieee: A. Balliu et al., “Sinkless Orientation Made Simple,” in Symposium
on Simplicity in Algorithms, 2023 Society for Industrial and Applied Mathematics,
2023, pp. 175–191.
ista: 'Balliu A, Korhonen J, Kuhn F, Lievonen H, Olivetti D, Pai S, Paz A, Rybicki
J, Schmid S, Studený J, Suomela J, Uitto J. 2023.Sinkless Orientation Made Simple.
In: Symposium on Simplicity in Algorithms. , 175–191.'
mla: Balliu, Alkida, et al. “Sinkless Orientation Made Simple.” Symposium on
Simplicity in Algorithms, 2023 Society for Industrial and Applied Mathematics,
2023, pp. 175–91, doi:10.1137/1.9781611977585.ch17.
short: A. Balliu, J. Korhonen, F. Kuhn, H. Lievonen, D. Olivetti, S. Pai, A. Paz,
J. Rybicki, S. Schmid, J. Studený, J. Suomela, J. Uitto, in:, Symposium on Simplicity
in Algorithms, 2023 Society for Industrial and Applied Mathematics, 2023, pp.
175–191.
conference:
end_date: 2023-01-25
location: Florence, Italy
name: 'SOSA: Symposium on Simplicity in Algorithms'
start_date: 2023-01-23
date_created: 2025-07-10T13:11:47Z
date_published: 2023-01-12T00:00:00Z
date_updated: 2025-09-24T09:24:20Z
day: '12'
department:
- _id: DaAl
doi: 10.1137/1.9781611977585.ch17
ec_funded: 1
external_id:
arxiv:
- '2108.02655'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2108.02655
month: '01'
oa: 1
oa_version: Preprint
page: 175-191
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: P33775
name: Fast Algorithms for a Reactive Network Layer
publication: Symposium on Simplicity in Algorithms
publication_identifier:
eisbn:
- '9781611977585'
publication_status: published
publisher: 2023 Society for Industrial and Applied Mathematics
quality_controlled: '1'
status: public
title: Sinkless Orientation Made Simple
type: book_chapter
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...
---
_id: '14815'
abstract:
- lang: eng
text: In the last few years, various communication compression techniques have emerged
as an indispensable tool helping to alleviate the communication bottleneck in
distributed learning. However, despite the fact biased compressors often show
superior performance in practice when compared to the much more studied and understood
unbiased compressors, very little is known about them. In this work we study three
classes of biased compression operators, two of which are new, and their performance
when applied to (stochastic) gradient descent and distributed (stochastic) gradient
descent. We show for the first time that biased compressors can lead to linear
convergence rates both in the single node and distributed settings. We prove that
distributed compressed SGD method, employed with error feedback mechanism, enjoys
the ergodic rate O(δLexp[−μKδL]+(C+δD)Kμ), where δ≥1 is a compression parameter
which grows when more compression is applied, L and μ are the smoothness and strong
convexity constants, C captures stochastic gradient noise (C=0 if full gradients
are computed on each node) and D captures the variance of the gradients at the
optimum (D=0 for over-parameterized models). Further, via a theoretical study
of several synthetic and empirical distributions of communicated gradients, we
shed light on why and by how much biased compressors outperform their unbiased
variants. Finally, we propose several new biased compressors with promising theoretical
guarantees and practical performance.
acknowledgement: 'The work in Sections 1-5 was conducted while A. Beznosikov was a
research intern in the Optimizationand Machine Learning Lab of Peter Richtárik at
KAUST; this visit was funded by the KAUST Baseline Research Funding Scheme. The
work of A. Beznosikov in Section 6 was conducted in Skoltech and was supported by
Ministry of Science and Higher Education grant No. 075-10-2021-068. '
article_processing_charge: Yes (in subscription journal)
article_type: original
arxiv: 1
author:
- first_name: Aleksandr
full_name: Beznosikov, Aleksandr
last_name: Beznosikov
- first_name: Samuel
full_name: Horvath, Samuel
last_name: Horvath
- first_name: Peter
full_name: Richtarik, Peter
last_name: Richtarik
- first_name: Mher
full_name: Safaryan, Mher
id: dd546b39-0804-11ed-9c55-ef075c39778d
last_name: Safaryan
citation:
ama: Beznosikov A, Horvath S, Richtarik P, Safaryan M. On biased compression for
distributed learning. Journal of Machine Learning Research. 2023;24:1-50.
apa: Beznosikov, A., Horvath, S., Richtarik, P., & Safaryan, M. (2023). On biased
compression for distributed learning. Journal of Machine Learning Research.
Journal of Machine Learning Research.
chicago: Beznosikov, Aleksandr, Samuel Horvath, Peter Richtarik, and Mher Safaryan.
“On Biased Compression for Distributed Learning.” Journal of Machine Learning
Research. Journal of Machine Learning Research, 2023.
ieee: A. Beznosikov, S. Horvath, P. Richtarik, and M. Safaryan, “On biased compression
for distributed learning,” Journal of Machine Learning Research, vol. 24.
Journal of Machine Learning Research, pp. 1–50, 2023.
ista: Beznosikov A, Horvath S, Richtarik P, Safaryan M. 2023. On biased compression
for distributed learning. Journal of Machine Learning Research. 24, 1–50.
mla: Beznosikov, Aleksandr, et al. “On Biased Compression for Distributed Learning.”
Journal of Machine Learning Research, vol. 24, Journal of Machine Learning
Research, 2023, pp. 1–50.
short: A. Beznosikov, S. Horvath, P. Richtarik, M. Safaryan, Journal of Machine
Learning Research 24 (2023) 1–50.
corr_author: '1'
date_created: 2024-01-16T12:13:36Z
date_published: 2023-10-01T00:00:00Z
date_updated: 2024-10-09T21:07:52Z
day: '01'
ddc:
- '000'
department:
- _id: DaAl
external_id:
arxiv:
- '2002.12410'
isi:
- '001111578500001'
file:
- access_level: open_access
checksum: c50f2b9db53938b755e30a085f464059
content_type: application/pdf
creator: dernst
date_created: 2024-01-16T12:13:27Z
date_updated: 2024-01-16T12:13:27Z
file_id: '14816'
file_name: 2023_JMLR_Beznosikov.pdf
file_size: 1510993
relation: main_file
success: 1
file_date_updated: 2024-01-16T12:13:27Z
has_accepted_license: '1'
intvolume: ' 24'
isi: 1
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
page: 1-50
publication: Journal of Machine Learning Research
publication_identifier:
eissn:
- 1533-7928
publication_status: published
publisher: Journal of Machine Learning Research
quality_controlled: '1'
status: public
title: On biased compression for distributed 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: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 24
year: '2023'
...
---
_id: '14995'
abstract:
- lang: eng
text: "Lincheck is a new practical and user-friendly framework for testing concurrent
data structures on the Java Virtual Machine (JVM). It provides a simple and declarative
way to write concurrent tests. Instead of describing how to perform the test,
users specify what to test by declaring all the operations to examine; the framework
automatically handles the rest. As a result, tests written with Lincheck are concise
and easy to understand. \r\nThe artifact presents a collection of Lincheck tests
that discover new bugs in popular libraries and implementations from the concurrency
literature -- they are listed in Table 1, Section 3. To evaluate the performance
of Lincheck analysis, the collection of tests also includes those which check
correct data structures and, thus, always succeed. Similarly to Table 2, Section
3, the experiments demonstrate the reasonable time to perform a test. Finally,
Lincheck provides user-friendly output with an easy-to-follow trace to reproduce
a detected error, significantly simplifying further investigation."
article_processing_charge: No
author:
- first_name: Nikita
full_name: Koval, Nikita
id: 2F4DB10C-F248-11E8-B48F-1D18A9856A87
last_name: Koval
- first_name: Alexander
full_name: Fedorov, Alexander
id: 2e711909-896a-11ed-bdf8-eb0f5a2984c6
last_name: Fedorov
- first_name: Maria
full_name: Sokolova, Maria
last_name: Sokolova
- first_name: Dmitry
full_name: Tsitelov, Dmitry
last_name: Tsitelov
- 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: 'Koval N, Fedorov A, Sokolova M, Tsitelov D, Alistarh D-A. Lincheck: A practical
framework for testing concurrent data structures on JVM. 2023. doi:10.5281/ZENODO.7877757'
apa: 'Koval, N., Fedorov, A., Sokolova, M., Tsitelov, D., & Alistarh, D.-A.
(2023). Lincheck: A practical framework for testing concurrent data structures
on JVM. Zenodo. https://doi.org/10.5281/ZENODO.7877757'
chicago: 'Koval, Nikita, Alexander Fedorov, Maria Sokolova, Dmitry Tsitelov, and
Dan-Adrian Alistarh. “Lincheck: A Practical Framework for Testing Concurrent Data
Structures on JVM.” Zenodo, 2023. https://doi.org/10.5281/ZENODO.7877757.'
ieee: 'N. Koval, A. Fedorov, M. Sokolova, D. Tsitelov, and D.-A. Alistarh, “Lincheck:
A practical framework for testing concurrent data structures on JVM.” Zenodo,
2023.'
ista: 'Koval N, Fedorov A, Sokolova M, Tsitelov D, Alistarh D-A. 2023. Lincheck:
A practical framework for testing concurrent data structures on JVM, Zenodo, 10.5281/ZENODO.7877757.'
mla: 'Koval, Nikita, et al. Lincheck: A Practical Framework for Testing Concurrent
Data Structures on JVM. Zenodo, 2023, doi:10.5281/ZENODO.7877757.'
short: N. Koval, A. Fedorov, M. Sokolova, D. Tsitelov, D.-A. Alistarh, (2023).
date_created: 2024-02-14T15:14:13Z
date_published: 2023-04-28T00:00:00Z
date_updated: 2025-09-09T12:51:51Z
day: '28'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.5281/ZENODO.7877757
main_file_link:
- open_access: '1'
url: https://doi.org/10.5281/zenodo.7877757
month: '04'
oa: 1
oa_version: Published Version
publisher: Zenodo
related_material:
record:
- id: '14260'
relation: used_in_publication
status: public
status: public
title: 'Lincheck: A practical framework for testing concurrent data structures on
JVM'
type: research_data_reference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...
---
_id: '15363'
abstract:
- lang: eng
text: Knowledge distillation is a popular approach for enhancing the performance
of "student" models, with lower representational capacity, by taking advantage
of more powerful "teacher" models. Despite its apparent simplicity, the underlying
mechanics behind knowledge distillation (KD) are not yet fully understood. In
this work, we shed new light on the inner workings of this method, by examining
it from an optimization perspective. Specifically, we show that, in the context
of linear and deep linear models, KD can be interpreted as a novel type of stochastic
variance reduction mechanism. We provide a detailed convergence analysis of the
resulting dynamics, which hold under standard assumptions for both strongly-convex
and non-convex losses, showing that KD acts as a form of \emph{partial variance
reduction}, which can reduce the stochastic gradient noise, but may not eliminate
it completely, depending on the properties of the teacher'' model. Our analysis
puts further emphasis on the need for careful parametrization of KD, in particular
w.r.t. the weighting of the distillation loss, and is validated empirically on
both linear models and deep neural networks.
acknowledgement: "MS has received funding from the European Union’s Horizon 2020 research
and innovation programme\r\nunder the Marie Skłodowska-Curie grant agreement No
101034413."
alternative_title:
- NeurIPS
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Mher
full_name: Safaryan, Mher
id: dd546b39-0804-11ed-9c55-ef075c39778d
last_name: Safaryan
- first_name: Elena-Alexandra
full_name: Peste, Elena-Alexandra
id: 32D78294-F248-11E8-B48F-1D18A9856A87
last_name: Peste
- 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: 'Safaryan M, Krumes A, Alistarh D-A. Knowledge distillation performs partial
variance reduction. In: 36th Conference on Neural Information Processing Systems.
Vol 36. ; 2023.'
apa: Safaryan, M., Krumes, A., & Alistarh, D.-A. (2023). Knowledge distillation
performs partial variance reduction. In 36th Conference on Neural Information
Processing Systems (Vol. 36). New Orleans, LA, United States.
chicago: Safaryan, Mher, Alexandra Krumes, and Dan-Adrian Alistarh. “Knowledge Distillation
Performs Partial Variance Reduction.” In 36th Conference on Neural Information
Processing Systems, Vol. 36, 2023.
ieee: M. Safaryan, A. Krumes, and D.-A. Alistarh, “Knowledge distillation performs
partial variance reduction,” in 36th Conference on Neural Information Processing
Systems, New Orleans, LA, United States, 2023, vol. 36.
ista: 'Safaryan M, Krumes A, Alistarh D-A. 2023. Knowledge distillation performs
partial variance reduction. 36th Conference on Neural Information Processing Systems.
NeurIPS: Neural Information Processing Systems, NeurIPS, vol. 36.'
mla: Safaryan, Mher, et al. “Knowledge Distillation Performs Partial Variance Reduction.”
36th Conference on Neural Information Processing Systems, vol. 36, 2023.
short: M. Safaryan, A. Krumes, D.-A. Alistarh, in:, 36th Conference on Neural Information
Processing Systems, 2023.
conference:
end_date: 2023-12-16
location: New Orleans, LA, United States
name: 'NeurIPS: Neural Information Processing Systems'
start_date: 2023-12-10
corr_author: '1'
date_created: 2024-05-05T22:01:04Z
date_published: 2023-12-15T00:00:00Z
date_updated: 2025-04-14T07:54:55Z
day: '15'
ddc:
- '000'
department:
- _id: DaAl
ec_funded: 1
external_id:
arxiv:
- '2305.17581'
file:
- access_level: open_access
checksum: 288c5148a85abf24ad5e22a6b1183655
content_type: application/pdf
creator: dernst
date_created: 2024-05-22T08:08:08Z
date_updated: 2024-05-22T08:08:08Z
file_id: '15417'
file_name: 2023_Neurips_Safaryan.pdf
file_size: 672571
relation: main_file
success: 1
file_date_updated: 2024-05-22T08:08:08Z
has_accepted_license: '1'
intvolume: ' 36'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: 36th Conference on Neural Information Processing Systems
publication_identifier:
issn:
- 1049-5258
publication_status: published
quality_controlled: '1'
scopus_import: '1'
status: public
title: Knowledge distillation performs partial variance reduction
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: 36
year: '2023'
...
---
_id: '17378'
abstract:
- lang: eng
text: Generative Pre-trained Transformer models, known as GPT or OPT, set themselves
apart through breakthrough performance across complex language modelling tasks,
but also by their extremely high computational and storage costs. Specifically,
due to their massive size, even inference for large, highly-accurate GPT models
may require multiple performant GPUs, which limits the usability of such models.
While there is emerging work on relieving this pressure via model compression,
the applicability and performance of existing compression techniques is limited
by the scale and complexity of GPT models. In this paper, we address this challenge,
and propose OPTQ, a new one-shot weight quantization method based on approximate
second-order information, that is both highly-accurate and highly-efficient. Specifically,
OPTQ can quantize GPT models with 175 billion parameters in approximately four
GPU hours, reducing the bitwidth down to 3 or 4 bits per weight, with negligible
accuracy degradation relative to the uncompressed baseline. Our method more than
doubles the compression gains relative to previously-proposed one-shot quantization
methods, preserving accuracy, allowing us for the first time to execute an 175
billion-parameter model inside a single GPU for generative inference. Moreover,
we also show that our method can still provide reasonable accuracy in the extreme
quantization regime, in which weights are quantized to 2-bit or even ternary quantization
levels. We show experimentally that these improvements can be leveraged for end-to-end
inference speedups over FP16, of around 3.25x when using high-end GPUs (NVIDIA
A100) and 4.5x when using more cost-effective ones (NVIDIA A6000). The implementation
is available at https://github.com/IST-DASLab/gptq.
acknowledged_ssus:
- _id: ScienComp
acknowledgement: Elias Frantar and Dan Alistarh 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. The work of Saleh Ashkboos and Torsten Hoefler
was supported by the PASC DaCeMI project, received EuroHPC-JU funding under grant
MAELSTROM, No. 955513. We thank the Swiss National Supercomputing Center (CSCS)
for supporting us with compute infrastructure.
article_processing_charge: No
author:
- first_name: Elias
full_name: Frantar, Elias
id: 09a8f98d-ec99-11ea-ae11-c063a7b7fe5f
last_name: Frantar
- first_name: Saleh
full_name: Ashkboos, Saleh
last_name: Ashkboos
- first_name: Torsten
full_name: Hoefler, Torsten
last_name: Hoefler
- 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, Ashkboos S, Hoefler T, Alistarh D-A. OPTQ: Accurate post-training
quantization for generative pre-trained transformers. In: 11th International
Conference on Learning Representations . International Conference on Learning
Representations; 2023.'
apa: 'Frantar, E., Ashkboos, S., Hoefler, T., & Alistarh, D.-A. (2023). OPTQ:
Accurate post-training quantization for generative pre-trained transformers. In
11th International Conference on Learning Representations . Kigali, Rwanda:
International Conference on Learning Representations.'
chicago: 'Frantar, Elias, Saleh Ashkboos, Torsten Hoefler, and Dan-Adrian Alistarh.
“OPTQ: Accurate Post-Training Quantization for Generative Pre-Trained Transformers.”
In 11th International Conference on Learning Representations . International
Conference on Learning Representations, 2023.'
ieee: 'E. Frantar, S. Ashkboos, T. Hoefler, and D.-A. Alistarh, “OPTQ: Accurate
post-training quantization for generative pre-trained transformers,” in 11th
International Conference on Learning Representations , Kigali, Rwanda, 2023.'
ista: 'Frantar E, Ashkboos S, Hoefler T, Alistarh D-A. 2023. OPTQ: Accurate post-training
quantization for generative pre-trained transformers. 11th International Conference
on Learning Representations . ICLR: International Conference on Learning Representations.'
mla: 'Frantar, Elias, et al. “OPTQ: Accurate Post-Training Quantization for Generative
Pre-Trained Transformers.” 11th International Conference on Learning Representations
, International Conference on Learning Representations, 2023.'
short: E. Frantar, S. Ashkboos, T. Hoefler, D.-A. Alistarh, in:, 11th International
Conference on Learning Representations , International Conference on Learning
Representations, 2023.
conference:
end_date: 2023-05-05
location: Kigali, Rwanda
name: 'ICLR: International Conference on Learning Representations'
start_date: 2023-05-01
corr_author: '1'
date_created: 2024-08-04T22:01:22Z
date_published: 2023-05-01T00:00:00Z
date_updated: 2026-04-07T12:43:03Z
day: '01'
ddc:
- '000'
department:
- _id: DaAl
ec_funded: 1
file:
- access_level: open_access
checksum: aacbf11dbd8b02a3e0bfd942a33e0593
content_type: application/pdf
creator: dernst
date_created: 2024-08-05T07:52:44Z
date_updated: 2024-08-05T07:52:44Z
file_id: '17385'
file_name: 2023_ICLR_Frantar.pdf
file_size: 437492
relation: main_file
success: 1
file_date_updated: 2024-08-05T07:52:44Z
has_accepted_license: '1'
language:
- iso: eng
month: '05'
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: '11th International Conference on Learning Representations '
publication_status: published
publisher: International Conference on Learning Representations
quality_controlled: '1'
related_material:
link:
- relation: software
url: https://github.com/IST-DASLab/gptq
record:
- id: '17485'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: 'OPTQ: Accurate post-training quantization for generative pre-trained transformers'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...
---
_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-04-07T12:43:03Z
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'
...
---
_id: '14461'
abstract:
- lang: eng
text: 'Communication-reduction techniques are a popular way to improve scalability
in data-parallel training of deep neural networks (DNNs). The recent emergence
of large language models such as GPT has created the need for new approaches to
exploit data-parallelism. Among these, fully-sharded data parallel (FSDP) training
is highly popular, yet it still encounters scalability bottlenecks. One reason
is that applying compression techniques to FSDP is challenging: as the vast majority
of the communication involves the model’s weights, direct compression alters convergence
and leads to accuracy loss. We present QSDP, a variant of FSDP which supports
both gradient and weight quantization with theoretical guarantees, is simple to
implement and has essentially no overheads. To derive QSDP we prove that a natural
modification of SGD achieves convergence even when we only maintain quantized
weights, and thus the domain over which we train consists of quantized points
and is, therefore, highly non-convex. We validate this approach by training GPT-family
models with up to 1.3 billion parameters on a multi-node cluster. Experiments
show that QSDP preserves model accuracy, while completely removing the communication
bottlenecks of FSDP, providing end-to-end speedups of up to 2.2x.'
acknowledged_ssus:
- _id: ScienComp
acknowledgement: The authors 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), as well as experimental support from the IST
Austria IT department, in particular Stefano Elefante, Andrei Hornoiu, and Alois
Schloegl. AV acknowledges the support of the French Agence Nationale de la Recherche
(ANR), under grant ANR-21-CE48-0016 (project COMCOPT), the support of Fondation
Hadamard with a PRMO grant, and the support of CNRS with a CoopIntEER IEA grant
(project ALFRED).
alternative_title:
- PMLR
article_processing_charge: No
arxiv: 1
author:
- first_name: Ilia
full_name: Markov, Ilia
id: D0CF4148-C985-11E9-8066-0BDEE5697425
last_name: Markov
- first_name: Adrian
full_name: Vladu, Adrian
last_name: Vladu
- first_name: Qi
full_name: Guo, Qi
last_name: Guo
- 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, Vladu A, Guo Q, Alistarh D-A. Quantized distributed training of
large models with convergence guarantees. In: Proceedings of the 40th International
Conference on Machine Learning. Vol 202. ML Research Press; 2023:24020-24044.'
apa: 'Markov, I., Vladu, A., Guo, Q., & Alistarh, D.-A. (2023). Quantized distributed
training of large models with convergence guarantees. In Proceedings of the
40th International Conference on Machine Learning (Vol. 202, pp. 24020–24044).
Honolulu, Hawaii, HI, United States: ML Research Press.'
chicago: Markov, Ilia, Adrian Vladu, Qi Guo, and Dan-Adrian Alistarh. “Quantized
Distributed Training of Large Models with Convergence Guarantees.” In Proceedings
of the 40th International Conference on Machine Learning, 202:24020–44. ML
Research Press, 2023.
ieee: I. Markov, A. Vladu, Q. Guo, and D.-A. Alistarh, “Quantized distributed training
of large models with convergence guarantees,” in Proceedings of the 40th International
Conference on Machine Learning, Honolulu, Hawaii, HI, United States, 2023,
vol. 202, pp. 24020–24044.
ista: 'Markov I, Vladu A, Guo Q, Alistarh D-A. 2023. Quantized distributed training
of large models with convergence guarantees. Proceedings of the 40th International
Conference on Machine Learning. ICML: International Conference on Machine Learning,
PMLR, vol. 202, 24020–24044.'
mla: Markov, Ilia, et al. “Quantized Distributed Training of Large Models with Convergence
Guarantees.” Proceedings of the 40th International Conference on Machine Learning,
vol. 202, ML Research Press, 2023, pp. 24020–44.
short: I. Markov, A. Vladu, Q. Guo, D.-A. Alistarh, in:, Proceedings of the 40th
International Conference on Machine Learning, ML Research Press, 2023, pp. 24020–24044.
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-04-07T13:00:54Z
day: '30'
department:
- _id: DaAl
ec_funded: 1
external_id:
arxiv:
- '2302.02390'
intvolume: ' 202'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2302.02390
month: '07'
oa: 1
oa_version: Preprint
page: 24020-24044
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: '17490'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Quantized distributed training of large models with convergence guarantees
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-04-07T13:30:20Z
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: '13053'
abstract:
- lang: eng
text: 'Deep neural networks (DNNs) often have to be compressed, via pruning and/or
quantization, before they can be deployed in practical settings. In this work
we propose a new compression-aware minimizer dubbed CrAM that modifies the optimization
step in a principled way, in order to produce models whose local loss behavior
is stable under compression operations such as pruning. Thus, dense models trained
via CrAM should be compressible post-training, in a single step, without significant
accuracy loss. Experimental results on standard benchmarks, such as residual networks
for ImageNet classification and BERT models for language modelling, show that
CrAM produces dense models that can be more accurate than the standard SGD/Adam-based
baselines, but which are stable under weight pruning: specifically, we can prune
models in one-shot to 70-80% sparsity with almost no accuracy loss, and to 90%
with reasonable (∼1%) accuracy loss, which is competitive with gradual compression
methods. Additionally, CrAM can produce sparse models which perform well for transfer
learning, and it also works for semi-structured 2:4 pruning patterns supported
by GPU hardware. The code for reproducing the results is available at this https
URL .'
acknowledged_ssus:
- _id: ScienComp
acknowledgement: "AP, EK, DA received funding from the European Research Council (ERC)
under the European\r\nUnion’s Horizon 2020 research and innovation programme (grant
agreement No 805223 ScaleML). AV acknowledges the support of the French Agence Nationale
de la Recherche (ANR), under grant ANR-21-CE48-0016 (project COMCOPT). We further
acknowledge the support from the Scientific Service Units (SSU) of ISTA through
resources provided by Scientific Computing (SciComp)."
article_processing_charge: No
arxiv: 1
author:
- first_name: Elena-Alexandra
full_name: Peste, Elena-Alexandra
id: 32D78294-F248-11E8-B48F-1D18A9856A87
last_name: Peste
- first_name: Adrian
full_name: Vladu, Adrian
last_name: Vladu
- first_name: Eldar
full_name: Kurtic, Eldar
id: 47beb3a5-07b5-11eb-9b87-b108ec578218
last_name: Kurtic
- 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
citation:
ama: 'Krumes A, Vladu A, Kurtic E, Lampert C, Alistarh D-A. CrAM: A Compression-Aware
Minimizer. In: 11th International Conference on Learning Representations .
OpenReview; 2023.'
apa: 'Krumes, A., Vladu, A., Kurtic, E., Lampert, C., & Alistarh, D.-A. (2023).
CrAM: A Compression-Aware Minimizer. In 11th International Conference on Learning
Representations . Kigali, Rwanda : OpenReview.'
chicago: 'Krumes, Alexandra, Adrian Vladu, Eldar Kurtic, Christoph Lampert, and
Dan-Adrian Alistarh. “CrAM: A Compression-Aware Minimizer.” In 11th International
Conference on Learning Representations . OpenReview, 2023.'
ieee: 'A. Krumes, A. Vladu, E. Kurtic, C. Lampert, and D.-A. Alistarh, “CrAM: A
Compression-Aware Minimizer,” in 11th International Conference on Learning
Representations , Kigali, Rwanda , 2023.'
ista: 'Krumes A, Vladu A, Kurtic E, Lampert C, Alistarh D-A. 2023. CrAM: A Compression-Aware
Minimizer. 11th International Conference on Learning Representations . ICLR: International
Conference on Learning Representations.'
mla: 'Krumes, Alexandra, et al. “CrAM: A Compression-Aware Minimizer.” 11th International
Conference on Learning Representations , OpenReview, 2023.'
short: A. Krumes, A. Vladu, E. Kurtic, C. Lampert, D.-A. Alistarh, in:, 11th International
Conference on Learning Representations , OpenReview, 2023.
conference:
end_date: 2023-05-05
location: 'Kigali, Rwanda '
name: 'ICLR: International Conference on Learning Representations'
start_date: 2023-05-01
corr_author: '1'
date_created: 2023-05-23T11:36:18Z
date_published: 2023-05-01T00:00:00Z
date_updated: 2026-04-07T13:30:19Z
day: '01'
ddc:
- '000'
department:
- _id: GradSch
- _id: DaAl
- _id: ChLa
ec_funded: 1
external_id:
arxiv:
- '2207.14200'
file:
- access_level: open_access
checksum: a6eec897e13a91cdc3eeaf309801752c
content_type: application/pdf
creator: dernst
date_created: 2024-07-22T09:09:45Z
date_updated: 2024-07-22T09:09:45Z
file_id: '17294'
file_name: 2023_ICLR_Peste.pdf
file_size: 458201
relation: main_file
success: 1
file_date_updated: 2024-07-22T09:09:45Z
has_accepted_license: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://openreview.net/pdf?id=_eTZBs-yedr
month: '05'
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: '11th International Conference on Learning Representations '
publication_status: published
publisher: OpenReview
quality_controlled: '1'
related_material:
link:
- relation: software
url: https://github.com/IST-DASLab/CrAM
record:
- id: '13074'
relation: dissertation_contains
status: public
status: public
title: 'CrAM: A Compression-Aware Minimizer'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...
---
_id: '14771'
abstract:
- lang: eng
text: Pruning—that is, setting a significant subset of the parameters of a neural
network to zero—is one of the most popular methods of model compression. Yet,
several recent works have raised the issue that pruning may induce or exacerbate
bias in the output of the compressed model. Despite existing evidence for this
phenomenon, the relationship between neural network pruning and induced bias is
not well-understood. In this work, we systematically investigate and characterize
this phenomenon in Convolutional Neural Networks for computer vision. First, we
show that it is in fact possible to obtain highly-sparse models, e.g. with less
than 10% remaining weights, which do not decrease in accuracy nor substantially
increase in bias when compared to dense models. At the same time, we also find
that, at higher sparsities, pruned models exhibit higher uncertainty in their
outputs, as well as increased correlations, which we directly link to increased
bias. We propose easy-to-use criteria which, based only on the uncompressed model,
establish whether bias will increase with pruning, and identify the samples most
susceptible to biased predictions post-compression. Our code can be found at https://github.com/IST-DASLab/pruned-vision-model-bias.
acknowledgement: The authors would like to sincerely thank Sara Hooker for her feedback
during the development of this work. EI was supported in part by the FWF DK VGSCO,
grant agreement number W1260-N35. AP and DA acknowledge generous ERC support, 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: 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, Alistarh D-A. Bias in pruned vision models: In-depth
analysis and countermeasures. In: 2023 IEEE/CVF Conference on Computer Vision
and Pattern Recognition. IEEE; 2023:24364-24373. doi:10.1109/cvpr52729.2023.02334'
apa: 'Iofinova, E. B., Krumes, A., & Alistarh, D.-A. (2023). Bias in pruned
vision models: In-depth analysis and countermeasures. In 2023 IEEE/CVF Conference
on Computer Vision and Pattern Recognition (pp. 24364–24373). Vancouver, BC,
Canada: IEEE. https://doi.org/10.1109/cvpr52729.2023.02334'
chicago: 'Iofinova, Eugenia B, Alexandra Krumes, and Dan-Adrian Alistarh. “Bias
in Pruned Vision Models: In-Depth Analysis and Countermeasures.” In 2023 IEEE/CVF
Conference on Computer Vision and Pattern Recognition, 24364–73. IEEE, 2023.
https://doi.org/10.1109/cvpr52729.2023.02334.'
ieee: 'E. B. Iofinova, A. Krumes, and D.-A. Alistarh, “Bias in pruned vision models:
In-depth analysis and countermeasures,” in 2023 IEEE/CVF Conference on Computer
Vision and Pattern Recognition, Vancouver, BC, Canada, 2023, pp. 24364–24373.'
ista: 'Iofinova EB, Krumes A, Alistarh D-A. 2023. Bias in pruned vision models:
In-depth analysis and countermeasures. 2023 IEEE/CVF Conference on Computer Vision
and Pattern Recognition. CVPR: Conference on Computer Vision and Pattern Recognition,
24364–24373.'
mla: 'Iofinova, Eugenia B., et al. “Bias in Pruned Vision Models: In-Depth Analysis
and Countermeasures.” 2023 IEEE/CVF Conference on Computer Vision and Pattern
Recognition, IEEE, 2023, pp. 24364–73, doi:10.1109/cvpr52729.2023.02334.'
short: E.B. Iofinova, A. Krumes, D.-A. Alistarh, in:, 2023 IEEE/CVF Conference on
Computer Vision and Pattern Recognition, IEEE, 2023, pp. 24364–24373.
conference:
end_date: 2023-06-24
location: Vancouver, BC, Canada
name: 'CVPR: Conference on Computer Vision and Pattern Recognition'
start_date: 2023-06-17
corr_author: '1'
date_created: 2024-01-10T08:42:40Z
date_published: 2023-08-22T00:00:00Z
date_updated: 2026-05-19T11:20:27Z
day: '22'
department:
- _id: DaAl
- _id: ChLa
doi: 10.1109/cvpr52729.2023.02334
ec_funded: 1
external_id:
arxiv:
- '2304.12622'
isi:
- '001062531308068'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2304.12622
month: '08'
oa: 1
oa_version: Preprint
page: 24364-24373
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: 2023 IEEE/CVF Conference on Computer Vision and Pattern Recognition
publication_identifier:
eisbn:
- '9798350301298'
eissn:
- 2575-7075
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
link:
- relation: software
url: https://github.com/IST-DASLab/pruned-vision-model-bias
record:
- id: '21854'
relation: dissertation_contains
status: public
status: public
title: 'Bias in pruned vision models: In-depth analysis and countermeasures'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...