  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. Given access to the proximal operator of $h$,
for strongly convex, convex, and nonconvex $f$, we design efficient first order
algorithms with complexities
$\tilde{O}\left(\kappa_A\sqrt{\kappa_f}\log\left(1/{\epsilon}\right)\right)$,
$\tilde{O}\left(\kappa_A\sqrt{L_f}D/\sqrt{\epsilon}\right)$, and
$\tilde{O}\left(\kappa_A L_f\Delta/\epsilon^2\right)$, respectively. Here,
$\kappa_A$ is the condition number of the matrix $A$ in the composition, $L_f$
is the smoothness constant of $f$, and $\kappa_f$ is the condition number of
$f$ in the strongly convex case. $D$ is the initial point distance and $\Delta$
is the initial function value gap. Tight lower complexity bounds for the three
cases are also derived and they match the upper bounds up to logarithmic
factors, thereby demonstrating the optimality of both the upper and lower
bounds proposed in this paper.
