Source-linked AI summary

Gradient-Guided Density Peak Clustering

Yikun Zhang, Yen-Chi Chen

arXiv:2610.01050v1math.STstat.MEstat.MLstat.TH

TL;DR

DPC’s nearest-higher-density paths can be unstable in low-density regions, making assignments sensitive to local perturbations. GGDPC inserts a gradient-ascent step before each uphill search and relates its graph to population gradient flow. The paper establishes convergence under five complementary criteria, spanning modes, assignments, dendrograms, paths, and density waterfalls.

  • Problem

    DPC’s 1NN uphill rule can send downstream observations to a different center after a local perturbation, while the full path from an arbitrary start is difficult to compare with a stable population object.

    Source: §1 · p. 2
  • Method

    GGDPC takes a gradient-ascent step before each nearest-neighbor uphill search to relate its graph to population gradient-ascent flow.

    Source: §9 · p. 26
  • Results

    GGDPC converges under five criteria: local modes, ARI, dendrogram, graph distance, and density waterfall.

    Source: §9 · p. 26
  • Takeaways & Limitations

    The results provide statistical, geometric, and topological interpretations of DPC-type clustering algorithms.

    Source: §9 · p. 26

    Several downstream results exhibit relatively strong dependence on ambient dimension.

    Source: §9 · p. 26

Abstract

from arXiv · show

Density peak clustering (DPC) connects each observation to its nearest neighbor of higher density and identifies cluster centers as high-density observations with unusually large nearest neighbor uphill shifts. The resulting uphill paths from observations to cluster centers, however, can be irregular and unstable in low-density regions, making the clustering assignments sensitive to local perturbations and obscuring the population geometry of the DPC graph. In this paper, we introduce \emph{gradient-guided density peak clustering} (GGDPC), which performs a gradient ascent step before each nearest neighbor uphill search. We develop a stability theory that relates the GGDPC graph to the gradient ascent flow of the population density. In particular, we establish consistency of GGDPC under five complementary criteria: recovery of local modes, adjusted Rand index, dendrogram (cluster tree), path length, and waterfall measure. Together, these results provide new statistical, geometric, and topological interpretations of DPC-type clustering algorithms.

1 Introduction

DPC’s nearest-higher-density links can send entire branches toward different centers after a local perturbation, complicating comparisons between its paths and population gradient flow. GGDPC adds a gradient step before the uphill search, and the paper develops consistency results for its clusters, paths, dendrogram, graph distance, and density waterfall.

1 Introduction

  • DPC’s nearest-higher-density rule can redirect downstream observations after a local perturbation, producing irregular cluster boundaries and complicating analysis of full paths from arbitrary starting points.The paper relates this instability to the gap in understanding the asymptotic behavior of the entire uphill path.Source: §1 · p. 2

1.1 Main Contributions

  • GGDPC takes a one-step gradient ascent update before each nearest-neighbor uphill search, aiming to stabilize paths while retaining DPC’s interpretable graph and center-selection structure.Near a density mode, where the gradient is small, it retains large uphill shifts used to distinguish well-separated centers.Source: §1.1 · p. 2
  • GGDPC adds a density waterfall plot and a dendrogram to DPC’s graph and decision diagram for visualizing density profiles and threshold-based component merges.The waterfall plots estimated density against global graph distance; the dendrogram follows component merges as the uphill-distance threshold increases.Source: §1.1 · pp. 3–4
  • The paper establishes convergence under five criteria: local modes, adjusted Rand index, dendrogram, graph distance, and density waterfall.The results also give explicit rates; rates generally become slower as the target geometry becomes more refined.Source: §1.1 · p. 4
  • GGDPC’s ascending paths approximate population gradient-ascent flow lengths uniformly over almost every starting point in the density support.The paper presents this as a route toward pathwise consistency for 1NN hill-climbing procedures, including quick shift.Source: §1.1 · pp. 4–5

