Efficiency of minimizing compositions of convex functions and smooth maps.

We consider global efficiency of algorithms for minimizing a sum of a convex function and a composition of a Lipschitz convex function with a smooth map. The basic algorithm we rely on is the prox-linear method, which in each iteration solves a regularized subproblem formed by linearizing the smooth map. When the subproblems are solved exactly, the method has efficiency O (ε - 2) , akin to gradient descent for smooth minimization. We show that when the subproblems can only be solved by first-order methods, a simple combination of smoothing, the prox-linear method, and a fast-gradient scheme yields an algorithm with complexity O ~ (ε - 3) . We round off the paper with an inertial prox-linear method that automatically accelerates in presence of convexity. [ABSTRACT FROM AUTHOR]