Cycling and Non-Acceleration of the Heavy-Ball Method in One Dimension

Abstract

The heavy-ball method (HB) is known to achieve the accelerated rate on smooth strongly convex quadratic functions, but it was unknown whether it can achieve such a rate on the more general class of smooth strongly convex functions. Recent work rules out acceleration by constructing functions on which HB cycles in $\mathbb{R}^2$. This implies the impossibilty of acceleration for functions with at least two variables, while the question remains open for univariate functions. In this blog post, we show that HB cannot achieve the accelerated rate for univariate functions. This is proved by rotating and projecting the existing two-dimensional cycle onto a line, and showing that the resulting cycle can be interpolated by some univariate function. The core construction was formalized in Lean 4. The results were proved with the help of Claude Opus 4.6. We provided the intuition and guidance, AI generated the proof, and then we verified its correctness.

1. Problem

We consider unconstrained minimization

\[\min_{x\in\mathbb R^d} f(x)\]

for differentiable functions $f:\mathbb R^d\to\mathbb R$. For fixed step size $\gamma$ and momentum $\beta$, the heavy-ball method (HB) is

\[\tag{HB} x_{t+1}=x_t-\gamma\nabla f(x_t)+\beta(x_t-x_{t-1}).\]

For any $L>\mu>0$ and any $d\in\mathbb{N}$, we let $\mathcal F_{\mu,L}(\mathbb{R}^d)$ denote the function class of all $L$-smooth $\mu$-strongly convex functions $f$ on $\mathbb{R}^d$, that is, $f:\mathbb{R}^d\to\mathbb{R}$ satisfying

\[f(y)\ge f(x)+\langle \nabla f(x),y-x\rangle+\frac{\mu}{2}\|y-x\|^2, \qquad f(y)\le f(x)+\langle \nabla f(x),y-x\rangle+\frac{L}{2}\|y-x\|^2,\]

for all $x,y\in\mathbb{R}^d$. We denote the set of $L$-smooth $\mu$-strongly convex quadratic functions by $\mathcal Q_{\mu,L}(\mathbb{R}^d)$. We have $\mathcal Q_{\mu,L}(\mathbb{R}^d) \subsetneq \mathcal F_{\mu,L}(\mathbb{R}^d)$.

Let $\kappa=L/\mu$ denote the condition number. On the class $\mathcal Q_{\mu,L}(\mathbb{R}^d)$ with any $d\in\mathbb{N}$, it is known that HB with some properly chosen $(\gamma,\beta)$ achieves the accelerated rate: HB returns a point $\hat{x}$ satisfying $\lVert \hat{x}-x^\star \rVert\leq\varepsilon$ within $O(\sqrt{\kappa}\log\frac{1}{\varepsilon})$ iterations. This rate is asymptotically optimal among all first-order methods. On the other hand, for the more general class of $\mathcal{F}_{\mu,L}(\mathbb{R}^d)$, HB is known to achieve the non-accelerated rate $O(\kappa\log\frac{1}{\varepsilon})$, and it remained open for a long time whether this rate can be improved to the accelerated rate. Recently, Goujaud et al. (2025a) showed that the answer is no for $\mathcal{F}_{\mu,L}(\mathbb{R}^d)$ with any $d\geq 2$. Informally speaking, they showed that for any parameter $(\gamma,\beta)$, if HB achieves the accelerated rate on $\mathcal Q_{\mu,L}(\mathbb{R}^d)$, then there exists a function in $\mathcal F_{\mu,L}(\mathbb{R}^2)$ on which HB cycles and does not converge. This implies the non-acceleration of HB in dimension at least two, and the possibility of acceleration on $\mathcal F_{\mu,L}(\mathbb{R})$ was later posed as an open problem [Goujaud et al., 2025b].

Open problem [Goujaud et al., 2025b].

Can the heavy-ball method accelerate on the univariate class $\mathcal F_{\mu,L}(\mathbb R)$?

In this blog post, we outline our approach to resolve the open problem. We show that the answer is no by constructing cycles in one dimension. A preprint will be released soon. We learned through personal communication that Dieuleveut and his collaborators have also solved the problem.

2. Cycles

We are interested in the cycling behavior because the existence of cycles is enough to eliminate any global convergence guarantee. Formally speaking, we say HB with parameters $(\gamma, \beta)$ cycles over $K$ nonconstant points $\{ x_0,\ldots,x_{K-1} \}\subseteq\mathbb{R}^d$ if there exists a function $f \in \mathcal F_{\mu,L}(\mathbb{R}^d)$ such that the iterates of HB satisfy $x_t=x_{t\bmod K}$ for all $t$. For example, the non-acceleration of HB over $\mathcal{F}_{\mu,L}(\mathbb{R}^d)$ for any $d\geq 2$ is proved by identifying the parameter region for $(\gamma,\beta)$ for which HB cycles over the $K$-th roots of unity [Goujaud et al., 2025a]:

