Graph Topology Invariant Gradient and Sampling Complexity for Decentralized and Stochastic Optimization
Guanghui Lan, Yuyuan Ouyang, Yi Zhou · SIAM Journal on Optimization · 2023
Abstract. One fundamental problem in constrained decentralized multiagent optimization is the trade-off between gradient/sampling complexity and communication complexity. In this paper, we propose new algorithms whose gradient and sampling complexities are graph topology invariant, while their communication complexities remain optimal. Specifically, for convex smooth deterministic problems, we propose a primal-dual sliding (PDS) algorithm that is able to compute an [Formula: see text]-solution with [Formula: see text] gradient complexity and [Formula: see text] communication complexity, where [Formula: see text] is the smoothness parameter of the objective function and [Formula: see text] is related to either the graph Laplacian or the transpose of the oriented incidence matrix of the communication network. The complexities can be further improved to [Formula: see text] and [Formula: see text], respectively, with the additional assumption of strong convexity modulus [Formula: see text]. We also propose a stochastic variant, namely, the stochastic primal-dual sliding (SPDS) algorithm, for convex smooth problems with stochastic gradients. The SPDS algorithm utilizes the minibatch technique and enables the agents to perform sampling and communication simultaneously. It computes a stochastic [Formula: see text]-solution with [Formula: see text] sampling complexity, which can be further improved to [Formula: see text] in the strong convexity case. Here [Formula: see text] is the variance of the stochastic gradient. The communication complexities of SPDS remain the same as that of the deterministic case.