A Rate Transfer Method: Convergence Rates in Stochastic Gradient Descent via Stochastic Calculus

1 Introduction

• Under smoothness and moment conditions, Theorem 2 transfers an SDE finite-time estimate to SGD, assuming the required moments of the iterates remain bounded.The comparison adds a forcing term to the SDE estimate, described as g(s) + Cα(s).Source: §1 · p. 1
• The rate-transfer method recovers classical SGD rates and the familiar geometric transient with an O(h) neighbourhood for stochastic Heavy Ball, without improving those known rates.Both examples obtain their rates through the same continuous-time Lyapunov calculation and finite-window transfer argument.Source: §1 · p. 2
• The method aims to replace bespoke discrete-time proofs with an associated SDE Lyapunov inequality and a comparatively short calculus argument for new stochastic gradient methods.The paper also says the approach extends to other forms of Lyapunov analysis.Source: §1 · p. 2

1.1 Related work.

• Earlier ODE and diffusion approaches use continuous models to study stochastic recursions, while diffusion-limit analyses target weak convergence of normalized errors rather than finite-time iteration-wise bounds.The ODE viewpoint is associated with Ljung [1977] and Kushner [1977]; the cited diffusion-limit work includes Kushner and Huang [1979, 1981].Source: §1.1 · p. 2
• To retain useful SDE estimates over arbitrarily long times despite finite-horizon approximation accuracy, the method uses weak Lyapunov comparisons on fixed windows and restarts the SDE from the current iterate.The local comparison error enters as additional forcing, while the Lyapunov function attenuates errors from earlier windows.Source: §1.1 · p. 2

2.1 Notation

• The notation defines derivatives of the drift, columns of the noise factor, and polynomial weights used to express growth.Db and higher derivatives denote multilinear maps; ⟨⟨x⟩⟩p denotes a polynomial weight of order p.Source: §2.1 · p. 3

2.2 Stochastic approximation

• The stochastic-approximation setup uses adapted iterates, deterministic stepsizes, and a diffusion-time clock that grows without bound.The noise has conditional mean zero and covariance A(Xn)=σ(Xn)σ(Xn)⊤; NT(m) marks the iteration after T diffusion-time units have passed.Source: §2.2 · p. 3

2.3 The associated SDE

• The associated SDE matches the recursion’s local drift and covariance scales, and its restarted solutions support comparisons over fixed diffusion-time windows.At each block boundary, the comparator restarts from the current iterate; the stochastic approximation itself continues normally.Source: §2.3 · p. 3

2.4 Lyapunov bounds for the associated SDE

• The SDE Lyapunov generator inequality yields a finite-time bound combining contraction R(s,t) with accumulated forcing g(t).V measures application-specific error or energy, while λ describes contraction and g the residual forcing.Source: §2.4 · p. 4

2.5 The finite-window transfer mechanism

• Restarting the SDE comparator at successive block boundaries propagates its contraction across windows and attenuates earlier approximation errors, avoiding accuracy requirements over a growing horizon.The transfer compares the Lyapunov observable directly; under the theorem’s bounded-contraction condition, approximation costs act as additional forcing Cα(s).Source: §2.5 · p. 5

3 Rate transfer under primitive assumptions

• The framework separates primitive finite-window assumptions from the global moment bound required for the theorem’s all-iteration conclusion.An SDE-based sufficient condition for that moment bound is developed in Section 3.3.Source: §3 · p. 6, §3.1 · p. 6

3.1 Primitive assumptions

• The primitive assumptions include C3 drift and diffusion coefficients and smoothness and moment conditions used for finite-window comparison.These conditions do not themselves include the global moment bound required for the all-iteration conclusion.Source: §3.1 · p. 6

3.2 Main rate-transfer theorem

• Theorem 2 gives a finite-time SGD bound under Assumption 1 and, for its all-iteration conclusion, additionally requires a uniform p-th moment bound and an SDE Lyapunov condition.The theorem’s fixed-window constants may depend on the window and moment constants.Source: §3.2 · p. 6

3.3 Stability from the associated SDE

• A Foster–Lyapunov inequality for the associated SDE can transfer stability to the stochastic-approximation iterates and supply the required moment bound.When the natural SDE Lyapunov function controls a lower-order moment, power lifting constructs an auxiliary function for the required p-th moment.Source: §3.3 · p. 7

4.1 How to apply the method

• Construct the associated SDE by matching drift and covariance to one stochastic-approximation step, establish its Lyapunov bound, verify regularity and moment conditions, then apply the transfer theorem.If a uniform moment bound is not immediate, the section suggests deriving it from a Foster–Lyapunov inequality, with power lifting when a higher moment is needed.Source: §4.1 · pp. 7–8

4.2 Strongly convex stochastic gradient descent

