Skip to yearly menu bar Skip to main content


Poster

Beating SGD Saturation with Tail-Averaging and Minibatching

Nicole Muecke · Gergely Neu · Lorenzo Rosasco

East Exhibition Hall B + C #207

Keywords: [ Hardness of Learning and ] [ Algorithms -> Kernel Methods; Algorithms -> Large Scale Learning; Algorithms -> Regression; Theory ] [ Optimization ] [ Stochastic Optimization ]


Abstract:

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