We study to what extent may stochastic gradient descent (SGD) be understood as a ``conventional'' learning rule that achieves generalization performance by obtaining a good fit to training data.  We consider the fundamental stochastic convex optimization framework, where SGD is classically known to minimize the population risk at an optimal rate, and prove that, surprisingly, there exist problem instances where the SGD solution exhibits both empirical risk and generalization gap lower bounded by a universal constant.  Consequently, it turns out that SGD is not algorithmically stable in any sense, and its generalization ability cannot be explained by uniform convergence or any other currently known generalization bound technique for that matter (other than that of its classical analysis).  Time permitting, we will discuss related results for with-replacement SGD, multi-epoch SGD, and full-batch gradient descent.

Based on joint works with Idan Amir, Roi Livni, Yishay Mansour and Uri Sherman.

-- 
Tim van Erven <tim@timvanerven.nl>
www.timvanerven.nl