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.
