Effective parallelisation for machine learning

Michael Kamp, Mario Boley, Olana Missura, Thomas Gärtner

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

7 Citations (Scopus)


We present a novel parallelisation scheme that simplifies the adaptation of learning algorithms to growing amounts of data as well as growing needs for accurate and confident predictions in critical applications. In contrast to other parallelisation techniques, it can be applied to a broad class of learning algorithms without further mathematical derivations and without writing dedicated code, while at the same time maintaining theoretical performance guarantees. Moreover, our parallelisation scheme is able to reduce the runtime of many learning algorithms to polylogarithmic time on quasi-polynomially many processing units. This is a significant step towards a general answer to an open question on the efficient parallelisation of machine learning algorithms in the sense of Nick's Class (NC). The cost of this parallelisation is in the form of a larger sample complexity. Our empirical study confirms the potential of our parallelisation scheme with fixed numbers of processors and instances in realistic application scenarios.

Original languageEnglish
Title of host publicationNIPS Proceedings
Subtitle of host publicationAdvances in Neural Information Processing Systems (NIPS 2017)
EditorsI. Guyon, U.V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan
Place of PublicationSan Deigo CA USA
PublisherNeural Information Processing Systems Foundation Inc.
Number of pages22
Publication statusPublished - 2017
Externally publishedYes
EventAdvances in Neural Information Processing Systems 2017 - Long Beach, United States of America
Duration: 4 Dec 20179 Dec 2017
Conference number: 30th
https://dl.acm.org/doi/proceedings/10.5555/3295222 (Proceedings)

Publication series

NameAdvances in Neural Information Processing Systems
PublisherNeural Information Processing Systems Foundation Inc.
ISSN (Print)1049-5258


ConferenceAdvances in Neural Information Processing Systems 2017
Abbreviated titleNIPS 2017
Country/TerritoryUnited States of America
CityLong Beach
Internet address

Cite this