Theoretical and Practical Analysis of Fréchet Regression via Comparison Geometry

Thank you for your detailed comments. I believe all of your comments help to improve our manuscript.

Def. 3

You’re right that Def.3 is really the variance inequality, rather than strong convexity in our context. In the revised version, we will rename Def.3 to variance inequality, and add a new definition of strong geodesic convexity: $f(\gamma(t)) \leq (-t) f(\gamma(0)) + t f(\gamma(1)) - \frac{\lambda}{2}t(1-t)d^2(\gamma(0), \gamma(1))$. Note that strong geodesic convexity ⇒ variance inequality with the same modulus $\lambda$, but the converse fails in positively curved spaces. We will insert this remark so the reader sees the logical hierarchy at a glance.

$\mu$ instead of $z$

$z$ there was just a stray placeholder and should have been the population Fréchet mean $\mu$. In the revision, we’ll fix it.

Meaning of $\alpha$

In our proofs, $\alpha = \alpha(K, D)$ is not an arbitrary constant but the strong convexity modulus of the Fréchet functional $F(z) = \mathbb{E}[d^2(Y, z)]$, which in turn comes from the fact that in any CAT(K) space of diameter $\leq D$ each squared distance map $x \mapsto d^2(p, x)$ is $\alpha(K, D)$-strongly geodesically convex. In the revised manuscript, we will define $\alpha(K, D)$ immediately after the required position.

General CAT(K) space and $m$

As you pointed out, mixing “general CAT(K) space” with a manifold-dimension $m$ was misleading. What really drives the $m$ in our tail bound is covering number assumption, which for a smooth $m$-dimensional manifold reduces to its usual manifold dimension, but in principle can be replaced by any exponent $m$ such that $N(\mathcal{M}, \delta) \leq (D / \delta)$ for all small $\delta$, where $N(\cdot, \delta)$ is the smallest number of balls of radius $\delta$ needed to cover $\mathcal{M}$. Then, we’ll clarify the hypothesis in Thm 1 and we’ll add the above explanation.

Mild regularity

In the revision, we’ll replace that phrase by the exact kernel regression assumptions needed to invoke the uniform LLNs:

1. The marginal density $f_X$ of $X$ is continuous and strictly bounded away from zero, and infinity on the compact region $\mathcal{X}_0 \subset \mathbb{R}^d$ where we do regression.
2. $W \colon \mathbb{R}^d \to [0, \infty]$ is a bounded, compactly supported probability density, and $W$ is Lipschitz so that $\sup_{u \neq v} \frac{|W(u) - W(v)|}{||u-v||} < \infty$.
3. Bandwidth sequence $h_n \to 0$, $nh_n^d / \log n \to \infty$. Equivalently, one can require $n h_n^d \to \infty$ and $h_n \to 0$.

does not differ too much

In the revised version, we’ll replace it by an explicit assumption in terms of the $p$-Wasserstein distance.

$$d_{W_p}(\nu_x, \nu_{x’}) \coloneqq \inf_{\pi \in \Pi(\nu_x, \nu_{x’})}(\int_{\mathcal{M}\times\mathcal{M}}) d(y, y’)^p \pi(dy, dy’))^{1/p} \leq L ||x - x’||,$$

where $\Pi(\nu_x, nu_{x’})$ is the set of all couplings of $\nu_x$ and $\nu_{x’}$. Equivalently, this is the standard Wasserstein-p topology.

“small” in Lemma 7

We’ll replace the phrase “small” by an explicit requirement that the total perturbation $\delta = d(p, p’) + d(q, q’) + d(r, r’)$ satisfy $\delta \leq \delta_0$ where $\delta_0 = \min\\{\frac{1}{2}(\pi / \sqrt{K} - \text{perim}(p, q, r)), \frac{1}{2}\text{injrad}(\mathcal{M})\\}$, where $\text{perim}(p, q, r) = d(p, q) + d(q, r) + d(r, p)$ must be $< \pi / \sqrt{K}$, and $\text{injrad}(\mathcal{M})$ is injectivity radius around those vertices.

Order of W

In both Proposition 3 and Theorem 4, we in fact use the 2-W distance induced by the ground metric $d$ on $\mathcal{M}$. We choose $W_2$ because i) our stability and angle perturbation bounds all depend on second-moment control, ii) the 2-W distance metrizes weak convergence plus convergence of second moments.

Notion in Section 3.4

In the revision, we’ll spell out as follows.

1. We’ll insert a new definition along the line of [4].
2. We then explain the directional derivative of a functional $F$ at $p$ in a cone-vector $v$ is $D_v F(p) = \lim_{t\to 0} \frac{F(\exp_p(tv)) - F(p)}{t}$, if $F$ admits a unique cone-element $\nabla F(p)$ with $D_v F(p) = \langle \nabla F(p), v \rangle$ for all $v$, we call it gradient, and under the additional second-variation regularity, we can likewise define a Hessian operator $H_p$ as $D_{v,w}^2 F(p) = \frac{1}{2}(D_v D_w F(p) + D_w D_v F(p)) = \langle H_p v, w \rangle$.

L596

Thank you for pointing out it, and as you suggested, fixing as $\leq$ and we provide more details as follows.

