Fast distributed coordinate descent for non-strongly convex losses

Olivier Fercoq; Zheng Qu; Peter Richtárik; Martin Takáč

doi:10.1109/MLSP.2014.6958862

Fast distributed coordinate descent for non-strongly convex losses

Olivier Fercoq, Zheng Qu, Peter Richtárik, Martin Takáč

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

31 Scopus citations

Abstract

We propose an efficient distributed randomized coordinate descent method for minimizing regularized non-strongly convex loss functions. The method attains the optimal O(1/k²) convergence rate, where k is the iteration counter. The core of the work is the theoretical study of stepsize parameters. We have implemented the method on Archer - the largest super-computer in the UK - and show that the method is capable of solving a (synthetic) LASSO optimization problem with 50 billion variables.

Original language	English (US)
Title of host publication	IEEE International Workshop on Machine Learning for Signal Processing, MLSP
Editors	Mamadou Mboup, Tulay Adali, Eric Moreau, Jan Larsen
Publisher	IEEE Computer Society
ISBN (Electronic)	9781479936946
DOIs	https://doi.org/10.1109/MLSP.2014.6958862
State	Published - Nov 14 2014
Externally published	Yes
Event	2014 24th IEEE International Workshop on Machine Learning for Signal Processing, MLSP 2014 - Reims, France Duration: Sep 21 2014 → Sep 24 2014

Publication series

Name	IEEE International Workshop on Machine Learning for Signal Processing, MLSP
ISSN (Print)	2161-0363
ISSN (Electronic)	2161-0371

Other

Other	2014 24th IEEE International Workshop on Machine Learning for Signal Processing, MLSP 2014
Country/Territory	France
City	Reims
Period	09/21/14 → 09/24/14

Bibliographical note

Publisher Copyright:
© 2014 IEEE.

Keywords

Coordinate descent
acceleration
distributed algorithms

ASJC Scopus subject areas

Human-Computer Interaction
Signal Processing

Access to Document

10.1109/MLSP.2014.6958862

Cite this

Fercoq, O., Qu, Z., Richtárik, P., & Takáč, M. (2014). Fast distributed coordinate descent for non-strongly convex losses. In M. Mboup, T. Adali, E. Moreau, & J. Larsen (Eds.), IEEE International Workshop on Machine Learning for Signal Processing, MLSP Article 6958862 (IEEE International Workshop on Machine Learning for Signal Processing, MLSP). IEEE Computer Society. https://doi.org/10.1109/MLSP.2014.6958862

Fercoq, Olivier ; Qu, Zheng ; Richtárik, Peter et al. / Fast distributed coordinate descent for non-strongly convex losses. IEEE International Workshop on Machine Learning for Signal Processing, MLSP. editor / Mamadou Mboup ; Tulay Adali ; Eric Moreau ; Jan Larsen. IEEE Computer Society, 2014. (IEEE International Workshop on Machine Learning for Signal Processing, MLSP).

@inproceedings{57b35fe24af340618ff16eed41f96be8,

title = "Fast distributed coordinate descent for non-strongly convex losses",

abstract = "We propose an efficient distributed randomized coordinate descent method for minimizing regularized non-strongly convex loss functions. The method attains the optimal O(1/k2) convergence rate, where k is the iteration counter. The core of the work is the theoretical study of stepsize parameters. We have implemented the method on Archer - the largest super-computer in the UK - and show that the method is capable of solving a (synthetic) LASSO optimization problem with 50 billion variables.",

keywords = "Coordinate descent, acceleration, distributed algorithms",

author = "Olivier Fercoq and Zheng Qu and Peter Richt{\'a}rik and Martin Tak{\'a}{\v c}",

note = "Publisher Copyright: {\textcopyright} 2014 IEEE.; 2014 24th IEEE International Workshop on Machine Learning for Signal Processing, MLSP 2014 ; Conference date: 21-09-2014 Through 24-09-2014",

year = "2014",

month = nov,

day = "14",

doi = "10.1109/MLSP.2014.6958862",

language = "English (US)",

series = "IEEE International Workshop on Machine Learning for Signal Processing, MLSP",

publisher = "IEEE Computer Society",

editor = "Mamadou Mboup and Tulay Adali and Eric Moreau and Jan Larsen",

booktitle = "IEEE International Workshop on Machine Learning for Signal Processing, MLSP",

address = "United States",

}

