PaperlayerView exact revision on arXiv

Source-linked AI summary

Understanding the Acceleration Phenomenon via High-Resolution Differential Equations

Bin Shi, Simon S. Du, Michael I. Jordan, Weijie J. Su

arXiv:1810.08907v3math.OCcs.LGmath.CAmath.NAstat.ML

TL;DR

Existing low-resolution ODEs omit NAG-SC’s gradient correction, obscuring its distinction from heavy-ball dynamics. The paper develops high-resolution ODEs and shows that gradient correction is critical to acceleration while NAG-C minimizes squared gradient norms faster than expected.

  • Problem

    Existing low-resolution ODEs omit NAG-SC’s gradient correction, while its role in distinguishing NAG-SC from heavy-ball remains unclear.

    Source: §1.1 · p. 4

  • Method

    The paper derives high-resolution ODEs, constructs continuous and discrete Lyapunov functions, and translates their properties to the original algorithms.

    Source: §2 · p. 8

  • Results

    High-resolution ODEs more faithfully model heavy-ball, NAG-SC, and NAG-C, identify gradient correction as critical to NAG-SC’s acceleration, and show faster-than-expected squared-gradient-norm minimization for NAG-C.

    Source: §6 · p. 32

  • Takeaways & Limitations

    The framework offers a tool for understanding, analyzing, and generalizing first-order optimization methods within smooth convex settings.

    Source: §6 · p. 32

    Whether the constraint on further leveraging gradient correction is a technical artifact or fundamental to acceleration remains an open question.

    Source: §5.1 · p. 30

Abstract

from arXiv · show

Gradient-based optimization algorithms can be studied from the perspective of limiting ordinary differential equations (ODEs). Motivated by the fact that existing ODEs do not distinguish between two fundamentally different algorithms---Nesterov's accelerated gradient method for strongly convex functions (NAG-SC) and Polyak's heavy-ball method---we study an alternative limiting process that yields high-resolution ODEs. We show that these ODEs permit a general Lyapunov function framework for the analysis of convergence in both continuous and discrete time. We also show that these ODEs are more accurate surrogates for the underlying algorithms; in particular, they not only distinguish between NAG-SC and Polyak's heavy-ball method, but they allow the identification of a term that we refer to as "gradient correction" that is present in NAG-SC but not in the heavy-ball method and is responsible for the qualitative difference in convergence of the two methods. We also use the high-resolution ODE framework to study Nesterov's accelerated gradient method for (non-strongly) convex functions, uncovering a hitherto unknown result---that NAG-C minimizes the squared gradient norm at an inverse cubic rate. Finally, by modifying the high-resolution ODE of NAG-C, we obtain a family of new optimization methods that are shown to maintain the accelerated convergence rates of NAG-C for smooth convex functions.

1 Introduction

The paper develops high-resolution ODEs to explain why NAG-SC globally accelerates while heavy-ball may fail, highlighting gradient correction as the essential distinction. It also derives sharper NAG-C guarantees and places the framework within prior continuous-time optimization research.

1 Introduction

  • First-order optimization dominates large-scale machine learning, while heavy-ball improves local convergence but lacks global guarantees and can fail even for strongly convex functions.Nesterov’s methods instead achieve optimal accelerated rates for smooth strongly convex and smooth convex objectives, respectively [Nes83, Nes13, NY83].Source: §1 · pp. 1, 3

1.1 Gradient Correction: Small but Essential

  • NAG-SC’s gradient correction contrasts gradients at consecutive iterates; despite close update forms, heavy-ball oscillates throughout the iterations, whereas NAG-SC is monotone in function value once the iteration counter exceeds 50.The correction is O(s1.5), so it is not reflected in the low-resolution ODE obtained by taking s → 0; existing continuous-time formulations give both methods the same limiting ODE [WRJ16].Source: §1.1 · pp. 3–4

1.2 Overview of Contributions

  • High-resolution ODEs retain O(√s) terms, distinguish NAG from heavy-ball, better match discrete trajectories, and preserve NAG-SC’s non-oscillation pattern.The NAG-SC correction appears as √s∇^2f(X(t))Ẋ(t), producing adaptive damping that can reduce oscillations in high-curvature directions.Source: §1.2 · pp. 5–7
  • For smooth convex objectives, the high-resolution NAG-C analysis yields an inverse cubic rate for minimizing the squared gradient norm, enabled by a sharper Lyapunov decrease from gradient correction.The resulting bound cannot be obtained from the corresponding low-resolution Lyapunov function [SBC16].Source: §1.2 · p. 7

