Olivier Fercoq (University of Edinburgh)

Smooth minimization of nonsmooth functions by parallel coordinate descent
Wednesday 27 February 2013 at 15.30, JCMB 6206


In this talk, we first show that coordinate descent methods can be efficiently applied to the optimization of nonsmooth convex functions with explicit max-structure. We derive a quadratic separable overapproximation of the smoothed function obtained by Nesterov's smoothing and from it we derive the iteration complexity of the Parallel Coordinate Descent Method applied to this class of functions.

In a second part, we compare the Parallel Coordinate Descent Method with the Monte Carlo approach, where we launch several times the serial randomized coordinate descent method in order to reduce the variance of the random process describing the value of the function. Using the theoretical iteration complexity, we show that, depending on the problem at stake, both approaches may be competitive, or that a nested parallelism may be better.

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