On the Convergence Analysis of the Decentralized Projected Gradient Descent Method
Woocheol Choi, Jimyeong Kim · SIAM Journal on Optimization · 2025
Abstract. In this work, we are concerned with the decentralized optimization problem: [Formula: see text] where [Formula: see text] is a convex domain and each [Formula: see text] is a local cost function only known to agent [Formula: see text]. A fundamental algorithm for this problem is the decentralized projected gradient method (DPG) given by [Formula: see text] where [Formula: see text] is the projection operator to [Formula: see text] and [Formula: see text] 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 [Formula: see text]. This work establishes new convergence estimates of DPG when the aggregate cost [Formula: see text] is strongly convex and each function [Formula: see text] is smooth. If the stepsize [Formula: see text] is suitably small, we prove that each [Formula: see text] converges linearly to an [Formula: see text]-neighborhood of the minimizer. In addition, we further improve the convergence result by showing that the point [Formula: see text] converges linearly to an [Formula: see text]-neighborhood of the minimizer if the domain is given by the half-space [Formula: see text] for any dimension [Formula: see text]. Numerical experiments are provided to support the convergence results.