Geodesically convex $M$-estimation in metric spaces

The problem of $M$-estimation, or empirical risk minimization, is pervasive to statistics and machine learning. In many problems, one seeks to minimize a function that takes the form of an expectation, i.e., $\Phi(x)=\mathbb{E}[\phi(Z,x)]$, where $Z$ is a random variable with unknown distribution, $x$ is the target variable, which lives in some target space, and $\phi$ can be seen as a cost function. Classification, regression, location estimation, maximum likelihood estimation, are standard instances of such problems. In practice, the distribution of $Z$ is unknown, so the function $\Phi$ cannot be evaluated. Hence, one rather minimizes a proxy of the form $\hat{\Phi}_{n}(x)=n^{-1}\sum_{i=1}^{n}\phi(Z_{i},x)$, where $Z_{1},\ldots,Z_{n}$ are available i.i.d. copies of $Z$. This method is called $M$-estimation, or empirical risk minimization. When the target space is Euclidean, a lot of results are available for guarantees of a minimizer $\hat{x}_{n}$ of $\hat{\Phi}_{n}$, as an estimator for a minimizer $x^{*}$ of $\Phi$. Asymptotic results (such as consistency and asymptotic normality) are classic and well known, especially under technical smoothness assumptions on the cost function $\phi$ [53], most of which can be dropped when the cost function is convex in the target variable [28, 44].

In this work, we are interested in the framework in which the target space is not Euclidean, and does not even exhibit any linear structure. Of course, the space needs to be equipped with a metric, at the very least in order to measure the accuracy of an estimation procedure. Thus, we consider a target space that is a metric space, which we denote by $(M,d)$.

Statistics and machine learning are more and more confronted with data that lie in non-linear spaces: In spatial statistics (e.g., directional data), computational tomography (e.g., data in quotient spaces such as in shape statistics, collected up to rigid transformations), economics (e.g., optimal transport, where data are measures), etc. Moreover, data and/or target parameters that are encoded as very high dimensional vectors may have a much smaller intrinsic dimension: For instance, if they are lying on small dimensional submanifolds of the ambient Euclidean space. In that case, leveraging the possibly non-linear geometry of the problems at hand can be a powerful tool in order to significantly reduce their dimensionality. This is the central motivating idea behind manifold learning [26, 1] or generative adversarial networks [50]. Even though more and more algorithms are developed to work and, in particular, optimize in non-linear spaces [42, 46, 55, 56, 7, 19], still little is understood from a statistical prospective.

A specific instance of $M$-estimation on metric spaces, which has attracted much attention, is that of barycenters. Given $n$ points $x_{1},\ldots,x_{n}\in M$, a barycenter is any minimizer $x\in M$ of the sum of squared distances $\sum_{i=1}^{n}d(x,x_{i})^{2}$. One can easily check that if $(M,d)$ is a Euclidean or Hilbert space, then the minimizer is unique and it is given by the average of $x_{1},\ldots,x_{n}$. Barycenters extend the notion of average to spaces that lack a linear structure. More generally, given a probability measure $P$ on $M$, one can define a barycenter of $P$ as any minimizer $x\in M$ of $\int_{M}d(x,z)^{2}\mathop{}\!\mathrm{d}P(z)$, provided that integral is finite for at least one (and hence, for all) value of $x\in M$. Barycenters were initially introduced in statistics by [24] in the 1940’s, and later by [33], where they were rather called Fréchet means or Karcher means. They were popularized in the fields of shape statistics [34], optimal transport [2, 20, 38, 18, 37, 36, 5, 6]. and matrix analysis [9, 8, 10]. Asymptotic theory is fairly well understood for empirical barycenters in various setups, particularly laws of large numbers [57, 51] and central limit theorems in Riemannian manifolds (it is natural to impose a smooth structure on $M$ in order to derive central limit theorems) [12, 13, 35, 32, 11, 23, 22]. A few finite sample guarantees are available, even though the non-asymptotic statistical theory for barycenters is still quite limited [51, 25, 49, 3, 39]. Asymptotic theorems are also available for more general $M$-estimators on Riemannian manifolds, e.g., $p$-means, where $\mathcal{Z}=X$ and $\phi(z,x)=d(x,z)^{p}$, for some $p\geq 1$ [49], including geometric medians as a particular case ($p=1$), but only suboptimal rates are known. In particular, the standard $n^{-1/2}$-rate is unknown in general, beyond barycenters. It should be noted that all central limit theorems for barycenters in Riemannian manifolds rely on the smoothness of the cost function $\phi=d^{2}$ and use standard techniques from smooth $M$-estimation [53] by performing Taylor expansions in local charts. Moreover, they assume that the data are almost surely in a ball with small radius, which essentially ensures the convexity of the squared distance function $d^{2}$ in its second variable, even though this synthetic property is not leveraged in this line of work. For instance, asymptotic normality cannot be obtained for geometric medians or other robust alternatives to barycenters, using these techniques.

