Peter Richtarik (University of Edinburgh)

Approximate level method
Wednesday 30 September 2009 at 15.30, JCMB 6206


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