Parallel and robust empirical risk minimization via the median trick

Authors Alexander Kogler
Patrick Traxler
Editors Johannes Blömer
Ilias S. Kotsiraes
Temur Kutsia
Dimitris E. Simos
Title Parallel and robust empirical risk minimization via the median trick
Booktitle Mathematical Aspects of Computer and Information Sciences - Poc. MACIS 2017
Type in proceedings
Publisher Springer
Series Lecture Notes in Computer Science
Volume 10693
ISBN 978-3-319-72452-2
DOI 10.1007/978-3-319-72453-9_31
Month December
Year 2017
Pages 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.