A General Analysis Framework of Lower Complexity Bounds for Finite-Sum Optimization

Guangzeng Xie, Luo Luo, Zhihua Zhang

This paper studies the lower bound complexity for the optimization problem whose objective function is the average of $n$ individual smooth convex functions. We consider the algori…