• For strongly convex SGD, the quadratic error Lyapunov function gives λ = 2µ and forcing g(t) = tr(Σ)α(t); the required moment bound follows from the stated assumptions and moment argument.The setup uses b(x) = −∇f(x), constant diffusion factor Σ^1/2, and a uniform moment bound from Proposition 3.Source: §4.2 · pp. 8–9
• For power-law stepsizes with 0 < ϑ < 1, the rate calculation uses λ = 2µ and δ = 1; at ϑ = 1, the harmonic regimes depend on whether 2µa is greater than, equal to, or less than 1.The resulting rate agrees with classical strongly convex SGD analyses, including Moulines and Bach.Source: §4.2 · p. 9

4.3 Stochastic Heavy Ball

• For stochastic Heavy Ball, the state is position and velocity, and the section uses an energy Lyapunov function under strong convexity, smoothness, bounded third derivative, and sufficiently small step size.The initial energy moment condition is E(1 + W(X0, V0))^3/2 < ∞.Source: §4.3 · pp. 9–10
• With constant step h, Heavy Ball has a geometric transient and persistent noise leaves an O(h) neighbourhood; the transfer constant is uniform in n and over sufficiently small h.The SDE forcing is g(t) = ς^2h/2.Source: §4.3 · p. 10

5 Conclusion and extensions

• Weak comparison on fixed diffusion-time windows, with the continuous comparator restarted across windows, carries contraction without requiring a growing-horizon SDE approximation.The finite-window comparison error enters the transferred estimate as an additional forcing term.Source: §5 · p. 10
• The theorem’s proof template can also cover monotone Robbins–Monro schemes, contractive fixed-point recursions, stable linear stochastic approximation, and other recursions with a suitable finite-dimensional SDE Lyapunov function, once moment and regularity conditions are verified.The paper omits these further examples to keep its focus on the transfer mechanism.Source: §5 · p. 10
• More general dissipation inequalities, higher-order stochastic modified equations, path-space and hitting-time quantities, Markovian noise, adaptive clocks, and two-timescale recursions require theorem extensions beyond the first-order rate-transfer result.The authors leave these directions for future work.Source: §5 · p. 10

A Finite-window comparison

• The appendix establishes the primitive finite-window comparison from restarted-SDE estimates and one-step weak comparison.Source: A Finite-window comparison · p. 12

A.1 Additional notation and conventions

• For a k-linear map A, A[v1, …, vk] denotes its evaluation at those arguments.Source: §A.1 · p. 12
• The notation f ≍p g means the nonnegative quantities are bounded above and below by constant multiples depending only on p.Source: §A.1 · p. 12
• Polynomial weights are monotone in their exponent, and an empty product equals 1; the exponents γ, γ1, γ2, … are local to the statement where introduced.The notation f = OT(g) denotes an upper bound by a constant multiple of g under the same convention.Source: §A.1 · p. 12

A.2 First-order local-to-window approximation

• The transfer theorem uses both the SDE Lyapunov bound and finite-window approximation to produce a finite-time bound for the stochastic approximation.Source: §A.2 · p. 13
• The Lyapunov bound is a generator inequality that can typically be checked by calculus from the SDE coefficients, whereas finite-window approximation describes the stochastic approximation–SDE relationship over a fixed diffusion-time window.Source: §A.2 · p. 13
• The section verifies finite-window approximation from basic regularity and moment conditions on the stochastic approximation and SDE.Source: §A.2 · p. 13

A.2.1 Primitive finite-window verification

• Global Lipschitzness and αmax < ∞ ensure the associated SDE is well posed for every restart.The diffusion coefficient α(t)σ(x) is uniformly Lipschitz in x and has linear growth, yielding a unique nonexplosive strong solution on every finite interval.Source: §A.2.1 · p. 13
• Global Lipschitzness is sufficient, not minimal; weaker local conditions are not pursued here.Polynomially growing coefficients can be handled under nonexplosion and sufficiently strong fixed-window polynomial moment bounds.Source: §A.2.1 · p. 13

A.2.2 Primitive finite-window comparison

• The body theorem states the finite-window comparison directly from the primitive assumptions.The appendix proves that comparison before applying the abstract restart result.Source: §A.2.2 · p. 13
• The finite-window comparison supplies the input to the abstract restart result for the global conclusion.The proposition's proof is given at the end of Section A.2.3.Source: §A.2.2 · p. 13
• The proof of the comparison is located in Section A.2.3.This is the stated proof location for the result.Source: §A.2.2 · p. 13

A.2.3 Proof of the finite window approximation

