The Sample Complexity of Gradient Descent in Stochastic Convex Optimization
This resolves an open problem in optimization theory by providing tight bounds on GD's performance, which is incremental but clarifies fundamental limitations for researchers in machine learning and optimization.
The paper analyzes the sample complexity of full-batch Gradient Descent (GD) in non-smooth stochastic convex optimization, showing that its generalization error is $ ilde{\Theta}(d/m + 1/\sqrt{m})$, matching worst-case empirical risk minimizers and indicating no advantage over naive methods.
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 Θ(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=Ω(1/ε^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.