From the Greene–Wu Convolution to Gradient Estimation over Riemannian Manifolds

The study of geometric methods in machine learning has never stalled. Researchers have investigated this topic from different angles, include kernel methods (e.g., Schölkopf et al.,, 2002; Muandet et al.,, 2017; Jacot et al.,, 2021), manifold learning (e.g., Lin and Zha,, 2008; Li et al.,, 2017; Zhu et al.,, 2018; Li and Dunson,, 2020), metric learning (e.g., Kulis et al.,, 2012; Li and Dunson,, 2019). Recently, attentions are concentrated on problems of learning with Riemannian geometry. Examples include convex optimization method over negatively curved spaces (Zhang and Sra,, 2016; Zhang et al.,, 2016), online learning algorithms with Riemannian metric (Antonakopoulos et al.,, 2019), mirror map based methods for relative Lipschitz objectives (Zhou et al.,, 2020).

Despite the rich literature on geometric methods for machine learning (e.g., Absil et al.,, 2009), some important non-Euclidean operations are relatively poorly understood, including the Greene–Wu (GW) convolution (Greene and Wu,, 1973, 1976, 1979; Parkkonen and Paulin,, 2012; Azagra and Ferrera,, 2006; Azagra,, 2013). To this end, we derive new properties of the GW convolution and apply it to machine learning problems.

Enabled by our study of the GW convolution, we design a new gradient estimation method over Riemannian manifolds. Perhaps the history of gradient estimation can date back to Sir Isaac Newton and the fundamental theory of calculus. Since then, many gradient estimation methods have been invented (Lyness and Moler,, 1967; Hildebrand,, 1987). In its more recent form, gradient estimation methods are often combined with learning and optimization. Flaxman et al., (2005) used the fundamental theorem of geometric calculus and solved online convex optimization problems with bandit feedback. Nesterov and Spokoiny, (2017); Li et al., (2020) introduced a stochastic gradient estimation method using Gaussian sampling, in Euclidean space or manifolds embedded in Euclidean spaces. We improve the previous results in two ways. 1. Our gradient estimation method generalizes this previous work by removing the ambient Euclidean space. 2 We tighten the previous error bound. Over an $n$-dimensional Riemannian manifold, we show that the error of gradient estimation is bounded by $\frac{L_{1}\left(n+3\right)^{3/2}\mu}{2}$ in contrast to $\frac{L_{1}n^{3/2}\mu}{2}$(Li et al.,, 2020), where $n$ is the dimension of the manifold, $L_{1}$ is the smoothness parameter of the objective function and $\mu$ is an algorithm parameter controlling finite-difference step size.

The application of our method to convex bandit optimization is related to online convex learning (e.g., Shalev-Shwartz,, 2011). The problem of online convex optimization with bandit feedback was introduced and studied by Flaxman et al., (2005). Since then, a sequence of works has focused on bandit convex learning in Euclidean spaces. For example, Hazan and Kale, (2012); Chen et al., (2019); Garber and Kretzu, (2020) have studied the gradient-free counterpart for the Frank-Wolfe algorithm, and Hazan and Levy, (2014) studied this problem with self-concordant barrier. An extension to this scheme is combining the methodology with a partitioning of the space Kleinberg, (2004). By doing so, regret rate of $\mathcal{O}\left(\sqrt{T}\right)$ can be achieved in Euclidean spaces (Bubeck et al.,, 2015; Bubeck and Eldan,, 2016). This rate is optimal in terms of $T$ for stochastic environement, as shown by Shamir, (2013). While there has been extensive study of online convex optimization problems, they are all restricted to Euclidean spaces. In this paper, we generalize previous results from Euclidean space to Hadamard manifolds, using our new gradient estimation method.