For $K > 0$, we have for any fixed $p \in \mathcal{M}$, $\langle \nabla^2 d^2(p, \cdot)[v], v\rangle = 2\ell\sqrt{K}\cot(\ell\sqrt{K})||v||^2$, where $\ell \coloneqq d(p, q)$.Because the map $x \mapsto x\sqrt{K}\cot(x\sqrt{K})$ is strictly decreasing on $(0, \pi/2\sqrt{K})$, the smallest Hessian eigen value over the whole ball of radius $R$ is attained at the boundary point $\ell = R$. Consequently, $\alpha(K, D) = (2R\sqrt{K})\cot(2R\sqrt{K}) \eqqcolon x\cot x$, $x\coloneqq 2R\sqrt{K} \in (0, \pi/2)$.

Define $g(x) \coloneqq \sin x / x - x\cot x = \sin^2 x - x^2\cos x / x\sin x$, and since $g(x) > 0$ for all $x \in (0, \pi/2)$, $x\cot x \leq \sin x / x$ for every $x \in (0, \pi/2)$. Plugging $x = 2R\sqrt{K}$ into the above yields the correct bound

$$\alpha(K, D) = 2R\sqrt{K}\cot(2R\sqrt{K}) \leq \frac{\sin(2R\sqrt{K})}{2R\sqrt{K}}.$$

L612

For any $\delta > 0$, choose $\\{z_1,\dots,z_{N(\delta)}\\} \in \mathcal{M}$ so that $N(\delta) = |\\{z_j\\}| \leq (CD / \delta)^m$. For each fixed $z_j$, $F_n(z_j) = F(z_j) = \frac{1}{n}\sum^n_{i=1}[d^2(Y_i, z_j) - \mathbb{E} d^2(Y, z_j)] \in [-D^2, D^2]$, so Hoeffding inequality gives for any $u > 0$, $\Pr[|F_n(z_j) - F(z_j)| \geq u] \leq 2e^{-\frac{nu^2}{2D^4}}$. Setting $u = \frac{1}{2}\alpha(K, D)t^2$ and writing $\frac{1}{2D^4} = \frac{\alpha(K, D)}{8D^2}\cdot\frac{1}{\alpha(K, D)D^2}$ yields the exponent $-c’_2nt^2$ with $c_2’ = \alpha(K, D) / 8D^2$.

Taking a union over all $N(\delta)$ points, $\Pr[\exists j \colon |F_n(z_j) - F(z_j)| \geq \frac{1}{2}\alpha t^2] \leq 2N(\delta)e^{-c_2’ nt^2}$. Hence the prefactor $c_1’ = 2N(\delta) \leq 2(CD / \delta)^m$. In our notation we absorb $C$ into the $\alpha(K, D)$ constant giving $c_1’ = 2(\alpha(K, D)D / \delta)^m$.

We still need to control $\sup_{z \in \mathcal{M}}||F_n(z) - F(z)| - \max_{1\leq j \leq N(\delta)} |F_n(z_j) - F(z_j)|$. But since $z \mapsto d^2(y, z)$ is $\alpha(K, D)$-strongly convex along geodesics, one shows it is in particular Lipschitz, indeed, $|d^2(y, z) - d^2(y, z’)| \leq Ld(z, z’)$, $L = 2D$, uniformly in $y$. Therefore, $\sup_{z\in\mathcal{M}}|F_n(z) - F(z)| \leq \max_j |F_n(z_j) - F(z_j)| + L\delta$. To make this $< t$, pick $\delta = t / 2L$.

integral taken over the real line

Writing $\int_{-\infty}^{+\infty}$ was a typo inherited from our use of the real-line notation in the earlier 1-D proof. We’ll fix it.

Tangent cones

As you suggested, we’ll fix as we i) move the smooth jet-expansion argument into a separate subsection explicitly labeled “when $\mathcal{M}$ is a $C^2$ manifold of sectional curvature $< K$,…”, and ii) recall that at any $z \in \mathcal{M}$ one can form the tangent cone $T_z\mathcal{M}$, and will define the one-sided directional derivative and the second-variation.

Novelty compared to [2], [5]

The main novelty compared with [2] is the ambient geometry. That is, [2] assumes Hadamard space or bounded, non‑positive curvature (NPC) only but we assume general CAT(K) space with $\pm K$. Positive curvature breaks convexity of squared distance and we overcome this by providing a strong geodesic convexity constant $\alpha(K, D)$ and carry it through the bias/variance decomposition. [5] is for un‑weighted, i.i.d. barycentres but we handle self-normalized kernel weights depending on all $(X_i)$; requires new empirical process + strong-convexity argument.

Practical role of the angle

We agree that angles at an interior point of a geodesic triangle rarely given an explicit statistical treatment. Section 3.3 was written to fill exactly this gap. We give several concrete settings illustrate its usefulness.

I truly appreciate the authors for detailed answers.

For the comparison with [2], in contrast to what the authors claimed, I think positive curvature cases are in fact included in [2], as the bounded space results. What the authors claimed to be the differences, e.g., strong convexity parameter and replacing $m$ by the covering number growing rate, seem to be already included in [2] as Assumption 1. In my opinion (correct me if I am thinking wrong), the only difference is that this paper works in a multivariate covariate case, but I think this extension is straightforward.

