Convergence guarantees for stochastic algorithms solving non-unique problems in metric spaces
Abstract
We prove a general quantitative theorem on the asymptotic behavior of stochastic quasi-Fejér monotone sequences in a broad metric context. Concretely, our result explicitly constructs a rate of convergence for such process, both in mean and almost surely, under an abstract stochastic regularity assumption, derived from previous work of Kohlenbach, López-Acedo and Nicolae [Isr. J. Math. 232(1), pp. 261-297, 2019] on such notions in a deterministic context. Our notion of regularity extends and unifies many common conditions from the literature, such as generalized contractivity for self maps, weak sharp minima and error bounds for real-valued functions, uniform monotonicity and global metric subregularity for set-valued operators, related Polyak-Łojasiewicz or Kurdyka-Łojasiewicz conditions, as well as expected sharp growth as e.g. studied by Asi and Duchi [SIAM J. Optim. 29(3), pp. 2257-2290, 2019]. The rate is moreover highly uniform, depending only on very few data of the surrounding objects. We also discuss special cases which allow for the construction of fast rates in the form of linear non-asymptotic guarantees. We conclude by presenting three concrete methods from stochastic approximation where our results yield new rates of convergence, including the classical example of the stochastic proximal point method, a randomized variant of the Krasnoselskii-Mann scheme for solving stochastic fixed-point equations, and a Busemann subgradient method recently introduced by Goodwin, Lewis, López-Acedo and Nicolae [Math. Program., to appear], all of which make use of our metric generality by being formulated over complete geodesic metric spaces of nonpositive curvature.
Related
- A note on the convergence guarantees of RLT-based algorithms for polynomial optimization
- Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities
- Global Convergence of DGM and PINN Algorithms for Solving Nonlinear PDEs
- Stochastic Augmented Lagrangian Framework with Second-Order Convergence Guarantees for Nonconvex Expectation-Constrained Optimization
- Learning to Solve Two-Stage Stochastic Unit Commitment Problems with Quality Guarantees
BibTeX
@misc{pischke2026convergence,
title = {{Convergence guarantees for stochastic algorithms solving non-unique problems in metric spaces}},
author = {Nicholas Pischke and Thomas Powell},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2605.06129},
eprint = {2605.06129},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.06129},
}
RIS
TY - UNPB
TI - Convergence guarantees for stochastic algorithms solving non-unique problems in metric spaces
AU - Nicholas Pischke
AU - Thomas Powell
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2605.06129
UR - https://arxiv.org/abs/2605.06129
AB - We prove a general quantitative theorem on the asymptotic behavior of stochastic quasi-Fejér monotone sequences in a broad metric context. Concretely, our result explicitly constructs a rate of convergence for such process, both in mean and almost surely, under an abstract stochastic regularity assumption, derived from previous work of Kohlenbach, López-Acedo and Nicolae [Isr. J. Math. 232(1), pp. 261-297, 2019] on such notions in a deterministic context. Our notion of regularity extends and unifies many common conditions from the literature, such as generalized contractivity for self maps, weak sharp minima and error bounds for real-valued functions, uniform monotonicity and global metric subregularity for set-valued operators, related Polyak-Łojasiewicz or Kurdyka-Łojasiewicz conditions, as well as expected sharp growth as e.g. studied by Asi and Duchi [SIAM J. Optim. 29(3), pp. 2257-2290, 2019]. The rate is moreover highly uniform, depending only on very few data of the surrounding objects. We also discuss special cases which allow for the construction of fast rates in the form of linear non-asymptotic guarantees. We conclude by presenting three concrete methods from stochastic approximation where our results yield new rates of convergence, including the classical example of the stochastic proximal point method, a randomized variant of the Krasnoselskii-Mann scheme for solving stochastic fixed-point equations, and a Busemann subgradient method recently introduced by Goodwin, Lewis, López-Acedo and Nicolae [Math. Program., to appear], all of which make use of our metric generality by being formulated over complete geodesic metric spaces of nonpositive curvature.
ER -