On the convergence analysis of the decentralized projected gradient descent method
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929339792097280 |
|---|---|
| author | Choi, Woocheol Kim, Jimyeong |
| author_facet | Choi, Woocheol Kim, Jimyeong |
| contents | In this work, we are concerned with the decentralized optimization problem: \begin{equation*} \min_{x \in Ω}~f(x) = \frac{1}{n} \sum_{i=1}^n f_i (x), \end{equation*} where $Ω\subset \mathbb{R}^d$ is a convex domain and each $f_i : Ω\rightarrow \mathbb{R}$ is a local cost function only known to agent $i$. A fundamental algorithm is the decentralized projected gradient method (DPG) given by \begin{equation*}
x_i(t+1)=\mathcal{P}_Ω\Big[\sum^n_{j=1}w_{ij} x_j(t) -α(t)\nabla f_i(x_i(t))\Big] \end{equation*} where $\mathcal{P}_Ω$ is the projection operator to $Ω$ and $ \{w_{ij}\}_{1\leq i,j \leq n}$ are communication weight among the agents. While this method has been widely used in the literature, its convergence property has not been established so far, except for the special case $Ω= \mathbb{R}^n$. This work establishes new convergence estimates of DPG when the aggregate cost $f$ is strongly convex and each function $f_i$ is smooth. If the stepsize is given by constant $α(t) \equivα>0$ and suitably small, we prove that each $x_i (t)$ converges to an $O(\sqrtα)$-neighborhood of the optimal point. In addition, we further improve the convergence result by showing that the point $x_i (t)$ converges to an $O(α)$-neighborhood of the optimal point if the domain is given the half-space $\mathbb{R}^{d-1}\times \mathbb{R}_{+}$ for any dimension $d\in \mathbb{N}$. Also, we obtain new convergence results for decreasing stepsizes. Numerical experiments are provided to support the convergence results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_08412 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the convergence analysis of the decentralized projected gradient descent method Choi, Woocheol Kim, Jimyeong Optimization and Control Systems and Control In this work, we are concerned with the decentralized optimization problem: \begin{equation*} \min_{x \in Ω}~f(x) = \frac{1}{n} \sum_{i=1}^n f_i (x), \end{equation*} where $Ω\subset \mathbb{R}^d$ is a convex domain and each $f_i : Ω\rightarrow \mathbb{R}$ is a local cost function only known to agent $i$. A fundamental algorithm is the decentralized projected gradient method (DPG) given by \begin{equation*} x_i(t+1)=\mathcal{P}_Ω\Big[\sum^n_{j=1}w_{ij} x_j(t) -α(t)\nabla f_i(x_i(t))\Big] \end{equation*} where $\mathcal{P}_Ω$ is the projection operator to $Ω$ and $ \{w_{ij}\}_{1\leq i,j \leq n}$ are communication weight among the agents. While this method has been widely used in the literature, its convergence property has not been established so far, except for the special case $Ω= \mathbb{R}^n$. This work establishes new convergence estimates of DPG when the aggregate cost $f$ is strongly convex and each function $f_i$ is smooth. If the stepsize is given by constant $α(t) \equivα>0$ and suitably small, we prove that each $x_i (t)$ converges to an $O(\sqrtα)$-neighborhood of the optimal point. In addition, we further improve the convergence result by showing that the point $x_i (t)$ converges to an $O(α)$-neighborhood of the optimal point if the domain is given the half-space $\mathbb{R}^{d-1}\times \mathbb{R}_{+}$ for any dimension $d\in \mathbb{N}$. Also, we obtain new convergence results for decreasing stepsizes. Numerical experiments are provided to support the convergence results. |
| title | On the convergence analysis of the decentralized projected gradient descent method |
| topic | Optimization and Control Systems and Control |
| url | https://arxiv.org/abs/2303.08412 |