1.3 Related Work

  • The paper builds on ODE, Lagrangian, Hamiltonian, mirror-descent, control-theoretic, and geometric approaches to acceleration, then organizes its framework across strongly convex, convex, and NAG-C extension analyses.Most technical proofs are deferred to the Appendix.Source: §1.3 · pp. 7–8, §1.4 · p. 8

2 The High-Resolution ODE Framework

The framework derives high-resolution ODEs, analyzes them with continuous Lyapunov functions, transfers those functions discretely, and maps the resulting properties back to optimization algorithms. It exposes NAG-specific gradient correction and recovers accelerated convergence guarantees, including an inverse-cubic squared-gradient rate for NAG-C.

2 The High-Resolution ODE Framework

  • The four-step framework derives a high-resolution ODE, constructs a continuous Lyapunov function, derives its discrete counterpart, and transfers ODE properties to the original algorithm.The framework is illustrated in Figure 3, which emphasizes that direct construction of discrete Lyapunov functions can be difficult.Source: §2 · p. 8, Figure 3 · p. 9

Step 1: Deriving High-Resolution ODEs

  • High-resolution derivations retain O(√s) terms, including the Hessian-driven gradient correction in NAG-SC and NAG-C but not in the heavy-ball method.Under mild objective conditions, the associated ODEs have unique global solutions and approximate their algorithms when s is small.Source: Step 1: Deriving High-Resolution ODEs · p. 10

Step 2: Analyzing ODEs Using Lyapunov Functions

  • A Lyapunov function for NAG-SC decreases exponentially along ODE trajectories, recovering its accelerated linear convergence rate and linking acceleration to gradient correction.The comparison with heavy-ball Lyapunov functions explains why the Hessian-driven correction produces acceleration for NAG-SC.Source: Step 2: Analyzing ODEs Using Lyapunov… · p. 11

Step 3: Constructing Discrete Lyapunov Functions

  • A phase-space representation replaces continuous position and velocity terms with discrete counterparts, yielding a discrete Lyapunov function with potential, kinetic, and mixed-energy components.The resulting updates have a symplectic-discretization flavor, with explicit position and implicit velocity updates.Source: Step 3: Constructing Discrete Lyapunov… · pp. 11–12

Step 4: Analyzing Algorithms Using Discrete Lyapunov Functions

  • The discrete Lyapunov analysis recovers NAG-SC’s optimal linear rate and shows that NAG-C minimizes the squared gradient norm at an inverse cubic rate.These conclusions follow by translating high-resolution ODE properties into discrete Lyapunov-function decrease rates.Source: Step 4: Analyzing Algorithms Using… · p. 12

3 Gradient Correction for Acceleration

This section uses high-resolution ODEs, Lyapunov functions, and numerical-stability analysis to distinguish NAG-SC from heavy-ball and examine gradient correction in continuous and discrete algorithms. It identifies gradient correction as central to acceleration and links it to a larger stable step size.

3 Gradient Correction for Acceleration

  • Gradient correction, present in NAG-SC but absent from heavy-ball, is identified as the key mechanism behind their different convergence behavior.In the ODE, it appears through the term 1−√s∇²f(X)Ẋ; in the discrete analysis, it enables NAG-SC to use a larger step size.Source: §3 · p. 12, §3.1 · p. 15, §3.2 · p. 19

3.1 The ODE Case

  • For f ∈ S^2_{μ,L}(R^n) and 0 < s ≤ 1/L, the high-resolution NAG-SC ODE converges linearly in function value.With s = 1/L, the bound includes 2L∥x_0−x⋆∥^2 e^−…; the Lyapunov analysis exposes the gradient-correction term’s role.Source: §3.1 · pp. 12–13

3.2 The Discrete Case

  • For the discrete methods, NAG-SC attains the optimal accelerated rate with s = 1/(4L), whereas heavy-ball has a non-accelerated global rate with s = μ/(16L^2).The heavy-ball rate is stated as log(f(x_k)−f(x⋆)) ≤ −O(kμ/L), compared with NAG-SC’s optimal −O(k√(μ/L)); the gradient correction permits NAG-SC’s larger step size.Source: §3.2 · pp. 16, 18, 19

