Treffer: On the Convergence Analysis of the Decentralized Projected Gradient Descent Method.

In this work, we are concerned with the decentralized optimization problem: \(\min_{x \in \Omega }{}f(x) = \frac {1}{n} \sum_{i=1}^n f_i (x), \) where \(\Omega \subset \mathbb{R}^d\) is a convex domain and each \(f_i : \Omega \rightarrow \mathbb{R}\) is a local cost function only known to agent \(i\). A fundamental algorithm for this problem is the decentralized projected gradient method (DPG) given by \(x_i(t+1)=\mathcal{P}_\Omega [\sum^n_{j=1}w_{ij} x_j(t) -\alpha \nabla f_i(x_i(t)) ] \) where \(\mathcal{P}_{\Omega }\) is the projection operator to \(\Omega\) 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 \(\Omega = \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 \(\alpha \gt 0\) is suitably small, we prove that each \(x_i (t)\) converges linearly to an \(O(\sqrt {\alpha })\) -neighborhood of the minimizer. In addition, we further improve the convergence result by showing that the point \(x_i (t)\) converges linearly to an \(O(\alpha)\) -neighborhood of the minimizer if the domain is given by the half-space \(\mathbb{R}^{d-1}\times \mathbb{R}_{+}\) for any dimension \(d\in \mathbb{N}\). Numerical experiments are provided to support the convergence results. [ABSTRACT FROM AUTHOR]

Copyright of SIAM Journal on Optimization is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)