1.2 Other Related Work

  • Unlike prior DPC modifications aimed at empirical robustness, GGDPC changes the uphill search so its graph can be compared directly with a smooth population dynamical system.The introduction places DPC alongside mode, density-level-set, and hierarchical clustering procedures, while distinguishing GGDPC’s theoretical objective from local corrections.Source: §1 · p. 2, §1.2 · p. 5

2 Problem Setup and Background

The paper sets up density-based clustering for an i.i.d. sample under regularity conditions on the support and density. It describes DPC’s uphill graph and contrasts its assignments with population clusters defined by gradient-ascent destinations.

2 Problem Setup and Background

  • The setup assumes an i.i.d. sample from a distribution with compact support and a smooth density satisfying regularity conditions on its critical points and gradient flow.The density is bounded away from zero on the support, has a three-times continuously differentiable extension, and has finitely many nondegenerate critical points.Source: §2 · p. 6

2.1 Density Peak Clustering

  • DPC links each observation to its nearest observation of higher estimated density, then identifies centers using uphill distance and partitions the graph by removing center edges.The section also notes that DPC can designate low-density observations as noise.Source: §2.1 · p. 7

2.2 Density Mode Clustering

  • Density mode clustering assigns observations to the local modes reached by gradient-ascent flow, defining population clusters as the modes’ basins of attraction.Under the stated conditions, almost every point in the support flows to a local mode.Source: §2.2 · p. 8
  • The paper uses a kernel density estimator in practice and describes mean shift as an iterative procedure that approximates its gradient-ascent flow.As the step size tends to zero, mean shift approximates the flow of the estimated density.Source: §2.2 · p. 8

3 Gradient-Guided Density Peak Clustering

GGDPC modifies DPC by taking a gradient-ascent step before searching for a nearest observation of higher density. This shifts the search direction toward the density gradient while retaining the higher-density ordering at the original observation.

3 Gradient-Guided Density Peak Clustering

  • GGDPC takes a gradient-ascent step before each nearest-neighbor uphill search, using estimates of density and its gradient on the observed data.A natural gradient estimate is the gradient of the density estimate, though the procedure allows another consistent gradient estimator.Source: §3 · p. 9
  • The higher-density constraint remains anchored at the original observation rather than the gradient-updated point.The paper motivates this choice by noting that the updated point may have no higher-density observations near the global mode and may create spurious centers near a local mode.Source: §3 · p. 9
  • The gradient step provides a stable search direction, while the subsequent nearest-neighbor search keeps the procedure on the observed data cloud.The paper describes this as preserving DPC’s computational advantage and interpretable graph structure.Source: §3 · pp. 9–10
  • GGDPC is designed to alleviate irregular cross-boundary propagation while behaving similarly to DPC near local modes where the gradient is small.The paper says the modification preserves DPC’s cluster-center identification mechanism.Source: §3 · p. 10

4 Convergence of GGDPC Clustering

The section studies GGDPC consistency through selected cluster centers and agreement with the population modal partition. It establishes modal consistency and examines assignment convergence under the adjusted Rand index, with an additional geometric condition for the latter.

4 Convergence of GGDPC Clustering

  • The section analyzes GGDPC consistency from two perspectives: selected cluster centers and agreement of assignments with the population modal partition.Source: §4 · pp. 10–11

4.1 Modal Consistency

  • Theorem 1 establishes modal consistency under A1 when η_n=o(1) and density and gradient estimates converge uniformly; A2 sharpens the Hausdorff-distance rate.Source: §4.1 · pp. 11–12

4.2 Convergence of the Adjusted Rand Index

  • Theorem 2 studies assignment convergence under the adjusted Rand index given A1–A3, where A3 requires local repulsion along regular separatrix boundaries.A3 specifically requires the Hessian of p to be strictly positive in the inward normal direction.Source: §4.2 · p. 13

5 GGDPC Dendrogram

This section characterizes the GGDPC dendrogram as a nested hierarchy equivalent to single-linkage clustering on the weighted GGDPC graph. It describes convergence to the population modal distance dendrogram, with small-scale branches collapsing and persistent upper-level structure converging, while merge topology can differ from the density cluster tree.

