arXiv Machine Learning

Bias-Optimal Bounds for Stochastic Gradient Descent

The paper presents a non‑asymptotic analysis of Stochastic Gradient Descent (SGD) that focuses on the bias component of its convergence bounds. Under assumptions of convexity or strong convexity and smoothness, the authors derive new bias‑optimal bounds for all constant step‑sizes <gamma L> in (0,2), covering critical and large step‑size regimes that were previously unexplored without extra variance assumptions. For critical step‑sizes, the paper shows that while an optimal bias term cannot be achieved, it can be approximated arbitrarily closely, and applies these results to obtain new complexity bounds for the Stochastic Proximal algorithm without requiring regularity assumptions.

arXiv Machine Learning
Oct 16

Generalization Guarantees of Randomized Block Coordinate Descent for Nonconvex Learning

The paper presents high‑probability generalization guarantees for Randomized Block Coordinate Descent (RBCD) when applied to nonconvex learning problems. It derives bounds on the gradients of both empirical and population risks under standard smoothness assumptions, and shows how polynomially decaying step sizes and early stopping can achieve optimal convergence rates for population gradients. In settings where the objective is gradient‑dominated, the authors provide functional suboptimality bounds that approach optimistic rates seen in convex or low‑noise scenarios, and they also establish dimension‑independent bounds for loss functions with a particular structure, extending applicability to high‑dimensional problems.

By Ruixi Hu, Liang Wu
arXiv Machine Learning
Jun 2

Safeguarded Stochastic Polyak Step Sizes for Non-smooth Optimization: Robust Performance Without Small (Sub)Gradients

arXiv:2512. 02342v3 Announce Type: replace-cross Abstract: The stochastic Polyak step size (SPS) has proven to be a promising choice for stochastic gradient descent (SGD), delivering competitive performance relative to state-of-the-art methods on smooth convex and non-convex optimization problems, including deep neural network training.

By Dimitris Oikonomou, Nicolas Loizou
arXiv Machine Learning
Sep 14

Almost Sure Convergence Analysis of Stochastic Gradient Methods with Clipping and Additive Noise

The paper proves that stochastic gradient descent with gradient clipping and additive Gaussian noise (SGD‑CN) converges almost surely under smoothness and bounded noise assumptions, given standard decaying step sizes. The analysis extends to momentum variants such as the stochastic heavy ball and Nesterov's accelerated gradient, showing that careful energy constructions yield similar guarantees. These results provide stronger theoretical foundations for understanding the pathwise behaviour of clipped stochastic gradient methods in both convex and nonconvex regimes.

By Amartya Mukherjee, Jun Liu
arXiv Statistics ML
Aug 25

Stochastic gradient descent with initial regularization

The paper studies a variant of stochastic gradient descent called SGDIR, which incorporates initial regularization. It derives dimension‑free upper bounds on the expected excess risk for the squared loss, providing new rates for both averaged and non‑averaged SGDIR under various assumptions. The authors also establish matching lower bounds in certain regimes and compare SGDIR to ridge regression in noisy settings, showing comparable performance up to a polylogarithmic factor.

By Nabil Kahal\'e