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

arXiv: https://arxiv.org/abs/2608.09022 · HTML: https://mlsanity.com/paper/2608.09022/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 42 references that are in the map.
- First posted on arXiv 10 Aug 2026.

## Builds on (most cited first, 20 of 20)

- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Coin Betting and Parameter-Free Online Learning](https://mlsanity.com/paper/1602.04128/) (2016)
- [Learning-Rate-Free Learning by D-Adaptation](https://mlsanity.com/paper/2301.07733/) (2023)
- [Adaptive Gradient Descent without Descent](https://mlsanity.com/paper/1910.09529/) (2019)
- [A First Order Method for Solving Convex Bi-Level Optimization Problems](https://mlsanity.com/paper/1702.03999/) (2017)
- [Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities](https://mlsanity.com/paper/2002.08872/) (2020)
- [Making SGD Parameter-Free](https://mlsanity.com/paper/2205.02160/) (2022)
- [Golden Ratio Algorithms for Variational Inequalities](https://mlsanity.com/paper/1803.08832/) (2018)
- [A Forward-Backward Splitting Method for Monotone Inclusions Without Cocoercivity](https://mlsanity.com/paper/1808.04162/) (2018)
- [Exact Optimal Accelerated Complexity for Fixed-Point Iterations](https://mlsanity.com/paper/2201.11413/) (2022)
- [From Halpern's Fixed-Point Iterations to Nesterov's Accelerated Interpretations for Root-Finding Problems](https://mlsanity.com/paper/2203.04869/) (2022)
- [A simple uniformly optimal method without line search for convex optimization](https://mlsanity.com/paper/2310.10082/) (2023)
- [Optimal and parameter-free gradient minimization methods for convex and nonconvex optimization](https://mlsanity.com/paper/2310.12139/) (2023)
- [A first-order primal-dual algorithm with linesearch](https://mlsanity.com/paper/1608.08883/) (2016)
- [Adaptive restart of accelerated gradient methods under local quadratic growth condition](https://mlsanity.com/paper/1709.02300/) (2017)
- [A Relaxed Inertial Forward-Backward-Forward Algorithm for Solving Monotone Inclusions with Application to GANs](https://mlsanity.com/paper/2003.07886/) (2020)
- [A Parameter-Free Conditional Gradient Method for Composite Minimization under H"older Condition](https://mlsanity.com/paper/2305.18181/) (2023)
- [Convergence analysis of the Halpern iteration with adaptive anchoring parameters](https://mlsanity.com/paper/2505.10807/) (2025)
- [Preconditioned Halpern iteration with adaptive anchoring parameters and an acceleration to Chambolle--Pock algorithm](https://mlsanity.com/paper/2506.22725/) (2025)
- [Parameter-Free Non-Ergodic Extragradient Algorithms for Solving Monotone Variational Inequalities](https://mlsanity.com/paper/2604.07662/) (2026)

## Abstract (arXiv)

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.