Parallel boosting with momentum

Indraneel Mukherjee; Kevin Canini; Rafael Frongillo; Yoram Singer

doi:10.1007/978-3-642-40994-3_2

Parallel boosting with momentum

Indraneel Mukherjee, Kevin Canini, Rafael Frongillo, Yoram Singer

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

21 Scopus citations

Abstract

We describe a new, simplified, and general analysis of a fusion of Nesterov's accelerated gradient with parallel coordinate descent. The resulting algorithm, which we call BOOM, for boosting with momentum, enjoys the merits of both techniques. Namely, BOOM retains the momentum and convergence properties of the accelerated gradient method while taking into account the curvature of the objective function. We describe a distributed implementation of BOOM which is suitable for massive high dimensional datasets. We show experimentally that BOOM is especially effective in large scale learning problems with rare yet informative features.

Original language	English (US)
Title of host publication	Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2013, Proceedings
Pages	17-32
Number of pages	16
Edition	PART 3
DOIs	https://doi.org/10.1007/978-3-642-40994-3_2
State	Published - 2013
Event	European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2013 - Prague, Czech Republic Duration: Sep 23 2013 → Sep 27 2013

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 3
Volume	8190 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2013
Country/Territory	Czech Republic
City	Prague
Period	9/23/13 → 9/27/13

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Keywords

accelerated gradient
boosting
coordinate descent

Access to Document

10.1007/978-3-642-40994-3_2

Cite this

Mukherjee, I., Canini, K., Frongillo, R., & Singer, Y. (2013). Parallel boosting with momentum. In Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2013, Proceedings (PART 3 ed., pp. 17-32). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8190 LNAI, No. PART 3). https://doi.org/10.1007/978-3-642-40994-3_2

Mukherjee, Indraneel ; Canini, Kevin ; Frongillo, Rafael et al. / Parallel boosting with momentum. Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2013, Proceedings. PART 3. ed. 2013. pp. 17-32 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 3).

@inproceedings{b01b420eef73475ab02a99793bd7a936,

title = "Parallel boosting with momentum",

abstract = "We describe a new, simplified, and general analysis of a fusion of Nesterov's accelerated gradient with parallel coordinate descent. The resulting algorithm, which we call BOOM, for boosting with momentum, enjoys the merits of both techniques. Namely, BOOM retains the momentum and convergence properties of the accelerated gradient method while taking into account the curvature of the objective function. We describe a distributed implementation of BOOM which is suitable for massive high dimensional datasets. We show experimentally that BOOM is especially effective in large scale learning problems with rare yet informative features.",

keywords = "accelerated gradient, boosting, coordinate descent",

author = "Indraneel Mukherjee and Kevin Canini and Rafael Frongillo and Yoram Singer",

note = "Copyright: Copyright 2013 Elsevier B.V., All rights reserved.; European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2013 ; Conference date: 23-09-2013 Through 27-09-2013",

year = "2013",

doi = "10.1007/978-3-642-40994-3_2",

language = "English (US)",

isbn = "9783642409936",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 3",

pages = "17--32",

booktitle = "Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2013, Proceedings",

edition = "PART 3",

}

Mukherjee, I, Canini, K, Frongillo, R & Singer, Y 2013, Parallel boosting with momentum. in Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2013, Proceedings. PART 3 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 3, vol. 8190 LNAI, pp. 17-32, European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2013, Prague, Czech Republic, 9/23/13. https://doi.org/10.1007/978-3-642-40994-3_2

Parallel boosting with momentum. / Mukherjee, Indraneel; Canini, Kevin; Frongillo, Rafael et al.
Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2013, Proceedings. PART 3. ed. 2013. p. 17-32 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8190 LNAI, No. PART 3).

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

TY - GEN

T1 - Parallel boosting with momentum

AU - Mukherjee, Indraneel

AU - Canini, Kevin

AU - Frongillo, Rafael

AU - Singer, Yoram

PY - 2013

Y1 - 2013

N2 - We describe a new, simplified, and general analysis of a fusion of Nesterov's accelerated gradient with parallel coordinate descent. The resulting algorithm, which we call BOOM, for boosting with momentum, enjoys the merits of both techniques. Namely, BOOM retains the momentum and convergence properties of the accelerated gradient method while taking into account the curvature of the objective function. We describe a distributed implementation of BOOM which is suitable for massive high dimensional datasets. We show experimentally that BOOM is especially effective in large scale learning problems with rare yet informative features.

AB - We describe a new, simplified, and general analysis of a fusion of Nesterov's accelerated gradient with parallel coordinate descent. The resulting algorithm, which we call BOOM, for boosting with momentum, enjoys the merits of both techniques. Namely, BOOM retains the momentum and convergence properties of the accelerated gradient method while taking into account the curvature of the objective function. We describe a distributed implementation of BOOM which is suitable for massive high dimensional datasets. We show experimentally that BOOM is especially effective in large scale learning problems with rare yet informative features.

KW - accelerated gradient

KW - boosting

KW - coordinate descent

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

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

U2 - 10.1007/978-3-642-40994-3_2

DO - 10.1007/978-3-642-40994-3_2

M3 - Conference contribution

AN - SCOPUS:84886551243

SN - 9783642409936

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 17

EP - 32

BT - Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2013, Proceedings

T2 - European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2013

Y2 - 23 September 2013 through 27 September 2013

ER -

Mukherjee I, Canini K, Frongillo R, Singer Y. Parallel boosting with momentum. In Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2013, Proceedings. PART 3 ed. 2013. p. 17-32. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 3). doi: 10.1007/978-3-642-40994-3_2

Parallel boosting with momentum

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this