3.3 A Numerical Stability Perspective on Acceleration

  • The section further examines gradient correction through numerical stability, asking which step sizes allow stable forward-Euler discretizations of the two high-resolution ODEs.The discussion is motivated by the view that gradient correction fundamentally causes the convergence-rate difference and focuses on forward Euler for simplicity.Source: §3.3 · p. 20
  • The worst-case stability analysis constrains the step size according to the smoothness bound L on the Hessian of f.The analysis uses the fact that the largest singular value of the Hessian can be as large as L.Source: §3.3 · p. 20
  • For the NAG-SC high-resolution ODE, the forward Euler characteristic equation yields a stability condition that is ensured by an appropriate step-size choice.These constraints agree with the earlier step-size discussion, although they arise from a numerical-stability perspective.Source: §3.3 · p. 21
  • NAG-SC’s Hessian correction enables forward Euler stability with the larger step size s = O(1/L), highlighting its importance for acceleration.The comparison of the two discretizations provides another numerical-stability interpretation of the gradient correction’s role.Source: §3.3 · p. 21

4 Gradient Correction for Gradient Norm Minimization

The high-resolution ODE framework shows that NAG-C minimizes the squared gradient norm at the sharp rate O(L2/k3), with gradient correction responsible for the improvement. The same rate holds for a modified accelerated method, while phase-space representations simplify the original method’s analysis.

4.1 The ODE Case

  • The high-resolution ODE yields an inverse-cubic squared-gradient-norm rate through a Lyapunov function containing a gradient-correction term absent from the low-resolution ODE.The low-resolution framework therefore cannot provide an analogous O(L/t3) result, according to the section’s discussion.Source: §4.1 · pp. 22–23

4.2 The Discrete Case

  • NAG-C achieves the O(L2/k3) rate for squared-gradient-norm minimization without modification, and gradient correction is responsible for this rate.This improves on the O(L2/k2) bound obtained directly from function-value convergence and is sharper than existing unmodified NAG-C bounds described here.Source: §4 · p. 21, §4.2 · p. 24
  • In discrete time, the Lyapunov analysis proves the same O(L2/k3) rate for NAG-C with step size s = 1/(3L), without additional iterates or adjusted step-size policies.The result is supported by numerical examples in Figure 4, where the scaled squared gradient norm stays bounded as k →∞.Source: §4.2 · p. 24, Figure 4 · p. 25

4.3 A Modified NAG-C without a Phase-Space Representation

  • A modified NAG-C method also achieves O(L2/k3) for squared-gradient-norm minimization and has the same convergence rates as NAG-C.Because both f(xk) and f(yk) appear in its iteration, the modified method lacks a phase-space representation and requires a more complex Lyapunov construction.Source: §4.3 · pp. 28–29

5 Extensions

Section 5 develops generalized high-resolution ODEs and discretized accelerated methods for smooth convex minimization. The generalized NAG-C matches original convergence rates, while its super-critical regime achieves faster function-value convergence than O(1/(s k^2)).

5 Extensions

  • The section introduces generalized high-resolution ODEs motivated by NAG-C and discretizes them into a family of accelerated methods for smooth convex functions.The analysis focuses on friction parameter α ≥ 3 and gradient-correction parameter β > 0.Source: §5 · p. 29

5.2 Faster Convergence in Super-Critical Regime

  • For α > 3, generalized NAG-C converges to the optimum faster than O(1/(s k^2)) in function value.The theorem establishes this faster rate under the same assumptions as the preceding proposition, while examples show that the stronger asymptotic behavior need not hold universally.Source: §5 · p. 29, §5.2 · p. 31

5.1 Convergence Rates

  • The generalized NAG-C achieves the same convergence rates as original NAG-C for both squared gradient norm and function-value minimization.The result uses step sizes 0 < s ≤ cα,β/L, with constants depending only on α and β; the stated analysis requires β > 1, while β = 1 recovers original NAG-C.Source: §5.1 · p. 30

5.2 Faster Convergence in Super-Critical Regime

  • The faster-rate proof applies to a broader class of methods than earlier low-resolution-ODE analyses, which established o(1/k^2) only for β = 1.Its argument combines the high-resolution ODE framework with finiteness of a series from Proposition 5.1.Source: §5.2 · p. 31
  • Numerical studies support the super-critical prediction but indicate that convergence can be slow for some problems.The scaled-error curves in Figure 5 slowly tend to zero, while the simulations described for Figure 6 imply slow convergence in some cases.Source: Figure 5 · p. 31, §5.2 · p. 32, Figure 6 · p. 32
  • The generalized NAG-C may admit an improved squared-gradient-norm rate, but confirming or disproving this asymptotic possibility remains open.The passage presents the improved rate as a conjectural implication rather than an established theorem.Source: §5.2 · p. 32

