NeurIPS 2017poster36 citations
Smooth Primal-Dual Coordinate Descent Algorithms for Nonsmooth Convex Optimization
Ahmet Alacaoglu, Quoc Tran Dinh, Olivier Fercoq, Volkan Cevher
Abstract
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.
BibTeX
@inproceedings{NIPS2017_71887f62,
author = {Alacaoglu, Ahmet and Tran Dinh, Quoc and Fercoq, Olivier and Cevher, Volkan},
booktitle = {Advances in Neural Information Processing Systems},
editor = {I. Guyon and U. Von Luxburg and S. Bengio and H. Wallach and R. Fergus and S. Vishwanathan and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Smooth Primal-Dual Coordinate Descent Algorithms for Nonsmooth Convex Optimization},
url = {https://proceedings.neurips.cc/paper_files/paper/2017/file/71887f62f073a78511cbac56f8cab53f-Paper.pdf},
volume = {30},
year = {2017}
}