This paper considers the optimization problem of the form $\min_{ { \bf x}\in{ \mathbb R}^d} f({ \bf x})\triangleq \frac{ 1}{ n}\sum_{ i=1}^n f_i({ \bf x})$, where $f(\cdot)$ satisfies the Polyak--{ \L}ojasiewicz (PL) condition with parameter $\mu$ and $\{ f_i(\cdot)\}_{ i=1}^n$ is $L$-mean-squared smooth. We show that any gradient method requires at least $\Omega(n+\kappa\sqrt{ n}\log(1/\epsilon))$ incremental first-order oracle (IFO) calls to find an $\epsilon$-suboptimal solution, where $\kappa\triangleq L/\mu$ 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 $f_1(\cdot),\dots,f_n(\cdot)$ are located on a connected network of $n$ agents. We provide lower bounds of $\Omega(\kappa/\sqrt{ \gamma}\,\log(1/\epsilon))$, $\Omega((\kappa+\tau\kappa/\sqrt{ \gamma}\,)\log(1/\epsilon))$ and $\Omega\big(n+\kappa\sqrt{ n}\log(1/\epsilon)\big)$ for communication rounds, time cost and local first-order oracle calls respectively, where $\gamma\in(0,1]$ is the spectral gap of the mixing matrix associated with the network and~$\tau>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.
Categories: math.OC cs.LG