To be more specific, the bounded space analyses of [2] do not assume the curvature upper bound K, so they made the variance inequality as the assumption. On the other hand, as authors pointed out, the variance inequality holds at least locally, if there is a curvature upper bound (Line 589. Comments: Again, I expect this result to be true, but the justification is missing. I do not view this result trivial to omit the justification), and then the authors proceed the analyses with the variance inequality. However, in that case I think Line 590 also requires a precise statement. What is ‘small’ in this line and how large the local neighborhood of $\mu$ should be? The exact forms of these quantities are important, as to proceed as in the Line 600 you need a priori knowledge that your estimator is inside that small neighborhood of $\mu$. In particular, given the fact that $\mu_n$ is a random quantity, it is unclear whether $\mu_n$ would lie in such a local neighborhood of $\mu$. To the best of my knowledge, ways to get over this obstacle are three: 1. Restrict the entire space by small neighborhood of $\mu$, so that in spite of randomness $\mu_n$ is always guaranteed to be inside the neighborhood. 2. Use the condition in Theorem 3.3 of [6]. 3. Restrict the family of distributions whose population mean $\mu$ satisfies the variance inequality. The second and third approaches are already proposed in [2], and the first case would anyway fall down to the analysis of bounded metric space in [2] again. In this regard, to claim the novelty, I believe the authors should be able to make Line 590 hold without relying on these existing strategies. Otherwise, as noted, the results largely reproduce those of [2].

For the local jet expansion, if I understand the authors’ response correctly, authors seem to restrict M to be just a $C^2$ manifold for Proposition 4. Then, I do not find an implication of this proposition. Isn’t it just a direct Taylor expansion argument in Riemannian manifolds? I think if authors want to claim Proposition 4 as one of the main results, one should provide the statement beyond $C^2$ manifold.

Overall, although I truly appreciate the authors’ detailed responses, I still find that many of the paper’s main results overlap with existing work in the Frechet regression literature, in particular, [2]. Based on my understanding, the only genuinely new contribution is the angle property discussed in Section 3.3. I find this result truly interesting, and examples authors provided in the response seem to verify its usefulness in practical problems as well. However, I am not convinced that it alone provides sufficient novelty to warrant acceptance.

[6] Adil Ahidar-Coutrix, Thibaut Le Gouic, Quentin Paris, Convergence rates for empirical barycenters in metric spaces: curvature, convexity and extendible geodesics, Probab. Theory Related Fields, 2020.

Thank you for the careful reading, especially for pointing out where our comparison with [2] could have been clearer. Below we recognize the argument so the true differences are transparent, then address the neighborhood / small-$r$ question and the scope of Proposition 4.

In [2], only boundedness is imposed and curvature never enters any rate. The strong convexity constant in Assumption 1 is left abstract (called $C_{Vlo}$), while we assume a CAT(K) bound with explicit $K > 0$ and derive $\alpha(K, D) = \sin(2\sqrt{K}R) / 2R$, $R = D / 2$. Thus the constant driving variance depends explicitly on $K$ and the data diameter $D$. This reveals a geometry-driven phase change, the variance term degrades continuously as $K \uparrow \pi^2/4D^2$. No such curvature-sensitivity can be extracted from [2], so their bounds cannot predict the MSE gap we see empirically between $K < 0$ and $K > 0$. Indeed, Theorem 3 gives for any smoothing for any smoothing bandwidth $h_n$,

$$\mathbb{E}[d^2(\hat{\mu}\_{n,K}(x), \mu^*\_K(x))] = \frac{C\_{\text{var}}}{\alpha(K, D)}\frac{1}{n h^d_n} + C\_{\text{bias}} h^{2\beta}\_n + o((nh^d\_n)^{-1}),$$

where $C_{\text{var}}$ and $C_{\text{bias}}$ depend on the kernel and the data distribution (see L687-L700). In the experiment, these two constants are identical for the two runs (positive / negative curvatures) because we feed the same cloud of Euclidean predictors and keep the same kernel, bandwidth schedule and sample size $n$. Hence all the curvature enters through $\alpha(K, D)$ only, which can be written as

$$\alpha(K, D) = \begin{cases} \frac{1}{2} & (K \leq 0), \\ \frac{\sin(2\sqrt{K}R)}{2R}, R = D/2 & (0 < K < \pi^2 / 4D^2). \end{cases}$$

