On the Optimal Lower and Upper Complexity Bounds for a Class of Composite Optimization Problems

Zhenyuan Zhu, Fan Chen, Junyu Zhang +1

We study the optimal lower and upper complexity bounds for finding approximate solutions to the composite problem ${\min }_{x}f(x)+h(Ax-b)$, where $f$ is smooth and $h$ is convex. Giv…