← All problems

Heavy-ball acceleration problem

Let 0<μ≤L0<\mu\le L and let Fμ,L(Rd)\mathcal{F}_{\mu,L}(\mathbb{R}^d) denote the class of differentiable functions f:Rd→Rf:\mathbb{R}^d\to\mathbb{R} that are μ\mu-strongly convex and have LL-Lipschitz continuous gradients. For fixed parameters α>0\alpha>0 and β≥0\beta\ge 0, the classical heavy-ball iteration is xk+1=xk−α∇f(xk)+β(xk−xk−1)x_{k+1}=x_k-\alpha\nabla f(x_k)+\beta(x_k-x_{k-1}). Does there exist a choice of α\alpha and β\beta, depending on μ\mu and LL, for which this iteration has a uniform accelerated worst-case convergence rate over Fμ,L(Rd)\mathcal{F}_{\mu,L}(\mathbb{R}^d), with dependence on the condition number κ=L/μ\kappa=L/\mu of accelerated order rather than the nonaccelerated order? The one-dimensional case asks the same question for d=1d=1.

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

A 2026 preprint claims to settle the one-dimensional case by showing that heavy-ball cannot achieve acceleration there, while the higher-dimensional question remains open.

The problem asks whether classical heavy-ball momentum can achieve accelerated worst-case performance on smooth, strongly convex functions. Earlier work established cycling obstructions in dimension d≥2d \ge 2, but left the one-dimensional case open.

Known results

  • Goujaud et al., 2023: for any parameters, either the quadratic worst-case rate is not accelerated or a smooth strongly convex example fails to converge; the construction has dimension at least 22.
  • A 2025 paper reported numerical one-dimensional cycles but explicitly did not claim a proof.

2026 one-dimensional claim

Fotopoulos, Helcig, Deck, and Alsbach claim that Fourier analysis and projected root-of-unity cycles prove non-acceleration in one dimension and enlarge the cycling region. Two other 2026 preprints describe this as settling the scalar case, but the claim remains unverified; higher-dimensional behavior is not resolved.

Current status (as of October 2026): The one-dimensional obstruction is claimed but unverified, while the higher-dimensional acceleration question remains open.

Sources

Solutions 0

No solutions have been posted yet.