Parallel and robust empirical risk minimization via the median trick

. Parallel and robust empirical risk minimization via the median trick. volume 10693, pages 378-391, DOI 10.1007/978-3-319-72453-9_31, 12, 2017.

BuchMathematical Aspects of Computer and Information Sciences - Poc. MACIS 2017
TypIn Konferenzband
VerlagSpringer
SerieLecture Notes in Computer Science
Band10693
DOI10.1007/978-3-319-72453-9_31
ISBN978-3-319-72452-2
Monat12
Jahr2017
Seiten378-391
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.