5.1 Definition and Computation

  • For thresholds λ ≤ λ′, the partition at λ refines the partition at λ′, so increasing the threshold produces successively coarser clusters.The partition is induced by the connected components of the truncated GGDPC graph, ignoring edge directions.Source: §5.1 · p. 14
  • The GGDPC dendrogram is identical to the single-linkage cluster tree induced by a dissimilarity matrix encoding GGDPC edge weights.The matrix assigns adjacent observations their edge weights and nonadjacent pairs a common value larger than every edge weight.Source: §5.1 · p. 15

5.2 Stability of the GGDPC Dendrogram

  • Without the non-degeneracy condition excluding flat tangential regions at modal projections, convergence of the sample mode’s uphill update to the population projection can be arbitrarily slow.The condition also requires a unique projection; the stated result assumes A4.Source: §5.2 · p. 16
  • The population modal distance dendrogram need not share the density cluster tree’s merge topology because their merge heights depend on projection distances and saddle-point density levels, respectively.The modal distance tree is constructed from a weighted tree on the population modes, with edge weights given by modal projection distances.Source: §5.2 · pp. 16–17
  • Under A1, A2, A4 and the stated vanishing estimation-error conditions, the GGDPC dendrogram converges in Gromov–Hausdorff distance to the population modal distance dendrogram.The result is stated for any deterministic sequence a_n → ∞; A4 requires unique, non-degenerate modal projections.Source: §5.2 · pp. 16–17
  • Non-modal observations’ shifts vanish, while shifts for local modes converge to their population modal projection distances.Source: §5.2 · p. 17
  • With η_n ≍ √q_n and a_n→∞ arbitrarily slowly, the dendrogram converges at the same polynomial rate as ARI in (10).Small-scale branches collapse while persistent upper-level structure converges to the modal distance dendrogram; this is illustrated in Figure 1’s bottom right panel.Source: §5.2 · p. 18

6 Stability of GGDPC Paths

Section 6 studies whether GGDPC uphill paths converge in length to population gradient-ascent flows. It establishes stability for an oracle procedure and for the sample procedure using estimated density and gradient.

6 Stability of GGDPC Paths

  • The target is convergence of the GGDPC uphill-path length to the population gradient-flow length from the same starting point to its mode.The analysis first treats the oracle procedure with known density and gradient, then the statistical procedure based on their estimates.Source: §6 · p. 18, §6.1 · p. 18

6.1 Oracle GGDPC Path Length

  • Oracle GGDPC path length is stable even when starting points approach basin boundaries, under regularity conditions controlling separation from boundary saddles.The result relies on assumptions including C1-linearization near relevant saddle points.Source: §6.1 · p. 19

6.2 Stability of the Sample GGDPC Path Length

  • The sample GGDPC path converges under stated assumptions, with its rate additionally affected by gradient-estimation error.The rate is driven by gradient estimation when d = 1 and by sample discretization when d > 1; a projection modification near estimated local modes can substantially improve it.Source: §6.2 · pp. 20–21

7 Convergence of GGDPC Graph Distance and Density Waterfall

Section 7 defines a population analogue of GGDPC graph distance and establishes convergence to it. It also introduces density waterfalls and proves convergence of their empirical measures.

7.2 Density Waterfalls

  • Graph distance paired with estimated density gives a two-dimensional representation of the density landscape associated with each cluster.The global density waterfall plots graph distance on the x-axis and estimated density on the y-axis.Source: §7 · p. 21, §7.2 · p. 23

7.1 Stability of the GGDPC Graph Distance

  • The population graph distance adds gradient-flow lengths within modal basins to projection distances between successive basins.Figure 4 depicts the flow curves and modal projections whose lengths make up the distance.Source: §7.1 · p. 22, Figure 4 · p. 22
  • GGDPC graph distance converges to a deterministic population analogue under the stated assumptions, and fixed-threshold truncated distances have the same rate.When the threshold parameter is fixed, some assumptions become unnecessary and the rate improves.Source: §7.1 · p. 23

