Pith. sign in

REVIEW 4 minor 44 references

Krasnosel'skii-Mann iterations beyond asymptotics: a combinatorial analysis

T0 review · 0 major / 4 minor · reviewed 2026-08-01 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper derives an exact, closed-form expression for the finite-step residual bound of the Krasnosel'skii–Mann iteration, showing geometric decay for contractions and continuous recovery of the nonexpansive bound as the contraction factor

desk verdict Solid, well-proved paper that turns a known recursion into an explicit, usable bound for KM residuals; the κ caveat is real but standard. read the letter →

arxiv 2607.18121 v1 pith:WKQFGWCM submitted 2026-07-20 math.NA cs.NA

Mario Bravo , Roberto Cominetti This is my paper · ORCID
classification math.NAcs.NA MSC 47J2547J2665J1533C0533C6533C9065K15
keywords fixedpointiterationscontractivemapserrorboundslatticepathsunder-relaxedPicardhypergeometricfunctionsKrasnosel'skii-Manniterationnon-asymptotic
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper establishes that the Krasnosel'skii–Mann under-relaxed iteration, applied to an ℓ-Lipschitz map on a convex set of diameter at most κ, satisfies the explicit finite-step bound ∥x_m − T x_m∥ ≤ κ R_m, where R_m is given by a closed-form expression with a hypergeometric function and an integral. For strict contractions the bound decays geometrically, and as the contraction factor tends to 1 it continuously recovers the classical nonexpansive bound. The same formulas yield the optimal relaxation parameter and error bounds for inexact iterations. If correct, this converts an asymptotic convergence theorem into a computable, parameter-explicit guarantee useful for optimization, Markov decision processes, and under-relaxed numerical solvers.

What carries the argument

The paper's engine is the family of coefficients c_{m,n} bounding distances between iterates by κ c_{m,n}. These coefficients satisfy a two-term recursion, and the paper interprets them as absorption probabilities in a Markov chain on Z^2 with two absorbing states. A bijection between winning paths and simple lattice paths under the diagonal allows exact counting via binomial differences, giving closed-form sums for c_{m,n}. From there, probabilistic representations in terms of binomial counting processes, followed by the residue theorem, produce the integral and hypergeometric formulas for the residual bound R_m. The same chain perspective, with rewards added at transient states, yields the

What would settle it

Take a concrete contractive map on a bounded set, e.g., T x = ℓ·x on [−1,1] with κ=2 and α=1/2, run the KM iteration numerically, and compare the observed residual ∥x_m − T x_m∥ to κ R_m for a range of m and ℓ (say ℓ=0.9, 0.99, m up to 100). Any observed residual exceeding the bound would falsify Theorem 2. Alternatively, verify the equality of the two representations (7) and (4) for R_m at random parameters, since (4) follows from the recursive definition and (7) is claimed as an identity.

Watch

Extended reading notes

Core claim

The central claim is an exact identity for the residual bound. For every m≥0, R_m equals (1−ℓ)ℓ_α^m plus a positive integral times s_α^m, with s_α=(1−α+α√ℓ)^2; for ℓ<1 this can be written using an Euler integral as R_m = (1−ℓ)ℓ_α^m + (ℓ/(1−√ℓ)^2) F_1(3/2;−m,1;3;η,−ξ) s_α^m, and at ℓ=1 it reduces to 2F1(1/2,−m;2;4α(1−α)). The derivation shows that the recursive distance coefficients c_{m,n} are absorption probabilities of a Markov chain on Z^2 whose winning paths are counted by lattice-path enumeration, yielding finite sums first and then the integral form. The identity smoothly connects the contractive and nonexpansive regimes, answering the motivating question.

Load-bearing premise

The bound requires a finite, known a priori diameter κ of the domain (or a uniform bound on ∥x_0 − T x_m∥); if κ is unknown or extremely large, the explicit residual bound is either unavailable or too loose to be useful.

Editorial extensions

