Stochastic gradient descent on Riemannian manifolds

Silvere Bonnabel

Source-linked AI summary

Stochastic gradient descent on Riemannian manifolds

Silvere Bonnabel

arXiv:1111.5280v4Nov 22, 2011math.OCcs.LGstat.ML

TL;DR

The paper addresses stochastic optimization when parameters lie on a Riemannian manifold rather than Euclidean space. It develops intrinsic gradient updates and proves almost-sure convergence under several settings, illustrating the approach in four applications.

Problem
Stochastic gradient descent lacks established almost-sure convergence guarantees for optimization problems on non-Euclidean spaces.
Method
The paper replaces Euclidean updates with intrinsic Riemannian-gradient steps using exponential maps or retractions, including curvature-adapted steps on selected manifolds.
Results
The proposed algorithms are proved to converge almost surely to critical points under assumptions covering compact trajectories, retractions, and selected negatively curved manifolds.
Takeaways & Limitations
The framework is versatile and potentially applicable to nonlinear problems in control, machine learning, and signal processing where manifolds enforce constraints or provide intrinsic algorithms.

Abstract

from arXiv · show

Stochastic gradient descent is a simple approach to find the local minima of a cost function whose evaluations are corrupted by noise. In this paper, we develop a procedure extending stochastic gradient descent algorithms to the case where the function is defined on a Riemannian manifold. We prove that, as in the Euclidian case, the gradient descent algorithm converges to a critical point of the cost function. The algorithm has numerous potential applications, and is illustrated here by four examples. In particular a novel gossip algorithm on the set of covariance matrices is derived and tested numerically.

1 Introduction

The paper extends stochastic gradient descent from noisy Euclidean optimization to intrinsic optimization on Riemannian manifolds, establishing almost-sure convergence and illustrating the framework through four applications.

Motivation: Stochastic approximation minimizes costs whose evaluations are corrupted by noise, building on gradient-based procedures such as Robbins–Monro.The Euclidean update uses noisy gradient evaluations and decreasing step sizes.
Contribution: The proposed manifold algorithms are intrinsic and independent of any particular embedding or local coordinate system.
Convergence: The paper proves almost-sure convergence of the proposed algorithms to critical points under assumptions extending established Euclidean results to non-Euclidean spaces.
Applications: Four examples apply the algorithms and convergence results, including online PCA, hyperbolic intrinsic means, positive-semidefinite matrix estimation, and a further numerical application.

2 Stochastic gradient on Riemannian manifolds

The paper replaces Euclidean noisy gradient updates with intrinsic manifold steps, using exponential maps or retractions while addressing constrained matrix estimation through Riemannian geometry.

Problem setup: The stochastic objective is an expected loss C(w)=E_zQ(z,w), accessed through independent observations because the underlying distribution is unknown.
Matrix constraints: For low-rank matrix estimation, unconstrained stochastic updates generally leave the fixed-rank manifold, while projection back to the manifold can be costly.
Intrinsic update: The proposed update moves along a manifold geodesic using a tangent-vector stochastic Riemannian gradient, reducing to the ordinary Euclidean update in R^n.
Intrinsic update: The procedure is coordinate-independent, and a retraction provides a first-order-computable alternative when evaluating the exponential map is difficult.Retractions approximate the exponential map with distance error O(t^2).
Retractions: On the sphere, a retraction can be implemented by adding in the ambient space and projecting back onto the sphere.

3 Convergence results

The paper derives almost-sure convergence results for intrinsic stochastic gradient methods on compact and selected noncompact manifolds, including versions based on retractions and curvature-adapted steps.

Convergence results: Three general convergence results cover compact trajectories, twice continuously differentiable retractions, and modified updates for negatively curved manifolds.
Compact trajectories: The compact-set theorem applies in particular to connected compact manifolds, including spheres, rotation groups, Grassmann manifolds, and Stiefel manifolds.
Hadamard manifolds: On negatively curved manifolds, adaptive step sizes account for destabilizing curvature effects and prove almost-sure confinement and convergence under mild Euclidean-like assumptions.Examples include the Poincaré disk, Poincaré half-plane, and positive-definite matrix space.
Compact trajectories: On a connected manifold with a compact trajectory set, bounded gradients, and standard step-size conditions, the cost converges almost surely and the gradient tends to zero almost surely.
Retractions: The same almost-sure convergence conclusion holds when the exponential map is replaced by a twice continuously differentiable retraction.
Hadamard manifolds: The Hadamard-manifold assumptions relax standard Euclidean moment conditions but require users to provide an upper bound involving distance from a reference point v.The paper notes that suitable reference points may be straightforward to identify in applications.

