Stochastic Inertial Krasnosel'skii-Mann Iteration Achieves Near-Optimal Sample Complexity

1 Introduction

• The problem is to find an approximate fixed point of a nonexpansive operator when exact evaluations may be unavailable or costly and noisy, possibly biased oracle responses are used.The target accuracy is measured by the last-iterate fixed-point residual.Source: §1 · pp. 1–2
• Existing simple stochastic methods fall short of near-optimal sample complexity, while prior near-optimal approaches rely on stronger assumptions or more elaborate algorithms.Stochastic KM’s O(ε^-4) random-iterate bound is one example; VR-GHAL uses recursive variance reduction and other techniques.Source: §1 · p. 2

1.1 Our contributions

• The method adds two inertial extrapolations to stochastic KM and retains one call to a possibly biased stochastic oracle per update.Its single-loop structure uses a carefully chosen parameter schedule.Source: §1 · p. 2, §1.1 · p. 3
• iKM has eO(ϵ^-2) sample complexity, matching the lower bound for unbiased oracles up to one logarithmic factor and improving stochastic KM’s best-known O(ϵ^-4) rate, which holds for weaker random-iterate convergence [Foster et al., 2019, Theorem 2; Bravo and Cominetti, 2024, Corollary 5.4].Source: §1.1 · p. 3
• With an exact oracle, iKM attains an O(K^-1) last-iterate rate, worst-case optimal for deterministic nonexpansive fixed-point methods and faster than classical KM’s Θ(K^-1/2).The optimality comparison is to Park and Ryu [2022, Theorem 4.6]; the classical KM rate is cited to Davis and Yin [2016].Source: §1.1 · p. 3

1.2 Related work

• Prior deterministic analyses of accelerated and inertial KM methods assume exact evaluations or summable perturbations, while stochastic analyses have not combined one response per iteration, a single loop, and near-optimal complexity for general nonexpansive maps.The paper presents its method as the first to combine these properties under its stochastic-oracle model.Source: §1.2 · pp. 3–4

2.1 The stochastic iKM algorithm

• Each update forms two inertial extrapolations and uses an oracle-based relaxed update with a noisy, possibly biased response.Source: §2.1 · p. 4

2.2 Stochastic oracle model and schedule

• The oracle model allows predictable, possibly history-dependent bias and conditionally centered noise with conditional second moment bounded by σ^2.Source: §2.2 · p. 5
• The proposed schedule has a tuning parameter a; increasing a delays α_k’s transition toward 1 and shifts λ_k’s peak later in the horizon.Source: §2.2 · pp. 5–6
• For unbiased oracles, iKM matches the stochastic lower bound up to a logarithmic factor and improves stochastic KM’s O(ϵ^-4) random-iterate bound.The lower-bound comparison is for the unbiased case.Source: §2.2 · p. 7
• In the deterministic setting (σ = 0 and no bias), deterministic iKM under nonexpansiveness achieves a worst-case-optimal O(1/K) last-iterate rate; no-inertia KM is also given an O(1/K) rate, described as slower.Source: §2.2 · p. 7

• The proposed schedule achieves near-optimal stochastic sample complexity and the optimal deterministic last-iterate rate with a simple single-loop update.Source: §3 · p. 7
• Future work includes practical implementations in large-scale stochastic first-order and operator-splitting methods, and adapting iKM’s inertial mechanism for model-free reinforcement learning.Deep neural network training is identified as a testbed for practical implementations.Source: §3 · p. 7

• Fast KM has an explicit nonasymptotic O(K^-1) fixed-point-residual bound, matching the optimal worst-case order for general nonexpansive problems [Boţ et al., 2026, Remark 5; Park and Ryu, 2022, Theorem 4.6].Source: A Relation to Fast KM · p. 10
• Fast KM’s query sequence is reproduced at every iteration by deterministic iKM with the specified parameters and base points.Source: A Relation to Fast KM · p. 10
• The Fast KM parameters differ from the main schedule, which is designed to be optimal in both deterministic and stochastic regimes.Source: A Relation to Fast KM · p. 10

A.1 Proof of Proposition 1

• The proof checks the Fast KM identity at k = 1 and for k ≥ 2, establishing the claimed query-sequence representation.Source: §A.1 · pp. 11–12

B.1 Auxiliary Lemmas

• For a nonexpansive map, the residual operator is 1/2-cocoercive, monotone, and 2-Lipschitz, and its zeros are exactly the map’s fixed points.Source: §B.1 · p. 12
• The regularized-root lemma states that the equation has a unique solution and that its solution map is firmly nonexpansive.Source: §B.1 · p. 12
• Lemma 4 provides bounds for schedule quantities over iterations 1 through K under its stated conditions.Source: §B.1 · p. 13

