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