In this work, we prove strong consistency and asymptotic normality of geodesically convex $M$-estimators under very mild assumptions. We recover the central limit theorems proven for barycenters in Riemannian manifolds with small diameter, but we cover a much broader class of location estimators, including robust alternatives to barycenters. Just as in the Euclidean case, ours results convey that convexity is a powerful property, since it yields strong learning guarantees under very little assumptions.

All our results are asymptotic, but it is worth mentioning that proving learning guarantees in non-linear spaces is a very challenging, ongoing research topic, because it requires non-standard tools from metric and differential geometry. In particular, very few non-asymptotic learning guarantees are available, even for simple estimators such as barycenters, and asymptotic theory is still an active research area in that framework (e.g., understanding non-standard asymptotic rates, a.k.a. sticky and smeary central limit theorems [30, 23]). Moreover, asymptotic guarantees such as asymptotic normality provide benchmarks that are also important for a finite sample theory.

Let $(M,d)$ be a complete and separable metric space that satisfies the following property: For all $x,y\in M$, there exists a continuous function $\gamma:[0,1]\to M$ such that $\gamma(0)=x$, $\gamma(1)=y$ and with the property that $d(\gamma(s),\gamma(t))=|s-t|d(x,y)$, for all $s,t\in[0,1]$. Such a function $\gamma$ is called a unit speed geodesic from $x$ to $y$ and it should be thought of as a (not necessarily unique) shortest path from $x$ to $y$. We denote by $\Gamma_{x,y}$ the collection of all such functions. The space $(M,d)$ is then called a geodesic space. Examples of geodesic spaces include Euclidean spaces, Euclidean spheres, metric graphs, Wasserstein spaces, quotient spaces, etc. [16, 15]. Geodesic spaces allow for a natural extension of the notion of convexity.

In this work, we will further assume that $(M,d)$ is a proper space, i.e., all bounded closed sets are compact. This assumption may seem limiting in practice but, at a high level, it essentially only discards infinite dimensional spaces. Indeed, Hopf-Rinow theorem [15, Chapter 1, Proposition 3.7] asserts that so long as $(M,d)$ is complete and locally compact, then it is proper. For instance, Hopf-Rinow theorem for Riemannian manifolds asserts that any complete (finite dimensional) Riemannian manifold is a proper geodesic metric space [21, Chapter 7, Theorem 2.8].

A Riemannian manifold $(M,g)$ is a finite dimensional smooth manifold $M$ equipped with a Riemannian metric $g$, i.e., a smooth family of scalar products on tangent spaces. We refer the reader to [21] and [40, 41] for a clear introduction to differential geometry and Riemannian manifolds. The distance inherited on $M$ from the Riemannian metric $g$ will be denoted by $d$. In this work, for simplicity, we only consider Riemannian manifolds without boundary, even though our results extend easily to the case with boundary.

The tangent bundle of $M$ is denoted by $TM$, i.e., $\displaystyle TM=\bigcup_{x\in M}T_{x}M$ where, for all $x\in M$, $T_{x}M$ the tangent space to $M$ at $x$. For all $x\in M$, we also let $\textrm{Exp}_{x}:T_{x}M\to M$ and $\textrm{Log}_{x}:M\to T_{x}M$ be the exponential and the logarithmic maps at $x$, respectively. The latter may not be defined on the whole tangent space, but it is always defined at least on a neighborhood of the origin. To provide intuition, at a given point $x\in M$, and for a given vector $u\in T_{x}M$, $\textrm{Exp}_{x}(u)$ is the Riemannian analog of “$x+u$” in the Euclidean space: From point $x$, add a vector $u$, whose direction indicates in which direction to move, and whose norm (given by the Riemannian metric $g$) indicates at which distance, in order to attain the point denoted by $\textrm{Exp}_{x}(u)$. On the opposite, given $x,y\in M$, $\textrm{Log}_{x}(y)$ (when it is well-defined) is the Riemannian analog of “$y-x$”, that is, from $x$, which vector in $T_{x}M$ led to move to $y$.