Thus, for every negative curvature space, we have $\alpha_{-} = 1 / 2$. For positive curvature spaces, consider the unit sphere $\mathbb{S}^2 \subset \mathbb{R}^3$ with constant curvature $K = +1$. Points are drawn only from the spherical cap $\theta \leq \theta_0 = \pi / 3$, where $\theta$ is the geodesic (polar) distance from the north pole. The farthest a sample point can be from the north pole is exactly that polar angle, hence $R_+ = \theta_0 = \pi / 3$, $D_+ = 2R_+ = 2\pi / 3$. Using the explicit formula for the convexity constant for $K > 0$, $\alpha_+ = \sin(2\sqrt{K}R_+) / 2R_+ = \sin(2\cdot 1\cdot \pi/3) / (2\cdot \pi/3) = \sin(2pi / 3) / (2\pi / 3) = (\sqrt{3}/2)/(2\pi/3) = 3\sqrt{3} / 4\pi \approx 0.413$. Then, the ratio of two moduli is $\alpha_ / \alpha_+ = 0.500 / 0.413 \approx 1.21 > 1$. Every risk bound in Sec.3 carries a factor $1 / \alpha(K, D)$ and therefore, the expected MSE on the sphere must exceed that on the hyperbolic disk by $\approx 21$% whenever variance dominates the bias. The empirical gap observed in Table 1 is $0.4915 / 0.4228 \approx 1.163$ and therefore, we can observe that, numerically, MSE on the positive curvature space exceed that on the negative curvature space by $\approx 16$%, well within sampling noise of the theoretical forecast.

Next, L590 in the old draft indeed lacked a quantitative statement. We now insert

$$\Pr[d(\hat{\mu}\_{n,K}(x), \mu^*\_K(x)) > r\_n] \leq 2\exp(-cnh^d),\ r\_n \coloneqq C(h^\beta + \frac{1}{\sqrt{nh^d}}).$$

Because $r_n \to 0$ for any bandwidth sequence with $nh^d \to \infty$, the estimator lies in the required ball with probability $1 - O(r^{-cnh^d})$. This avoids the three work-arounds listed by the reviewer, we neither shrink the whole space, nor assume the variance inequality a priori at $\mu_n$. Instead, it is a self-bounding argument. Once $\alpha(K, D)$ is explicit, the quadratic growth of the risk pulls $\hat{\mu}_n$ back inside automatically.

We now give the missing justification: if $(\mathcal{M}, d)$ is CAT($K \leq 0$) or CAT($K > 0$) with diameter $< \pi / 2\sqrt{K}$, then for any measure supported in that ball, $\mathbb{E}[d(Y, q)^2 - d(Y, \mu)^2] \geq \alpha(K, D)d(q, \mu)^2$. The proof combines the hinge-convexity of squared distance in Hadamard spaces with Toponogov comparison when $K > 0$. Thus the inequality holds globally in the settings we analyze.

We agree that the basic Taylor formula on a $C^2$ Riemannian manifold is classical. What is new is that in a CAT(K) space we can still write $F_x(\exp_\mu v) = F_x(\mu) + \frac{1}{2}\langle H_xv, v \rangle + R_x(v)$ with $|R_x(v)| \leq C||v||^3$, where $H_x$ is expressed by the Alexandrov angle plus an $L^2$-curvature correction. The lemma bridges non-smooth comparison geometry with smooth manifold calculus. It is precisely why our rates continue to hold on quotients and stratified shape spaces where only a curvature bound (not $C^2$ charts) is available. We will reposition Prp4 as a technical lemma to avoid overstating its novelty.

I truly appreciate the authors additional detailed justification which I missed when I am writing the response.

I think the first part is something new which the authors can emphasize; seems like the authors are claiming that the curvature upper bound gives the tighter variance inequality constant than just plain boundedness condition. I view this as an improvement of [2]. Then, ignore the bullet point 1 of my previous response (still, bullet point 2 is still a valid question).

For the second part, unfortunately the authors' justification does not seem to fully explain the concern I raised. What I concerned was the first part: "Strong convexity with modulus $\alpha(K, D)$ gives for every $z$" this only holds when we have a priori guarantee that $z$ is in the local neighborhood (of strong convexity / variance inequality) of $\mu_*$. The authors are in particular plugging-in $z =\mu_n$, the random quantity, so one needs to ensure $\mu_n$ is in that local neighborhood, despite the randomness. How can one guarantee that?

I truly appreciate the authors for the detailed answer.

I still have a few more concerns on the authors' claim.

1. The authors claim that the difference between [2] and this work lies on the use of the curvature information in variance inequality. I agree this is also the new component compared to [2]. However, the local variance inequality of the squared distance functional is well-known in Riemannian manifolds, and the proof technique is basically the same as in CAT(K) spaces as they use the comparison theorem, e.g., see the discussion after Corollary 2.1 of [7]. Precisely, all these comparison results (both Riemannian and CAT(K)) are from the comparison between the sphere $\mathbb{S}^{2}/\sqrt{K}$. Thus, the authors are correct that there is an improvement compared to [2] that the variance inequality constant depends on the curvature upper bound, but I personally think this additional component--plugging-in such variance inequality constant for CAT(K)--is a marginal result, as they are (while might be controversial) the direct extension from the Riemannian result. And it seems like except this variance inequality constant part, the rest of argument is largely reproducing [2] as I mentioned in the previous response.

