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