For all $x\in M$, we denote by $\langle\cdot,\cdot\rangle_{x}$ the scalar product on $T_{x}M$ inherited from $g$ and by $\|\cdot\|_{x}$ the corresponding norm.

Let $x,y\in M$ and $\gamma\in\Gamma_{x,y}$ be a geodesic (in the sense of Section 2.1) from $x$ to $y$. If $x$ and $y$ are close enough, $\gamma$ is unique [41, Proposition 6.11] and in that case, for all $t\in[0,1]$, $\gamma(t)=\textrm{Exp}_{x}(t\dot{\gamma}(0))$, where $\dot{\gamma}(0)\in T_{x}M$ is the derivative of $\gamma$ at $t=0$, given by $\dot{\gamma}(0)=\textrm{Log}_{x}(y)$. We denote the parallel transport map from $x$ to $y$ along $\gamma$ as $\pi_{x,y}:T_{x}M\to T_{y}M$, without specifying its dependence on $\gamma$ (which is non-ambiguous if $y$ is close enough to $x$). The map $\pi_{x,y}$ is a linear isometry, i.e., $\langle u,v\rangle_{x}=\langle\pi_{x,y}(u),\pi_{x,y}(v)\rangle_{y}$, for all $u,v\in T_{x}M$. Moreover, it holds that $\pi_{x,y}(\dot{\gamma}(0))=-\dot{\gamma}(1)$. Intuitively, parallel transport is an important tool that allows to compare vectors from different tangent spaces, along a given path on the manifold.

For further details and properties on Riemannian manifolds used in the mathematical development of this work, we refer the reader to Appendix B.

Let $\mathcal{Z}$ be some abstract space, equipped with a $\sigma$-algebra $\mathcal{F}$ and a probability measure $P$. Let $\phi:\mathcal{Z}\times M\to\mathbb{R}$ satisfy the following:

1. (i)

   For all $x\in M$, the map $\phi(\cdot,x)$ is measurable and integrable with respect to $P$;

2. (ii)

   For $P$-almost all $z\in\mathcal{Z}$, $\phi(z,\cdot)$ is convex.

Finally, let $Z,Z_{1},Z_{2},\ldots$ be i.i.d. random variables in $\mathcal{Z}$ with distribution $P$ and set the functions

for all $x\in M$ and for all positive integers $n$. Finally, we denote by $M^{*}$ the set of minimizers of $\Phi$. Note that by convexity of $\Phi$, the minimizing set $M^{*}$ is convex, i.e., for all $x,y\in M^{*}$ and for all $\gamma\in\Gamma_{x,y}$, $\gamma([0,1])\subseteq M^{*}$.

Important examples include the case where $\mathcal{Z}=M$ and $\phi$ is a function of the metric, which yields location estimation. Specifically, assume that $\mathcal{Z}=M$ and that $\phi(z,x)=\ell(d(z,x))$, for all $z,x\in M$, where $\ell:[0,\infty)\to[0,\infty)$ is a non-decreasing, convex function. Then, a natural framework to ensure convexity of the functions $\phi(z,\cdot)$ is that of spaces with curvature upper bounds, a.k.a. CAT spaces. Here, we only give an intuitive definition on CAT spaces. We refer the reader to Appendix D for a more detailed account on CAT spaces.

Fix some real number $\kappa$. We say that $(M,d)$ is $\textrm{CAT}(\kappa)$ (or that it has global curvature upper bound $\kappa$) if all small enough triangles in $M$ are thinner than what they would be in a space of constant curvature $\kappa$, i.e., a sphere if $\kappa>0$, a Euclidean space if $\kappa=0$ and a hyperbolic space if $\kappa<0$. This setup is very natural to grasp the convexity of the distance function to a point. Fix $x_{0}\in M$. The function $d(\cdot,x_{0})$ is convex if and only if for all $y,z\in M$ and all $\gamma\in\Gamma_{y,z}$, $d(\gamma(t),x_{0})\leq(1-t)d(y,x_{0})+td(z,x_{0})$, which controls the distance from $x_{0}$ to any point in the opposite edge to $x_{0}$ in a triangle with vertices $x_{0},y,z$. In other words, it indicates how thin a triangle with vertices $x_{0},y,z$ must be.