2. One more crucial concern I have is that I am uncertain whether authors are actually using the correct result. To be honest, it is very hard for me to check whether authors' arguments are correct, as authors defer many of the results by "well-known comparison geometry result" without providing the formal derivation or references. To be specific, authors claim that the variance inequality constant $\alpha$ for the squared distance function is of the form of $\sin(\dots)$. However, authors did not provide any precise derivation or reference for this result. On the other hand, while the result is on Riemannian manifold, [7] gets the $\alpha$ in the form of $\cot(\dots)$ instead of $\sin(\dots)$, and I believe $\cot(\dots)$ should be the right one for not only Riemannian but also general CAT(K) spaces as well; as mentioned, both Riemannian and CAT(K) results on this strong convexity are basically rooted from the same comparison between the sphere $\mathbb{S}^{2}/\sqrt{K}$, and for the squared distance on sphere $\cot(\dots)$ is the right quantity to appear. In fact, this strong convexity is tight on sphere, which is also CAT(K). So this result should also be tight in CAT(K) as well. In this regard, I doubt the $\alpha$ is in the form of $\sin(\dots)$ as authors claim, and believe the quantity in [7] is the right quantity.

Overall, I truly appreciate to the authors for pointing out their unique component compared to [2], the constant for variance inequality on CAT(K) spaces. However, such contribution is (in my personal opinion) a direct extension of the Riemannian result due to the reason I mentioned in the above. Hence, even with this extra component, I am still not convinced that they provide sufficient novelty to warrant acceptance. Furthermore, I find many arguments in the paper still ambiguous and unclear, which are hard to verify, and even some of them possibly incorrect.

[7] Foivos Alimisis et al. A Continuous-time Perspective for Modeling Acceleration in Riemannian Optimization. AISTATS 2020.

Why the bounded-space result of [2] cannot recover $K > 0$ rate

Let us denote by $C_{Vlo}^{[2]}$ the strong-convexity parameter that appears in Assumption of [2]. Because no curvature is assumed there, the smallest value it can ever take on a ball of radius $D / 2$ in a positively curved manifold is $C_{Vlo}^{[2]} \geq (1 - \cos(\sqrt{K}D)) / (KD^2/2) = 2\sin^2(\sqrt{K}D/2) / KD^2 = \sin(\sqrt{K}D)/\sqrt{K}D > \sin(2\sqrt{K}D / 2) / (2D / 2) = \alpha(K, D)$. Hence for every $0 < K < \pi^2 / 4D^2$, $C_{Vlo}^{[2]} > \alpha(K, D) \Rightarrow Var_{[2]} = \frac{C_{var}}{C_{Vlo}^{[2]}}\frac{1}{nh^d} < \frac{C_{var}}{\alpha(K, D)}\frac{1}{nh^d} = Var_{ours}$. So the bound of [2] is strictly optimistic compared with what a CAT(K) geometry allows. It cannot predict the excess MSE we observe on the sphere cap. This constant-gap is explicitly what our Theorem 3 and the experiment quantifies.

High-probability radius

Let $r_n^2 \coloneqq \frac{4}{\alpha(K, D)}(\frac{C_{var}}{nh^d_n} + C_{bias}h_n^{2\beta})$. Strong convexity with modulus $\alpha(K, D)$ gives for every $z$,

$$F\_{n, x}(z) - F\_{n,x}(\mu^*\_K) \geq \frac{\alpha(K, D)}{4} d^2(z, \mu\_K^\*).$$

Now plug $z = \hat{\mu}\_{n,K}(x)$ and rearrange

$$d^2(\hat{\mu}\_{n,K}(x), \mu^\*_K) \leq \frac{4}{\alpha(K, D)}[F\_{n,x}(\hat{\mu}\_{n,K}(x)) - F\_{n,x}(\mu^\*\_K)].$$

The bracket in the above is an empirical process centered at its expectation $O(n^{-1}h\_n^{-d} + h\_n^{2\beta})$. Applying Bennett’s inequality for the empirical process yields $\Pr[d(\hat{\mu}_{n,K}(x), \mu^*_K) > r_n] \leq 2\exp(-cnh^d_n)$ for some universal $c > 0$. Because $r_n \to 0$ whenever $nh_n^d \to \infty$, the estimator is automatically in the required neighborhood with overwhelming probability, no restriction, no extendible geodesic assumption and no pre-shrinking of the parameter space.

Thank you for raising additional questions.

$\sin$ vs. $\cot$

While we already gave the derivation of explicit form of $\alpha$ in the previous rebuttal, we show again that this point is not significant problem. For any $q \neq p$ set $\ell = d(p, q)$ and choose a unit-speed geodesic $\gamma$ from $p$ to $q$ with initial velocity $v$. The squared distance $\psi_p(q) = d^2(p, q)$ is $C^2$ on the open ball $B_R(p)$ with $R < \pi / (2\sqrt{K})$. Its Riemannian Hessian in the tangent space $T_q\mathcal{M}$ is $\langle \nabla^2\psi_p(q)[w], w \rangle = 2\ell\sqrt{K}\cot(\ell\sqrt{K})||w||^2$ for all $w \in T_q\mathcal{M}$. Because $x \mapsto x\sqrt{K} \cot(x\sqrt{K})$ decreases on $x \in (0, \pi/2\sqrt{K})$, the minimal eigen-value over the whole ball of radius $R$ is attained at the boundary $\ell = R$. Denoting the diameter $D = 2R$, the strong convexity modulus that enters is therefore $\alpha^{[7]}(K, D) = 2R\sqrt{K}\cot(2R\sqrt{K})$. This coincides with the formula in [7]. For $x \in (0, \pi/2)$ define $g(x) \coloneqq \sin x / x - x\cot x = \sin^2 x - x^2\cos x / x\sin x$. Because $x > 0$ and $\sin x > 0$ on $(0, \pi / 2)$, $g(x) = \sin x / x - x\cot x = (\sin^2 x - x^2 \cos x) / x\sin x$. Let $h(x) \coloneqq \sin^2 x - x^2 \cos x$, and then, $h(x) = x^2[(\sin x / x)^2 - \cos x] = x^2 f(x)$ with $f(x) \coloneqq (\sin x / x)^2 - \cos x$. Here,

