Provable Parameter-Free Fixed-Point Algorithms with Linear Convergence Rates

Abstract

In this paper, we develop provable parameter-free and adaptive fixed-point algorithms for contractive mappings, with an emphasis on automatically exploiting hidden contractivity without requiring prior knowledge of the contraction factor. Our first method is a completely parameter-free variant of the Halpern fixed-point iteration. It requires no line search, bisection, or prior estimate of the contraction factor, while retaining essentially the same per-iteration computational cost as classical fixed-point schemes. We establish explicit linear convergence rates for both the fixed-point residual and the distance to the unique fixed point. The second algorithm is an adaptive Halpern method that requires only an upper bound on the contraction factor and reduces to an existing adaptive Halpern scheme in the nonexpansive case. This method also enjoys explicit linear convergence guarantees. We further extend these ideas in two directions. First, by combining the proposed fixed-point schemes with Tikhonov regularization, we obtain a parameter-free method for solving co-coercive equations and establish an iteration complexity of $\mathcal{O}({ε^{-1}\ln(ε^{-1})})$ for computing an $ε$-solution. Second, using the relation between Halpern iterations and Nesterov's accelerated fixed-point schemes, we derive parameter-free Nesterov's accelerated variants that inherit linear convergence in the contractive setting. Numerical experiments on several examples demonstrate that the proposed algorithms are competitive with, and often outperform, existing adaptive fixed-point methods. In particular, the methods successfully exploit contractive behavior when it is present while remaining effective on nonexpansive problems.

Disclosure

“ere visiting the Vietnam Institute for Advanced Study in Mathematics (VIASM), Hanoi, Vietnam, in June 2026. Declaration of AI-Assisted Tools. During the preparation of this manuscript, we used large lan- guage models, including ChatGPT and Gemini, to assist in verifying elementary mathematical deriva- tions, algebraic manipulations, and properties of mathematical expressions. We also used Codex to assist with implementing the proposed algorithms, generating synthetic data, and prep”

PDF page 26

Classification

Computational experiments or data processing

Multiplier

3

Verified

2026-08-23T05:07:02.687944Z

Structural counts