Mean-square and linear convergence of a stochastic proximal point algorithm in metric spaces of nonpositive curvature
This work extends stochastic optimization methods from Hilbert spaces to more general nonlinear spaces, addressing incremental theoretical advancements in optimization for domains with nonpositive curvature.
The paper tackles the problem of approximating zeros of the mean of a stochastically perturbed monotone vector field in nonlinear Hadamard spaces by defining a stochastic proximal point algorithm and proving its convergence. It achieves explicit, uniform rates of convergence in mean and almost surely, with linear nonasymptotic guarantees under certain conditions.
We define a stochastic variant of the proximal point algorithm in the general setting of nonlinear (separable) Hadamard spaces for approximating zeros of the mean of a stochastically perturbed monotone vector field and prove its convergence under a suitable strong monotonicity assumption, together with a probabilistic independence assumption and a separability assumption on the tangent spaces. As a particular case, our results transfer previous work by P. Bianchi on that method in Hilbert spaces for the first time to Hadamard manifolds. Moreover, our convergence proof is fully effective and allows for the construction of explicit rates of convergence for the iteration towards the (unique) solution both in mean and almost surely. These rates are moreover highly uniform, being independent of most data surrounding the iteration, space or distribution. In that generality, these rates are novel already in the context of Hilbert spaces. Linear nonasymptotic guarantees under additional second-moment conditions on the Yosida approximates and special cases of stochastic convex minimization are discussed.