### Peter Richtarik (University of Edinburgh)

#### Approximate level method

*Wednesday 30 September 2009 at 15.30, JCMB 6206*

##### Abstract

In this paper we propose and analyze a variant of the level method, which is
an algorithm for minimizing nonsmooth convex functions. Level method enjoys
optimal iteration complexity and is practical for large-scale problems when
it is hard or impossible to utilize the structure of the objective function
for speedup. The main per-iteration work is spent on 1) minimizing a
piecewise-linear model of the objective function and on 2) projecting onto
the intersection of the feasible region and a polyhedron arising as a level
set of the model. We show that by replacing exact computations in both cases
by approximate ones, in relative scale, the number of iterations needed to
obtain a solution of any fixed accuracy increases only by the factor of four.
This means that it is in principle possible to retain the optimal theoretical
properties of the algorithm while spending less work on solving the
subproblems.

### Seminars by year

*Current*
*2016*
*2015*
*2014*
*2013*
*2012*
*2011*
*2010*
*2009*
*2008*
*2007*
*2006*
*2005*
*2004*
*2003*
*2002*
*2001*
*2000*
*1999*
*1998*
*1997*
*1996*