Parallel and robust empirical risk minimization via the median trick

Autoren Alexander Kogler
Patrick Traxler
Editoren Johannes Blömer
Ilias S. Kotsiraes
Temur Kutsia
Dimitris E. Simos
Titel Parallel and robust empirical risk minimization via the median trick
Buchtitel Mathematical Aspects of Computer and Information Sciences - Poc. MACIS 2017
Typ in Konferenzband
Verlag Springer
Serie Lecture Notes in Computer Science
Band 10693
ISBN 978-3-319-72452-2
DOI 10.1007/978-3-319-72453-9_31
Monat December
Jahr 2017
Seiten 378-391
SCCH ID# 17074
Abstract

The median trick is a technique to boost the success probability of algorithms. We apply it to empirical risk minimization (ERM) and related problems. We obtain a parallel ERM principle, i.e. we get parallel, scalable algorithms for many learning problems. We provide generalization bounds and carry out computer experiments to demonstrate the practical effectiveness of the median trick. Our results can be summarized as follows: The median trick applies to a large class of classification and regression problems. It is simple to implement, scales well, and is robust due to the application of the median. The trade-off is a slightly decreased accuracy compared to sequential algorithms.