REVIEW 4 cited by
The Sample Complexity of Gradient Descent in Stochastic Convex Optimization
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
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 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.
Forward citations
Cited by 4 Pith papers
-
Rapid Overfitting of Multi-Pass Stochastic Gradient Descent in Stochastic Convex Optimization
In non-smooth stochastic convex optimization, a second epoch of SGD with the standard step size can push the population loss up to a constant, and the paper gives matching rates for any step size and step count.
-
Flat Minima and Generalization: Insights from Stochastic Convex Optimization
In smooth stochastic convex optimization, flat empirical minima can incur constant population risk while sharp minima generalize optimally, and sharpness-aware algorithms can converge to such bad flat minima.
-
Complexity of Vector-valued Prediction: From Linear Models to Stochastic Convex Optimization
For vector-valued linear prediction with convex Lipschitz losses, ERM's sample complexity is Θ̃(k/ε²), and any d-dimensional stochastic convex optimization problem embeds into this setting with k=Θ(d) outputs.
-
The Fourth Quadrant: A Stylized View of Benign Misfitting
In a stylized single-spike linear model, useful span predictors in the window d/gamma^2 << n << d/gamma are forced to overshoot the training labels, so good test error comes together with large training error.
Discussion (0). Continue with ORCID to comment.