Perturbed Iterate SGD for Lipschitz Continuous Loss Functions with Numerical Error and Adaptive Step Sizes

Michael R. Metel

math.OCNov 9, 2022

Perturbed Iterate SGD for Lipschitz Continuous Loss Functions with Numerical Error and Adaptive Step Sizes

Authors: Michael R. Metel

Abstract

Motivated by neural network training in finite-precision arithmetic environments, this work studies the convergence of perturbed iterate SGD using adaptive step sizes in an environment with numerical error. Considering a general stochastic Lipschitz continuous loss function, an asymptotic convergence result to a Clarke stationary point is proven as well as the non-asymptotic convergence to an approximate stationary point in expectation. It is assumed that only an approximation of the loss function's stochastic gradient can be computed, in addition to error in computing the SGD step itself.

Figures & tables

Panel of Figure 1 — Figure 1: Plots of SGD, PISGD, and PNSGD. The mean (thick solid), minimum (thin solid), and maximum (dotted) test set accuracy for R20C10 in $\mathbb{F}_{15/20}$ (top), and R32C100 in $\mathbb{F}_{17/24}$ (bottom) over 10 runs.

Panel of Figure 2 — Figure 2: For the first run of the R20C10 experiments, $\hat{c}^{k}_{1}$ was computed for the first 100 training steps, such that $\langle\mathbb{E}[\widehat{\nabla}F(\bm{w}^{k}+\hat{\bm{u}}^{k},\bm{\xi},\bm{b}^{k})],\nabla f_{\alpha_{k}}(\bm{w}^{k})\rangle=\hat{c}^{k}_{1}\|\nabla f_{\alpha_{k}}(\bm{w}^{k})\|^{2}_{2}$ , to empirically observe how well Assumption 5.1 holds.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Symbol	Description	Page
Section 1
$f$	Loss function	1
$F$	Stochastic loss function	1
$\bm{\xi}$	Random vector argument of $F$	1
$\bm{w}$	Decision variables of $f$	2
Section 2

Appendix

Table 1: Table of notation divided by section.

Stochastic Optimization Convergence

Stochastic optimization convergence studies how noisy, sampled, or delayed updates approach solutions and how fast they do so.

See all 205 papers

Gradient Descent's Last Iterate is Often (slightly) Suboptimal
Apr 15, 2026Guy Kornowski, Ohad ShamirLast-Iterate Convergence Gradient Descent
Institute for Advanced Study · Weizmann Institute of Science · University of Toronto and the Vector Institute
Flatland: The Adventures of Gradient Descent with Large Step Sizes
Jun 4, 2026Leonardo Galli, Curtis Fox, Wiebke Bartolomaeus +2Edge of Stability Gradient Descent
LMU Munich · Munich Center for Machine Learning · University of British Columbia +1
Convergence of stochastic gradient descent for learning linear neural networks
Oct 20, 2026Gabin Maxime Nguegnang, Bubacarr Bah, Holger Rauhut +1Stochastic Optimization Convergence Stochastic Gradient Descent

Apr 15, 2026J/K move · Enter open · S save

Gradient Descent's Last Iterate is Often (slightly) Suboptimal

Guy Kornowski, Ohad Shamir

Institute for Advanced Study · Weizmann Institute of Science · University of Toronto and the Vector Institute

Last-Iterate Convergence Gradient Descent Stochastic Gradient Descent

Open paper AskPDF arXiv

We consider the well-studied setting of minimizing a convex Lipschitz function using either gradient descent (GD) or its stochastic variant (SGD), and examine the last iterate convergence. By now, it is known that standard stepsize choices lead to a last iterate convergence rate of

\log T/\sqrt{T}

after

T

steps. A breakthrough result of Jain et al. [2019] recovered the optimal

1/\sqrt{T}

rate by constructing a non-standard stepsize sequence. However, this sequence requires choosing

T

in advance, as opposed to common stepsize schedules which apply for any time horizon. Moreover, Jain et al. conjectured that without prior knowledge of

T

, no stepsize sequence can ensure the optimal error for SGD's last iterate, a claim which so far remained unproven. We prove this conjecture, and in fact show that even in the noiseless case of GD, it is impossible to avoid an excess poly-log factor in

T

when considering an anytime last iterate guarantee.

Abstract

Stochastic Optimization Convergence

Explore similar work

Gradient Descent's Last Iterate is Often (slightly) Suboptimal

Flatland: The Adventures of Gradient Descent with Large Step Sizes

Convergence of stochastic gradient descent for learning linear neural networks