MathDB

Nesterov acceleration asymptotic conjecture

Let ρ∈N\rho\in\mathbb{N}, and assume (A1) obtained from the preceding lemma. Let (ak)k⩾0(a_k)_{k\geqslant 0} be the sequence defined by the two Nesterov equations referred to in the source. Nesterov acceleration asymptotic conjecture. The sequence satisfies

ak∼cΓ(2ρ)2Γ(ρ)2⋅{Γ(ρ−ω)Γ(ω)Γ(4ρ−1−2ω)Γ(2ρ−1/2−ω)Γ(ρ+1/2−ω)22ρ−14ω⋅1k2ωif ω∈(0,ρ),122ρ−1log⁡kk2ρif ω=ρ,122ρ−1Γ(ω−ρ)1kω+ρif ω>ρ.a_k \sim c\frac{\Gamma(2\rho)^2}{\Gamma(\rho)^2}\cdot\left\{\begin{array}{ll}\displaystyle \frac{\Gamma(\rho-\omega)\Gamma(\omega)}{\Gamma(4\rho-1-2\omega)}\frac{\Gamma(2\rho-1/2-\omega)}{\Gamma(\rho+1/2-\omega)}\frac{2^{2\rho-1}}{4^\omega}\cdot\frac{1}{k^{2\omega}} & \text{if }\omega\in(0,\rho),\\[.3cm]\displaystyle \frac{1}{2^{2\rho-1}}\frac{\log k}{k^{2\rho}} & \text{if }\omega=\rho,\\[.3cm]\displaystyle \frac{1}{2^{2\rho-1}}\Gamma(\omega-\rho)\frac{1}{k^{\omega+\rho}} & \text{if }\omega>\rho.\end{array}\right.

This gives the conjectured asymptotic behavior of the sequence associated with Nesterov acceleration, with distinct regimes according to the relation between ω\omega and ρ\rho. The parser supplies no evidence that the conjecture has been proved or disproved.

Sources & referencesView supporting material

Primary source

Francis Bach, “On the Effectiveness of the z-Transform Method in Quadratic Optimization”, arXiv:2507.03404 (2025).

accelerated-methodsasymptotic-analysisoptimization

Progress summary

Refreshed
Open

The proposed formula for how Nesterov's sequence eventually decays has not been proved or disproved.

The conjecture predicts three distinct decay laws, depending on whether ω<ρ\omega<\rho, ω=ρ\omega=\rho, or ω>ρ\omega>\rho. Francis Bach describes the question as open and reports that the formula is empirically valid.

Known results

  • Bach's zz-transform analysis gives explicit candidate equivalents in all three regimes, but not a proof.
  • For ρ=1\rho=1, part of the required function decomposition can be obtained by hand; larger integer values of ρ\rho can be explored by symbolic computation.

Current status (as of August 2026): The three-regime asymptotic formula remains an open conjecture; no proof, counterexample, or verified resolution was found.

Sources

Solutions 0

No solutions have been posted yet.