Convex SGD: Generalization Without Early Stopping

Julien Hendrickx, Alex Olshevsky
1/8/2024
cs.LGmath.ST

No confident code implementation found for this paper.

Abstract

We consider the generalization error associated with stochastic gradient descent on a smooth convex function over a compact set. We show the first bound on the generalization error that vanishes when the number of iterations $T$ and the dataset size $n$ go to zero at arbitrary rates; our bound scales as $\tilde{O}(1/\sqrt{T} + 1/\sqrt{n})$ with step-size $α_t = 1/\sqrt{t}$. In particular, strong convexity is not needed for stochastic gradient descent to generalize well.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex Optimization

90% match2023

Stochastic Gradient Descent in Non-Convex Problems: Asymptotic Convergence with Relaxed Step-Size via Stopping Time Methods

86% match2025

The Dimension Strikes Back with Gradients: Generalization of Gradient Methods in Stochastic Convex Optimization

86% match2024

Tight Generalization Error Bounds for Stochastic Gradient Descent in Non-convex Learning

86% match2025

Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithm

86% match2026

Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithm

86% match2023

Cite this paper

@article{hendrickx2024convex,
  title  = {Convex SGD: Generalization Without Early Stopping},
  author = {Julien Hendrickx and Alex Olshevsky},
  year   = {2024},
  eprint = {2401.04067},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2401.04067v2}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2401.04067.svg)](https://codeofpaper.com/paper/2401.04067)

Discussion