Correction to: From Halpern’s fixed-point iterations to Nesterov’s accelerated interpretations for root-finding problems

Quoc Tran-DinhComputational 2025 · DOI

TL;DR

This paper provides a formal mathematical correction to a previously published work on accelerated root-finding algorithms. It fills a critical gap in the proof of Theorem 3, rigorously establishing that the sequence of iterates generated by the algorithm actually converges to a solution, rather than just getting "closer" to the solution set.

What Problem Does This Paper Address?

In the world of numerical optimization and root-finding (finding where a function $G(x) = 0$), researchers often design "accelerated" algorithms inspired by Nesterov’s famous work. A common challenge in proving these algorithms work is showing iterate convergence.

It is one thing to prove that the "error" (the value of the function) goes to zero; it is a much harder task to prove that the sequence of points $\{x_k\}$ produced by the computer actually settles down at a specific coordinate $y^*$. The original paper, which linked Halpern’s fixed-point iterations to Nesterov-style acceleration, had an incomplete proof for this specific claim. This correction provides the missing mathematical steps to ensure the theory is airtight.

Methods

The author employs a Lyapunov-like analysis, a standard technique in stability theory and optimization. The core of the proof involves:

  1. Defining a Potential Function ($\mathcal{V}_k$): The author uses a non-negative, non-increasing function that tracks the "energy" or distance of the current iterate from the solution.
  2. Decomposition and Limits: By rewriting $\mathcal{V}_k$ and analyzing its components as the number of iterations ($k$) goes to infinity, the author proves that the distance between the iterate $x_k$ and any solution $y^*$ converges to a fixed value.
  3. Opial’s Lemma: This is the "secret sauce" of the proof. Opial’s Lemma is a classic tool in functional analysis used to prove that a sequence in a Hilbert space converges to a specific point, provided certain conditions about its limit points and distances are met.

Datasets

Not discussed in the paper. This is a purely theoretical mathematical correction and does not involve empirical testing or datasets.

Key Insights and Ideas

  • The Importance of Boundedness: The proof first establishes that the sequence of iterates $\{x_k\}$ is bounded. Without this, the sequence could theoretically wander off to infinity even if the function value was improving.
  • Vanishing Cross-Terms: A key part of the "missing proof" involves showing that specific inner product terms (which represent the interaction between the current position and the direction of movement) vanish as $k$ increases. Specifically, the author shows that $|t_k \langle x_k - y^*, y_k - x_k \rangle| \to 0$.
  • Co-coercivity is Key: The proof relies on the operator $G$ being $1/L$-co-coercive, which implies it is also $L$-Lipschitz continuous. These properties ensure the operator behaves predictably enough to allow for convergence.

Key Results

The primary result is the completion of the proof for Theorem 3. Specifically:

  • Iterate Convergence: It is now formally proven that the sequence $\{x_k\}$ converges to a solution $y^*$ in the set of zeros of $G$ ($\text{zer}(G)$).
  • Auxiliary Convergence: The paper also proves that the auxiliary sequence $\{y_k\}$ (often used in accelerated methods to calculate the next step) converges to the same limit point $y^*$.
  • Rigorous Foundation: While the original conclusion of the 2024 paper remains valid, this note provides the necessary mathematical rigor to support the claim of iterate convergence.

Limitations and Future Work

As a formal correction, the scope is narrow. The proof provided is specific to the case where the parameter $\mu = 1$. While this covers the primary accelerated interpretation discussed in the original paper, it does not explore broader parameter spaces. Future work in this sub-field continues to look for ways to relax assumptions on the operator $G$ while maintaining these strong convergence guarantees.

Summary updated

BibTeX
@inproceedings{trandinh2025correction,
  author = {Quoc Tran-Dinh},
  title = {{Correction to: From Halpern’s fixed-point iterations to Nesterov’s accelerated interpretations for root-finding problems}},
  booktitle = {Computational},
  year = {2025},
  doi = {10.1007/s10589-025-00746-0},
}
Figure