← Back to all news
arXiv Statistics ML

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

The paper introduces two parameter‑free Halpern fixed‑point algorithms that automatically exploit hidden contractivity without needing a prior estimate of the contraction factor. Both methods achieve explicit linear convergence rates for the fixed‑point residual and distance to the unique fixed point, with one variant using a line‑search to locally estimate the contraction factor. Extensions include parameter‑free Nesterov‑type variants and a Tikhonov‑regularized approach for cocoercive equations, yielding an iteration complexity of \(\mathcal{O}(\epsilon^{-1}\log(\epsilon^{-1}))\).

Related stories

arXiv Machine Learning
Oct 12

Learning to accelerate Krasnosel'skii-Mann fixed-point iterations with guarantees

The paper presents a learning-to-optimize (L2O) framework that injects summable perturbations into Krasnosel'skii-Mann iterations to accelerate solving fixed-point problems with nonexpansive mappings. It proves that, under metric sub-regularity, the parametrized iterations achieve local linear convergence with a vanishing bias and include all fast-converging iterations. The framework is applied to enhance operator splitting methods, such as Douglas‑Rachford, and is validated on a best‑approximation problem.

By Andrea Martin, Giuseppe Belgioioso
safety
More like this →
Hugging Face Trending Papers
Sep 24

Anchored Extra-Proximal Methods: Optimal Higher-Order Methods for Monotone Inclusion Problems

The paper introduces the Anchored Extra-Proximal (AEP) framework for solving composite monotone inclusion problems, combining anchored extrapolation with an inexact anchored proximal update. By replacing the operator in the implicit update with its Taylor approximation and using a bisection line search, the authors derive a pth-order method that achieves a tangent-residual error ε in “~O(ε^{-2/(3p-1)})” oracle calls for every p ≥ 2. This complexity matches a proven lower bound, establishing the method as optimally efficient for deterministic algorithms in the pth-order oracle model.

More like this →
arXiv Machine Learning
Oct 2

Generalized Geometry Block Proximal Linearized Method for Multiblock Nonconvex and Nonsmooth Optimization

The paper introduces the Generalized Geometry Block Proximal Linearized (GGBPL) method, which uses a generalized geometry proximal linearized operator to update block variables in multiblock nonconvex and nonsmooth optimization problems. By allowing arbitrary inner products and admissible metrics, GGBPL adapts to the geometric structure of various problems, improving numerical efficiency over traditional Euclidean‑based methods. An inertial variant (iGGBPL) is also presented, and a unified convergence framework is established, proving objective convergence, global convergence to a critical point, and an ε‑stationary point iteration complexity of φ(ε−−). The methods are applied to sparse nonnegative matrix factorization and sparse nonnegative CP decomposition with λ₀ constraints, showing superior performance in numerical experiments.

By Weifeng Yang
benchmarks
More like this →
arXiv Machine Learning
Jul 13

Solving Stochastic Fixed-Point Equations with High Probability

arXiv:2607. 09097v1 Announce Type: cross Abstract: We study stochastic fixed-point equations $\mathbf{T}(\mathbf{x}) = \mathbf{x}$ over normed spaces $(\mathcal{E}, \|\cdot\|)$, where the operator $\mathbf{T}$ is nonexpansive or contractive and is accessed only through unbiased stochastic evaluations with bounded second central moment.

By Jelena Diakonikolas
More like this →