Decentralized Constrained Optimization: Double Averaging and Gradient Projection

TLDR

This paper proposes a novel decentralized projected gradient scheme based on local averaging and proves its convergence using only local functions’ smoothness, and demonstrates the effectiveness of this method in both constrained and unconstrained problems.

Abstract

In this paper, we consider the convex, finite-sum minimization problem with explicit convex constraints over strongly connected directed graphs. The constraint is an intersection of several convex sets each being known to only one node. To solve this problem, we propose a novel decentralized projected gradient scheme based on local averaging and prove its convergence using only local functions’ smoothness. Experimental studies demonstrate the effectiveness of the proposed method in both constrained and unconstrained problems.