Accelerated, Parallel and Proximal Coordinate Descent

par Olivier Fercoq (School of Mathematics, University of Edinburgh - United Kingdom)

jeudi 27 mars 2014, 14:00 → 15:00 Europe/Paris

203 (XLIM)

We propose a new stochastic coordinate descent method for minimizing the sum of convex functions each of which depends on a small number of coordinates only. Our method (APPROX) is simultaneously Accelerated, Parallel and PROXimal; this is the first time such a method is proposed. The method converges at a rate O(1/k^2), where k is the iteration counter. We show that the method can be implemented without the need to perform full-dimensional vector operations, which is considered to be the major bottleneck of accelerated coordinate descent.