### Martin Takáč and Jakub Marecek (University of Edinburgh)

#### First-order (gradient) methods for solving structured convex problems

*Tuesday 13 March 2012 at 16.00, JCMB 5215*

##### Abstract

First-order methods have in the last 5 years become immensely popular due to
their ability to solve structured convex optimization problems of very high
dimensions, low memory demands and relative simplicity with which they can be
implemented. In this reading seminar the speakers will discuss, in detail, two
of the several fundamental papers in the area. Both papers were a breakthrough
in the complexity and practical efficiency of gradient algorithms for nonsmooth
convex problems of special structure.

In the first paper it was shown that (nonsmooth convex) problems of
saddle-point structure can be solved in O(1/ε) iterations; using a
novel smoothing technique, which is an order-of-magnitude improvement over the
black-box model optimal complexity of O(1/ε^{2}).

The second paper shows that (nonsmooth convex) problems of composite structure,
where the objective function is the sum of a smooth convex and a 'simple'
nonsmooth convex function, can be effectively treated as smooth problems;
i.e., they can be solved in O(1/sqrt(ε)) iterations.

It is recommended that attendees prepare by reading the papers.

- Y. Nesterov. Smooth minimization of non-smooth functions.
Mathematical Programming, 103 (1): 127–152, 2005.

- Y. Nesterov. Gradient methods for minimizing composite objective
function. 2007.