If this is right

  • Every ℓ-Lipschitz KM iterate on a set of diameter ≤κ satisfies ∥x_m − T x_m∥ ≤ κ R_m, with R_m computable in closed form for any m, α, ℓ.
  • For ℓ<1 the bound decays geometrically, so long-horizon problems such as discounted Markov decision processes with discount factor near 1 get explicit non-asymptotic guarantees.
  • The formula reproduces the classical nonexpansive bound as ℓ→1, so the contractive and nonexpansive regimes are bridged by a single continuous estimate.
  • The uniqueness and asymptotics of the optimal relaxation parameter give a principled selection rule: for ℓ≤1/2 use α=1, and for ℓ>1/2 use α≈1−c*_ℓ/m.
  • For inexact iterations, the error bound takes the form of a discrete convolution of the residual bound with the noise sequence, so the effect of computation errors can be propagated explicitly.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The explicit rate s_α^m implies a crossover iteration count m* where geometric decay overtakes the nonexpansive O(1/√m) behavior; estimating m* from the formula could guide adaptive algorithms that switch from KM to the unrelaxed iteration.
  • The bound suggests a quantitative 'near-nonexpansive' regime: for ℓ=1−ε the initial iterations track the nonexpansive envelope for roughly O(1/ε) steps before contraction dominates.
  • The same Markov-chain/lattice-path technique may extend to variable relaxation parameters α_m or to stochastic variants of KM, where closed-form bounds are largely missing.
  • If the conjectured relative gap R_m/S_m ≤ √(3/2) holds, then the closed-form bound is within 23% of the minimax-tight bound, making it a safe drop-in for rigorous stopping criteria.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper derives explicit non-asymptotic bounds for the fixed-point residuals of Krasnosel'skii–Mann iterations for ℓ-Lipschitz maps on convex subsets of normed spaces. The main quantity R_m (defined as c_{m,m+1}/α) is shown to satisfy a closed-form expression in terms of (1−ℓ)ℓ_α^m plus an integral/hypergeometric term involving s_α=(1−α+α√ℓ)^2; as ℓ→1 this recovers the Baillon–Bruck nonexpansive bound. The proof strategy combines a recursive estimate (11) with an absorbing Markov chain on Z^2, lattice-path enumeration (Theorem 3), and hypergeometric/integral representations (Propositions 7–8, Theorem 2). The paper also analyses the optimal choice of the relaxation parameter α, gives asymptotic expansions for the minimizer, and extends the bounds to inexact iterations (Theorem 14).

Significance. If correct, this is a substantial contribution to the quantitative analysis of KM iterations. It provides explicit, computable residual bounds that decay geometrically for ℓ<1 and that interpolate smoothly to the nonexpansive Baillon–Bruck bound as ℓ→1. The formulas are derived without any fitted parameters: α is a user-chosen relaxation and ℓ, κ are problem inputs. The derivation is transparent and self-contained, with the lattice-path counting and integral representations carefully justified. The comparison with the minimax-tight transport bounds S_m is honest and non-circular, including a rigorous absolute-gap estimate (Proposition 20) and extensive numerical evidence. The dependence of the bound on the diameter/a-priori constant κ is explicitly stated as an input, which is a standard applicability condition rather than a correctness gap.

minor comments (4)
  1. [§2.7, Theorem 6] Theorem 6 is stated without proof; the text says the proofs 'follow step by step' from [6]. Since this theorem is not used in the derivation of the main results, this is not load-bearing, but the authors should either provide the proofs in an appendix or explicitly state it as a known result with a precise reference.
  2. [Figure 1 caption] The caption says 'Already for ℓ=0.9 the (km) bound improves upon Banach–Picard's coarse bound', but the improvement occurs only for a range of iteration counts, not uniformly in m. Rephrasing to 'can improve over a range of m' would be more accurate.
  3. [Abstract and Disclosure] There are minor typographical issues, e.g. 'fix ed' in the abstract and the rendering 'Krasnosel'ski ˘ ı–Mann' in the Disclosure. These do not affect the mathematics.
  4. [§4.2.1, Proposition 11] The proof of (34) uses uniform convergence and strong convexity of Ψ_ℓ. The statement is correct, but it would be helpful to note explicitly that the constants in the O(1/m^{3/2}) term depend on ℓ, as they do in (33).

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the central bound is self-contained; self-cited optimal-transport comparison is non-load-bearing.

full rationale

The paper's central claim, the explicit formula for R_m (Theorem 2), is derived from the KM iteration itself rather than from the result it purports to establish. The recursion (11) is obtained from the convex-combination identity for x_m and the Lipschitz/triangle inequality; the Markov-chain interpretation and lattice-path enumeration in Section 2 provide a closed-form solution (4)-(5) using Krattenthaler's external enumeration theorem [25]. Theorem 2's integral and hypergeometric representations (23)-(25) follow from Proposition 8 via Cauchy's residue theorem and Euler's integral representations, with the ℓ=1 case obtained by dominated convergence from the same formula, not by inserting Baillon-Bruck's bound (3). The optimization and inexact-iteration results depend only on R_m and elementary estimates. The κ-dependence is an explicitly stated input (diameter or a priori bound), not a fitted parameter. The only self-citations that could be questioned are in Section 2.7: Theorem 5 is quoted from [9] for minimax tightness of S_m, and the proof of Theorem 6 is omitted with a pointer to [6]; these support the R_m-versus-S_m comparison and the conjecture R_m/S_m ≤ sqrt(3/2), but they are not used to prove the main R_m formula. Hence there is no load-bearing circularity; the minor non-load-bearing self-citation warrants only a low score.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central derivation introduces no fitted constants and no new physical or mathematical entities: α, ℓ, and κ are inputs, and the Markov chain is a proof device rather than a postulated object. The main external inputs are standard lattice-path and hypergeometric results.

