  Stochastic gradient descent (SGD) has become the most attractive optimization
method in training large-scale deep neural networks due to its simplicity, low
computational cost in each updating step, and good performance. Standard excess
risk bounds show that SGD only needs to take one pass over the training data
and more passes could not help to improve the performance. Empirically, it has
been observed that SGD taking more than one pass over the training data
(multi-pass SGD) has much better excess risk bound performance than the SGD
only taking one pass over the training data (one-pass SGD). However, it is not
very clear that how to explain this phenomenon in theory. In this paper, we
provide some theoretical evidences for explaining why multiple passes over the
training data can help improve performance under certain circumstance.
Specifically, we consider smooth risk minimization problems whose objective
function is non-convex least squared loss. Under Polyak-Lojasiewicz (PL)
condition, we establish faster convergence rate of excess risk bound for
multi-pass SGD than that for one-pass SGD.
