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

Yunyan Bai, Yuxing Liu, Luo Luo

This paper considers the optimization problem of the form ${\min }_{\mathbf{x}\in {\mathbb{R}}^d}f(\mathbf{x})\triangleq \frac{1}{n}{\sum }_{i=1}^n{f}_i(\mathbf{x})$, where $f(\cdot )$ satisfies the…