6 Discussion · A Technical Details in Section 2 · A.1 Derivation of High-Resolution ODEs

The paper presents high-resolution ODEs as faithful tools for analyzing and generalizing heavy-ball, NAG-SC, and NAG-C, while identifying gradient correction as central to acceleration and motivating extensions beyond smooth convex optimization. A Lyapunov-function framework translates these continuous-time findings to discrete methods through a phase-space representation, and the appendix derives the heavy-ball and NAG-C ODEs by asymptotic expansion.

6 Discussion

  • High-resolution ODEs more faithfully model heavy-ball, NAG-SC, and NAG-C, revealing gradient correction as critical to NAG-SC’s acceleration and NAG-C’s faster squared-gradient-norm rate.The framework also suggests a new family of methods with NAG-C’s optimal convergence rates.Source: §6 · p. 32
  • A phase-space Lyapunov framework translates continuous-time ODE properties into discrete-time guarantees for the three optimization methods.The transformation links continuous position and velocity variables to their discrete counterparts.Source: §6 · p. 33
  • The framework suggests studying an interpolation algorithm corresponding to 0 < β < 1 between heavy-ball at β = 0 and NAG-SC at β = 1.Further directions include applying alternative discretization schemes to high-resolution ODEs and incorporating higher-order powers of √s.Source: §6 · p. 33
  • Possible extensions include high-resolution ODEs for mirror descent [WWJ16], differential inclusions for non-smooth optimization, and stochastic differential equations for stochastic optimization [KB17, HLLL17, LTE17, LS17, XWG18, HMC+18, GGZ18].The framework may also characterize local first-order-method behavior near non-convex saddle points [JGN+17] [DJL+17] [HLS17] and support approximate-stationary-point analysis [CDHS17a] [CDHS17b] [AZ18].Source: §6 · p. 33

A.1 Derivation of High-Resolution ODEs

  • The technical appendix formally derives high-resolution ODEs for the heavy-ball method and NAG-C using a continuous interpolation of their iterate sequences.It sets t_k = k√s and uses a sufficiently smooth map X(t) over the relevant time domains.Source: §A.1 · p. 37
  • For heavy-ball, substituting the interpolation expansion and ignoring O(s) terms yields the stated high-resolution ODE (1.10).The derivation proceeds by rearranging the discrete update and inserting the expansion from (2.1).Source: §A.1 · p. 37
  • For NAG-C, substituting the corresponding expansion and ignoring O(s) terms yields the stated high-resolution ODE (1.12).The derivation follows the analogous rearrangement and substitution steps for the NAG-C update.Source: §A.1 · p. 37

A.2 Derivation of Low-Resolution ODEs · A.3 Solution Approximating Optimization Algorithms

The appendix derives low-resolution ODEs for NAG-SC, heavy-ball, and NAG-C, showing that NAG-SC and heavy-ball collapse to the same low-resolution dynamics despite NAG-SC’s gradient correction. It then relates the high-resolution dynamics to a step-size-indexed family whose zero-step-size case is the corresponding low-resolution ODE.

A.2 Derivation of Low-Resolution ODEs

  • The section derives low-resolution ODEs for accelerated gradient methods using second-order Taylor expansions at neighboring iterates.The derivation is presented as a literature-based comparison for ease of reading.Source: §A.2 · pp. 37–38
  • NAG-SC’s low-resolution ODE is obtained by substituting the Taylor expansions into its equivalent discrete form and taking s → 0.Source: §A.2 · p. 38
  • The heavy-ball method’s low-resolution ODE is derived analogously from its equivalent discrete form by taking s → 0.Source: §A.2 · p. 38
  • NAG-SC and heavy-ball share the same low-resolution ODE, so this approximation fails to retain NAG-SC’s gradient-correction information.Source: §A.2 · p. 38
  • NAG-C likewise yields its low-resolution ODE by inserting the Taylor expansions into its equivalent form and taking s → 0.The resulting ODE is reported as the same as [SBC16].Source: §A.2 · p. 38

