# A Class of Accelerated Fixed-Point-Based Methods with Delayed Inexact Oracles and Its Applications

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 83 references that are in the map.
- First posted on arXiv 15 Dec 2025.

## Builds on (most cited first, 30 of 36)

- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization](https://mlsanity.com/paper/1506.08272/) (2015)
- [Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Norm](https://mlsanity.com/paper/2102.07922/) (2021)
- [Perturbed Iterate Analysis for Asynchronous Stochastic Optimization](https://mlsanity.com/paper/1507.06970/) (2015)
- [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)
- [Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent](https://mlsanity.com/paper/1407.1537/) (2014)
- [A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates](https://mlsanity.com/paper/1806.10188/) (2018)
- [An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization](https://mlsanity.com/paper/1505.04824/) (2015)
- [Asynchronous Stochastic Optimization Robust to Arbitrary Delays](https://mlsanity.com/paper/2106.11879/) (2021)
- [Improved asynchronous parallel optimization analysis for stochastic incremental methods](https://mlsanity.com/paper/1801.03749/) (2018)
- [Exact Optimal Accelerated Complexity for Fixed-Point Iterations](https://mlsanity.com/paper/2201.11413/) (2022)
- [Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties](https://mlsanity.com/paper/1403.3862/) (2014)
- [ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates](https://mlsanity.com/paper/1506.02396/) (2015)
- [Halpern-Type Accelerated and Splitting Algorithms For Monotone Inclusions](https://mlsanity.com/paper/2110.08150/) (2021)
- [From Halpern's Fixed-Point Iterations to Nesterov's Accelerated Interpretations for Root-Finding Problems](https://mlsanity.com/paper/2203.04869/) (2022)
- [ASAGA: Asynchronous Parallel SAGA](https://mlsanity.com/paper/1606.04809/) (2016)
- [Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees](https://mlsanity.com/paper/2109.04522/) (2021)
- [The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than 1/k2](https://mlsanity.com/paper/1510.08740/) (2015)
- [On the O(1/k) Convergence of Asynchronous Distributed Alternating Direction Method of Multipliers](https://mlsanity.com/paper/1307.8254/) (2013)
- [Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions](https://mlsanity.com/paper/2310.02987/) (2023)
- [Convergence Rates with Inexact Non-expansive Operators](https://mlsanity.com/paper/1404.4837/) (2014)
- [From the Ravine method to the Nesterov method and vice versa: a dynamical system perspective](https://mlsanity.com/paper/2201.11643/) (2022)
- [Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problems](https://mlsanity.com/paper/2301.03113/) (2023)
- [On Unbounded Delays in Asynchronous Parallel Fixed-Point Algorithms](https://mlsanity.com/paper/1609.04746/) (2016)
- [Cyclic Coordinate Update Algorithms for Fixed-Point Problems: Analysis and Applications](https://mlsanity.com/paper/1611.02456/) (2016)
- [Fast convergence of generalized forward-backward algorithms for structured monotone inclusions](https://mlsanity.com/paper/2107.10107/) (2021)
- [Rates of convergence for inexact Krasnosel'skii-Mann iterations in Banach spaces](https://mlsanity.com/paper/1705.09340/) (2017)
- [Asynchronous Block-Iterative Primal-Dual Decomposition Methods for Monotone Inclusions](https://mlsanity.com/paper/1507.03291/) (2015)

## Built on by (most cited first, 1 of 1)

- [Stochastic Inertial Krasnosel'skii-Mann Iteration Achieves Near-Optimal Sample Complexity](https://mlsanity.com/paper/2609.28543/) (2026)

## Abstract (arXiv)

In this paper, we develop a novel accelerated fixed-point-based framework using delayed inexact oracles to approximate a fixed point of a nonexpansive operator (or equivalently, a root of a co-coercive operator), a central problem in scientific computing. Our approach leverages both Nesterov's acceleration technique and the Krasnosel'skii-Mann (KM) iteration, while accounting for delayed inexact oracles, a key mechanism in asynchronous algorithms. We also introduce a unified approximate error condition for delayed inexact oracles, which can cover various practical scenarios. Under mild conditions and appropriate parameter updates, we establish both O(1/k2) non-asymptotic and o(1/k2) asymptotic convergence rates in expectation for the squared norm of residual. Our rate significantly improves the O(1/k) rates in classical KM-type methods, including their asynchronous variants. We also establish o(1/k2) almost sure convergence rates and the almost sure convergence of iterates to a solution of the problem. Within our framework, we instantiate three settings for the underlying operator: (i) a deterministic universal delayed oracle; (ii) a stochastic delayed oracle; and (iii) a finite-sum structure with asynchronous updates. For each case, we instantiate our framework to obtain a concrete algorithmic variant for which our convergence results still apply, and whose iteration complexity depends linearly on the maximum delay. Finally, we verify our algorithms and theoretical results through two numerical examples on both matrix game and shallow neural network training problems.