\[\left\{ x_t = \left(\cos\frac{2t\pi}{K}, \sin\frac{2t\pi}{K} \right): t=0,1,\ldots,K-1 \right\} \subseteq \mathbb{R}^2.\]

A 7-th root-of-unity cycle — A $7$-th root-of-unity cycle when $(\gamma,\beta,\mu,L) = (3.5,0.75,0.005,1)$

The constructed two-dimensional function realizing the cycle — The constructed function $f\in\mathcal{F}_{\mu,L}(\mathbb{R}^2)$ realizing the left cycle

Since the root-of-unity cycles have affine dimension two, they do not answer the open problem.

The $m$-Jump $K$-th Root-of-Unity Cycles

The root-of-unity cycle we saw above is the “ordered” cycle. In the following, we consider a more general class of cycles, which will be referred to as the $m$-jump root-of-unity cycles. Then, we identify parameter region for $(\gamma,\beta)$ for which HB admits such cycles. We use complex notation for easier handling of rotations. Let

\[\omega_K=e^{2\pi i/K},\qquad \theta_K=\frac{2\pi}{K},\qquad U_K=\{m\in\{1,\ldots,K-1\}:\gcd(m,K)=1\}.\]

For $K\geq 3$ and $m\in U_K$, the $m$-jump $K$-th root-of-unity cycle is defined as

\[\{ x_t = \omega_K^{tm}: t=0,1,\ldots,K-1 \} = \left\{ 1,\ \omega_K^m,\ \omega_K^{2m},\ldots,\omega_K^{(K-1)m} \right\}.\]

Since $\gcd(m,K)=1$, the cycle traverses all $K$-th roots of unity. Note that the $1$-jump $K$-th root-of-unity cycle corresponds to the “ordered” cycle. We let $\Omega^{\mathrm{rou}}_{K,m}$ denote the parameter region for $(\gamma,\beta)$ for which HB cycles over the $m$-jump $K$-th root-of-unity cycle.

The 1-jump 7-th root-of-unity cycle — The $1$-jump $7$-th root-of-unity cycle

The 2-jump 7-th root-of-unity cycle — The $2$-jump $7$-th root-of-unity cycle

The 3-jump 7-th root-of-unity cycle — The $3$-jump $7$-th root-of-unity cycle

Conditions for Cycling over Root-of-Unity Cycles

Let the (normalized) heavy-ball operator be

\[M_m= \frac{(1+\beta-\mu\gamma)-\omega_K^m-\beta\omega_K^{-m}} {(L-\mu)\gamma} \in \mathbb{C}.\]

For $m=1$, this corresponds to the matrix $M$ in Theorem 3.5 of Goujaud et al. (2025a) written as a complex number. By following the proof of their Theorem 3.5, we obtain the following result.

Conditions for existence of root-of-unity cycles.

Fix $K\ge3$ and $m\in U_K$. We have $$ \Omega^{\mathrm{rou}}_{K,m} = \left\{ (\gamma,\beta) : |\arg M_m|+\arg(1-M_m)\le \frac{\pi}{K} \right\}. $$ Note that $M_m$ depends on $(\gamma,\beta)$.

Proof Sketch. Following the proof of Theorem 3.5 of Goujaud et al., (2025a), we show that there exists a function $f \in \mathcal F_{\mu,L}(\mathbb{R}^2)$ for which HB with parameters $(\gamma,\beta)$ cycles over the $m$-jump $K$-th root-of-unity cycle if and only if

\[\max_{\Delta\in\{1,2,\ldots,K-1\}}\phi_{K,m}(\Delta)\le 0,\]

where the residual is defined as

\[\phi_{K,m}(\Delta) =\operatorname{Re}\!\left((1-M_m)^*M_m(\omega_K^{m\Delta}-1)\right), \qquad \forall\Delta\in\{1,2,\ldots,K-1\}.\]

If, after possibly replacing without loss of generality $m$ by $K-m$, we have $1\le m\le (K-1)/2$, then it can be proven that the $\Delta$ that achieves the above maximum is $\Delta_m = m^{-1} \pmod K$. By some technical calculations, the angle bound follows from the condition $\phi_{K,m}(\Delta_m)\leq 0$.

3. Main Result

The following theorem is our main result:

One-dimensional cycling theorem.