4 Examples

Four examples apply the proposed algorithms and convergence results, with the latter two including numerical experiments.

Examples: The first two examples are tutorial applications, while the third and fourth are more detailed and include numerical experiments.

4.1 Subspace tracking

The paper formulates online PCA as stochastic optimization on the Grassmann manifold and proves almost-sure convergence to covariance-matrix invariant subspaces. A retraction-based update preserves convergence while reducing the per-step cost relative to geodesic updates.

Online PCA estimates an r-dimensional subspace from streaming n-dimensional vectors with covariance matrix A.
The Grassmann manifold Gr(r,n) represents r-dimensional subspaces, equivalently rank-r orthogonal projectors.
The stochastic Riemannian gradient algorithm converges almost surely to an invariant subspace of covariance matrix A.Under the stated bounded-input conditions, convergence follows from the general theorem for stochastic Riemannian gradient descent.
The dominant subspace associated with the first r eigenvalues is the only stable subspace of the averaged algorithm under basic assumptions.
The QR-based retraction replaces each geodesic SVD update with ambient gradient motion followed by orthonormalization.The retraction is infinitely differentiable and yields Oja’s vector field for subspace tracking.
Geodesic updates cost O(nr^2)+O(r^3), whereas retraction updates cost O(nr^2), making them advantageous when r is large.

4.2 Randomized computation of a Karcher mean on a hyperbolic space

The paper applies stochastic Riemannian gradient descent to compute Karcher means on the Poincaré disk. Randomly sampled point updates converge almost surely to the Karcher mean under boundedness and geometric assumptions.

The Poincaré disk is a hyperbolic space whose boundary lies at infinite distance, with geodesics given by orthogonal circular arcs or diameters.
The Karcher mean minimizes the sum of squared geodesic distances and is unique on Hadamard manifolds.
The randomized algorithm samples one point uniformly at each step and uses half the squared geodesic distance as its loss.The stochastic gradient is the Riemannian gradient of that sampled loss.
On the Poincaré disk, the Riemannian gradient follows the same direction as the Euclidean gradient and has norm d(z_t,w_t).
Randomized updates can reduce computational burden when data are redundant and can filter noisy measurements of a slowly moving point.In Euclidean space, the update becomes a first-order discrete low-pass filter computing a weighted mean.
The iterates converge almost surely to the Karcher mean of the points z_1, ..., z_N.
The convergence proof uses a geodesic-ball condition, curvature −1, and bounded stochastic-gradient norms.
Choosing the auxiliary point v may require knowledge of d(w_t,v), although v=0 is an obvious choice in this example.

4.3 Identification of a fixed rank symmetric positive semi-definite matrix

The paper applies its Riemannian stochastic-gradient framework to online identification of fixed-rank positive semidefinite matrices, using factorized representations that preserve rank and positivity. Under Gaussian inputs, the method converges to the true matrix in the full-rank case and to an invariant subspace in the rank-deficient case, while offering computational advantages for low rank.

Problem formulation: The target matrix W is positive semidefinite and is estimated online from noisy expert-provided outputs using a stochastic-gradient cost function.The model represents kernels or Mahalanobis distances, and the objective is the expected squared prediction loss.
Manifold formulation: Representing W as G G^T reduces a rank-r matrix problem to factors G ∈ R^(n×r), supporting scalable low-rank estimation.The fixed-rank positive semidefinite manifold is modeled through square-root factorization and a quotient-space geometry.
Algorithm: The Riemannian gradient is H(z_t, G_t) = 2(ŷ_t − y_t)x_t x_t^T G_t, and adaptive scaling makes the nonlinear update well-defined on equivalence classes while enforcing rank and positivity.The scaling choice is f(G_t) = max(1, ∥G_t∥^6), with step sizes satisfying the paper’s standard conditions.
Convergence: Almost surely, W_t converges to W_∞ with ∇C(W_t) → 0; when r = n, W_∞ = V, while for r < n it converges to an invariant r-dimensional subspace of V.If that subspace is V’s dominant subspace, the limit equals V; simulations indicate other invariant subspaces are unstable.
Simulation results: The rank-3, 100×100 simulation asymptotically identifies V, with estimation error decreasing rapidly initially and then slowly approaching zero.As iterations increase, the estimation error becomes arbitrarily small in the reported simulations.
Simulation results: In the full-rank comparison, the proposed method has comparable performance but is slightly slower than projected Euclidean stochastic gradient, while its low-rank complexity is linear in n rather than at least O(n^2).The comparison is favorable to the proposed method when rank is low, where diagonalization-based projection can become intractable and nonconvexity can degrade approximation-then-projection methods.

