On the Complexity of Decentralized Smooth Nonconvex Finite-Sum Optimization

We study the decentralized optimization problem min_bf x∈mathbb Rd f(bf x)triangleq frac1msumi=1m fi(bf x), where the local function on the i-th agent has the form of fi(bf x)triangleq frac1nsumj=1n fi,j(bf x) and every individual fi,j is smooth but possibly nonconvex. We propose a stochastic algorithm called DEcentralized probAbilistic Recursive gradiEnt deScenT (DEAREST) method, which achieves an ε-stationary point at each agent with the communication rounds of tildemathcal O(Lε-2/√γ,), the computation rounds of tildemathcal O(n+(L+minnL, √n/mbar L)ε-2), and the local incremental first-oracle calls of mathcal O(mn + minmnL, √mnbar Lε-2), where L is the smoothness parameter of the objective function, bar L is the mean-squared smoothness parameter of all individual functions, and γ is the spectral gap of the mixing matrix associated with the network. We then establish the lower bounds to show that the proposed method is near-optimal. Notice that the smoothness parameters L and bar L used in our algorithm design and analysis are global, leading to sharper complexity bounds than existing results that depend on the local smoothness. We further extend DEAREST to solve the decentralized finite-sum optimization problem under the Polyak-Lojasiewicz condition, also achieving the near-optimal complexity bounds.