Gradient methods for minimizing composite objective function

TLDR

Composite convex optimization problems, where one term is smooth and accessed via a black‑box oracle and the other is simple and known, can be solved efficiently despite the sum’s unfavorable properties. The paper analyzes new methods for solving such composite objective functions. The authors propose primal and dual gradient methods with O(1/k) convergence, an accelerated multistep variant achieving O(1/k²), and efficient line‑search procedures that add only a small constant factor to per‑iteration cost. Preliminary experiments confirm that the accelerated scheme outperforms the other methods.

Abstract

In this paper we analyze several new methods for solving optimization problems with the objective function formed as a sum of two convex terms: one is smooth and given by a black-box oracle, and another is general but simple and its structure is known. Despite to the bad properties of the sum, such problems, both in convex and nonconvex cases, can be solved with eciency typical for the good part of the objective. For convex problems of the above structure, we consider primal and dual variants of the gradient method (converge as O ‡ 1 k · ), and an accelerated multistep version with convergence rate O ‡ 1 k2 · , where k is the iteration counter. For all methods, we suggest some ecient “line search” procedures and show that the additional computational work necessary for estimating the unknown problem class parameters can only multiply the complexity of each iteration by a small constant factor. We present also the results of preliminary computational experiments, which confirm the superiority of the accelerated scheme.