A Riemannian manifold $(\mathcal{M},g)$ is a smooth manifold equipped with a metric tensor $g$ such that at any point $p\in\mathcal{M}$, $g_{p}$ defines a positive definite inner product in the tangent space $T_{p}\mathcal{M}$. For a point $p\in\mathcal{M}$, we use $\left<,\right>_{p}$ to denote the inner product in $T_{p}\mathcal{M}$ induced by $g$. Also, we use $\|\cdot\|_{p}$ to denote the norm associated with $\left<,\right>_{p}$. Intuitively, a Riemannian manifold is a space that can be locally identified as an Euclidean space. With such structures, one can locally carry out calculus and linear algebra operations.

A vector field $X$ assigns each point $p\in\mathcal{M}$ a unique vector in $T_{p}\mathcal{M}$. Let $\mathfrak{X}(\mathcal{M})$ be the space of all smooth vector fields. An affine connection is a mapping $\nabla:\mathfrak{X}(\mathcal{M})\times\mathfrak{X}(\mathcal{M})\rightarrow\mathfrak{X}(\mathcal{M})$ so that (i) $\nabla_{f_{1}X_{1}+f_{2}X_{2}}Y=f\nabla_{X_{1}}Y+f_{2}\nabla_{X_{2}}Y$ for $f_{1},f_{2}\in C^{\infty}(\mathcal{M})$, (ii) $\nabla_{X}(a_{1}Y_{1}+a_{2}Y_{2})=a_{1}\nabla_{X}Y_{1}+a_{2}\nabla_{X}Y_{2}$ for $a_{1},a_{2}\in\mathbb{R}$, and (iii) $\nabla_{X}(fY)=f\nabla_{X}Y+X(f)Y$ for all $f\in C^{\infty}(\mathcal{M})$. The Levi-Civita connection is the unique affine connection that is torsion free and compatible with the Riemannian metric $g$. A geodesic curve $\gamma:[0,1]\rightarrow\mathcal{M}$ is a curve so that $\nabla_{\dot{\gamma}(t)}\dot{\gamma}(t)=0$ for all $t\in[0,1]$, where $\nabla$ here denotes the Levi-Civita connection. One can think of geodesic curves as generalizations of straight line segments in Euclidean space. At any point $p\in\mathcal{M}$, the exponential map ${\mathrm{Exp}}_{p}$ is a local diffeomorphism that maps $v\in T_{p}\mathcal{M}$ to ${\mathrm{Exp}}_{p}(v)\in\mathcal{M}$ such that there exists a geodesic curve $\gamma:[0,1]\rightarrow\mathcal{M}$ with $\gamma(0)=p$, $\dot{\gamma}\big{|}_{0}=v$ and $\gamma(1)={\mathrm{Exp}}_{p}(v)$. Since the exponential map is (locally) diffeomorphic, the inverse exponential map is also properly defined (locally). We use ${\mathrm{Exp}}_{p}^{-1}$ to denote the inverse exponential map of ${\mathrm{Exp}}_{p}$.

We say a vector field $X$ is parallel along a geodesic $\gamma:[0,1]\rightarrow\mathcal{M}$ if $\nabla_{\dot{\gamma}(t)}X=0$ for all $t\in[0,1]$. For $t_{0},t_{1}\in[0,1]$, we call the map $\mathcal{P}_{t_{0},t_{1}}^{\gamma}:T_{\gamma(t_{0})}\mathcal{M}\rightarrow T_{\gamma(t_{1})}\mathcal{M}$ a parallel transport, if it holds that for any vector field $X$ such that $X$ is parallel along $\gamma$, $X(\gamma(t_{0}))$ is mapped to $X(\gamma(t_{1}))$. Parallel transport induced by the Levi-Civita connection preserves the Riemannian metric, that is, for $p\in\mathcal{M}$, $u,v\in T_{p}\mathcal{M}$, and geodesic $\gamma:[0,1]\rightarrow\mathcal{M}$, it holds that $\left<u,v\right>_{\gamma(0)}=\left<\mathcal{P}_{0,t}^{\gamma}(u),\mathcal{P}_{0,t}^{\gamma}(v)\right>_{\gamma(t)}$ for any $t\in[0,1]$.