A.3 Solution Approximating Optimization Algorithms

  • The low-resolution ODE is the s = 0 special case of the high-resolution ODE, and the analysis therefore considers solutions Xs(t) across a family indexed by step size s.Source: §A.3 · p. 39

A.3.1 Proof of Proposition 2.1

The proof establishes global existence and uniqueness for the high-resolution ODEs of heavy-ball and NAG-SC, then shows their approximation to the low-resolution ODE over any fixed time interval.

Global Existence and Uniqueness

  • Both high-resolution ODEs have unique global solutions X ∈ C2(I; Rn) under the stated smoothness and strong-convexity conditions.The result follows by phase-space representations, Lipschitz conditions, and the classical global existence and uniqueness theorem.Source: §A.3.1 · pp. 39–40

Approximation

  • A Lyapunov-function argument bounds the gradient norm along solutions of both high-resolution ODEs.The same boundedness property is used in the subsequent approximation analysis.Source: §A.3.1 · pp. 39–40
  • For every fixed T > 0, the high-resolution solutions of heavy-ball and NAG-SC approximate the low-resolution ODE solutions.Lemma A.2 proves the approximation separately for heavy-ball and NAG-SC using phase-space representations, boundedness, and Gronwall’s inequality.Source: §A.3.1 · pp. 41–42
  • Consequently, heavy-ball and NAG-SC converge to the low-resolution ODE (1.9) on any fixed time interval.This conclusion is stated in Lemma A.4 and completes the proof of Proposition 2.1 together with the preceding results.Source: §A.3.1 · p. 42

A.3.2 Proof of Proposition 2.2 · A.4 Closed-Form Solutions for Quadratic Functions · B Technical Details in Section 3

The appendices establish global well-posedness and low-resolution approximation for the high-resolution ODEs, then derive quadratic closed forms that clarify oscillations, convergence, and special-function structure.

A.3.2 Proof of Proposition 2.2

  • The high-resolution ODE (1.12) has a unique global solution X ∈ C2(I; Rn) under the stated phase-space and Lipschitz conditions.The proof combines a phase-space representation, Theorem 11, and Lyapunov-function bounds.Source: §A.3.2 · pp. 43–44
  • For any fixed T > 0, solutions of the high-resolution ODE converge to the corresponding low-resolution ODE, completing Proposition 2.2.Lemma A.6 establishes the approximation, while Lemma A.7 supplies the NAG-C convergence statement.Source: §A.3.2 · pp. 45–46

A.4 Closed-Form Solutions for Quadratic Functions

  • Closed-form solutions are derived for all three high-resolution ODEs and compared with their low-resolution counterparts for quadratic objectives.The comparison is designed to expose their key differences.Source: §A.4 · p. 46

A.4.1 Oscillations and Non-Oscillations

  • For NAG-SC and heavy-ball, low-resolution quadratic solutions oscillate except at θ = µ, whereas high-resolution NAG-SC converges faster and is non-oscillatory when s ≥2.The high-resolution NAG-SC solution is always faster than the corresponding low-resolution rate.Source: §A.4.1 · p. 48

A.4.2 Kummer’s Equation and Confluent Hypergeometric Function

  • The low-resolution NAG-C quadratic solution is expressed through Bessel functions and yields an asymptotic estimate.This closed form was previously proposed in [SBC16].Source: §A.4.2 · pp. 48–49
  • The high-resolution NAG-C quadratic equation transforms into Kummer’s equation and admits an analytic solution using confluent hypergeometric functions.The solution uses the first- and second-kind functions M(·, ·, ·) and U(·, ·, ·).Source: §A.4.2 · p. 49
  • For high-resolution NAG-C, the quadratic asymptotic behavior is characterized separately for s < 4/θ and s ≥4/θ, with the upper bound guaranteed when s < 4/L.These regimes follow from the sign of sθ^2 −4θ.Source: §A.4.2 · pp. 49–50

B.1 Proof of Lemma 3.2 · B.2 Completing the Proof of Lemma 3.4 · B.2.1 Derivation of (3.16)

The appendix proves Lemma 3.2 by estimating Lyapunov function (3.3) and its derivative along the high-resolution ODE (1.10), then derives (3.16) under s ≤ 1/L to complete the related proof.

