Choosing the parameter of the Fermat distance: navigating geometry and noise
Authors: Frederic Chazal
Laure Ferraris
Pablo Groisman
Matthieu Jonckheere
Frederic Pascal
Facundo Fabián Sapienza
Venue: Accepted by TMLR ()

Abstract: The Fermat distance has been recently established as a valuable tool for machine learning tasks when a natural distance is not directly available to the practitioner or to improve the results given by Euclidean distances by exploiting the geometrical and statistical properties of the dataset. This distance depends on a parameter $\alpha$ that significantly affects the performance of subsequent tasks. Ideally, the value of $\alpha$ should be large enough to navigate the geometric intricacies inherent to the problem. At the same time, it should remain restrained enough to avoid any deleterious effects stemming from noise during the distance estimation process.
We study both theoretically and through simulations how to select this parameter.

Publishod in Transactions on Machine Learning Research (/)
Choosing the parameter of the Fermat distance: navigating geometry and noise
Frédéric Chazal
frederic. chazal@inria..ff Instifut de Mathématique d' d'Orsoy, Faculté des Sciences d'Orsay, Université Poris-Sackos France
Laure Ferraris
Instifut de Mathématique d' d'Orsay, Faculté des Sciences d' d'Orsay, Université Paris-Saclay, France
Pablo Groisman
pgroisma wbo.ar ar IMAS-CONICET, Dep. de Matemática, Pac. Cs. Exactas Naturales, Universidad de Buenos Aires, Argentina
Matthieu Jonckheere,
LAAS-CNRS, Université de Toulouse, CNRS, Toulouse, France.
Frédéric Pascal
ptaprrcccccoeeeeenneesseeee.e Université Paris-Saclay CNRS, CentraleSupélec, Laboratoire des Signauz et Systèmes, 91190, Gif-sur- Yuette, France
Facundo Sapienza
Jsapienza@berkedeyyccc edu
Department of Statistics, University of California, Berkeley, CA, USA
Reviewed on OpenReview:
Abstract
The Fermat distance has been recently established as valuable tool for machine learning tasks when a natural distance is not directly available to the practitioner or to improve the results given by Euclidean distances by exploiting the geometrical and statistical properties of the dataset. This distance depends on a parameter a that significantly affects the perfor- mance of subsequent tasks. Ideally, the value of a should be large enough navigate the geometric intricacies inherent to the problem. At the same time, it should remain restrained enough to avoid any deleterious effects stemming from noise during the distance estimation process. We study both theoretically and through simulations how to select this parameter.
Keywords- Fermat distance, clustering, geometry, density, metric learning
1 Introduction
The Fermat distance and other density based distances have recently attracted interest machine learning and shown usefulness in various application domains. For example, they have been used in topological data analysis to detect cancer fingerprints (4) in sigual analysis to detect periodicity and anomalies in ECG and the reconstruction
of dynamical systems g. The also have shown interesting potential in semi-supervised learning and in definition of notions data depth 3 Exploiting both the geometric and statistical properties of datasets, the Fermat distance
favor geodesic paths to go through high data density areas by reducing distances between points there and avoid low density areas by increasing distances between points there of the space in which they are defined. The influence of the density in the definition of the Fermat distance depends the performances subsequent tasks, such as clustering, tend to improve as a increases while at the same time the estimation of the Fermat distance tends become dramatically sensitive noise. The overall objective of this paper
parameter whose choice is critical:

---

Publishod in Transactions on Machine Learning Research (/)
is to better understand the role and behavior of this parameter a in the estimation of the Fermat distance and its impact clustering subsequent tasks.
Let Qo = (q...... )n C _ be independent random points with common densily M C CRP ~> Rg0 supported on smooth Riemannian manifold M embedded in R?. We assume that f is density with respect the volume form on M. Typically, d = dim(M) <. D, but it can take any value S d $ D.
We first recall the definition of the somple Fermat distance and the macroscopic Permat distance Definition 1.1 (Sample Fermat distance). For 2 and I, y R. we define,
14
18
1-1
D 8) inf
Σ
18-1 %51" (gh....... is a path from to y. 2
(1.1)
where || denotes the D-direnniooall Euclidean norm, q1 and on the nearest neighbors in Qn of a and y, respectively. Definition 1.2 (Macroscopic Fermat distance). For 2 1 and x, E M.
(=.)))== = inf "El's. J, f(a-1)/d'
(1.2)
where Fz.y is the set of rectifiable paths y [0, 1] + -M such that 7(0) x, 7(1) = y-
These distances have been used in several situations and proved to be useful in a variety of learning tasks
18
16
Under different assumptions on M and f. it has been shown that when >> 1, as n - Do,
(o-1)/d DQ... (I, u) - p(a, d) D (x.
a.s.,
(1.3)
where p(ard) d) is positive constant depending only the intrinsic dimension d of M and the parameter
14
It worth noting that in the works 16 18
different definition of Fermat distance introduced, specifically
expressed
De a y) 1/a
(1.4)
This alternative definition carries implications for practical implementations, each accompanied by its advantages and limitations, which must be considered when using it along with specific subsequent machine learning tasks.
Our study sheds light on some key points about the use the Fermat distance, as given in Definition 1.2 for both clustering and classification tasks.
Contributions. Firstly, we demonstrate the existence of critical value co, dependent the underlying distribu- tion's geometric parameters and its intrinsic dimensionality. For values a > ou, both classification and clustering tasks become feasible for large sample sizes, which implies that the derivation of meaningful distance measurement hinges upon a exceeding this pivotal threshold. Under regularity assumptions, we show that ag scales linearly with the dimension. Contrary to this point, also highlight that using large values of leads to drawbacks due to increased variability in the sample Fermat distance. This effect has a negative impact on the distance estimation for finite samples. We prove that the variance of the sample Fermat distance scales exponentially with in dimension one, and we obtain exponential bounds in terms of a/d in higher dimensions. We conclude that a sensible choice for a crucial and provide guidelines to perform this choice.
To illustrate our findings, we conduct experiments on synthetic datasets and observe that there is a practical critical window of values of a where the performance is optimal. Although the definitions and results presented in this study are relevant to both the supervised context of classification and the unsupervised tasks of clustering, our subsequent analysis in the following sections will framed within the context of clustering analysis.
2

---

