Research map / Learning theory and algorithms / Sample complexity

A (1+?)-Approximation for Ultrametric Embedding in Subquadratic Time

AAAI 2025 · Learning theory and algorithms › Sample complexity · approach: Learning under log-concave distributions · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives the first subquadratic algorithm for arbitrarily precise (c-approximation, (1+ε)) best ultrametric fit via a new γ-Kruskal tree construction without spanners and a dynamic approximate farthest-neighbor structure for cut weights.

Problem

Best ultrametric fit (BUF): finding an ultrametric that best preserves Euclidean distances (minimum maximum distortion) of n points; exact solution needs quadratic time and linkage methods are quadratic in time and space.

Approach

Computes a γ-Kruskal tree without building a γ-spanner, via a BFS over LSH buckets, and computes α-approximate cut weights with a dynamic approximate farthest-neighbor data structure (Pagh et al.) supporting merges; combining γ=α=√c yields a c-approximation in Õ(n^{1+1/c}) time.

Key results

• Theoretical result: a c-approximation of BUF in time Õ(n^{1+1/c}) for any c≥1, hence (1+ε)-approximation in Õ(n^{2-ε+o(ε^2)}).
• On MICE, PENDIGITS, SHUTTLE, FastUlt with c=4 achieves approximation 1.88, 1.53, 1.41 versus CVL's 3.27, 1.85, 2.41 at comparable runtime.
• Observed approximation factors are far below theory: the gamma-KT with theoretical factor 2.0 achieves observed 1.23 ± 0.23 with exact cut weights.

Measured effects reported in the paper

Surprising findings

• The α-ACW algorithm's multiplicative factor can be reduced from α to √α in practice while still over-approximating cut weights, since the AFN structure is very accurate.
• FastUlt is slower than CVL on large synthetic datasets, though it avoids the quadratic blow-up of single linkage.

Limitations

• Theoretical guarantee factor for cut weights is worst-case; practical implementation multiplies by √α, a heuristic deviating from the proven guarantee.
• On large synthetic datasets the algorithm is slower than the CVL baseline (e.g., 21m58s vs 1m54s for N=10^6, d=10).
• Only Euclidean spaces with d=O(log n) after JL reduction are covered.

Experimental setup

Datasets: IRIS DIABETES MICE PENDIGITS SHUTTLE synthetic uniform random points

Benchmarks: IRIS DIABETES MICE PENDIGITS SHUTTLE synthetic uniform random point sets

Metrics: approximation factor (distortion relative to optimal) running time (s)

Baselines: FKW exact quadratic algorithm CVL (Cohen-Addad et al. 2021) single linkage (fastcluster)

Builds on: Cohen-Addad et al. (2021) sqrt(2)-approximation for BUF Ultrametric fit framework (Chatziafratis et al.) Pagh et al. approximate farthest neighbor data structure Kruskal's algorithm Locality-sensitive hashing

Closest papers by meaning

• UltraTWD: Optimizing Ultrametric Trees for Tree-Wasserstein Distance (ICML 2025 · similarity 0.86)
• Euclidean Embedding of Data Using Local Distances (NeurIPS 2026 · similarity 0.85)
• Sparse Dimensionality Reduction Revisited (ICML 2024 · similarity 0.85)
• Learning Ultrametric Trees for Optimal Transport Regression (AAAI 2024 · similarity 0.84)
• Tree-Wasserstein Distance for High Dimensional Data with a Latent Feature Hierarchy (ICLR 2025 · similarity 0.84)
• Fast unsupervised ground metric learning with tree-Wasserstein distance (ICLR 2025 · similarity 0.84)