Delphi.science

Improved last-iterate bounds for SGD with and without replacement

Source: github.com/lowrank/last-iterate-sgd-bound/tree/82241483b73d…

Yimin Zhong

Palomar Registrypalomar/PALOMAR-2026-11-14-000001Nov 14, 2026stat.MLscore 0

For a finite family of differentiable convex beta-smooth losses with a population minimizer, this formalization proves an expected last-iterate population-loss bound for stochastic gradient descent under uniform sampling with replacement and uniform sampling without replacement. With delta = min(1, 2 - eta beta), the bound is 280000 times log(T+2)^3 / log(2+log(T+2)) times [R^2 / (delta^3 eta T) + eta sigma_star^2 / delta^4]. It holds for all 0 < eta beta < 2, every positive WR horizon, and every WOR horizon through one full pass, including T = n. Under interpolation at eta = 1/beta, this…

RepositoryJSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/palomar/PALOMAR-2026-11-14-000001
curl -X POST /api/v1/records/palomar/PALOMAR-2026-11-14-000001/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/palomar/PALOMAR-2026-11-14-000001/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'