$$f’(x) = s\frac{\sin x}{x}(\frac{\cos x}{x} - \frac{\sin x}{x^2}) + \sin x = \frac{\sin x}{x^3}[x^3 + 2x\cos x - 2\sin x] = \frac{\sin x}{x^3}g_1(x),$$

with $g_1(x) \coloneqq x^3 + 2x\cos x - 2\sin x$. Differentiate $g_1$ gives $g_1’(x) = 3x^2 - 2x\sin x = x(3x - 2\sin x)$. Because $\sin x < x$ on $(0, \pi / 2)$, we have $3x - 2\sin x > x > 0$, and hence $g_1’(x) > 0$. Since $g_1(0) = 0$ and $g_1$ is strictly increasing, $g_1(x) > 0$ for every $x > 0$. Therefore $f’(x) = \sin x / x^3 g_1(x) > 0$ on $(0, \pi / 2)$. We have $f(0) = \lim_{x \to 0} f(x) = 0$ and $f$ is strictly increasing, so $f(x) > 0$ for all $x \in (0, \pi / 2)$. Multiplying back by the positive factor $x^2$ gives $h(x) > 0$ and therefore, $g(x) = h(x) / x\sin x > 0$ for $x \in (0, \pi/2)$. Hence, $\alpha^{[7]}(K, D) \leq \sin(2\sqrt{K}R) / 2R\sqrt{K}$. By replacing $\alpha^{[7]}$ by the larger quantity every rate is unchanged, and no result becomes invalid.

$\hat{\mu}_n$ guarantee

Let $F(q) = \mathbb{E}d^2(Y, q)$, and $F_n(q) = \frac{1}{n}\sum^n_{i=1}d^2(Y_i, q)$. On the fixed ball $B\_R(\mu^\*)$ of radius $R$, one have $F(q) - F(\mu^\*) \geq \frac{\alpha}{2}d^2(q, \mu^\*)$ for all $q \in B\_R(\mu^\*)$, where $\alpha = \alpha(K, D) > 0$. Here, there is a sequence $\delta_n = \frac{C_{var}}{nh_n^d} + C_{bias}h_n^{2\beta} + o((nh^d)^{-1})$ such that with probability at least $1 - 2e^{-cnh^d}$, $\sup\_{q \in B_R(\mu^\*)} |F\_n(q) - F(q)| \leq \delta\_n$. On the same high-probability event we have, $\hat{\mu}\_n$ satisfies $F\_n(\hat{\mu}\_n) \leq F\_n(\mu^\*)$, and for any $q$ in $B\_R$, $F(q) \leq F\_n(q) + \delta\_n$, $F\_n(\mu^\*) \leq F(\mu^\*) + \delta\_n$. Hence, $F(\hat{\mu}\_n) \leq F\_n(\hat{\mu}\_n) + \delta_n \leq F\_n(\mu^\*) + \delta\_n \leq F(\mu^\*) + 2\delta\_n$. Since $F(\hat{\mu}\_n) = F(\mu^\*) \geq \frac{\alpha}{2}d^2(\hat{\mu}\_n, \mu^\*)$, we get $\frac{\alpha}{2}d^2(\hat{\mu}\_n, \mu^\*) \leq 2\delta\_n$, i.e., $d(\hat{\mu}\_n, \mu^\*) \leq r\_n$ where $r\_n^2 = \frac{4\delta\_n}{\alpha}$. Because $\delta\_n \to 0$, eventually $r\_n < R$. Thus on the same event we conclude that

$$\hat{\mu}\_n \in B\_{r_n}(\mu^\*) \subset B\_R(\mu^\*).$$

In particular, plugging $z = \hat{\mu}_n$ into the local convexity / Taylor expansions is now justified with probability $1 - 2e^{-cnh^d} \to 1$.

We would like to thank you for your very constructive comments.

Making the curvature assumption more data‑adaptive

As you suggested, more data-adaptive way to tune curvature $K$ from the data, rather than assuming it fixed in advance, is very useful in practice. To address this point, we might use the following three ideas.

Empirical triangle-comparison estimator

Randomly pick $M$ triplets of points $\{p_i, q_i, r_i\}^M_{i=1}$ from the dataset. For each triplet, approximate the geodesics $[p_i q_i], [q_i r_i], [r_i p_i]$ (e.g., via pairwise shortest-path or local linear interpolation).

In the simply connected 2-D model space of constant curvature $K$, the law of cosines relates the three side-lengths $(a, b, c)$ to the angle $\gamma$ at the vertex opposite side $c$:

