Beating SGD Saturation with Tail-Averaging and Minibatching

TitleBeating SGD Saturation with Tail-Averaging and Minibatching
Publication TypeConference Proceedings
Year of Publication2019
AuthorsMuecke, N, Neu, G, Rosasco, L
Conference NameNeural Information Processing Systems (NeurIPS 2019)
Date Published11/2019
Conference LocationVancouver, Canada
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.

Associated Module: 

CBMM Relationship: 

  • CBMM Funded