• An O(α2 k) defect between the two one-step approximations sums over the diffusion-time window to give the required finite-window comparison.The comparison applies both one-step approximations to the backward function and uses their shared first-order term.Source: §A.2.3 · p. 13
• The linear energy estimate controls the relevant process moments without requiring an operator-norm bound on its drift matrix.Its proof localizes the process, applies Itô’s formula, uses BDG and Gronwall inequalities, and removes stopping by Fatou’s lemma.Source: §A.2.3 · pp. 14, 17
• If b and σ are C1 and satisfy global Lipschitz condition (11), with αmax < ∞, then for every fixed S > 0 and finite p > 0, restarted-SDE state moments are bounded uniformly over starting time s and initial state x.Source: §A.2.3 · p. 17
• For fixed windows, the restarted semigroup is C2 and its gradient and Hessian obey polynomial-growth bounds uniform in the window’s starting time, endpoint, and initial state.State moments and first- and second-variation moments control these derivatives, yielding the growth hypotheses needed by the Taylor lemma.Source: §A.2.3 · pp. 13, 17, 18
• The flow argument obtains C2 dependence through localization and composition across finitely many intervals where α is piecewise constant; quantitative estimates use only first- and second-derivative bounds.The stated standard setting assumes globally Lipschitz C3 coefficients, with polynomial growth allowed for second derivatives.Source: §A.2.3 · pp. 14, 19

• The additional C3 coefficient assumption permits direct use of the C2 flow theorem; with only C2 coefficients, finite differences could construct the second spatial variation, but require a longer proof.Source: §A.2.3 · p. 19
• Moment bounds for the state, Jacobian, and second variation justify differentiation under expectation, yielding C2 semigroup regularity and polynomial gradient and Hessian bounds.Source: §A.2.3 · p. 21
• The Taylor-remainder argument uses Hessian growth for small increments and gradient growth along the segment for large increments, avoiding a higher power of the increment.Source: §A.2.3 · p. 22
• The fixed-window Dynkin formula is justified by stopping on bounded balls, using polynomial derivative and moment bounds, and removing the stopping via dominated convergence.Source: §A.2.3 · pp. 23–24
• The finite-window approximation holds with ϵ_m = 0 and ρ(s) = C_T M_pα(s); for nonincreasing stepsizes, the endpoint bound is C_T α_m⟨⟨X_m⟩⟩^p.Source: §A.2.3 · pp. 26–27
• The proof applies the SDE approximation and conditional Taylor bound to the same backward function, then telescopes the one-step defects across the finite window.Source: §A.2.3 · pp. 26–27

B Proof of the Rate Transfer Theorem

• The proof develops the abstract restart result and primitive comparison separately, then combines them to prove the Rate Transfer Theorem and Theorem 2.The appendix applies the abstract transfer result under the Lyapunov hypothesis.Source: B Proof of the Rate Transfer Theorem · p. 27
• The transfer theorem uses an SDE Lyapunov bound and a finite-window approximation comparing the stochastic approximation with the SDE.These are identified as the two main conditions to verify in applications.Source: B Proof of the Rate Transfer Theorem · p. 27
• The endpoint transfer theorem combines a Lyapunov generator inequality for the restarted SDE with a mean finite-window approximation.The theorem concerns the stochastic approximation over fixed diffusion-time windows.Source: B Proof of the Rate Transfer Theorem · p. 27
• The restarted process has an evolution family with a composition property used repeatedly in the proof.The passage also introduces a scalar Lyapunov factor.Source: B Proof of the Rate Transfer Theorem · p. 27
• The endpoint transfer route combines a continuous estimate with a finite-window comparison.Source: B Proof of the Rate Transfer Theorem · p. 27

B.1 Lyapunov-envelope and endpoint transfer

• The transfer theorem composes an SDE Lyapunov bound with a finite-window approximation between the SDE and stochastic approximation.The proof uses the continuous-time estimate and a general finite-window residual over successive restart windows.Source: §B.1 · pp. 27–28
• A generator Lyapunov inequality yields the finite-time SDE evolution-operator estimate used in the transfer argument.The finite-time envelope is the continuous-time input to the blockwise transfer.Source: §B.1 · pp. 28–29
• The general blockwise result transfers the restarted SDE bound to the stochastic approximation using a one-sided finite-window comparison and its residuals.The endpoint bound is assembled across restart windows, including the final partial interval.Source: §B.1 · p. 29
• A fixed step yields an O(h^δ) neighborhood, while subharmonic power-law steps have stretched-exponential contraction and harmonic rates depend on competing decay exponents.At the harmonic boundary, the schedule and contraction forcing both decay polynomially.Source: §B.1 · p. 31
• The applications recover classical strongly convex SGD rates and the stochastic Heavy Ball geometric transient with an O(h) neighborhood.These examples illustrate rate recovery rather than an improvement over the known rates.Source: §B.1 · p. 31

C Stability from the associated SDE

• Once the stepsize is small enough, the Taylor argument gives a uniform bound on EΦ(Xn), and coercivity yields a uniform pth-moment bound.No smallness condition is needed for the finite initial segment before that tail argument starts.Source: C Stability from the associated SDE · p. 32
• Power lifting raises a coercive Lyapunov function W of growth order p0 to Φ = (1 + W)^r, where r = p/p0.The construction targets a Lyapunov function with growth comparable to the pth moment.Source: C Stability from the associated SDE · p. 33
• Under the tail drift condition and global Lipschitz noise, the lifted generator bound absorbs its Cα(t)Φ term when α(t) is sufficiently small.The resulting inequality has negative drift plus a constant.Source: C Stability from the associated SDE · p. 33