Fercoq, O, Qu, Z, Richtárik, P & Takáč, M 2014, Fast distributed coordinate descent for non-strongly convex losses. in M Mboup, T Adali, E Moreau & J Larsen (eds), IEEE International Workshop on Machine Learning for Signal Processing, MLSP., 6958862, IEEE International Workshop on Machine Learning for Signal Processing, MLSP, IEEE Computer Society, 2014 24th IEEE International Workshop on Machine Learning for Signal Processing, MLSP 2014, Reims, France, 09/21/14. https://doi.org/10.1109/MLSP.2014.6958862

Fast distributed coordinate descent for non-strongly convex losses. / Fercoq, Olivier; Qu, Zheng; Richtárik, Peter et al.
IEEE International Workshop on Machine Learning for Signal Processing, MLSP. ed. / Mamadou Mboup; Tulay Adali; Eric Moreau; Jan Larsen. IEEE Computer Society, 2014. 6958862 (IEEE International Workshop on Machine Learning for Signal Processing, MLSP).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Fast distributed coordinate descent for non-strongly convex losses

AU - Fercoq, Olivier

AU - Qu, Zheng

AU - Richtárik, Peter

AU - Takáč, Martin

PY - 2014/11/14

Y1 - 2014/11/14

N2 - We propose an efficient distributed randomized coordinate descent method for minimizing regularized non-strongly convex loss functions. The method attains the optimal O(1/k2) convergence rate, where k is the iteration counter. The core of the work is the theoretical study of stepsize parameters. We have implemented the method on Archer - the largest super-computer in the UK - and show that the method is capable of solving a (synthetic) LASSO optimization problem with 50 billion variables.

AB - We propose an efficient distributed randomized coordinate descent method for minimizing regularized non-strongly convex loss functions. The method attains the optimal O(1/k2) convergence rate, where k is the iteration counter. The core of the work is the theoretical study of stepsize parameters. We have implemented the method on Archer - the largest super-computer in the UK - and show that the method is capable of solving a (synthetic) LASSO optimization problem with 50 billion variables.

KW - Coordinate descent

KW - acceleration

KW - distributed algorithms

UR - http://www.scopus.com/inward/record.url?scp=84912553418&partnerID=8YFLogxK

U2 - 10.1109/MLSP.2014.6958862

DO - 10.1109/MLSP.2014.6958862

M3 - Conference contribution

AN - SCOPUS:84912553418

T3 - IEEE International Workshop on Machine Learning for Signal Processing, MLSP

BT - IEEE International Workshop on Machine Learning for Signal Processing, MLSP

A2 - Mboup, Mamadou

A2 - Adali, Tulay

A2 - Moreau, Eric

A2 - Larsen, Jan

PB - IEEE Computer Society

T2 - 2014 24th IEEE International Workshop on Machine Learning for Signal Processing, MLSP 2014

Y2 - 21 September 2014 through 24 September 2014

ER -

Fercoq O, Qu Z, Richtárik P, Takáč M. Fast distributed coordinate descent for non-strongly convex losses. In Mboup M, Adali T, Moreau E, Larsen J, editors, IEEE International Workshop on Machine Learning for Signal Processing, MLSP. IEEE Computer Society. 2014. 6958862. (IEEE International Workshop on Machine Learning for Signal Processing, MLSP). doi: 10.1109/MLSP.2014.6958862

Fast distributed coordinate descent for non-strongly convex losses

Abstract

Publication series

Other

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this