Fix $K\ge3$ and $m\in U_K$. If $(\gamma,\beta)\in\textrm{int}(\Omega^{\text{rou}}_{K,m})$, then there exists a function $f\in\mathcal F_{\mu,L}(\mathbb R)$ and an initialization for which the heavy-ball method has a $K$-cycle on $\mathbb{R}$.

Construction. We let the cycle be the projection of the rotated $m$-jump $K$-th root-of-unity cycle onto the real line:

\[y_t= \cos(mt\theta_K+\varphi_*) = \textrm{Re}(\omega_K^{tm}\mathrm{e}^{i\varphi_\ast}),\]

where the angle of rotation $\varphi_\ast$ is chosen as

\[\varphi_*=-\frac12\arg((1-M_m)M_m)-\frac{\pi}{2K}.\]

If HB cycles over $\{ y_t \}$, then the gradient at $y_t$ must be

\[g_t=\frac{(1+\beta)y_t-y_{t+1}-\beta y_{t-1}}{\gamma}.\]

By verifying the interpolation conditions for smooth strongly convex functions [Taylor et al., 2017], there exists a function $f\in\mathcal F_{\mu,L}(\mathbb R)$ satisfying $f'(y_t)=g_t$ for all $t\in\{0,1,\ldots,K-1\}$. By construction, HB cycles over $y_0,\ldots,y_{K-1}$, meaning root-of-unity cycling implies cycling in dimension one, from which it follows that:

Consequence.

Combining the above cycling theorem with Theorem 3.6 of Goujaud et al. (2025a), we conclude that the heavy-ball method does not accelerate on $\mathcal F_{\mu,L}(\mathbb R)$ and solve the open problem. Hence, no parameter choice gives an accelerated worst-case convergence rate on $\mathcal F_{\mu,L}(\mathbb R^d)$ for any $d\ge1$.

4. Proof Idea

We let $\varphi$ be the angle of rotation and $y_t=\cos(mt\theta_K+\varphi)$ for $t=0,1,\ldots,K-1$. If HB cycles over $\{y_t\}$, then by the update rule, the gradients at $y_t$ must be

\[g_t=\frac{(1+\beta)y_t-y_{t+1}-\beta y_{t-1}}{\gamma}.\]

Step 1: Rotate slightly so that the projected roots have a stable sort order

If $\varphi = 0$, the roots of unity may be projected onto the same point but with different gradients, i.e., $y_s=y_t$ but $g_s\neq g_t$. To overcome this issue, we show that by taking

\[\varphi\in\left(-\frac\pi K,0\right),\]

all $\{y_t\}$ are distinct, and their order is fixed. Let $y_{\sigma(0)} < y_{\sigma(1)} < \cdots < y_{\sigma(K-1)}$ denote the sorted order.

Step 2: Simplify the interpolation conditions

To show the existence of functions in $\mathcal{F}_{\mu,L}(\mathbb{R})$, we invoke the interpolation conditions [Lessard et al., 2016, Taylor et al., 2017]. In one dimension, the conditions reduce to checking slopes of the sorted points. Namely, it is enough to ensure that each adjacent sorted pair $(\sigma(i), \sigma(i+1))$ satisfies

\[\mu\le \frac{g_{\sigma(i+1)}-g_{\sigma(i)}}{y_{\sigma(i+1)}-y_{\sigma(i)}}\le L.\]

Write $y_{\sigma(i+1)}-y_{\sigma(i)} = \operatorname{Re}(w_i)>0$ where $w_{i}=e^{i\varphi}(\omega_K^{m\sigma(i+1)}-\omega_K^{m\sigma(i)})$. By subsituting the formula for $g_t$ into the interpolation conditions, the conditions can be expressed as

\[\operatorname{Re}(M_m w_{i})\ge0, \qquad \operatorname{Re}((1-M_m) w_{i})\ge0.\]

Further simplification yields

\[\arg w_{i}\in \left[-\frac\pi2+|\arg M_m|,\frac\pi2-\arg(1-M_m)\right].\]

Step 3: Choose the angle of rotation

The remaining thing is to show that there exists $\varphi$ that fulfills the above conditions on $\arg w_i$.

By studying the properties of the permutation $\sigma$, the angle $\arg w_i$ can only take two possible values:

\[\arg w_i \in \left\{ -\frac\pi2+\frac\pi K+\varphi, \frac\pi2+\varphi \right\}.\]

Therefore, it suffices to ensure

\[\left\{-\frac\pi2+\frac\pi K+\varphi, \frac\pi2+\varphi \right\} \subseteq \left[-\frac\pi2+|\arg M_m|,\frac\pi2-\arg(1-M_m)\right].\]

