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


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.

  1. Y. Nesterov. Smooth minimization of non-smooth functions. Mathematical Programming, 103 (1): 127–152, 2005.
  2. Y. Nesterov. Gradient methods for minimizing composite objective function. 2007.