Gradient sliding for composite optimization

详细信息    查看全文

• 作者：Guanghui Lan
• 刊名：Mathematical Programming
• 出版年：2016
• 出版时间：September 2016
• 年：2016
• 卷：159
• 期：1-2
• 页码：201-235
• 全文大小：694 KB
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Calculus of Variations and Optimal Control
  Mathematics of Computing
  Numerical Analysis
  Combinatorics
  Mathematical and Computational Physics
  Mathematical Methods in Physics
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1436-4646
• 卷排序：159

文摘

We consider in this paper a class of composite optimization problems whose objective function is given by the summation of a general smooth and nonsmooth component, together with a relatively simple nonsmooth term. We present a new class of first-order methods, namely the gradient sliding algorithms, which can skip the computation of the gradient for the smooth component from time to time. As a consequence, these algorithms require only \(\mathcal{O}(1/\sqrt{\epsilon })\) gradient evaluations for the smooth component in order to find an \(\epsilon \)-solution for the composite problem, while still maintaining the optimal \(\mathcal{O}(1/\epsilon ^2)\) bound on the total number of subgradient evaluations for the nonsmooth component. We then present a stochastic counterpart for these algorithms and establish similar complexity bounds for solving an important class of stochastic composite optimization problems. Moreover, if the smooth component in the composite function is strongly convex, the developed gradient sliding algorithms can significantly reduce the number of graduate and subgradient evaluations for the smooth and nonsmooth component to \(\mathcal{O} (\log (1/\epsilon ))\) and \(\mathcal{O}(1/\epsilon )\), respectively. Finally, we generalize these algorithms to the case when the smooth component is replaced by a nonsmooth one possessing a certain bi-linear saddle point structure.KeywordsConvex programmingComplexityGradient sliding Nesterov’s methodData analysis