Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2412.13054 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910185999564800 |
|---|---|
| author | Huang, Kun Pu, Shi Nedić, Angelia |
| author_facet | Huang, Kun Pu, Shi Nedić, Angelia |
| contents | Consider $n$ agents connected over a network collaborating to minimize the average of their local cost functions combined with a common nonsmooth function. This paper introduces a unified algorithmic framework for solving such a problem through distributed stochastic proximal gradient methods, leveraging the normal map update scheme. Within this framework, we propose two new algorithms, termed Normal Map-based Distributed Stochastic Gradient Tracking (norM-DSGT) and Normal Map-based Exact Diffusion (norM-ED). We demonstrate that both methods can asymptotically achieve comparable convergence rates to the centralized stochastic proximal gradient descent method under a general variance condition on the stochastic gradients. Additionally, the number of iterations required for norM-ED to achieve such a rate (i.e., the transient time) behaves as $\mathcal{O}(n^{3}/(1-λ)^2)$ for minimizing composite objective functions, matching the performance of the non-proximal ED algorithm. Here $1-λ$ denotes the spectral gap of the mixing matrix related to the underlying network topology. To our knowledge, such a convergence result is state-of-the-art for the considered composite problem. Under the same condition, norM-DSGT enjoys a transient time of $\mathcal{O}(\max\{n^3/(1-λ)^2, n/(1-λ)^3\})$, which matches that of the non-proximal DSGT algorithm and norM-ED under the condition $(1-λ)^{-1}=\mathcal{O}(n^{2})$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_13054 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Distributed Normal Map-based Stochastic Proximal Gradient Methods over Networks Huang, Kun Pu, Shi Nedić, Angelia Optimization and Control Consider $n$ agents connected over a network collaborating to minimize the average of their local cost functions combined with a common nonsmooth function. This paper introduces a unified algorithmic framework for solving such a problem through distributed stochastic proximal gradient methods, leveraging the normal map update scheme. Within this framework, we propose two new algorithms, termed Normal Map-based Distributed Stochastic Gradient Tracking (norM-DSGT) and Normal Map-based Exact Diffusion (norM-ED). We demonstrate that both methods can asymptotically achieve comparable convergence rates to the centralized stochastic proximal gradient descent method under a general variance condition on the stochastic gradients. Additionally, the number of iterations required for norM-ED to achieve such a rate (i.e., the transient time) behaves as $\mathcal{O}(n^{3}/(1-λ)^2)$ for minimizing composite objective functions, matching the performance of the non-proximal ED algorithm. Here $1-λ$ denotes the spectral gap of the mixing matrix related to the underlying network topology. To our knowledge, such a convergence result is state-of-the-art for the considered composite problem. Under the same condition, norM-DSGT enjoys a transient time of $\mathcal{O}(\max\{n^3/(1-λ)^2, n/(1-λ)^3\})$, which matches that of the non-proximal DSGT algorithm and norM-ED under the condition $(1-λ)^{-1}=\mathcal{O}(n^{2})$. |
| title | Distributed Normal Map-based Stochastic Proximal Gradient Methods over Networks |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2412.13054 |