Publishod in Transactions on Machine Learning Research (/)
2 Population clusters and a lower bound on a
We start with definition of clusters that extends the one given by the level sets of density.
Definition 2.1 (Clusters). For a measure with density (with respect the volume form) on the Riemannian manifold M C R and a family of sets C == (C) C2 C RR,, we say that C are o a-clusters of f if there exists e >> 0 such that
(=, vz, - for all 1 s m.j # 1, E Cv,y' Cj-
(2.1)
If this holds for some
will say that the clustering problem (C, feasibbele just feasible.
Note that this definition of clusters aligns with clustering methods that find clusters by comparing intra-cluster distances with inter-cluster distances. In practice, this is usually done by finding centers or centroids c Cm (e.g., K- ---medoids X-means Lechniques) such that,
(Z, ea) S (2, -,, for all siis m,jii, E
(2.2)
This last notion is the one that is used to find the empirical centroids (i.e., estimators of ci,..., Cm) and then the clusters. We could adopt this definition and state our results regarding this property, but we prefer use (2.1]
avoid dealing with centroid estimations and their consistency properties. We remark that all the statements and definitions below can rephrased to fit the notion of clusters that involves centroids.
If macroscopic clustering problem is feasible, we define the critical parameler the least ag 2 1 for which 2.1 holds for every a > egg. More precisely,
ao inf 2 1: are a-clusters for a > a').
(2.3)
We will demonstrate that using the Fermat distance in our definition enables to address various natural scenarios characterized by clusters effectively. This also generalizes other notions of clusters based on level sets of f (see Proposition 2.2 below). We will also show the existence of finite critical parameter ao under mild conditions. Observe that the clusters of f need not be uniquely defined.
2.1 Preliminaries
We first introduce notations used in the sequel. Given a set C' E IRP, the distance function to C, denoted by de, is defined by
dc(x)
inf - y/ yEC
(2.4)
Notice that since C' = RD= de(x) 0}. the distance function de fully characterize C as soon as is closed.
We call rfoetttt of C, denoted by C", the of points at distance at most of C, equivalently the sublevel set defined by
C" = f= ( $r}.
(2.5)
Finally, we define the reach of C, denoted as rch(C) as the largest value > 0 such that for all y C", there exists a unique E C such that x-- yl (v).. The reach of a quantifies how far a compact set from being convex. Notice that rch(C) is small if either C' is not smooth or if C' is close to being self-intersecting, On the other hand, if C is convex, then rCh oc.
Consider two disjoint, connected and compact sets A, B c R such that AUB. We denote the shortest Euclidean distance between A and by
dist B) inf {la b| A,
(2.6)
If dist(A, B) - 5> > and we call p E R x C the middle point a shortest straight line from A to B, then the projection of onto C' is not unique it has at least candidate A and B. We can then state that rch(C) < 5/2. Moreover, if A and B are convex, rch(C) = 8/2. The interested reader can refer to I M for a more detailed introduction these concepts.
3

---

Publishod in Transactions on Machine Learning Research (/)
2.2 Existence of a critical parameter
We can now state the existence of a critical parameter ou.
Proposition 2.2. Let C (C,) be family of compact and connected sets such that C U C. has positive reach T O. Suppose that f(z) an for all C, and [(x) S for all x & C, with ai > do- Then, there exists positive constant 30 2 depending on the diameters of the Ci reuch of C and the intrinsic dimensioo of C such that for all
30
a>1+d
(2.7)
log(ar/oo)
the macroscopic clustering problem () is a-feasible. If the length of geodesics in C is uniformll bounded, the constant Bg can be taken independent of d (and hence, the bound from below for the critical parameter is linear in d).
Proof. The proof of this proposition is postponed to Appendix
A
Remark 2.3. As pointed out before, the reach encodes the geometric complexity of the problem. A small reach is associated with more complex problem. This is present in the previous result in the dependence of the constant So on the reach. The constant So can be computed explicitly, and in fact, an explicit formula is given in the course of the proof of the proposition. When C' is such that the geodesic path lengths are not uniformly upper bounded, the parameter Bo turns out to scale proportional to d, giving that the bound from below for do scales as d?.
Remark 2.4. The hypothesis of Proposition 2.2 forces f to be discontinuous (otherwise, we necessary have dg = az). We prefer to first deal with this restriclive situation simplify the exposition, but in fact, this restriction removed to cover the case when ʃ is a continuous densily by defining more carefully. In that case, we choose ap < 01 in such way that there is a region around each cluster that separates the level sets f (as) and f (a)). Tt is worth observing the behavior of the lower bound as + and as ap + 01
be
Proposition 2.5. Let C = (Ci)isism and C= UCC as before. Suppose that f 2 a1 in C, and let ap be such that r = inf |s 1l E f (10; anl), 1 ((an } < = reh(C). Then, there exists e > such that for every <rr< C
log F-(r+ー] (cr (cr ao-vv v1)
1
(2.8)
log(ai/00
the macroscopic clustering problem is a-feasible. If the length of geodesics in C is uniformly bounded, we can take as in 2.7 with the constant Su independent of (and hence the bound from below for the critical parometer is linear in d).
Proof. The proof is postponed to Appendix A
3 Empirical clusters
In this section, we leverage concepts established the preceding section to address clustering quandary the context of finite samples. Our goal is to ascertain the specific conditions under which clustering problem can solved solely by harnessing the properties of the Fermat distance.
Definition 3.1 (Clustering). Given a family clusters (C,) C IRP and points Qn = (......goll c RD, we say that the empirical clustering problem acasiblle for Qn if there exists such that
(2, y) S n (n- 13/4 De -c,
(3.1)
for all S i S m, 2,6 Qn n C. and y' Qn n C₁ # i. When Qn is random, call F(a, F(a, e, Qn, .I,..., Cm) the event under which the samples are such that 3.1 holds.
The idea here is that simple classification rule using Fermat distance should be sufficient to reach perfect clustering. We now state the main result of this section, which relates the macroscopic problem the microscopic
4

---

Publishod in Transactions on Machine Learning Research (/)
Proposition 3.2. Let C (Ci)isism be family of disjoint, compact and connected sets, and C = U C.. Assume () a feasible for large enough. Assume forther that C is a closed d dimensional Riemannian manifold embedded in RD and f is smooth probability densily function with lim inf M (a) >
Then there exist O, constants 0, O and integer io such that for 2 have for ao.
P(F(a, 6,))) S Sen
Connersely, for every 6 > O there is - < ao such that for every 2 n,
Proof. The proof is given in Appendix A
Remark 3.3. Following D. given a and d, the constant y can be chosen the open interval (0, a(2a d)). is open problem to determine á as function of a and d.
3.1 Example with piecewise constant densities (clutter)
In R., we denote d' d-dimensional ball centered in the origin O with radius r by Ba(r), and the volume (1) by Wa- Consider two d d-dimensional ring C1, C2 centered at 0 contained in hypercube K: C1 Ba( x Ba(1), C2 = Ba( {, K = [-3,3] Let Pe be the uniform measure supported on C C1 U C2, and Pk be the uniform measure supported on K. Suppose Qn = (g.......0 9n a random sample generated from mixture of Pe and Pk.
X X,, Pa XPc + (1- Pk:
(3.2)
with [0,1] being proportion parameter that quantifies the higual-to-niise ratio in the sample (see Figure la
This model is usually called clutter noise in the literature. We are observing data points near or in C, but we aim at finding bi-partition of K such that C₁ and C2 strietly contained in two different clusters. We plug the sample Fermat distance in the K K-meddidd algorithm, that we denote Fermat K K-medoidd (see Section for more details). We are interested in the relation between the parameter a and the predictions for any point in C U2.
Notice that the distribution Pa admits a density f with respect to the Lebesgue measure,
f(z)
+ (1c, + (cx + A)
K Lx(x),
(3.3)
where [Ci|, [C2] and | denote volume of Ci, C2 and K, respectively.
Our goal now is to find an explicit bound for the critical parameter. The argument follows the same lines as the proof of Proposition 2.2 but with explicit quantities. The idea that it is sufficient to set a such that the Fermat cost of the shortest straight line between C₁ and C2 and outside C1 UC2, is always greater than any Fermat distance between two points inside the same cluster. We need to compute the longest geodesic distance (with respect to the Euclidean norm) lying in C denoted by L. This model's explicit upper bound is L < 5m/2. In the proof of Proposition 2.2 the upper bound on is computed for a general case and depends on the r-covering number C, with < r rch(C)). We have, rCh(C) dist(Ci, C2)/2 1/2, a1 A/([Ca] + [Cal), and au
A/|K]-
Any continuous path that intersects both C1 and C2 has an Euclidean length of at least dist(Ca, C2) = 1. Then, the Fermat distance of any path lying in two distinct clusters is at least ag (1-a)/d It suffices to choose a such that the Fermat cost between Ci and C2 is always greater than
dp (-o)/d Laf (1-i-
log(L) log(a /ap)
(3.4)
We have obtained the upper bound
log Gw
< 1 + log(a1/ag
(3.5)
meaning that (C1, C2) c-clusters for every 2 Figure shows the result of applying K-medoids for different choices of a and different values of À with sample size n. We observe that we can achieve clustering above this threshold for the theoretical values of ag found using 3.5
5

---

Published in Transactions on Machine Learning Research (/)
The bbes
apha 1
abota 1.2
apns 1.6
2,
3
O
O
(a)
19h2
-2
(b)
Figure An example of predictions of the Fermat medoids algorithm on data with common density f for (A) X 0.99, 1000 and (B) 2/3, n 1500. The theoretical values for the critical value of a based (3.5) give au < 1.45 and 0g < 2.2, respectively, meaning that above those values are able to perform elficient clustering with high probability for large n.
Remark that oep is the theoretical critical parameter. In practice, fluctuates (see Proposition 3.2 This synthetic example illustrates that the parameter a calibrates the sensitivity of the distance both the geometry and density of the data. Note that when 1, the Fermat distance boils down to the Euclidean distance, and predictions result from the classical K medoids algorithm. By pushing up the value, the algorithm captures the structure of both rings despite the noise and performs partition that perfectly identifies Ci and C2.
the sample Fermat distance, the threshold
4 Variability as a function of
When opting for large value of to get distance that aptly captures the intricacies of the geometry and the data distribution, it is essential to recognize that this choice can introduce two noteworthy challenges.
Heightened variability of Somple Fermat Distance, Choosing a large value of a can lead to amplified vari- ability within the sample Fermal distance.

---

Published in Transactions on Machine Learning Research (/)
2. Floating point arithmetic. There is the concern numerical inaccuracies arising due to the utilization of larger that lead to the manipulation of numbers that differ in orders of magnitude.
This section delves into the first of these issues, furnishing preliminary insights into the exploration of variance within the sample Fermat distance statistic.
Deriving exact characterizations of the variance of (o-11// DQ... (z, y) in dimeensions larger than one have been shown to be challenging (2 (3) and is still an open problem in the context of First Passage Percolation. The one-dimensional case is much more tractable, but the computations are not obvious even in this case.
Since interested in comparing the variability of the Fermat distance for different values of a, we need that does not depend on the scale of the statistic as varies, We consider the coefficient of variation of D
Var (Dém.)) D
(4.1)
when a varies and n is fixed. In particular, we aim to understand the effect of the parameter a on the variation, giving idea of threshold which might better set below in practice.
4.1 One-dimensionss case
For the one-dimensional case, we can explicitly calculate the spacings between consecutive points the optimal path. In that case, are going to consider sample Qn {g1, 92...., qn of uniform independent points in [0, 1] and study the microscopic Fermat distance. In this simple case, it is given by,
D
ld
(4.2)
1=0
1=0
with 8² , (n) the order statistics of Qu, g¹)) 0 and 9 g(++2) =
Proposition 4.1. The expectation and variance of Dam for the wniform case verify
lim E/na-1 D = I(a + 1),
lim Varin" " D = I(2a 1) (a 1+I
Proof. The proof is provided in the Appendix A
This result shows how the variability of the Fermat distance increases exponentially with the value of a. we consider the coefficient of variation given by
Var(De=1 Qn.a
r(2a 1) (a 1 (a +
(4.3)
['aa 1)²
this scales exponentially as a function of a, given large values even for small values of a. Notice that this result further implies that the constant pla, d) involved in Equation 1.3) satisfies p(a,1) T(o + 1).
4.2 Higher dimensions
In higher dimensions, as already mentioned, the asymptotic behavior n the variance of Fermat distance an open problem even for Poisson point processes in Euclidean space. Similarly, cannot prove sufficiently informative bound on the variance the Fermat distance terms of the parameter a. This is to the difficulty finding quantitative lower bounds for the Fermat distance.
However, we conjecture that the coefficient of variation scales exponentially in f= a/d. This suggests that we should choose in order to guarantee that a/d is not too large. We now prove bound for the moments of the Fermat distance for an intensity one Poisson process in Euclidean space, showing that moments of order k are at most of order l'k0 1).

---

Publishod in Transactions on Machine Learning Research (/)
Proposition 4.2. Let Qn be a Poisson process with intensity n in the hypercube of IR Then we have,
I m((n J (0,a)() 2c 0 T 1))-
Proof. The proof is provided in the Appendix
5
Experiments
We consider here a series of clustering experiments involving the Fermat distance for different choices of o. We are going evaluate the trade-off between small values of a for which clustering not feasible (Section and large values of a where finite sampling effects distort the distance (Section
5.1 Fermat K K-medoids
We the K-medoids algorithm for clustering 15 10 each cluster are forced to be point in the set Qn- An advantage of K-medoids is that different notions of distances can be used, leading to different partitions. The algorithm consists of alternating updates in the estimated cluster centroids & and cluster Ć C Qn until the cluster assignment does not change. 'These updates are sequentially given by
robust version of K- K-means in which the centroids of
2 +- arg min
Σ De.a((
(5.1)
zEC;
C fx E Qn D S D))
(5.2)
Note that different values of give different partitions. II a 1, the sample Fermat distance boils down the Euclidean distance, and both Fermat K-medoids and classical K K-medoids coincide. For > 1, clusters are not necessarily convex.
5.2 Synthetic data
We evaluate the performance of the Fermat K-medoids clustering algorithu when analysing the Swiss-roll generated dataset. We consider four clusters sampled from Gaussian distribution in dimensions with different
and then mapped to three dimensions using the map (x, v) + (a cos(wx), oy, sin(wr)) for 3, w = 15. We consider a total of n 1000 random samples, equally split between four different clusters. This generates the dataset illustrated in Figure 2 When evaluating the performance of Fermat K-medoids using adjusted mutual information, adjusted
rand index, accuracy, and Fl score (19 27 20), we observe that smaller values of result in poor performances for all performance metrics. As we increase the value of a, the performance increases until the performance decays again for large values of a, having an optimal value some middle range values for a. We also observe large variances in performance for large values of resulting in decaying median performances over new samplings. We compare the performance using K-medoids but with the distance obtained using Isomap P and C-Isomap (24).
These experiments show that there is optimal range of values of a that results in better clustering performance. This illustrates the point made previous sections, showing that both small and large values a result poor performances.
5.3 Clustering MNIST
We now consider an example that inhabits a higher-dinennsionll and inhereutly more realistic realu: the digits and 8 extracted from the MNIST dataset. Our approach begins by subjecting the data to preprocessing through PCA, resulting a rednced--dimensional representation of dimension 40. We then cluster this representation using K K-medoids with the Fermat distance. We compute the adjusted mutual information (AMI) and compare it
to the performances of means with Euclidean distance and a robust EM procedure 21 22 recognized for its consistently good performance
fully unsupervised method.
The findings are consolidated in Figure 3 In this instance, the clear presence an advantageous parameter range becomes apparent. Notably, the remarkable advantage gained from operating within this window, compared to
8

---

Published in Transactions on Machine Learning Research (/)
Adgartal
Adgotadd Htad
67
02-
13
Aueeayy
21 Store
Figure 2: Different clustering performance indices for the Swiss Roll dataset. Solid lines correspond to the mean, median, and best performance archived by Fermat K-medoids over different samplings of the dataset. Dashed lines correspond to the performance obtained by the best output between Isomap and C-Isomap. This experiment has been presented previously ICLR 2018 Workshop Track (23
0.6
Adjusted Mutual Information (AMI)
0.5
0.4
Robust EM
0.3
K-Means
Fermat K-Medoids
0.2
0.1
2
4
8
Figure 3: Performance of Fermat K-medoids algorithm compared to standard K-means and Robust expertaton-moxiniztion.. Simulations credit to Alfredo Umfurer.
employing the Euclidean distance, is striking. Furthermore, it is remarkable that even relatively straightforward algorithm like K-medoids can yield performance akin to significantly more computationally intricate methods when paired with the appropriate distance parameter.

---

Published in Transactions on Machine Learning Research (/)
d=2
d 3
d
Coefficient Variatio
Vor oke
1:0
10
0.
0.0
2.0
255
4.1
1.5
24
4.0
4.5
3.0 3.5
50
s// /dd
Figure 4: Coefficient of variation for the uniform distributions as a function of a/d for different ambient dimensions d =2 2,3, 4.
5.4 Coefficient of variation.
We conclude this section by conducting numerical exploration of the influence of noise the coefficient of variation of the Fermat distance. We plot in Figure 4 the coefficient of variation defined in 4. in the case a uniform distribution [0, 1j function of a/d. As conjectured, observe exponential behaviour in the parameter a/d, demonstrated in dimension one and conjectured in higher dimensions.
Acknowledgments
We acknowledge the support the STIC AMSUD Project LAGOON for Pablo Croisman and Matthieu Jonckheere as well as the DATAIA support for Facundo Sapienza and Laure Ferraris.
References
[1] Eddie Aamari, Clément Berenfeld, and Clément Levrard. Optimal reach estimation metric learning. arXie preprint arXim:2207.060 060744 2022.
[2] Antonio Auffinger, Michael Damron, and Jack Hanson. 50 years of first-passage percolation, volume 68 of Univ.
Lect. Ser. Providence, RI: American Mathematical Society (AMS), 2017.
3 Jeff Calder and Mahmood Ettehad. Hamilton-jacobi equations graphs with applications to semi-supervised learning and data depth. Journal of Machine Learning Research, 23(318):1-62 2022.
[4] A. Carpio, L. L. Bonilla, J. C. Mathews, and A. R. Tameenbaum. Fingerpriuts of cancer by persistent homology. bio 2019.
[5] Ana Carpio, LL Bonilla, Mathews, and Tannenbaum. Fingerprints of cancer by persistent homology. bio page 777169, 2019.
66] Alejandro Cholaquidis, Ricardo Fraiman, and Leonardo Moreno. Universally consistent estimation of the reach.
J. Stat. Plann. Inference, 225:110 120, 2023.
[7] A. Erdélyi and F. G. Tricomi. The asymptotic expansion of ratio of gamma functions. Pacific Journal of Mathematics, 1(1):133 142, 1951.
(8) Herbert Federer. Curvature measures. Transactions of the American Mathematical Society, 93(3):188-44 491, 1959.
[9] Ximena Fernández, Eugenio Borghini, Gabriel Mindlin, and Pablo Croisman. Intrinsic persistent homology via density-based metric learning. Journal of Machine Learning Research, 24(75):1-44 42, 2023.
110 J. Friedman, T. Hastie, and R. Tibshirani. The elements of statistical learning, volume 1. Springer series in statistics New York, 2001.
10

---

Publishod in Transactions on Machine Learning Research (/)
[11] Pablo Groisman, Matthieu Jonckheere, and Facundo Sapienza. Nonhomogeneous euclidean first-passage perco- lation and distance learning. Bernoulki 28(1):255 276, 2022.
[12] Howard and C. M. Newman, Euclidean models of first- mist-passage percolation. Probability Theory and Related Pields, 108(2))153-170, 1997.
[13] C. D. Howard and C. M. Newman. Geodesics and spanning trees for Fuclidean first-passage percolation. Ann. Probab., 29(2):577-66) -23,, 2001.
[14] S. J. Hwang, S. B. Damelin, and A. O. Hero, III. Shortest path through random points. Ann. Appl. Probab., 26(5):2791 2823, 2016.
[15] Leonard Kaufman. Partitioning around medoids (program pam). Finding Groups in Data, 344:68-125, 1990.
[16] Little, D. McKenzie, and J. Murphy. Balancing geometry and density: Path distances on high-dimensional data. STAM Journal Mathematics of Data Science, 4:1, 2022.
17] Andriana Manousidaki, Anna Little, and Yuying Xie. Clustering and visualization of single-cell ma--ee data using path metrics. bioHlave pages 2021-12, 2021.
[18] D. Mckenzie and S. Damelin. Power weighted shortest paths for clustering euclidean data. Foundations of Dala Science, 133):007, 2019.
[19] Marina Meilä. Comparing clusterings-an an information based distance. Journal of multivoriate analysis, 98(5):873 895, 2007.
200 David M. W. Powers. Evaluation: from precision, recall and f-measure to roc, informedness, markedness and correlation, 2020.
21] Violeta Roizman, Matthieu Jonckheere, and Frédéric Pascal. A flexible em-like clustering algorithm for noisy data. arXiu preprint 19X.0:190.006661 2019.
22) Violeta Roizman, Matthieu Jonekheere, and Frédéric Pascal. Robust clustering and outlier rejection using the mahalanobis distance distribution. In 2020 28th European Signal Processing Conference (EUSIPCO), pages 2448 2452,222222 2021.
[23] Sapienza, P. Groisman, and M. Jonckheere. Weighted geodesic distance following Fermat's principle. International Conference on Learning Representation, 2018.
[24] Vin Silva and Joshua Tenenbaum. Global versus local methods in nonlinear dimensionality reduction. Advances in neural information processing systems, 15, 2002.
255 Joshua B. Tenenbaum, Vin de Silva, and John C. Langford. A global geometric framework for nonlinear dimen- sionality reduction. Science, 290(5500): 23119 2323, 2000.
[26] Nicolás García Trillos, Anna Little, Daniel McKenzie, and James M Murphy. Fermat distances: Metric approx- imation, spectral convergence, and clustering algorithms. arXiv preprint arX:::2307.057550 2023.
[27] Nguyen Xuan Vinh, Julien Epps, and James Bailey. Information theoretic measures for clusterings compar- ison: Variants, properties, normalization and correction for chance. Journal of Machine Learning Research, 11(95):2887722 2854,, 2010.
288 Mariia Vladimirova, Stéphane Girard, Hien Nguyen, and Julyan Arbel. Sub-weibull distributions: Generalizing sub-gaussian and sub-exponential properties to heavier tailed distributions. Stal, 9(1)x8318 2020. c318 st84.318.
11

---

Publishod in Transactions on Machine Learning Research (/)
A Proofs
Proof of Proposition 2.
We prove that there exists 2 such that for all there is e >> 0 such that for S m and 2, E Ci.
(a,,,)) s Da(a,y)) c, for all y' E C2 jti. First, we bound from below the Fermat distance between two points in two different sets, By assumption, rch(() 7 Since S min dist(Ce, C2)/2, for all x & C, f(x) $ an and any path from Cs to Cj has measure at least 2r in 143 the complement of C' when i # j, we have for I Ci, v E Ct,,
Da v') 2 a0 (3-0)/d 27.
(A.1)
Second, we bound from above the Fermat distance between two points i and y in the same cluster C.. Since C is compact, we can consider a finite covering by N, D-dimensional balls, Bo, with radius T, and centers y = fui,...,eN,, C C, ie.,
Nr. C CCUBD(()))CCC
We are going to build a path from æ y inside Cf C and project it onto C. By construction, we know that the path will be projected onto C. Let V. = (VDC.). Observe that (Bn(u)r)): ir E Vi) is a covering of Ca by (V:) NC.( N, balls. Consider the weighted graph G, with vertex set Va in which two vertices are connected if and only their respective balls intersect. The weight of an edge is given by the Enclidean distance between the two points. By construction, this graph connected, and the weight of each edge is most 2r. We connect x to the center v(x) E Vi of a ball containing it. We have |x v(x) S r. Similarly, we connect to a v(y) E V. such that by - evy) $ r.
By definition, the shortest path from x to inside G, denoted by cannot go through the same vertex more than once. Then the Euclidean length of y, denoted by Iy| verifies
Ir| $ (C.) S 2r.
As 7 C C" and r < r, the projection of onto C, TT(7) = %, is well defined. Moreover Te(7) C C.. The projection map is Lipschitz, with Lipschitz constant
[ Theorem 4.8)). Then we have,
Ins po (7) S __ --r 2r
The path Y. from r to y, is contained in C. C C and for all x E C., f(x) 2 a1. Then,
(1-a)/d T (2(a,)) & I fla- & al 7- N, 2r. Next, we calibrate a to ensure the clustering feasibility, ie., one gel,
(A.2)
(1a)/d 27 > di --r dp
(laa/d T N, 2r:
(A.3)
which is equivalent to,
log
Nr
> 1+d log(a1/00)
Now, suppose that N, is optimal, f.c., it is the smallest number of balls (D( that covers C. As C is compact, there exists a positive constant e (depending on the dimension) such that N2 S cr V 1, where d is the intrinsic dimension of C. Choose r 5 to get,
log (c(G)-dv1)
1 d log(a1/00
(A.4)
12

---

Publishod in Transactions on Machine Learning Research (/)
The first part of the proof finishes by taking B = (c(2) 1).
If C is smooth enough that the length of geodesics in C' is uniformly bounded by R, we take instead T/ to be the geodesic from æ to y to obtain the bound
Da v) s / fla-lya s af (1-a)/d R,
instead
A.2 The rest of the proof follows verbatim to obtain
log( R/27) log (og(a1/an) /oa)
1+
(A.5)
Proof of Proposition 2.5 careful. Recall that C' is compact, f 2 an in C and as is such that there exists region around each cluster that strictly separates the level-sets (a1) and (ao) with the projection being well defined. More precisely, have that for
The proof follows the same lines the of Proposition 2.2 but need to be more
= inf {|s 1 8 E ((0: aul), t f ((a1; ool) 0,
the inequality = rch(C) > is verified.
We first prove that rch(C") = rCh(C)) --=====--- y,- do that, observe that for any > 0, (C")²= C In fact, if E (CT)); as C is compact, we know that there exists at least one projection of I onto C' denoled by (o(r). Applying the customs passage theorem, we have [( (x)) ((())) * ó. Call z the point lying at this intersection. We have,
de(x) = inf l pp S 1x - 2| + inf 2 -pl < 56+ PEC
DEC
Then x E C=+5__ On the other hand, for x E C either dc(x) S and x E (C or de(x) > Suppose des (x) 8. As assumed that des (x) |r 2| > 5 and
Ix (z) |a 2| + |r (x) 6
A contradiction. Hence (x) < 6 and x e c (C This proves our claim
rch(C") rCh(C) 7 -
The bound from below for the macroscopic Fermat distance between two points lying in two different clusters is the same as in A.1 and we omit it here.
The upper bound for the macroscopic Fermat distance between two points lying in the same cluster is also very similar. The only difference that we need to build an r-covering of C instead of C, with r < rch(C") = y, We define the shortest path (in the neighborhood graph restricted to C?) inside (CT)² = C,+r, 1 i m, in the same manner. The length of this path is smaller than 2(T N),,, where N, is the covering number of C",
We first project this path C", which will be projected on CP by coustruction. We project this new path C, which is still by construction projected on C. Applying two times Federer's theorem (8) Theorem 4.8-(8)) the condition A.3 on becomes
(1 [--oddd 27 > af
[1-a)fd
T1 11
(--))
N. 2r.
T r-
which is equivalent to
log -
a > 1 1+
log(a1/00)
13

---

Publishod in Transactions on Machine Learning Research (/)
Next, we prove Proposition 3.2 We will use the following lemmaa, whose proof is elementary and is omitted.
Lemma A.1. Assume M is compact ond that for all æ E M,, If(x) > >>>0 0. Then for every > 0 there is > such that for every u, U E M with lu vl S 6 have (u, D (2 (v, c for every 2 E M.
Proof of Proposition 3.2 We first prove that the definition a-clusters implies with overwhelming probability n large enough. Using the definition of owu, for > ou 1 there exists >> such that,
D1 v) & (x, - e, for all 2, E C. o' C2 iti.
(A.6)
Consider the events,
An,a = { f1r0- (e. - pD w) S s/33, for all x Qn)
By Proposition 2.6 in there is y and c> 0 such that for large enough
p(A snn VI sissn m.
Now, on An.a. we have for x, E Os and v' E Cj. i ti,
(o-1)/d Do (2, S DD (I. y) + c/3
S nD (z, 1/) + f/3 -
(by the clustering condition 2.1
s n 1o- (.. + 22/33-
Since 2c/3- -c/3 have
n (1-1)/d Da (2, S (a--)d D e/3,
on An.a Hence
& 5e
for n large enough.
Next, take a < og such that (C, f) not a-fessible and suppose that the microscopic clustering conditions
are
satisfied, Le., there exists > 0 such that for every i j. x, y E C: nQn and y' E C3 n Qn we have
n (111))/ (z (o-11// Do (x,8))= -c
(A.7)
So, An.. we have,
uD v) n (a-1)/d
DQn.a y) + t/3
s n (a (a-1)/4 1)/d Den. (z, + e/3
(by A.7
s nD (z, v/ + 2 e.
We have,
(x,))) & Dz y') c/3p, which not hold since (C, f) is not feassibll This means that A.. F(n,a) and the conclusion of the proposition follows.
Proof of proposition 4.1 The study of the statistic D&=i_ boils down to the study of the uniform spacings given by
A, (i+1) -00h (6) for i 1,2, 1, Ao ()) and A.. 1 - (n) Using that the joint density of the order statistics , ()) ..... (n) given by
p(1,,2,..... bn) n! s0000
14

---

Publishod in Transactions on Machine Learning Research (/)
it is easy to derive the joint distribution of the vector "o....,An-1) which is uniformly distributed on the n dimensional simplex denoted by
Sn =
(80: 8n-1) R", 80, 81, ......... 1
Σ S J
That is (Ao....,An ~ Dir(a), where Dir(a) denotes the flat Dirichlet distribution with parameter E Ra+1
(1,..,, 1) and An 1 Ei= A. The moments of the Dirichlet distribution can be easily found
I(n 1)
B ) "KAoo.....DDiii (|/3))
+an++++ T(a 1),
T(n 1) I(n + + 1)
E A
A -
[(a 1)²
The relative asymptotic behaviour of Gamma functions given by f
[( + aa)
--- (1 [( +
1+ (1+ (a (a + 1)
+ (11 )
(A.8)
implies that r(n a 1)/(n + (m) + 1 as n cc. Then,
lim n "[A[A = I(a 1),
lim n 20 "EEE 4, I(a+ n-
n-000
Finally,
a E E Un.0l = n1 --1g
A
= E [[(nn)) 11000 I(a + 1).
1=0
On the other hand, the second moment be computed
( E
2
(n
1)B [A?"] + renn 1)E[A748]
(n 20 E[A + +
nn + 1) [B A
Rearranging the terms the last expression, we obtain
n Varin a- Dd=1 n+1 (B|n 20 A Bin Ail?)
+ (n + 1) Covin AT, n A2).
As n + 0o, the first term on the right-hand side converges to [[2a + 1) I(a + 1) Based again in Equation A.8
have
I'n +(n+1) 1)
I'(n + 1)²
I(a+1)²
I(n+ 2a
[(n + a + 1]3
2a(2a 1) 0(n
1
n
2n+
ala -(1- 1)
+ +(n
I(a 1)
2n4
a²
T(a+ + 1)a n
O(n -2)
n
where n4
This implies
lim (n + 1) Cov(n" Af, n A3) = a²r(a 1)3
15

---

Publishod in Transactions on Machine Learning Research (/)
which finally gives
lim Varln"-'D@nn.ll 1(2a 1) - (a + 1)1((a 1)2.
Proof of Proposition 4.2 Note that we can turn results for a Poisson process intensity n in the hypercube to a scaled Poisson process n 1., which essentially (up to exponentially small probability events) a unit Poisson process P in the hyperplane (see Theorem 2.4 in (12)). Hence with I = n 1/d we replace 22"-1)/ aa. ( (0,e)) e1) by p... (e)))), and now work with a unit Poisson process. The proof is based on constructing a specific (sub-optimal) path that has been considered previously in 13 Define the sets,
D((0)= = b < for 2 23i5 2gisd st, 0 o.b.
where o; -1 12:20 Let us now construct inductively specific path l points qo. .0....9 such that for S 1,
00 X₁ inf (1 > 0, there is point in Di
4e particle present in Dx, (Øx-1),
Finally, Q--1 = len. Observe that,
[4 91-11"² & xe
xe and lu011 - le11" s
Σ d x
Using basic properties of Poisson processes, we get that the random variables (X.)sgig are i.idd Now,
P(X, 2 x) = P( no points in Dz(0)) = e -(14)aa
Therefore,
P(XP 2 x)) = (1/1)///0
=e -1//)o/0
Hence,
Dd (0,e()) S Σ
17, T 11 + 1g - lea1"
1m0
which gives that
P(D2,p(0,les) 2 Lo) P
q 1 lx
i=1
< P
l q. 1 10
lx
S P
Σ
x 12/20/12
Note that a > d, we cannot use the usual large deviation bounds as the variable X, does not have an exponential moment. We can, however, their usual moments. Our computations similar to the ones in 28
Observe that P(Y 2 x) -c- - /d implies E(Y") d 1).
16

---

Publishod in Transactions on Machine Learning Research (/)
Let Y; = X;" and take 7 2 1. Then,
P
Σ
2:21
x E
(Σ x: }
(A.9)
1=1
B077)
17
(A.10)
(A.11)
(A.12)
We use the bound T(x + 1) & x" for x 2 in the last line. Taking such that (10)) = = we can state that for all y
P
Σ 1=1
Yi 2 (10))1
sea
and 700= x with e 20d0 leads
I Y: 2
/d
1m
for all x > c. Hence
sot [ -0/00)//00 dr,
E
We obtain,
(11 (a,pee)())) s cl + +))
17


Reviews:
[{"review_id": "CdYWv3b5fr", "reviewer": "Reviewer_XVgj", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**:\n\n- Paper is well-written and addresses an interesting issue within the realm of machine learning, particularly in the context of clustering. \n- The mathematical derivations appear robust and devoid of any significant mathematical errors.\n\n- The paper follows an interesting trajectory, incorporating a variety of tools, notably from high-dimensional geometry and analysis. However, it's worth noting that the current strength of the claims may not be particularly interesting at this point.\n\n**Weaknesses**:\n\n- It would enhance the paper's practical applicability if the authors delved more extensively into the potential applications of Fermat distance in real-world settings. As it stands, the paper appears more focused on the mathematical aspects.\n\n- The definition of \"clusters\" in Definition 2.1 appears overly restrictive. Specifically, the assumption of the existence of a metric (Fermat distance in this case) where all inter-cluster distances are consistently smaller than intra-cluster distances seems applicable to only a limited subset of clustering scenarios, notably a special case of \"well-separated\" ones.\n\n- Due to the stringent assumptions, the proof of Proposition 2.2 seems somewhat simplistic, potentially hampering the overall contribution of the paper. Nonetheless, the incorporation of mathematical tools such as the \"reach of set\" or leveraging Theorem 4.8 from [6] is indeed a commendable contribution.\n\n- **Major concern 1**: The conditions outlined in Propositions 2.2 and 3.2 are posited as \"sufficient\" for identifying optimal clusters $\\left(C_i\\right)_{i=1}^{m}$. While it's evident that they are \"necessary,\" establishing their sufficiency requires an algorithm with a rigorously proven capacity to identify clusters (computational complexity aside). I am not convinced the conditions in Propositions 2.2 and 3.2 are \"sufficient\" for finding the optimal (true) clusters. \n\n- **Major concern 2**: Proposition 3.2 appears hastily presented and somewhat vague. The mere \"existence\" of constants $\\gamma, \\delta, c, \\bar{n}$ lacks depth; they should be properly bounded as functions of other parameters. For instance, there should be clear bounds on $\\bar{n}$ to prevent divergence or restrictions on the values of $\\gamma$, which might vary significantly. In other words, $\\bar{n}$ might diverge to infinity in some cases, or $\\gamma$ could become very small or very large (the latter is not good for the converse statement).\n\n- **Major concern 3**: The overal contribution of this work is not entirely clear. While the authors establish general statements regarding the clusterability of certain mixture models via the utilization of Fermat distance with a propely chosen $\\alpha$, the inherent complexity of these problems appears to have transitioned into abstract and possibly intractable quantities, such as \"the reach of the cluster sets.\" This shift raises concerns about the practical utility of Fermat distances in real-world applications. In other words, I am afraid authors have turned one form of complexity into another form, which is still not tractable and thus undermines the use of Fermat distances for practical use.\n\n- The analyses in Section 3.1, 4.1, and 4.2 rely on carefully selected toy examples rather than providing broad mathematical guarantees. Admittedly, offering general assurances in this field might be challenging and could correspond to open problems in mathematics.\n\n----------\n\n**Minor comments**:\n\n- Abstract: exploding or exploiting?\n\n- The abstract lacks clarity and might require a major revision. Notably, Fermat distance remains undefined, yet the discussion on $\\alpha$ has already started.\n\n- The minimization problem in Eq (1.1) of Definition 1.1 appears mathematically flawed. The objective for $\\inf$ is ambiguous, seemingly involving the choice and ordering of $q_i$s, but lacks precise clarification.\n\n- In Remark 2.4, the authors assert that the conditions in Proposition 2.2 necessitate $f$ to be discontinuous. However, in my understanding $f$ can be continuous and conditions in Propostion 2.2 still hold, for example by forcing $C_i$s to be distanced away from each other, right?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper explores the theoretical implications of employing both statistical and empirical versions of Fermat distance in clustering problems. Fermat distance between any two points $x,y\\in\\mathcal{M}\\subseteq\\mathbb{R}^D$ (where $\\mathcal{M}$ denotes a $d$-dimensional Reimannian manifold with $d\\leq D$) and with respect to a probability density $f$ over the manifold is defined, in the statistical sense, as:\n\n$D^d_{\\alpha}=\\inf_{\\gamma\\in\\Gamma_{x,y}}\\int\\frac{1}{f^{(\\alpha-1)/d}}$,\n\nwhere $\\inf$ is taken w.r.t. all integrable paths over $\\mathcal{M}$ connecting $x$ to $y$, i.e., $\\Gamma_{x,y}$. The empirical version tries to approximate the above formula via $n$ randomly sampled points from $f$, which turns the above continuous minization problem into a tractable combinatorial optimization problem (Eq. (1.1) of the paper). Uniform convergence of the empirical version to the true statistical one is already proved in the literature.\n\n**Claims**:\n\nThe authors claim and subsequently prove that for sufficiently large values of $\\alpha$, the metric, even in the empirical scenario with a sufficiently large sample size $n$, becomes valuable for clustering specific statistical mixture models or well-separated high-density regions of a single density function $f$.\n\n**Contributions**\n\n- In Proposition 2.2, the authors establish the validity of their claim for the asymptotic case ($n\\rightarrow\\infty$) using various geometric tools. Proposition 3.2 extends this validation to the non-asymptotic scenario ($n<\\infty)$. However, reservations are expressed in the Weaknesses section.\n\n- The authors illustrate their findings through a toy example in Section 3.1 with a piecewise-constant density function over a hyper-cube containing two distinct inner rings. Section 4.1 addresses the drawbacks of choosing large $\\alpha$, proposing the existence of an optimal \"window.\" The authors substantiate this claim with a one-dimensional toy example, showcasing the diminishing ratio of \"std-to-mean\" for Fermat distance as $n^{-1/2}$ but exponential growth concerning $\\alpha.\" Section 4.2 explores the higher-dimensional case again in a limited setting.\n\n**Experiments**\n\nPaper also presents a number of numerical experiments, but I didn't manage to check them entirely.\n\n------------------\n\n**Overal Rating**\n\nThis a nice theory paper and is enjoyable to read. Mathematical derivations are crisp and valid, as far as I have checked (I have also checked some of the proofs, but not all of them). The mathematical derivations and proofs are sound, but concerns arise regarding the overall impact. None of the statements are exceptionally strong, applications seem constrained, and some contributions rely on toy examples rather than rigorous mathematical guarantees.\n\nMy current vote is weak reject, but I am open to reconsider this rating it if authors manage to address my concerns properly. Also, I would like to see assessments from other reviewers as well.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the weaknesses section.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "EwpSCyk10Q", "reviewer": "Reviewer_Ck1k", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- The paper is clearly written with a streamlined story to serve the reader.\n- The proved results are interesting, characterizing what would happen for different values of $\\alpha$'s for large sample sizes.\n\nWeaknesses:\n- Some typos or inaccuracies:\n   - Abstract, \"exploding\": Does it mean exploring?\n   - The first paragraph: \"it can take any value\": To be precise I would write \"it can take any integer value in $[1,D]$.\n   - Remark 2.4: \"we necessary have $a_0=a_1$\"\n- In Eq. (1.1), I found the definition questionable: I think the minimum is always attained when $k=1$ and it does not make sense to have larger $k$. Am I correct? If so, please fix it.\n- The legends of the figures are too small. For example, I can't see the legends of Figure 2 clearly without zooming in.\n- I don't see the negative consequences of Proposition 4.1. What can we say about correct recovery or feasibility if the variance is large? Large variance does not seem to have any negative impacts on feasibility. Am I correct?\n- There is a huge gap between theory and experiments. Specifically, the theory concerns whether the clustering problem is feasible. The experiments show clustering accuracy of a specific algorithm (say, a Fermat-distance variant of K-medoids). The issue is that such an algorithm does not necessarily solve the clustering problem optimally (when it is feasible), and it rather relies on a good initialization. Note that in Figure 2 the red curve (best performance among different trials) is almost an increasing function of $\\alpha$. I would argue that a large $\\alpha$ benefits as it makes the clustering problem feasible and furthermore a K-mediods variant with multiple initializations can find a good solution (red curve). This is different from what the paper argues: A large $\\alpha$ can be harmful due to the variability. Please justify.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers the Fermat distance parameterized by $\\alpha$, and the clustering problem defined using this distance.\n\nThe main results of the paper show that the parameter $\\alpha$ needs to be chosen carefully in such a way that the feasibility and variance is balanced. Specifically, the results in Section 2 show that, under certain conditions, a large enough $alpha$ would ensure the clustering problem is feasible. On the other hand, Section 4 shows that with a large $\\alpha$ the variability of the sample Fermat distance is very large.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See the above.", "broader_impact_concerns": "The work is primarily theoretical and does not immediately induce ethical implications.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "b4uNU4Rp39", "reviewer": "Reviewer_oM8B", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths :\n- The authors' objective of optimizing (in terms of performance) the choice of the parameter  $\\alpha$ in order to better perform a clustering task is very relevant in my opinion. I particularly appreciated the proposal of theoretical results to support the behaviours shown in experiments, for a clustering problem conducted using K-medoids method.\n- A study on the sample Fermat distance for understanding its variability, in particular for large value of $\\alpha$, is also conducted in dimension one, and verified in the experiments.\n\nWeaknesses :\n- As the authors point out throughout the paper, the theoretical analysis of a critical value for the parameter $\\alpha$ in the Fermat distance is (i) application dependant and (ii) very difficult to achieve in general cases. Consequently, the analysis carried out in the paper seems somewhat preliminary.\n- The experiments are conducted in the specific case of clustering, although, as mentioned by the authors, a classification task could also be carried out in the same framework.\n\nHowever, to the best of my knowledge, this is the first attempt at a theoretical analysis of the parameter $\\alpha$ in the Fermat distance, which in my opinion paves the way for future research.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a theoretical and experimental study of the parameter $\\alpha$ in the Fermat distance for the clustering problem. The Fermat distance extends the Euclidean distance, by including information about the underlying manifold on which the data is supported and the density function from which the data points are sampled. The authors highlight the importance of the $\\alpha$ parameter for the performance of the clustering problem, and prove the existence of a lower critical value, given by an explicit quantity depending on the geometric complexity of the problem and which delimits its feasibility. Experiments are conducted to empirically confirm that the performance of the clustering problem strongly depends on $\\alpha$.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- It is said (page 2) that the re-scaling of the distance by the power $1/\\alpha$ \"carries implications for practical implementations\", can you develop on this?\n\n- Regarding the experiments in Figure 1, it might be interesting to increase the number of points $n$, to see in the results are more in line with the theoretical value of the critical value (i.e. the clustering remains good for smaller values of $\\alpha$).\n\n- Can the theoretical critical value $\\alpha_0$ of the simulated experiment in Section 5.2 be computed (at least approximatively)?\n\n- Typo : in the proof of Prop 3.2, I think that in (A.6) you meant to include the parameter $\\mu$ in the clustering condition in order to prove the inequality on the sample Fermat distance (page 13)? Moreover, when you say \"(by the clustering condition (2.1))\", I assume you are referring to (A.6) (same inequality).\n\nI think these comments should be addressed for paper acceptance.", "broader_impact_concerns": "I don't think that this paper requires a Broader Impact Statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Based on the reviews, the paper makes significant theoretical contributions by exploring the Fermat distance in clustering problems. The detailed mathematical proofs and the introduction of new propositions about the Fermat distance’s behavior in clustering underscore its potential use in ml problems..

Some reviewers have noted that the application of these theoretical insights into practical scenarios is limited and somewhat abstract. This is sometimes expected with such theoretical approaches. The reliance on toy examples and the lack of broad empirical validations are seen as potential weaknesses. Despite these concerns, which have been discussed during the rebutal, the focus on Fermat distance and its detailed theoretical examination provides a case for its publication, as the field is relatively unexplored and the paper opens new directions for future research. 

In general, reviewer feedback is positive, all leaning towards acceptance, despite reservations about the paper's practical implications and the robustness of some claims.
Decision: Accept (poster)