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

Summary

This paper develops provable, parameter-free, and adaptive fixed-point algorithms for contractive mappings, with a focus on automatically exploiting hidden contractivity without requiring prior knowledge of the contraction factor. The authors address the gap between optimization and fixed-point literature, where parameter-free methods in optimization have gained significant attention, but parameter-free fixed-point algorithms often lack rigorous theoretical guarantees, with most existing results establishing only asymptotic convergence without explicit rates.

The paper considers two main problems: the fixed-point problem (FP) of finding x⋆ ∈ H such that x⋆ = T(x⋆) for a mapping T: H → H, and the root-finding problem (CE) of finding x⋆ ∈ H such that G(x⋆) = 0 for a single-valued mapping G. The authors unify the settings by referring to T as a ρ-contractive mapping with ρ ∈ (0, 1], where ρ = 1 corresponds to nonexpansive mappings. For the root-finding problem, they assume G is β-co-coercive.

The main contributions are fourfold. First, the authors propose a completely parameter-free Halpern fixed-point algorithm (Algorithm 1) that requires no line search, bisection, or prior estimate of the contraction factor. This method establishes explicit linear convergence rates for both the fixed-point residual ∥xk − T(xk)∥ and the distance to the unique fixed point ∥xk − x⋆∥. The algorithm is inspired by the geometric Halpern method of [38], replacing the parameter φk with an upper bound φ̄k that is updated adaptively using estimates of the contraction ratio.

Second, the authors develop an adaptive Halpern fixed-point algorithm (Algorithm 2) that requires only an upper bound ρ̄ of the contraction factor ρ. This method reduces to the existing adaptive Halpern scheme of [20] when ρ = 1 (nonexpansive case). The algorithm also enjoys explicit linear convergence guarantees for both the fixed-point residual and the distance to the fixed point.

Third, by combining the proposed fixed-point schemes with Tikhonov regularization, the authors obtain a parameter-free method (Algorithm 3) for solving co-coercive equations. They establish an iteration complexity of O(ϵ−1 ln(ϵ−1)) for computing an ϵ-solution satisfying ∥G(xkϵ)∥ ≤ ϵ. The approach applies Tikhonov regularization to define Gµ:= G + µI and Tµ:= I − ηGµ, choosing parameters appropriately so that Tµ becomes contractive.

Fourth, exploiting the equivalence between Halpern iterations and Nesterov's accelerated fixed-point schemes established in [42], the authors derive parameter-free Nesterov-accelerated variants (Algorithm 4) that inherit linear convergence in the contractive setting. These variants do not explicitly involve the anchor point x0, which may help reduce error accumulation.

The theoretical results include explicit convergence bounds. For Algorithm 1, Theorem 3.1 establishes that ∥xk − T(xk)∥ ≤ Cρ ρk ∥x0 − T(x0)∥ and ∥xk − x⋆∥ ≤ Cρ(1+ρ)/(1−ρ) ρk ∥x0 − x⋆∥, where Cρ:= 1 + (1+ρ)/(1−ρ)2 ρ. For Algorithm 2, Theorem 4.1 establishes that ∥xk − T(xk)∥ ≤ 2/Ck ∥x0 − x⋆∥ and ∥xk − x⋆∥ ≤ 2/((1−ρ)Ck) ∥x0 − x⋆∥, where Ck:= (1+φ̂0)/2 · ((φ̂0+1)/2) k · (φ̂0 + 2φ̂0/(φ̂0−1)) − φ̂0/(φ̂0−1).

The numerical experiments evaluate nine algorithms on various test problems. On linear contractive mappings (Example 1.1), all proposed methods converge successfully within approximately 20-30 iterations on average, while the existing method [Alg. 3.1 (He et al.)] fails to converge within 10,000 iterations. On nonlinear contractive mappings (Example 1.2), the proposed methods converge in approximately 14-17 iterations on average, again outperforming the existing method. On nonexpansive mappings (Examples 2.1-2.3), the proposed methods remain effective, with Alg. 1 (ωmax) and Alg. 3 (geo.) exhibiting the best overall performance. In the LASSO experiments (Example 2.2), all proposed algorithms successfully attain the target accuracy in fewer than 100 iterations on average, while the existing method fails to achieve the prescribed tolerance within 5,000 iterations.

The paper concludes that the proposed algorithms successfully exploit hidden contractivity when present while remaining effective on nonexpansive problems, and they consistently outperform existing adaptive fixed-point methods in the numerical experiments.

Improvements to AI Systems:

1. Adaptive Solver for Optimization and Equilibrium Problems: Implement the parameter-free Halpern fixed-point algorithm (Algorithm 1) as a core solver in AI systems that require finding fixed points (e.g., reinforcement learning value iteration, generative adversarial network (GAN) equilibrium, or multi-agent coordination). The system can automatically exploit hidden contractivity in the mapping without manual tuning of contraction factors, achieving linear convergence rates even when the contraction factor is unknown. This eliminates the need for line search or bisection, reducing computational overhead.

2. Robust Convergence in Nonconvex/Nonexpansive Settings: Integrate Algorithm 2 (adaptive Halpern with only an upper bound on contraction) into AI training pipelines that involve nonexpansive operators (e.g., proximal gradient methods for sparse coding, or projected gradient descent in constrained optimization). The improved system guarantees explicit linear convergence for residuals and distances to the solution, even when the operator is only nonexpansive (ρ=1), outperforming existing methods that fail to converge in practice (e.g., within 10,000 iterations).

3. Parameter-Free Root-Finding for Co-Coercive Equations: Use Algorithm 3 (with Tikhonov regularization) to solve co-coercive equations in AI systems, such as finding zeros of monotone operators in variational inequality problems (e.g., in game theory or optimal transport). The system achieves an iteration complexity of O(ε−1 ln(ε−1)) for ε-accurate solutions, with no need to pre-specify regularization or step-size parameters, making it deployable in real-time decision-making where problem parameters are unknown.

4. Accelerated Nesterov Variants for Faster Learning: Adopt Algorithm 4 (parameter-free Nesterov-accelerated fixed-point variants) in AI models that rely on accelerated gradient methods (e.g., deep learning optimizers, convex optimization layers). The improved system inherits linear convergence in contractive settings without requiring an anchor point, reducing error accumulation in long-horizon tasks (e.g., training recurrent networks or solving dynamic programming problems). This leads to faster convergence and better numerical stability compared to standard accelerated methods.

5. Automatic Detection and Exploitation of Problem Structure: Build an AI system that dynamically switches between the proposed algorithms based on observed convergence behavior. For instance, it can start with Algorithm 1 (fully parameter-free) and, if contraction is detected, maintain linear rates; if not, it can fall back to Algorithm 2 for nonexpansive cases. This makes the system universally applicable to a wide range of optimization and equilibrium problems without user intervention, improving robustness in automated machine learning pipelines.

6. Improved Baseline for Benchmarking in AI Research: The numerical experiments show that existing adaptive fixed-point methods (e.g., He et al.) fail to converge on linear and nonlinear contractive mappings, while the proposed methods succeed in 14–30 iterations. AI systems can use these algorithms as a new state-of-the-art baseline for evaluating fixed-point solvers in applications like policy evaluation, matrix games, and LASSO regression, leading to more reliable and efficient model training.

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 O(epsilon-1 (epsilon-1)) for computing an epsilon-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.