Average-case optimization analysis for distributed consensus algorithms on regular graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909402432274432 |
|---|---|
| author | Nguyen, Nhat Trung Rogozin, Alexander Gasnikov, Alexander |
| author_facet | Nguyen, Nhat Trung Rogozin, Alexander Gasnikov, Alexander |
| contents | The consensus problem in distributed computing involves a network of agents aiming to compute the average of their initial vectors through local communication, represented by an undirected graph. This paper focuses on the studying of this problem using an average-case analysis approach, particularly over regular graphs. Traditional algorithms for solving the consensus problem often rely on worst-case performance evaluation scenarios, which may not reflect typical performance in real-world applications. Instead, we apply average-case analysis, focusing on the expected spectral distribution of eigenvalues to obtain a more realistic view of performance. Key contributions include deriving the optimal method for consensus on regular graphs, showing its relation to the Heavy Ball method, analyzing its asymptotic convergence rate, and comparing it to various first-order methods through numerical experiments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_00605 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Average-case optimization analysis for distributed consensus algorithms on regular graphs Nguyen, Nhat Trung Rogozin, Alexander Gasnikov, Alexander Optimization and Control Distributed, Parallel, and Cluster Computing The consensus problem in distributed computing involves a network of agents aiming to compute the average of their initial vectors through local communication, represented by an undirected graph. This paper focuses on the studying of this problem using an average-case analysis approach, particularly over regular graphs. Traditional algorithms for solving the consensus problem often rely on worst-case performance evaluation scenarios, which may not reflect typical performance in real-world applications. Instead, we apply average-case analysis, focusing on the expected spectral distribution of eigenvalues to obtain a more realistic view of performance. Key contributions include deriving the optimal method for consensus on regular graphs, showing its relation to the Heavy Ball method, analyzing its asymptotic convergence rate, and comparing it to various first-order methods through numerical experiments. |
| title | Average-case optimization analysis for distributed consensus algorithms on regular graphs |
| topic | Optimization and Control Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2409.00605 |