The Riemann curvature tensor $\mathcal{R}:\mathfrak{X}(\mathcal{M})\times\mathfrak{X}(\mathcal{M})\times\mathfrak{X}(\mathcal{M})\to\mathfrak{X}(\mathcal{M})$ is defined as $\mathcal{R}(X,Y)Z=\nabla_{X}\nabla_{Y}Z-\nabla_{Y}\nabla_{X}Z-\nabla_{[X,Y]}Z$, where $[,]$ is the Lie bracket for vector fields. The sectional curvature $\mathcal{K}:\mathfrak{X}(\mathcal{M})\times\mathfrak{X}(\mathcal{M})\to\mathbb{R}$ is defined as $\mathcal{K}(X,Y)=\frac{g(\mathcal{R}(X,Y)X,Y)}{g(X,X)g(Y,Y)-g(X,Y)^{2}}$, which is the high dimensional generalization of Gaussian curvature. Intuitively, for a point $p$, $\mathcal{K}\left(X(p),Y(p)\right)$ is the the Gaussian curvature of the sub-manifold spanned by $X(p),Y(p)$ at $p$.

For a continuously connected Riemannian manifold $(\mathcal{M},g)$, a distance metric can be defined. The distance between $p,q\in\mathcal{M}$ is the infimum over the lengths of piecewise smooth curves in $\mathcal{M}$ connecting $p$ and $q$, where the length of a curve is defined with respect to the metric tensor $g$. A Riemannian manifold is complete if it is complete as a metric space. By the celebrated Hopf–Rinow theorem, if a Riemannian manifold is complete, the exponential map ${\mathrm{Exp}}_{p}$ is defined over the entire tangent space $T_{p}\mathcal{M}$ for all $p\in\mathcal{M}$. The cut locus of a point $p\in\mathcal{M}$ is the set of points $q\in\mathcal{M}$ such that there exists more than two distinct shortest path from $p$ to $q$.

We refer the readers to books (e.g., Petersen,, 2006; Lee,, 2006) for more background on Riemannian geometry.

For better readability, we list here some notations and conventions that will be used throughout the rest of this paper.

• •

  For any $x\in\mathcal{M}$, let $U_{p}$ denote the open set near $p$ that is a diffeomorphic to a subset of $\mathbb{R}^{n}$ via the local normal coordinate chart $\phi$. Define the distance $d_{p}(q_{1},q_{2})$ ($q_{1},q_{2}\in U_{p}$) such that

  $\displaystyle d_{p}(q_{1},q_{2})=d_{\text{Euc}}(\phi(q_{1}),\phi(q_{2})).$

  where $d_{\text{Euc}}$ is the Euclidean distance in $\mathbb{R}^{n}$.

• •

  As mentioned in the preliminaries, for any $p\in\mathcal{M}$, we use $\left<\cdot,\cdot\right>_{p}$ and $\|\cdot\|_{p}$ to denote the inner produce and norm induced by the Riemannian metric $g$ in the tangent space $T_{p}\mathcal{M}$. We omit the subscript when it is clear from context.

• •

  For any $p\in\mathcal{M}$ and differentiable function $f$ over $\mathcal{M}$, We use $\mathrm{grad}f\big{|}_{p}$ to denote the gradient of $f$ at $p$.

• •

  For any $p\in\mathcal{M}$ and $\alpha>0$, we use $\mathbb{S}_{p}(\alpha)$ to denote the origin-centered sphere in $T_{p}\mathcal{M}$ with radius $\alpha$. For simplicity, we write $\mathbb{S}_{p}=\mathbb{S}_{p}(1)$.