7.2 Density Waterfalls

  • The empirical density waterfall measure converges to its population counterpart in Wasserstein-1 distance, with the same conclusion for fixed admissible local thresholds.Its convergence rate inherits the trade-off between sample discretization and gradient estimation found for path length.Source: §7.2 · p. 24

8 Empirical Studies

The empirical studies compare GGDPC with DPC-type methods on a two-component Gaussian mixture and illustrate it on Old Faithful eruption data. On the mixture, GGDPC balances clustering accuracy and computational efficiency; the real-data structure is assessed qualitatively.

Old Faithful illustration

  • The Old Faithful illustration can only be assessed qualitatively because ground-truth labels are unavailable for the real-world data.The data record 272 eruptions.Source: §8 · p. 25

Empirical comparison on the two-component Gaussian mixture

  • The comparison includes original DPC and several DPC-type variants, with competing methods given oracle-favorable tuning where applicable.For methods requiring k-nearest-neighbor searches, k is selected to maximize ARI against ground-truth labels.Source: §8 · pp. 25–26
  • GGDPC attains among the highest ARI values while requiring substantially less computation than most competing DPC-type methods, without ground-truth information for tuning.The comparison reports ARI and running time over 1,000 Monte Carlo replications; reported GGDPC times exclude optional dendrogram construction.Source: §8 · p. 26
  • In the overlapping Gaussian-mixture experiment, DPC-MDNN’s single-linkage construction can create neighborhood chains between components and merge most observations.The text notes that average or complete linkage may alleviate this behavior, but those modifications are outside the cited procedure.Source: §8 · p. 26

9 Discussion

The discussion frames GGDPC as a more stable DPC variant with a population-level interpretation, and reviews its consistency results, convergence-rate challenges, and broader use of waterfall plots.

  • GGDPC ascending paths approximate the population density's gradient-ascent flow, giving their empirical stability a direct population-level geometric interpretation.Source: §9 · p. 26
  • Five complementary consistency results cover local modes, ARI, dendrograms, graph distance, and density waterfalls, with rates requiring progressively finer path control for the geometric measures.Modal consistency requires the weakest control, followed by ARI and dendrogram convergence; graph distance and density waterfalls require substantially finer path control.Source: §9 · p. 26

1. Improved rates of convergence

  • Downstream convergence results depend relatively strongly on ambient dimension, partly because of sample discretization within modal neighborhoods.Source: §9 · p. 26
  • Mapping observations in estimated modal neighborhoods directly to their estimated local modes is proposed as a refinement that improves Theorem 7's rate and downstream convergence.Source: §9 · p. 26

2. Minimax theory for separatrices and gradient flow length

  • Minimax theory remains less developed for separatrices and gradient-flow lengths, whose nonlocal structure lets local estimation errors propagate and complicate sharp bounds.Source: §9 · p. 27

3. Waterfall plots as visualization tools for local signatures

  • A waterfall plot pairs one-dimensional distances to a cluster representative with density values, compactly summarizing local cluster structure when direct data visualization is difficult.Source: §9 · p. 27
  • Waterfall plots are not specific to DPC: mean shift can use accumulated path length to a local mode, while k-means can use distance to the assigned centroid.Source: §9 · p. 27

Declaration of the Use of AI-Assisted Technologies

The authors disclose using ChatGPT for proof exploration, exposition, language editing, and simulation-code refinement, while stating that they independently reviewed and verified the work.

Supplementary Materials to “Gradient-Guided Density Peak Clustering”

The supplement explains fixed edge scores and optional low-density screening in GGDPC, and provides proof support for local-mode consistency via a uniform sample coverage lemma.

A Technical Concepts in Dynamical Systems

  • The supplement defines stable and unstable manifolds for gradient-ascent flow and introduces smooth conjugation and linearization concepts used in its analysis.At a non-degenerate critical point, the stable and unstable manifold tangent spaces correspond to the negative- and positive-eigenspaces of the density Hessian.Source: A Technical Concepts in Dynamical… · p. 34

