Timezone: »

Smooth Primal-Dual Coordinate Descent Algorithms for Nonsmooth Convex Optimization
Ahmet Alacaoglu · Quoc Tran Dinh · Olivier Fercoq · Volkan Cevher

Mon Dec 04 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #171

We propose a new randomized coordinate descent method for a convex optimization template with broad applications. Our analysis relies on a novel combination of four ideas applied to the primal-dual gap function: smoothing, acceleration, homotopy, and coordinate descent with non-uniform sampling. As a result, our method features the first convergence rate guarantees among the coordinate descent methods, that are the best-known under a variety of common structure assumptions on the template. We provide numerical evidence to support the theoretical results with a comparison to state-of-the-art algorithms.

Author Information

Ahmet Alacaoglu (EPFL)
Quoc Tran Dinh (Department of Statistics and Operations Research, University of North Carolina at Chapel Hill, North Carolina)
Olivier Fercoq (Telecom ParisTech)
Volkan Cevher (EPFL)

More from the Same Authors