Bregman Proximal Method for Efficient Communications under Similarity
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910632820867072 |
|---|---|
| author | Beznosikov, Aleksandr Dvinskikh, Darina Bylinkin, Dmitry Semenov, Andrei Gasnikov, Alexander |
| author_facet | Beznosikov, Aleksandr Dvinskikh, Darina Bylinkin, Dmitry Semenov, Andrei Gasnikov, Alexander |
| contents | We propose a novel stochastic distributed method for both monotone and strongly monotone variational inequalities with Lipschitz operator and proper convex regularizers arising in various applications from game theory to adversarial training. By exploiting similarity, our algorithm overcomes the communication bottleneck that is a major issue in distributed optimization. The proposed method enjoys optimal communication complexity. All the existing distributed algorithms achieving the lower bounds under similarity condition essentially utilize the Euclidean setup. In contrast to them, our method is built upon the Bregman proximal maps and it is compatible with an arbitrary problem geometry. Thereby the proposed method fills an existing gap in this area of research. Our theoretical results are confirmed by numerical experiments on a stochastic matrix game. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_06953 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Bregman Proximal Method for Efficient Communications under Similarity Beznosikov, Aleksandr Dvinskikh, Darina Bylinkin, Dmitry Semenov, Andrei Gasnikov, Alexander Optimization and Control We propose a novel stochastic distributed method for both monotone and strongly monotone variational inequalities with Lipschitz operator and proper convex regularizers arising in various applications from game theory to adversarial training. By exploiting similarity, our algorithm overcomes the communication bottleneck that is a major issue in distributed optimization. The proposed method enjoys optimal communication complexity. All the existing distributed algorithms achieving the lower bounds under similarity condition essentially utilize the Euclidean setup. In contrast to them, our method is built upon the Bregman proximal maps and it is compatible with an arbitrary problem geometry. Thereby the proposed method fills an existing gap in this area of research. Our theoretical results are confirmed by numerical experiments on a stochastic matrix game. |
| title | Bregman Proximal Method for Efficient Communications under Similarity |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2311.06953 |