B GGDPC Dendrograms Under General Edge Scoring Rules

  • Any fixed edge-scoring function yields a valid hierarchy: partitions at lower thresholds refine those at higher thresholds, without requiring score monotonicity, continuity, or smoothness.The score may jointly use uphill distance and source density; changing the threshold changes which edges are retained.Source: B GGDPC Dendrograms Under General Edge… · pp. 35–36

B.1 Practical Choice of the Edge Score

  • The paper recommends scoring edges by uphill distance alone, preserving a geometric distance interpretation and supporting the stated dendrogram stability theory; general scores need additional assumptions for convergence.This choice also keeps dendrogram heights on the same distance scale as the GGDPC decision diagram.Source: §B.1 · p. 36

B.2 Optional Density Screening

  • Optional density screening uses the score s_α(w, p) = w · 1{p ≥ q_α}, where q_α is the empirical lower α-quantile of estimated densities, to prevent very low-density observations from becoming centers.The passage gives α = 0.05 as an example level; screening addresses low-density observations that could otherwise create small dendrogram branches.Source: §B.2 · p. 36
  • Low-density observations retain their outgoing edges for every λ, cannot become centers solely from large uphill distances, and attach to the graph rather than being labeled noise.The screening rule is distinct from explicit noise-detection procedures.Source: §B.2 · p. 37

C Proof of Theorem 1

  • The proof of Theorem 1 establishes GGDPC cluster-center consistency with population local modes after a uniform sample coverage lemma.Source: C Proof of Theorem 1 · p. 37

C.1 A Uniform Sample Coverage Lemma

  • Under Assumption A1(a) and bounded density on compact support, the coverage lemma concludes that its uniform sample-coverage guarantee holds for all sufficiently large n.The excerpt does not provide the guarantee's full rate or expression.Source: §C.1 · pp. 37–38

C.2 Main Proof of Theorem 1

The proofs establish localization and classification of sample modes and develop a separatrix-repulsion lemma, with assumptions A3–A5 illustrated using a two-Gaussian mixture. Under A1 and A3, Lemma D.1 establishes local repulsion from each modal-basin separatrix using a C² function comparable to distance from the boundary.

C.2 Main Proof of Theorem 1

  • With probability tending to one, the proof bounds sample-mode localization by a constant times q_n + ||b_g − ∇p||∞ under the stated differentiability condition.The bound applies to the maximal distance between sample and true local modes.Source: §C.2 · p. 40
  • Away from the true modes, every observation has a nearby higher-density observation with high probability, so no other observation is a sink of the truncated graph.The proof constructs nearby points by following the population gradient flow or, at a non-modal critical point, moving along a positive-eigenvalue direction.Source: §C.2 · pp. 40–41
  • With probability tending to one, a sample mode belongs to the truncated center set exactly when its corresponding ψ_j exceeds λ, yielding a one-to-one correspondence and equal cardinalities.For ψ_j < λ the sample mode is excluded; for ψ_j > λ it is included.Source: §C.2 · pp. 41–42

D Proof of Theorem 2

  • Theorem 2’s proof introduces a local repulsion lemma from the separatrix without requiring Assumption A5, then uses it to prove the theorem.The proof section begins with an example illustrating Assumptions A3, A4, and A5.Source: D Proof of Theorem 2 · p. 42

D.1 Example: A Two-Gaussian Mixture for Assumptions A3, A4, and A5

  • A two-Gaussian mixture illustrates A3’s normal repulsion, satisfies A4 when modal heights differ, and verifies A5 through local C1-linearizability near the saddle.For A3, the normal Hessian is bounded away from zero on compact subsets of the regular separatrix; for A5, the example uses the smoothness of p and Hartman’s spectral condition.Source: §D.1 · pp. 43–44