assumptions (5)
  • domain assumption T is ℓ-Lipschitz with ℓ∈(0,1] on a convex subset C of a normed space, with either diam(C)≤κ or an a priori bound ∥x0 - T x_m∥≤κ.
    This is the stated setting of Theorem 1 and the coarse estimate entering recursion (11); all bounds scale with κ.
  • standard math Krattenthaler's lattice-path enumeration theorem [25, Thm 10.14.1] for simple paths weakly below the diagonal with a given number of east-north turns.
    Used in §2.4 to count H-winning paths; cited external result, not proved in the paper.
  • standard math Euler integral representations of Gauss 2F1 and Appell F1 hypergeometric functions (Appendix A).
    Used to derive formulas (6), (9), (16), (17), and the ℓ→1 limit.
  • standard math Cauchy's residue theorem and trigonometric inversion for lattice-path generating functions.
    Used in §3.2 to derive the integral representation (20) for c_{m,n}.
  • domain assumption For inexact iterations, errors satisfy ∥e_m∥≤κ ε_m and T x_m + e_m ∈ C.
    Used in Theorem 14; the projection remark shows how to relax the domain-inclusion condition at the cost of an error factor.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Krasnosel'skii-Mann iterations beyond asymptotics: a combinatorial analysis." pith.science (2026). https://pith.science/paper/WKQFGWCM

