Decentralised convex optimisation with probability-proportional-to-size quantization
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917906812502016 |
|---|---|
| author | Pasechniuk, Dmitrii Dvurechensky, Pavel Uribe, César A. Gasnikov, Alexander |
| author_facet | Pasechniuk, Dmitrii Dvurechensky, Pavel Uribe, César A. Gasnikov, Alexander |
| contents | Communication is one of the bottlenecks of distributed optimisation and learning. To overcome this bottleneck, we propose a novel quantization method that transforms a vector into a sample of components' indices drawn from a categorical distribution with probabilities proportional to values at those components. Then, we propose a primal and a primal-dual accelerated stochastic gradient methods that use our proposed quantization, and derive their convergence rates in terms of probabilities of large deviations. We focus on affine-constrained convex optimisation and its application to decentralised distributed optimisation problems. To illustrate the work of our algorithm, we apply it to the decentralised computation of semi-discrete entropy regularized Wasserstein barycenters. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_18312 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Decentralised convex optimisation with probability-proportional-to-size quantization Pasechniuk, Dmitrii Dvurechensky, Pavel Uribe, César A. Gasnikov, Alexander Optimization and Control 65K10 G.1.6 Communication is one of the bottlenecks of distributed optimisation and learning. To overcome this bottleneck, we propose a novel quantization method that transforms a vector into a sample of components' indices drawn from a categorical distribution with probabilities proportional to values at those components. Then, we propose a primal and a primal-dual accelerated stochastic gradient methods that use our proposed quantization, and derive their convergence rates in terms of probabilities of large deviations. We focus on affine-constrained convex optimisation and its application to decentralised distributed optimisation problems. To illustrate the work of our algorithm, we apply it to the decentralised computation of semi-discrete entropy regularized Wasserstein barycenters. |
| title | Decentralised convex optimisation with probability-proportional-to-size quantization |
| topic | Optimization and Control 65K10 G.1.6 |
| url | https://arxiv.org/abs/2501.18312 |