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

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 O(ε-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.