---
abstract: 'While stochastic gradient descent (SGD) is a workhorse in machine learning, the learning properties of many practically used variants are hardly known. In this paper, we consider least squares learning and contribute filling this gap focusing on the effect and interplay of multiple passes, mini-batching and averaging, and in particular tail averaging. Our results show how these different flavors of SGD can be combined to achieve optimal learning errors, hence providing practical insights.'
author:
- 'Nicole Mücke[^1] , Gergely Neu[^2] and Lorenzo Rosasco[^3]'
bibliography:
- 'bib\_SGD.bib'
title:
- 'Beating SGD Saturation with Tail-Averaging and Minibatching'
- 'Beating SGD Saturation with Tail-Averaging and Minibatching'
---

Introduction
============

Stochastic gradient descent (SGD) provides a simple and yet stunningly efficient way to solve a broad range of machine learning problems. Our starting observation is that, while a number of variants including multiple passes over the data, mini-batching and averaging are commonly used, their combination and learning properties are studied only partially. The literature on convergence properties of SGD is vast, but usually only one pass over the data is considered, see, e.g., [@NemJudLan09]. In the context of nonparametric statistical learning, which we consider here, the study of one-pass SGD was probably first considered in [@SmaYao06] and then further developed in a number of papers (e.g., [@YinPon08; @YaoTar14; @orabona]). Another line of work derives statistical learning results for one pass SGD with averaging from a worst-case sequential prediction analysis [@RSS12; @HK14; @RaShaSri11]. The idea of using averaging also has a long history going back to at least the works of [@R88] and [@PolJu92], see also [@ShaZha13] and references therein. More recently, averaging was shown to lead to larger, possibly constant, step-sizes, see [@BacMou13; @DieuBa16; @DieFlaBac17]. A different take on the role of (weighted) averaging was given in [@NeuRos18], highlighting a connection with ridge regression, a.k.a. Tikhonov regularization. A different flavor of averaging called *tail averaging* for one-pass SGD was considered in [@JKKNS18] in a parametric setting. The role of minibatching has also being considered and shown to potentially lead to linear parallelization speedups, see e.g. [@Cotter11] and references therein. Very few results consider the role of multiple passes for learning. Indeed, this variant of SGD is typically analyzed for the minimization of the empirical risk, rather than the actual population risk, see for example [@Ber97]. To the best of our knowledge the first paper to analyze the learning properties of multipass SGD was [@RosVil15], where a cyclic selection strategy was considered. Other results for multipass SGD were then given in [@HarRecSin16] and [@LinCamRos16]. Our starting point are the results in [@LinRos17] where optimal results for multipass SGD where derived considering also the effect of mini-batching. Following the approach in this latter paper, multipass SGD with averaging was analyzed by [@PillRudBa18] with no minibatching.

In this paper, we develop and improve the above results on two fronts. On the one hand, we consider for the first time the role of multiple passes, mini-batching and averaging at once. On the other hand, we further study the beneficial effect of tail averaging. Both mini-batching and averaging are known to allow larger step-sizes. Our results show that their combination allows even more aggressive parameter choices. At the same time averaging was shown to lead to slower convergence rates in some cases. In a parametric setting, averaging prevents linear convergence rates [@BacMou13; @DieFlaBac17]. In a nonparametric setting, it prevents exploiting the possible regularity in the solution [@DieuBa16], a phenomenon called [*saturation*]{} [@engl96]. In other words, uniform averaging can prevent optimal rates in a nonparametric setting. Our results provide a simple explanation to this effect, showing it has a purely deterministic nature. Further, we show that tail averaging allows to bypass this problem. These results parallel the findings of [@JKKNS18], showing similar beneficial effects of tail-averaging and minibatching in the finite-dimensional setting. Following [@LinRos17], our analysis relies on the study of batch gradient descent and then of the discrepancy between batch gradient and SGD, with the additional twist that it also considers the role of tail-averaging. The rest of the paper is organized as follows. In Section \[LS\_learn\], we describe the least-squares learning problem that we consider, as well as the different SGD variants we analyze. In Section \[appet\], we collect a number of observations shedding light on the role of uniform and tail averaging. In Section \[sec:main\], we present and discuss our main results. In Section \[numerics\] we illustrate our results via some numerical simulations. Proofs and technical results are deferred to the appendices.

Least Squares Learning with SGD {#LS_learn}
===============================

An appetizer: Averaging and Gradient Descent Convergence {#appet}
========================================================

Main Results and Discussion {#sec:main}
===========================

Numerical Illustration {#numerics}
======================

[**Acknowledgments**]{}\
\
NM is supported by the German Research Foundation under DFG Grant STE 1074/4-1. L. R. acknowledges the financial support of the AFOSR projects FA9550-17-1-0390 and BAA-AFRL-AFOSR-2016-0007 (European Office of Aerospace Research and Development), and the EU H2020-MSCA-RISE project NoMADS - DLV-777826.

Analysis {#sec:analysis}
========

[^1]: Institute for Stochastics and Applications, University of Stuttgart, [*nicole.muecke@mathematik.uni-stuttgart.de*]{}

[^2]: Universitat Pompeu Fabra, Barcelona, Spain, [ *gergely.neu@gmail.com*]{}

[^3]: LCSL, Massachusetts Institute of Technology & Istituto Italiano di Tecnologia & DIBRIS, Universita’ degli Studi di Genova, [*lrosasco@mit.edu*]{}