D.2 Local Repulsion Lemma

  • Under A1 and A3, each modal basin admits a local C2 repulsion function comparable to distance from its separatrix.The lemma supplies positive neighborhood and comparison constants.Source: §D.2 · pp. 44–45
  • At regular separatrix points, the proof uses signed distance positive inside the basin, flow invariance, and a Taylor expansion.The boundary is locally a C2 hypersurface, and Assumption A3 supports the resulting bound.Source: §D.2 · pp. 44–45
  • At boundary saddles, the proof uses a C2 local stable manifold of dimension d −1 and a chart whose signed first coordinate defines the basin-side function.Compactness of the separatrix completes the argument.Source: §D.2 · p. 45

D.3 Main Proof of Theorem 2

The proof of Theorem 2 establishes that GGDPC paths remain within population modal basins under a boundary-distance condition, then relates observation-wise misclustering to ARI. Theorem 5’s proof sets up a Gromov–Hausdorff comparison for dendrogram ultrametrics using mapping distortions.

D.3 Main Proof of Theorem 2

  • Theorem 2’s proof proceeds through one-step control near the separatrix, discrete basin invariance, misclustered-observation control, and conversion to ARI.The one-step argument uses a nearby observation to the population gradient-flow update and establishes admissibility for the empirical update.Source: §D.3 · pp. 45–47
  • GGDPC iterations stay in the initial population basin with probability tending to one when the starting point is sufficiently far from its boundary.The proof first controls a one-step update near the separatrix, then establishes basin invariance for the path and pairs empirical modes with population modes.Source: §D.3 · pp. 46–47
  • The proof converts observation-wise misclustering into an ARI bound by noting that every disagreeing pair contains at least one misclustered observation.It defines pair counts for the population and GGDPC partitions and rearranges the ARI expression in terms of false positives and false negatives.Source: §D.3 · pp. 47–48

E Proof of Theorem 5

  • Theorem 5’s proof represents dendrogram comparison through Gromov–Hausdorff distance between the associated ultrametric spaces, using forward, reverse, and joint mapping distortions.The joint distortion penalizes departures from an approximate inverse relationship between the two mappings.Source: E Proof of Theorem 5 · p. 49

E.1 Proof of Proposition 4

The proofs relate thresholded GGDPC graphs to single-linkage clustering and establish stability of empirical modal projections and recovery of the population mode tree. They construct correspondences between observations and population modes to compare modal-tree paths, introduce basin hitting times, and address observations near non-modal critical points by moving along a positive-curvature direction.

E.1 Proof of Proposition 4

  • For λ≥dmax, both procedures return one cluster; below dmax, thresholded GGDPC and single linkage induce the same clusters through connected paths in Gλ.Source: §E.1 · pp. 49–50

E.2 A Stability Lemma of the Empirical Modal Projection

  • The empirical modal projections converge to their population projections and, with probability tending to one, each remains in the same parent basin of attraction.The proof establishes max_j≥2 ||bzj,n − zj|| = oP(1).Source: §E.2 · pp. 50, 52

E.3 Main Proof of Theorem 5

  • With probability tending to one, vertices with outgoing weight above λ0 are the non-root sample modes, and contracting their components yields exactly the population mode tree.The empirical edge c mj,n→bzj,n becomes the population edge mj→mπ(j).Source: §E.3 · p. 53
  • The proof bounds the GGDPC update shift by the distance to an admissible point plus twice the step size times the estimated gradient norm.The displayed bound is O_P(ϵ_n + η_n||bg(X_i)||).Source: §E.3 · p. 54
  • Near a non-modal critical point, the proof shifts an observation along a positive-eigenvalue direction and finds a nearby admissible observation with higher estimated density.The higher-density comparison holds uniformly with probability tending to one.Source: §E.3 · pp. 54–55
  • The proof maps each observation to its basin’s mode, with empirical and population paths sharing the same modal edges and their population ultrametric equal to the maximum edge weight.For observations mapped to the same mode, the population ultrametric distance is zero.Source: §E.3 · pp. 55–56