Hence, if $\mathcal{Z}=M$ is $\textrm{CAT}(\kappa)$ and has diameter at most $D_{\kappa}$ (see Appendix D for its definition), [45, Proposition 3.1] guarantees that for all $z\in M$, $d(z,\cdot)$ is convex on $M$ and hence, $\phi(z,\cdot)=\ell(\phi(z,\cdot))$ is also convex as soon as $\ell:[0,\infty)\to[0,\infty)$ is non-decreasing and convex itself. In that setup, important examples of functions $\ell$ include:

1. (i)

   $\ell(u)=u^{2}$: Then, a minimizer of $\Phi$ is a barycenter of $P$ and a minimizer of $\hat{\Phi}_{n}$ is an empirical barycenter of $Z_{1},\ldots,Z_{n}$

2. (ii)

   $\ell(u)=u$: Then, a minimizer of $\Phi$ is a geometric median of $P$

3. (iii)

   More generally, if $\ell(u)=u^{p},p\geq 1$, a minimizer of $\Phi$ is called a $p$-mean of $P$

4. (iv)

   $\ell(u)=u^{2}$ if $0\leq u\leq c$, $\ell(u)=c(2u-c)$ if $u>c$, where $c>0$ is a fixed parameter. This function was introduced by Huber [31] in order to produce low-bias robust estimators of the mean: It provides an interpolation between barycenter and geometric median estimation.

Important examples of CAT spaces include Euclidean spaces, spheres, simply connected Riemannian manifolds with bounded sectional curvature, metric trees, etc. In Appendix D, we provide a more detailed list of examples.

Here, we assume that there exists $L>0$ such that $\phi(z,\cdot)$ is $L$-Lipschitz on $M$, for all $z\in\mathcal{Z}$. For instance, this is satisfied if $M$ has bounded diameter and $\phi=\ell\circ d$, for some locally Lipschitz function $\ell:[0,\infty)$, such as the functions mentioned above for location estimation.

Recall that we denote by $M^{*}$ the set of minimizers of $\Phi$. The following theorem need not require that $\Phi$ has a unique minimizer: It asserts that any minimizer of $\Phi_{n}$ will eventually become arbitrarily close to $M^{*}$ with probability $1$.

A simple adaptation of the proof shows that the same conclusion applies if $\hat{x}_{n}$ is not exactly a minimizer of $\hat{\Phi}_{n}$ but rather satisfies $\hat{\Phi}_{n}(\hat{x}_{n})\leq\min_{x\in M}\hat{\Phi}_{n}(x)+\varepsilon_{n}$, where $\varepsilon_{n}$ is any non-negative error term that goes to zero almost surely, as $n\to\infty$.

The proof of Theorem 1 is based on the following extension of [47, Theorem 10.8]. The proof is a straightforward adaptation of that of [47, Theorem 10.8].

This lemma is the reason why, in this section, we require $\phi(z,\cdot)$ to be Lipschitz, with a constant that does not depend on $z\in\mathcal{Z}$. If $M$ was Euclidean, the Lipschitz assumption of Lemma 1 would not be necessary because on any compact subset, it would be a consequence of the convexity and pointwise convergence of the functions $f_{n},n\geq 1$, see [47, Theorem 10.6]. However, to the best of our knowledge, this may not hold in the more general case that we treat here (and may be subject to a further research question).

As a corollary to Lemma 1, we now state the following results, which is essential in our proof of Theorem 1. The proof is deferred to Appendix C.

Now, we prove that, at least in a Riemannian manifold, the Lipschitz condition on $\phi$ can be dropped for the consistency of $\hat{x}_{n}$. In this section, we assume that $(M,g)$ is a complete Riemannian manifold and we have the following theorem.

Again, this theorem applies if $\hat{x}_{n}$ satisfies $\hat{\Phi}_{n}(\hat{x}_{n})\leq\min_{x\in M}\hat{\Phi}_{n}(x)+\varepsilon_{n}$, where $\varepsilon_{n}$ is any non-negative error term that goes to zero almost surely, as $n\to\infty$.

Once one has Lemma 4 below, which builds upon Lemma 3, the proof of Theorem 2 is very similar to that of Theorem 1, hence, we omit it.

By adapting the proof of [47, Theorem 10.8], this lemma yields the following result.