B.1 Proof of Lemma 3.2

  • The proof applies the Cauchy–Schwarz inequality to estimate Lyapunov function (3.3).Source: §B.1 · p. 50
  • Along solutions of high-resolution ODE (1.10), the time derivative of Lyapunov function (3.3) is computed.Source: §B.1 · p. 50
  • The derivative estimate provides the bound needed in the Lyapunov argument.Source: §B.1 · p. 50
  • These estimates complete the proof of Lemma 3.2.Source: §B.1 · p. 50

B.2 Completing the Proof of Lemma 3.4

  • The estimates from Lemma 3.2 are used within the completion of the proof of Lemma 3.4.Source: §B.1 · p. 50

B.2.1 Derivation of (3.16)

  • The derivation of (3.16) uses (B.2) together with the basic inequality for f(x) ∈ S1.Source: §B.2.1 · p. 51

B.2.2 Derivation of (B.2) … C.1.4 Estimate for Lyapunov function E(2) and E(3)

The technical appendices derive discrete Lyapunov estimates by decomposing energies and applying phase representations, convexity, and Cauchy–Schwarz inequalities. They also establish finite-iterate estimates for gradient norms, function values, and Lyapunov quantities under the stated step-size condition.

B.2.2 Derivation of (B.2)

  • B.2.2 derives the difference of Lyapunov function (2.6) by separately evaluating potential, kinetic, and mixed-energy components, then merging the resulting terms.The derivation identifies an additional perfect-square term before obtaining the final Lyapunov difference.Source: §B.2.2 · pp. 52, 55

B.3 Proof of Lemma 3.5

  • B.3 proves the heavy-ball Lyapunov estimate by decomposing its function into potential, kinetic, and mixed-energy parts and comparing the resulting coefficients.The proof uses the heavy-ball phase representation, convexity, and Cauchy–Schwarz inequality.Source: §B.3 · pp. 56, 57, 59

C Technical Details in Section 4

C.1.2 Estimate For ∥∇f(xk)∥2 at k = 0, 1, 2, 3

  • The cited text states that relations (C.1)–(C.3) are used together and includes expressions 200L2s2(1 + L2s2) + 147 and 1 + L2s2 + 729.Source: §C.1.2 · p. 60

C.1.4 Estimate for Lyapunov function E(2) and E(3)

  • The C.1.4 appendix bounds Lyapunov functions E(2) and E(3) using the phase-space representation, prior estimates, and Cauchy–Schwarz inequality.The resulting polynomial contains terms through L6s6, and Lemma 4.3 applies when s ≤1/(3L).Source: §C.1.4 · p. 61

C.2 Proof of Theorem 7 … D.1.2 Case: β ≥1

The appendices prove the main convergence results using discrete and continuous Lyapunov constructions, establish Nesterov’s lower bound, and analyze the α = 3 family across β < 1 and β ≥ 1 cases.

C.2 Proof of Theorem 7

  • Theorem 7 is proved by constructing a discrete Lyapunov function whose decrease yields function-value and gradient-norm convergence bounds under an appropriate step size.The proof uses a tighter basic inequality for functions in F1 when s ≤ 1/L.Source: §C.2 · pp. 62–64

C.3 Nesterov’s Lower Bound

  • Nesterov’s lower-bound result supplies a function in F1 showing that any first-order method obeys the stated lower bound for 1 ≤ k ≤ (1/2)(n − 1).The construction applies for any initial point x0 ∈ Rn.Source: §C.3 · p. 64

D.1 Proof of Theorem 8: Case α = 3

  • For α = 3, the proof combines the generalized high-resolution ODE, a continuous Lyapunov function, and a phase-space representation to derive results analogous to Theorem 5 and Corollary 4.2.The detailed optimization of β and its effect on the initial point is left unspecified in the passage.Source: §D.1 · pp. 64–65

D.1.1 Case: β < 1

  • When β < 1, a discrete Lyapunov function decreases under a sufficient step-size condition, but β ≤ 1/2 cannot satisfy that condition for sufficiently large k.For 1/2 < β < 1, the analysis instead establishes the condition after a threshold k3,β.Source: §D.1.1 · pp. 65, 67

D Technical Details in Section 5

  • Across the α = 3 cases, the discrete analysis repeatedly estimates Lyapunov differences through the phase-space representation and controls gradient terms using step-size restrictions.These calculations provide the monotonicity needed for the case-specific convergence proofs.Source: §D.1.1 · p. 66, §D.1.2 · pp. 68–69

