{"ID":2877202,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.20823","arxiv_id":"2508.20823","title":"Revisiting Stochastic Gradient Descent for Strongly Convex Objectives: Tight Uniform-in-Time Bounds","abstract":"Stochastic optimization via Stochastic Gradient Descent (SGD) is a fundamental problem in statistics and optimization. This paper revisits Stochastic Gradient Descent (SGD) for strongly convex objectives, establishing tight, uniform-in-time convergence bounds. We prove that, with probability at least $1 - β$, a convergence rate of order $\\frac{\\log \\log k + \\log (1/β)}{k}$ simultaneously holds for all $ k \\in \\mathbb{N}_+ $, and demonstrate this bound is tight up to constant factors. We also provide an improved last-iterate convergence rate for such objectives. While focused on strongly convex objectives, our results generalize to the Polyak-Łojasiewicz functions and indicate an $\\mathcal{O}(k^{-1} \\log \\log k)$ convergence rate for contractive stochastic approximation with additive noise.","short_abstract":"Stochastic optimization via Stochastic Gradient Descent (SGD) is a fundamental problem in statistics and optimization. This paper revisits Stochastic Gradient Descent (SGD) for strongly convex objectives, establishing tight, uniform-in-time convergence bounds. We prove that, with probability at least $1 - β$, a converg...","url_abs":"https://arxiv.org/abs/2508.20823","url_pdf":"https://arxiv.org/pdf/2508.20823v2","authors":"[\"Kang Chen\",\"Yasong Feng\",\"Tianyu Wang\"]","published":"2025-08-28T14:20:49Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}