Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GD. (arXiv:2204.12446v1 [stat.ML])

We provide sharp path-dependent generalization and excess error guarantees
for the full-batch Gradient Decent (GD) algorithm for smooth losses (possibly
non-Lipschitz, possibly nonconvex). At the heart of our analysis is a novel
generalization error technique for deterministic symmetric algorithms, that
implies average output stability and a bounded expected gradient of the loss at
termination leads to generalization. This key result shows that small
generalization error occurs at stationary points, and allows us to bypass
Lipschitz assumptions on the loss prevalent …

arxiv ml risk