Provable Parameter-Free Fixed-Point Algorithms with Linear Convergence Rates
Abstract
In this paper, we develop provable parameter-free 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 parameter-free variant of the Halpern fixed-point iteration with 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 also a parameter-free Halpern method, but it requires a line-search procedure to find a local estimate for the contraction factor, which may need a few additional operator evaluations. This method also enjoys explicit linear convergence guarantees. We further extend these ideas in two directions. First, using the relation between Halpern iterations and Nesterov-type accelerated fixed-point schemes, we derive parameter-free Nesterov-type (three-term) variants that inherit linear convergence in the contractive setting. Second, by combining the proposed fixed-point schemes with Tikhonov regularization, we obtain new methods for solving cocoercive equations and establish an iteration complexity of 𝒪(ε−1log(ε−1)) for computing an ε-solution, provided that a valid lower bound on the cocoercivity constant is available. 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 on the selected nonexpansive test problems.
Related
- Disjoint unions and fixed-parameter algorithms for chromatic villainy
- Volume of quasi-homogeneous sublevel sets: Two linear algebra deterministic algorithms with convergence rates
- Linear Corrector Estimates and Corrected Pressure Convergence for a Two-Parameter Hyperbolic Relaxation of the Incompressible Navier--Stokes Equations
- A class of high-order discontinuous-Galerkin methods satisfying infinitely many entropy conditions with provable error estimates and strong convergence for general nonlinear conservation laws
- Provable Classical and Quantum Local Algorithms for Max-k-Cut and Quantum Advantage at Moderate Girth
BibTeX
@misc{trandinh2026provable,
title = {{Provable Parameter-Free Fixed-Point Algorithms with Linear Convergence Rates}},
author = {Quoc Tran-Dinh and Pham Ngoc Anh and Ha Manh Tien},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.09022},
eprint = {2608.09022},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.09022},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Provable Parameter-Free Fixed-Point Algorithms with Linear Convergence Rates
AU - Quoc Tran-Dinh
AU - Pham Ngoc Anh
AU - Ha Manh Tien
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2608.09022
UR - https://arxiv.org/abs/2608.09022
AB - In this paper, we develop provable parameter-free 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 parameter-free variant of the Halpern fixed-point iteration with 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 also a parameter-free Halpern method, but it requires a line-search procedure to find a local estimate for the contraction factor, which may need a few additional operator evaluations. This method also enjoys explicit linear convergence guarantees. We further extend these ideas in two directions. First, using the relation between Halpern iterations and Nesterov-type accelerated fixed-point schemes, we derive parameter-free Nesterov-type (three-term) variants that inherit linear convergence in the contractive setting. Second, by combining the proposed fixed-point schemes with Tikhonov regularization, we obtain new methods for solving cocoercive equations and establish an iteration complexity of 𝒪(ε^−1log(ε^−1)) for computing an ε-solution, provided that a valid lower bound on the cocoercivity constant is available. 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 on the selected nonexpansive test problems.
ER -