That is,

\[|\arg M_m|-\frac\pi K\le \varphi\le -\arg(1-M_m).\]

Thus a valid $\varphi$ exists if and only if

\[|\arg M_m| + \arg(1-M_m) \le \frac\pi K.\]

This is precisely the condition for the existence of root-of-unity cycles. In other words, if $(\gamma,\beta)\in\textrm{int}(\Omega^{\text{rou}}_{K,m})$, then the above interval is non-empty, and we can choose $\varphi$ to be the midpoint of the interval

\[\varphi_*=\frac12\left(|\arg M_m|-\frac\pi K-\arg(1-M_m)\right) =-\frac12\arg((1-M_m)M_m)-\frac\pi{2K}.\]

This concludes the proof.

The rotated 1-jump 7-th root-of-unity cycle — The rotated $1$-jump $7$-th root-of-unity cycle when $(\gamma,\beta,\mu,L) = (3.5,0.75,0.005,1)$

The constructed univariate function — The constructed function $f\in\mathcal{F}_{\mu,L}(\mathbb{R})$

5. Additional Results

We let the augmented root-of-unity region be

\[\Omega_{\mathrm{aug}} =\bigcup_{K\ge3}\ \bigcup_{m\in U_K}\Omega^{\mathrm{rou}}_{K,m}.\]

This augmented region is strictly larger than the ordered one that considers only $m=1$. For example, there are parameters $(\gamma,\beta)$ that lie in $\Omega^{\mathrm{rou}}_{5,2}$ but not in $\Omega^{\mathrm{rou}}_{K,1}$ for any $K$.

The augmented cycling region in the (L gamma, beta) plane — **The augmented region.** The union over all coprime modes $m$ contains parameters certified only by higher modes $m\ge 2$ (black) and missed by the ordered $m=1$ cycles (purple). PDF version.

The same calculation also explains the fractional regions observed in Figure 8 of Goujaud et al., (2025b). For $m\in U_K$, checking only the residual $\phi_{K,m}(1)$ is equivalent, after a change of variables, to evaluating the ordered polynomial condition at a fractional period $K/m$ (see Theorem 3.5 of Goujaud et al., (2025a)). However, $\phi_{K,m}(\Delta)$ is not necessarily maximized by $\Delta=1$; the maximizer is

\[\Delta_m=m^{-1}\pmod K.\]

Thus the fractional condition is generally only a relaxation, and the corresponding region can be strictly larger than the true cycling region.

Fractional relaxation versus the genuine cycling region for K=7, m=2 — **Fractional relaxation vs. the genuine region**, for $(K,m)=(7,2)$. The red region is the fractional relaxation that keeps only the $\Delta=1$ residual; the blue region is the genuine cycling region from the full residual system, whose binding constraint is the maximizer $\Delta_m=m^{-1} \bmod K$. PDF version.

6. Use of AI and Formal Verification

AI tools were useful for algebraic exploration, for reorganizing rough proof attempts, and for translating parts of the argument into Lean. The final mathematical claims were not accepted directly from model output: the role of AI was to accelerate iteration, not to replace verification.

The one-dimensional cycling theorem was formalized in Lean 4 with Mathlib (see here). The formalization checks the core angle argument, the angle choice, the projected slope bounds, and the resulting cycle-existence statement, modulo two external mathematical inputs: the one-dimensional smooth strongly convex interpolation criterion and the previously known containment of the acceleration-relevant parameters in the roots-of-unity cycling region.

In practice, Lean was most valuable for controlling details that are easy to get wrong on paper: signs of arguments, boundary cases, modular inverses, and the exact interval in which the phase must lie.

References

[Polyak, 1964] Some methods of speeding up the convergence of iteration methods. USSR Comput. Math. Math. Phys., 1964.
[Nesterov, 1983] A method for solving a convex programming problem with convergence rate $O(1/k^2)$. Dokl. Akad. Nauk SSSR, 1983.
[Ghadimi et al., 2015] Global convergence of the heavy-ball method for convex optimization. Eur. Control. Conf., 2015.
[Lessard et al., 2016] Analysis and design of optimization algorithms via integral quadratic constraints. SIAM J. Optim., 2016.
[Taylor et al., 2017] Smooth strongly convex interpolation and exact worst-case performance of first-order methods. Math. Program., 2017.
[Goujaud et al., 2025a] Provable non-accelerations of the heavy-ball method. Math. Program., 2025.
[Goujaud et al., 2025b] Open problem: Two riddles in heavy-ball dynamics. arXiv preprint, 2025.