Step 1: parameter ranges and the order of αk

• 0 < r_1 < r_2 < ··· < r_K < 2, and α_1 = 0.These establish the strict order of the r_k sequence and part (a)'s stated initial value.Source: §B.2 · p. 14

Step 2: monotonicity and endpoint orders of βk

• β_k decreases with k, and the proof establishes its endpoint orders (14).For 2 ≤ k ≤ K, β_k = 4/(3r_{k−1}) by (12); the proof also derives bounds and asymptotic orders for β_k.Source: §B.2 · pp. 14–16

Step 3: unimodality and peak location of λk

• λ_k is unimodal: it increases until the sampled grid crosses w⋆, then decreases, with its maximum at a boundary index or adjacent grid point(s) bracketing w⋆.The continuous profile Φ has a unique maximizer w⋆; if the real-valued grid index for the peak lies before 1, then k_λ = 1.Source: §B.2 · pp. 16, 18

B.2 Proof of Lemma 1

• The peak-height argument establishes the existence of an index because (10) gives ω0 > log 2 > ωK.It then applies (39) and the minimality in (108).Source: §B.2 · p. 19
• Equations (107) and (111) prove (16), completing the proof of Lemma 1.Source: §B.2 · p. 19

B.3 Proof of Theorem 1

• The proof reduces the last-iterate residual to bounding R_K, the worst-case root-mean-square residual over 0 ≤ ρ ≤ 1.The final affine point and the potential are introduced as part of this reduction.Source: §B.3 · p. 20
• A one-step potential estimate is applied in expectation, and an induction combines the resulting terms across iterations.The proof then uses this control to bound the expected potential at iteration K.Source: §B.3 · pp. 21–22
• The final argument bounds the initial potential using D and the schedule terms, then substitutes the estimates to obtain (17).D is defined as the distance from x1 to the fixed-point set.Source: §B.3 · pp. 22–23

B.4.1 Proof of Lemma 2

• The proof of Lemma 2 establishes its first estimate on G and obtains the second using Cauchy–Schwarz.Source: §B.4.1 · p. 23

B.4.2 Proof of Lemma 3

• Because G is continuous, monotone, and has full domain, it is maximal monotone [Bauschke and Combettes, 2017, Corollary 20.28].Source: §B.4.2 · p. 23
• Minty’s theorem then shows that the resolvent of G is everywhere defined.Source: §B.4.2 · p. 23
• The regularized-root equation has a unique solution for every v ∈ H.Source: §B.4.2 · p. 24

B.4.3 Proof of Lemma 4

• For x > 0 and c > 1, log(1 + cx) < c log(1 + x), an inequality used to derive a schedule bound.Source: §B.4.3 · p. 24
• The function q log q − (q − 1) increases for q > 1, supporting the derivation of the schedule conditions.Source: §B.4.3 · p. 24
• The proof establishes schedule condition (40c) using the preceding bound and positivity.Source: §B.4.3 · p. 25
• The proof establishes conditions (40d) and (41) using positivity and the preceding ratio bounds.Source: §B.4.3 · p. 25

B.4.4 Proof of Lemma 5

• Finiteness of BK implies bk ∈ L2 for 1 ≤ k ≤ K − 1, while the proof also establishes ξk ∈ L2.Source: §B.4.4 · p. 25
• Induction and closure under finite linear combinations establish square-integrability of the iterates and query/update variables, including yk, zk, Tzk, b^T_k(zk), and xk+1.The argument uses that T maps L2 random variables to L2 random variables.Source: §B.4.4 · pp. 25–26
• The proof obtains yk and zk in L2 for every 1 ≤ k ≤ K without using the K-th oracle call or assuming bK is square-integrable.Source: §B.4.4 · p. 26

B.4.5 Proof of Lemma 6

• The half-iterate error Sk bridges the proof: Ψk+1 is bounded using ∥Sk∥² and ∥Gpk+1∥², which are then bounded in terms of Ψk to obtain (123).Source: §B.4.5 · pp. 27–29
• Monotonicity and positive schedule parameters bound the cross term in the potential estimate, while the coefficient on ∥Sk∥² is shown to be at most one.Source: §B.4.5 · pp. 27–28
• Substituting the corrected query-point relation into the inertial update expresses zk+1 using xk and ezk − xk.Source: §B.4.5 · p. 27
• The proof uses a vector that is Fk-measurable and square-integrable, together with the oracle second-moment bound, in its conditional estimate.Source: §B.4.5 · pp. 28–29