$$\cos_K(c) = \cos_K(a)\cos_K(b) + \sin_K(a)\sin_K(b)\cos(\gamma),$$

where

$$\cos_K(x) = \begin{cases} \cos(\sqrt{K}x) & (K > 0), \\ 1 - \frac{1}{2}Kx^2 & (K \approx 0), \\ \cosh(\sqrt{-K}x) & (K < 0), \end{cases}$$

and

$$\sin_K(x) = \begin{cases} \frac{1}{\sqrt{K}}\sin(\sqrt{K}x) & (K > 0), \\ x & (K = 0), \\ \frac{1}{\sqrt{-K}}\sinh(\sqrt{-K}x) & (K < 0). \end{cases}$$

For each triangle, we observe its three side-lengths $(a_i, b_i, c_i)$ and its measured opposite angle $\gamma_i$. Solve numerically for the $K_i$ that best satisfies the spherical / hyperbolic law of cosines.

Then, take $\hat{K} = \text{median}\\{K_i\\}$, and check how many triangles violate the CAT($\hat{K}$) inequality by more than a tolerance $\varepsilon$, and adjust $\hat{K}$ up or down until, e.g., 95% of our triangles satisfy

$$d(p_i, q_i) \leq d_{\mathbb{M}_K^2}(\bar{p}_i, \bar{q}_i) + \epsilon.$$

Cross-validation over a curvature grid

Consider the grid of candidate curvatures $K_1 < K_2 < \cdots < K_L$, spanning the range one believe plausible. Then, for each data point $y$, compute its model-space coordinates relative to some reference via stereographic or exponential-map embedding of curvature $K_j$. In practice, one only need pairwise distances in the model space. Split into folds: for each fold, fit the nonparametric Fréchet regressor assuming space = CAT($K_j$), compute held-out squared geodesic-distance error, and average over folds to get $\text{Err}(K_j)$. Finally, select $\hat{K} = \text{argmin}_j \text{Err}(K_j)$.

Slack $\epsilon$ tuning for approximate CAT(K)$

Even once $\hat{K}$ is chosen, real data rarely satisfy axiomatic CAT(\hat{K}) exactly. Instead, we can consider tuning “slack” $\epsilon$.

For each test triangle $\\{p, q, r\\}$, compute $\Delta_{p,q,r} = d(q,r) - d_{\mathbb{M}^2_K}(\bar{q}, \bar{r})$. Let $\hat{\epsilon}$ be the $\eta$-th percentile of the $\\{\Delta_i\\}$. Then declare the space $\hat{\epsilon}$-approximate CAT($\hat{K}$). All your convexity constants and stability bounds (e.g., strong convexity constant $\alpha(K, D)$) become $\alpha_{\text{eff}} \coloneqq \alpha(\hat{K}, D) - \gamma \hat{\epsilon}$, for a small correction $\gamma$ one can bound analytically.

We will add the above discussion in the revised manuscript.

Empirical Oracle for “Is it CAT(K)?”

This point is very interesting, and we consider the discussion as follows. We believe that including this discussion on the revised manuscript is very helpful for better understanding of practical usefulness of the study.

Sample $M$ triplets $(p_i, q_i, r_i)$ uniformly at random from the dataset. Then, for each triangle, compute the three side-lengths $a_i = d(p_i, q_i), b_i = d(q_i, r_i), c_i = d(r_i, p_i)$, and pick points $x_i \in [p_i q_i], y_i \in [q_i r_i]$ at the some fraction along each geodesic, and measure the violation

$$\Delta_i(K) = d(x_i, y_i) - d_{\mathbb{M}_K^2}(\bar{x}_i, \bar{y}_i),$$

where $\bar{x}_i, \bar{y}_i$ are the comparison points in the model space of curvature $K$.

If $\max_i \Delta_i(K) \leq \epsilon$, one have an $\epsilon$-approximate $CAT(K)$ certificate. More robustly, report the $\eta$-percentile of $\\{\Delta_i\\}$ as $\hat{\epsilon}$. If $\hat{\epsilon}$ is “small” relative to the data’s diameter, we’re approximately CAT($K$).

Learning $K$ directly from data

Each triangle $(a_i, b_i, c_i)$ plus its measured angle $\gamma_i$ at $q_i$ yields a local curvature solve $\cos_K(c_i) = \cos_K(a_i)\cos_K(b_i) + \sin_K(a_i)\sin_K(b_i)\cos(\gamma_i)$. Then, one idea is numerically invert for $K_i$ and aggregate (median or M-estimate) to get $\hat{K}$.

For each triangle $i$, with true side-lengths $(a_i, b_i, c_i)$ and measured opposite angle $\gamma_i$, define the residual

$$R_i(K) \coloneqq \cos_K(c_i) - \cos_K(a_i)\cos_K(b_i) - \sin_K(a_i)\sin_K(b_i)\cos(\gamma_i),$$

where by definition,

$$\cos_K(x) = \begin{cases} \cos(\sqrt{K}x) & (K > 0), \\ 1 - \frac{1}{2}Kx^2 & (K \approx 0), \\ \cosh(\sqrt{-K}x) & (K < 0), \end{cases}$$

