The Sample Complexity of Gradient Descent in Stochastic Convex Optimization

arXiv:2404.04931v1 Announce Type: new
Abstract: 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 (minmax) optimal 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 …

abstract analyze arxiv complexity cs.lg error gradient math.oc optimization parameters sample setup show stochastic type