F Proof of Theorem 7

  • Theorem 7’s proof sets up a basin around a local mode and defines hitting times for population gradient ascent and oracle GGDPC paths to a modal neighborhood.It also introduces the stopping time and path length for a finite GGDPC path within the basin.Source: F Proof of Theorem 7 · pp. 56–57

F.1 Proof of Lemma 6

This section develops supporting conditions and lemmas for the stability and behavior of sample GGDPC paths, including uphill updates, saddle passages, basin invariance, and termination near local modes. It combines these controls in proofs concerning sample-path properties and finite population graph distance.

F.1 Proof of Lemma 6

  • A trajectory starting at distance at least r from a basin boundary remains at least C_S r away, and a radius-C_Sr/2 tube around it stays in the basin.The proof combines estimates near regular boundary points and finitely many saddle points, then takes the minimum of their constants.Source: §F.1 · p. 58

F.2 Other Supporting Lemmas

  • Under Assumption A1(a-b), Lemma F.1 establishes a uniform local sample-count bound.Source: §F.2 · pp. 58–59
  • Near a non-degenerate local mode, the gradient norm is bounded proportionally to distance from the mode, and the local path-length function is O(ϵ) on an ϵ-ball.The gradient also points toward the mode in the stated radial inequality.Source: §F.2 · p. 59
  • For compact subsets of a basin, the truncated gradient-flow length function is C2 near the relevant trajectories and satisfies ∇L_ϵ(x)^T∇p(x) = −||∇p(x)||.The lemma also gives bounds on its derivatives away from the modal core.Source: §F.2 · p. 60
  • Under Assumption A1, Lemma F.4 establishes a population bound for the 1NN uphill shift uniformly outside a shrinking modal core.The stated region is within a fixed neighborhood of the mode but outside B(m*, ϵ_n).Source: §F.2 · p. 61
  • Lemma F.5 controls the length of oracle GGDPC paths that enter the shrinking modal core and remain in the basin until termination.Source: §F.2 · p. 62
  • For fixed ϵ, Lemma F.6 establishes stability of oracle GGDPC path length under its stated sampling-rate and boundary-separation conditions.The result is uniform over the specified compact subset away from the basin boundary.Source: §F.2 · pp. 63–64
  • Under Assumptions A1, A3, and A5, Lemma F.7 establishes length stability for trajectories in a separatrix tube outside the modal core.The result applies for sufficiently small tube-width and core-radius parameters.Source: §F.2 · p. 64
  • Away from saddle neighborhoods, gradient-flow segments lie in compact regions where the flow is C1 with uniformly bounded derivatives; δ-dependent factors can arise only near boundary saddles or ∂Ca.The saddle analysis uses a linearizing neighborhood and considers paths whose endpoints lie on the same side of the local stable manifold.Source: §F.2 · pp. 64–66
  • Under Assumptions A1, A3, and A5, the 1NN uphill shift admits a bound uniformly over a shrinking tube, with probability tending to one.The lemma also extends the argument to points in a safe region whose distance from the basin boundary is at least cδn.Source: §F.2 · pp. 68, 70
  • The oracle GGDPC path remains in a shrinking tube around the population gradient-flow path until entering a local-mode neighborhood, with probability tending to one.The proof combines control away from critical points, contraction near the mode, and a saddle-crossing bound.Source: §F.2 · pp. 70–71

F.3 Main Proof of Theorem 7

  • In the proof of Theorem 7, basin invariance keeps the oracle path in the tube, allowing the uphill-shift bound to be applied inductively before the mode neighborhood is reached.The proof identifies the rate derivation for Term II as the major change and handles points away from saddles, near the mode, and near boundary saddles.Source: §F.3 · pp. 71–72
  • The Theorem 7 proof closes by combining new bounds for Terms I–III with (67).Source: §F.3 · p. 73

G Proof of Theorem 8

  • Theorem 8’s proof uses the local sample uphill condition for sample bounds and path invariance within a basin, then combines sufficient conditions and supporting lemmas.One sufficient condition resembles Assumption A2 in the main paper.Source: G Proof of Theorem 8 · pp. 73–74