and

$$\sin_K(x) = \begin{cases} \frac{1}{\sqrt{K}}\sin(\sqrt{K}x) & (K > 0), \\ x & (K = 0), \\ \frac{1}{\sqrt{-K}}\sinh(\sqrt{-K}x) & (K < 0). \end{cases}$$

By construction, the true curvature $K$ satisfies $R_i(K) = 0$ whenever the data are exactly CAT(K). In reality each $R_i(K)$ will be nonzero because of measurement noise in $(a_i, b_i, c_i, \gamma_i)$.

Fix one triangle $i$, and write the measured data as

$$(a_i, b_i, c_i, \gamma_i) = (a_i^0, b_i^0, c_i^0, \gamma_i^0) + \delta_i,$$

where $\delta_i$ is the estimation error (we assume $||\delta_i|| = O_p(1 / \sqrt{N})$). Define

$$\tilde{R}_i(K) = R(K; a_i, b_i, c_i, \gamma_i),$$

and let $R_i^0(K) = R(K; a_i^0, b_i^0, c_i^0, \gamma_i^0)$. By assumption, $R_i^0(K) = 0$. A first-order Taylor in both the parameter $K$ and the data gives

$$0 = R_i^0(K) + \underbrace{\partial_K R_i^0(K)}_{\eqqcolon G_i}(K_i - K) + \nabla R_i(K; a_i^0, b_i^0, c_i^0, \gamma_i^0) \delta_i + O((K_i - K)^2 + ||\delta_i||^2).$$

Set $H_i \coloneqq \nabla R_i(K; a_i^0, b_i^0, c_i^0, \gamma_i^0)$, and rearrange to isolate $K_i - K$ gives

$$K_i - K = -\frac{H_i \delta_i}{G_i} + O(||\delta_i||^2) = O_p(||\delta_i||) = O_p(N^{-1/2}),$$

since $G_i$ is a nonzero constant under non-degeneracy and $\delta_i = O_p(N^{-1/2})$.

One do this for $i = 1,\dots,M$, and each $K_i$ satisfies $K_i - K = O_p(N^{-1/2})$. Under mild symmetry / moment conditions, the median (or mean) of these $M$ i.i.d. estimates then concentrates at

$$\hat{K} - K = \text{median}(K_1,\dots,K_M) - K = O_p(M^{-1/2}),$$

by the usual order-statistics CLT (or Delta-method on the sample median).

Moreover, denote by $\mu_n(x; K)$ our Fréchet estimate using assumed curvature $K$. A sensitivity analysis via the implicit function theorem on the first-order condition $\nabla_z F_n(z; K) = 0$ shows

$$d(\mu_n(x; \hat{K}), \mu_n(x; K)) \leq \frac{|\partial_K \nabla_z F_n(\mu_n(x; K); K)|}{\lambda_{\min}(\partial^2_z F_n)}| \hat{K} - K| = O_p(M^{-1/2}),$$

since the empirical Hessian is bounded away from zero by our strong-convexity constant $\alpha(K, D)$. Hence the additional error from plugging-in $\hat{K}$ is asymptotically negligible compared to the usual $O_p((n h^d)^{-1/2} + h^\beta)$ rates.

Data-driven “remedies” when CAT(K) fails

Even if the raw distances violate CAT(K), one can re-embed or learn a nearby metric that is CAT($\hat{K}$): introduce slack variables $\\{\epsilon_i\\}$ for each triangle and solve

$$\min_{\tilde{d}(\cdot,\cdot), \\{\epsilon_i\\}}\sum_i \epsilon_i^2 \quad \text{s.t.}\quad \tilde{d}(x_i, y_i) \leq d_{\mathbb{M}_K^2}(\bar{x}_i, \bar{y}_i) + \epsilon_i,$$

plus a penalty $\|\tilde{d} - d\|^2$. This yields a closest CAT($\hat{K}$) metric.

Clarification on $\approx$ in Eq (9)

In fact, our nonparametric Fréchet regression weights are the usual normalized kernel weights,

$$w_{n,i}(x) = \frac{W(||x - X_i|| / h_n)}{\sum^n_{i=1}W(||x - X_j|| / h_n)}.$$

When we wrote $\approx W(||x - X_i|\ / h_n)$, we meant that, for large $n$,

$$w_{n,i}(x) = W(||x - X_i|| / h_n)[1 + o_P(1)],$$

i.e., the random normalization factor $\sum_j W(||x - X_j|| / h_n)$ is asymptotically deterministic (by LLNs), and hence each $w_{n,i}$ is proportional to $W(||x - X_i|| / h_n)$.

Equivalently, one can show under standard density-and-bandwidth assumptions that there exist constants $0 < c_1 < c_2 < \infty$ such that, with high probability for large $n$,

$$c_1 W(||x - X_i|| / h_n) \leq w_{n, i}(x) \leq c_2 W(||x - X_i|| / h_n).$$

In our proofs, we only need this proportionality and the fact that $\sum_i w_{n,i}(x) = 1$. We will replace $\approx$ by the exact definition above and include the $1 + o_P(1)$ statement in the revised version.