Poster
Beating SGD Saturation with Tail-Averaging and Minibatching
Nicole Muecke · Gergely Neu · Lorenzo Rosasco
East Exhibition Hall B, C #207
Keywords: [ Stochastic Optimization ] [ Optimization ] [ Algorithms -> Kernel Methods; Algorithms -> Large Scale Learning; Algorithms -> Regression; Theory ] [ Hardness of Learning and ]
While stochastic gradient descent (SGD) is one of the major workhorses in machine learning, the learning properties of many practically used variants are still poorly understood. In this paper, we consider least squares learning in a nonparametric setting and contribute to filling this gap by focusing on the effect and interplay of multiple passes, mini-batching and averaging, in particular tail averaging. Our results show how these different variants of SGD can be combined to achieve optimal learning rates, also providing practical insights. A novel key result is that tail averaging allows faster convergence rates than uniform averaging in the nonparametric setting. Further, we show that a combination of tail-averaging and minibatching allows more aggressive step-size choices than using any one of said components.
Live content is unavailable. Log in and register to view live content