D.1.2 Case: β ≥1

  • When β ≥ 1, the constructed Lyapunov function is consistent with NAG-C at β = 1, and its decrease follows from the same sufficient step-size framework.For 1 ≤ β < 3, the proof establishes the step-size condition after a threshold k3,β; at β = 1, k3,β = 2 and consistency with (4.8) is recovered.Source: §D.1.2 · pp. 68–70

D.2 Proof of Theorem 8: Case α > 3 … D.4.1 The ODE Case

The appendix proves the super-critical α > 3 convergence results using generalized continuous and discrete Lyapunov functions, while a counterexample limits the faster-rate guarantee. The ODE analysis introduces a parameterized Lyapunov family and establishes the asymptotic limits needed for Theorem 12.

D.2 Proof of Theorem 8: Case α > 3

  • For α > 3, the proof uses the generalized high-resolution ODE and constructs continuous and discrete Lyapunov functions consistent with the α → 3 case.The discrete analysis evaluates Lyapunov differences through the phase-space representation and derives conditions ensuring decrease.Source: §D.2 · pp. 70–71
  • The resulting α > 3 analysis provides a stronger function-value convergence rate than Corollary 4.2, with the optimal constant β and its initialization effect left unspecified.The proof also separates the step-size analysis according to whether β > 1/2 and α < β or α ≥ β.Source: §D.2 · pp. 71, 73

D.3 A Simple Counterexample

  • A simple counterexample shows that Proposition 5.1 cannot guarantee the faster convergence rate.The counterexample is constructed explicitly in the appendix, although the supplied passage does not include its formula.Source: §D.3 · p. 74

D.4.1 The ODE Case

  • The super-critical ODE analysis introduces a Lyapunov function indexed by 2 < ν ≤ α − 1, recovering earlier Lyapunov functions at boundary parameter choices.For ν = α − 1 it reduces to (D.8), and as ν = α − 1 → 2 it reduces to (D.1); when ν = α − 1 = 2 and β = 1, it matches (4.1).Source: §D.4.1 · p. 74
  • For solutions of ODE (5.1) with α > 3 and β > 0, there exists a parameter-dependent threshold tα,β,ν after which the Lyapunov estimates yield Theorem 12’s stated bounds.The threshold depends only on α, β, and ν, and the proof derives the result from the Lyapunov derivative and integral estimates.Source: §D.4.1 · pp. 74–76
  • The ODE proof establishes existence of several asymptotic limits through Lemmas D.1–D.3 and uses them to control the trajectory and Lyapunov-function terms.The supplied passages identify these limits but do not reproduce their explicit formulas.Source: §D.4.1 · pp. 75–76
  • Theorem 12 follows by combining Lemmas D.1 and D.3 with the Cauchy–Schwarz inequality and then completing the two estimates in (D.14).The proof expands the generalized Lyapunov function and derives both equations of (D.14).Source: §D.4.1 · p. 77

D.4.2 Proof of Theorem 9

The proof establishes Theorem 9 by constructing a discrete Lyapunov function and controlling its decrease under suitable parameter and step-size conditions. Auxiliary limit lemmas then yield the key Lyapunov inequality and the sharper convergence rate.

D.4.2 Proof of Theorem 9

  • The discrete Lyapunov function combines potential, Euclidean-distance, and mixed-energy terms, recovering earlier forms in limiting parameter regimes.It is defined for 2 ≤ ν < α − 1; ν = α − 1 gives consistency with (D.10), while β = 1 and ν → 2 recovers (4.6).Source: §D.4.2 · p. 77
  • For β > 1/2, sufficiently large k, and step size 0 < s ≤ cα,β,ν/L, summing the component estimates controls the Lyapunov-function difference.The estimates separately analyze potential, Euclidean-distance, and mixed-energy contributions, with thresholds determined by kα,β,ν.Source: §D.4.2 · pp. 77, 78, 80, 81
  • Under Theorem 9’s assumptions, Lemmas D.4 and D.5 establish the required limits and series convergence, while bounded Lyapunov energy implies bounded iterates and auxiliary quantities.The proof uses monotonicity and translated auxiliary sequences to establish boundedness and complete Lemma D.5.Source: §D.4.2 · pp. 81–82
  • Combining Lemmas D.4 and D.5 yields both equations of (D.17), and consequently the proof obtains the sharper convergence rate stated in Theorem 9.The first equation follows directly from the two lemmas, and the second is obtained using Lemma D.4.Source: §D.4.2 · pp. 77, 82

Related papers

Loading 1810.08907v3…