@misc{pith2026260718121,
  author       = {Pith},
  title        = {Pith review of: Krasnosel'skii-Mann iterations beyond asymptotics: a combinatorial analysis},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WKQFGWCM}},
  note         = {Machine review of arXiv:2607.18121}
}
abstract

We revisit the classical Krasnosel'skii-Mann fixed point iteration for contractions and nonexpansive maps in general normed spaces. This iteration is ubiquitous across a wide range of areas, including convex optimization, monotone inclusions, Markov decision processes, under-relaxed methods for nonlinear PDEs, and more. Drawing on a remarkable connection with a Markov chain on $\mathbb{Z}^2$, and using counting arguments from enumerative combinatorics of lattice paths, we derive explicit estimates for the distance between iterates, as well as non-asymptotic error bounds for the fixed point residuals. As the contraction parameter approaches one, these bounds smoothly recover the known estimates for nonexpansive maps. Building upon these estimates, we further derive error bounds for inexact Krasnosel'skii-Mann iterations.

Figures

Figures reproduced from arXiv: 2607.18121 by the authors.

Figure 1
Figure 1. Krasnosel’skii–Mann bound κ Rm (blue) and Banach–Picard coarse bound κ ℓ m (red) as functions of the iteration m, for κ = 1 and different relaxation parameters α and contraction factors ℓ . Already for ℓ = 0.9 the (km) bound improves upon Banach–Picard’s coarse bound, particularly with α = 0.9. The improvement becomes increasingly pronounced as the contraction factor ℓ approaches 1. Note however that comparing the u… view at source ↗
Figure 2
Figure 2. An H-winning path and its reflected lattice path Proof. Let pm,n be the probability that the chain is absorbed at the H-winning state sh, when starting from s0 = (m, n) ∈ D. By conditioning on the first jump it follows that pm,n satisfies exactly the same recursion (11), with p0,n = 1 − π n 0 = c0,n, and therefore cm,n = pm,n for all (m, n) ∈ D. □ 2.3. Stratification of H-winning paths. By partitioning the set of al… view at source ↗
Figure 3
Figure 3. The optimal transport z for dm,n when α ∈ [ 1 2 , 1] (left) and the feasible transport ˜z for cm,n (right). In both cases the demands π n i at destinations i ∈ {0, . . . , m} are shipped at zero cost directly from their twin sources i (horizontal arrows). The transports differ in how they manage the excess supplies π m i −π n i at the sources, to meet the demands at destinations j ∈ {m+ 1, . . . , n}. The feasible t… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Residual bounds after m = 10 iterations as a function of ℓ ∈ [ 1 2 , 1], for different relaxation parameters α. The brown dashed curve is the normalized coarse Banach–Picard bound ℓ m. The blue and red curves—barely distinguishable in the center and right panels— corre…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

44 extracted references · 1 linked inside Pith

  1. [1]

    and Bruck, R

    Baillon, J.-B. and Bruck, R. E. (1992). Optimal rates of asymptotic regularity for averaged nonexpansive mappings. In Proceedings of the Second International Conference on Fixed Point Theory and Applications (K.K. Tan, ed.). World Scientific Press, London, 27--66

    1992

  2. [2]

    and Bruck, R

    Baillon, J.-B. and Bruck, R. E. (1996). The rate of asymptotic regularity is O (1/ n ) . In Theory and Applications of Nonlinear Operators of Accretive and Monotone Types, Lecture Notes in Pure Appl. Math. 178. Marcel Dekker, New York, 51--81

    1996

  3. [3]

    , Bruck, R

    Baillon, J.-B. , Bruck, R. E. and Reich, S. (1978). On the asymptotic behavior of nonexpansive mappings and semigroups in B anach spaces. Houston J. Math., 4 1--9

    1978

  4. [4]

    Bauschke, H. H. and Combettes, P. L. (2011). Convex Analysis and Monotone Operator Theory in Hilbert Spaces. CMS Books in Mathematics, Springer, New York

    2011

  5. [5]

    , Reich, S

    Borwein, J. , Reich, S. and Shafrir, I. (1992). Krasnosel'skii-Mann iterations in normed spaces . Canadian Mathematical Bulletin, 35 21--28

    1992

  6. [6]

    , Champion, T

    Bravo, M. , Champion, T. and Cominetti, R. (2022). Universal bounds for fixed-point iterations via optimal transport metrics. Applied Set-Valued Analysis and Optimization, 4 293--310

    2022

  7. [7]

    and Cominetti, R

    Bravo, M. and Cominetti, R. (2018). Sharp convergence rates for averaged nonexpansive maps. Israel Journal of Mathematics, 227 163--188

    2018

  8. [8]

    and Cominetti, R

    Bravo, M. and Cominetti, R. (2024). Stochastic fixed-point iterations for nonexpansive maps: Convergence and error bounds. SIAM Journal on Control and Optimization, 62 191--219

    2024

Show all 44 references
  1. [9]

    , Cominetti, R

    Bravo, M. , Cominetti, R. and Lee, J. (2026). Minimax-optimal H alpern iterations for L ipschitz maps. arXiv:2601.15996

    2026

  2. [10]

    , Cominetti, R

    Bravo, M. , Cominetti, R. and Pavez-Sign \'e , M. (2019). Rates of convergence for inexact K rasnosel'skii-- M ann iterations in B anach spaces. Mathematical Programming, 175 241--262

    2019

  3. [11]

    Browder, F. E. and Petryshyn, W. V. (1966). The solution by iteration of nonlinear functional equations in B anach spaces. Bulletin of the American Mathematical Society, 72 571--575

    1966

  4. [12]

    , Soto, J

    Cominetti, R. , Soto, J. A. and Vaisman, J. (2014). On the rate of convergence of K rasnosel'skii- M ann iterations and their connection with sums of B ernoullis. Israel Journal of Mathematics, 199 757--772

    2014

  5. [13]

    Contreras, J. P. and Cominetti, R. (2023). Optimal error bounds for non-expansive fixed-point iterations in normed spaces. Mathematical Programming, 199 343--374

    2023

  6. [14]

    Dotson, W. (1970). On the M ann iterative process. Transactions of the American Mathematical Society, 149 65--73

    1970

  7. [15]

    Edelstein, M. (1966). A remark on a theorem of M.A. Krasnosel'skii . American Mathematical Monthly, 73 509--510

    1966

  8. [16]

    and O'Brien, R

    Edelstein, M. and O'Brien, R. C. (1978). Nonexpansive mappings, asymptotic regularity and successive approximations. Journal of the London Mathematical Society, 17 547--554

    1978

  9. [17]

    Feller, W. (1971). An Introduction to Probability Theory and Its Applications, vol. 2. 2nd ed. John Wiley & Sons, New York

    1971

  10. [18]

    Ferziger, J. H. , Perii\'c, M. and Street, R. L. (2020). Computational Methods for Fluid Dynamics . Springer International Publishing, Cham

    2020

  11. [19]

    Foglia, K. R. and Colao, V. (2025; revised 2026). On the rate of asymptotic regularity of iterative methods for nonexpansive mappings in CAT(0) spaces and hyperbolic optimization. arXiv:2510.25363v3

    2025 arXiv

  12. [20]

    and Kirk, W

    Goebel, K. and Kirk, W. A. (1983). Iteration processes for nonexpansive mappings. In Topological Methods in Nonlinear Functional Analysis, S. Singh, S. Thomeier, and B. Watson, eds. American Mathematical Society. Contemp. Math., 21, 115--123

    1983

  13. [21]

    Groetsch, C. (1972). A note on segmenting M ann iterates. Journal of Mathematical Analysis and Applications, 40 369--372

    1972

  14. [22]

    Halpern, B. (1967). Fixed points of nonexpanding maps. Bulletin of the American Mathematical Society, 73 957--961

    1967

  15. [23]

    Ishikawa, S. (1976). Fixed points and iteration of a nonexpansive mapping in a B anach space. Proceedings of the American Mathematical Society, 59 65--71

    1976

  16. [24]

    Krasnosel'skii, M. A. (1955). Two remarks on the method of successive approximations. Uspekhi Matematicheskikh Nauk, 10 123--127

    1955

  17. [25]

    Krattenthaler, C. (2015). Lattice path enumeration. In Handbook of Enumerative Combinatorics. CRC Press, Boca Raton, 589--678

    2015

  18. [26]

    Langtangen, H. P. and Linge, S. (2017). Finite Difference Computing with PDEs: A Modern Software Approach, vol. 16 of Texts in Computational Science and Engineering. Springer

    2017

  19. [27]

    Levin, D. A. , Peres, Y. and Wilmer, E. L. (2017). Markov Chains and Mixing Times. 2nd ed. American Mathematical Society, Providence, RI

    2017

  20. [28]

    Lieder, F. (2021). On the convergence rate of the H alpern-iteration. Optimization Letters, 15 405--418

    2021

  21. [29]

    Mann, W. R. (1953). Mean value methods in iteration. Proceedings of the American Mathematical Society, 4 506--510

    1953

  22. [30]

    , Mangani, L

    Moukalled, F. , Mangani, L. and Darwish, M. (2016). The Finite Volume Method in Computational Fluid Dynamics, vol. 113 of Fluid Mechanics and Its Applications. Springer, Cham

    2016

  23. [31]

    Ollivier, Y. (2010). A survey of R icci curvature for metric spaces and M arkov chains. In Probabilistic Approach to Geometry, vol. 57 of Advanced Studies in Pure Mathematics. Mathematical Society of Japan, Tokyo, 343--381

    2010

  24. [32]

    Outlaw, C. (1969). Mean value iteration of nonexpansive mappings in a B anach space. Pacific Journal of Mathematics, 30 747--750

    1969

  25. [33]

    and Ryu, E

    Park, J.-K. and Ryu, E. K. (2022). Exact optimal accelerated complexity for fixed-point iterations. In Proceedings of the 39th International Conference on Machine Learning, vol. 162 of Proceedings of Machine Learning Research. PMLR, 17420--17457

    2022

  26. [34]

    Patankar, S. V. (1980). Numerical Heat Transfer and Fluid Flow. McGraw-Hill, New York

    1980

  27. [35]

    Puterman, M. L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley, New York

    1994

  28. [36]

    Reich, S. (1979). Weak convergence theorems for nonexpansive mappings in B anach spaces. J. Math. Anal. Appl., 67 274--276

    1979

  29. [37]

    and Shafrir, I

    Reich, S. and Shafrir, I. (1990). Nonexpansive iterations in hyperbolic spaces. Nonlinear Analysis: Theory, Methods & Applications, 15 537--558

    1990

  30. [38]

    and Shtern, S

    Sabach, S. and Shtern, S. (2017). A first order method for solving convex bilevel optimization problems. SIAM Journal on Optimization, 27 640--660

    2017

  31. [39]

    Schaefer, H. (1957). \"U ber die methode sukzessiver approximationen. Jahresbericht der Deutschen Mathematiker-Vereinigung, 59 131--140

    1957

  32. [40]

    Schlosser, M. J. (2013). Multiple hypergeometric series: Appell series and beyond. In Computer Algebra in Quantum Field Theory: Integration, Summation and Special Functions (C. Schneider and J. Bl \"u mlein, eds.). Texts & Monographs in Symbolic Computation, Springer, Vienna, 305--324

    2013

  33. [41]

    Sutton, R. S. and Barto, A. G. (1998). Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA

    1998

  34. [42]

    Takahashi, W. (1970). A convexity in metric space and nonexpansive mappings. i. Kodai Mathematical Seminar Reports, 22 142--149

    1970

  35. [43]

    Wendel, J. G. (1948). Note on the gamma function. The American Mathematical Monthly, 55 563--564

    1948

  36. [44]

    Woess, W. (2000). Random Walks on Infinite Graphs and Groups, vol. 138 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge

    2000

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.