Timezone: »

 
Poster
Beating SGD Saturation with Tail-Averaging and Minibatching
Nicole Muecke · Gergely Neu · Lorenzo Rosasco

Thu Dec 12 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #207
in Optimization -- Stochastic Optimization »

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.

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

Author Information

Nicole Muecke (University of Stuttgart)
Gergely Neu (Universitat Pompeu Fabra)
Lorenzo Rosasco (University of Genova- MIT - IIT)

More from the Same Authors