Approximate level method<BR>

<p>
Peter Richtarik, CORE<BR>

<P>
Abstract:<BR>
In this paper we propose and analyze a variant of the 
<font color="blue">level method</font>,
which is an algorithm for minimizing nonsmooth convex functions.
The main work per iteration is spent on 1) minimizing a
piecewise-linear model of the objective function and on 2)
projecting onto a polyhedron arising as a level set of the
model. We show that by replacing exact computations in both cases by
<font color="blue">approximate computations</font>, in 
<font color="blue">relative scale</font>, the
theoretical iteration complexity increases only by the factor of
four. This means that while spending less work on the subproblems,
the new approach still retains the good theoretical
properties of the algorithm.