The Dimension Strikes Back with Gradients: Generalization of Gradient
  Methods in Stochastic Convex Optimization
Matan Schliserman Uri Sherman Tomer Koren
We study the generalization performance of gradient methods in the
fundamental stochastic convex optimization setting, focusing on its dimension
dependence. First, for full-batch gradient descent (GD) we give a construction
of a learning problem in dimension $d=O(n^2)$, where the canonical version of
GD (tuned for optimal performance of the empirical risk) trained with $n$
training examples converges, with constant probability, to an approximate
empirical risk minimizer with $\Omega(1)$ population excess risk. Our bound
translates to a lower bound of $\Omega (\sqrt{d})$ on the number of training
examples required for standard GD to reach a non-trivial test error, answering
an open question raised by Feldman (2016) and Amir, Koren, and Livni (2021b)
and showing that a non-trivial dimension dependence is unavoidable.
Furthermore, for standard one-pass stochastic gradient descent (SGD), we show
that an application of the same construction technique provides a similar
$\Omega(\sqrt{d})$ lower bound for the sample complexity of SGD to reach a
non-trivial empirical error, despite achieving optimal test performance. This
again provides an exponential improvement in the dimension dependence compared
to previous work (Koren, Livni, Mansour, and Sherman, 2022), resolving an open
question left therein.