Efficiency of minimizing compositions of convex functions and smooth maps
Efficiency of minimizing compositions of convex functions and smooth maps
复制标题
DOI：
10.1007/s10107-018-1311-3
复制
发表时间：
2019-11-01
影响因子：
2.7
通讯作者：
Paquette, C.
中科院分区：
文献类型：
--
作者：
Drusvyatskiy, D.;Paquette, C.
我们考虑用于最小化一个凸函数以及一个李普希茨凸函数与一个光滑映射的复合函数之和的算法的全局效率。我们所依赖的基本算法是近似线性方法，该方法在每次迭代中求解一个通过将光滑映射线性化而形成的正则化子问题。当子问题被精确求解时，该方法具有$O(\epsilon^{-2})$的效率，类似于光滑最小化的梯度下降法。我们表明，当子问题只能通过一阶方法求解时，平滑、近似线性方法和快速梯度方案的一种简单组合产生一种具有$\tilde{O}(\epsilon^{-3})$复杂度的算法。我们用一种惯性近似线性方法结束本文，该方法在凸性存在的情况下自动加速。
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(epsilon(-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) over tilde(epsilon(-3)). We round off the paper with an inertial prox-linear method that automatically accelerates in presence of convexity.