On the Complexity of Finite-Sum Smooth Optimization under the Polyak-Lojasiewicz Condition

This paper considers the optimization problem of the form min_bf x∈mathbb Rd f(bf x)triangleq frac1nsumi=1n fi(bf x), where f(·) satisfies the Polyak--Lojasiewicz (PL) condition with parameter μ and fi(·)i=1n is L-mean-squared smooth. We show that any gradient method requires at least Omega(n+kappa√nlog(1/ε)) incremental first-order oracle (IFO) calls to find an ε-suboptimal solution, where kappatriangleq L/μ is the condition number of the problem. This result nearly matches upper bounds of IFO complexity for best-known first-order methods. We also study the problem of minimizing the PL function in the distributed setting such that the individuals f1(·),dots,fn(·) are located on a connected network of n agents. We provide lower bounds of Omega(kappa/√γ,log(1/ε)), Omega((kappa+τkappa/√γ,)log(1/ε)) and Omegabig(n+kappa√nlog(1/ε)big) for communication rounds, time cost and local first-order oracle calls respectively, where γ∈(0,1] is the spectral gap of the mixing matrix associated with the network and~τ>0 is the time cost of per communication round. Furthermore, we propose a decentralized first-order method that nearly matches above lower bounds in expectation.