How Smoothness Controls Overfitting: Sharp Curvature–Time Laws for Gradient Descent

How does the population risk of gradient descent evolve as optimization continues on the same finite training sample? Classical stability bounds can overstate the statistical cost of longer training. We establish sharp curvature–time laws for projected gradient descent on the unit ball with convex, $1$-Lipschitz, $L$-smooth losses for every $L\ge 1$. At unit smoothness, the worst-case expected excess risk is $$\begin{gathered} \Theta (\min \\ 1,q^{-1}+n^{-1/2}+q{n}^{-3/2} \\ ) \end{gathered}$$ for sample size $n$ and cumulative step size $q$. Although the classical stability certificate is already constant-order at $q\asymp n$, the worst-case risk remains at the optimal $\Theta (n^{-1/2})$ scale and reaches constant order only at $q\asymp n^{3/2}$. The key is an interaction–dissipation principle that balances higher-order sample interactions against the stabilizing effect of losses unchanged by sample replacement. Beyond convexity, sharp risk laws show that even vanishing negative curvature can separate the last iterate from the full parameter average. On a single weakly nonconvex instance, the last iterate, a uniformly sampled iterate, and the full parameter average all have $O(n^{-1/2})$ risk at an earlier horizon, but at a common later horizon their risks are $\Theta (1)$, $\Theta ((\log n{)}^{-1})$, and $\Theta ((\log n{)}^{-2})$, respectively. Further applications yield sharp guarantees for weakly regularized pairwise learning, randomized coordinate descent, and fixed-source learning.