Stochastic Riemannian optimization and rates

At iteration k, let the history determine x_k and let G_k belong to TₓₖM. Conditional unbiasedness means its expectation given that history equals grad f(x_k), using the linear structure of this fixed tangent space. Bound its conditional squared deviation by σ². Also assume ∥G_k∥≤B almost surely and that all iterates lie in a fixed compact region. The bounded-sample condition gives a safe retraction step size; compactness supplies uniform local regularity constants only when the objective and retraction are smooth on a surrounding neighborhood.

A sphere example projects a bounded random ambient vector a onto the current tangent plane. For the linear sample objective aᵀx, this is its induced-metric sample gradient. If a has the appropriate mean, projection preserves conditional unbiasedness when the sample law given the history has that mean. Fresh independent samples are one sufficient construction, while dependent data require an explicit conditional analysis. Unbiasedness of the tangent estimate does not say the retracted next point is an unbiased ambient average, because the retraction is nonlinear.

Assume f is bounded below by f_inf along the region of interest. Require the uniform pullback inequality f(Rₓ(v))≤f(x)+gₓ(grad f,v)+(L/2)∥v∥² for every trial vector of norm at most r at the relevant iterates. Choose a constant step η≤1/L with ηB≤r. Conditioning on the history and using the variance decomposition bounds expected one-step change by minus η/2 times the squared gradient norm plus Lη²σ²/2. This argument requires the bound for the actual sampled steps, not just for the deterministic mean direction.

Summing over T transitions telescopes the objective and gives the displayed average-gradient estimate, with Δ_f=f(x₀)−f_inf. Choosing η=η₀/√T, where η₀>0 is fixed and T is large enough for the stated step restrictions, yields order T⁻¹/² in expected squared gradient norm. Equivalently, a uniformly selected output iterate has that expectation bound. To make it at most ε² therefore needs order ε⁻⁴ transitions under these nonconvex bounded-variance assumptions. This is not a bound on distance to a minimizer or on objective suboptimality without additional geometry.

Classical stochastic approximation instead uses positive decreasing steps whose sum diverges while their squared sum converges. For a C³ objective on a connected manifold with uniformly positive injectivity radius, independent data samples giving bounded unbiased tangent estimates and compact containment, Bonnabel’s manifold results give almost-sure convergence of objective values and decay of gradient norms, for the exponential update and suitable twice continuously differentiable retractions. Those conclusions do not by themselves prove convergence of the full point sequence to one selected minimizer. Extra assumptions are needed to exclude wandering among critical points or to identify a desired solution.

A finite-horizon constant step chosen from T is a different schedule, so its rate should not be presented as the same theorem. Mini-batching independent tangent estimates reduces conditional variance by the batch size, while correlation can spoil that factor. Strong geodesic convexity, variance reduction or special quotient structure can support sharper conclusions, but only on domains and under regularity assumptions that are actually verified. Reporting the target quantity, sampling model, metric and step policy makes a stochastic guarantee interpretable and prevents a stationary-point certificate from being mistaken for global learning success.