Decentralized Finite-Sum Optimization over Time-Varying Networks
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916601677217792 |
|---|---|
| author | Metelev, Dmitry Chezhegov, Savelii Rogozin, Alexander Beznosikov, Aleksandr Sholokhov, Alexander Gasnikov, Alexander Kovalev, Dmitry |
| author_facet | Metelev, Dmitry Chezhegov, Savelii Rogozin, Alexander Beznosikov, Aleksandr Sholokhov, Alexander Gasnikov, Alexander Kovalev, Dmitry |
| contents | We consider decentralized time-varying stochastic optimization problems where each of the functions held by the nodes has a finite sum structure. Such problems can be efficiently solved using variance reduction techniques. Our aim is to explore the lower complexity bounds (for communication and number of stochastic oracle calls) and find optimal algorithms. The paper studies strongly convex and nonconvex scenarios. To the best of our knowledge, variance reduced schemes and lower bounds for time-varying graphs have not been studied in the literature. For nonconvex objectives, we obtain lower bounds and develop an optimal method GT-PAGE. For strongly convex objectives, we propose the first decentralized time-varying variance-reduction method ADOM+VR and establish lower bound in this scenario, highlighting the open question of matching the algorithms complexity and lower bounds even in static network case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_02490 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Decentralized Finite-Sum Optimization over Time-Varying Networks Metelev, Dmitry Chezhegov, Savelii Rogozin, Alexander Beznosikov, Aleksandr Sholokhov, Alexander Gasnikov, Alexander Kovalev, Dmitry Optimization and Control We consider decentralized time-varying stochastic optimization problems where each of the functions held by the nodes has a finite sum structure. Such problems can be efficiently solved using variance reduction techniques. Our aim is to explore the lower complexity bounds (for communication and number of stochastic oracle calls) and find optimal algorithms. The paper studies strongly convex and nonconvex scenarios. To the best of our knowledge, variance reduced schemes and lower bounds for time-varying graphs have not been studied in the literature. For nonconvex objectives, we obtain lower bounds and develop an optimal method GT-PAGE. For strongly convex objectives, we propose the first decentralized time-varying variance-reduction method ADOM+VR and establish lower bound in this scenario, highlighting the open question of matching the algorithms complexity and lower bounds even in static network case. |
| title | Decentralized Finite-Sum Optimization over Time-Varying Networks |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2402.02490 |