4.4 Non-linear gossip algorithm for decentralized covariance matrix estimation

The paper develops a Riemannian gossip algorithm for decentralized covariance estimation, using the Fisher information geometry on positive definite matrices. Random neighboring-node updates converge to consensus and are faster than Euclidean gossip, especially for heterogeneous initial matrices.

Covariance estimation: The problem is decentralized estimation of a covariance matrix from measurements distributed across sensor-network nodes.Each node begins with an estimated covariance matrix, and neighboring nodes exchange information at random times.
Statistically meaningful geometry: The Fisher information metric supplies a statistically meaningful geometry on positive definite matrices, with distances linked to Kullback–Leibler divergence.The associated Karcher mean is also described as more robust to outliers than the arithmetic mean.
Randomized algorithm: At each step, a randomly selected neighboring pair moves toward one another along their geodesic; γ_t = 1/2 places the update halfway between them.The procedure is an application of the paper’s general Riemannian stochastic-gradient update.
Theoretical properties: The algorithm is invariant under invertible linear coordinate changes and, under the stated step-size conditions, all covariance matrices converge almost surely to a common value.The invariance acts by congruence, mapping each matrix W to GWG^T.
Simulation results: In simulations with n = 10 and m = 6, Riemannian gossip converges faster on average than usual gossip, particularly when initial matrices are far apart or heterogeneous.The comparison averages results over 50 runs and uses both averaged cost and convex-hull diameter criteria.

5 Conclusion

The paper establishes stochastic gradient descent on Riemannian manifolds and proves convergence under reasonable assumptions. It presents the approach as versatile, while identifying further convergence questions for matrix completion and broader stochastic consensus settings.

Conclusion: The paper proposes a stochastic gradient algorithm on Riemannian manifolds and proves its convergence under reasonable assumptions.The convergence result also holds when a retraction is used.
Conclusion: The framework is potentially applicable to nonlinear problems in control, machine learning, and signal processing.The manifold formulation can enforce constraints or produce intrinsic algorithms.
Conclusion: The paper connects its framework to Amari’s natural gradient, which has produced substantial gains in blind source separation.The natural gradient is obtained in the Fisher-metric setting with a simple retraction.
Conclusion: Future work includes convergence analysis for matrix completion and more general nonlinear consensus on complete manifolds with stochastic communication graphs.The authors also seek to understand whether hyperbolic geometry can accelerate consensus algorithms.

Appendix A: Links with information geometry

The appendix relates the proposed Riemannian stochastic-gradient method to information geometry and Amari’s natural gradient. In the Fisher metric with a trivial retraction, the method yields an asymptotically efficient estimator.

Natural gradient: The Fisher information matrix defines a Riemannian structure on the parameter space, and the corresponding gradient rescales the conventional Euclidean gradient.With addition as retraction and γ_t = 1/t, this becomes Amari’s natural-gradient update.
Statistical efficiency: The paper concludes that, with the Fisher metric and trivial retraction, its stochastic-gradient method provides an asymptotically efficient estimator.The natural gradient has also been applied to blind source separation with substantial performance gains.
Open question: Whether the estimator achieves the intrinsic Cramér–Rao bound is left for future research.The appendix explicitly places this result beyond the scope of the paper.

Appendix B: Riemannian geometry background

The appendix introduces the geometric objects used by the algorithm: geodesics, exponential maps, injectivity radius, gradients, and Hessians. These definitions explain how distance and descent directions are constructed intrinsically on a Riemannian manifold.

Basic geometry: A Riemannian manifold is a metric space whose distance is the length of a minimizing path between points.The length is defined from the manifold’s metric tensor.
Geodesics and exponential maps: A geodesic is the unique locally shortest path between sufficiently close points, and exp_x(v) maps a tangent vector to the corresponding point on that geodesic.The inverse exponential map returns the tangent vector from x to the point.
Geodesics and exponential maps: The injectivity radius bounds geodesic balls within which the exponential-map construction remains unambiguous.A geodesic ball is defined to have radius below the injectivity radius at its center.
Differential operators: The Riemannian gradient is the tangent vector representing directional change through the metric inner product, while the Hessian is defined through second derivatives.These objects provide the intrinsic analogues of Euclidean derivatives.
Distance gradients: For half the squared distance to a point p, the gradient at x is the inverse exponential-map vector exp_x^-1(p), with norm d(p,x).It is tangent to the geodesic linking x and p.