G.1 Local Sample Uphill Condition

  • Under the stated observation condition—Xi ∈ B(x + ηn bg(x), ζn) and bp(Xi) > bp(x)—Assumption A6 (local sample uphill availability) holds with Cup = 1 with probability tending to one.Source: §G.1 · p. 75

G.2 Supporting Lemmas

  • The boundary-saddle path lemma shows that, with probability tending to one, a sample path segment remains on the same side of the local stable manifold during passage.The lemma considers a sufficiently small fixed saddle neighborhood and a segment that traverses it once outside the terminal modal neighborhood.Source: §G.2 · p. 76
  • Estimated critical points are uniquely located near population critical points, with no other critical points near C; their gradients and density differences satisfy local bounds.For local modes, the estimated Hessian is uniformly negative definite nearby.Source: §G.2 · p. 78
  • Lemma G.4 concerns sample updates before the terminal modal neighborhood, under A1, A2, A3, and A5, with uniform density and gradient estimation errors of oP(1) and oP(δn), respectively.Source: §G.2 · p. 79
  • With probability tending to one, sample paths stay in C_a until entering the modal core, where c_ma,n becomes the terminal vertex within the basin.The supporting lemmas also control the remaining within-basin path length.Source: §G.2 · pp. 80–81

G.3 Main Proof of Theorem 8

  • Theorem 8’s proof combines regular-segment error bounds with controls near saddle boundaries and in the modal region to obtain its final conclusion.The proof treats the saddle boundary using Lemma G.2 and separately bounds updates in the modal region outside the core.Source: §G.3 · pp. 82–83

H.1 Essential Uniform Finiteness of the Population GGDPC Graph Distance

  • Under Assumption A1 and convergent gradient flows, the population graph distance is finite; with Assumption A4, it is uniformly bounded on C \ N_C.The essential supremum may be taken with respect to either Lebesgue measure or P.Source: §H.1 · p. 83

H.2 Main Proof of Theorem 9

The proof parts establish high-probability agreement between sample and population modal structure and a uniform graph-distance bound, using a dyadic-partition argument for Term II combined with Term I. They also develop integrated graph-distance control near separatrices for Theorem 10.

H.2 Main Proof of Theorem 9

  • With probability tending to one, the nearest observation to a point outside the specified separatrix neighborhood lies in the same modal basin and remains order δ_n from its relative boundary.Source: §H.2 · p. 84
  • The empirical modal edge from each nonprimary sample mode enters the component associated with its population-mode parent with probability tending to one.Consequently, the empirical modal sequence agrees with the population sequence.Source: §H.2 · p. 85
  • Theorem 9’s proof establishes the asserted uniform rate for the difference between empirical and population graph distances.The proof absorbs the displayed error terms into this rate under the stated rate conditions.Source: §H.2 · pp. 85–86

I.1 An Integrated Graph Distance Lemma

  • The integrated graph-distance lemma controls GGDPC path length by dividing paths into regular, critical-annular, and shrinking-core regions.The proof notes that the separatrix neighborhood has Lebesgue measure O(δ), and that the critical-annulus contribution is O(1) uniformly over starting vertices; the result also holds for fixed λ outside the listed ψ_j values.Source: §I.1 · pp. 86, 89

I.2 Main Proof of Theorem 10

  • Theorem 10’s proof starts from bounded population graph distance and splits its comparison into a coupled-observation term and a graph-distance term across regions near and far from separatrices.Source: §I.2 · pp. 90–91

H.2 Main Proof of Theorem 9

  • The proof bounds Term II using a dyadic partition after rescaling the compact support to [0, 1]^2, then combines the Term I and Term II rates.The samples are described as i.i.d. on a fixed compact rectangle; the partition controls mass imbalance on sets of diameter at most order 2^-k, with Markov's inequality used in the Wasserstein bound.Source: §I.2 · p. 91
Loading 2610.01050v1…