Graph Topology Invariant Gradient and Sampling Complexity for Decentralized and Stochastic Optimization
针对约束分散式多智能体优化问题，提出梯度与采样复杂度不依赖图拓扑的算法，同时保持最优通信复杂度，适用于凸光滑确定性与随机梯度问题。
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 -solution with gradient complexity and communication complexity, where is the smoothness parameter of the objective function and 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 and , respectively, with the additional assumption of strong convexity modulus . 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 -solution with sampling complexity, which can be further improved to in the strong convexity case. Here is the variance of the stochastic gradient. The communication complexities of SPDS remain the same as that of the deterministic case.