• •

  We will use another set of notations for parallel transport. For two points $p,q\in\mathcal{M}$ and a smooth curve $\gamma$ connecting $p$ and $q$, we use $\mathcal{P}_{p\rightarrow q}^{\gamma}$ to denote the parallel transport from $T_{p}\mathcal{M}$ to $T_{q}\mathcal{M}$ along the curve $\gamma$. Let $\Omega_{\min}(p,q)$ denote the set of minimizing geodesics connecting $p$ and $q$. Define $\mathcal{P}_{p\rightarrow q}:T_{p}\mathcal{M}\rightarrow T_{q}\mathcal{M}$ be defined such that $\mathcal{P}_{p\rightarrow q}(v)=\mathbb{E}_{\gamma\sim\Omega_{\min}(p,q)}\left[\mathcal{P}_{p\rightarrow q}^{\gamma}(v)\right]$ for any $v\in T_{p}\mathcal{M}$, where the expectation is taken with respect to the uniform probability measure over $\Omega_{\min}(p,q)$. Since for any point $p$, its cut locus is of measure zero, the operation $\mathcal{P}_{p\rightarrow q}$ is deterministically defined for almost every $q$.

• •

  For any $p\in\mathcal{M}$, $v\in T_{p}\mathcal{M}$ and $q\in\mathcal{M}$, define $v_{q}=\mathcal{P}_{p\rightarrow q}(v)$.

• •

  As a convention, if $U\subseteq\mathcal{M}$ is diffeomorphic to $V\subseteq\mathbb{R}^{n}$, we simply say $U$ is diffeomorphic. Similarly, a map is said to be diffeomorphic when the domain of the map is diffeomorphic to an open subset of the Euclidean space. For simplicity, we omit all musical isomorphisms when there is no confusion.

In their seminal works, Greene and Wu showed that the approximation is convexity-preserving when the width of the kernel approaches 0 (Theorem 2 by Greene and Wu, (1973)). We show that the GW convolution is convexity-preserving even if the width of the kernel is strictly positive. Also, second order properties of the GW approximation is proved.

Our decomposition of the Greene-Wu convolution also allows other properties of the GW convolution easily derived. Perhaps one of the most important property of a function is its Hessian (matrix), which we discuss now. The definition of Hessian is in Definition 3 (e.g., Schoen and Yau, (1994); Petersen, (2006)).

With the Levi-Civita connection, which is torsion-free, one can verify that

For any $p\in\mathcal{M}$, with the normal coordinate specified by the exponential map ${\mathrm{Exp}}_{p}$, the Christoffel symbol vanishes at $p$. This means $H(f)(\partial_{i},\partial_{j})\Big{|}_{p}=\partial_{i}\partial_{j}f\big{|}_{p}$ in local normal coordinate. Similar to the Euclidean case, the eigenvalues of the Hessian matrix describes the curvature of the function. Next, we will show how the curvature of the function is affected after applying the GW convolution.

In the study of the second order properties of the GW approximation, we will restrict our attention to kernels whose radial density function is uniform. More specifically, we will use $\alpha=1$ and $\Theta_{\mu,\alpha}(t)=\frac{1}{2\mu}\mathbb{I}_{\left[t\in\left[-\mu,\mu\right]\right]}$. Since one can construct other kernels by combining kernels with uniform radial density functions, investigating kernels with uniform radial density is sufficient for our purpose. With this in mind, we look at

The following theorem tells us how the geometry of the function and the geometry of the space are related after the GW convolution.

We will use the double exponential map (Gavrilov,, 2007) notation in the proof. The double exponential map (also written ${\mathrm{Exp}}_{p}$) is defined as ${\mathrm{Exp}}_{p}:T_{p}\mathcal{M}\times T_{p}\mathcal{M}\rightarrow\mathcal{M}$ such that, when $v\in T_{p}\mathcal{M}$ is small enough (${\mathrm{Exp}}_{p}(v)\in U_{p}$),

With this notation, we are ready to prove Theorem 3.