  We analyze the sample complexity of full-batch Gradient Descent (GD) in the
setup of non-smooth Stochastic Convex Optimization. We show that the
generalization error of GD, with common choice of hyper-parameters, can be
$\tilde \Theta(d/m + 1/\sqrt{m})$, where $d$ is the dimension and $m$ is the
sample size. This matches the sample complexity of \emph{worst-case} empirical
risk minimizers. That means that, in contrast with other algorithms, GD has no
advantage over naive ERMs. Our bound follows from a new generalization bound
that depends on both the dimension as well as the learning rate and number of
iterations. Our bound also shows that, for general hyper-parameters, when the
dimension is strictly larger than number of samples, $T=\Omega(1/\epsilon^4)$
iterations are necessary to avoid overfitting. This resolves an open problem by
Schlisserman et al.23 and Amir er Al.21, and improves over previous lower
bounds that demonstrated that the sample size must be at least square root of
the dimension.
